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

       

XDGL планировшик


В этом подразделе мы опишем алгоритм, в соответствии с которым действует XDGL для операции a(opi, t). (t обозначает идентификатор XML-транзакции).

  1. Вычислить множество всех путей в схеме, приводящих к данным, которые читаются или изменяются операцией a(opi, tj). Назовем это множество DP (data-path-set).
  2. Вычислить множество узлов nj схемы, которые соответствуют конечным узлам путей из DP. В случае, если на узел налагается предикат pj, ассоциировать его с этим узлом. Обозначим полученное множество через NP={(nj, pj)} (node-predicate-set).
  3. Вычислить множество всех узлов nj схемы (и их свойства propertiesj), в поддеревьях которых могут появиться фантомы. Обозначим полученное множество через PH={(nj, propertiesj)} (phantom-set).
  4. Если opi расширяет схему, то вычислить свойство propertiesi нового узла.
  5. Вычислить множество узлов схемы, которые прочитываются в результате выполнение операций locpath в a(opi, tj) (это множество включает в себя узлы, прочитанные locpath на промежуточных шагах). Назовем это множество RS (read-set).
  6. Для каждого nj ? {RS \ DP} установить блокировки (S, #t) и (IS, #t) на nj и всех предках nj соответственно.
  7. По следующим правилам установить для opi структурные блокировки:

    • Пусть opi - это операция Q. Для каждого nj ? NP:
      1. если nj соответствует узлу, атомизируемому при выполнении opi, то установить на nj блокировку (ST, pj), иначе установить на nj блокировку (S, pj);
      2. для каждого предка nj установить блокировку (IS, #t).

    • Пусть opi - это операция II. Для каждого nj ? NP:
      1. если nj соответствует целевым узлам II, то установить блокировку (SI, pj) на узел nj и блокировку (IS, #t) на всех его предков;
      2. если nj соответствует дополнительным ветвям locpath (необходимым для указания предиката) операции II, то установить на узел nj блокировку (ST, pj) (либо (S, pj), если для проверки предиката не требуется атомизация узла) и блокировку (IS, #t) на его предков;
      3. если nj соответствует новому узлу, который вставляется II операцией, то установить на узел nj блокировку (X, pj) и блокировку (IX, #t) на его предков.
    • Для операций IA или IB.
      выполнить шаги, аналогичные предыдущему пункту.
    • Пусть opi - это операция D. Для каждого nj ? NP:
      1. если nj соответствует целевым узлам D, то установить на узел nj блокировку (XT, pj) и блокировку (IX, #t) на его предков;
      2. если nj соответствует дополнительным ветвям locpath (необходимым для указания предиката) операции D, то установить на узел nj блокировку (ST, pj) (либо (S, pj), если для проверки предиката не требуется атомизация узла) и блокировку (IS, #t) на его предков.


    • Пусть opi - это операция RN. Для каждого nj ? NP:
      1. если nj соответствует целевым узлам RN (переименовываемому узлу и новому узлу, полученному при переименовании), то установить на узел nj блокировку (X, pj) и блокировку (IX, #t) на его предков;
      2. если nj соответствует дополнительным ветвям locpath (необходимым для указания предиката) операции RN, то установить на узел nj блокировку (ST, pj) (либо (S, pj), если для проверки предиката не требуется атомизация узла) и блокировку (IS, #t) на его предков.


  8. Для каждого nj ? PH установить блокировку (L, propertiesj).
  9. Если opi расширяет схему, то установить блокировку (IN, propertiesi) для всех предков узла, расширяющего схему.
  10. Если требуемую блокировку установить невозможно (она не совместима с уже установленной блокировкой), то блокировать выполнение операции a(opi, t) до тех пор, пока не будет освобождена конфликтующая блокировка.



Содержание раздела