pytanie o nested set Opcje

[wiewiorek]

Jak mamy w bazie danych tabelę z kolumnami:
id | id_parent | order
To dodając nowy element użytkownik wybiera z select listy rodzica oraz z drugiej select listy liczbę reprezentującą wagę/kolejność dodawanego elementu w stosunku do innych na tym samym poziomie.

A jak mamy w bazie danych tabelę ze strukturą charakterystyczną dla nested set:
id | left | right
To użytkownik dodając nowy element wybiera z select listy rodzica, ale w jaki sposób może ustalić wagę/kolejność nowo dodawanego elementu w stosunku do innych na tym samym poziomie ? Nie bardzo wiem jak umożliwić użytkownikom ustalenie kolejności.

[Zyx]

Przecież left i right dzieci tego samego węzła są ułożone w kolejności, w jakiej te elementy występują:

Kod

SELECT ... ORDER BY `left`

[wiewiorek]

No dobra, ale jak rodzic ma dwójkę potomków a ja chcę wstawić miedzy nie jeszcze jednego potomka albo przed nimi, albo po nich to w jaki sposób mam to umożliwić użytkownikowi ?

[Crozin]

Musisz odpowiednio pozmieniać wartości left/right sporej części drzewa. W sieci masz mnóstwo przykładów na to jak przemieszczać poszczególne gałęzie w takim modelu drzewka. google: moving nested set, move nested set - czy cokolwiek zwierającego "nested set" i coś związanego z ruchem.

[wiewiorek]

Tylko takie przenoszenie gałęzi oznacza wielokrotny update co moze prowadzic do anomalii.

[everth]

A gdzie jest napisane że relacyjne bazy danych najlepiej nadają do tworzenia drzew? Jeśli rzeczywiście chcesz ustabilizować sobie strukturę drzewa to napisz jakiś wyzwalacz który po dodaniu dziecka uaktualni strukturę drzewa - bo wysyłanie kilkunastu zapytań w tym celu mija się z celem (IMG:style_emoticons/default/smile.gif)

[erix]

gałęzi oznacza wielokrotny update co moze prowadzic do anomalii.

Blokowanie tabeli albo transakcja.

[Crozin]

Tylko takie przenoszenie gałęzi oznacza wielokrotny update co moze prowadzic do anomalii.

Nie. Oznacza to jednokrotny update i insert. Ale jak już erix zauważył: transakcje.

[wiewiorek]

A ma ktos gotowe zapytania do przenoszenia poddrzewa ? Bo cos nie do konca mi dziala ten skrypt do przenoszenia galezi:

[SQL] pobierz, plaintext 
--tabela:
CREATE TABLE nested_category (
 category_id INT AUTO_INCREMENT PRIMARY KEY,
 name VARCHAR(20) NOT NULL,
 lft INT NOT NULL,
 rgt INT NOT NULL
);
 
