Методы реализации древовидных и сетевых структур в реляционных СУБД

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

Оператор 13. Установить направление обхода False. Изменяет первоначальное направление обхода на обратное.

Оператор 14. Перейти по указателю стека вершин. Это действие означает чтение головы стека вершин и перехода по выбранному из него указателю на родительскую вершину относительно текущей вершины.

Оператор 15. Удалить из стека вершин головную вершину. Означает просто уменьшение указателя стека вершин на 1.

Оператор 16. Окончание цикла соответствующее команде ENDDO.

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

Сделаем следующие замечания:

· пример иллюстрирует возможность работы с сетевой структурой, поскольку повторяющиеся поддеревья записываются в таблицу один раз;

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

· алгоритм может быть реализован также и на основе массива, содержащегося в оперативной памяти;

Иерархическое представление ориентированной сети без циклов. Для такого представления достаточно всего два поля CHTO и KUDA. Воспользуемся снова той же таблицей TREE.DBF и заполним на основе сети, изображённой на Рис. 12, поля CHTO и KUDA, оставив пустыми поля LLINK, RLINK. В результате мы получим неупорядоченный набор иерархических отношений. Создадим тег вторичного индекса по полю KUDA и, тем самым сгруппируем записи по общности родительских вершин. В результате действия процедуры ProshPod, алгоритм которой изображён на Рис. 14, получим заполненные поля LLINK и RLINK, для любого поддерева, например, - исходящих из вершины 1 или 2. Для построения бинарного дерева для всей сети необходимо воспользоваться алгоритмом, изображённом на Рис. 15.

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

начало

1. Установить вершину 6.Сохранить адрес записи

начала обхода в lnSA и ключ в lcChto

7.

текущая вершина lcChto Нет

встречается в поле

Kuda?

. Да

3. Начало цикла

i = 0

4. Нет

NO =.T.?

Да

5.Есть нет

указатель на левое

поддерево? Нет

11. Kuda=lcKuda?

да

13. i=i+1. Занести в стек

вершин указатель Да

текущую на вершину lcKuda= CHTO

15.Перейти на левое

поддерево

20.Окончание цикла 5

(i = 0)

конец

Рис. 14. Алгоритм процедуры ProshPod построения бинарного поддерева.

начало

Начало цикла с условием

Not Eof()

Да

Запись найдена?

Конец цикла

Рис. 15. Алгоритм построения двоичного дерева над неупорядоченным “лесом” деревьев

Избыточный двухсвязный список можно легко преобразовать в строгий двухсвязный список простым удалением поля KUDA, или в односвязный – удалением поля RLINK и использованием тега по полю KUDA.

Еще одну разновидность представления можно получить, оставив поля CHTO и LLINK и введя поле уровня вершины.

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

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

· ключевое поля KUDA преобразовывается в указатель на родительскую вершину;

· указатель LLINK становится указателем NEXT на следующую вершину в порядке левостороннего обхода;

· указатель RLINK остаётся без изменения и указывает всегда на правое поддерево, если оно существует. В противном случае RLINK содержит -1;

· для ускорения выполнения обратных обходов вводится логическое поле RLINKI, которое принимает значение True, если узел имеет более одной родительской вершины;

· для использования этого представления в качестве нейронной сети добавляется еще поле для представления количественной характеристики, интерпретируемой в различных контекстах различным образом: степень достоверности в сетях логического вывода; весовая характеристика при обучении нейронной сети и т.п.

В результате мы получим нижеследующий следующий листинг структуры таблицы.

Structure for table: C:\APPL\ELABOR\FTE5\WORK\TREE.DBF

Number of data records: 12

Date of last update: 25.10.98

Code Page: 1251

Field Field Name Type Width Dec Index

1 CHTO Character 4

2 KUDA Character 4

3 NEXT Character 4

4 RLINK Character 4

5 RLINKI Logical 1

6 Kol Numeric 3 2

** Total ** 20

Для работы с таким представлением автором были разработаны специальные пакеты программ в системе Visual FoxPro и Visual Basic.

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

Рис. 16. Представление дерева в форме классификации Дьюи

Десятичная система Дьюи применима ко всякому лесу: корень k-того дерева в лесу обозначается номером k; если α-номер любого узла степени m, то его сыновья обозначаются номерами α.1,α.2,…,α.m. Вместо десятичной системы счисления в реальных приложениях употребляют системы с основанием 128 или 256 и отводят более чем одну позицию для нумерации сыновей любого узла. Так например, в случае системы с основанием 256 и двухбайтовой позиции получим возможность оперировать более чем с 65000 членов семьи одного узла.

Обратим внимание на следующие важные свойства представления деревьев в форме классификации Дьюи:

· обозначения узлов представляют собой строки символов;

· узел, имеющий уровень k имеет обозначение длиной k*n символов, где n – число позиций, отведённое под номер;

· последние n символов представляют порядковый номер узла в составе семьи;

· для любого узла первые k*n-n символов являются обозначением родительской вершины.

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

Для представления “леса” на основе классификации Дьюи необходима таблица базы данных (например, Tree.dbf), содержащая, как минимум, два поля:

· в поле Tree.NomVer хранится индекс вершины дерева;

· в поле Tree.Link – ключ записи таблицы, содержащей данные, ассоциированные с данным узлом.

Для такой таблицы создаётся индексный файл, содержащий обычно три тега (в терминах языка FoxPro):

· Index on NomVer to TAG NomVer;

· Index on Str(len(trim(NomVer))) + NomVer to TAG Family;

· Index on Link to TAG Link.

Тег NomVer обеспечивает упорядочивание индексов вершин в соответствии с прямым левосторонним обходом. Тег Family – в соответствии с уровнями дерева, т. е. сначала будут идти вершины первого уровня, затем – второго и т.д. Тег Link обеспечивает прямой доступ к узлам дерева по ассоциированным с узлами данным и, одновременно, группирование одинаковых данных, но встречающихся в различных контекстах.