Structuri de arbori (ierarhică) de date într-o bază de date relațională

Kuzmenko Dmitri, iBase.ru

Astăzi, cele mai multe depozite de date, atât simple și complexe, sunt bazate pe baze de date relaționale. Ei folosesc un sistem de fișiere-server (dBase, Paradox, Clipper, FoxPro, Access), sau SQL servere (Oracle, Informix, Sybase, Borland Interbase, MS SQL, și așa mai departe. D.). Bazele de date relaționale, în majoritatea cazurilor, să îndeplinească cerințele din orice domeniu de date, dar de multe ori cazul în care doriți să vizualizați și să stocheze datele într-o formă ierarhică. Opțiuni pentru proiectarea unor astfel de reprezentări în modelul relațional, și vor fi discutate în acest articol.

scule

Ca instrument de dezvoltare aplicație client în acest articol se aplică Delphi, precum SQL-Server - Borland Interbase SQL Server 4.x. De fapt, pentru partea teoretică a articolului nu este esențială, dar partea practică conține cel puțin utilizarea specifică a acestor instrumente.

obiecte de masă

Pentru a ajunge la construcția de „copaci“, trebuie să luăm în considerare ceea ce este un tabel relational.

Tabelul are o structură, adică. E. Include domenii care descriu caracteristicile unui anumit obiect, de exemplu, „om“. Înregistrarea unui tabel (poate fi numită „Oameni“) reprezintă caracteristici ale obiectelor instanțe de același tip. Identificatorul permite căutarea între o multitudine de exemplare un exemplar de tipul dorit.

Același tip de obiecte legate

Să presupunem că într-adevăr doriți să creați un tabel „People“, în care aveți nevoie pentru a ține evidența legăturilor de familie, cum ar fi relația părinte-copil. Pentru simplificare, să ne imaginăm că la descendenții unui părinte nu poate fi decât un singur (de exemplu, „părinte“):

Pentru a stoca informații referitoare la instanța mamă a unui obiect, orice obiect din tabel trebuie să fie în plus față de identificatorul atributului „părinte“. Figura arată că toate „descendenți“ sunt părinte, cu excepția „Roditel1“. Copie a „Roditel1“ poate fi, în principiu, absentă - se poate considera că descendenții primul nivel este întotdeauna unul și același părinte, astfel încât să păstreze informațiile cu privire la aceasta în mod necesar (în ce cazuri este necesar, ne vom uita la mai târziu).

Astfel, structura noastră „high-născuți“ din tabel este după cum urmează:

„Mamă“ se referă întotdeauna la valoarea câmpului „ID“. Aici ne așteptăm deznodamant - dacă ne-am decis că „... se referă la valoarea existentă a câmpului ...“, și în conformitate cu normele relaționale declarate, ar lega de proiectare SQL «modifica tabelul ... adăugați constrângere ... cheie străină», hit-ar vicios cerc „de pui și ouă“. Cum de a crea o instanță a unui obiect, dacă părintele nu este? Într-adevăr, poate, exista o instanță fără un părinte? Pentru a scapa de stadiul inițial, deși, ar fi prima întrebare, este necesar să se renunțe la Declarația de comunicare parentală> identificator la nivel de server. Acest lucru va reduce securitatea datelor, ci ne izbaveste de mult gândit la început. A doua întrebare (poate exista o instanță, fără un părinte) poate răspunde în condiții de siguranță „nu“, stabilind constrângerea de integritate pentru „părinte“ ca „este necesară o valoare“ (NOT NULL).

Pentru că am refuzat să creeze FK, pe câmpul „părinte“ nu este un index este construit în mod automat, ceea ce ar fi necesar pentru a accelera de optimizare a interogare, alegând grupul de descendenți pentru un anumit părinte. Nu uitați să adăugați un index și apoi manual.

Acum, să vedem cum se va arata ca un tabel plin cu copii ale obiectelor din imagine 2:

Alte atribute ...

Apoi, pentru a iesi din tabelul OBIECTE toate elementele rădăcină care efectuează destul de anchetă

SELECT * FROM OBIECTE
UNDE PARENT = 0

Răspunsul la această întrebare ar arata astfel:

Acum, în scopul de a obține toți urmașii lui un astfel de caz „Roditel1“ ID-ul să-l folosească în aceeași interogare ca ID al părintelui:

SELECT * FROM OBIECTE
UNDE PARENT = 1

Răspunsul la această întrebare ar arata astfel:

01 februarie Potomok1
01 martie Potomok2

Astfel, pentru a obține o listă de înregistrări de nivel poate fi una și aceeași interogare:

ALEGE VSE_POLYA TABELURILOR
UNDE PARENT = identifier

Pentru a oferi astfel de informații pot fi sub formă de „directoare“ și „fișiere“, cum ar fi în Windows Explorer. Dacă faceți clic pe catalogul duce la „căderea prin“ la un nivel mai profund, și așa mai departe. D.

