Граф предшествования
Материал из Seo Wiki - Поисковая Оптимизация и Программирование
Граф предшествования (граф cериализация), понятие теории графов.
Граф предшествования для последовательности событий S состоит из
- узла для каждой подтвержденной транзакции в S
- стрелки из Ti в Tj если транзакция Ti предшествует или конфликтует с одной из Tj.
В заданном расписании S, охватывающем транзакции T1 и T2, T1 предшествует T2, если существуют действия A1 транзакции T1 и A2 транзакции T2, удовлетворяющие условиям:
[править] Пример
| 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.
Для этого расписания граф предшествования будет таким:
Файл:Graf pred 1.jpg
Как видно, граф не содержит циклов, следовательно расписание является условно-последовательным с учетом конфликтов.
Рассмотрим теперь другой пример.
| 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. Очевидно, граф будет содержать цикл, и это показывает, что данное расписание не является условно-последовательным.
Файл:Graf pred 2.jpg
[править] Ссылки
- Фундаментальные основы систем баз данных, 5-е издание, использование графов предшествования обсуждается в 17 главе.
- basic precedence graph generator by Laurens Stötzel, University of Duisburg-Essen, Germany
<imagemap>
Image:Wiki_letter_w.svg
| Для улучшения этой статьи желательно?:
|