=$

|

metodę zagnieżdżonych zbiorów poznałem po raz pierwszy po przeczytaniu którejś z książek joe celko. chyba tej: Advanced SQL Programming, ale na 100% nie jestem pewien.
zagnieżdżone zbiory (nested sets) polegają w duzym skrócie na tym, że każdy element drzewa jest opisany nie jednym id, ale parą liczb. są to w miarę dowolne liczby, z założeniem jedynie takim, że "lewa" jest mniejsza od "prawej", oraz, że obie liczby (lewa i prawa) wszystkich elementów drzewa poniżej danego muszą się mieścić w zakresie (lewa, prawa) swoich rodziców.
skomplikowane? też nie zrozumiałem.
przypomnijmy sobie nasze oryginalne, testowe drzewo:

teraz.
tworzymy sobie taką tabelkę:

# create table nested_sets ( id_left int4 primary key, id_right int4 not null check (id_left < id_right), name text);

jako primary key wybrałem sobie id_left, ale mogłem wybrać też right. w szczególności – wartości w polach id_left i id_right muszą być unikatowe. czyli jeśli w którymś elemencie w polu id_left jest wartość 5, to nie może się ona powtórzyć ani w id_left ani w id_right.
ok. jak nadać numerki?
proste. zaczynamy od elementu głównego, i przyznajemy mu id_left = 1. potem idziemy do jego pierwszego dziecka. jego id_left dajemy kolejny numer. jeśli ten element ma podelementy, to powtarzamy zejście w dół z przyznawaniem kolejnych id_left. jeśli dany element nie ma "dzieci", to nadajemy mu id_right równy kolejnej liczbie. i wracamy piętro wyżej.
mało jasne? pewnie nie umiem za dobrze opisać. więc lecimy w krokach:

1. elementowi sql, przypisujemy id_left = 1, i schodzimy w dół do "postgresql".
2. elementowi postgresql, przypisujemy id_left = 2, i ponieważ ma jakieś dzieci, schodzimy w dół – do "linux"
3. elementowi linux przypisujemy id_left = 3
4. ponieważ linux nie ma "dzieci", przypisujemy mu id_right = 4 i wracamy wyżej
5. ponieważ postgresql nie ma "dzieci", przypisujemy mu kolejne id_right. czyli id_right = 5. i wracamy wyżej.
6. jesteśmy z powrotem w sql. wchodzimy w kolejne dziecko – oracle
7. elementowi oracle przypisujemy id_left = 6.
8. itd. aż dojdziemy do ustawienia dla elementu sql, id_right = 18

zwracam uwagę na to, że w tej numeracji widać od razu, że ilość elementów jest równo połową największego id_right. co jest poniekąd logiczne.
cała tabelka wygląda tak:

id_left	id_right	name
1	18	sql
2	5	postgresql
3	4	linux
6	17	oracle
7	8	solaris
9	14	linux
10	11	glibc1
12	13	glibc2
15	16	windows

ok. jak się pyta taką bazę?
tu uwaga – ten model znam najsłabiej. głównie dlatego, że go osobiście nie lubię. jeśli znajdziecie błąd w tym co poniżej napiszę – proszę o informację. nie jestem nieomylny, a jak już mówiłem – tego modelu drzew nie lubię i nie bawiłem się nim w ogóle.
1. pobranie listy elementów głównych (top-levelowych)

SELECT

    ns1.*

FROM

    nested_sets ns1

    LEFT OUTER JOIN nested_sets ns2 ON (ns1.id_left > ns2.id_left AND ns1.id_right < ns2.id_right)

WHERE

    ns2.id_left IS NULL

;

zwrócić należy uwagę na fakt iż jeśli nasze drzewo ma tylko i wyłącznie 1 element top-levelowy to zapytanie można uprościć do:

# SELECT * FROM nested_sets WHERE id_left = 1;

jeśli stosujemy numerację od 1, lub

# SELECT * FROM nested_sets ORDER BY id_left ASC LIMIT 1;

jeśli numeracja startuje od nieznanej liczby.

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

dane wejściowe:

• ID : id_left elementu

SELECT
    ns.*
FROM
    nested_sets ns
WHERE
    [ID] BETWEEN ns.id_left + 1 AND ns.id_right
ORDER BY ns.id_left DESC LIMIT 1

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
    nsc.*
FROM
    nested_sets nsp
    JOIN nested_sets nsc ON (nsc.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right)
WHERE
    nsp.id_left = [ID]
    AND NOT EXISTS (
        SELECT *
        FROM nested_sets ns
        WHERE
        ( ns.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right )
        AND
        ( nsc.id_left BETWEEN ns.id_left + 1 AND ns.id_right )
    )

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

dane wejściowe:

• ID : id elementu

SELECT
    ns.*
FROM
    nested_sets ns
WHERE
    [ID] BETWEEN ns.id_left + 1 AND ns.id_right

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

dane wejściowe:

• ID : id elementu

SELECT

    nsc.*

FROM

    nested_sets nsp

    JOIN nested_sets nsc ON nsc.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right

WHERE

    nsp.id_left = 6

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

dane wejściowe:

• ID : id elementu

>SELECT true from nested_sets WHERE id_left = [ID] AND id_right = [ID] + 1;

jeśli zwróci true – to jest liść. jeśli nic nie zwróci – to nie jest liściem.

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

• ID : id elementu

SELECT

    ns.*

FROM

    nested_sets ns

WHERE

    [ID] BETWEEN ns.id_left + 1 AND ns.id_right

ORDER BY

    ns.id_left ASC LIMIT 1

podstawową zaletą tego rozwiązania jest to, że bardzo szybko zwraca listę wszystkiego "nad", "pod" czy listę liści.

wadami jest mała intuicyjność, skomplikowane przenoszenie elementów (gdybym miał to zaimplementować, to najprawdopodobniej po prostu po każdym przeniesieniu od nowa bym numerował id_left/id_right.

dodatkowo – część zapytań wymaga albo "order by xxx limit 1", albo subselectów co raczej nie wróży dobrze wydajności. a order by limit 1 nie zawsze można użyć (np. użycie tego w joinach jest już mocno problematyczne).