Desigur, pentru a putea să se întoarcă pe copac trebuie să fie stocate în aplicația „lista de întoarcere“, de ex., E. O listă de articole pe care le-am plecat adânc în interiorul, identificatorii proprietarilor respectivi (un fel de „stivă“). Pe de altă parte, trebuie să aibă posibilitatea de a alege tot drumul până la rădăcinile pornind de la un element arbitrar. Acest lucru se poate face prin scris o procedură stocată (în cazul în care SQL-Server suportă standardul ANSI SQL 3 în ceea ce privește procedurile stocate (PSM), și vă permite să se întoarcă seturi de înregistrări de proceduri stocate). Aici este o astfel de procedură pentru Interbase:

CREATE PROCEDURE GETPARENTS (ID INTEGER)
RETURNĂRI (DID INTEGER, OID INTEGER, NUME VARCHAR (30))
AS
BEGIN
While (: ID> 0) DO / * caută să rădăcină * /
BEGIN
SELECT O.ID, O.PARENT, O.NAME
OBIECTE DE LA O
UNDE O.ID =: ID
ÎN: DID. OID. NAME;
ID =: OID; / * Cod părinte pentru următoarea probă * /
SUSPENDARE;
END
END

Procedura este trecut ID-ul de la care doriți să urce „în sus“ copac. În bucla, identificatorul nu este încă să devină egal cu 0 (nu ridicat deasupra elementului rădăcină), are loc proba de înregistrare cu respectivul identificator, identificatorul este apoi înlocuit cu identificatorul părinte.

Efectuarea acestei proceduri pentru datele noastre ar conduce la următorul rezultat (interogare SELECT * FROM GETPARENTS 4):

03 aprilie Potomok3
01 martie Potomok2
1 0 Roditel1

Combinând câmpul „NAME“ de la dreapta la stânga, obținem o „cale“ completă a elementului curent la rădăcină: „Roditel1 / Potomok2 / Potomok3“. Această cale poate fi folosit fie pentru a afișa pentru utilizator, sau pentru aplicații în scopuri interne.

Vizualizarea structurii arborelui

Pentru a vizualiza o astfel de structură, puteți utiliza TTreeView componente, furnizate în Delphi 2.0 și 3.0. Această componentă generează o reprezentare a „contur“ de tip folosind obiecte TTreeNode. Din păcate, cu acest tip de facilitate la locul de muncă nu este foarte convenabil, deoarece este produs dintr-un GUI elemente standard și design-ul nu se poate folosi de moștenire. Pentru a stoca date suplimentare de nod copac trebuie să fie folosit câmpul TTreeNode.Data este un pointer la orice structură de obiect sau de date.

La afișarea unui număr mic de intrări (până la 1000) pot fi citite în memorie și pentru a forma întregul TTreeView tabel în memorie, apoi fără a se referi la baza de date. Cu toate acestea, în cazul în care este necesară revizuirea periodică „arbore“, o astfel de abordare ar fi prea lent. Optimul ar fi dezvăluite doar reciti ramuri de copac. În același timp, re-lectură va avea loc cât mai repede posibil, t. Pentru a. Chiar și structura arborescentă cel mai complex conține un maxim de 200-500 celule într-o singură ramură.

Pentru a pune în aplicare re-citirea înregistrărilor pentru „arat“ de copac, puteți utiliza o interogare cu elemente de probă de o ramură de mai sus.

Procedura TMainForm.NodeViewExpanding (Expeditor: TObject; Node: TTreeNode;
var AllowExpansion: Boolean);
începe
GetExpandingItems (Node);
se încheie;

Să presupunem că avem o componentă pe un formular Query1, care include o cerere

SELECT * FROM OBIECTE
UNDE PARENT =: Parent

Procedura GetExpandingItems poate fi pus în aplicare după cum urmează:

TMainForm.GetExpandingItems procedură (var nod: TTreeNode)
var newNode: TTreeNode;
începe
<если не передан "раскрываемый" узел, то это самый первый узел.
în caz contrar este necesar ca părinte transferat la cererea ID-
membru care nu vom fi în întregime corectă pentru a păstra
Node.Data ca un număr întreg și nu ca un pointer la structura de date>
dacă Nodul = zero atunci
. Query1.ParamByName ( 'mamă') asInteger: = 0
altfel
începe
Query1.ParamByName ( 'mamă') asInteger: = integer (Node.Data) ;.
Node.DeleteChildren; <удалить "подэлементы" если они были>
se încheie;
Query1.Open;
Query1.First;
în timp ce nu fac Query1.EOF
începe
NewNode: = TreeView1.Items.AddChildObject (Query1.FieldByName ( 'NAME') asString.)
. Integer (NewNode.Data): = Query1.FieldByName ( 'ID') asInteger;
Query1.Next;
se încheie;
Query.Close;
se încheie;

După efectuarea acestei funcții sunt elemente pentru nodul copil, sau rădăcină elemente menționate anterior, în cazul în care Nod = zero.

Cu toate acestea, în acest caz, structura de date OBIECTE tabel nu ne permite să știm (fără a cere) „sub-elemente“, indiferent dacă sunt sau nu elementul său. Și TreeView pentru toate elementele care nu se va afișa un semn sau pictograma „rezolvat“ „+“.

