1 Система хранения XML СУБД Sedna Андрей Фомичев Институт Системного Программирования РАН 5 апреля 2005

2 План доклада Краткое описание XML СУБД Sedna Хранение XML-данных во внешней памяти Управление памятью: слоистая организация адресного пространства Стратегии выполнения XPath-запросов Заключение

3 XML СУБД Sedna Поддержка всех традиционных функций СУБД Эффективное хранение больших объемов XML-данных Поддержка языка запросов XQuery Sedna – полнофункциональная прирожденная XML СУБД, разработанная с нуля, призванная решать следующие задачи: Языки реализации – C/C++ и Scheme

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

5 Методы хранения XML-данных Реляционные СУБД –BLOB, CLOB –Декомпозиция на отношения Прирожденные (Native) XML СУБД –Дерево во внешней памяти –Нумерующие числа

6 XPath-запросы /child::a/descendant::b/child::c a bac bcbaa bcc a bac bcbaa bcc a bac bcbaa bcc a bac bcbaa bcc Структурные XPath-запросы child:: descendant:: attribute:: self:: descendant-or-self:: /child::a/descendant::b[child::d/child::text() = Bob]/child::c

7 Описывающая схема Foundation on databases Abiteboul Hull Vianu... An Introduction to Database Systems Date Addison-Wesley 2004 A Relational Model for Large Shared Data Banks Codd... The Complexity of Relational Query Languages Codd library book paper titleauthorissue publisheryear titlebook /child::library/child::book/child::title library book title

8 Структура хранения title... Идентификатор узла Нумерующее число Таблица косвенности дети Следующий в блоке Сосед справа Предыдущий в блоке Сосед слева родитель

9 Принятые решения, позволяющие производить эффективное изменение данных Дескрипторы узлов имеют фиксированный размер Дескрипторы узлов частично упорядочены Нумерующая схема не требует перестройки XML-дерева при изменении данных Введена таблица косвенности для указателей на родителей

10 Какие изменения блоков влечет за собой изменение узла Оценка количества блоков, которые придется изменить не зависит от размера документа узел левый сосед правый сосед родитель Таблица косвенности ребенок

11 Требования к указателям и методу их реализации 1.Указатели должны существовать в адресном пространстве большого размера 2.Операция разыменования указателя должна быть эффективной 3.Необходимо минимизировать расходы связанные с подменой указателей (pointer swizzling) или полностью избежать их

12 Подмена указателей (pointer swizzling)Подмена указателей (pointer swizzling) Стратегии подмены указателей Автоматическая подмена указателей (automatic swizzling) Подмена указателей по требованию (swizzling on demand) Запрет подмены указателей (no swizzling) Внешняя память Оперативная память Адрес в базе данных Адрес оперативной памяти

13 Идея слоистого адресного пространства Расширенное адресное пространство + собственный механизм виртуальной памяти Адрес в базе данных = Адрес памяти Нет необходимости в подмене указателей

14 Поддержка слоистого адресного пространства

15 Экспериментальные результаты Загрузка тестового XML-документа XMark размером 113Мб ~60 миллионов переключений между блоками накладные расходы связанные с поддержкой слоистой организации адресного пространства составили 3%

16 XPath-запросы с предикатами: способы выполнения Способы выполнения /child::dep/child::person[child::data/child::salary=100] dep person data salary сверху-вниз (top-down) снизу-вверх (bottom-up) слияние (merge) сверху-вниз (top-down) снизу-вверх (bottom-up) слияние (merge)

17 XPath-запросы с предикатами: пример (1) /library/book [issue/year=2004]/ title

18 XPath-запросы с предикатами: пример (2) /*/book [author=Date]/ issue[year=2004]/ publisher

19 XPath-запросы с предикатами: пример (3) /library/* [.//publisher]

20 Спасибо за внимание! Google it: Sedna XML DBMS