Многоверсионный вариант двухфазного

В этом разделе мы рассмотрим вариант широко известного двухфазного протокола синхронизации транзакций (2PL), адаптированного для применения в версионной базе данных.

Рассматривая алгоритм работы MVTO-планировщика, мы использовали ряд терминов, которые теперь определим строго. Будем различать три типа версии элемента данных.

Завершенные версии (commited versions). Эти версии, созданные теми транзакциями, которые уже успешно закончили свою работу.
Текущая версия (current version). Это последняя из завершенных версий.
Незавершенные версии (uncommited versions). Это версии, созданные теми транзакциями, которые еще находятся в работе.

В MV2PL планировщик следит за тем, чтобы в каждый момент времени существовало не более одной незавершенной версии. В зависимости от того, позволяется ли мы транзакциям читать незавершенные версии данных, различаются два варианта этого алгоритма. Мы будем одновременно рассматривать оба варианта MV2PL (с чтением незавершенных данных и без него). Сначала рассмотрим схему работы MV2PL в предположении, что все версии элементов данных сохраняются в базе. Затем обсудим вариант этого алгоритма, в котором допускается одновременное существование не более двух версий одного и того же элемента данных.

Все операции, которые обрабатывает планировщик, разделяются на два класса: обычные операции и финальные операции. Под финальной операцией понимается последняя операция транзакции перед ее завершением или же сама операция завершения (commit). Обе интерпретации допустимы. При этом каждая отдельная операция транзакции обрабатывается следующим образом.

Если операция не является финальной, то:
1. операция r(x) выполняется незамедлительно; ей сопоставляется последняя из завершенных к данному моменту версий x (или последняя из незавершенных версий x во втором варианте алгоритма);
2. операция w(x) выполняется только после завершения транзакции, записавшей последнюю версию x.
Если операция является финальной для транзакции ti то она откладывается до тех пор, пока не завершатся следующие транзакции: