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

Исторически первая волна работ была посвящена адаптации реляционных СУБД для хранения XML-данных [5, 6], так как было вполне естественно использовать существующую инфраструктуру для решения поставленных задач. Однако результатом этих исследований стало понимание принципиальных ограничений реляционных СУБД для эффективного хранения и обработки XML-данных. Действительно, XML-данные хранятся в реляционных СУБД либо как BLOB, либо разбиваются на множество отношений. В первом случае необходима выгрузка всего документа для выполнения запроса, а во втором производится слишком много ресурсоемких операций соединения.

Понимание ограничений реляционных СУБД для хранения XML вызвало всплеск активности по разработке методов, предназначенных для управления XML-данными. Не претендуя на полную классификацию, автор хотел бы подчеркнуть ряд общих характеристик этих методов:

1. Методы [7-9], которые основаны на декомпозиции XML-документов на узлы, как реляционные СУБД, но делают акцент на эффективном восстановлении (частей) XML-документов. Ключом к решению этой задачи является установление отношений родитель-ребенок и предок-потомок эффективным образом, для чего вводится понятие так называемой нумерующей схемы. После этого восстановление XML-документа осуществляется посредством специальных операций соединения, которые обычно называются структурными соединениями (structural joins) и соединениями включения (containment joins). Обычно, работы, использующие этот подход, концентрируются на эффективной реализации вышеописанных операций соединения и введении дополнительных индексов (так как одной нумерующей схемы недостаточно), но уделяют мало внимания структурам хранения и вопросам изменения данных.
2. Методы [10], которые представляют XML-документ как дерево, состоящее из узлов связанных ссылками, и которые концентрируются на хранении этого дерева во внешней памяти таким образом, чтобы удовлетворить определенным требованиям. Например, могут делаться попытки минимизировать количество используемых блоков или сбалансировать дерево блоков так, чтобы к любому узлу XML-дерева можно было добраться за фиксированное количество чтений. Основным недостатком данного подхода является то, что он обычно требует ресурсоемкого обхода XML-дерева для ответа на запросы языка XPath [1].
3. Общей характеристикой третьей группы методов[11,12] является то, что они используют (в каком-то виде) описывающую схему XML-документа. Описывающую схему можно определить следующим образом: для каждого пути в XML-документе существует и только один путь в описывающей схеме. Имеющиеся исследования позволяют утверждать, что описывающая схема (или путеводитель по данным, как ее еще иногда называют) может быть использована для формулирования запросов к данным, оптимизации [3,4], индексации [11] и сжатия данных [12].

Автор полагает, что третья группа методов является наиболее перспективной. Более того, описывающая схема может использоваться не только для описанных выше задач, но и для организации непосредственно хранения XML-данных. Использование описывающей схемы для организации хранения позволяет избежать дорогостоящих обходов XML-дерева и минимизировать количество считываемых блоков при ответе на запрос.

В докладе рассматриваются следующие вопросы:

• Метод хранения XML-документов, основанный на описывающей схеме. Автором описывается метод и подробно обсуждаются принятые решения. Затрагиваются не только вопросы эффективного доступа к данным, но и вопросы изменения данных;
• Алгоритмические аспекты выполнения XPath-запросов при использовании вышеописанного метода хранения XML-данных. Обсуждаются преимущества, которые дает описывающая схема;
• Практическая применимость данного метода, которая подтверждается работающим прототипом системы и серией экспериментов.

Принцип организации хранения XML-данных, рассматриваемый в докладе, положен в основу среды хранения XML СУБД Charisma, а также был использован в системе виртуальной интеграции данных BizQuery [2] (Charisma и BizQuery — проекты, выполняемые Институтом системного программирования РАН).

Литература:

1. XML Path Language (XPath) 2.0, W3C Working Draft 12 November 2003, http://www.w3.org/TR/2003/WD-xpath20-20031112/
2. Antipin, K., Fomichev, A., Grinev, M., Kuznetsov, S., Novak, L., Pleshachkov, P., Rekouts M. and Shiryaev, D.: Efficient Virtual Data Integration Based on XML, Proceedings of ADBIS 2003
3. McHugh, J., Abiteboul, S., Goldman, R., Quass, D., Widom, J.: Lore: A Database Management System for Semistructured Data. SIGMOD Record, 26(3):54-66, September 1997
4. Goldman, R. and Widom, J.: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23th VLDB Conference, Greece, 1997
5. Tian, F., DeWit, D., Chen, J., Zhang, C.: The Design and Performance Evaluation of Alternative XML Storage Strategies. SIGMOD Record 31(1): 5-10 (2002)
6. Florescu, D., Kossman, D.: A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database, Technical Report 3680, INRIA, France, 1999
7. Jagadish, H., Al-Khalifa, S., Chapman, A., Lakshmanan, L., Nierman, A., Paparizos S., Patel, J., Srivastava D., Wiwatwattana N., Wu, Y. and Yu, C.: TIMBER: A Native XML Database, The VLDB Journal, Volume 11, Issue 4 (2002) pp 274-291
8. Li, Q., Moon, B.: Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th VLDB Conference, Roma, Italy, 2001
9. Al-Khalifa, S., Jagadish, H., Patel, J., Wu, Y., Koudas, N., Srivastava, D.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of ICDE 2002, San Jose, California
10. Fiebig, T., Helmer, S., Kanne, C.-C., Moerkotte, G., Neumann, J., Schiele, R., Westmann, T.: Anatomy of a native XML base management system, The VLDB Journal, Volume 11, Issue 4 (2002) pp 292 - 314
11. Leela, K., Haritsa, J.: SphinX: Schema-conscious XML Indexing, Technical Report, TR-2001-04, DSL/SERC, http://dsl.serc.iisc.ernet.in/pub/TR/TR-2001-04.pdf
12. Buneman, P., Grohe, M., Koch, C.: Path Queries on Compressed XML, Proceedings of the 29th VLDB Conference, Germany, 2003