В реляционной СУБД

Представление деревьев и графов

Одним из главных достоинств иерархических и сетевых СУБД считают естественность представления данных иерархической и сетевой природы. А как представлять такие данные в реляционных СУБД?

Для деревьев характерными операциями являются

· спуск по дереву или нахождение сына текущей вершины;

· подъем по дереву или переход к родительской вершине;

· горизонтальное перемещение или следующего сына прежней родительской вершины.

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

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

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

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

эти таблицы могут выглядеть так

Вершины Связи

	Id Info … 1 … 2 … 3 … …………
		Out In Info … 1 2 … 1 3 2 3 … 2 7 … 2 8 … … … …

Иногда иерархическая либо сетевая природа данных неочевидна. Например, структура БД по жилищному фонду Республики Марий Эл сначала представлялась простой и понятной (пример Ю. В. Ускова). Предполагались таблицы населенных пунктов, улиц, домов, квартир. В процессе разработки проявилась неоднородность информации. Так некоторые населенные пункты административно подчиняются другим, иногда адрес не содержит названия улицы или номер дома, а в других случаях добавляется номер корпуса и т. п. Выходом явилась иерархическая структура БД. Вершины дерева стали соответствовать различным структурным элементам, что определялось признаком типа вершины. БД оказалась вполне удобной при эксплуатации.

Дата добавления: 2014-01-07