CODEWITHSUNDEEP
sqldatabasesqlitedata-structurestree
jonjbar
jonjbar

Reputation: 4066

Select next(sibling) and previous(sibling) from a SQLite DB tree representation

I've got the following sample tree structure in an SQLite DB:

id | idparent | order
1    -1         0
2     1         0
3     2         0
4     1         1

Which represents the following tree:

1
|- 2
|  |- 3
|- 4

And I would like to create a select statement to get all the nodes next, previous, next sibling and previous sibling. Such a statement would return from the previous sample:

id | idparent | next | previous | nextsibling | previoussibling
1    -1         2      NULL       NULL          NULL
2     1         3      1          4             NULL
3     2         4      2          NULL          NULL
4     1         NULL   3          NULL          2

I can get the nextsibling and previoussiblingbut I'm stuck with the next and previous:

SELECT node.id, node.idparent,
??? AS next
??? AS previous,
(SELECT id FROM nodes WHERE idparent = node.idparent AND `order` > node.`order` LIMIT 1) AS nextsibbling,
(SELECT id FROM nodes WHERE idparent = node.idparent AND `order` < node.`order` LIMIT 1) AS previoussibbling
FROM nodes node;

I guess I need to use the WHERE NOT EXISTS clause but I can't figure out how I can achieve that. I should mention that changing the DB structure is not an option.

Thanks in advance for any help.

Upvotes: 1

Views: 993

Answers (2)

outis
outis

Reputation: 77450

Your schema (what's called the "adjacency list model") is rather limited in terms of which operations it supports. Instead, try the nested set mode: store bounds for each node rather than each node's parent. A node descends from all nodes where the parent's bounds contain the child's. The bounds also give the depth first traversal of the tree, where the lower bound gives when the node is entered and the upper bound gives when the node is exited. Sorting the nodes by the left bound thus gives a pre-order traversal, and sorting by the right gives a post-order traversal.

CREATE TABLE `hier` (
  `id` int(11) PRIMARY KEY AUTO_INCREMENT,
  `left` int(11) NOT NULL,
  `right` int(11) NOT NULL,
  `data` varchar(128),
  INDEX `bounds` (`left`,`right`),
  INDEX `sdnuob` (`right`, `left`)
);

INSERT INTO HIER (id, `left`, `right`, data) 
   VALUES
 (1, 1, 8, 'foo'),
 (2, 2, 5, 'mane'), 
 (3, 3, 4, 'padme'), 
 (4, 6, 7, 'hum')
;

SELECT h.id AS node,
    p.id AS prev, p.`left` AS p_l, n.id AS `next`, n.`left` AS n_l,
    ps.id AS prevSibling, ns.id AS nextSibling
  FROM hier AS h
    LEFT JOIN hier AS p ON h.`left` > p.`left`
    LEFT JOIN hier AS pb ON h.`left` > pb.`left`
    LEFT JOIN hier AS n ON h.`left`< n.`left`
    LEFT JOIN hier AS nb ON h.`left`< nb.`left`
    LEFT JOIN hier AS ps ON h.`left` = ps.`right`+1
    LEFT JOIN hier AS ns ON h.`right`= ns.`left`-1
  GROUP BY node, prevSibling, nextSibling, p.`left`, n.`left`
  HAVING (p.`left` IS NULL OR p.`left` = MAX(pb.`left`))
     AND (n.`left` IS NULL OR n.`left` = MIN(nb.`left`))
;

Result:

+------+------+------+------+------+-------------+-------------+
| node | prev | p_l  | next | n_l  | prevSibling | nextSibling |
+------+------+------+------+------+-------------+-------------+
|    1 | NULL | NULL |    2 |    2 |        NULL |        NULL |
|    2 |    1 |    1 |    3 |    3 |        NULL |           4 |
|    3 |    2 |    2 |    4 |    6 |        NULL |        NULL |
|    4 |    3 |    3 | NULL | NULL |           2 |        NULL |
+------+------+------+------+------+-------------+-------------+

If you really need to find a node's parent (or depth), you can use a view, or use the technique applied in the view to a query:

CREATE VIEW hier_depth AS 
SELECT c.*, p.id AS parent, p.`left` AS p_left, COUNT(a.id) AS depth
  FROM hier AS c
    LEFT JOIN hier AS p ON p.`left` < c.`left` AND c.`right` < p.`right`
    LEFT JOIN hier AS a ON a.`left` < c.`left` AND c.`right` < a.`right`
  GROUP BY c.id, parent
  HAVING p.`left` IS NULL OR p.`left` = MAX(a.left)
;

Upvotes: 2

Martin v. L&#246;wis
Martin v. L&#246;wis

Reputation: 127587

I don't think your schema supports a next query. IIUC, you might need to go up multiple levels to determine the next node.

I recommend to add a path column, which takes colon-separated paths as values, such as 1:2:3 or 1:4. The next node will then be the next one in path order.

Upvotes: 1

Related Questions