Граф приоритета

Граф приоритетов , также называемый графом конфликтов. и сериализуемости граф , используется в контексте управления параллелизмом в базах данных . Это ориентированный граф , представляющий приоритет транзакций в расписании, отражаемый приоритетом конфликтующих операций в транзакциях. Расписание является сериализуемым для конфликтов тогда и только тогда, когда его график приоритета зафиксированных транзакций является ациклическим .

Граф приоритета для расписания S содержит:

• Узел для каждой зафиксированной транзакции в S
• Дуга от Ti _до Tj _, если действие Ti _{предшествует} конфликтует с одному из _и действий Tj ним. То есть действия принадлежат разным транзакциям, по крайней мере одно из действий является операцией записи, и действия обращаются к одному и тому же объекту (чтение или запись).

Циклы зафиксированных транзакций можно предотвратить, прервав нерешительную (ни зафиксированную, ни прерванную) транзакцию в каждом цикле графа приоритетов всех транзакций, которые в противном случае могут превратиться в цикл зафиксированных транзакций (а зафиксированная транзакция не может быть прервана). . Одна транзакция, прерываемая за цикл, необходима и достаточна для разрыва и устранения цикла (возможно большее количество прерываний, которые могут произойти при некоторых механизмах, но они не нужны для сериализуемости). Вероятность генерации цикла обычно невелика, но, тем не менее, такая ситуация тщательно обрабатывается, обычно со значительными накладными расходами, поскольку требуется корректность. Транзакции, прерванные из-за предотвращения нарушения сериализуемости, перезапускаются и немедленно выполняются снова.

Примеры графиков приоритета

Пример 1

$S={\begin{bmatrix}T1&T2\\R(A)&R(A)\\A=A*5&R(B)\\W(A)&B=B+A\\R(B)&W(B)\\B=B*10&\\W(B)&\\\end{bmatrix}}$

Пример 2

$D=R1(A)$ $R2(B)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

Граф приоритета графика D с 3 транзакциями. Поскольку существует цикл (длиной 2; с двумя ребрами) через зафиксированные транзакции T1 и T2, этот график (история) не является сериализуемым для конфликтов . Обратите внимание, что фиксация транзакции 2 не имеет никакого значения для создания графа приоритетов.

Пример 3

Пример тестирования сериализуемости

Алгоритм проверки сериализуемости конфликтов расписания S вместе с примером расписания.

$S={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\\end{bmatrix}}$

или

$S=R1(A)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

1. Для каждой транзакции T _x, участвующей в расписании S, создайте узел с меткой T _i на графе приоритетов. Таким образом, граф приоритета содержит T ₁ , T ₂ , T ₃ .
2. Для каждого случая в S, где T _j выполняет read_item (X) после того, как T _i выполняет write_item (X), создайте ребро (T _i → T _j ) в графе приоритета. В приведенном выше примере этого не происходит, поскольку чтение после записи не выполняется.
3. Для каждого случая в S, где T _j выполняет write_item (X) после того, как T _i выполняет read_item (X), создайте ребро (T _i → T _j ) в графе приоритета. В результате получается направленное ребро от T ₁ к T ₂ (поскольку T ₁ имеет R(A) до того, как T ₂ имеет W(A) ).
4. Для каждого случая в S, где T _j выполняет write_item (X) после того, как T _i выполняет write_item (X), создайте ребро (T _i → T _j ) в графе приоритета. Это приводит к появлению направленных ребер от T ₂ к T ₁ , от T ₂ к T ₃ и от T ₁ к T ₃ .
5. Расписание S сериализуемо тогда и только тогда, когда граф приоритета не имеет циклов. Поскольку T ₁ и T ₂ составляют цикл, приведенный выше пример не является (конфликт) сериализуемым.

Внешние ссылки

• Основы систем баз данных, 5-е издание. Использование графов приоритета обсуждается в главе 17, поскольку они относятся к тестам на сериализуемость конфликтов .
• Авраам Зильбершац , Генри Корт и С. Сударшан. 2005. Концепции системы баз данных (5-е изд.), Стр. 628–630. McGraw-Hill, Inc., Нью-Йорк, штат Нью-Йорк, США.