Problematyka powiązań Opcje

[spenalzo]

Mam taki schemat:


:arrow: http://spenalzo.republika.pl/schemat.gif
(wybaczcie za koślawy rysunek)

Jest to schemat powiązań pomiędzy użytkownikami:
R - root (ja)
R.1-R.6 - moi znajomi
A-H - znajomi R.1-R.6 (tutaj dla uproszczenia schematu po jednym)
A.1-H.6 - znajomi A-H

Oczywiście mogą potem być dalej różne inne powiązania (np. A.1.1.1-A.1.2.6 itd itp) - ale ja widze tylko od poziomu R do ostatniego na schemacie czyli A.1-H.6
Powiazania pomiędzy użytkownikami są zależne w taki sposób, że jeżeli dodam nowego znajomego to wszyscy (do 3 poziomu zaglębienia) widzą jego, ci na 2 poziomie widzą jego i jego znajomych na I poziomie itd. Natomiast ja widzę jego znajomych do 3 poziomu, czyli schemat się powtarza. Z kolei użytkownicy na 6 poziomie widzą moich znajomych na 3 poziomie.

W jaki sposób rozpracować strukture tych powiazań i w jakim stopniu przerzucić "ciężar" tych powiązań na php a w jakim stopniu na MySQLa?

[bumelang]

Z tego, co wiem, to to się modeluje na dwa sposoby: pierszy, oczywisty - zarzucanie bazy milionem zapytań dotyczących kolejnych rodziców i dzieci danego węzła, co ma na sens gdy często się dodaje a rzadko wybiera dane i chyba średnio ma sens przy Twoim schemacie.

Drugi jest znacznie bardziej wysublimowany i nadaje się do informacji często wybieranej, ale rzadko dodawanej z uwagi na duży koszt dodawania czy usuwania rekordu. Wygląda to tak, że w SQLu przechowuje nadmiarową informację dotyczącą struktury drzewa (tj. poza informacją o ojcu), którą trzeba odbudować za każdym razem gdy ta się zmienia.

Korzyść z tego za to taka, że wszystkie operacje wybierania całej gałęzi etc. wykonuje się jednym zapytaniem. Jest to dość skomplikowane i średnio pamiętam jak to się dokłanie robi. Nie wiem też na ile na MySQLu da się to sensownie zaimplementować, ale że ciągle mnie ta baza zaskakuje, to być może się da.

Poszukaj sobie w googlach po prostu "SQL trees" czy coś w tym stylu - to powinno Ci to przybliżyć problem. Pozdrowienia.

[cagrET]

http://searchdatabase.techtarget.com/tip/1...i537290,00.html

http://searchdatabase.techtarget.com/tip/1...i801943,00.html

[spenalzo]

Hmmm poszukałem sporo różnym przykładów takich drzewek, jak np. to:

Kod

            Albert (1,12)

            /        

           /          

    Bert (2,3)     Chuck (4,11)

                   /    |    

                  /     |      

                 /      |      

                /       |        

        Donna (5,6)  Eddie (7,8)  Fred (9,10)

Kod

emp         lft  rgt

======================

'Albert'      1   12

'Bert'        2    3

'Chuck'       4   11

'Donna'       5    6

'Eddie'       7    8

'Fred'        9   10

ale nie rozumiem w jaki sposób przypisuje się te numery do lft i rgt, co one oznaczają i skąd się one biorą?

[Bakus]

Nie wiem, czy to będziedobre rozwiązanie, ale czy nie możasz zapisywać w tabeli tylko "ojców"

Przykład tabelki:

ID Nick Rodzic
1 spenalzo 0 - nie posiadasz "rodzica" - jesteś root
...
5 bakus 1 - poleca mnie nr 1 - ty
...
315 kolega_bakusa 5 - dorzucam swojego kolege

Rozumiesz o czym rozmawiam
Nie jestem pewien, czy takie coś się sprawdzi w zadanui, jakie wykonujesz, ale obsług takiego czegoś jest prosta... szukasz w bazie ludzi R.1-R.8 -> wyciągasz te rekordy w których Rodzic to 1 - czyli ty...

P.S. Najprostrze rozwiązania są w większości przypadków jedynie słusznnymi...

[menic]

@Bakus bumelang juz o tym wspomnial i wyjasnij + i - :wink:

[bumelang]

spenalzo:
To jest przechodzenie przez drzewo w tzw. porządku wzdłużnym, tylko że dopasowanym do drzew niebinarnych, czyli odwiedzasz korzeń, potem jego potomoków poczynajac od lewego i konczac na prawym (rekurencyjnie wywolujesz te sama metode z warunkiem stopu na lisciach: wezel != null). Wewnątrz procedury wchodzac w skrajne lewe poddrzewo nadajesz wezel.lft = i+1 natomiast wchodzac juz w skrajne prawe wezel.rgt = i+1, gdzie i jest zmienną globalną.

Sęk w tym, że w bazach lepszych niż MySQL, typu choćby PostgreSQL, robi się to procedurami w bazie, a ciężko mi powiedzieć, jak MySQL sobie z takowymi radzi i czy w ogóle, bo go nie widziałem na oczy od wersji 3.x.

Wydaje mi się, że Bakus ma trochę racji o tyle, że w tym konkretnym przypadku możnaby ograniczyć całą tę zabawę do przechowywania wskaźników do ojca, "dziadka" i "pradziadka" , a potem oczywiście
[sql:1:f768448c86]SELECT * FROM users WHERE father=$father;[/sql:1:f768448c86], i dwa następne zapytania dla pradziadek = pradziadek i dziadek = dziadek.

Wątpie jednak, Bakusie, czy ma sens całkowicie znormalizowana struktura, tj. tylko z ojcem, bo liczba zapytań do bazy będzie co najmniej 2 razy taka jak w powyższym rozwiązaniu, a te jak wiadomo zawsze są bardzo kosztowne.

[bumelang]

Jak zawsze przeczytałem swojego posta dopiero po wysłaniu i stwierdziłem, że strasznie zaciemniłem tę procedurą do przeglądania wzdłużnego. Więc teraz zapisuję w pseudokodzie, żebyś się mógł przejść po drzewku i zobaczyć jak to działa :

Kod

procedure ogladacz(wezel)

begin

  if(wezel != NULL)

  begin

    wezel.lft = i+1;

    weź pierwsze dziecko od lewej;

    while(sa jeszcze dzieci)

    begin

       ogladacz(dziecko);

       weź następne dziecko;

    end

    wezel.rgt = i+1;

  end

end

Pozdrowienia

[Bakus]

Ups... sorki faktycznie... szybko czytając, wątek nie zgłębiłem sensu...

Usuwał nie będe, bo mnie moja wypowiedź wydaje czytelniejsza... Nie ubliżając nikomu!

Jeszcze raz sorki...

[mateuszkrzeszowi...]

http://www.depesz.pl/various-sqltrees.php

[a1internet]

W jaki sposób rozpracować strukture tych powiazań i w jakim stopniu przerzucić "ciężar"  tych powiązań na php a w jakim stopniu na MySQLa?

Śliczny schemat
Najpierw przeczytaj rekomendowaną już wyżej stronę (http://www.depesz.pl/various-sqltrees.php), a potem wykorzystaj klasę Tree z PEAR-a (http://pear.php.net/package/Tree).

[spenalzo]

W sumie to mam już rozwiązane, jak bede miał więcej czasu to opisze