Tree структури (йерархична) данни в релационна база данни

Kuzmenko Дмитрий, iBase.ru

Днес, най-за съхранение на данни, както прости и сложни, са базирани на релационни бази данни. Използват се както на файлове сървърни системи (DBASE, Paradox, Clipper, FoxPro, Access), или SQL сървъри (Oracle, Informix, Sybase, Borland InterBase, MS SQL, и така нататък. Г.). Релационни бази данни в повечето случаи, отговарят на изискванията на всеки домейн данни, но често се случва, когато искате да видите и да се съхраняват данните в йерархична форма. Опции за проектиране на такива представителства в релационния модел, както и ще бъдат обсъдени в тази статия.

използваните инструменти

Като инструмент за развитие на клиентско приложение в тази статия се отнася Delphi, както и SQL-сървър - Borland InterBase SQL Server 4.x. В действителност, за теоретичната част на статията не е от съществено значение, но практическата част съдържа най-малко специфичното използване на тези инструменти.

Таблица обекти

За да се стигне до изграждането на "дървета", трябва да имаме предвид това, което е релационна таблица.

Таблица има структура, т.е.. Д. Тя включва полета, описващи характеристиките на определен обект, например, "човек". Записване на маса (това може да се нарече "Хора") представляват характеристики на обектите случаи от същия вид. Идентификаторът позволява търсене сред множество копия по едно копие от желания тип.

Същият тип, свързани обекти

Да предположим, че ние наистина искаме да създадете таблица "Хора", в което се нуждаете, за да следите на семейните връзки, като например връзката родител-дете. За простота, нека си представим, че при децата на родител може да бъде само един (например, "майка"):

С цел да се съхранява информация за родителската инстанция на обект, който и да е обект в таблицата трябва да бъде в допълнение към идентификатор "родител" атрибут. Фигурата показва, че всички "потомци" са родителя, с изключение на "Roditel1". Копие на "Roditel1" по принцип може да отсъства - може да се приема, че потомците на първото ниво е винаги една и съща майка, така че съхранява информацията за него е задължително (в кои случаи е необходимо, ние ще разгледаме по-късно).

По този начин структурата на нашата "знатен" на таблицата, е както следва:

В "Родител" винаги се отнася до стойността на полето "ID". Тук ние чакаме капан - ако ние решихме, че "... се отнася до съществуващата стойността на полето ...", както и в съответствие с релационни правилата, обявени, ще сочат дизайн SQL "ALTER TABLE ... добавите ограничение ... външен ключ", хит-би порочен кръг "кокошката и яйцето". Как да се създаде копие на обекта, ако родителят не е? В действителност, тя може да има като пример без родител? За да се отървете от началния етап обаче, ще бъде на първия въпрос, е необходимо да се откаже от Декларацията от родителска комуникация> идентификатор на ниво сървър. Това ще намали сигурността на данните, но избави ни от много мисъл в началото. Вторият въпрос (може да има инстанция-без родител) може спокойно да се отговори с "не", задаване на ограничение цялост за "Родител" като "стойност е задължителна" (NOT NULL).

Защото ние отказа да се създаде FK, на "майка" на полето не е индекс е изградена автоматично, което ще бъде необходимо да се ускори оптимизатора на заявки, избирайки групата на потомци на конкретен родител. Не забравяйте да добавите индекс и след това ръчно.

Сега нека видим как тя ще изглежда като една маса, пълна с копия на обекти в картината 2:

Други атрибути ...

След това, за да се измъкнем от масата на обектите всички кореноплодни елементи, които се представят доста запитване

SELECT * FROM ОБЕКТИ
КЪДЕТО майка = 0

Отговорът на този въпрос ще изглежда така:

Сега, за да получите всички потомци на подобен случай "Roditel1" ID, за да го използвате в една и съща заявка, като идентификацията на родителя:

SELECT * FROM ОБЕКТИ
КЪДЕТО майка = 1

Отговорът на този въпрос ще изглежда така:

01 февруари Potomok1
1 март Potomok2

По този начин, за да получите списък на всички записи ниво може да бъде една и съща заявка:

ИЗБЕРЕТЕ VSE_POLYA НА МАСИ
При основен = идентификатор

За да се предостави такава информация може да бъде под формата на "директории" и "досиета", като в Windows Explorer. Кликвайки каталога води до "пропадане" на по-дълбоко ниво, и така нататък. Г.

