Отношения зависимости и порядка
Отношения зависимости между операциями D определяются логическими операторами отрицания и импликации следующим образом. Для операций t1, t2
T, если t1 → t2, то журнал должен содержать t2 при условии, что он содержит t1. Если ¬t1 → ¬t2, то в журнале должна отсутствовать операция t2, если в нем отсутствует операция t1. Эти отношения несимметричны, рефлексивны и транзитивны. Для операций t1, t2 T, если t1 → ¬t2, то в журнале не может присутствовать t2, если он содержит t1. Если ¬t1 → t2, то журнал должен содержать t2, если в него не входит t1. Эти отношения симметричны, не рефлексивны и не транзитивны. Эти четыре логические отношения с характеристическими функциями, приведенными в Таблице 1, рассматриваются как основные отношения зависимости. Также мы считаем полезным использование симметричных отношений эквивалентности t1 ~ t2 ≡ t1 → t2 
t2 → t1 и взаимоисключения t1 ⊕ t2 ≡ t1 → ¬t2 ¬t1 → t2. Отношение эквивалентности устанавливается между двумя операциями t1, t2 T и означает, что эти операции могут встречаться в транзакции T только совместно. Отношение взаимоисключения между t1, t2 T обязывает транзакцию T включать в себя либо t1, либо t2 и запрещает содержать обе эти операции или ни одну из них.
| 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 |
Таблица 1.Характеристические функции бинарных отношений зависимости.
В некоторых случаях приходится рассматривать более сложные множественные отношения между операциями. В общем виде они представляются характеристической функцией D(t1, t2, t3, …) и соответствующей таблицей значений, подобной Таблице 1.
В качестве примера рассмотрим множественное отношение кардинальности D(n:m)(t1+,…, t+I+ , t1-,…, t-I-). Данное отношение связано с ограничениями кардинальности ассоциаций и размерности коллекций элементов данных в объектно-ориентированной модели.
Оно считается выполненным, если
n ≤ card( T+ ) - card( T- ) ≤ m, где
T+ = { ti+, i
D(m:m)(t1+,…, t1-, …).
| t1+ T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| t2+ T | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| t1- T | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| t2- T | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| D(0:0) (t1+,t2+,t1-,t2-) | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| D(1:1) (t1+,t2+,t1-,t2-) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| D(2:2) (t1+,t2+,t1-,t2-) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
Часто требуется удовлетворить некоторое ограничение c = с(x1, x2, …), выраженное алгебраическим образом с помощью соответствующей логической функции нескольких переменных. Если конкурентные транзакции содержат операции модификации элементов данных, являющихся фактическими параметрами функции ограничения, то возможным способом сохранить целостность является принятие всех операций модификации первой транзакции или всех операций модификации второй транзакции. В этом случае между операциями устанавливается отношение алгебраической зависимости Dc (t1', t2', …,t1'', t2'',…), где операции первой транзакции t1', t2'
T' и операции второй транзакции t1'', t2'' T' модифицируют элементы данных, на которые наложено ограничение c(x1, x2,…).
Будучи выполненным, данное отношение приводит к выделению классов эквивалентности для операций каждой транзакции и исключению ситуаций одновременного их применения в результирующей транзакции:
D c (t1', t2',…,t1'', t2'',…) ≡ t1' ⊕ t1''
t1' ~ t2' t2' ~ t3' … t1'' ~ t2'' t2'' ~ t3'' …Отношение порядка или предшествования операций в транзакции P определим следующим образом. Для операций t1, t2
T, если t1 ∠ t2, то операция t1 должна появиться до операции t2 (не обязательно непосредственно перед ней) в любом решении, которое одновременно содержит операции t1 и t2. Отношение порядка несимметрично, не рефлексивно, но транзитивно. Так как отношение подразумевает наличие обеих операций в одной транзакции, отношение t1 ∠ t2 может быть установлено только между теми операциями, которые не связаны отношениями зависимости t1 → ¬t2 и t1 ⊕ t2 непосредственно или косвенно через другие отношения.Обсуждаемые отношения являются строгими в том смысле, что если операции не удовлетворяют некоторым установленным отношениям, то транзакция необходимо становится некорректной, что означает невозможность ее выполнения или потерю целостности воспроизводимыми данными. В ряде случаев могут быть рассмотрены более слабые отношения, обозначаемые
D
и P, которые совпадают со строгими отношениями D, P за исключением того, что они имеют достаточный, но не необходимый характер для корректности транзакции. Другими словами, иногда они могут быть не выполнены, не нарушая условия корректности транзакции и целостности данных. Поскольку риск нарушения все равно остается, предварительные решения (транзакции и данные), полученные без учета подобных отношений, должны быть дополнительно проверены на более поздних этапах рассмотренного выше процесса реконсиляции.
