Концепция сериализуемости
Концепции транзакции и механизма блокировок хорошо документированы в литературе [BHG, PAP, PON, GR]. В следующих нескольких абзацах делается обзор терминологии, используемой в этой области.
Транзакцией называют упорядоченное множество операций, переводящих базу данных из одного согласованного состояния в другое. История моделирует перекрывающееся выполнение множества транзакций в виде линейно упорядоченной последовательности их операций чтения и записи (вставки, модификации, удаления) определенных элементов данных. Говорят, что две операции в истории конфликтуют, если они выполняются различными транзакциями над одним и тем же элементом данных, и хотя бы одна из них выполняет операцию записи этого элемента данных. Согласно [EGLT], это определение можно широко интерпретировать в зависимости от того, что понимать под "элементом данных". Это может быть строка таблицы, область страницы, целая таблица или коммуникационный объект, такой, например, как сообщение в очереди. Конфликтующие операции могут возникать не только на отдельных элементах данных, но и на множествах элементов данных, покрываемых предикатными блокировками.
Отдельная история приводит к образованию графа зависимостей (dependency graph), определяющего временные потоки данных между транзакциями. Операции зафиксированных транзакций представляются вершинами графа. Если в истории операция op1
транзакции T1 конфликтует с операцией op2 транзакции T2 предшествует этой операции, то пара <op1, op2> становится ребром графа зависимостей. Две истории считаются эквивалентными, если они включают одни и те же зафиксированные транзакции и один и тот же граф зависимостей. История называется сериализуемой, если она эквивалентна последовательной истории (serial history), т.е. если она имеет такой же граф зависимостей (межтранзакционный поток временных данных), как если бы все транзакции в ней выполнялись поочередно.
