Граф реконсиляции
Граф (гиперграф) реконсиляции RG определим как набор пяти множеств (V = V1
V2 VC , E = ED EP), где: - V1, V2 - множества вершин, соответствующих операциям исходных транзакций T' и T". VC - множество операций, применяемых в корректирующей транзакции. При проведении анализа каждой вершине на графе присваивается логический статус. Статус указывает, включается ли соответствующая операция в итоговый журнал или нет.
- ED, EP - множества ребер (гипер-ребер), которые соответствуют отношениям зависимости и порядка, установленным между операциями. Каждое ребро помечается семантическим ограничением, порождающим соответствующее отношение. Бинарные отношения графически представляются обычными линиями, а множественные отношения - прямоугольными элементами, опирающимися на узловые вершины.
Граф реконсиляции обладает рядом свойств, существенных для его конструктивного анализа. Так как предполагается, что каждая транзакция, участвующая в процессе реконсиляции, является корректной, ребра, соответствующие обратным импликациям t1 → ¬t2 и ¬t1 → t2, могут быть установлены только между вершинами, принадлежащим разным транзакциям. В то же время ребра, соответствующие прямым импликациям t1 → t2 и ¬t1 → ¬t2, могут появиться как внутри отдельных транзакций, так и в разных транзакциях. Аналогично, между парой вершин одной транзакции не может существовать противоположных отношений порядка, что противоречило бы возможности их одновременного применения.
Следующие свойства связаны с обобщающими идеями сильных цепей зависимости и предшествования.
Пусть RG(V,E) - граф реконсиляции. Путь v1(t1), v2(t2), ..., vn(tn)
V вдоль ребер зависимости e1(D1), e2(D2), …, en-1(Dn-1) ED, начинающийся в вершине v1(t1) и заканчивающийся в вершине vn(tn), назовем цепью зависимости (или vn зависит от v1), если только существует соответствующая последовательность отношений зависимости t1D1t2, t2D2t3, …, tn-1Dn-1tn, эквивалентная простой импликации t1Dtn.
Прямой зависимостью назовем цепь зависимости, эквивалентную импликации t1 → tn или ¬t1 → ¬tn. Обратной зависимостью будем называть цепь, эквивалентную импликации t1 → ¬tn или ¬t1 → tn.
В графе реконсиляции не существует циклов обратной зависимости. Если бы такой цикл был найден, это означало бы, что любой статус операции, приписанный ее вершине, не соответствует логическим отношениям. Это противоречит существованию тривиальных решений логической системы, в качестве которых всегда могут быть выбраны операции первой или второй транзакции.
Путь v1(t1), v2(t2), ..., vn(tn)
V на графе реконсиляции RG(V,E) вдоль ребер предшествования e1(P1), e2(P2), …, en(Pn-1) EP, начинающийся в вершине v1(t1) и заканчивающийся в вершине vn(tn), назовем цепью предшествования (или v1 предшествует vn), если только отношения предшествования P1, P2, …, Pn-1 устанавливают порядок t1 ∠ t2, t2 ∠ t3, …, tn-1 ∠ tn.В графе реконсиляции не существует циклов предшествования, содержащих только вершины какой-либо одной транзакции. В противном случае это также противоречило бы существованию тривиальных решений задачи.