Разбира се, за да бъде в състояние да се върне на дървото трябва да се съхраняват в приложение "списъка завръщане", т.е.. Д. списък на елементите, на които ние сме преминали дълбоко вътре, идентификаторите на съответните им собственици (вид на "купчина"). От друга страна, трябва да имат възможност да избират чак до корените, започвайки от произволно елемент. Това може да стане чрез написването на съхранена процедура (ако SQL-сървър поддържа стандарта ANSI SQL 3 от гледна точка на съхранени процедури (PSM), и ви позволява да се върнете рекордни комплекти от съхранени процедури). Ето такава процедура за InterBase:

CREATE ПРОЦЕДУРА GETPARENTS (ID INTEGER)
Декларации (DID INTEGER, OID INTEGER, NAME VARCHAR (30))
AS
ЗАПОЧНЕТЕ
Докато (: ID> 0) ДА / * стреми да корен * /
ЗАПОЧНЕТЕ
SELECT O.ID, O.PARENT, O.NAME
От предмети О
КЪДЕТО O.ID =: ID
В: DID. OID. ИМЕ;
ID =: OID; / * Майка код за следващата проба * на /
СПРЕТЕ;
END
END

Процедурата е преминал ID, от която искате да се изкачи "нагоре" дървото. В линия, идентификатора все още не е стане равно на 0 (не е повишила над корен елемент) се появява проба запис със споменатия идентификатор, идентификатор след това се заменя със идентификатор майка.

Изпълнението на тази процедура за нашите данни ще доведе до следния резултат (заявка SELECT * FROM GETPARENTS 4):

03 апр Potomok3
1 март Potomok2
1 0 Roditel1

Комбинирането на поле "NAME" от дясно на ляво, ние получаваме пълна "пътя" на текущия елемент на корена: "Roditel1 / Potomok2 / Potomok3". Този път може да се използва за да се покаже на потребителя, или за вътрешни приложения цели.

Визуализация на дървовидна структура

За да се визуализира на такава структура, можете да използвате компонент TTreeView, предоставена в Delphi 2.0 и 3.0. Този компонент генерира изображение на тип "очертанията", използвайки TTreeNode обекти. За съжаление, с този тип съоръжение за работа не е много удобно, тъй като той се произвежда от стандартни графични елементи и дизайна не може да използва наследството. За да съхранявате допълнителни данни дърво възли трябва да бъдат използвани поле TTreeNode.Data е показалец към всеки обект или данни структура.

Когато и да показва малък брой записи (до 1000) може да се прочете в паметта и да се образува цялата маса TTreeView в паметта, а след това, без да се позовава на базата данни. Въпреки това, ако е необходимо да се прави периодичен преглед "дърво", такъв подход би бил твърде бавен. Оптималната ще се предоставя само на препрочитам клоните на дърветата. В същото време препрочитането ще се проведе възможно най-бързо, т. За да се. Дори и най-сложна структура дърво съдържа максимум 200-500 клетки в един клон.

За изпълнение на повторното четене на записи за "оре" на дървото, може да използвате заявка с примерни елементи от един клон по-горе.

процедура TMainForm.NodeViewExpanding (Sender: TObject; възел: TTreeNode;
Var AllowExpansion: булеви);
започвам
GetExpandingItems (възел);
приключи;

Нека приемем, че имаме компонент във формуляр Query1, която включва искане

SELECT * FROM ОБЕКТИ
КЪДЕТО майка =: майка

процедура GetExpandingItems може да се прилага, както следва:

Процедура TMainForm.GetExpandingItems (VAR възел: TTreeNode)
Var NewNode: TTreeNode;
започвам
<если не передан "раскрываемый" узел, то это самый первый узел.
необходимото като родител прехвърлени към искането на ID
член, че ние няма да сме съвсем правилно да се има
Node.Data като цяло число, а не като указател към структурата на данните>
ако Node = нула тогава
. Query1.ParamByName ( "майка") asInteger: = 0
още
започвам
Query1.ParamByName ( "майка") asInteger: = цяло число (Node.Data) ;.
Node.DeleteChildren; <удалить "подэлементы" если они были>
приключи;
Query1.Open;
Query1.First;
докато не се направи Query1.EOF
започвам
NewNode: = TreeView1.Items.AddChildObject (Query1.FieldByName ( "NAME") asString).
. Цяло число (NewNode.Data): = Query1.FieldByName ( "ID") asInteger;
Query1.Next;
приключи;
Query.Close;
приключи;

След извършване на тази функция са елементи за споменатите дете възел, или корен елементи, ако възел = нула.

