Классика баз данных - статьи

       

Покажем что ограничения, которые мы


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

S = w1[x1]w1[y1]r2[y1]r3[x1]w2[z2]r3[z2]w2[x2]

Граф, составленный по правилам алгоритма SGT, будет содержать дуги (t1, t2), (t1, t3), (t2, t3):



Рис 2. Граф сериализации для плана S, составленный по правилам SGT.

Этот граф ацикличен. Однако для S не существует эквивалентного моноверсионного последовательного расписания. Действительно,  Поскольку t3 читает версию x, записанную t1 (r3[x1]), то t2, которая тоже пишет элемент x (w2[x2]), должна следовать в моноверсионном последовательном расписании либо после t3, либо перед t1. Но первый вариант невозможен из-за шага r3[z2], а второй – из-за r2[y1].

Таким образом, многоверсионный планировщик должен также специальным способом проверять согласованность шагов, создающих новые версии. Для этого в граф добавляются дополнительные дуги, которые фиксируют “позиции записи” в соответствующем последовательном расписании. Теперь мы можем описать общую схему работы MVSG-планировщика. Когда очередной шаг pi(x) поступает планировщику, он предпринимает следующие действия:
  1. Если это первое действие транзакции ti, поступившее планировщику, то соответствующий узел добавляется к графу конфликтов.
  2. Если это шаг ri(x), то выбирается подходящая версия xj, и в граф добавляется дуга (tj, ti) (поскольку, согласно нашим обозначениям, версию xj записала транзакция tj). Для всех других k, таких что wk(xk) является шагом tk, в граф добавляется либо дуга (tk, tj), либо дуга (ti, tk). В этом и состоит выбор “позиции записи”.
  3. Если это шаг wi(xi), то для каждой транзакции tk, которая прочитала, скажем, версию xj, нужно добавить либо дугу (ti, tj), либо дугу (tk, ti). Т.е. ti должна следовать либо до tj, либо после tk в соответствующем последовательном расписании.
  4. Если граф остается ацикличным, то изменения в графе фиксируются, а действие добавляется к списку запланированных. Иначе транзакция откатывается.



Содержание  Назад  Вперед