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


Предикатные блокировки


Блокировка узла схемы в каком-либо режиме неявно приводит к блокировке в этом режиме всех узлов в XML-документе, которые соответствуют данному узлу схемы. Очевидно, что во многих случаях это будет приводить к блокировке лишних узлов XML-документа. Например, для запроса /price[. = 100] не нужно блокировать все узлы price, а достаточно заблокировать узлы price, значение которых равно 100.

Для решения указанной проблемы мы с каждой структурной блокировкой ассоциируем предикат. Этот предикат накладывает ограничение на значение узла в XML-документе. Таким образом, блокировка в XDGL состоит из двух частей: типа блокировки и предиката. Две блокировки (lock-type1, pred1) и (lock-type2, pred2) совместимы, если выполняется одно из условий:

  1. тип блокировки lock-type1 совместим с lock-type2 согласно таблице совместимости,
  2. конъюнкция предикатов pred1 и pred2 тождественно равна false.

Вообще говоря, проверка совместимости предикатов является NP-трудной задачей [], и поэтому в XDGL мы проверяем на совместимость только простые предикаты (сравнения с константами) для которых существуют полиномиальные алгоритмы проверки на совместимость [], а остальные предикаты отождествляем с true.




- Начало -  - Назад -  - Вперед -