Re: An alternative to possreps

On 9 jun, 11:49, David BL <davi..._at_iinet.net.au> wrote:
>
> I think there are some interesting differences to consider.  Consider
> the following wikipedia article on algebraic data types:
>
>    http://en.wikipedia.org/wiki/Algebraic_data_type
>
> This has an example of a recursive type named 'Tree' written in
> Haskell as follows:
>
> data Tree = Empty
>           | Leaf Int
>           | Node Tree Tree
>
> Assuming Tutorial D doesn't balk at recursive types,

It does.

Furthermore, the concept of wanting to fit graph structures in a scalar type definition seems inappropriate. I'm inclined to suggest that your "proliferation of types" derives from this (inappropriate) desire (to make graphs fit with the scalar types feature) (or at least to make them fit in a way that is really inappropriate - see further).

The canonical way for dealing with trees (and in fact arbitrary graphs), is to observe that they are a set of nodes plus a set of edges. So a "graph" type is a type that has two components : NODES and EDGES. This means that a graph type can be considered as being a TUPLE type with two attributes, or it can be considered as being a scalar type with two components NODES and EDGES. The difference between these two options is in fact negligible.

But the important thing to observe is that both NODES and EDGES will be set-valued in either case, and in the RM context that means : they will be relation-valued components (or tuple attributes). From that point onward, you are outside the realms of what scalar types and possreps give you, instead you've passed over into the realm of operators of the relational algebra (plus transitive closure and its generalized version).

Using transitive closure on the EDGES, plus the operators of the relational algebra, gives you everything you need to answer queries such as "give me the tree that has node <X> for root.". And (just by way of example) if <X> is a leaf, then you will get a GRAPH value in which the NODES component (/attribute) is singleton <X> and the EDGES component is the empty relation.

Under the IM, you _COULD_ define a LEAF type to be a subtype of your GRAPH type (with precisely the type constraint that NODES is singleton and EDGES empty), but note that this doesn't happen "generically" for every conceivable GRAPH type (your GRAPH type will be different and thus distinct for each possible node type).

> How is your project going? I've had a look at your web site a few
> times, but not read it in any detail.  Have you implemented a DBMS
> that supports ACID transactions?

It could hardly be called a DBMS if it didn't have ACID, no ? Not too much progress these last few months, alas. Received on Sat Jun 11 2011 - 16:49:24 CEST