Стремительно возрастающее число XML-документов обеспечивает импульс для развития систем, которые могут эффективно хранить и управлять данными в формате XML. Для управления XML-данными были разработаны новые выразительные средства, такие как языки запросов XPath и XQuery. Особенности модели данных XML, заключающиеся в древовидности структуры данных и упорядоченности узлов дерева XML-документа, обуславливают необходимость реализации средств, позволяющих легко устанавливать иерархические связи между узлами (предок-потомок или отец-сын), а также сравнивать два узла по порядку их следования в документе. Для решения подобных задач используется сопоставление сущностей модели данных XML уникальным идентификаторам (именующим (нумерующим) числам), совокупность которых называется нумерующей (именующей, маркирующей) схемой (labeling scheme).

Проведенный анализ существующих нумерующих схем [1, 2, 3] показал их неэффективность: плохая обработка динамических вставок элементов, необходимость перенумерации узлов дерева при больших количествах вставок новых элементов или сильная зависимость размера нумерующего числа от глубины дерева документа из-за использования символа-разделителя в нумерующем числе на каждом уровне глубины дерева.

В данном докладе предлагается новая нумерующая схема, которая используется в разрабатываемой в Институте системного программирования РАН XML-ориентированной СУБД SEDNA [10]. Данная нумерующая схема - SLS (Sedna Labeling Schema), позволяет решить описанные выше проблемы за счет уменьшения размера нумерующего числа, а также более эффективного его выделения при последующей вставке узлов в документ.

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

Для сравнения существующих нумерующих схем, описанных в [1, 2, 3], с нумерующей схемой, предлагаемой авторами, была разработана программа расчета эффективности алгоритмов (объем нумерующей схемы). Эта программа составляет нумерующую схему для XML-документов различных размеров на входе каждым из описанных в [1, 2, 3] методов, а также методом, предлагаемым в данном докладе. По результатам выполнения этой программы стало очевидно, что нумерующая схема SLS является более эффективной по сравнению с остальными тестируемыми нумерующими схемами.

Литература:

1. V. Christophides, D. Plexousakis, M. Scholl, S. Tourtounis. On Labeling Schemes for the Semantic Web. In WWW-2003, 2003.
2. T. Amagasa, M. Yoshikawa, S. Uemura. QRS: A Robust Numbering Scheme for XML Documents, In ICDE, 2003.
3. K. Deschler, E. Rundensteiner. MASS: A Multi-Axis Storage Structure for Large XML Documents. WPI TR 03-23. ftp://ftp.cs.wpi.edu/pub/techreports/pdf/03-23.pdf
4. N. Wirth. Type extensions. ACM Trans. on Progr. Languages and Systems, 10(2):204-214, 1988.
5. Online Computer Library Center. Dewey decimal classification. www.oclc.org/dewey/.
6. P.F. Deitz. Maintaining order in a linked list. In Proc. of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC’82), 122-127, 1982.
7. P.F. Deitz and D.D. Sleator. Two algorithms for maintaining order in a list. In Proc. of the Sixteen Annual ACM Symposium on Theory of Computing (STOC’87), 365-372, 1987.
8. R. Agrawal, A. Borgida, and H.V.Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proc. of the SIGMOD Intern. Conf. on Management of Data , 253-262, 1989.
9. Q. Li and B. Moon. Indexing and querying XML data for regular path expressions. In Proc. of 27th Intern. Conf. on Very Large Data Bases (VLDB’02), 2001.
10. М. Гринев, С. Кузнецов, А. Фомичев. XML-СУБД Sedna: технические особенности и варианты использования. "Открытые системы", № 8, 2004, с. 36-43.