Re: Constraints and Functional Dependencies

From: Marshall <>
Date: 24 Feb 2007 08:41:27 -0800
Message-ID: <>

On Feb 24, 7:35 am, mAsterdam <> wrote:
> Hi Marshall,

Hey dude! Long time no chat.

> [snip intro]
> > With such a system, a relation R with attribute a (which I will
> > write as R(a)) having a as a foreign key into S(b) is expressed
> > as follows:
> > forall R(a): exists S(b): a = b
> Just to be sure notationally: the first colon reads
> ' it is true that ', the second ' such that it is true that ', right?

That works, although I find the "it is true that" can usually be dropped. I'd probably read it as

  for all a in R there exists a b in S such that a equals b

Something like that. With the understanding that "a in R" means "a value of the attribute named 'a' in the relvar R."

Oh, that reminds me: there might be some use to expressing "constraints" on constants! They wouldn't be runtime constraints necessarily but they might be useful because of constraint propogation through views, for example. Instead of "constraints" they would be static properties of the constants that the compiler could verify. In fact, I generally quite like the idea of having a uniform way of specifying such properties, and having it be a separate concern whether the properites are checked statically or dynamically.

> > In the context of relations with named attributes, it is not necessary
> > to declare or make up logic variable names, the way we have to when we
> > are using sets of ordered pairs. We can use the existing attribute
> > names as the names of the logic variables. However that raises the
> > question of what happens when we want to quantify over an attribute
> > more than once in a given formula. In that case let a primed attribute
> > name be considered a second instance of a logic variable quantified
> > over the attribute.
> > So if we want to say that for every row of R
> > with attribute a there exists a row of R with an unequal value
> > for attribute a, we can say:
> > forall R(a): exists R(a'): a != a'
> This looks like setting up a (unintended) trap of mixing attributes
> and attribute values.
> Why not prime the first instance^W^W^W all instances?
> forall R(a): exists R(a'), exists R(a''): a' != a''
> ?
> (saying that R has at least two rows with different
> values for a, just like above.)

I am sensitive to the concern you mention, however I think it will be okay as is. (Although I admit I am not a teacher.) Many constraints will not quantify over a given relatin more than once, for example, and they are a lot more readable without the primes. Also, it's not that different than issues one runs into with SQL. When one says

  select * from R where a > b

the "a > b" part is using attribute names as variables in an expression that is evaluated for every tuple in the relation.

> > What about candidate keys? Suppose we have a relation R with
> ... only the ...
> > *sets* of attributes A and B: R{A, B}.

I debated whether to make that specific or not. Yes, the two are only equivalent if all attributes of R are in A union B.

My intent is to express that with R{A, B}.

> > [...]
> Very nice :-)

Yeah, aren't those cute?

Marshall Received on Sat Feb 24 2007 - 17:41:27 CET

Original text of this message