Nested Sets - przenoszenie węzłów i liści góra/dół Opcje

[grz16w]

Witam.

Czy ktoś wie lub posiada przykład działającej poprawnie funkcji przesuwania liści i węzłów w strukturze Nested Sets wewnątrz jednej gałęzi (rodzica)? Mam tabelę posiadającą kolumny `id`, `nazwa`, `lft`, `rgt`, `parent`. W jaki sposób zamienić miejscami dwa węzły lub liście wewnątrz tego samego rodzica (uwzględniając, że te węzły mogą posiadać również swoje dzieci itd.)? Z góry dziękuję serdecznie za odpowiedzi

[Crozin]

Zanim zapomnę: o ile dobrze pamiętam phpBB3 albo jakiś inny PHP-owski skrypt forum ma drzewo kategorii oparte o ten właśnie model i jest tam kod do przenoszenia - możesz podejrzeć.

Ogólnie to jest to trochę... zamotane. Bo trzeba zmieniać klucze LFT i RGT w połowie drzewa przy próbie przeniesienia jakiegoś węzła. Sprawy nie ułatwia fakt, że właściwie każdy rodzaj czy nawet wariant operacji wymaga nieco innego podejścia.

Przede wszystkim musisz wyliczyć deltę, czyli fragment drzewa który przenosisz (różnica RGT i LFT). Następnie musisz pomniejszyć indeksy LFT / RGT wszystkich elementów występujących po przenoszonej gałęzi właśnie o wartość delty. Teraz drzewo ponownie jest spójne - nie ma żadnych "dziur". Kolejny krok to zrobienie miejsca na przenoszoną gałąź. Musisz indeksy LFT / RGT wszystkich elementów które będą miały występować po wklejanym elemencie zwiększyć o wartość delty. Ostatni krok to zmienienie indeksów LFT / RGT przenoszonej gałęzi tak by pasowały do swojej nowej lokacji.

I jeszcze kilka rad:
1. W przypadku nested set warto również przechowywać w bazie informacje o poziomie zagłębienia konkretnego elementu - bardzo ułatwia to wiele operacji.
2. Całość obejmij transakcją.
3. Mimo iż da się to skrócić czasami do mniejszej ilości ale bardziej skomplikowanych zapytań nie rób tego. 10 prostych UPDATE-ów jest po stokroć lepsze niż 2 skomplikowane, pełne CASE-ów i innych paskudnych konstrukcji.

[jang]

http://www.phpriot.com/articles/nested-trees-2/7

Odrobinę trzeba przerobić bo klasa jest pod postgree ale z tego co pamiętam to działało całkiem nieżle.
Za pomocą dodatkowego zapytania zmieniasz wartość "parent_id" czyli przenosisz liścia , gałąź w inne miejsce. Następnie wywołujesz metodę rebuild() i masz nowe drzewko

[JoShiMa]

Witam.

Czy ktoś wie lub posiada przykład działającej poprawnie funkcji przesuwania liści i węzłów w strukturze Nested Sets wewnątrz jednej gałęzi (rodzica)?

Czytałeś to: przenoszenie gałęzi ?

[grz16w]

Czytałeś to: przenoszenie gałęzi ?

tak, czytałem i w podobny sposób zrobiłem inne funkcje, czyli przenoszenie gałęzi, a nie zamiana miejscami (wewnątrz jednej gałęzi nadrzędnej). Nie wiedziałem jak z tego to drugie wykombinować

Crozin, wielkie dzięki, świetny opis, już się biorę do roboty mam nadzieję że się uda bo tylko ta funkcja mi została do opracowania

[JoShiMa]

tak, czytałem i w podobny sposób zrobiłem inne funkcje, czyli przenoszenie gałęzi, a nie zamiana miejscami (wewnątrz jednej gałęzi nadrzędnej). Nie wiedziałem jak z tego to drugie wykombinować

Ale to nie ma znaczenia gdzie przenosisz. Istotą jest tylko żeby prawidłowo obliczyć miejsce.

[grz16w]

Ale to nie ma znaczenia gdzie przenosisz. Istotą jest tylko żeby prawidłowo obliczyć miejsce.

Mój błąd, masz rację, właśnie skończyłem tą opcję i faktycznie to tak funkcjonuje a korzystając z okazji miałbym jeszcze jedno pytanko. Czy jest możliwość obliczenia "głębokości" danego węzła/liścia mając do dyspozycji jedynie pola `lft`, `rgt`, `parent` bez możliwości stworzenia dodatkowej kolumny np. `depth`?

Ten post edytował grz16w 11.04.2011, 22:04:52

[Crozin]

