relacyjna baza, hierarchiczna struktura, wydajne zapytanie
Sergiusz Brzeziński
Ciekawy jestem Waszych propozycji na rozwiązanie pewnych problemów
związanych z wydajnością przy zadawaniu pytania do bazy danych.
Jest relacyjna baza danych. Zaimplementowano w niej hierarchiczną
strukturę drzewiastą:
Jest korzeń, do korzenia należą grupy, do grup podgrupy itd. Do grup
mogą należeć też towary. Grupa może należeć tylko do jednej nadgrupy
(lub do korzenia) i posiadać dowolnie wiele podgrup i(lub) towarów.
Towar może należeć równocześnie do różnych grup.
Relacja implementująca drzewo nazywa się "hierarchia" i ma następujące
atrybuty:
hierarchia
----------
hi_id_grupy
hi_id_potomka
hi_id_grupy to oczwiście identyfikator nadgrupy a hi_id_potomka to
identyfikator grupy lub towaru należącego do danej nadgrupy
Oczywiście istnieje też tabela grup i tabela towarów. Każdy towar jak i
każda grupa ma swój unikalny identyfikator, do którego odwołujemy się w
tabeli hierarchia, a identfikatory grup i towarów nie powtarzają się
tzn. nie ma pary: grupa, towar z tym samym identyfikatorem.
I wreszcie pytania:
1.
Potrzebuję zadać pytanie(a) SQL, które udzieli odpowiedzi czy dana grupa
lub towar należy bezpośrednio lub pośrednio do jakiejś innej grupy.
Najprostrze (i jedyne?) rozwiązanie to wyszukanie w relacji "hierarchia"
bezpośredniej(ich) nadgrup(y) a następnie rekurencyjne dalsze pytania aż
do momentu trafienia na szukaną nadgrupę lub korzenia. Ale taka
strategia nie jest zbyt efektywna. W przpadku gdy jakiś towar należy
równocześnie do wielu grup oraz znajduje się dość głęboko w hierarchii
może być zadana całkiem spora liczba pytań SQL zanim otrzymamy
odpowiedź, że towar NIE NALEŻY do grupy, o którą pytamy.
Jeśli towar należy np. do trzech grup, z których każda znajduje się na
piątym poziomie zaglębienia, a towar nie należy do grupy o którą pytamy,
to trzeba będzie zadać aż 15 pytań SQL aby otrzymać odpwiedź przeczącą.
A jeśli zbierze się więcej takich pytań to zrobi się niezła masakra.
Jakie macie propozycje aby zmniejszyć liczbę zapytań i zoptymalizować
proces wyszukiwania przynależności do grupy? W pierwszej kolejności
interesują mnie jakieś sprytne pytania, które operować będą tylko na
istniejących tabelach. W drugiej kolejnści wprowadzenie np. dodatkowych
tabel z nadmiarowymi informacjami.
2.
Zagadnienie trochę podobne do poprzedniego ale powodujące jeszcze
większe problemy z ilością zapytań: "podaj mi identyfikatory wszystkich
potomków należących do danej nadgrupy". I podobnie jak poprzednio
najprostrza jet rekurencja, która może nas jednak sporo kosztować. Jak
proponujecie zmniejszyć liczbę zapytań operując tylko na istniejących
tabelach, a jak wprowadzając jakieś nadmiarowe tabele pomocnicze?
3.
W jaki inny sposób proponujecie przechowywanie struktury drzewiastej w
relacyjnej bazie danych?
z góry dzięki za sugestie i pomysły
pozdrawiam
Sergiusz Brzeziński
Sergiusz Brzeziński
Jak w możliwie najmniejszej liczbie pytań (być może wkorzystując jakąś
nadmiarową tabelę pomocniczą) znaleźć w hierarchii ścieżkę(i) do
korzenia dla towaru lub grupy o danym identyfikatorze.
Jacek Marciniak
> Potrzebuję zadać pytanie(a) SQL, które udzieli odpowiedzi czy dana grupa
> lub towar należy bezpośrednio lub pośrednio do jakiejś innej grupy.
> Najprostrze (i jedyne?) rozwiązanie to wyszukanie w relacji "hierarchia"
> bezpośredniej(ich) nadgrup(y) a następnie rekurencyjne dalsze pytania aż
> do momentu trafienia na szukaną nadgrupę lub korzenia. Ale taka
> strategia nie jest zbyt efektywna. W przpadku gdy jakiś towar należy
Ale jaki serwer?
Na przykład Oracle ma w składni selecta
SELECT....CONNECT BY ..[PRIOR] ....
To ułatwia "chodzenie po takiej strukturze....w innych...trzeba sobie radzić
inaczej.
Można też wybrać (w zależności od potrzeb) inny sposób implementacji takiego
drzewa (z "niewielką" redundancją, ale wydajniejszy).
Jacek
Marcin Jaskólski
> Witam,
>
> Ciekawy jestem Waszych propozycji na rozwiązanie pewnych problemów
> związanych z wydajnością przy zadawaniu pytania do bazy danych.
>
> Jest relacyjna baza danych. Zaimplementowano w niej hierarchiczną
> strukturę drzewiastą:
>
> Jest korzeń, do korzenia należą grupy, do grup podgrupy itd. Do grup
> mogą należeć też towary. Grupa może należeć tylko do jednej nadgrupy
> (lub do korzenia) i posiadać dowolnie wiele podgrup i(lub) towarów.
> Towar może należeć równocześnie do różnych grup.
> 3.
> W jaki inny sposób proponujecie przechowywanie struktury drzewiastej w
> relacyjnej bazie danych?
swego czasu uzywałem brutalnego rozwiązania ze stringami, coś w ten deseń:
Grupa
ID Nazwa
A Pojazdy
A00 Samochody sportowe
A0000
A01 Motocykle
A0100 Motocykle Kawasaki
B Zabawki
.
.
Po prostu grupa x jest podgrupa grupy y <==> identyfikator grupy y jest
prefiksem identyfikatora grupy x.
Ograniczenie - trzeba się zdecydować że podgrupy są oznaczane przez
powiedzmy 2 znaki, co ogranicza liczbę podgrup.
Wyszukanie podgrup powiedzmy grupy Motocykle jest trywialne - select id
from grupy where id like 'A01%' czy jakoś tak :-) Trzeba się tylko
upewnić, czy przy takich zapytaniach zostaną odpowiednio użyte indeksy.
pozdrawiam,
Marcin Jaskólski
Paweł Matejski
[ciach]
Widać, że FAQ nie czytałeś....
P.S. Łatwo znaleźć samemu, ale jakby Ci lenistwo dopadło... http://www.dbf.pl/faq/
--
P.M.