Программные продукты и системы

Существует ряд задач, требующих представления структурированных данных в реляционных базах данных (РБД). Прежде всего это связано с информацией, представленной в виде графовых или сетевых структур. В настоящее время отсутствуют решения по оптимальным схемам хранения столь сложно структурированных данных (Гладков М., Шибанов С. Сложные структуры в реляционных базах данных. // Открытые системы, 2004.).

Существуют два основных метода представления графов (в памяти) ЭВМ: матричный, (то есть представления массивами) и связными нелинейными списками. Выбирается метод представления в зависимости от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то используется представление графа связными списками; в противном случае – матричное представление. Хранение графов в РБД осложняется большим количеством ссылок на элементы графа, неизвестным заранее. Основная сложность состоит в эффективном хранении и поддержании целостности этих ссылок.

На сегодняшний день выявлены два способа хранения древовидных структур: 1) в виде матрицы смежности с использованием вспомогательной таблицы; 2) по методу вложенных множеств. Как оказалось, данные схемы не применимы прямо к произвольному графу, так как в них используются ограничения иерархической структуры, в частности не предполагается и не учитывается возможность ненаправленных связей, петель.

Рассмотрим возможные способы хранения графов в РБД.

Используя матрицу смежности для хранения графов в РСУБД, запишем ее не в классическом виде, а представленной связным списком вершин. Ключом такого реляционного отношения является сочетание идентификаторов исходящей вершины (родителя) и входящей (потомка). Для ненаправленного графа, подразумевающего возможное повторение этих сочетаний, введем отдельное идентификационное поле (рис. 1).

В этом случае ID_Out и ID_In, представляющие обозначения входящих и исходящих вершин по матрице, соответствуют ID_el узлов графа в основной таблице с данными.

Представление графа списками ребер и вершин является одним из наиболее распространенных при аналитической работе с графами и широко используется в программировании, однако в случае с РБД фактически соответствует рассмотренному.

Случай хранения графа с использованием связного (списочного) представления сводится к хранению структуры, напоминающей нелинейный разветвленный список. Получаемая структура имеет два типа элементов: (элемент графа–ссылка) и (ссылка–ссылка). Тем не менее, полученная структура нелинейным разветвленным списком не является, так как в ней могут наличествовать петли и обратно направленные связи (рис. 2).

Связи B®D и D®C не соответствуют представлению в виде дерева и не соответствуют теории нелинейных разветвленных списков.

Реляционная схема хранения приведена на рисунке 3. Основные данные (элементы списка) хранятся в таблице «Граф». Связанная таблица «Граф: элементы графа» используется совместно с основной для отдельного хранения элементов, отсутствующих в случае сочетаний ссылка-ссылка. Поле «Type» имеет бинарное значение: 0 – ссылка–элемент, 1 – ссылка–ссылка.

Наконец, еще одним вариантом хранения является представление графа в виде леса связанных деревьев (рис. 4). В случае такого представления рационально использовать схему хранения деревьев, усовершенствовав ее для представления нескольких связанных иерархий.

Автором выявлены две наиболее рациональные схемы хранения иерархических структур, имеющие разную эффективность, в зависимости от типа решаемой задачи. В одном случае для хранения дерева используются две таблицы: основная и вспомогательная. В основной таблице хранится только непосредственный предок узла, а во вспомогательной каждому узлу соотнесены все его предки по направлению к вершине. Для хранения графа расширим эту схему на идентификатор дерева, использующийся совместно с номером узла, к которому он принадлежит. Таким образом, применяемая для хранения графов схема будет иметь вид, представленный на рисунке 4.

В другом случае, согласно методу вложенных множеств (МВМ), каждому элементу иерархии в зависимости от его места присваиваются два числовых значения: левое и правое (см.: Celko Joe. A Look at SQL Trees. //DBMS, March 1996). Каждое дерево, входящее в граф, получает эти значения независимо от структуры самого графа (рис. 5).

В этом случае модернизация схемы хранения иерархий сводится к добавлению нового поля – идентификатора дерева (рис. 6).

Логично использовать для всех деревьев графа единую, сквозную нумерацию, учитывающую все деревья, его составляющие (рис. 7).

Представления матрицей смежности и списками ребер и вершин рационально объединить воедино, поскольку для этих представлений используется одна и та же схема хранения. Назовем этот объединенный способ «хранением при помощи списков ребер и вершин», что наиболее точно отвечает сути схемы хранения. Исключим из окончательного рассмотрения связное (списочное) представление графа из-за выявленной особой сложности работы с ним. Таким образом, окончательный список представлений графа выглядит следующим образом:

1) представление графа списками ребер и вершин;

2) представление графов в виде леса связанных деревьев на основании метода матрицы смежности со вспомогательной таблицей;

3) представление графов в виде леса связанных деревьев на основании метода вложенных множеств с независимой нумерацией;

4) представление графов в виде леса связанных деревьев на основании метода вложенных множеств со сквозной нумерацией.

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

Исходные данные: E1 – число элементов в графе; E2 – число дуг в графе; M1 – число строк таблицы, хранящей элементы графа (для всех представлений M1=E1); M2 – число строк таблицы (если она есть), хранящей дуги графа (для представления в виде списка ребер и списка вершин M2=E2; для представления в виде леса деревьев по методу матрицы смежности M2>E2>E1; .в представлениях по методу вложенных множеств вспомогательная таблица отсутствует); N1 – число столбцов таблицы, содержащей элементы графа; N2 – число столбцов таблицы, хранящей дуги графа по методу списка вершин и ребер; N2 +1 – число столбцов таблицы, хранящей дуги графа в представлении в виде леса деревьев с использованием метода матрицы смежности; N1+1 – число столбцов в таблице в представлении в виде леса деревьев с использованием метода матрицы смежности; N1+3 – число столбцов в таблице в представлении в виде леса деревьев по методу вложенных множеств.

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

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

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

Проведенный анализ выявил полезность с точки зрения составления запросов метода представления в виде леса деревьев по методике матрицы смежности и наилучшее поведение в задаче поиска пути в графе метода представления в виде леса деревьев с использованием метода вложенных множеств и сквозной нумерации.

Результаты показывают необходимость развития методов представления графов и оптимизации задач по работе с ними в РСУБД, так как ни одна из рассмотренных схем хранения не может быть признана оптимальной.