I was trying to lookup some old posts, maybe started by Marshall, not
sure about that, to do with defining keys. Finally gave up, for some
reason the google new archive isn't my cup of tea.


I remember thinking that keys could be defined algebraically something
like this: Let {K} stand for the set of attributes of r that make a key,

( r GROUP ( {K} AS k ) ) {k} = ( r {K}) GROUP ( {K} AS k)) {k}

will be true when r satisfies the key constraint.

( r GROUP ( {K} AS k ) ) {k} MINUS ( r {K}) GROUP ( {K} AS k)) {k}

will contain rva's that include the keys of tuples that violate the
constraint. UNGROUP could also be used.


Seem to remember some objection or other, but not exactly what it was.


(I don't suggest that this should be directly implemented, just that it
gives a minimal definition that is algebraic (eg., doesn't resort to any
notion of 'Count'). One reason an algebra (eg., D&D's) seems important,
more than expository, is because it serves as a definition for some of
the central operation of a relational machine, ie. defines the machine.
Sometimes surprises me that people looking for initial implementation
guidance aren't pointed to an algebra first. Implementation of the
above is more than exercise in optimization as it would 'prove' many of
the features any relational machine needs.)

paul c wrote:
Oops, I can think of my own objections. Must have been thinking of
something else because the above is definitely wrong.

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.

On Apr 7, 3:05*am, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

How about A join project_K(A)=A? No counts, nesting or aggregates
there, and off the top of my head it pretty much captures the idea:
the left to right inclusion is trivial, but if there are separate
tuples with the same key, the join produces spurious tuples in excess
of the original relation.

Or in other words, since a key constraint is basically shorthand for
{K->A_i} where A_i ranges over all of the attributes of the relation,
the above is a point-free algebraic means of expressing the equivalent
set of equality generating tableaux.
--
Sampo

On Apr 8, 6:47*am, Sampo Syreeni <de... (AT) iki (DOT) fi> wrote:
This is not a constraint. [Natural] join (aka D&D <AND>, or in less
sloppy notation "^") is a semilattice operation, so that it induces a
partial order "<" (which is essentially subset order generalized from
unary relations into n-ary relations) via equivalence:

x ^ y = x <-> x < y

Projection is a generalized union ("v") -- a complementary operation
which elevates semilattice into lattice. Therefore, the constraint
becomes

A < A v K

which holds in a lattice trivially. The other way to see it is to
rewrite the constraint

A join project_K(A)=A

in the lattice terms as

A ^ (K v A) = A

which trivially holds by absorption law.

On Apr 8, 6:59*pm, Vadim Tropashko <vadim... (AT) gmail (DOT) com> wrote:

As I spelled it, no, it indeed isn't; a hardy remainder of why I
should never try to do any mental calculation or to device any new
notation to suit my intuitions. But I'll try again: perhaps I meant to
say A join_K A=A instead, without renaming attributes.. We want to
express K_1=K_2 => (A\K)_1=(A\K)_2, algebraically and point-free. The
basic idea remains the same: no extra tuples.

The right to left inclusion is trivial: by the definition of an
equijoin: a self-equijoin cannot lose tuples, nor can you project
downto something which losslessly joins back because all attributes
are present on either side. The left to right direction remains to be
shown. First suppose the key constraint holds. In this case a join
along the key will match precisely one tuple in either direction, so
the result of the join is an identity, and inclusion holds.
Contrariwise suppose that the above "constraint" does not apply. Then
there are at least two tuples for which K is equal but A\K differ.
That means that they would be crossmatched in the join. Now choose one
of the crossmatched cases from the right side and project back to
left; either you now have values which weren't in the original A or a
contradiction in the tuples not agreeing on K. The latter case shows
that K is not in fact a key.

True, this is still hazy logic, but not quite as bad as my previous
post. And even if it needs emendation, the gist of the argument should
be clear.
--
Sampo

Sampo Syreeni wrote:
I believe it's always true, so not much use as a constraint. Suspect
it's just a variation on Heath's theorem with the "third" attribute set
empty. All you can conclude from Heath is NOT("K is key") OR ("A = A{K}
JOIN A"). You can't conclude NOT("A = A{K} JOIN A") OR ("K is key").
Ie., if K->N is true, the equation is true, but if K->N is not true, I
think the equation is still true when only two attribute sets are
mentioned, at least it is for the values I gave, which is enough to make
it useless as a constraint.


No counts or aggregates in either. By 'nesting' I presume you mean what
D&D call 'GROUP'-ing - I believe they use the term to avoid confusion
with so-called NFNF relations. Such a GROUP always implies a key and
vice-versa. Keys being so fundamental from a practical point of view
(the basic addressing mechanism), makes me wonder if there is a possible
algebra where such a GROUP is fundamental. If possible, I guess it
would have to be a binary operator (as Vadim's projection operator is).
But maybe it's the case that there is a proof that such an algebra
would require NFNF relations.

On Apr 8, 10:18*am, Sampo Syreeni <de... (AT) iki (DOT) fi> wrote:
Algebraically and point free -- no argument there. Unless I understand
your idea differently, from my perspective "point-free" algebraic
notation means no mentioning attribute sets whatsoever. I'm not sure
what Paul meant by "key constraint", but inclusion dependency is
expressed algebraically (http://arxiv.org/abs/0902.3532) as

r v x < s v x

To think of it: this kind of inequality is the simplest expressionn
that one can manufacture from 3 relation symbols and relational
operations, so no wonder it is important.

The functional depndency constraint, is entirely different animal,
however. It can be expressed with the count ("given a function
argument the number of values in the range of is no more than one"),
but this is outside the scope of relational algebra. The other (rather
neat) construction from database folklore involves partitions (http://
vadimtropashko.wordpress.com/relational-lattice/lattice-perspective-
into-funcional-dependencies/)

Vadim Tropashko wrote:
By 'key constraint', I meant also what you call 'functional dependency
constraint', not inclusion dependency.

On Apr 8, 10:18*am, Sampo Syreeni <de... (AT) iki (DOT) fi> wrote:
Please define this notation in terms of common operators.
Preferably by equivalent formal notation not natural language.

I am interested in knowing what you are trying to say and helping you.
But your writing always consists of vague phrases of which
it is difficult to impossible to identify or guess the referents.
This is exacerbated by misconceptions and histrionics.
The way to be clear is to put in the effort to force yourself to be
clear,
instead of settling for being unclear.

philip