oj. od ostatniego tekstu nt. drzew już trochę czasu minęło. czas więc dokończyć tę serię 🙂

metodę tę wymyśliliśmy ze znajomymi z firmy w której kiedyś pracowałem.
jest mocno prawdopodobne, że ktoś jeszcze wpadł na taki pomysł, natomiast wiem, że gdy ją wymyślaliśmy – nie korzystaliśmy z niczyich prac.

na czym ona polega? w skrócie na tym, że baza zna wszystkie powiązania między wszystkimi elementami drzewa które są ze sobą powiązaną na zasadzie “ojciec, ojciec ojca, ojciec ojca ojca, …".

w tym celu używamy 2 tabel – pierwszej aby przechowywać informacje o elementach drzewa, a w drugiej – o powiązaniach między nimi.

przykładowo, oryginalne, testowe drzewo:

tabelki:

# create table nodes_5 (

id int4 primary key,

name text

);

# create table tree_5 (

id int4 primary key,

parent_id int4 not null references nodes_5(id),

child_id int4 not null references nodes_5(id),

depth int4

);

wstawianie elementów polega na tym, że wstawiamy rekord do nodes_5, po czym dodajemy do tree_5 rekord którego child_id będzie takie jak aktualnego elementu, depth będzie równy 1, a parent_id będzie wskazywał na element nadrzędny.

następnie w tree_5 należy wstawić rekord którego depth będzie 0, a parent_id i child_id będą ustawione na id nowo wstawionego elementu.

na koniec należy skopiować wszystkie elementy gdzie child_id było takie jak aktualnie parent_id, podbijając depth o 1 i zmieniając child_id na id wstawionego elementu.

uff. skomplikowane?

tak się tylko wydaje. tabelki po wstawieniu danych wyglądają tak – prześledźcie je to zobaczycie, że sprawa jest prosta.

tabelka nodes_5:

tabelka tree_5:
# select * from tree_5;

mam nadzieję, że teraz wygląda to bardziej oczywiście 🙂

ok. jak się pyta taką bazę?

1. pobranie listy elementów głównych (top-levelowych)

SELECT n.* from nodes_5 n left outer join tree_5 t on (n.id = t.child_id and t.depth = 1) where t.id is null

2. pobranie elementu bezpośrednio “nad" podanym elementem:

dane wejściowe:

• ID : id elementu

select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.depth = 1 and t.child_id = [ID];

jeśli zapytanie nic nie zwróci – znaczy to, że dany element był “top-levelowy".

3. pobranie listy elementów bezpośrednio “pod" podanym elementem

dane wejściowe:

• ID : id elementu

select n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.depth = 1 and t.parent_id = [ID];

4. pobranie listy wszystkich elementów “nad" danym elementem (wylosowanym)

dane wejściowe:

• ID : id elementu

select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID];

5. pobranie listy wszystkich elementów “pod" danym elementem (wylosowanym)

dane wejściowe:

• ID : id elementu

select n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.parent_id = [ID];

6. sprawdzenie czy dany element jest “liściem" (czy ma pod-elementy)

dane wejściowe:

• ID : id elementu

select count(*) from tree_5 where depth = 1 and parent_id = [ID]

jeśli zwróci 0 – to jest to liść. w innym przypadku zwróci ilość bezpośrednich “dzieci".

7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

• ID : id elementu

select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID] order by depth desc limit 1;

podstawową zaletą tego rozwiązania jest to, że praktycznie wszystkie operacje można uzyskać prostym “where" po jednej tabeli (tree_5) – join do nodes_5 służy tylko do tego by móc zwrócić coś poza samym id.

wady – nieoczywiste przenoszenie elementów. pewna nadmiarowość informacji.

co do przenoszenia elementów – kiedyś o tym pisałem, ale aby było wszystko w jednym miejscu:

zakładając, że mamy drzewo i w nim element o id X przenosimy tak aby był bezpośrednio pod Y, zapytania które to zrealizują wyglądają tak:

DELETE FROM tree_5 WHERE id IN (
                SELECT r2.id FROM tree_5 r1 JOIN tree_5 r2 ON r1.child_id = r2.child_id
                WHERE r1.parent_id = X AND r2.depth > r1.depth
                );
INSERT INTO tree_5 (parent_id, child_id, depth)
        SELECT r1.parent_id, r2.child_id, r1.depth + r2.depth + 1
        FROM
                tree_5 r1,
                tree_5 r2
        WHERE
                r1.child_id = Y AND
                r2.parent_id = X;

aha. oczywiście trzeba sprawdzić czy przenosiny elementu nie wygenerują pętli.