Re: Three Kinds of Logical Trees

dawn wrote:
> 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.

Yes. But I'm not sure how realistic an example that is. Note that I'm trying to classify *logical* trees, so the structure of the tree needs to have some meaning apart from just being a data structure. Usually when we talk about a tree of ints, we've got some data structure going because we want logn lookup. That I would call a set, even if the underlying physical structure is a tree.

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

Yes, exactly. In other words, one has, say, 20 different kinds of nodes; each node type may have a fixed or variable number of children; each specific child may be constrained to be of a particular type: a parse tree. I'm looking for a term that captures the fact that a node has a specific structure. Each node has fixed *local* structure, but the tree's *overall* structure is not fixed. (Hence "dynamic heterogeneous.")

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

(I am unclear why you use the term "metadata" here. To me that means the system catalog; one doesn't usually join from the catalog to user-define tables, yes?)

I agree "scalar" is an unsatisfying term. I have in mind a better one, but it requires a type system that's a lot different from SQL's. (Which I assert is an "opportunity." :-)

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

I'm not saying that this is necessarily the best way to go, but you can certainly handle this case in a 1NF way.

I think this kind of structure is what one often ends up with in SQL. And I do think it works really well. Consider the customer/account/ invoice/invoice line item sort of case. The structure is rigid, but any of the queries you want to ask against this sort of structure are quite easy.

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

Yes!

SQL handles the static heterogeneous case with ease, but really chokes on the other two cases. The big difference seems to be the fixed depth vs. variable depth issue. It's impossible to handle variable depth without something more powerful than the basic RM; you need something at least as powerful as transitive closure; recursive queries or (ugh) iteration will also work.

So the area I'm exploring is, what kinds of operations do we want to do on the dynamic tree types, and what smallest bit of power to we have to add to the RM to handle that well?

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

The issue for me is not the model so much, as it is what operators do we need to work on them. Modeling structure is relatively easy; the hard part is querying, updating, and constraining.

Marshall Received on Thu Jul 21 2005 - 17:01:43 CEST