Методы хранения XML в реляционных базах данных

Таблица 1.6 - Content (Document) Management Systems

Как видно из приведенных выше таблиц, практически все программное обеспечение платное, а среди систем управления содержанием совсем нет свободного программного обеспечения.

2 СПЕЦИАЛЬНЫЙ РАЗДЕЛ

2.1 Постановка задачи

В данной работе необходимо реализовать хранение XML на основе объектно-реляционного отображения документа в базу данных. Требования к приложению:

             обеспечить возможность ввода XML документа;

             обеспечить возможность сохранения XML документа любой структуры в базе данных;

             обеспечить возможность поиска и извлечения документа из БД;

Далее предположим, что изменения в структуре XML документа вносятся реже, чем выполняются запросы на добавление документа в базу данных и извлечения документа из базы. Это предположение основано на фактах из реальной жизни. Бухгалтерские отчеты, бланки заявлений и многое другое имеют постоянную структуру, редко меняющуюся с течением времени. Гораздо чаще документы сохраняются и извлекаются из БД. Также предположим, что каждый документ, внесенный в базу данных, имеет уникальный номер.

Задачи, которые необходимо выполнить для реализации:

             выбрать способ представления ХМЛ в РСУБД;

             разработать схему БД в соответствии с выбранной моделью отображения;

             выбрать средства реализации;

             реализовать БД;

             реализовать типовые запросы к данным.

2.2 Выбор способа представления XML в РСУБД

В настоящее время для хранения древовидных структур в базах данных применяются два основных метода: метод матриц смежности и метод вложенных множеств (метод обхода).

Граф можно представить в виде матрицы смежности, где на пересечении i-ой строки и j-го столбца стоит "1", если между узлами (вершинами) графа, с номерами i и j, соответственно, есть связь (ребро, дуга), или "0" в противном случае. Для реализации этого способа в базе данных создается таблица, в которой хранятся элемент дерева и ссылка на родителя. Примерный вид таблицы базы данных смотри в таблице – 2.1.

Таблица 2.1 - Примерный вид таблицы БД для хранения деревьев в реляционной базе данных по методу матриц смежности

              При таком способе хранения ID выступает в качестве первичного ключа а ID родителя в качестве внешнего ключа, ссылающегося на ID. Преимущества и недостатки данного метода смотри в таблице 2.2.

Для наглядного представления метода вложенных множеств смотри рисунок 2.1. Квадратик на рисунке обозначает узел, цифра в левом его углу является порядковым номером этапа маршрута при входе в узел, а цифра справа — при выходе, т.е. когда тем же способом пройдены все потомки. Отсюда следует и название метода – все номера потомков узла находятся в интервале между его левым и правым номером. Храня порядок обхода дерева, мы избегаем рекурсии при выполнении запросов. Очевидная сложность — пересчет порядка обхода при добавлении новых или перемещении имеющихся узлов (удаление можно игнорировать).

Таблица 2.2 - Преимущества и недостатки метода матриц смежности

Для нумерации дерева может быть использован алгоритм обхода графа в глубину. Обозначим стек для открытых вершин через S. Через top(S) обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной A может быть записана следующим образом:

Начало

              Посетить вершину A

              Сохранить A в S (A=>S)

              Пока S не пуст делай

                            x = top(S)

                            Если имеется неисследованное ребро (x, y), то

                                          Исследовать ребро (x, y)

                            Все если

                            Если вершина y новая, то

                                          Посетить вершину y

                                          Сохранить y в S (y=>S)

              Иначе

                                          Удалить x из S

                            Все если

              Все пока

Конец

Рисунок 2.1 -  Нумерация узлов в методе вложенных множеств

Преимущества и недостатки данного метода смотри в таблице 2.3. Как следует из таблиц, метод матриц смежности обеспечивает быструю вставку и удаление вершин дерева, но медленное извлечение дерева. А метод вложенных множеств быстрое извлечение дерева, но медленную вставку и удаление вершин.

Таблица 2.3 - Преимущества и недостатки метода вложенных множеств

Поскольку в §2.1 было сказано, что изменения в структуре XML документы вносятся реже, чем выполняются запросы на добавление документа в базу данных и извлечения документа из базы, то наиболее оптимальным методом представления XML в БД будет метод вложенных множеств.

2.3 Разработка схемы базы данных

Для метода множенных множеств разработаем структуру таблицы базы данных (смотри таблица 2.4.).

Таблица 2.4 Структура таблицы для метода вложенных множеств