Введение в базы данных Ограничения, присущие файловым системам

8.4.1 Теорема Есварана о сериализуемости
Общепринятым критерием правильности управления параллельной работой транзакций является способность к упорядочению: чередующееся выполнение заданного множества транзакций будет верным, если оно упорядочено, то есть при его выполнении будет получен такой же результат, как и при последовательном выполнении тех же транзакций. Концепция способности к упорядочению была впервые предложена Есвараном. Им была доказана важная теорема двухфазной блокировки.
Теорема Есварана: если все транзакции подчиняются протоколу двухфазной блокировки, то для всех возможных чередующихся графиков запуска существует возможность упорядочения.
Протокол двухфазной блокировки (или двухфазный протокол синхронизационных захватов) определяет следующие правила:
− перед выполнением каких-либо операций с некоторым объектом, транзакция должна заблокировать этот объект;
− после снятия блокировки, транзакция не должна накладывать никаких других блокировок.

Рисунок 8.5 - Протокол двухфазной блокировки
Таким образом, транзакция, которая подчиняется данному протоколу, характеризуется двумя фазами:
1) нарастания блокировок: накладываются блокировки, и производится работа с заблокированными объектами;
2) снятия блокировок: работа с ранее заблокированными объектами может продолжаться; на второй фазе блокировки только снимаются.
На практике вторая фаза часто сводится к единственной операции завершения транзакции (фиксация либо откат) с одновременным снятием всех блокировок. Если A и B являются любыми двумя транзакциями с графиком запуска, способным к упорядочению, то либо A логически предшествует B, либо B использует результаты выполнения транзакции A (символ  - работа с объектом БД; ○ — блокирование объекта;  — разблокирование). 
Если некоторая транзакция A не подчиняется протоколу двухфазной блокировки (и, следовательно, состоит не менее чем из двух операция блокирования и разблокирования), то всегда можно построить другую транзакцию B, которая при чередующемся выполнении вместе с A приводит к графику, не подлежащему упорядочению и неверному.