From: PV

To: Editor

Date: 18 Feb 2004

 

I have a problem on representing trees. It's only a theoretical problem anyway, and I tried to solve it without success.

 

I'm required to create a relation or a set of relations that can represent a tree like the one below (the example is a binary tree):

 

        A
        |
   +----+----+
   |         |
   B         C
             |
       +-----+-----+  
       |           |  
       G           H  
       |           |
    +--+--+     +--+--+
    |     |     |     |
    I     J     K     L

 

The condition is, it should be possible to sort the nodes in pre-order, in-order, and post-order. When sorted, the corresponding sort orders of the nodes in the example are:

 

Preorder:  ABCGIJHKL

Inorder:   BIJGKLHCA

Postorder: BAIGJCKLH

 

How should I solve this problem? I tried to solve it using Tutorial D, since there's a TCLOSE operator there.

 

 

Fabian Pascal Responds: How the representation and manipulation of data hierarchies should be handled in relational systems is covered in chapter 7, Climbing Trees in SQL, in my PRACTICAL ISSUES IN DATABASE MANAGEMENT. The underlying relational principle is to represent order information explicitly, as values in tables, rather than implicitly in the physical ordering of tuples in tables; such information can be generated by a well-designed true relational RDBMS (TRDBMS).

 

This is precisely where SQL implementation fail: their recursive operations violate this relational principle by using implicit ordering and nonrelational operations such as UNION ALL; they are also highly procedural and not very intuitive.

 

To the extent that a product does not support hierarchic operations, users must either develop their own stored procedures (if the product supports them), or write application code.

 

 

Posted 04/16/04