ВВЕДЕНИЕ В СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

       

Теорема Есварана о сериализуемости


Концепция способности к упорядочению была впервые предложена Есвараном [50].

В этой работе был предложен протокол двухфазной блокировки:

  • Перед выполнение каких-либо операций с некоторым объектом, транзакция должна заблокировать этот объект.
  • После снятия блокировки, транзакция не должна накладывать никаких других блокировок.

    Транзакции, используемые в этом протоколе, не различаются по типам и считаются монопольными. Описанные выше протоколы доступа к данным с использованием S- и X-блокировок и протокол преднамеренных блокировок являются модификациями протокола двухфазной блокировки для случая, когда блокировки имеют различные типы.

    Есвараном сформулирована следующая теорема:

    Теорема Есварана. Если все транзакции в смеси подчиняются протоколу двухфазной блокировки, то для всех чередующихся графиков запуска существует возможность упорядочения.

    Протокол называется двухфазным, потому что он характеризуется двумя фазами:

  • 1 фаза - нарастание блокировок. Во время этой фазы накладываются блокировки, и производится работа с заблокированными объектами.
  • 2 фаза - снятие блокировок. Во время этой фазы блокировки только снимаются. Работа с ранее заблокированными данными может продолжаться.

    Работа транзакции может выглядеть приблизительно, как на рисунке:

    Рисунок 1 Работа транзакции по протоколу двухфазной блокировки

    На следующем рисунке показан пример транзакции, не подчиняющийся протоколу двухфазной блокировки:

    Рисунок 2 Транзакция, не подчиняющаяся протоколу двухфазной блокировки

    На практике, как правило, вторая фаза сводится к одной операции завершения транзакции (или отката транзакции) с одновременным снятием всех блокировок.

    Если некоторая транзакция A не подчиняется протоколу двухфазной блокировки (и, следовательно, состоит не менее чем из двух операция блокирования и разблокирования), то всегда можно построить другую транзакцию B, которая при чередующемся выполнении вместе с A приводит к графику, не подлежащему упорядочению и неверному.



    Содержание раздела