Convert a standard Mysql table to a nested table

Question

What is the cleanest way to convert a MySQL table like this :

     id | fullindi                              | parent | rank
---------------------------------------------------------------
      1 | LHUILLIER Pierre (ca 1700 - 1745)     |    0   |   0
      9 | LHUILLIER Claude (ca 1729 - 1806)     |    1   |   1
  10357 | LHUILLIER Joseph (ca 1730 - 1738)     |    1   |   2
      7 | LHUILLIER François (ca 1731 - 1794)   |    1   |   3
      3 | LHUILLIER Antoine (1736 - av. 1797)   |    1   |   4
      4 | LHUILLIER Anne Marie (1737 - ____)    |    1   |   5
   4903 | LHUILLIER Dominique (1740 - ____)     |    1   |   6
      5 | LHUILLIER Thérèse (1741 - ____)       |    1   |   7
      8 | LHUILLIER Augustin (ca 1743 - ____)   |    1   |   8
      6 | LHUILLIER Joseph (1745 - ap. 1804)    |    1   |   9
    322 | LHUILLIER N... (1749 - ____)          |    9   |   1
    323 | LHUILLIER Marianne (1751 - ____)      |    9   |   2
    324 | LHUILLIER François (1752 - ____)      |    9   |   3
    325 | LHUILLIER Augustin (1754 - av. 1810)  |    9   |   4
    326 | LHUILLIER Léopold (1757 - av. 1819)   |    9   |   5
    327 | LHUILLIER Nicolas (1758 - ____)       |    9   |   6
    328 | LHUILLIER N... (1760 - ____)          |    9   |   7
    329 | LHUILLIER Claude (1765 - ____)        |    9   |   8
   4643 | LHUILLIER Jean Baptiste (1766 - 1836) |    9   |   9
    331 | LHUILLIER Marie Jeanne (1767 - 1823)  |    9   |  10
   etc

to a nested table like this :

     id | fullindi                              | posleft | posright
--------------------------------------------------------------------
      1 | LHUILLIER Pierre (ca 1700 - 1745)     |    0    |   848
      9 | LHUILLIER Claude (ca 1729 - 1806)     |    1    |   1
    322 | LHUILLIER N... (1749 - ____)          |    2    |   3
    323 | LHUILLIER Marianne (1751 - ____)      |    4    |   5
    324 | LHUILLIER François (1752 - ____)      |    6    |   7
    325 | LHUILLIER Augustin (1754 - av. 1810)  |    8    |   9
   etc

I precise that it needs to be independent of the depth (max = 20 levels ) and of the number of items (more than 1.000 items).

Any help will be greatly appreciate.

Best regards.

Answer 1

There is a previous question Here

Where someone does this in php, you could probably take the logic from that to get the solution you need.

I found this on a crappy website and the SQL was all in one line so it has taken a bit of formatting. I have left the sample pretty much as is and all credit should go the the fantastic Joe Celko who has been writing about sql for years.

     CREATE TABLE Tree (
    child CHAR(10) NOT NULL, 
    parent CHAR(10), 
    CONSTRAINT PK_Tree PRIMARY KEY CLUSTERED(child))

     -- insert the sample data for testing 

     INSERT INTO Tree(child,parent) VALUES ('Albert', NULL)
     INSERT INTO Tree(child,parent) VALUES ('Bert', 'Albert') 
     INSERT INTO Tree(child,parent) VALUES ('Chuck', 'Albert') 
     INSERT INTO Tree(child,parent) VALUES ('Donna', 'Chuck') 
     INSERT INTO Tree(child,parent) VALUES ('Eddie', 'Chuck') 
     INSERT INTO Tree(child,parent) VALUES ('Fred', 'Chuck') 


CREATE TABLE Stack (
    StackID int IDENTITY(1,1),
    stack_top INTEGER NOT NULL, 
    child VARCHAR(10) NOT NULL, 
    lft INTEGER NOT NULL, 
    rgt INTEGER, 
    CONSTRAINT PK_Stack PRIMARY KEY CLUSTERED(StackID))


    DECLARE @lft_rgt INTEGER, @stack_pointer INTEGER, @max_lft_rgt INTEGER

    SET @max_lft_rgt = 2 * (SELECT COUNT(*) FROM Tree)

    INSERT INTO Stack 
    SELECT 1, child, 1, @max_lft_rgt 
    FROM Tree 
    WHERE parent IS NULL

    SET @lft_rgt = 2

    SET @Stack_pointer = 1

    DELETE FROM Tree WHERE parent IS NULL

    -- The Stack is now loaded and ready to use 

    WHILE (@lft_rgt < @max_lft_rgt) 
        BEGIN 
            IF EXISTS (SELECT * FROM Stack AS S1, Tree AS T1 WHERE S1.child = T1.parent AND S1.stack_top = @stack_pointer) 
                BEGIN 
                    -- push when stack_top has subordinates and set lft value 
                    INSERT INTO Stack 
                    SELECT (@stack_pointer + 1), 
                    MIN(T1.child), 
                    @lft_rgt, 
                    NULL 
                    FROM Stack AS S1, 
                    Tree AS T1 
                    WHERE S1.child = T1.parent AND S1.stack_top = @stack_pointer

                     -- remove this row from Tree 
                     DELETE FROM Tree 
                     WHERE child = (SELECT child FROM Stack WHERE stack_top = @stack_pointer + 1)

                     SET @stack_pointer = @stack_pointer + 1 
                END 
        -- push 
        ELSE 
            BEGIN 
                -- pop the Stack and set rgt value 
                UPDATE Stack SET rgt = @lft_rgt, stack_top = -stack_top 
                WHERE stack_top = @stack_pointer 

                SET @stack_pointer = @stack_pointer - 1
            END

            -- pop 
        SET @lft_rgt = @lft_rgt + 1
    END

You should be able to use this to sort out your list by changing the column names etc.

Once again this is not my work, once again thanks again to Joe Celko (I have been a fan of the nested set model for a long time now and have a few systems in production using it). I have been unable to find Joe's blog if there is one (If you are out there please comment here and take all the credit.