[sqlite] Re: Some questions on hierarchical data (nested set model)

[Jef Driesen]

Jef Driesen wrote:

I want to store a tree in an sqlite database. My first choice was the adjacency list model:

CREATE TABLE tree (
    id INTEGER PRIMARY KEY AUTOINCREMENT,
    name TEXT,
    parent_id INTEGER
);

But this method requires multiple queries to display the entire tree (or a subtree) in my GUI (a gtk+ treeview). Because childs can only be added to the treeview if all its parents are already added.

But then I found some resources on the nested set model [1,2]:

CREATE TABLE tree (
    id INTEGER PRIMARY KEY AUTOINCREMENT,
    name TEXT,
    lft INTEGER,
    rgt INTEGER
);

Retrieving a (sub)tree can be done with only one sql query, at the expense of more complex queries to add or remove rows. Because all lft and rgt values to the right of the node have to be modified.

[1] http://www.sitepoint.com/article/hierarchical-data-database
[2] http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

I start to understand this model, but I still have some questions:

Q3. How do I move a node (or subtree)?

In the adjacency list model, this is extremely easy by pointing the parent_id to another node. But I don't know how to do that in the nested set model.

I managed to solve this problem now. I had to write my solution (see
below) in pseudo sql code (e.g some extra non-sql code was required)
because sqlite does not support stored procedures. It think it is doable
to incorporate the IF/THEN/ELSE inside the sql query, but I didn't try
to do that.

a = @source_lft;
b = @source_rgt;
IF @source_lft < @target_lft THEN
     c = @b + 1;
     d = @target_rgt - 1;
     v =  (@d - @c + 1) = @target_rgt - (@b + 1);
     w = -(@b - @a + 1);
     e = @a;
     f = @d;
ELSE
     c = @target_rgt;
     d = @a - 1;
     v = -(@d - @c + 1) = @target_rgt - @a
     w =  (@b - @a + 1);
     e = @c;
     f = @b;
END IF;

UPDATE tree SET lft = lft + CASE
     WHEN lft BETWEEN @a AND @b THEN
        @v /* Move the subtree up/down */
     ELSE
        @w /* Make room for the subtree under the new parent */
     END
     WHERE lft BETWEEN @e AND @f;
UPDATE tree SET rgt = rgt + CASE
     WHEN rgt BETWEEN @a AND @b THEN
        @v /* Move the subtree up/down */
     ELSE
        @w /* Make room for the subtree under the new parent */
     END
     WHERE rgt BETWEEN @e AND @f;




-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------