Re: more algebra

I should have said something like this (using D&D-style algebra):

If { K } stands for the set of key attributes of r and N stands for the set of non-key attributes,

( r GROUP ( { N } AS n ) ) = ( EXTEND r ADD ( RELATION { TUPLE { N   } AS n ) { K, n }

will be 'true' iff r satisfies the key constraint.

I admit the above is pretty ugly but underneath it's pretty simple. More graphically, if you have:

r:
a b
1 2
1 3
2 4,

and supposing 'a' is to be 'key', the left-hand-side would 'look' like:

r':
a n:b
1 {2,3}
2 {4}

and the right-hand-side like:

r'':
a n:b

1 {2}
1 {3}
2 {4}

so the constraint would fail and changing the equation into an expression by replacing '=' with 'MINUS' would produce the tuple{s} that violate the constraint.

I realize some people might prefer to use a builtin 'COUNT' function which would simplify the above somewhat and others would say why not just have a keyword? It is very interesting to me how implementations often mimic some procedure that is suggested by the chosen language verbs, style and syntax with what I would call a cultural bias. As a user, I too would prefer simple keywords and clauses like the 'key' that sql uses.

But as we know, sql is not very rigourous whereas I think the D&D algebra is, eg., the above expressions seem to me to work fine when the set of key attributes is empty and also when it is equal to set of all of r's attributes. So I think the simple user interface is a big trap.

Perhaps all of this post is premature, but can't help suggesting that implementers need to devise intermediate syntax and a way to translate the algebra to it in order to make the possible optimizations more obvious as I think the graphical representation does. In other words, I think an algebraic definition (predicate logic is okay too, but I suspect even harder to write for most people) is crucial for correct results but not very easy to optimize for all cases. I don't know what work has been done specifically about this, although I know there has been plenty done in the compiler field in order to map the same language to different processors. Received on Wed Apr 07 2010 - 02:05:23 CEST