Recursive SQL query on nested-set tree with stop condition

Question

I am using a nested-set tree structure in a table. The concept is described here.

The example data looks as follow:

+----+-----------+------+-------+-----------------+
| id | parent_id | left | right | stop_descending |
+----+-----------+------+-------+-----------------+
|  1 |      NULL |    1 |    10 |               0 |
|  2 |         1 |    2 |     3 |               0 |
|  3 |         1 |    4 |     9 |               1 |
|  4 |         3 |    5 |     6 |               0 |
|  5 |         3 |    7 |     8 |               0 |
+----+-----------+------+-------+-----------------+

Getting the whole tree is pretty straightforward:

SELECT t0.*
FROM nested_set AS t0
LEFT JOIN nested_set AS t1 ON t0.left BETWEEN t1.left AND t1.right
WHERE t1.parent_id IS NULL
ORDER BY t0.left;

However, I would like to get all nodes whose parent has not a stop_ descending flag. The result should include nodes 1,2,3. Nodes 4,5 should be excluded as their parent has the stop_ descending flag. If nodes 4 and 5 would have children, these should be excluded as well. The recursion should stop, once the is_leaf value equals 1.

I tried many different approaches but never got the proper result. Im am running the query in MariaDB 10.1.26. Maybe there a better solution involing CTE on higher version.

I just changed the column names. This should describe the actual question better. — kiessan
– kiessan, Commented Feb 23, 2018 at 19:35

Juan Carlos Oropeza · Accepted Answer · 2018-02-23 20:27:16Z

2

You do another self join to check if that leaf is part of a node with stop_decending = 1

SQL DEMO

SELECT t0.*, t1.*, t3.*
FROM nested_set AS t0
LEFT JOIN nested_set AS t1 
  ON t0.left BETWEEN t1.left AND t1.right

LEFT JOIN nested_set as t3
  ON t0.id BETWEEN t3.left AND t3.right
 AND t3.stop_descending  = 1

WHERE t1.parent_id IS NULL
  AND t3.id IS NULL
ORDER BY t0.left;

OUTPUT

| id | parent_id | left | right | stop_descending | id | parent_id | left | right | stop_descending |     id | parent_id |   left |  right | stop_descending |
|----|-----------|------|-------|-----------------|----|-----------|------|-------|-----------------|--------|-----------|--------|--------|-----------------|
|  1 |    (null) |    1 |    10 |               0 |  1 |    (null) |    1 |    10 |               0 | (null) |    (null) | (null) | (null) |          (null) |
|  2 |         1 |    2 |     3 |               0 |  1 |    (null) |    1 |    10 |               0 | (null) |    (null) | (null) | (null) |          (null) |
|  3 |         1 |    4 |     9 |               1 |  1 |    (null) |    1 |    10 |               0 | (null) |    (null) | (null) | (null) |          (null) |

For debug comment the filter AND t3.id IS NULL

edited Feb 23, 2018 at 20:27

answered Feb 23, 2018 at 19:32

Juan Carlos Oropeza

48.4k14 gold badges87 silver badges128 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

kiessan Over a year ago

This just returns the root node for me. Furthermore, it would only cover the direct children of that node.

Juan Carlos Oropeza Over a year ago

Please check again.

Collectives™ on Stack Overflow

Recursive SQL query on nested-set tree with stop condition

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related