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.
>
> dynamic heterogeneous: parse tree. There are specific kinds of
> nodes, but the structure of the tree is relatively unconstrained.

Or "often constrained by the grammar of a language"?

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

If you looking at these trees having metadata as nodes down to values as leaf nodes, then I would say that SQL handles some subset of such trees. If a name on a node refers to a multipart value, or a value that is a tuple of dimension > 1, so that it has two or more non-leaf nodes as children, then SQL would require that name to refer to a relation. Also, if a name on a node refers to multiple values, that name must refer to a relation (not a list, for example).

It might be the case, however, that trees of this type can be converted into a tree structure that SQL can handle where only metadata is lost in the conversion. For example, if "Organization" has a child node of "address" which has child nodes that include "city" and "postcode" then SQL isn't going to do well with references made to "address". Or am I misunderstanding?

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

I work with a model that I think fits into your static homogeneous category, but where an fk can go either direction (using multivalues).

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

I find it somewhat interesting and worth pursuing, but this partitioning doesn't resonate with me. cheers --dawn

>
> Marshall
Received on Mon Jul 18 2005 - 14:57:38 CEST