Структуры данных
В СУБД Sedna в основе хранения XML -документа во внешней памяти лежит описывающая ( descriptive ) схема XML -документа, в соответствии с которой осуществляется кластеризация узлов XML -документа в блоках базы данных. Описывающая схема генерируется (и поддерживается) динамически на основе хранимых данных и представляет собой краткое и точное описание структуры этих данных. Выражаясь формально, для каждого пути в документе существует в точности один путь в описывающей схеме, и каждый путь в описывающей схеме является путем в документе.
<library> <book> <title>Foundation of Databases</title> <author>Abitboul</author> <author>Hull</author> <author>Vianu</author> </book> <book> <title>An Introduction to Database Systems</title> <author>Date</author> <issue> <publisher>Addison-Wesley</publisher> <year>2004</year> </issue> </book> ... <paper> <title>A Relational Model for Large Shared Data Banks</title> <author>Codd</author> </paper> </library>
Рис. 2. Организация данных
Общие принципы организации хранения XML -документа иллюстрируются на . Центральным компонентом является описывающая схема, представляемая в виде дерева узлов. Каждый узел схемы помечается названием разновидности XML -узла (например, element , attribute , text и т.д.) и содержит указатель на блоки данных, в которых хранятся узлы XML -документа, соответствующие данному узлу схемы. Некоторые узлы схемы, в зависимости от вида узла, помечаются дополнительными именами.
Блоки данных, относящиеся к одному узлу схемы, связаны указателями в двунаправленный список. Дескрипторы узлов в списке блоков частично упорядочены в соответствии с порядком документа. Это означает, что каждый дескриптор узла в блоке i предшествует каждому дескриптору узла в блоке j в соответствии с порядком документа том и только в том случае, когда i < j (т.е. блок i предшествует блоку j в списке). Внутри блока узлы линейно не упорядочиваются, что сокращает накладные расходы на поддержку порядка документа при выполнении операций обновления.
В системе хранения разделяются структурная часть узла и его текстовое значение, являющееся содержимым текстового узла, или значением узла-атрибута и т.д. Длины текстовых значений являются переменными, и они хранятся в отдельных блоках со специальной структурой. В структурной части узла, представляемой в виде дескриптора узла, отражаются его связи с другими узлами (предком, потомками, братьями и т.д.).
Рис. 3. Общая структура дескриптора узла
Общая структура дескриптора узла для всех разновидностей узлов показана на . Поле метки содержит метку нумерующей схемы (про нумерующую схему и идентификаторы узлов см. ниже. Указатели на следующий и предыдущий узлы в том же блоке служат для восстановления порядка документа между узлами документа, соответствующими одному и тому же узлу схемы, а указатели на левого и правого братьев по схеме – для поддержки порядка документа между узлами-братьями. В дескрипторе хранятся ссылки только на первые дочерние узлы в соответствии с описывающей схемой. Поддержка только указателя на первого потомка в соответствии со схемой позволяет экономить память и, что более важно, сохранять фиксированный размер дескриптора блока. Последнее свойство особенно существенно для эффективного выполнения операций обновления, поскольку упрощается управление свободной памятью внутри блока.
Использование прямых указателей способствует эффективному выполнению запросов, но порождает проблемы эффективного выполнения операций обновления. Чтобы организация данных была эффективно пригодна для обновлений, нужно минимизировать число модификаций данных, производимых при выполнении операции обновления. Например, выполнение некоторых операций обновления может привести к перемещению узла. Если у узла, который требуется переместить, имеются узлы-потомки, то в каждом из них необходимо поменять значения указателей на узел-предок. Чтобы избежать этой массовой операции, для ссылок на узлы-предки используются косвенные указатели, реализуемые через таблицу косвенности.
Нумерующая схема назначает уникальную метку каждому узлу XML -документа в соответствии с присущими данной схеме правилами нумерации. Метки кодируют информацию об относительной позиции узла в документе. Таким образом, основное назначение нумерующей схемы состоит в обеспечении быстрых механизмов определения структурной связи между парой узлов. При разработке СУБД Sedna требовалась нумерующая схема, обеспечивающая обнаружение связи “потомок-предок” и сравнение узлов в порядке документа. Первый механизм позволяет поддерживать планы выполнения запросов, основанные на соединениях " включению” ( containment join ) [-]. Второй механизм используется для реализации операций XQuery , основанных на порядке документа (например, сравнение узлов, XPath и т.д.).
Основная проблема существующих нумерующих схем для XML (например, схемы, предложенной в []) состоит в том, что вставка узлов может повлечь реконструкцию всего XML -документа. В СУБД Sedna используется новая нумерующая схема, не требующая подобной реконструкции. Идея этой нумерующей схемы основана на том наблюдении, что для каждых двух заданных строк str 1 и str 2 , таких что str 1 < str 2 (в лексикографическом порядке), существует строка str , такая что str 1 < str < str 2 . Например, для str 1 = " abn ", str 2 = " ghn " возможным значением str является " bcb ", а для str 1 = " ab ", str 2 = " ac " значением str может быть " abd ". Нумерующая схема, поддерживающая порядок документа, может быть использована для реализации понятия уникального идентификатора ( unique identity ), принятого в XQuery , потому что в такой схеме любые два узла с одинаковыми метками являются одним и тем же узлом.
Для реализации некоторых операций и механизмов управления базой данных требуется поддержка идентификатора узла, являющегося неизменным во все время существования узла и обеспечивающего эффективный доступ к узлу. Например, идентификаторы узлов могут использоваться для ссылки на узлы в индексных структурах. Эти идентификаторы также требуются для корректной реализации операций обновления. Как отмечалось выше, при выполнении некоторых операций обновления может потребоваться перемещение узлов. Поэтому указатели на узлы не обладают свойством неизменности. Хотя метка нумерующей схемы этим свойством обладает, для получения узла по известной метке требуется обход дерева документа. Реализация идентификатора узла показана на . Она основана на поддержке специальной таблицы косвенности, которая также используется для реализации косвенных указателей на узлы-потомки. Идентификатор узла является указателем на запись в таблице косвенности, которая содержит указатель на узел.
