XML - статьи

/A>Обоснование алгоритма


Обоснование рассмотренного в предыдущем разделе алгоритма вычисления выражений XPath на основе сохраненных в контексте предков контекстного узла производится следующей теоремой.

Теорема 1   При распределении количества предков по грамматическим правилам языка XPath в соответствии с вышеописанным алгоритмом вычисление выражения языка XPath может быть построено таким образом, что требуемые для вычисления обратных осей XPath предки контекстного узла всегда могут быть извлечены непосредственно из контекста, без необходимости иметь в дереве документа указатели с дочерних узлов на родительские узлы.

Доказательство 2   Доказательство теоремы проведем в 2 этапа. На первом этапе рассмотрим количество предков, которое требуется для вычисления каждой из осей языка XPath. На втором этапе покажем, что рассмотренное в алгоритме распределение количества предков между грамматическими правилами обеспечит для произвольного выражения языка XPath наличие требуемого количества предков для каждой из осей, встречающейся в этом выражении.

  1. Рассмотрим каждую из осей языка XPath и установим количество предков, необходимое для ее вычисления.

    • Ось

      parent по определению выбирает родительский узел для контекстного узла, поэтому для реализации данной оси необходимо иметь в контексте сохраненный родительский узел, что соответствует количеству предков, равному 1.

    • Оси

      ancestor и

      ancestor-or-self по определению выбирают всех предков контекстного узла (ось

      ancestor-or-self выбирает также контекстный узел). В соответствии с предлагаемым подходом вычисления выражений языка XPath реализация этих осей требует для себя хранения в контексте всех предков контекстного узла, что согласно нашему определению из раздела  соответствует количеству предков, равному +?.

    • Оси

      child,

      descendant,

      attribute и



      namespace обладают тем общим свойством, что каждая из них осуществляет спуск по дереву документа по крайней мере на глубину 1; поэтому реализация этих осей не требует обращения к предкам контекстного узла. Более того, примечательным для данных осей является то свойство, что исходный контекстный узел является родителем (а для оси


      descendant
       – предком) результирующего контекстного узла; следовательно, реализации этих осей при необходимости могут сохранять в контексте количество предков, на 1 большее того количества предков, которое находилось во входном контексте.


    • Оси

      self и

      descendant-or-self
      не требуют обращения к предкам контекстного узла, а также ввиду своей семантики не могут сохранить в контексте количество предков, большее, чем было сохранено во входном контексте.


    • При рассмотрении осей

      following-sibling
      и

      preceding-sibling
      необходимо заметить, что алгоритм разработан для представления XML-документов в виде SXML, где отсутствуют указатели между соседними узлами-братьями, и поэтому доступ к ним осуществляется через их (общий) родительский узел. В соответствии с таким способом вычисления, реализация данных осей должна требовать в контексте наличия сохраненного родителя контекстного узла, что соответствует количеству предков, равному 1.


    • Реализация осей

      following
      и

      preceding требует в контексте количество предков, равное +?, поскольку при выборе всех узлов XML-документа, следующих за контекстным узлом (для оси

      preceding
       – предшествующих контекстному узлу) в порядке документа, необходимо подниматься по дереву документа до корневого узла.


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



      Рассуждения по поводу количества предков для каждого из грамматических правил XPath приводились при рассмотрении алгоритма. Так, например, было отмечено, что шаги доступа (location steps) в пути доступа (location path) должны рассматриваться в обратном порядке, с той целью, чтобы каждый шаг доступа после своего вычисления сохранял в контексте количество предков, необходимое для вычисления последующих шагов. Аналогичные рассуждения по поводу распределения количества предков для остальных грамматических правил XPath повторяют рассуждения, сделанные при рассмотрении алгоритма, и поэтому здесь опущены.


    • Поскольку каждая из осей, встречающаяся в произвольном выражении XPath, в соответствии с алгоритмом получает для себя необходимое количество предков, это и означает возможность вычисления любой обратной оси XPath за счет извлечения предков контекстного узла непосредственно из контекста и доказывает утверждение теоремы.

      Замечание 2  При доказательстве теоремы попутно приведена схема вычисления для каждой из обратных осей XPath с помощью сохраненных в контексте узлов – предков контекстного узла.

      Замечание 3  Сформулированное в алгоритме распределение количества предков между грамматическими правилами языка XPath допускает для некоторых выражений XPath наличие сохраненных предков в контексте, полученном в результате вычисления всего выражения. В качестве примера подобного выражения рассмотрим путь доступа

      /descendant::tr[parent::table]

      выбирающий все узлы документа с именем

      tr
      , родительские узлы которых имеют имя

      table
      . Легко видеть, что в данном пути доступа от реализации оси

      descendant требуется сохранить в контексте количество предков, равное 1, поскольку внутри предиката используется ось

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


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