Hi all,

I use a simple nested set to repesent a hierarchical menu in SQL. I've read Joe
Celkos article about trees at

http://www.intelligententerprise.com/001020/celko.shtml

and my simple menu table (in MySql) contains the fields id(bigint),
menuname(varchar), left(int), right(int). So it's easy to build up a structure
like this:

A(1,8)

Unfortunately the reorganization of the tree is more complex and I can not find
answers to my two questions on the net:

1. How to renumber the values for left and right after the deletion of an
element? When I delete element C(4,7) in the tree, D and A have to change to
D(4,5) and A(1,6). How to formulate this in SQL?

2. How to exchange two elements and their subtrees? After swapping elements B
and C (their menu names) the tree should be structured like this:

A(1,8)

The problem are the subtrees (D) which can hold a different number of elements.
I tried to save the subtrees in a temporary table, delete them from the tree and
then reinsert them under their swapped parents, but the copy/delete/reinsert
takes a lot of SQL code. Is there any easier way to swap elements?

Kind regards,
Oliver

element? <<

That depends on your business rules for replacing an employee. Let's
just promote the subordinates to their former boss's boss:

CREATE VIEW LftRgt (i)
AS SELECT lft FROM OrgChart
UNION ALL
SELECT rgt FROM OrgChart;

UPDATE OrgChart
SET lft = (SELECT COUNT(i)
FROM LftRgt
WHERE i <= lft,
rgt = (SELECT COUNT(i)
FROM LftRgt
WHERE i <= rgt;

The following solution for swapping the positions of two siblings
under the same parent node is due to Mr. Vanderghast and originally
appeared in a posting on the MS-SQL Server Newsgroup.

If the leftmost sibling has its (lft, rgt) = (i0, i1) and the other
subtree, the rightmost sibling, has (i2, i3), implicitly, we know that
(i0 < i1 < i2 < i3).

With a little algebra, we can figure out that if (i) is a lft or rgt
value in the table between i0 and i3, then

1) If (i BETWEEN i0 AND i1) then (i) should be updated to (i + i3-
i1).

2) If (i BETWEEN i2 AND i3 then (i) should be updated to (i + i0 -
i2).

3) If (i BETWEEN i1+1 AND i2-1) then (i) should be updated to (i0 + i3
+ i - i2 -i1).

All of this becomes a single update statement, but we will put the
(lft, rgt) pairs of the two siblings into local variables so a human
being can read the code.

CREATE PROCEDURE SwapSiblings
(IN lft_sibling CHAR(2), IN rgt_sibling CHAR(2))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
DECLARE i0 INTEGER;
DECLARE i1 INTEGER;
DECLARE i2 INTEGER;
DECLARE i3 INTEGER;
SET i0 = (SELECT lft FROM Tree WHERE node = lft_sibling);
SET i1 = (SELECT rgt FROM Tree WHERE node = lft_sibling);
SET i2 = (SELECT lft FROM Tree WHERE node = rgt_sibling);
SET i3 = (SELECT rgt FROM Tree WHERE node = rgt_sibling);

UPDATE Tree
SET lft = CASE WHEN lft BETWEEN i0 AND i1
THEN i3 + lft - i1
WHEN lft BETWEEN i2 AND i3
THEN i0 + lft - i2
ELSE i0 + i3 + lft - i1 - i2 END,
rgt = CASE WHEN rgt BETWEEN i0 AND i1
THEN i3 + rgt - i1
WHEN rgt BETWEEN i2 AND i3
THEN i0 + rgt - i2
ELSE i0 + i3 + rgt - i1 - i2 END
WHERE lft BETWEEN i0 AND i3
AND i0 < i1
AND i1 < i2
AND i2 < i3;
END;

I am current developing a class for PHP4, to make nested sets available
for MySql
This is a solution for your first problem in PHP4 for MySql


<?php
function delete_node($id) {
$id = (int)$id; //force int to avoid sql-injections
// thats for mysql we should lock the tables
if (!$this->db_query("LOCK TABLES {$this->tablename} WRITE")) {
return false;
}
// get the root_id ,left_id and right_id of the node that should be
deleted
if (!$row = $this->get_node($id)) {
return false;
}
list($root_id, $left_id, $right_id) = $row;
// delete node
$sql = "DELETE FROM {$this->tablename} WHERE id ='$id'";
if (!$this->db_query($sql)) {
return false;
}
// hang all childs of the deleted node one element higher (close
the gap)
$sql = "UPDATE {$this->tablename} SET left_id = left_id-1, right_id
= right_id-1 ";
$sql.= "WHERE root_id = '$root_id' AND left_id BETWEEN $left_id AND
$right_id";
if (!$this->db_query($sql)) {
return false;
}
// update the left_id of the right neighbour nodes
$sql = "UPDATE {$this->tablename} SET left_id = left_id-2 ";
$sql.= "WHERE left_id > $right_id AND root_id = '$root_id'";
if (!$this->db_query($sql)) {
return false;
}
// update the right_id of the right neighbour nodes
$sql = "UPDATE {$this->tablename} SET right_id = right_id-2 ";
$sql.= "WHERE right_id > $right_id AND root_id = '$root_id'";
if (!$this->db_query($sql)) {
return false;
}
if (!$this->db_query("UNLOCK TABLES")) {
return false;
}
// ok
return true;
}
?>

Sorry for bother you with PHP code!

Recommendation:
to increase the performance of your nested set model, you should add the
column 'root_id'.
For example, every thread in a discussion forum gets his own root_id. Is
there a new reply, only
the tree with the same root_id has to be changed. This improves the read
and write performance
of a nested set model considerable.

A great tutorial in german about nested sets:
http://ffm.junetz.de/members/reeg/DS...00000000000000

regards Dietmar Simons




Oliver Berse schrieb:

Oliver Berse wrote:

I think, you can rather easily perform the delete of one single element
if you look at it as two actions:
1 Move the subtrees out from the element as siblings of the element to
delete.
2 Delete the element and all of its subtrees (none left due to 1)

I'm sure that this is doable in one step, too. But you might need both
actions anyway. Therefore you can just program those and combine them.


As to swapping: Here it might also be easier to do it as two actions:
1 Copy the first element incl. subtrees after the second (insert it!)
2 Delete the first element

Otherwise, you'll have to store the width of one of the elements in
order to do two updates.
By the way, step 2 is identical to step 2 of the first task.


If you need actual SQL, just post what you've tries so far.

Regards,
Heinz