Można ale jest to dosyć skomplikowane, a trzymanie tego w formie statycznej nie sprawia wielu problemów przy modyfikacji drzewa. A warto to mieć o czym przekonasz się chociażby w w momencie gdy będziesz chciał wybrać przykładowo tylko pierwszy poziom zagłębienia itp.

[JoShiMa]

Mój błąd, masz rację, właśnie skończyłem tą opcję i faktycznie to tak funkcjonuje a korzystając z okazji miałbym jeszcze jedno pytanko. Czy jest możliwość obliczenia "głębokości" danego węzła/liścia mając do dyspozycji jedynie pola `lft`, `rgt`, `parent` bez możliwości stworzenia dodatkowej kolumny np. `depth`?

Oczywiście i nawet parent nie jest potrzebne i to wcale nie jest skomplikowane (Crozin opowiada bzdury). W cyklu artykułów z którego jeden Ci podesłałam jest to pokazane. Chyba w trzecim z serii. W jednym niezbyt skomplikowanym zapytaniu możesz wyciągnąć dowolną gałąź i od razu policzyć depth dla wszystkich jej elementów/ Dodając w takim zapytaniu klauzlę HAVING wyciąg asię tylko wskazany poziom. Bułka z masłem.

--- EDIT ---

Tak czysto logicznie. Wystarczy policzyć ile elementów ma jednocześnie lft mniejszy i rgl większy od tego, który badasz. Policzysz w ten sposób wszystkie elementy, które okalają wskazany a więc sa dla niego nadrzędne. Proste, nie?

@Crozin naucz się wreszcie tego, no nie trudne a może przestaniesz straszyć ludzi.

Ten post edytował JoShiMa 11.04.2011, 22:45:36

[Crozin]

@JoShiMa: Szkoda tylko, że nie dodałeś że dynamiczne obliczanie zagłębienia wymaga dodatkowego złączenia (w dodatku w jednym z gorszych wariantów), HAVING też do demonów szybkości nie należy. No i trzeba powtarzać ten bezsensowny krok za każdym razem, gdy chcemy skorzystać z tej kolumny.

Przy 1 000 rekordów to bez znaczenia, ale przy 500 000 czy 50 mln sprawa wygląda trochę inaczej.

Ten post edytował Crozin 11.04.2011, 23:00:27

[JoShiMa]

@JoShiMa: Szkoda tylko, że nie dodałeś że dynamiczne obliczanie zagłębienia wymaga dodatkowego złączenia

Lub podzapytania. I nie odwracaj kota ogonem. Pisałeś, że to wyjątkowo trudne a ja twierdzę, że bułka z masłem.

(w dodatku w jednym z gorszych wariantów), HAVING też do demonów szybkości nie należy. No i trzeba powtarzać ten bezsensowny krok za każdym razem, gdy chcemy skorzystać z tej kolumny.

Jeszcze bardziej bezsensowne jest przeliczanie kolumny ilekroć chcemy przenieść element lub gałąź.

Nie musisz lubić nested-set, bo jak wszystko mają swoje wady. Fajnie jednak by było, gdybyś nie wprowadzał w związku z tym ludzi w błąd pisząc, że to koszmarnie trudne.

[Crozin]

Lub podzapytania. I nie odwracaj kota ogonem. Pisałeś, że to wyjątkowo trudne a ja twierdzę, że bułka z masłem.

To podzapytanie to o ile się nie mylę (już trochę późno jest) jeszcze gorszy pomysł. I nigdzie nie napisałem, że jest to "wyjątkowo trudne", tylko "dosyć skomplikowane" bo jest*. Programiście utrudnia prace, bo każdorazowo musi zaśmiecać treść zapytania fragmentem do wyliczenia tej wartości, a silnik bazy danych wręcz katowany jest jeżeli mamy do czynienia z jakimś sensowniejszym zestawem danych.

Jeszcze bardziej bezsensowne jest przeliczanie kolumny ilekroć chcemy przenieść element lub gałąź.

Uznam, że po prostu z rozpędu już to palnąłeś. Bo właśnie napisałeś, że jednokrotne wyliczenie wartości i zapisanie jej jest bardziej bezsensowne niż każdorazowe wyliczenie tej samej wartości. Może jeszcze miałoby to sens w przypadku gdyby owa wyliczana wartość zajmowała masę miejsca, ale tutaj mowa jest o zwykłej liczbie całkowitej.

Nie musisz lubić nested-set, bo jak wszystko mają swoje wady. Fajnie jednak by było, gdybyś nie wprowadzał w związku z tym ludzi w błąd pisząc, że to koszmarnie trudne.

A gdzie napisałem, że nie lubię? Zresztą jak można nie lubić "algorytmu"? I nie wciskaj mi słów których nigdy nie napisałem (patrz: koszmarnie trudne) bo takie coś jest po prostu bezczelne.

