Версионный вариант алгоритма временных меток

Одним из наиболее старых и простых версионных алгоритмов является версионный вариант алгоритма временных меток (Multiversion Timestamp Ordering, MVTO). Как и в простом методе временных меток, описанном в предыдущем подразделе, в алгоритме MVTO порядок выполнения операций одновременно выполняемых транзакций задается порядком временных меток, которые получают транзакции во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее записала. Алгоритм MVTO не только следит за порядком выполнения операций транзакций, но также отвечает за трансформацию операций над объектами базы данных в операции над версиями этих объектов, т.е. каждая операция над объектом базы данных o

преобразуется в соответствующую операцию над некоторой версией объекта o.

При описании алгоритма будем использовать следующие обозначения. Как и раньше, временную метку, полученную транзакцией Ti

в начале ее работы, будем обозначать как t(Ti). Операция чтения объекта базы данных o, выполняемая в транзакции Ti, будет обозначаться как Ri(o). Для обозначения того, что транзакция Ti

читает версию объекта базы данных o, созданную транзакцией Tk, будем использовать запись Ri(ok). Для обозначения того, что транзакция Ti

записывает версию элемента данных o, будем использовать запись Wi(oi).

Алгоритм MVTO работает следующим образом.

Любая операция Ri(o)

преобразуется в операцию Ri(ok), где ok

– это версия объекта o, помеченная наибольшей временной меткой t(Tk), такой что t(Tk)

t(Ti). Другими словами, транзакции Ti

для чтения дается версия объекта o, созданная транзакцией Tk, которая не моложе Ti, но старше любой другой транзакции Tn, создававшей свою версию объекта o.
При обработке операции Wi(o)

выполняются следующие действия: