Язык XML Path (XPath), разработанный консорциумом W3C - это язык для адресации структурных частей XML-документа. Язык XPath является ключевым языком в составе платформы XML и изначально разрабатывался как основа для нескольких других языков обработки XML-данных, в частности, XSLT и XPointer [1]. Ввиду важности языка XPath в контексте процессоров XML и XML-ориентированных СУБД, актуальной является задача оптимизации вычисления выражений языка XPath.

В докладе поднимается проблема экспоненциальной временнoй алгоритмической сложности некоторых известных реализаций XPath и обсуждаются конструкции языка XPath [2], недостаточно аккуратный подход к реализации которых приводит к экспоненциальной алгоритмической сложности вычислений. Обсуждаются примеры выражений XPath [3], для вычисления которых существующие промышленные реализации XPath (в частности, Saxon, Xalan и XL) требуют экспоненциального от размера этих выражений времени, даже для маленьких XML-документов.

Для преодоления проблемы экспоненциальной временнoй сложности вычисления выражений XPath в докладе предлагаются способы оптимизации, основанные на поддержании уникального упорядоченного набора узлов (distinct document order) при вычислении каждого шага доступа [4] и предварительном вычислении глубоко вложенных предикатов XPath. Рассматриваются комбинации шагов доступа XPath, для которых возможно упростить их вычисление [5]. Использование статического вывода типов для выражений XPath позволяет выявлять предикаты, не требующие генерации контекстной позиции, что ускоряет вычисление осей XPath и глубоко вложенных предикатов. Предлагается оптимизация операций обобщенного сравнения (general comparison) и предикатов на контекстную позицию.

Обсуждаются вопросы реализации предложенных способов оптимизации вычисления выражений XPath функциональными методами [6]. Иллюстрируется концепция отложенных вычислений языка функционального программирования Scheme, позволяющая производить вычисление глубоко вложенных предикатов XPath в точности для тех значений контекста, для которых это вычисление реально требуется. Затрагивается вопрос интеграции функциональной реализации XPath с языком программирования Scheme [7].

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

Литература:

1. Лизоркин Д.А. Оптимизация вычисления обратных осей языка XML Path при его реализации функциональными методами. Сборник трудов Института системного программирования РАН, 2004.
   http://modis.ispras.ru/Lizorkin/Publications/xpath-context.ps
2. James Clark and Steve DeRose (редакторы). Язык XML Path (XPath) Версия 1.0. Рекомендация Консорциума Всемирной Сети от 16 Ноября 1999.
   http://citforum.ru/internet/xpath/index.shtml
3. Georg Gottlob, Christoph Koch and Reinhard Pichler. Efficient Algorithms for Processing XPath Queries. 28th International Conference on Very Large Data Bases (VLDB 2002), Hong Kong, China, August 20-23, 2002.
   http://www.dbai.tuwien.ac.at/research/xmltaskforce/vldb2002.pdf
4. Sven Helmer, Carl-Christian Kanne and Guido Moerkotte. Optimized Translation of XPath into Algebraic Expressions Parameterized by Programs Containing Navigational Primitives. University of Mannheim, Germany.
   http://pi3.informatik.uni-mannheim.de/publications/TR-02-011.pdf
5. Michael Kay. XSLT and XPath Optimization. XML Europe 2004 - Conference Proceedings.
   http://idealliance.org/papers/dx_xmle04/papers/02-03-02/02-03-02.pdf
6. Лизоркин Д.А. и Лисовский К.Ю. Язык XML Path (XPath) и его функциональная реализация SXPath. Электронные Библиотеки. - 2003, Том 6, Выпуск 4.
   http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part4/LL
7. Лизоркин Д.А. Проект DDO SXPath: разработка и реализация функциональными методами языка запросов, основанного на XPath, и его оптимизация.
   http://modis.ispras.ru/Lizorkin/ddo.html