Рубрики

Граф прецедентов для тестирования сериализуемости конфликтов в СУБД

Необходимое условие: Сериализуемость конфликта

График приоритетности или график сериализации обычно используется для проверки конфликтности сериализуемости расписания.
Это ориентированный граф (V, E), состоящий из набора узлов V = {T 1 , T 2 , T 3 ……… .T n } и набора направленных ребер E = {e 1 , e 2 , e 3 ……………… e m }.
Граф содержит один узел для каждой транзакции T i . Ребро e i имеет вид T j -> T k, где T j — начальный узел e i, а T k — конечный узел e i . Ребро e i создается между узлами T j -T k, если одна из операций в T j появляется в расписании перед какой-либо конфликтующей операцией в T k .

Алгоритм может быть записан как:

  1. Создайте узел T на графике для каждой участвующей транзакции в расписании.
  2. Для конфликтующей операции read_item (X) и write_item (X) — Если Транзакция T j выполняет read_item (X) после того, как T i выполняет write_item (X), нарисуйте ребро от T i до T j в графе.
  3. Для конфликтующей операции write_item (X) и read_item (X) — Если Транзакция T j выполняет write_item (X) после того, как T i выполняет read_item (X), нарисуйте ребро от T i до T j в графе.
  4. Для конфликтующей операции write_item (X) и write_item (X) — Если Транзакция T j выполняет write_item (X) после того, как T i выполняет write_item (X), нарисуйте ребро от T i до T j в графе.
  5. Расписание S сериализуемо, если в графе приоритетов нет цикла .

Если в графе приоритетов нет цикла, это означает, что мы можем построить последовательное расписание S ', которое является конфликтным эквивалентом расписания S.
Серийное расписание S 'можно найти с помощью топологической сортировки ациклического графика приоритета. Таких графиков может быть больше 1.

Например,
Рассмотрим график S:

 S : r1(x) r1(y) w2(x) w1(x) r2(y) 

Создание графика приоритетов:

  1. Сделайте два узла, соответствующие Транзакции T 1 и T 2 .
  2. Для конфликтующей пары r1 (x) w2 (x), где r1 (x) происходит до w2 (x), нарисуйте ребро от T 1 до T 2 .
  3. Для конфликтующей пары w2 (x) w1 (x), где w2 (x) происходит до w1 (x), нарисуйте ребро от T 2 до T 1 .

Поскольку график является циклическим, мы можем сделать вывод, что он не конфликтен сериализуемо с любым расписанием последовательного расписания.
Давайте попробуем вывести последовательный график из этого графика, используя топологическое упорядочение.
Ребро T 1 -> T 2 говорит о том, что T 1 должен предшествовать T 2 в линейном порядке.
Ребро T 2 -> T 1 говорит о том, что T 2 должен предшествовать T 1 в линейном порядке.
Таким образом, мы не можем предсказать какой-либо конкретный порядок (когда график циклический). Поэтому из этого графика невозможно получить серийный график.

Рассмотрим другой график S1:

 S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x)

График для этого графика:

Поскольку график является ациклическим, расписание сериализуемо конфликтно. Выполнение топологической сортировки на этом графике даст нам возможное последовательное расписание, которое по конфликту эквивалентно расписанию S1.
В Топологической сортировке мы сначала выбираем узел с степенью 0, то есть T1. За этим последуют Т3 и Т2.
Таким образом, S1 конфликтизуемо сериализуемо, поскольку конфликтно эквивалентно последовательному расписанию T1 T3 T2.

Источник: книга по операционным системам, Silberschatz, Galvin and Gagne

Эта статья предоставлена Saloni Baweja . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Рекомендуемые посты:

Граф прецедентов для тестирования сериализуемости конфликтов в СУБД

0.00 (0%) 0 votes