Деревовидні (ієрархічні) структури даних в реляційних базах даних
Кузьменко Дмитро, iBase.ru
Сьогодні більшість сховищ даних, як простих так і складних, побудовані на основі реляційних баз даних. У них використовуються або файл-серверні системи (dBase, Paradox, Clipper, FoxPro, Access), або SQL-сервери (Oracle, Informix, Sybase, Borland InterBase, MS SQL і т. Д.). Реляційні бази даних в більшості випадків задовольняють вимоги будь-якої предметної області даних, але часті і випадки коли потрібне представлення і зберігання даних в ієрархічному вигляді. Варіанти побудови таких уявлень в реляційної моделі і будуть розглянуті в даній статті.
використовувані інструменти
Як інструмент розробки клієнтського додатка в даній статті застосовується Delphi, а в якості SQL-сервера - Borland InterBase SQL Server 4.x. Насправді для теоретичної частини статті це несуттєво, а практична частина містить мінімум специфіки використання зазначених інструментів.
Таблиці-об'єкти
Для того, щоб підійти до побудови "дерев", ми повинні розглянути, що являє собою реляційна таблиця.
Таблиця має структуру, т. Е. Складається з полів, що описують характеристики якогось об'єкта, наприклад, "Людина". Записи такої таблиці (можна назвати її "Люди") представляють собою характеристики примірників об'єктів одного і того ж типу. Ідентифікатор дозволяє знайти серед безлічі екземплярів один екземпляр необхідного типу.
Однотипні пов'язані об'єкти
Припустимо що ми дійсно хочемо створити таблицю "Люди", в якій потрібно відстежувати родинні зв'язки типу батько-нащадок. Для простоти уявімо собі, що у нащадків батько може бути тільки один (наприклад, "Батько"):
Для того, щоб зберігати інформацію про батьку примірника об'єкта, будь-який об'єкт в таблиці повинен крім ідентифікатора мати атрибут "батько". На малюнку видно, що всі "Нащадки" мають батька, крім самого "Родітель1". Примірник "Родітель1" може в принципі взагалі бути відсутнім - можна прийняти що у нащадків першого рівня завжди один і той же батько, тому зберігати інформацію про нього необов'язково (в яких випадках це необхідно, ми розглянемо далі).
Отже, структура нашої "родовитої" таблиці буде виглядати наступним чином:
Поле "Батько" завжди посилається на значення поля "Ідентифікатор". Тут нас чекає підводний камінь - якби ми вирішили, що "... посилається на існуюче значення поля ...", і відповідно до реляційними правилами оголосили-б зв'язок конструкцією SQL "alter table ... add constraint ... foreign key", то потрапили-б в замкнуте коло "курка і яйце". Як створити екземпляр об'єкта якщо батька немає? Дійсно, може-ли існувати екземпляр об'єкта без вказівки батька? Щоб позбутися на початковому етапі хоча-б від першого питання, потрібно відмовитися від декларації зв'язку батько-> Ідентифікатор на рівні сервера. Це знизить захищеність даних, але позбавить нас від довгих роздумів на самому початку шляху. На друге питання (може-ли існувати екземпляр без батька) можна безболісно відповісти "ні", встановивши обмеження цілісності для поля "Батько" як "значення обов'язково" (NOT NULL).
Оскільки ми відмовилися від створення FK, по полю "батько" не автоматично побудований індекс, який був би потрібен оптимізатора для прискорення запитів, які обирають групи нащадків для конкретного батька. Не забудьте додати такий індекс потім, вручну.
Давайте тепер подивимося, як буде виглядати таблиця, заповнена екземплярами об'єктів з малюнка 2:
Решта атрибути ...
Тоді, щоб отримати з таблиці OBJECTS все кореневі елементи, досить виконати запит
SELECT * FROM OBJECTS
WHERE PARENT = 0
Відповідь на цей запит буде виглядати так:
Тепер, для того щоб отримати всіх нащадків наприклад примірника "Родітель1", потрібно використовувати його ID в тому ж самому запиті як ідентифікатор батька:
SELECT * FROM OBJECTS
WHERE PARENT = 1
Відповідь на цей запит буде виглядати так:
2 1 Потомок1
3 1 Потомок2
Таким чином отримати список записів будь-якого рівня можна одним і тим же запитом:
ВИБРАТИ ВСЕ_ПОЛЯ З ТАБЛИЦІ
ДЕ БАТЬКО = ІДЕНТИФІКАТОР
Уявити таку інформацію можна в вигляді "каталогів" і "файлів", наприклад, як в Windows Explorer. Клік миші по каталогу призводить до "провалювання" на більш глибокий рівень, і т. Д.
Звичайно, для того щоб мати можливість повернутися назад по дереву потрібно в додатку зберігати "список повернення", т. Е. Список елементів, за якими ми заглибилися всередину, з ідентифікаторами їх власників (своєрідний "стек"). З іншого боку, потрібно мати можливість вибрати весь шлях аж до кореня починаючи з довільного елемента. Це можна зробити написавши збережену процедуру (якщо ваш SQL-сервер підтримує стандарт ANSI SQL 3 в частині процедур (PSM) і дозволяє з збережених процедур повертати набори записів). Ось як виглядає така процедура для InterBase:
CREATE PROCEDURE GETPARENTS (ID INTEGER)
RETURNS (DID INTEGER, OID INTEGER, NAME VARCHAR (30))
AS
BEGIN
WHILE (: ID> 0) DO / * шукаємо до кореня * /
BEGIN
SELECT O.ID, O.PARENT, O.NAME
FROM OBJECTS O
WHERE O.ID =: ID
INTO: DID. OID. NAME;
ID =: OID; / * Код батька для наступної вибірки * /
SUSPEND;
END
END
В процедуру передається ідентифікатор, з якого потрібно підніматися "вгору" по дереву. У циклі, поки ідентифікатор не став рівним 0 (піднялися вище кореневого елемента) відбувається вибірка записи з зазначеним ідентифікатором, потім ідентифікатор змінюється на ідентифікатор батька.
Виконання цієї процедури для наших даних привело б до наступного результату (запит SELECT * FROM GETPARENTS 4):
4 3 Потомок3
3 1 Потомок2
1 0 Родітель1
Поєднуючи поля "NAME" справа наліво ми отримаємо повний "шлях" від поточного елемента до кореня: "Родітель1 / Потомок2 / Потомок3". Цей шлях можна використовувати або для показу користувачеві, або для внутрішніх цілей програми.
Візуалізація деревовидної структури
Для візуалізації подібної структури можна скористатися компонентом TTreeView, що поставляється в Delphi 2.0 і 3.0. Цей компонент формує уявлення типу "outline" за допомогою об'єктів TTreeNode. На жаль, з цим типом об'єкта працювати не дуже зручно, оскільки він зроблений від стандартного елемента GUI і при розробці не можна використовувати спадкування. Для зберігання додаткових даних вузла дерева доводиться використовувати поле TTreeNode.Data, що представляє собою покажчик на довільний об'єкт або структуру даних.
При відображенні невеликої кількості записів (до 1000) можна зчитувати в пам'ять всю таблицю і формувати TTreeView в пам'яті, не звертаючись потім до бази даних. Однак якщо потрібно періодично перечитувати "дерево", то такий підхід буде занадто повільним. Оптимальним було б перечитування тільки розкривається гілки дерева. При цьому перечитування відбуватиметься максимально швидко, т. К. Навіть найскладніша деревоподібна структура містить максимум 200-500 елементів в одній гілці.
Для реалізації перечитування записів по "відкриттю" гілки дерева можна використовувати наведений вище запит з вибіркою елементів однієї гілки.
procedure TMainForm.NodeViewExpanding (Sender: TObject; Node: TTreeNode;
var AllowExpansion: Boolean);
begin
GetExpandingItems (Node);
end;
Припустимо, що у нас на формі є компонент Query1, який містить запит
SELECT * FROM OBJECTS
WHERE PARENT =: Parent
Процедура GetExpandingItems може бути реалізована наступним чином:
procedure TMainForm.GetExpandingItems (var Node: TTreeNode)
var NewNode: TTreeNode;
begin
<если не передан "раскрываемый" узел, то это самый первый узел.
інакше потрібно як Parent передати в запит ідентифікатор
елемента, який ми не зовсім коректно будемо зберігати в
Node.Data як ціле число, а не як покажчик на структуру даних>
if Node = nil then
Query1.ParamByName ( 'Parent'). AsInteger: = 0
else
begin
Query1.ParamByName ( 'Parent'). AsInteger: = integer (Node.Data);
Node.DeleteChildren; <удалить "подэлементы" если они были>
end;
Query1.Open;
Query1.First;
while not Query1.EOF do
begin
NewNode: = TreeView1.Items.AddChildObject (Query1.FieldByName ( 'NAME'). AsString)
integer (NewNode.Data): = Query1.FieldByName ( 'ID'). asInteger;
Query1.Next;
end;
Query.Close;
end;
Після виконання цієї функції створюються елементи, дочірні для зазначеного Node, або кореневі елементи, якщо Node = nil.
Однак в цьому випадку структура даних таблиці OBJECTS не дає нам можливості дізнатися (без додаткового запиту) чи є у елемента його "піделементи". І TreeView для всіх елементів не буде показувати ознака "розкриття" або значок "+".
Для цих цілей без розширення нашої структури даних не обійтися. Очевидно необхідно додати в таблицю OBJECTS поле, яке буде містити кількість дочірніх елементів (0 або більше). Таке поле можна додати
ALTER TABLE OBJECTS ADD CCOUNT INTEGER DEFAULT 0;
Але хто буде модифікувати це поле, записуючи туди нове кількість дочірніх елементів? Можна, звичайно, робити це і з клієнтського застосування. Однак найбільш правильним рішенням буде додавання тригерів на вставку, зміна і видалення записів в таблиці OBJECTS.
Тригер по вставці запису повинен збільшити кількість "дітей" у свого батька:
CREATE TRIGGER TBI_OBJECTS FOR OBJECTS
ACTIVE BEFORE INSERT POSITION 0
AS
BEGIN
UPDATE OBJECTS O
SET O.CCOUNT = O.CCOUNT + 1
WHERE O.ID = new.PARENT;
END
Тригер зі зміни перевіряє, чи не міняється батько елемента. Якщо так, то значить елемент переміщається від одного батька до іншого і потрібно відповідно зменшити CCOUNT у старого і збільшити у нового.
CREATE TRIGGER TBU_OBJECTS FOR OBJECTS
ACTIVE BEFORE UPDATE POSITION 0
AS
BEGIN
if (old.PARENT <> new.PARENT) then
begin
UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT - 1
WHERE O.ID = old.PARENT;
UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT + 1
WHERE O.ID = new.PARENT;
end
END
При видаленні потрібно зменшити кількість "дітей" у власника:
CREATE TRIGGER TBD_OBJECTS FOR OBJECTS
ACTIVE BEFORE DELETE POSITION 0
AS
BEGIN
UPDATE OBJECTS O
SET O.CCOUNT = O.CCOUNT - 1
WHERE O.ID = old.PARENT;
END
(Зверніть увагу, що у всіх тригерах при зверненні до таблиці іспользуетс псевдонім O, а для полів в тригері використовується уточнітелі new. Або old. Це зроблено для того, щоб SQL-сервер не переплутав змінювані поля в UPDATE і поля таблиці в контексті тригера) .
Тепер таблиця OBJECTS повністю автоматично відстежує кількість "дітей" у кожного елемента.
Увага! Дана реалізація відстеження кількості дочірніх елементів призводить до того, що одночасне додавання двох елементів до одного з батьків призведе до блокування (deadlock) поновлення батьківської записи. У багатокористувацької середовищі таку ситуацію треба передбачати, наприклад, намагатися робити додавання / видалення або перенесення елементів в максимально коротких транзакціях read_committed, а при виникненні блокування спробувати ще раз виконати операцію без виведення повідомлення про помилку користувачеві. Додатково див. "Перенесення елементів" у другій частині статті.
Для того щоб TTreeNode "знав" про наявність у нього дітей, поле Data має вже вказувати на якусь структуру даних. Нам потрібно зберігати ідентифікатор вузла, на всякий випадок ідентифікатор батька, і кількість дочірніх записів, а текст (NAME) можна зберігати в TTreeNode, як це зроблено в наведеному вище прикладі. Отже, створимо додаткову структуру:
type
PItemRec = ^ ItemRec;
ItemRec = record
Id. integer;
Parent: integer;
CСount: integer;
end;
При створенні нового TreeNode нам доведеться тепер розподіляти пам'ять для ItemRec
var R: PItemRec;
.
NewNode: = TreeView1.Items.AddChildObject (Query1.FieldByName ( 'NAME'). AsString);
New (R);
NewNode.Data:=R;
R ^ .Id: = Query1.FieldByName ( 'ID'). AsInteger;
R ^ .Parent: = Query1.FieldByName ( 'PARENT'). AsInteger;
R ^ .CCount: = Query1.FieldByName ( 'CCOUNT'). AsInteger;
NewNode.HasChildren: = R ^ .CCount> 0;
.
(Для того щоб правильно звільняти пам'ять, займану операцією New (R), необхідно в методі TTreeView.OnDeletion написати один рядок - Dispose (PItemRec (Node.Data); Це звільнить зайняту пам'ять при видаленні будь-якого елементу TTreeNode або групи елементів).
Властивість HasChildren призведе до автоматичної промальовуванні значка "+" в TreeView у елемента, який має дочірні елементи. Таким чином ми отримуємо уявлення дерева без необхідності зчитувати всі його елементи відразу.