Въпреки това, в този случай структурата на данните на обектите на маса, не ни позволява да се знае (без да иска) или не му елемент "под-елементи". И TreeView за всички елементи няма да се появи в знак на "решен" или иконата "+".

За тези цели, без удължаване на нашите структури от данни не може да се направи. Очевидно е необходимо да се добавят поле маса предмети, които ще съдържа броя на подчинените елементи (0 или повече). може да се добави такова поле

Промяна на таблица ОБЕКТИ ADD CCOUNT ЦЯЛО DEFAULT 0;

Но кой ще се промени тази област, новият запис на броя на децата? Вие със сигурност може да направи това, както и от заявката на клиента. Въпреки това, най-правилното решение е да добавите тригери да вмъкнете, промяна или изтриване на записи в таблицата с обекти.

Trigger да вмъкнете запис е да се увеличи броят на "деца" от своя родител:

CREATE TRIGGER TBI_OBJECTS за обекти
АКТИВНОТО ПРЕДИ INSERT ПОЗИЦИЯ 0
AS
ЗАПОЧНЕТЕ
UPDATE ОБЕКТИ О
SET O.CCOUNT = O.CCOUNT + 1
КЪДЕТО O.ID = new.PARENT;
END

А спусъка да се промени проверява дали елемент родител се променя. Ако отговорът е да, това означава, че елементът е преместен от един родител на другия и се наложи да бъде намалена съответно CCOUNT старото и новото увеличение.

CREATE TRIGGER TBU_OBJECTS за обекти
АКТИВНОТО ПРЕДИ UPDATE ПОЗИЦИЯ 0
AS
ЗАПОЧНЕТЕ
ако (old.PARENT <> new.PARENT) след това
започвам
UPDATE ОБЕКТИ О SET O.CCOUNT = O.CCOUNT - 1
КЪДЕТО O.ID = old.PARENT;
UPDATE ОБЕКТИ О SET O.CCOUNT = O.CCOUNT + 1
КЪДЕТО O.ID = new.PARENT;
край
END

При изтриване на необходимост да се намали броят на "деца" от собственика:

CREATE TRIGGER TBD_OBJECTS за обекти
АКТИВНОТО ПРЕДИ DELETE ПОЗИЦИЯ 0
AS
ЗАПОЧНЕТЕ
UPDATE ОБЕКТИ О
SET O.CCOUNT = O.CCOUNT - 1
КЪДЕТО O.ID = old.PARENT;
END

(Моля, имайте предвид, че всички се задейства, когато се отнасят до масата, използвани псевдоним За и за полетата в тригер използва квалификант ново. Или възраст. Това се прави, за да се гарантира, че SQL-сървър смесени покажат полетата в актуализацията, както и полетата на таблицата в спусъка контекст) ,

Сега ОБЕКТИ маса напълно автоматично проследява броя на "деца" на всеки елемент.

Внимание! Тази реализация проследяване на броя на подчинените елементи води до факта, че едновременно добавяне на два елемента в един родител ще блокира (безизходица) обновяване на записа родител. В многопотребителска среда такава ситуация е необходимо да се осигури, например, се опитват да направят Добавяне / изтриване или трансфер на изделия в най-кратки READ_COMMITTED сделките, както и в случай на блокиране, опитайте отново да извърши операцията, без да показва съобщение за грешка на потребителя. За повече информация вижте ". Преместването елементи" във втората част на статията.

За да TTreeNode "знаел" за наличието на децата му, Област за данни вече трябва да сочи към някаква структура на данните. Ние трябва да се запази ID възел, за всеки случай идентификатора майка, и на броя на подчинените записи, както и текст (име) да се съхраняват в TTreeNode, както в примера по-горе. Така че, ние ще създаде допълнителна структура:

тип
PItemRec = ^ ItemRec;
ItemRec = рекорд
Id. цяло число;
Майка: цяло число;
CSount: цяло число;
приключи;

Когато създавате нов 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 ( "майка") asInteger;
. R ^ .CCount: = Query1.FieldByName ( "CCOUNT) asInteger;
NewNode.HasChildren: = R ^ .CCount> 0;
.

(За да бъде правилно освобождаване на паметта, заета от операция New (R), е необходимо в метода да напише една линия TTreeView.OnDeletion - изхвърля (PItemRec (Node.Data); Това ще освободи паметта заета от отстраняване TTreeNode всеки елемент или група от елементи).

HasChildren имот автоматично ще рисуване върху иконата "+" в дървовидна структура елемент, който има дъщерни елементи. По този начин ние да получите изглед от дърво без да се налага да прочетете всички елементи наведнъж.