Interested Article - Граф предшествования
jan
- 2020-08-29
- 1
Граф предшествования ( граф сериализации ), понятие теории графов .
Граф предшествования для последовательности событий S состоит из
- узла для каждой подтвержденной транзакции в S
- стрелки из T i в T j если транзакция T i предшествует или конфликтует с одной из T j .
В заданном расписании S, охватывающем транзакции T 1 и T 2 , T 1 предшествует T 2 , если существуют действия A 1 транзакции T 1 и A 2 транзакции T 2 , удовлетворяющие условиям:
- A 1 выполняется раньше A 2
- A 1 и A 2 адресуют один и тот же элемент данных
- Хотя бы одно из действий A 1 и A 2 связано с операцией записи
Граф предшествования позволяет наглядно показать, является ли расписание условно-последовательным .
Пример
| Time | T 1 | T 2 | T 3 |
|---|---|---|---|
| 1 | read(A) | ||
| 2 | write(A) | ||
| 3 | Commit | ||
| 4 | write(A) | ||
| 5 | Commit | ||
| 6 | write(A) | ||
| 7 | Commit |
Рассмотрим данный пример. Расписание для него будет иметь следующий вид:
S: r 1 (A);w 2 (A);w 1 (A);w 3 (A);
Чтение r 1 (A) транзакции T 1 Выполняется раньше записи w 2 (A) транзакции T 2 . Следовательно, T 1 предшествует T 2 . Аналогично, T 2 предшествует T 3 .
Для этого расписания граф предшествования будет таким:
Как видно, граф не содержит циклов, следовательно расписание является условно-последовательным с учетом конфликтов .
Рассмотрим теперь другой пример.
| Time | T 1 | T 2 | T 3 |
|---|---|---|---|
| 1 | read(A) | ||
| 2 | write(A) | ||
| 3 | read(B) | ||
| 4 | Commit | ||
| 5 | write(B) | ||
| 6 | Commit | ||
| 7 | write(A) | ||
| 8 | Commit |
S: r 1 (A);w 2 (A);r 2 (B);w 1 (B);w 3 (A);
T 1 предшествует T 2 , вместе с тем, T 2 предшествует T 1 . Очевидно, граф будет содержать цикл, и это показывает, что данное расписание не является условно-последовательным.
Ссылки
- , использование графов предшествования обсуждается в 17 главе.
- basic by Laurens Stötzel, University of Duisburg-Essen, Germany
jan
- 2020-08-29
- 1
