Re: Three Kinds of Logical Trees

Marshall Spight wrote:
> I've been thinking about trees in the abstract lately, and
> trying to classify them. I am not talking about trees as
> a physical data structure, such as BTrees or Red-Black, but
> rather trees as logical data structures. In other words,
> the *interface* to a tree.
>
> I've identified three distinct kinds.
> "homogeneous tree"
> All nodes are the same type, tree has varying structure
>
> "dynamic heterogenous"
> Nodes are varying types, tree has varying structure
>
> "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.

Or a simpler example of a tree with an interger on each node.

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

There are people here much more knowledgeable about trees than I (but that has not stopped me before, eh?) but even with the lose definition, I wouldn't say "relatively unconstrained" but perhaps "either unconstrained or constrained by a grammar." The grammar constraint might not be fully encoded into the tree, due to the complexity of the grammar.

> 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.

I'm not so sure. If your tree extends from metadata down to data values, you might have to add in that less-than-satisfying term "scalar value" for your leaf nodes. Otherwise, if you have such a structure and you have a value that is either multipart or multivalued within this static structure, you still don't have SQL-92 support and most SQL-DBMS's don't make it easy to have such structures, even if they are supported in some way.

Interesting topic, but I not quite sure about this partitioning as yet.  Are you trying to carve out how the relational model fits within a tree model by giving a term to such trees? If so and if I understand your terms, then there are at least NF2 (non-first normal form) models that would fit your "static" heterogeneous term. Cheers! --dawn Received on Sat Jul 16 2005 - 17:25:15 CEST