Structuri arborescente

In multe aplicaţii (comerţul electronic, structura organizatorică a unei firme, teoria grafelor, memorarea cunoştinţelor în web-ul semantic, etc.) se utilizează tabele de informaţii ce memorează anumite structuri arborescente (colecţie de arbori), aşa cum apar în următorul exemplu.

In continuare se dă o modalitate de memorare a unei astfel de structuri arborescente (tabele ce se pot folosi în comerţul electronic): 

produse[cod, denumire] 
-- cu informatii despre unele produse/grupuri de produse (noduri in structura arborescenta)
structura[cod, codp, pozitia] 
-- cu memorarea structurii arborescente a multimii de produse (legaturile dintre noduri)

Semnificaţia coloanelor din tabelul structura este:

Pentru produsele din rădăcină nu există înregistrare în tabelul "structura" (acestea nu au un produs părinte). Cu această structură produsele se pot diviza în categorii (pe nivelul 1, care sunt rădăcinile din colecţia de arbori), subcategorii (pe nivelul 2), sub-subcategorii, etc.
In directorul exemple/StrArborescente/ se află instrucţiuni care crează tabelele amintite şi adaugă date în aceste tabele.

Probleme:

Determinarea tuturor descendenţilor unui nod dat (nu numai a nodurilor incluse imediat în nodul curent) se face dificil, mai ales dacă se cere şi nivelul pe care apare fiecare dintre aceste noduri în structura arborescentă.

Rezolvarea acestei probleme se face simplu în Oracle prin folosirea unei variante a instrucţiunii Select-Sql:

Instructiune_select
  [START WITH conditie1
  [CONNECT BY [NOCYCLE] conditie2]]

Aici se observă două clauze noi (START WITH şi CONNECT BY), care pot să apară în orice ordine.
In această variantă a instrucţiunii se cere ca să apară o singură sursă de date (în FROM din SELECT), care poate să fie şi un view. In această sursă (unică) de date trebuie să existe informaţiile necesare pentru a deduce structura arborescentă (colecţia de arbori).

Ca sursă de înregistrări se ia mulţimea generată de instrucţiunea select. Cu clauza "start with" se precizează acele noduri din sursa de date de unde se pleacă la generarea unei structuri arborescente, iar aceste înregistrări formează primul nivel din structura arborescentă care se determină (nodurile rădăcină). Dacă această clauză lipseşte, atunci se iau în considerare toate înregistrările sursei de date (care vor forma un singur nivel), iar dacă această clauză este prezentă, atunci se cere şi clauza "connect by", care va adăuga noi nivele la cele deja determinate.

Clauza "connect by" precizează modul de determinare a legăturilor din structura arborescentă. Pentru un nod deja determinat în structura arborescentă (cu sau fără START WITH) se determină o legătură spre noi noduri în această structură prin conditie2 (condiţie ce apare în această clauză): pentru o înregistrare curentă se determină înregistrările legate de aceasta (din aceeaşi sursă de date) şi care îndeplinesc conditia2 cu valoarea true.

Dacă p este un nod la care s-a ajuns, atunci un nod fiu f al lui p se adaugă la lista care se determină (pentru un nou nivel) dacă valoarea conditie2 (care depinde de p şi f) este true. Inregistrarea părinte curentă p (iniţial poate fi una de start, determinată de condiţia din "start with") conţine valori pentru p şi f (folosite în conditie2), din care numai una este prioritară, şi anume aceea care este precedată de operatorul unar prior.

Pentru view-ul MultProduse precizat mai sus, se poate lua în considerare o înregistrare oarecare (cu o valoare dată pentru cod, sau pentru codp, sau pentru denumire) şi se determină alte înregistrări din acelaşi view prin condiţia cod=codp (cod sau codp este fixat pentru o înregistrare curentă şi se determină toate înregistrările legate de acesta prin condiţia dată). Pentru a preciza care valoare se ia din înregistrarea curentă (care are prioritate), una din coloane se va preceda de prior.
Pentru exemplificare, considerăm o parte dintr-o structură arborescentă, dată în figura următoare. Inregistrările din viewul MultProduse, corspunzătoare acestor noduri, sunt trecute în tabelul alăturat.

MultProduse
codcodpdenumire
10...
21...
32...
42...

Sa presupunem că se ia o înregistrare de start, care va fi pe nivelul 1. Inregistrări "fiu" sau "parinte" determinate în modul descris mai sus sunt pe nivelul 2 (nivelul următor). Dacă pentru aceste înregistrări "fiu" sau "parinte" determinate se mai continuă, se pot determina înregistrările "fiu" sau "parinte" pentru cele determinate anterior, deci înregistrările aflate pe nivelul 3. In expresiile din instrucţiunea select se poate folosi pseudocoloana level, care furnizează nivelul descris mai sus pentru o înregistrare curentă.

Exemple:

Gestiunea grafurilor orientate

Pentru a memora arcele unui graf orientat, cu vârfurile etichetate cu caractere, vom folosi următorul tabel:

create table graf(inceput char(1),final char(1));

Vom introduce unele arce în acest graf: 

insert into graf values('2','1');
insert into graf values('1','6');
insert into graf values('6','5');
insert into graf values('5','2');
insert into graf values('6','7');
insert into graf values('2','3');
insert into graf values('3','4');
insert into graf values('5','4');
insert into graf values('4','8');
insert into graf values('9','8');
insert into graf values('3','9');
insert into graf values('4','a');
insert into graf values('8','b');

Pentru a determina vârfurile la care se ajunge dintr-un vârf dat se poate folosi instrucţiunea:

select lpad(' ', level-1) || inceput || '->' || final
from graf
start with inceput = '3'
connect by inceput =prior final;

si se obtine:

3->4
  4->8
    8->b
  4->a
3->9
  9->8
    8->b

Cu aceeaşi instrucţiune, dar cu: "start with inceput = '1' se obţine o eroare:

ERROR: 
ORA-01436: CONNECT BY loop in user data

Pentru a elimina o astfel de eroare generată de apariţia ciclurilor, se poate folosi clauza "NOCYCLE":

select lpad(' ', level-1) || inceput || '->' || final
from graf
start with inceput = '1'
connect by nocycle inceput =prior final;

care va genera următorul răspuns:

 1->6
   6->5
     5->2
       2->1
       2->3
         3->4
           4->8
             8->b
           4->a
         3->9
           9->8
             8->b
     5->4
       4->8
         8->b
       4->a
   6->7

Pentru a determina toate nodurile din graf de la care se ajunge în nodul cu eticheta '4' avem instrucţiunea:

select level,lpad(' ', level-1) || inceput || '->' || final
from graf
start with final = '4'
connect by nocycle prior inceput = final;

cu rezultatul:

3->4
 2->3
  5->2
   6->5
    1->6
5->4
 6->5
  1->6
   2->1

Generare date de test

Cu ajutorul pachetului DBMS-RANDOM şi cu clauza CONNECT BY se pot genera date aleatoare de test, ca în exemplul următor:

select round(dbms_random.value(1,10000)) cod, dbms_random.string('U',20) valoare from dual connect by level<=1000;

Valorile astfel generate se pot include într-un tabel memorat.

Se pleacă de la singură înregistrare existentă în tabelul dual si se verifică dacă este indeplinită condiţia din Connect by. Condiţia folosită este level<=1000, deci plecând de la singura înregistrare aflată în dual, cu level=1, se determină tot această înregistrare, pentru level=2, apoi de la aceasta se determină următoarea (tot aceasta), cu level=3, etc.