Re: Nested Sets and Delete/Exchange?

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.

| id | root_id | left_id | right_id | payload |

A great tutorial in german about nested sets:

http://ffm.junetz.de/members/reeg/DSP/node10.html#SECTION04340000000000000000

regards Dietmar Simons

Oliver Berse schrieb:

> 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)
> |       \
> B(2,3)  C(4,7)
>         |
>         D(5,6)
> 
> 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)
> |       \
> C(2,5)  B(6,7)
> |
> D(3,4)
> 
> 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
>