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

Концепция способности к упорядочению была впервые предложена Есвараном [Eswaran K.P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of Consistency and Predicate Locks in a Data Base System //CACM. - 1976. - V.19, №11.]. В этой работе был предложен протокол двухфазной блокировки:

1. Перед выполнение каких-либо операций с некоторым объектом, транзакция должна заблокировать этот объект. 2. После снятия блокировки, транзакция не должна накладывать никаких других блокировок. Транзакции, используемые в этом протоколе, не различаются по типам и считаются монопольными. Описанные выше протоколы доступа к данным с использованием S- и X-блокировок и протокол преднамеренных блокировок являются модификациями протокола двухфазной блокировки для случая, когда блокировки имеют различные типы. Есвараном сформулирована следующая теорема: Теорема Есварана. Если все транзакции в смеси подчиняются протоколу двухфазной блокировки, то для всех чередующихся графиков запуска существует возможность упорядочения. Протокол называется двухфазным, потому что он характеризуется двумя фазами:  1 фаза - нарастание блокировок. Во время этой фазы накладываются блокировки, и производится работа с заблокированными объектами.  2 фаза - снятие блокировок. Во время этой фазы блокировки только снимаются. Работа с ранее заблокированными данными может продолжаться. Работа транзакции может выглядеть приблизительно, как на рисунке:

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

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