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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

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

В заданном расписании S, охватывающем транзакции T1 и T2, T1 предшествует T2, если существуют действия A1 транзакции T1 и A2 транзакции T2, удовлетворяющие условиям:

  • A1 выполняется раньше A2</li>
  • A1 и A2 адресуют один и тот же элемент данных</li>
  • Хотя бы одно из действий A1 и A2 связано с операцией записи</li> Граф предшествования позволяет наглядно показать, является ли расписание условно-последовательным.

    Пример

    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

    Ссылки


    en:Precedence graph
  • Личные инструменты

    Served in 0.090 secs.