INSERT INTO nested_category
VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
(9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
[SQL] pobierz, plaintext 

[SQL] pobierz, plaintext 
--skrypt do przenoszenia galezi z categori_id = 2 do category_id = 6:
LOCK TABLE nested_category WRITE;
 
 
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE category_id = 2;
 
SELECT @newMyRight := rgt
FROM nested_category
WHERE category_id = 6;
 
 
UPDATE nested_category
SET lft = 0-lft, rgt = 0-rgt
WHERE lft >= @myLeft AND rgt <= @myRight;
 
 
UPDATE nested_category
SET lft = lft - @myWidth
WHERE lft > @myRight;
 
UPDATE nested_category
SET rgt = rgt - @myWidth
WHERE rgt > @myRight;
 
 
UPDATE nested_category
SET lft = lft + @node_size
WHERE lft >= IF(@newMyRight > @myRight, @newMyRight - @myWidth, @newMyRight);
 
UPDATE nested_category
SET rgt = rgt + @node_size
WHERE rgt >= IF(@newMyRight > @myRight, @newMyRight - @myWidth, @newMyRight);
 
 
UPDATE nested_category
SET
    lft = 0-lft+IF(@newMyRight > @myRight, @newMyRight - @myRight - 1, @newMyRight - @myRight - 1 + @myWidth),
    rgt = 0-rgt+IF(@newMyRight > @myRight, @newMyRight - @myRight - 1, @newMyRight - @myRight - 1 + @myWidth)
WHERE lft <= 0-@myLeft AND rgt >= 0-@myRight;
 
 
UNLOCK TABLES;
[SQL] pobierz, plaintext 

Ten post edytował wiewiorek 5.08.2010, 20:13:44

[everth]

@wiewiorek - prawdopodobnie (nie testowałem dogłębnie tych procedur) poniżej masz kod do przenoszenia gałęzi.
Zapoznałem się bliżej z nested set (nie wiedziałem że istnieje taki model drzewa w sql (IMG:style_emoticons/default/winksmiley.jpg) i wychodzi na to że jest to bardzo fajna rzecz. Poprzednicy mówili o stosowaniu transakcji - zgadzam się, jednak jeśli tylko użytkownik ma możliwość tworzenia procedur to zarządzanie tym drzewem staje się bajecznie proste. Niestety w tym przypadku nie możemy użyć wyzwalaczy (może gdyby pokombinować, nie wiem).

Przy budowaniu procedur korzystałem z gotowców z tej strony oraz tego rozwiązania w przypadku przenoszenia gałęzi.

Templatka z procedurami była przygotowywana dla tabeli "nested_category", dla innych trzeba przepisać nazwę. Tak wygląda użycie:

[SQL] pobierz, plaintext 
CALL MOVE_BRANCH('NAZWA','DOKĄD'); -- przenosi gałąź NAZWA do kontenera DOKĄD
CALL ADD_SIBLING('OBOK','NAZWA'); -- tworzy nowy węzeł "NAZWA" obok węzła OBOK
CALL ADD_CHILD('RODZIC','NAZWA'); -- dodaje węzeł NAZWA do kontenera RODZIC
CALL REMOVE_NODE('NAZWA'); -- usuwa węzeł NAZWA wraz z wszystkimi dziećmi
CALL REMOVE_NODE_ONLY('NAZWA'); -- usuwa węzeł NAZWA, dzieci zostają przeniesione poziom wyżej
[SQL] pobierz, plaintext 

Templata z procedurami jest taka:

[SQL] pobierz, plaintext 
DELIMITER $$
 
DROP PROCEDURE IF EXISTS `MOVE_BRANCH`$$
CREATE PROCEDURE `MOVE_BRANCH` (IN `$FROM` VARCHAR(20), IN `$TO` VARCHAR(20))
BEGIN
    START TRANSACTION;
 
    /* cat_b.lft + 1 is the destination. */
    SELECT @destination := (lft + 1) FROM nested_category WHERE name = `$TO`;
 
    SELECT @cat_a_width := ((rgt - lft) + 1) FROM nested_category WHERE name = `$FROM`;
 
    /* Rip this table a new cat_a sized hole inside cat_b. */
    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 name = `$FROM`;
 
    SELECT @diff := @destination - @cat_a_lft;
 
    /* Move cat_a and all inhabitants to new hole */
    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;
 
    /* Close the gap created when we moved cat_a. */
    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;
END$$
 
DROP PROCEDURE IF EXISTS `ADD_SIBLING`$$
CREATE PROCEDURE `ADD_SIBLING`(IN `$container` VARCHAR(20), IN `$name` VARCHAR(20))
BEGIN
	START TRANSACTION;
	SELECT @myRight := rgt FROM nested_category WHERE name = $container;
	UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
	UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
	INSERT INTO nested_category(name, lft, rgt) VALUES($name, @myRight + 1, @myRight + 2);
	COMMIT;
END$$
 
DROP PROCEDURE IF EXISTS `ADD_CHILD`$$
CREATE PROCEDURE `ADD_CHILD`(IN `$container` VARCHAR(20), IN `$name` VARCHAR(20))
BEGIN
	START TRANSACTION;
	SELECT @myLeft := lft FROM nested_category WHERE name = $container;
	UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
	UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;
	INSERT INTO nested_category(name, lft, rgt) VALUES($name, @myLeft + 1, @myLeft + 2);
	COMMIT;
END$$
 
DROP PROCEDURE IF EXISTS `REMOVE_NODE`$$
CREATE PROCEDURE `REMOVE_NODE`(IN `$name` VARCHAR(20))
BEGIN
	START TRANSACTION;
	SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1 FROM nested_category WHERE name = $name;
	DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
	UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
	UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
	COMMIT;
END$$
 
DROP PROCEDURE IF EXISTS `REMOVE_NODE_ONLY`$$
CREATE PROCEDURE `REMOVE_NODE_ONLY`(IN `$name` VARCHAR(20))
BEGIN
	START TRANSACTION;
	SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1 FROM nested_category WHERE name = $name;
	DELETE FROM nested_category WHERE lft = @myLeft;
	UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
	UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
	UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
	COMMIT;
END$$
 
DELIMITER ;
[SQL] pobierz, plaintext 

Ten post edytował everth 7.08.2010, 00:08:54

[wiewiorek]

Dzięki everth (IMG:style_emoticons/default/smile.gif)

Mi w nested set nie podoba się to, że trudno wskazać położenie nowo dodawanego potomka w stosunku do innych potomków - bo najwygodniej dodaje się potomka przed innymi potomkami albo po innych potomkach. Bo jak np. mamy coś takiego:
zwierzęta
/ | \
pies kot chomik

To w jaki sposób dać użytkownikowi możliwość dodania 'bocian' po 'kot' ? Trudno powiedzieć, najłatwiej po prostu zawsze dodawać nowy element w tym samym miejscu - czyli na końcu - po 'chomik' lub na początku - przed 'pies' lub zrobić dla użytkownika select listę z opcjami wyboru położenia nowo dodawanego elementu: 'na początku' i 'na końcu'. No bo jak inaczej ? Zrobić dla użytkownika select listę z opcjami dla nowo dodawanego elementu:
-umieść przed pies
-umieść po pies
-umieść przed kot
-umieść po kot
-umieść przed chomik
-umieść po chomik

to by było bez sensu. Dlatego wskazywanie położenia nowo dodawanego elementu w nested set jest utrudnione i praktycznie ograniczone do położenia przed lub po innych elementach na tym samym poziomie.

[zegarek84]

To w jaki sposób dać użytkownikowi możliwość dodania 'bocian' po 'kot' ? Trudno powiedzieć, najłatwiej po prostu zawsze dodawać nowy element w tym samym miejscu - czyli na końcu - po 'chomik' lub na początku - przed 'pies' lub zrobić dla użytkownika select listę z opcjami wyboru położenia nowo dodawanego elementu: 'na początku' i 'na końcu'. No bo jak inaczej ? Zrobić dla użytkownika select listę z opcjami dla nowo dodawanego elementu:
-umieść przed pies
-umieść po pies
-umieść przed kot
-umieść po kot
-umieść przed chomik
-umieść po chomik

to by było bez sensu. Dlatego wskazywanie położenia nowo dodawanego elementu w nested set jest utrudnione i praktycznie ograniczone do położenia przed lub po innych elementach na tym samym poziomie.

domyślnie to najlepiej dodawać na końcu (jak to tradycyjnie wszystko na końcu ląduje)... jednak jeśli chcesz taką listę robić i możliwość wyboru to zauważ, że powtórzyły się miejsca wyboru na tej liście... najnaturalniej by było jeśli chcesz listę rozwijalną to razem z grupowaniem gdzie wymieniasz elementy na tym samym poziomie a do wyboru jest tylko miejsce lub wymieniasz elementy normalnie nie w liście za koleją i miedzy tymi elementami masz input typu ratio domyślnie z zaznaczoną ostatnią opcją (czyli na końcu)...

poza tym w tabeli wg. mnie warto sobie to połączyć z parent_id (szybciej znajdziesz elementy na tym samym poziomie jeśli jest bardzo wiele poziomów...

samą wartość parent_id możesz sobie wygenerować np. jednym zapytaniem:

[SQL] pobierz, plaintext 
SELECT node.*, parent.id AS parent FROM `test_tree` AS node, `test_tree` AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.id!=parent.id
GROUP BY node.id
ORDER BY parent.lft DESC
[SQL] pobierz, plaintext 

zaś wartości poprzypisywać w dodatkowej kolumnie np. tym:

[SQL] pobierz, plaintext 
UPDATE `test_tree` SET p_id = (SELECT parent.id FROM `test_tree` AS node, `test_tree` AS parent
WHERE `test_tree`.id = node.id AND node.lft BETWEEN parent.lft AND parent.rgt AND node.id!=parent.id
GROUP BY node.id
ORDER BY parent.lft DESC)
[SQL] pobierz, plaintext 

z kolei samo przenoszenie gałęzi już istniejących to jakoś wydaje mi się, że prościej skorzystać z tabel tymczasowych do tego celu przeznaczonych - ale jak kto woli...
ogólnie fajnie jest to wszystko opisane na tym blogu:
Me vs. tree czyli drzewka w MySQL i PHP

Ten post edytował zegarek84 7.08.2010, 11:37:14