Hack 85. Traverse a Simple Tree

You want to implement and query a tree of your ancestors. Just who is your sister's brother's cousin again?

You want to construct your ancestral tree in a database. For testing purposes you have to use your relatives' titles (such as mum and dad) rather than their names (Janette, Ian, etc.). Your test tree looks like Figure 10-4.

Figure 10-4. Family tree hierarchy

You want to be able to query the database and determine who your ancestors are.

When building a tree-like hierarchy such as this one, the foreign keys are the descendents. This structure would look like Table 10-13.

You can find direct ancestors by following the parent link to the next ancestor. You need to repeat this for the maximum depth of the tree. In this case, the tree has a maximum depth of 3, and thus a maximum of two steps are required. For one step:

SELECT parent FROM ancestors WHERE parent IS NOT NULL AND name = 'Me' ; PARENT ------- Dad

For two steps:

SELECT parent FROM ancestors WHERE parent IS NOT NULL AND name = 'Me' UNION SELECT a2.parent FROM ancestors a1 JOIN ancestors a2 on (a1.parent = a2.name) WHERE a2.parent IS NOT NULL AND a1.name = 'Me' ; PARENT -------- Dad Dads Dad

Writing queries using this approach can quickly become really disgusting! One way to conceal the hack is to make a view of the parentchild relationships:

CREATE VIEW relationship AS SELECT parent,name as child FROM ancestors WHERE parent IS NOT NULL UNION SELECT a2.parent,a1.name FROM ancestors a1 JOIN ancestors a2 on (a1.parent = a2.name) WHERE a2.parent IS NOT NULL ;

As long as you have coded sufficient depth into the view, you can query parentage using:

SELECT parent FROM relationship WHERE child = 'Me';

You can change this to find all descendents of 'Dads Dad':

SELECT child FROM relationship WHERE parent = 'Dads dad' ; CHILD ------------------------------------------------------------ Dad Brother Me Sister

The weakness of this approach is that you must know the maximum depth of the tree before you create the view. If you underestimate the depth, the query will still run, but it will give only a partial answer.

10.9.1. Tree Visualization

You can adapt this technique to build a visual representation of the tree. The order of the rows in the representation is critical, so you will have to order by the root node, and then the second from the root, then the third, and so on. One tricky issue occurs when you are ordering on a component that is NULL. The SQL standard does not precisely state what happens with an ORDER BY involving NULL, and it tends to have its own rules that are different from what you would expect. You can sidestep this issue by substituting the space character where NULL would normally appear:

DROP VIEW treeinfo; CREATE VIEW treeinfo as SELECT a1.name as node,a1.name p1,' ' as p2,' ' as p3,1 as depth FROM ancestors a1 WHERE parent IS NULL UNION SELECT a1.name as node,a2.name as p1,a1.name as p2,' ' as p3,2 as depth FROM ancestors a1 JOIN ancestors a2 on (a1.parent = a2.name) WHERE a2.parent IS NULL UNION SELECT a1.name as node,a3.name as p1,a2.name as p2,a1.name as p3,3 as depth FROM ancestors a1 JOIN ancestors a2 on (a1.parent = a2.name) JOIN ancestors a3 on (a2.parent = a3.name) WHERE a3.parent IS NULL ;

You need the p1,p2,p3 fields only to maintain the ordering of the tree. You never have to show them in the query result:

select tree from ( SELECT p1,p2,p3,'+'||node tree FROM treeinfo where depth = 1 UNION SELECT p1,p2,p3,' +--'||node tree FROM treeinfo where depth = 2 UNION SELECT p1,p2,p3,' +--'||node tree FROM treeinfo where depth = 3 ) ORDER by p1,p2,p3

In MySQL, you need to use an alias for the derived table. You also need to use CONCAT rather than ||:

select tree from ( SELECT p1,p2,p3, CONCAT('+', node) tree FROM treeinfo where depth = 1 UNION SELECT p1,p2,p3, CONCAT(' +--', node) tree FROM treeinfo where depth = 2 UNION SELECT p1,p2,p3, CONCAT(' +--', node) tree FROM treeinfo where depth = 3 ) t ORDER by p1,p2,p3

For the family tree example, this produces:

TREE ------------------ +Dads Dad +--Dad +--Brother +--Me +--Sister 5 rows selected.

10.9.2. Oracle Recursive Extensions

Oracle includes some SQL extensions that allow you to traverse a tree without knowing the maximum depth in advance. The CONNECT BY clause allows you to link each child node to its parent. For instance, to find 'Me' and all ancestors you could do:

SQL> SELECT name 2 FROM ancestors 3 CONNECT BY PRIOR parent = name 4 START WITH name = 'Me'; NAME ------------------------------------------------------------ Me Dad Dads Dad

You can reverse the CONNECT BY equality to get descendants, and you can view the depth of the recursion using the pseudovariable LEVEL. To see all descendants of 'Dads Dad' you could use:

SQL> SELECT name, LEVEL 2 FROM ancestors 3 CONNECT BY PRIOR name = parent 4 START WITH name='Dads Dad'; NAME LEVEL ------------------------------------------------------------ ---------- Dads Dad 1 Dad 2 Brother 3 Sister 3 Me 3

Rudy Limeback and Gordon Russell