Three Kinds of Logical Trees

"static heterogeneous"

  Nodes are varying type, tree has fixed structure.

Examples

homogeneous: org chart. Every node is a person record, but the structure of the organization may be of whatever form.

dynamic heterogeneous: parse tree. There are specific kinds of nodes, but the structure of the tree is relatively unconstrained.

static heterogeneous: customer/account/invoice/line item. Each level in the tree is fixed, with fixed relationships.

Here "dynamic" and "static" refer to the structure of the tree.

SQL handles the third kind of tree extremely well. The first two kinds, not so much. In particular, noth that the transitive closure problem applies to the first two kinds of trees, but not to the third.

The functional programming people have lots of examples in their books of dynamic heterogeneous trees, and the mixture of union types and pattern matching as language features seems to handle these structures quite well. You could probably use the same techniques to handle homogenous trees equally well.

Interestingly, I note that static tree nodes have a reference (fk) to their parent, while the homogeneous and dynamic hetero types are done with a node having references to its children.

Comments? Has anyone else written about this sort of thing?

Marshall Received on Fri Jul 15 2005 - 10:17:16 CEST