drzewa w sql’u – metoda wielu tabel

tak naprawdę to nazwa "metoda wielu tabel" nie oddaje w pełni tego o co chodzi, natomiast jest pewnym przybliżeniem.
zgodnie z tą metodą należy stworzyć dla każdego poziomu zagnieżdżenia tabelę.
w oparciu o nasze dane testowe należy stworzyć system tabel:

CREATE TABLE categories_1 (
    id       BIGSERIAL PRIMARY KEY,
    codename TEXT NOT NULL DEFAULT ''
);
CREATE UNIQUE INDEX ui_categories_1_cn ON categories_1 (codename);

CREATE TABLE categories_2 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_2 ADD FOREIGN KEY (parent_id) REFERENCES categories_1 (id);
CREATE UNIQUE INDEX ui_categories_2_picn ON categories_2 (parent_id, codename);

CREATE TABLE categories_3 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_3 ADD FOREIGN KEY (parent_id) REFERENCES categories_2 (id);
CREATE UNIQUE INDEX ui_categories_3_picn ON categories_3 (parent_id, codename);

CREATE TABLE categories_4 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_4 ADD FOREIGN KEY (parent_id) REFERENCES categories_3 (id);
CREATE UNIQUE INDEX ui_categories_4_picn ON categories_4 (parent_id, codename);

i w nim dane:

# select * from categories_1;
 id | codename
----+----------
  1 | sql
(1 row)

# select * from categories_2;
 id | parent_id |  codename
----+-----------+------------
  1 |         1 | oracle
  2 |         1 | postgresql
(2 rows)

# select * from categories_3;
 id | parent_id | codename
----+-----------+----------
  1 |         2 | linux
  2 |         1 | linux
  3 |         1 | solaris
  4 |         1 | windows
(4 rows)

# select * from categories_4;
 id | parent_id | codename
----+-----------+----------
  1 |         2 | glibc1
  2 |         2 | glibc2
(2 rows)

jak widać pojawia się pewien problem – nieobecny w innych systemach tabel – aby prawidłowo zidentyfikować element drzewa nie wystarczy nam jego numer, ale musimy też znać poziom zagłębienia.
oczywiście możliwe jest wymuszenie nadawania numerów kolejnych tak aby nie powtarzały się w różnych tabelach, ale wtedy znalezienie który element jest w której tabeli będzie nietrywialne.

teraz pora na zadania testowe dla tego układu tabel:
1. pobranie listy elementów głównych (top-levelowych)

 > SELECT * FROM categories_1;

proste i miłe.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:
brak danych
w innym przypadku:

 > SELECT p.* FROM categories_[X] c join categories_[X-1] p ON c.parent_id = p.id WHERE c.id = [ID]

pojawia się problem. zapytania są zmienne. nie jest to bardzo duży problem, ale np. utrudnia wykorzystywanie rzeczy typu "prepared statements".

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.
> SELECT c.* FROM categories_[X] p join categories_[X+1] c ON c.parent_id = p.id WHERE p.id = [ID]

znowu pojawia sie problem z zapytaniami o zmiennej treści (nie parametrach – treści – nazwach tabel!). dodatkowo – musimy gdzieś przechowywać informację o maksymalnym zagnieżdżeniu i sprawdzać ją przed wykonaniem zapytania – aby się nie okazało, że odwołujemy się do nieistniejącej tabeli.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:
brak danych
jeśli X == 2 to:

 > SELECT c1.* FROM categories_2 c2 join categories_1 c1 ON c2.parent_id = c1.id WHERE c2.id = [ID]

jeśli X == 3 to:

 > SELECT c1.*, c2.*
FROM categories_3 c3 join categories_2 c2 on c3.parent_id = c2.id join categories_1 c1 ON c2.parent_id = c1.id
WHERE c3.id = [ID]

itd.

jak widać tu problem się multiplikuje. nie tylko zmieniają nam się nazwy tabel, ale wręcz cała konstrukcja zapytania zaczyna przypominać harmonijkę – z każdym ruchem (wgłąb struktury) wyciąga się.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.
  • MaxX : maksymalny poziom zagłębienia w systemie
SELECT c[X+1].* FROM categories_[X+1] c[X+1] WHERE c[X+1].parent_id = [ID]
UNION
SELECT c[X+2].*
FROM categories_[X+1] c[X+1] join categories_[X+2] c[X+2] ON c[X+1].id = c[X+2].parent_id
WHERE c[X+1].parent_id = [ID]
UNION
SELECT c[X+3].*
FROM categories_[X+1] c[X+1]
join categories_[X+2] c[X+2] ON c[X+1].id = c[X+2].parent_id
join categories_[X+3] c[X+3] ON c[X+2].id = c[X+3].parent_id
WHERE c[X+1].parent_id = [ID]
...

łaaaał. robi się coraz gorzej. napisanie tego dla np. 16 poziomów zagnieżdżenia przerasta moje chęci.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.
SELECT count(*) from categories_[X+1] WHERE parent_id = [ID]

zasadniczo proste, ale trzeba pamiętać o wcześniejszym sprawdzeniu czy przypadkiem X+1 nie jest większe od maksymalnie obsługiwanego limitu – aby uniknąć błędów w bazie.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:

 > SELECT c1.* FROM categories_1 c1 WHERE id = [ID]

jeśli X == 2 to:

 > SELECT c1.* FROM categories_2 c2 join categories_1 c1 ON c2.parent_id = c1.id WHERE c2.id = [ID]

jeśli X == 3 to:

 > SELECT c1.*
FROM categories_3 c3 join categories_2 c2 on c3.parent_id = c2.id join categories_1 c1 ON c2.parent_id = c1.id
WHERE c3.id = [ID]

itd.

eh. chyba widzicie do czego to zmierza.

jak widać – zapisywanie tak drzew ma swoje problemy. i raczej niewiele rzeczy można w tym zrobić ładnie szybko i porządnie.
zasadniczo – nie opisywałbym tej metody gdyby nie fakt iż z nieznanych powodów jest ona bardzo często sugerowana przez ludzi których odpytuję w ramach rozmowy kwalifikacyjnej.  no – a skoro się pojawia, to trzeba ją omówić. choćby pobieżnie.

4 thoughts on “drzewa w sql’u – metoda wielu tabel”

  1. Drzewa w SQL się implementuje metodą lewa-prawa krawędź. Potrafi to samo, co rekursja i wiele tabel, a poza tym pozwala wybrać poddrzewo jednym SELECTem.

  2. czyli używasz metody “nested sets” wymyślonej przez joe celko.
    znam. nie lubię, ale znam.
    jak może zauważyleś – ten artykuł to cześć serii. drugi z serii dokładniej.
    w następnych postach będą omówione inne metody.
    nested sets też, aczkolwiek uważam te metodę za totalną stratę czasu.

    a następne posty pojawią się jak będę miał trochę więcej wolnego czasu.

  3. z niecierpliwoscia czekam na kolejne czesci (szczegolnie na omowienie metody 5). Probuje stworzyc uniwersalna klase dla moich projektow opierajac sie wlasnie na niej i mysql 5.x

    pozdrawiam

Comments are closed.