XML-СУБД Sedna технические особенности и варианты использования


Структуры данных - часть 2


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

Рис. 3. Общая структура дескриптора узла

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

Использование прямых указателей способствует эффективному выполнению запросов, но порождает проблемы эффективного выполнения операций обновления. Чтобы организация данных была эффективно пригодна для обновлений, нужно минимизировать число модификаций данных, производимых при выполнении операции обновления. Например, выполнение некоторых операций обновления может привести к перемещению узла. Если у узла, который требуется переместить, имеются узлы-потомки, то в каждом из них необходимо поменять значения указателей на узел-предок. Чтобы избежать этой массовой операции, для ссылок на узлы-предки используются косвенные указатели, реализуемые через таблицу косвенности.

Нумерующая схема назначает уникальную метку каждому узлу XML -документа в соответствии с присущими данной схеме правилами нумерации. Метки кодируют информацию об относительной позиции узла в документе. Таким образом, основное назначение нумерующей схемы состоит в обеспечении быстрых механизмов определения структурной связи между парой узлов. При разработке СУБД Sedna требовалась нумерующая схема, обеспечивающая обнаружение связи “потомок-предок” и сравнение узлов в порядке документа. Первый механизм позволяет поддерживать планы выполнения запросов, основанные на соединениях " включению” ( containment join ) [-]. Второй механизм используется для реализации операций XQuery , основанных на порядке документа (например, сравнение узлов, XPath и т.д.).




- Начало -  - Назад -  - Вперед -



Книжный магазин