Транзакция как логическая единица работы базы данных. Изучение свойств операций: атомарности, согласованности, изолированности, долговечности. Проблемы, вызванные конкурентностью выполнения алгоритмов. Эквивалентность и сериализуемость конфликтов.
Аннотация к работе
Для поддержания согласованности данных в процессе транзакции применяются все правила, проверки, ограничения и триггеры.Isolation Свойство изолированности означает, что конкурирующие за доступ к базе данных транзакции физически обрабатываются последовательно, изолированно друг от друга, но для пользователей это выглядит так, как будто они выполняются параллельно.Durability Свойство долговечности трактуется следующим образом: если транзакция завершена успешно, то те изменения в данных, которые были ею произведены, не могут быть потеряны ни при каких обстоятельствах (даже в случае последующих ошибок).Транзакции, истории и расписания База данных: x , y , z , … Операции: r(x), w(x) Транзакции: конечная последовательность операций-r 1 (x)r 1 (y) w 1 (z) История: упорядоченная совокупность операций нескольких транзакций-r 1 (x)r 2 (x ) w 1 (x) w 2 (x) с 1 с 2 Расписание: префикс ИСТОРИИПРОБЛЕМЫ, вызванные конкурентностью выполнения Потеря обновлений-r 1 (x) r 2 (x) w 1 (x) w 2 (x) Несогласованное чтение-r 1 (x) r 2 (y) w 2 (y) r 1 (y) Грязное чтение - r 1 (x) w 1 (x) r 2 (x) w 2 (y) a 1Серийное расписание Расписание, в котором все операции любой транзакции либо предшествуют, либо следуют за операциями любой другой транзакции Серийное расписание всегда КОРРЕКТНОКОНФЛИКТЫ Пара операций из расписания, такая, что Операции принадлежат разным транзакциям Работают с одним элементом данных По крайней мере одна из двух-операция записи Конфликты присутствуют в любом нетривиальном РАСПИСАНИИЭКВИВАЛЕНТНОСТЬ и сериализуемость Множество конфликтов расписания содержит пары, в которых первая операция предшествует второй (и пары находятся в конфликте) Расписания эквивалентны, если их множества конфликтов совпадают Расписание называется сериализуемым , если оно эквивалентно по конфликтам серийному Сериализуемые расписания КОРРЕКТНЫКРИТЕРИЙ сериализуемости Граф конфликтов (граф сериализуемости ) Вершины соответствуют транзакциям Дуги проводятся для каждого конфликта в направлении конфликта Расписание сериализуемо по конфликтам тогда и только тогда, когда граф сериализуемости не содержит КОНТУРОВПЛАН доказательства Граф конфликтов серийного расписания не может иметь контуров, потому что транзакции упорядочены и все дуги направлены от начала к концу расписания Если граф не имеет контуров, эквивалентное серийное расписание можно построить с помощью топологической сортировки ГРАФАСЕРИАЛИЗУЕМОСТЬ по коммутативности Любые операции чтения коммутируют Любые операции над разными элементами коммутируют Расписание сериализуемо по коммутативности, если его можно преобразовать в серийное перестановками соседних операций Сериализуемость по коммутативности эквивалентна сериализуемости по КОНФЛИКТАМДИСПЕТЧЕР транзакций Модель СУБД: диспетчер (транзакций) и исполнитель запросов Требования к диспетчеру транзакций: корректность и производительность Пессимистические и оптимистические ПРОТОКОЛЫИСПОЛЬЗОВАНИЕ замков Операции установки lr (x ), lw (x ) и снятия замка ur (x ), uw (x ) Совместимость замков: замки для одного элемента данных несовместимы, если они устанавливаются разными транзакциями и по крайней мере один из них---на запись. Попытка установки несовместимого замка переводит транзакцию в состояние ожидания Проблемы, связанные с использованием замков: корректность, тупики, ПРОИЗВОДИТЕЛЬНОСТЬПРОТОКОЛ блокирования 2 PL Для каждой операции необходимо предварительно установить замок, все замки должны быть сняты до завершения транзакции Транзакция не может устанавливать новые замки после того, как она сняла какой-либо из ЗАМКОВКОРРЕКТНОСТЬ 2 PL Двухфазный протокол генерирует расписания, сериализуемые по КОНФЛИКТАМТУПИКИ W 2 (x) w 2 (y) r 1 (y) r 2 (x) Транзакции, попавшие в тупик, должны быть оборваны Граф ожиданий Вершины-активные транзакции Дуги проводится из ожидающей транзакции в транзакцию, установившую несовместимые замки Тупик имеет место тогда и только тогда, когда в графе ожиданий имеется КОНТУРРЕШЕНИЕ T1 Lock(A); Read (A); Управлением блокировками на сервере занимается менеджер блокировок, контролирующий их применение и разрешение конфликтов.Элементы для блокировок Отношения Блок данных Один КОРТЕЖДВА вида блокировки : блокировка записи - транзакция блокирует элементы таким образом, что запрос другой транзакции к этим элементам будет отменен ; блокировка чтения - транзакция блокирует элементы так, что запрос со стороны другой транзакции на блокировку записи этих элементов будет отвергнут, а на блокировку чтения - принят.Протокол для деревьев WTL База данных структурирована как дерево Протокол: Все замки-на запись Для установки замка необходимо иметь установленный замок на родительскую вершину (кроме корня дерева) Снятие замков возможно в любое время и не препятствует установке новых ЗАМКОВКОРРЕКТНОСТЬ WTL Граф сериализуемости ацикличен Пусть y-родитель x , и w 1 (x ) Для каждой изменяемой записи записывается новое значение: . Работа происходит только на уровне протокола.