[MYSQL] Zapytanie w drzewie zalezności Opcje

[ShadowOfMonster]

Powiedzmy że mamy oto taką przykładową strukturę zależności użytkowników:
(strzałki interpretują zależność master/slave User2 ma mastera jako User1 ale ma też slave'a User3 ale np. User8 ma jako master'ów User4, User3 etc. (kolejność nadrzędności jest ważna) sama długość gałęzi drzewa jest teoretycznie nieograniczona)
Dany User może mieć mnóstwo slav'ów ale tylko jednego master'a.

User1 -> User2 -> User3 -> User4 ->User5
User1 -> User6 -> User7
User6 -> User11
User4-> User8->User9->User10
(etc.)

Oczywiście takich drzewek mamy sporo
W bazie jest to prosto reprezentowane poprzez kolumny id, name, master

Teraz problem składa sie na funkcję która powie mi np. czy User999 ma jako master'a User2 lub czy User10 ma jako mastera User4

Oczywiście logicznie jest to do zrobienia. Wykonywać zapytania w SQL tak długo aż dojedziemy do kolesia który nie ma mastera i stwierdzimy że jest false lub go w końcu znajdziemy i będzie true no ale tak to trochę można bazę zajechać.
Można tez po prostu wczytać wszystkie rekordy do zmiennej tablicowej (lub przy pewnych założeniach jakąś większą część) i w php bawić sie w wyszukiwanie (odtwarzanie drzewa) ale przy bardzo dużej bazie (tablica rzędu 50MB) gdzie chcemy znaleźć kilka odpowiedzi da nam długi czas wykonywania skryptu.

Więc moje pytanie sprowadza się do tego czy takie wyszukiwanie mastera można załatwić odpowiednim zapytaniem w SQL'u poprze powiązanie kolumny master?

Ten post edytował ShadowOfMonster 8.07.2009, 04:02:55

[wookieb]

Według mnie przydałoby się dodanie jeszcze jednego pola np :* path_id a do tego path_order. Path id trzyma numer ścieżki a path_order pozwoli ci na szybkie znalezienie który user na jakiej jest pozycji. Można się wtedy pozbyć kolumny master.
Path_id: 1,1,1,1,1
Path_order: 1,2,3,4,5
Users: u1, u8, u6, u10, u2

[ShadowOfMonster]

Według mnie przydałoby się dodanie jeszcze jednego pola np :* path_id a do tego path_order. Path id trzyma numer ścieżki a path_order pozwoli ci na szybkie znalezienie który user na jakiej jest pozycji. Można się wtedy pozbyć kolumny master.
Path_id: 1,1,1,1,1
Path_order: 1,2,3,4,5
Users: u1, u8, u6, u10, u2

Coś w rodzaju współrzędnych gałęzi - tez to znam. Pytam czy po prostu nie ma takiego zapytania w SQL które dzięki powiązaniu rekordu master po prostu samo nie szłoby to końca gałęzi użytkowników gdzie master byłby null lub zero a odpowiedz prosta true lub false w przypadku odnalezienia lub nie. Miało by to pewne zalety optymalizacji bazy danych a jedynie zwiększenie potrzeby czasu na odnalezienie naszego mastera lub nie. Biorąc pod uwagę że mamy bazę danych na poziomie 500MB i w tabeli redukcja dwóch kolumn (path_id i Path_order do jednej master). Proces sql po prostu mógłby skakać z wiersza do wiersza dzięki powiązaniu kolumny master z id. Miałoby by to walory optymalizacyjne wielkości bazy (pamięci też) kosztem czasu procesu który byłby szybszy niż czas procesu w przypadku zabawy całą tabelą w php ale na pewno dłuższy od twojego rozwiązania. Nie mam czasu na bawienie się w testowanie takich rzeczy a nie przychodzi mi do głowy aby takie zapytanie istniało dlatego się pytam.

Dla pojedynczej strony nie ma to wielkiego znaczenia. Ale jeśli mówimy o bazach danych gdzie tabele sięgają milionów wierszy każdy element ma pewne znaczenie w działaniu i optymalizacji. Skakanie z wiersza do wiersza wydaje się nie optymalizacyjne jeśli np. mamy do czynienia z gałęzią sięgającą tysiąc w głąb. Ale w moim przypadku mówimy o dwóch rekordach a wczytany zostanie cały pojedyńczy wiersz danego użytkownika (lub master'a) jeśli odpowiedź będzie true.

Tak mi wpadł problem do głowy. (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

Pozdrawiam.