Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Given the following type of data structure.

    ID  NAME  TREELEFT  TREERIGHT  PARENT
    1   XYZ       1         2         0
    2   ABC       3         6         0
    3   DEF       4         5         2
    4   HIJ       7         10        0
    5   KLM       8         9         4
    6   NOP       11        16        0
    7   QRS       12        15        6
    8   TUV       13        14        7

The methodology is more or less identical to the nested set model except I've included a parent, just to make my life a little easier. (https://en.wikipedia.org/wiki/Nested_set_model#Example) I need to come up with a way of detecting gaps. For example if ID=6 had a different treeright say 17. There would technically be a gap of 1.

For the moment I've done this in a series of different queries.

One to detect if treeright doesn't exceed 2n, another to detect if treeright is always > than treeleft. Another couple to ensure that no treelefts or treerights are identical to each other.

However if I could add just check to ensure that the tree had no gaps I'm sure a couple of the other tests would become redundant. Can anyone think of a good way to do this. I've been racking my brain on this one for quite a long period of time.

share|improve this question
    
So basically you want to know if a btree is broken, and therefore a gap in select val from (select treeleft as val from treetable union all select treeright as val from treetable) order by val ? –  Phil Oct 17 '12 at 17:11
    
@Phil Yes I want to see if the btree is broken. What would be the query given the union that will detect a gap? –  Mark D Oct 23 '12 at 3:16

1 Answer 1

up vote 0 down vote accepted

It took me a while to figure this one out.

        SELECT  t1.id      + 1 AS `start`, 
                MIN(t3.id) - 1 AS `stop`
          FROM (SELECT  table1.id
                  FROM (SELECT treeleft  AS id FROM structure
                        UNION ALL
                        SELECT treeright AS id FROM structure
                       )  
                    AS  table1) 
             AS t1
LEFT OUTER JOIN (SELECT  table2.id
                   FROM (SELECT treeleft  AS id FROM structure
                         UNION ALL
                         SELECT treeright AS id FROM structure 
                        )  
                     AS  table2)  
             AS  t2 
             ON  t1.id = t2.id - 1
LEFT OUTER JOIN (SELECT  table3.id
                   FROM (SELECT treeleft  AS id FROM structure
                         UNION ALL
                         SELECT treeright AS id FROM structure
                        ) 
                     AS  table3) 
             AS  t3
             ON  t1.id < t3.id
          WHERE  t2.id IS NULL 
            AND  t3.id IS NOT NULL
       GROUP BY  t1.id, 
                 t2.id;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.