/A>Алгоритм вычисления выражений XPath, содержащих обратные оси
Идея алгоритма состоит в том, что по ходу вычисления выражения языка XPath мы будем запоминать те узлы обрабатываемого документа, которые являются предками для контекстного узла и которые потребуются при дальнейшем вычислении выражения. Как и сам контекстный узел, его предки будут храниться в контексте, над которым производится вычисление выражения XPath. В тот момент, когда вычисление выражения потребует адресации к родительскому узлу контекстного узла или другому его предку, требуемый узел будет сразу извлекаться из контекста. При данном подходе переход к предку контекстного узла не требует нового обращения к дереву документа благодаря тому, что требуемый узел уже был сохранен заранее. Мы можем корректно говорить о том, что при вычислении выражения XPath предки всегда посещаются раньше своих потомков, на основании следующего утверждения.
Утверждение 1 При вычислении выражения языка XPath над некоторым XML-документом, для того, чтобы выбрать в документе некоторый контекстный узел, всегда необходимо сначала посетить все узлы, которые являются для него предками.
Доказательство 1 Доказательство утверждения проведем индукцией по глубине документа. Поскольку вычисление выражения языка XPath начинается от корня документа, то базис индукции доказан, т.к. корень документа является предком для всех остальных узлов в документе.
В соответствии с Информационным Пространством XML Infoset [], узлы XML-документа описываются информационными элементами, которые соединены между собой исключительно дочерними и родительскими связями. Поскольку вычисление выражения начинается от корневого узла и в дереве существуют только вертикальные связи между узлами, любой путь, позволяющий добраться до конкретного контекстного узла, с необходимостью будет проходить через его родительский узел; что доказывает индуктивный переход. Утверждение доказано.
Замечание 1 Некоторые реализации Информационного Пространства XML, например, Объектная Модель Документа (Document Object Model, DOM), дополнительно используют указатели и между соседними узлами-братьями, т.е. такими, которые имеют общий родительский узел. Наличие подобных горизонтальных связей не влияет на справедливость данного утверждения, поскольку при перемещении по горизонтальным связям родительский узел для контекстного узла остается постоянным. Данное замечание означает, что все последующие результаты в полной мере могут быть применены к Объектной Модели Документа и любой изоморфной ей модели.
Организация вычисления выражений языка XPath с использованием сохраняемых в контексте предков контекстного узла будет основана на специальной реализации осей языка XPath. Реализация обратных осей (таких как parent, ancestor, preceding и др.) будет обеспечиваться благодаря наличию в контексте предварительно сохраненных там узлов – предков контекстного узла. Для того, чтобы необходимые для обратных осей предки контекстного узла были сохранены в контексте, нам также потребуется специальная реализация и тех осей, которые осуществляют спуск по дереву документа . Оси, осуществляющие спуск по дереву документа (например, оси child, descendant), должны отвечать также за то, чтобы сохранять в контексте узлы, которые были пройдены в процессе спуска (и которые станут предками для контекстного узла на последующих шагах доступа). Доказанное выше утверждение гарантирует, что предки контекстного узла всегда могут быть сохранены в контексте, до того как потребуется их использование.
При оптимизации вычисления обратных осей XPath за счет хранения в контексте предков контекстного узла желательно также добиться минимальности хранимой в контексте дополнительной информации. Мы будем стремиться к тому, чтобы хранить в контексте только тех предков контекстного узла, которые действительно потребуются при дальнейшем вычислении выражения XPath, и не включать в контекст остальных предков. Утверждается, что желаемого результата можно добиться за счет статического анализа выражения XPath. Под фазой статического анализа понимается такая фаза обработки, на которой выражение XPath анализируется без учета входных данных; в отличие от следующей за ней фазы динамического вычисления, когда выражение вычисляется по отношению к конкретному XML-документу.
