Re: Universal Quantifier

On Jan 27, 4:58 am, Bob Badour <bbad..._at_pei.sympatico.ca> wrote:
> paul c wrote:
> > Marshall wrote:
>
> >> Consider that database constraints can be expressed as quantified
> >> logical formula. If table A has primary key p and table B has attribute
> >> q which is a foreign key referencing A(p), we could express that as:
>
> >> forall B(q). exists A(p). p=q;
> >> ...
>
> > What formula would express a primary key?
>
> Faking it heavily, I suggest something along the lines of:
>
> forall A1(p1,q1) in A(p,q). forall A2(p2,q2) in A(p,q).
> if p1 = p2 then q1 = q2;
>
> where p is actually the set of attributes composing the key and q is
> actually the set of dependent attributes.

Yes. To expand, what we are really doing with this kind of constraint is expression functional dependencies; keys are a kind of FD.

There is a funny issue of naming that comes up. With many constraints (such as my FK constraint above) we only need mention any given attribute of any given relation once. However, to express an FD, we have to express each attribute twice. This raises some syntactic questions. Bob's formulation above is one approach. An alternative approach I have considered is to allow renaming of attributes on the fly:

(In the context of Bob's schema above, with relation A(p, q) where {p} -> {q} )

  forall A(p, q). forall(p2=p, q2=q). p=p2 => q=q2

(The =>, read "implies" is equivalent to Bob's "if/then")

A more mainstream-math sort of approach would be to prime the attribute names, sort of semi-implicitly doing what we do above:

  forall A(p, q). forall A(p', q'). p=p' => q=q'

This is in fact my current favorite notation.

If we want to get terse (which we might or might not) we could consider the possibility of writing (or viewing) a constraint within the context of a given relation. We could also adopt the convention that universal quantification is assumed if no quantification is explicitly supplied. (Again, this is a convention that one occasionally sees here or there.) In that case we can simply write:

  (In the context of A)

  p=p' => q=q'

Which is actually quite readable. In fact in general omitting the relation and assuming the forall makes for better readability than you might guess given how much is being omitted.

This works especially well when describing properties of relations that are functions; for example of integer division, we could write its type as follows:

  /: a:int, b:int -> c:int | b != 0

The "b != 0" constraint, made fully explicit, would be

  forall /(b). b != 0

which really doesn't add much.

Expanding on my idea of a "relation context" above, I should note that it is a notational convenience only; there is no actual first-class context involved. In fact, after reading various authors' categorizations of constraints by scope, I have come to the conclusion that "there is no 'there' there"; all constraints are database constraints. If a constraint happens to range over only a single relation, well, that's just how many of the relations in the database it happens to range over.

Consider my FK constraint from a few messages back:

  forall B(q). exists A(p). p=q

Is that a constraint on A, or a constraint on B? If we viewed it in the context of A, we might write it as:

  forall B(q). exists (p). p=q

and there is a similarly shorter version we might view in the context of B. I could imagine an interactive dbms that would let us view all constraints, view constraints of A, etc., that might abbreviate things accordingly if we supplied a specific context.

I also seem to recall that Vadim had yet another formulation for FDs, although I can't recall what it was and searching didn't find it.

> One also has to express irreducibility, though.

Hmmm. I'm not clear if perhaps irreducibility isn't a second-order property.

In any event, I could imagine that a constraint system might be able to deduce that a given FD was implied by a different FD, and hence redundant.

Marshall Received on Sat Jan 27 2007 - 18:42:37 CET