PS. Nie wiem czy zauważyłeś, ale kłócisz się (bo tak to zaczynam odbierać) o straszną pierdołę. O to, że zasugerowałem przechowywanie wyniku jednej operacji na stałe w bazie.

* Dobra, może "skomplikowane" to złe słowo tutaj - ale "niewygodne" pasuje idealnie.

Ten post edytował Crozin 11.04.2011, 23:34:08

[JoShiMa]

To podzapytanie to o ile się nie mylę (już trochę późno jest) jeszcze gorszy pomysł.

Wręcz przeciwnie. Przy większych bazach jest szybsze.

I nigdzie nie napisałem, że jest to "wyjątkowo trudne", tylko "dosyć skomplikowane" bo jest*. Programiście utrudnia prace, bo każdorazowo musi zaśmiecać treść zapytania fragmentem do wyliczenia tej wartości

Za to przy Twoim sposobie każdorazowo musi zaśmiecać kod wyliczeniami nowych wartości depth przy przenoszeniu gałęzi. Przenosząc gałąź do innej lokalizacji musisz obliczyć depth dla tej lokalizacji. różnicę między wartością bieżącą a doelową i przeliczyć depth wszystkich elementów przenoszonej gałęzi. Rzeczywiście. Mniej skomplikowane. No sorry ale nie przekonasz mnie, że to jest jakiekolwiek ułatwienie. Nie wiem czemu ale odnoszę wrażenie, że znasz zagadnienie jedynie z teorii.

Aha. Wolałabym, żebyś się do mnie zwracał w rodzaju żeńskim.

[wiewiorek]

Joshima napisal: "@Crozin naucz się wreszcie tego, no nie trudne a może przestaniesz straszyć ludzi. / Pisałeś, że to wyjątkowo trudne a ja twierdzę, że bułka z masłem. "

Uwielbiam takich ludzi jak Joshima - mowia, ze cos jest latwe ale kodu nie podadza - jak to mowi moja babcie "g*** widzieli, g*** umieja"

Nested set z pewnością są SKOMPLIKOWANE !

grz16w więc co tam chciałeś ? przenoszenie gałęzi - więc to będzie tak:
zakładając, że mamy tabelę nested_category z kolumnami:
category_id
name
lft
rgt

Kod do przenoszenia poddrzewa:

[SQL] pobierz, plaintext 
--przenoszenie poddrzewa np. z category_id = 2 i podczepienie go do np. category_id = 6:
START TRANSACTION;
 
--jesli przenoszone poddrzewo ma trafic na poczatek:
--SELECT @destination := (lft + 1) FROM nested_category WHERE category_id = 6;
--jesli przenoszone poddrzewo ma trafic na koniec:
SELECT @destination := rgt FROM nested_category WHERE category_id = 6;
SELECT @cat_a_width := ((rgt - lft) + 1) FROM nested_category WHERE category_id = 2;
 
UPDATE nested_category SET rgt = rgt + @cat_a_width WHERE rgt >= @destination;
UPDATE nested_category SET lft = lft + @cat_a_width WHERE lft >= @destination;
 
SELECT @cat_a_lft := lft, @cat_a_rgt := rgt FROM nested_category WHERE category_id = 2;
SELECT @diff := @destination - @cat_a_lft;
 
UPDATE nested_category SET rgt = rgt + @diff WHERE rgt BETWEEN @cat_a_lft AND @cat_a_rgt;
UPDATE nested_category SET lft = lft + @diff WHERE lft BETWEEN @cat_a_lft AND @cat_a_rgt;
 
UPDATE nested_category SET rgt = rgt - @cat_a_width WHERE rgt >= @cat_a_lft;
UPDATE nested_category SET lft = lft - @cat_a_width WHERE lft >= @cat_a_lft;
 
COMMIT;
[SQL] pobierz, plaintext 

Glebokosc elementow drzewa daje:

[SQL] pobierz, plaintext 
SELECT node.name, (COUNT(parent.category_id) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.category_id
ORDER BY node.lft;
[SQL] pobierz, plaintext 

Ale tak jak mowil Crozin - ZDECYDOWANIE daj kolumne depth i parent_id - zobaczysz ze to w wielu sytuacjach ulatwi zapytania. A i jeszcze dodam, ze sam zawsze sie waham czy uzywac nested set czy adjacency list, ale mysle ze warto wziac pod uwage, ze w wiekszosci wypadkow uzywana bywa adjacency list czyli sposob z sama kolumna parent_id i nie wplywa to w zauwazalny sposob na czas oczekiwania na wyswietlenie strony - jesli rekordow jest bardzo duzo to wowczas stosuje sie cachowanie.

Ten post edytował wiewiorek 12.04.2011, 08:03:59

[JoShiMa]

Uwielbiam takich ludzi jak Joshima - mowia, ze cos jest latwe ale kodu nie podadza - jak to mowi moja babcie "g*** widzieli, g*** umieja"

Podałam linka do serii artykułów w których pokazane są i wyjaśnione wszystkie zapytania. Nieskromnie dodam, że sama to pisałam. Więc nie mów mi, że kodu nie podałam. Trzeba tylko uważnie czytać cały wątek.

[grz16w]

Więc tak.. Użyłem metody:

SELECT node.name, (COUNT(parent.category_id) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.category_id
ORDER BY node.lft;

jednak nie wiem jak z tego wykombinować głębokość konkretnego elementu. To zapytanie wyświetla mi jedynie tablicę, w której jest tylko pierwszy rekord z bazy i jego zagłębienie. Jak dostać się do pozostałych elementów? Od razu mówię że troszkę jestem zielony jeżeli chodzi o SQL

[JoShiMa]

A to zapytanie wywołujesz w bazie czy w skrypcie PHP? Powinno Ci wyrzucić wszystkie elementy jesli masz prawidłowo skonstruowane drzewo i wszystkie elementy lft rgt mają prawidłowe wartości.Pokaż zawartość tabeli.

[grz16w]

Wykonuję to zapytanie przez PHP. Gdy wykonuję w panelu phpMyAdmin wyświetla poprawnie tabelę nazw z przypisanymi wartościami zagłębienia, natomiast poprzez PHP już nie.

Kod

$zapytanie = "
SELECT node.nazwa, (COUNT(parent.id) - 1) AS depth
FROM kategorie AS node,
kategorie AS parent
WHERE node.lewa BETWEEN parent.lewa AND parent.prawa
GROUP BY node.id
ORDER BY node.lewa;
";

$sql = mysql_query($zapytanie);
$sql = mysql_fetch_assoc($sql);
print_r($sql);

po tym wyświetla mi tablicę tylko z pierwszym elementem z bazy...

Kod

Array
(
    [nazwa] => kat1
    [depth] => 0
)

zrzuty z phpMyAdmin:

[Crozin]

To podzapytanie to o ile się nie mylę (już trochę późno jest) jeszcze gorszy pomysł.

Wręcz przeciwnie. Przy większych bazach jest szybsze.

Aż zrobię testy jutro czy pojutrze jak znajdę chwilę czasu. Wyniki oczywiście udostępnię.

Za to przy Twoim sposobie każdorazowo musi zaśmiecać kod wyliczeniami nowych wartości depth przy przenoszeniu gałęzi. Przenosząc gałąź do innej lokalizacji musisz obliczyć depth dla tej lokalizacji. różnicę między wartością bieżącą a doelową i przeliczyć depth wszystkich elementów przenoszonej gałęzi. Rzeczywiście. Mniej skomplikowane. No sorry ale nie przekonasz mnie, że to jest jakiekolwiek ułatwienie.

Na dobrą sprawę to jedyne co trzeba zrobić to:

[SQL] pobierz, plaintext 
UPDATE ... SET depth = depth + 123 WHERE ...;
[SQL] pobierz, plaintext 

Gdzie 123 to różnica dla korzenia przenoszonej gałęzi. WHERE określa jeszcze po prostu całą przenoszoną gałąź.

Nie wiem czemu ale odnoszę wrażenie, że znasz zagadnienie jedynie z teorii.

Nie wiem czemu ale odnoszę wrażenie, że jest dokładnie odwrotnie albo doszło tutaj do jakiegoś nieporozumienia między nami.

@grz16w: mysql_fetch_array zwraca kolejny (jeden) wynik z pobranych. W manualu masz przykład użycia.

Nie wiem czemu ale odnoszę wrażenie, że znasz zagadnienie jedynie z teorii.

Przepraszam, przyzwyczajenie.

[JoShiMa]

$sql = mysql_query($zapytanie);
$sql = mysql_fetch_assoc($sql);
print_r($sql);[/code]

po tym wyświetla mi tablicę tylko z pierwszym elementem z bazy...

No bo pobierasz tylko jeden rekord. mysql_fetch_assoc($sql); ma latać w pętli

@Crozin, znów oszukujesz. Najpierw trzeba obliczyć depth dla miejsca docelowego i depth węzła który przenosisz. Dopiero potem możesz obliczyć różnicę i wykonać zapytanie, które pokazałeś. Niby drobiazgi, ale jednak

Ten post edytował JoShiMa 12.04.2011, 21:52:40