Граф предшествования (граф сериализации), понятие теории графов.
Граф предшествования для последовательности событий S состоит из узла для каждой подтвержденной транзакции в S стрелки из Ti в Tj если транзакция Ti предшествует или конфликтует с одной из Tj.
В заданном расписании S, охватывающем транзакции T1 и T2, T1 предшествует T2, если существуют действия A1 транзакции T1 и A2 транзакции T2, удовлетворяющие условиям: A1 выполняется раньше A2 A1 и A2 адресуют один и тот же элемент данных Хотя бы одно из действий A1 и A2 связано с операцией записи
Граф предшествования позволяет наглядно показать, является ли расписание условно-последовательным.
Пример
Time T1 T2 T3 1 read(A) 2 write(A) 3 Commit 4 write(A) 5 Commit 6 write(A) 7 Commit Рассмотрим данный пример. Расписание для него будет иметь следующий вид:
S: r1(A);w2(A);w1(A);w3(A);
Чтение r1(A) транзакции T1 Выполняется раньше записи w2(A) транзакции T2. Следовательно, T1 предшествует T2. Аналогично, T2 предшествует T3.
Для этого расписания граф предшествования будет таким:
Как видно, граф не содержит циклов, следовательно расписание является условно-последовательным с учетом конфликтов.
Рассмотрим теперь другой пример.
Time T1 T2 T3 1 read(A) 2 write(A) 3 read(B) 4 Commit 5 write(B) 6 Commit 7 write(A) 8 Commit S: r1(A);w2(A);r2(B);w1(B);w3(A);
T1 предшествует T2, вместе с тем, T2 предшествует T1. Очевидно, граф будет содержать цикл, и это показывает, что данное расписание не является условно-последовательным.
Ссылки Фундаментальные основы систем баз данных, 5-е издание, использование графов предшествования обсуждается в 17 главе. basic precedence graph generator by Laurens Stötzel, University of Duisburg-Essen, Germany
Категория:Семейства графов Категория:СУБД