Граф предшествования

Граф предшествования (граф сериализации), понятие теории графов.

Граф предшествования для последовательности событий S состоит из

• узла для каждой подтвержденной транзакции в S
• стрелки из T_i в T_j если транзакция T_i предшествует или конфликтует с одной из T_j.

В заданном расписании S, охватывающем транзакции T₁ и T₂, T₁ предшествует T₂, если существуют действия A₁ транзакции T₁ и A₂ транзакции T₂, удовлетворяющие условиям:

• A₁ выполняется раньше A₂
• A₁ и A₂ адресуют один и тот же элемент данных
• Хотя бы одно из действий A₁ и A₂ связано с операцией записи

Граф предшествования позволяет наглядно показать, является ли расписание условно-последовательным.

Пример

Time	T1	T2	T3
1	read(A)
2		write(A)
3		Commit
4	write(A)
5	Commit
6			write(A)
7			Commit

Рассмотрим данный пример. Расписание для него будет иметь следующий вид:

S: r₁(A);w₂(A);w₁(A);w₃(A);

Чтение r₁(A) транзакции T₁ Выполняется раньше записи w₂(A) транзакции T₂. Следовательно, T₁ предшествует T₂. Аналогично, T₂ предшествует T₃.

Для этого расписания граф предшествования будет таким:

Как видно, граф не содержит циклов, следовательно расписание является условно-последовательным с учетом конфликтов.

Рассмотрим теперь другой пример.

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: r₁(A);w₂(A);r₂(B);w₁(B);w₃(A);

T₁ предшествует T₂, вместе с тем, T₂ предшествует T₁. Очевидно, граф будет содержать цикл, и это показывает, что данное расписание не является условно-последовательным.

Ссылки

• Фундаментальные основы систем баз данных, 5-е издание, использование графов предшествования обсуждается в 17 главе.
• basic precedence graph generator by Laurens Stötzel, University of Duisburg-Essen, Germany