Pentru aceste scopuri, fără o extensie a structurilor noastre de date nu pot face. Este în mod evident necesar să se adauge un câmp OBIECTE tabel care va conține numărul de elemente copil (0 sau mai mult). Un astfel de câmp poate fi adăugat

ALTER OBIECTE TABLE ADD CCOUNT INTEGER DEFAULT 0;

Dar cine va modifica acest domeniu, noua înregistrare la numărul de copii? Puteți face cu siguranță că, și din aplicația client. Cu toate acestea, soluția cea mai corectă este de a adăuga declanșatoare pentru a insera, modifica sau șterge intrările din tabelul de obiecte.

Trigger pentru a insera o înregistrare este de a crește numărul de „copii“ de la societatea-mamă:

CREATE TBI_OBJECTS TRIGGER PENTRU OBIECTE
ACTIVE INSERT ÎNAINTE POZIȚIA 0
AS
BEGIN
UPDATE OBIECTE O
SET O.CCOUNT = O.CCOUNT + 1
UNDE O.ID = new.PARENT;
END

Un declanșator pentru a schimba verifică dacă modificările elementul părinte. Dacă da, înseamnă că elementul este mutat de la un părinte la altul și trebuie să fie redusă în mod corespunzător CCOUNT vechi și nouă creștere.

CREATE TBU_OBJECTS TRIGGER PENTRU OBIECTE
ACTIVE ÎNAINTE UPDATE POZIȚIA 0
AS
BEGIN
în cazul în care (old.PARENT <> new.PARENT) atunci
începe
UPDATE OBIECTE O SET O.CCOUNT = O.CCOUNT - 1
UNDE O.ID = old.PARENT;
UPDATE OBIECTE O SET O.CCOUNT = O.CCOUNT + 1
UNDE O.ID = new.PARENT;
capăt
END

Când ștergeți necesitatea de a reduce numărul de „copii“ de la proprietar:

CREATE TBD_OBJECTS TRIGGER PENTRU OBIECTE
ACTIVE ȘTERGE ÎNAINTE POZIȚIA 0
AS
BEGIN
UPDATE OBIECTE O
SET O.CCOUNT = O.CCOUNT - 1
UNDE O.ID = old.PARENT;
END

(Vă rugăm să rețineți că toate declanșează atunci când se referă la masa a folosit un pseudonim Despre, precum și pentru câmpurile din declanșator folosit calificativul nou. Sau vechi. Acest lucru se face pentru a se asigura că SQL Server amestecat câmpurile care se pot modifica în UPDATE, și câmpurile de masă în context de declanșare) .

Acum, OBIECTE tabelul complet automat urmărește numărul de „copii“ ale fiecărui element.

Atenție! Această implementare a urmăririi numărului de elemente copil duce la faptul că adăugarea simultană a două elemente la un singur părinte va bloca (blocaj) actualizarea înregistrării părinte. Într-un mediu multiutilizator o astfel de situație, este necesar să se prevadă, de exemplu, să încerce să facă adăuga / șterge sau transferul de articole în cel mai scurt tranzacțiile READ_COMMITTED, iar în caz de blocare a încerca din nou să efectueze operația fără a afișa un mesaj de eroare către utilizator. Pentru mai multe informații consultați. „Elemente în mișcare“, în a doua parte a articolului.

Pentru a TTreeNode „cunoscut“ despre prezența copiilor săi, câmp de date trebuie să indice deja într-o anumită structură de date. Avem nevoie de a păstra ID-ul nodului, doar în cazul în care identificatorul de bază, precum și numărul de înregistrări pentru copii și textul (numele) pot fi stocate în TTreeNode, la fel ca în exemplul de mai sus. Deci, vom crea o structură suplimentară:

tip
PItemRec = ^ ItemRec;
ItemRec = înregistrare
Id-ul. întreg;
Părinte: întreg;
CSount: integer;
se încheie;

Când creați un nou TreeNode, vom avea acum să aloce memorie pentru ItemRec

var R: PItemRec;
.
NewNode: = TreeView1.Items.AddChildObject (Query1.FieldByName ( 'NAME') asString.);
Noi (R);
NewNode.Data:=R;
. R ^ .Id: = Query1.FieldByName ( 'ID') asInteger;
. R ^ .Parent: = Query1.FieldByName ( 'PARINTE') asInteger;
. R ^ .CCount: = Query1.FieldByName ( 'CCOUNT') asInteger;
NewNode.HasChildren: = R ^ .CCount> 0;
.

(Pentru a elibera în mod corespunzător memoria ocupată de operație nouă (R), este necesară în metoda de a scrie o singură linie TTreeView.OnDeletion - Evacuarea (PItemRec (Node.Data) Acest lucru va elibera memoria ocupată prin îndepărtarea TTreeNode orice element sau grup de elemente).

HasChildren proprietate va atrage în mod automat pictograma „+“ în TreeView un element care are elemente copil. Astfel, vom obține o vedere copac fără a fi nevoie de a citi toate elementele dintr-o dată.