/A> Введение
Язык XML Path (XPath) [1], разработанный Консорциумом Всемирной Сети, – это язык для адресации структурных частей XML-документа. Язык XPath является ключевым языком для платформы XML и изначально разрабатывался как основа для нескольких других языков обработки XML-данных; в частности, XSLT, XPointer и XQuery.
Поскольку большинство языков платформы XML не являются языками программирования общего назначения, при реализации законченных XML-приложений они обычно используются совместно с некоторым традиционным языком программирования. Комбинирование двух различных по своей природе языков (например, XPath и Java) приводит к проблеме, известной как несоответствие импеданса (impedance mismatch) [2].
Барьер между языками платформы XML и языками программирования общего назначения может быть снят за счет обработки XML-данных функциональными методами. В основе данного подхода лежит SXML – реализация Информационного Пространства XML в виде S-выражений [3]. Язык функционального программирования Scheme семейства Лисп использует S-выражения для представления и своих данных, и своего кода, что позволяет создать единую среду для написания XML-приложений. Язык Scheme [4] – это один из самых лаконичных и компактных языков, применяемых на практике, и получил широкое признание как скрипт-язык [5]. На Scheme были реализованы инструменты для обработки SXML-документов, совместимые со спецификациями Консорциума Всемирной Сети и обеспечивающие бесшовную интеграцию языков платформы XML с языком программирования высокого уровня.
Язык XPath предоставляет приложению возможность навигации по иерархической структуре XML-документа [1]. В частности, приложению, производящему обработку XML-данных, может потребоваться выбрать родительский узел или более далеких предков для данного узла дерева XML-документа. Для обеспечения заданной функциональности спецификация языка XPath предоставляет обратные оси – такие как parent,
ancestor и ряд других, – которые позволяют выбрать узлы, предшествующие данному узлу в порядке обхода узлов в дереве документа. Узел в Модели данных языка XPath [1] (и, в более общем случае, информационная единица в Информационном Пространстве XML [6]) имеет свойство «родитель», представляющее собой указатель с данного узла на его родительский узел. Документ в SXML является S-выражением и поэтому не обладает подобными указателями, поскольку S-выражения моделируют ориентированные деревья, по определению не имеющие указателей в направлении к корню [7].
Может казаться, что с помощью SXML нельзя полностью смоделировать Информационное Пространство XML и Модель данных XPath. Так, в SXPath – реализации функциональными методами языка XPath для документов на SXML – до настоящего времени проводилось очень неэффективное во временном отношении вычисление обратных осей XPath, что обусловлено отсутствием указателей с дочерних узлов на родительские узлы в SXML. Однако в данной статье мы покажем, что возможно организовать вычисление выражений XPath таким образом, что наличие указателей с дочерних узлов на родительские узлы становится необязательным. В работе предлагается алгоритм, оптимизирующий вычисление обратных осей языка XPath над SXML-документами и документами, не имеющими указателей с дочерних узлов на родительские узлы. Предложенный алгоритм был полностью реализован на языке функционального программирования Scheme как расширение к SXPath. Проведенные эксперименты свидетельствуют о значительном увеличении производительности SXPath при вычислении над SXML-документами выражений языка XPath, содержащих обратные оси.
Применение предлагаемого в статье алгоритма не ограничивается случаем, когда обрабатываемые древовидные данные представлены в виде SXML, но может использоваться и в других случаях – когда возвращение к родительскому элементу является невозможным или нежелательным. Например, предлагаемый алгоритм может оптимизировать вычисление выражений языка XPath над потоковыми данными, поскольку обеспечивает возможность последовательного просмотра документа в одном направлении, без необходимости возвращаться к родительским элементам, являющимся с точки зрения порядка документа предшественниками для своих дочерних узлов.
Необходимо отметить, что, хотя рассуждения в данной статье проводятся для Рекомендации XPath версии 1.0, все полученные результаты полностью переносятся и на язык XPath версии 2.0 [8], черновая спецификация которого в настоящий момент проходит процесс перехода в статус Рекомендации консорциума Всемирной Сети.
Статья организована следующим образом. В разделе 2 дается обзор основных понятий, используемых в ходе дальнейшего изложения. Раздел 3 посвящен рассмотрению связанных работ по данной предметной области. В разделе 4 на простом примере иллюстрируется основная идея предлагаемого в данной работе алгоритма. Описание основного алгоритма и его обоснование даны в разделе 5. В разделе 6 обсуждаются свойства предложенного алгоритма; ограничения алгоритма рассматриваются в разделе 7. Результаты проведенных экспериментов обсуждаются в разделе 8. Раздел 9 завершает статью.