January 6th, 2007 by depesz | Tags: | Comments Off on drzewa w sql’u – metoda “śledzenie rodzica”
Did it help? If yes - maybe you can help me?

jest to zdecydowanie najbardziej rozpowszechniona metoda przechowywania drzew w bazach.
zakłada ona (zgodnie z naszymy podstawowymi założeniami), że każdy element ma tylko 1 element nadrzędny (lub go nie ma – gdy jest to element główny). dzięki temu całość można zapisać w jednej tabeli
:

$ CREATE TABLE categories (
    id        BIGSERIAL,
    parent_id INT8 REFERENCES categories (id),
    codename  TEXT NOT NULL DEFAULT '',
    PRIMARY KEY (id)
);
CREATE UNIQUE INDEX ui_categories_picn ON categories (parent_id, codename);

nasze testowe drzewo w tej tabeli będzie wyglądało tak:

# SELECT * FROM categories;
 id | parent_id |  codename
----+-----------+------------
  1 |    [null] | sql
  2 |         1 | postgresql
  3 |         1 | oracle
  4 |         2 | linux
  5 |         3 | solaris
  6 |         3 | linux
  7 |         3 | windows
  8 |         6 | glibc1
  9 |         6 | glibc2
(9 rows)

jak widać – same podstawowe danych, jedna tabelka, mała nadmiarowość. wygląda ok. a jak to odpytać?

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

> SELECT * FROM categories where parent_id is null;

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

  • ID : id elementu
SELECT p.* FROM categories c JOIN categories p ON c.parent_id = p.id WHERE c.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 * FROM categories WHERE parent_id = [ID];

4. pobranie listy wszystkich elementów “nad" danym elementem (wylosowanym)
dane wejściowe:

  • ID : id elementu

tu pojawia się problem. można to rozwiązać selectem z dużą ilością joinów (tyle joinów ile poziomów kategorii jest powyżej naszego elementu), albo zastosować rozwiązanie algorytmiczne:

  1. pobierz dane dla aktualnego elementu: SELECT * FROM categories WHERE id = [ID];
  2. jeśli parent_id dla aktualnego elementu jest inny niż NULL wykonaj:
    1. SELECT * FROM categories WHERE id = [aktualny.parent_id]
    2. ustaw aktualny na właśnie pobrany

jest to rozwiązanie typu z wieloma zapytaniami, ale rozwiązanie z joinami ma wszystkie wady zapytań z “metody wielu tabel" (nota bene tam też można było zastosować podejście algorytmiczne, realizowane w aplikacji klienckiej)

5. pobranie listy wszystkich elementów “pod" danym elementem (wylosowanym)
dane wejściowe:

  • ID : id elementu

niestety – i tym razem zapisanie tego w postaci pojedynczego zapytania będzie problematyczne. w tym przypadku należy zastosować rozwiązanie rekurencyjne:

  1. pobierz listę wszystkich elementów bezpośrednio pod podanym elementem (vide punkt 3)
  2. dla każdego z elementów powtórz powyższy punkt
  3. powtarzaj tak długo aż dojdziesz do sytuacji gdy już nie ma elementów poniżej.

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

  • ID : id elementu
>SELECT count(*) from categories WHERE parent_id = [ID];

jeśli zwróci 0 – to dany element jest liściem.

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

  • ID : id elementu

niestety – jedyną słuszną metodą jest użycie algorytmu z punktu 4 i pobranie ostatniego elementu (takiego dla którego algorytm się kończy, bo parent_id jest NULLem.

podstawową zaletą tego rozwiązania jest to, że stała struktura tabel jest w stanie przechowywać dowolną ilość danych w drzewie – niezależnie od ilości elementów czy poziomów zagłębień.
wadami jest głównie konieczność korzystania z pewnych rozwiązań algorytmicznych zamiast użycia zapytań bazodanowych.

Sorry, comments for this post are disabled.