XML - статьи



              

/A>Алгоритм вычисления выражений XPath, содержащих обратные оси


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

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

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

В соответствии с Информационным Пространством XML Infoset [], узлы XML-документа описываются информационными элементами, которые соединены между собой исключительно дочерними и родительскими связями. Поскольку вычисление выражения начинается от корневого узла и в дереве существуют только вертикальные связи между узлами, любой путь, позволяющий добраться до конкретного контекстного узла, с необходимостью будет проходить через его родительский узел; что доказывает индуктивный переход. Утверждение доказано.

Замечание 1   Некоторые реализации Информационного Пространства XML, например, Объектная Модель Документа (Document Object Model, DOM), дополнительно используют указатели и между соседними узлами-братьями, т.е. такими, которые имеют общий родительский узел. Наличие подобных горизонтальных связей не влияет на справедливость данного утверждения, поскольку при перемещении по горизонтальным связям родительский узел для контекстного узла остается постоянным. Данное замечание означает, что все последующие результаты в полной мере могут быть применены к Объектной Модели Документа и любой изоморфной ей модели.




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