Delphi - сбориник статей

       

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


В этой статье я рассматриваю несколько различных вариантов представления деревьев в базах данных, то есть структуры таблиц и реализацию некоторых операций по работе с деревьями через SQL-запросы к этим таблицам. Подчеркиваю, что речь идет о структуре данных и об операциях обработки. Вопросы написания компонент для представления деревьев здесь не рассматриваются.

Сразу уточню кое-какие моменты: эта статья написана для показа идеи, но не реализации. Отсюда несколько следствий. Я по возможности старался использовать максимально простые запросы, ориентируясь на Local SQL. Это сделано специально, чтобы идея была понятна как можно большему числу читателей. Если начать использовать более оптимальные конструкции, характерные для какой-либо продвинутой СУБД, это может привести к сложностям понимания для людей, работающих с другой СУБД. По той же причине вся программная обработка запросов в примерах написана на Delphi (то есть на стороне клиента), хотя на практике это лучше реализовать на сервере через хранимые процедуры и триггеры. Также в некоторых местах я, возможно, упускаю особенности обработки данных в некоторых экстремальных условиях (добавление первой записи в пустую таблицу, удаление последней записи из таблицы). Просто чтобы не загромождать код примера обработкой различных вариантов, которые усложнят понимание той самой идеи.

В принципе, Паскаль достаточно прост и понятен. И его вполне можно использовать для описания алгоритмов. Но, чтобы еще лучше сконцентрироваться на главном, я при описании реализации операций исхожу из предположения, что у меня имеется несколько вспомогательных функций, реализация которых в рамках данной статьи не существенна. Для простоты понимания тех, кто привык к правильному коду, можно считать, что у меня имеется дополнительный модуль, в котором определены некоторые специальные функции: unit SpecialFunctions; interface uses DBTables; {Процедура выводит узел с идентификатором ID, текстом Name и уровнем номер Level} procedure OutNode(ID,Level : Integer; const Name : String); {Функция создает запрос с текстом, переданным через StrSQL, открывает и возвращает его. Подразумевается запрос SELECT} function OpenQuery(const StrSQL : String) : TQuery; {Процедура выполняет запросы UPDATE, INSERT и DELETE, текст которых передан через StrSQL} procedure ExecQuery(const StrSQL : String); {Функция возвращает идентификатор последней записи, добавленной через запрос INSERT} function LastInsertID : Integer;

Используя процедуру OutNode, мы последовательно выводим узлы дерева. Как и куда будут выводиться эти узлы, не важно. Параметр Level определяет уровень узла (для древовидного отображения). Предполагается также, что запросы, полученные от функции OpenQuery, автоматически уничтожаются, после использования. Чтобы не загромождать код вызовом метода Free, обработкой исключений и прочими деталями, не представляющими сейчас интереса.

В статье рассматриваются три варианта представления деревьев. Для каждого из них приведены реализации пяти операций, которые показались мне наиболее необходимыми. Вот эти операции: {Процедура выводит поддерево, начиная с узла Root (нижнее замыкание). Для вывода используется вспомогательная процедура OutNode. Как и куда осуществляется вывод, не важно) procedure OutTree(Root : Integer); {Процедура добавляет узел с названием Name, делая его потомком узла Parent.} procedure AddNode(Parent : Integer; const Name : String); {Процедура удаляет поддерево, начиная с узла Node} procedure DeleteNode(Node : Integer);


{Функция возвращает true, если узел Node находится в поддереве узла Parent. Данная функция необходима для проверки того, можно ли изменить структуру дерева и сделать узел Parent потомком узла Node. Если проверку не проводить, то возможно появление циклов, которые в дереве недопустимы.} function NodeInSubtree(Node,Parent : Integer) : Boolean; {Процедура изменяет структуру дерева, назначая узел Parent родителем узла Node.} procedure SetParent(Node,Parent : Integer);



Содержание раздела