• The collection of trees is called a forest. A single node by itself is a degenerate tree. Each of the trees in the forest will have a root, so the concept of an orphan does not really work. I think you wanted to establish a node is the root of a single tree and that for some reason you are breaking pieces of the tree off incorrectly.

    You will probably find this in any textbook on graph theory. I do not know if you had time to look at the nested set model, very quickly. Here is the skeleton of a nested set model for your tree;

    CREATE TABLE Forest

    (node_name VARCHAR(20) NOT NULL PRIMARY KEY,

    lft INTEGER NOT NULL CHECK (lft > 0),

    rgt INTEGER NOT NULL CHECK (rgt > 1),

    CHECK(lft < rgt));

    INSERT INTO Forest

    VALUES

    ('Root',1,8),

    ('first child of root',2, 5),

    ('first child of first child of root',3,4),

    ('second child of root', 6,7),

    --- this has to be forced in a nested sets model

    ('orphan' 100,103),

    ('child of 5', 101, 102);

    In order to create an "orphan", you have to go out of your way and force it in the nested set model. This means disjoint trees (as opposed to subtrees) will not have (lft, rgt) coordinates not between the (lft, rgt) coordinates of the second tree. You seem to want to use the tree whose root is named "root", so you would need something like this:

    WITH Root_Tree (node_name,lft, rgt)

    SELECT node_name, lft, rgt FROM Forest WHERE lft =1;

    SELECT F.node_name, F.lft, F.rgt

    FROM Forest AS F, Root_Tree AS R

    WHERE F.lft NOT BETWEEN R.lft AND R.rgt

    Books in Celko Series for Morgan-Kaufmann Publishing
    Analytics and OLAP in SQL
    Data and Databases: Concepts in Practice
    Data, Measurements and Standards in SQL
    SQL for Smarties
    SQL Programming Style
    SQL Puzzles and Answers
    Thinking in Sets
    Trees and Hierarchies in SQL