infoarena

Comentarii la postul http://infoarena.ro/blog/sql-query

Dacă nu se fac update-uri, cred că ar merge ceva de genul:
Pentru fiecare nod reţinem adâncimea faţă de rădăcină. Acum, un nod este părinte al unui nod dacă după ce urcăm nodul cu adâncimea mai mare până ajunge la aceeaşi adâncime cu nodul de adâncime mai mic şi dacă am ajuns în acelaşi nod (cu cel de sus). Petem face asta ţinând pentru fiecare nod al 2^k - lea tată. Ar fi necesare cam log(adâncime_arbore) query-uri.
Sunt tare curios cum s-ar face altfel.

Se poate stoca ierarhia folosind asa-zisul "nested model": fiecarui nod din structura ierarhica i se asociaza doua valori - stanga si dreapta. Numerotarea se face creascator, parcurgand arborele in preordine; la parcurgerea descendenta (dinspre parinte spre fii) se completeaza valoarea "stanga", iar la cea ascendenta (intoarcerea dinspre fii spre parinte) se compleateaza valoarea "dreapta". In acest mod fiecare valoare "stanga" are proprietatea ca se afla in intervalul definit de valorile "stanga" si "dreapta" ale oricaruia din parintii lui - cel direct sau cei indirecti. Folosind proprietatea asta se poate determina foarte usor daca un anumit nod din ierarhie este subordonat direct/indirect altui nod. Aproape la fel de usor se poate obtine o lista a tuturor nodurilor subordonate altui nod. Partea mai grea este sa adaugi noduri intr-o ierarhie... :)

@stocarul
Daca nu sunt update-uri poti face o parcurgere df in care tii intr-un hash toate nodurile pe care le ai in stiva momentan si cand ajungi intr-un nod x rezolvi toate query-urile care il implica ca fiu  :) Dar banuiesc ca exista update-uri.

@luci
Dap, a ta e mai faina. Valoarea 'dreapta' a unui nod va fi cel mai mare numar asociat in subarborele sau?  :) La asta te refereai?

@klamathix
Da, cel mai mare + 1, daca numerotam consecutiv.

Facem pargurgerea euler a ierarhiei initiale, si introducem in baza de date pe rand in ordinea din parcurgerea euler. Vom tine id-ul minim si maxim al nodurilor din subarbore pt fiecare nod (sunt consecutive nodurile din subarbore). Pt un query se verifica daca t1[y] < t1[ x ] < t2[y].

Ce zice Cosmin Tutunaru e corect dar nu e practic. Nu prea e ok din punct de vedere SQL sa ti multe referinte catre acelasi tabel pe aceeasi obiect sql (linie din tabel). Cel putin asa stiu....

Cam aceeasi complexitate se obtine si cu LCA pentru constructie, apoi O(1) pe query. Verificam daca LCA dintre X si Y este nodul Y.
LE: Si cum zice cosmin se poate face LCA. Eu ma refeream la RMQ

Este vorba de o baza de date, trebuie sa si mearga implementata. Intr-o baza de date nu poti tine un numar variabil de pointeri.

Nu stiu daca asta e solutia sau nu, dar mi se pare o idee destul de buna.
Este oarecum asemanatoare cu una din ideile prezentate anterior.

Fiecarei persoana din baza de date i se atribuie o valoare in plus care va ajuta la identificarea lantului ierarhic( not. lantIerarhicValue) .
Pe langa aceasta valoare, pentru a usura operatiunea de inserare este necesar sa retinem pentru fiecare Angajat cine este
 - superiorul
 - ultimul angajat dinaintea lui care se afla in aceeasi echipa cu el. (not. previousEmployee )
(ex. A este seful lui B, C si D - pentru C valoarea este B, pentru D valoarea este C)

lantIerarhicValue se determina asa.

Pentru radacina (let's call it CEO), avem o valoare destul de mare X
fiecare subordonat direct primeste o valoare mai mica decat X
ex. Daca CEO are subordonati pe A,B,C,D  acestora le dam valori

• A.lantIerarhicValue= 1 * 1/maximumNumberOfDirectSubordinates * X;
• B.lantIerarhicValue= 2 * 1/maximumNumberOfDirectSubordinates * X;
• C.lantIerarhicValue= 3 * 1/maximumNumberOfDirectSubordinates * X;
• D.lantIerarhicValue= 4 * 1/maximumNumberOfDirectSubordinates * x;

Acum pentru a raspunde la interogari de genul:
este A subordonat indirect al lui B putem verifica daca A.lantIerarhicValue  este intre B.lantIerarhicValue si .B.previousEmployee.lantIerarhicValue.

Una din problemele care ar putea sa para ar fi sa nu cunoasteam valoarea lui maximumNumberOfDirectSubordinates
Dar putem veni cu o solutie pentru aceasta problema:
Setam maximumNumberOfDirectSubordinates cu o valoare destul de mare. Daca la un anumit moment un sef are mai multi subordonati directi decat aceasta valoare(putem sa o dublam), crestem valoarea si actualizam intreg arborele.

Sunt de acord cu parcurgerea euler.E eficient si usor de implementat,excelent pentru concursuri.