Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find all nodes in a subtree in a recursive SQL query?

I have a table which defines a child-parent relationship between nodes:

CREATE TABLE node (                           ' pseudo code alert
  id        INTEGER PRIMARY KEY,
  parentID  INTEGER, ' should be a valid id.
)

If parentID always points to a valid existing node, then this will naturally define a tree structure.

If the parentID is NULL then we may assume that the node is a root node.

How would I:

  1. Find all the nodes which are decendents of a given node?
  2. Find all the nodes under a given node to a specific depth?

I would like to do each of these as a single SQL (I expect it would necessarily be recursive) or two mutually recursive queries.

I'm doing this in an ODBC context, so I can't rely on any vendor specific features.

Edit

  • No tables are written yet, so adding extra columns/tables is perfectly acceptable.
  • The tree will potentially be updated and added to quite often; auxillary data structures/tables/columns would be possible, though need to be kept up-to-date. If you have any magic books you reach for for this kind of query, I'd like to know.

Many thanks.

like image 933
jamesh Avatar asked Jan 19 '09 00:01

jamesh


People also ask

How do you find the number of nodes in a subtree?

Thus, we can calculate the number of nodes recursively using the concept of DFS and DP, where we should process each edge only once and count[] value of children used in calculating count[] of its parent expressing the concept of DP(Dynamic programming). Time Complexity : O(n) [in processing of all (n-1) edges].

How do you find the number of nodes in left subtree?

Find the left and the right height of the given Tree for the current root value and if it is equal then return the value of (2height – 1) as the resultant count of nodes. Otherwise, recursively call for the function for the left and right sub-trees and return the sum of them + 1 as the resultant count of nodes.

How do I get all parent children in SQL?

level + 1 FROM pc a JOIN cte c ON a. parent = c. child ) SELECT distinct parent, child , level FROM cte order by level, parent; This will give you all descendants and the level.

How do you recurse in SQL?

Recursion is achieved by WITH statement, in SQL jargon called Common Table Expression (CTE). It allows to name the result and reference it within other queries sometime later. Naming the result and referencing it within other queries.


1 Answers

This link provides a tutorial on both the Adjacency List Model (as described in the question), and the Nested Set Model. It is written as part of the documentation for MySQL.

What is not discussed in that article is insertion/delection time, and maintenance cost of the two approaches. For example:

  • a dynamically grown tree using the Nested Set Model would seem to need some maintenance to maintain the nesting (e.g. renumbering all left and right set numbers)
  • removal of a node in the adjacency list model would require updates in at least one other row.
like image 167
jamesh Avatar answered Sep 22 '22 22:09

jamesh