Wstęp
Pracując z bazami danych często ma się do czynienia z danymi hierarchicznymi. Oznacza to, że struktura rekordów przypomina drzewo. Każdy element może mieć maksymalnie jednego rodzica (jeśli nie ma rodzica to nazywany jest korzeniem drzewa), jak również dowolną ilość dzieci. Przodkami elementu nazywamy jego rodzica, rodzica jego rodzica, rodzica rodzica jego rodzica, itd. Natomiast potomkami nazywamy dzieci elementu, dzieci jego dzieci, itd.
Struktura bazy danych
Istnieje wiele metod przechowywania danych hierarchiczny w relacyjnych bazach danych. Najprostsza polega na dodaniu do rekordu pola wskazującego element który jest rodzicem (jest to zwykle klucz obcy odnoszący się do klucza głównego rodzica lub NULL jeśli mamy do czynienia z korzeniem). Jest to bardzo prosta struktura, którą bardzo łatwo zaimplementować.
Poniższym przykład pokazuje prostą hierarchiczną strukturę danych. Warto zwrócić uwagę na narzucone więzy integralności.
CREATE TABLE tree (
id INTEGER PRIMARY KEY,
parent INTEGER
REFERENCES tree(id)
ON DELETE CASCADE,
value VARCHAR(100)
);
INSERT INTO tree VALUES (1, NULL, 'a');
INSERT INTO tree VALUES (2, NULL, 'b');
INSERT INTO tree VALUES (11, 1, 'aa');
INSERT INTO tree VALUES (111, 11, 'aaa');
INSERT INTO tree VALUES (112, 11, 'aab');
INSERT INTO tree VALUES (12, 1, 'ab');
INSERT INTO tree VALUES (121, 12, 'aba');
INSERT INTO tree VALUES (122, 12, 'abb');
INSERT INTO tree VALUES (21, 2, 'ba');
INSERT INTO tree VALUES (211, 21, 'baa');
Wiele prostych operacji da się wykonać na tej strukturze za pomocą nie skąplikowanych zapytań SQL. Poniższe przykłady pokazują operacje dla rekordu, którego wartość wynosi ‘ab’. Warto zwrócić uwagę na usuwanie danych (za pomocą instrukcji DELETE) - dzięki użyciu konstrukcji ON DELETE CASCADE podczas tworzenia tabeli baza zapewnia nam automatyczne usuwanie wszystkich potomków usuwanego rekordu.
-- pobranie klucza rodzica SELECT parrent FROM tree WHERE value = 'ab'; -- pobranie rodzica SELECT * FROM tree WHERE id = ( SELECT parent FROM tree WHERE value = 'ab' ); -- pobranie dzieci SELECT * FROM tree WHERE parent = ( SELECT id FROM tree WHERE value = 'ab' ); -- zmiana rodzica elementu UPDATE tree SET parent = (SELECT id FROM tree WHERE value = 'b') WHERE value = 'ab'; -- usuniecie elementu i wszystkich jego potomków DELETE FROM tree WHERE value = 'ab';
Pobieranie przodków i potomków
Niestety w tej strukturze danych pobieranie przodków i potomków jest bardziej skomplikowane. Zwykle aby rozwiązać ten problem stosuje się wielokrotne wywoływanie zapytań SQL z poziomu aplikacji korzystającej z bazy danych. Niestety jest to rozwiązanie wolniejsze od zastosowania pojedynczego wywołania.
Jeśli korzystamy z bazy danych PostgreSQL to możemy rozwiązać ten problem poprzez wykorzystanie języka PL/pgSQL.
Pobieranie przodków (ancestors)
Poniższy funkcja zwraca ciąg kluczy rekordów na ścieszce od klucza podanego jako argument do korzenia danego drzewa.
CREATE OR REPLACE FUNCTION tree_ancestors(
start_id int
) RETURNS SETOF int AS $$
DECLARE
cid int := start_id;
BEGIN
WHILE cid IS NOT NULL LOOP
RETURN NEXT cid;
SELECT parent INTO cid FROM tree WHERE tree.id = cid;
END LOOP;
END;
$$ LANGUAGE plpgsql strict;
-- przykłady użycia:
-- pobranie samych numerów przodków
SELECT * FROM tree_ancestors(111);
SELECT t FROM tree_ancestors(111) AS t;
-- pobranie głebokości w drzewie (1 == korzen)
SELECT count(*) FROM tree_ancestors(111);
-- pobranie całych rekordów przodków
SELECT id, parent, value
FROM tree_ancestors(111) AS t JOIN tree ON t = tree.id;
Pobieranie potomków (descendants)
Poniższy funkcja zwraca ciąg kluczy rekordów potomków danego rekordu. Kolejność wyników jest typowa dla wyszukiwania wszerz.
Oznacza to, że najpierw są zwracane dzieci rekordu, dopiero potem dzieci tych dzieci, itd.
CREATE OR REPLACE FUNCTION tree_descendants(
start_id int
) RETURNS SETOF int AS $$
DECLARE
rec RECORD;
current INT[];
build INT[];
tmp INT;
BEGIN
build := ARRAY[0];
current := ARRAY[0, start_id];
WHILE current > ARRAY[0] LOOP
build := ARRAY[0];
FOR i IN 2..array_upper(current, 1) LOOP
tmp := current[i];
FOR rec IN SELECT * FROM tree WHERE parent = tmp LOOP
RETURN NEXT rec.id;
build := build || rec.id;
END LOOP;
END LOOP;
current := build;
END LOOP;
END;
$$ LANGUAGE plpgsql strict;
– przykłady użycia:
– pobranie numerów potomków
SELECT * FROM tree_descendants(1);
SELECT t FROM tree_descendants(1) AS t;
– pobranie ilości potomków
SELECT count(*) FROM tree_descendants(1);
– pobranie całych rekordów potomków
SELECT id, parent, value
FROM tree_descendants(1) AS t JOIN tree ON t = tree.id;
Podsumowanie
Kilka ogólnych uwag dotyczących korzystania z PL/pgSQL do obsługi tej struktury danych:
- wykorzystanie PL/pgSQL wiąże nas z bazą PostgreSQL
- bardzo trudno było by korzystać z tej metody za pomocą ORM
- jeśli mamy zamiar korzystać ze zliczania przodków a zwłaszcza potomków to zalecane by było napisać funkcje bardziej dostosowane do tego celu
