Re: Character string relation and functional dependencies

From: Tegiri Nenashi <>
Date: Mon, 10 Dec 2007 10:59:40 -0800 (PST)
Message-ID: <>

On Dec 8, 8:05 pm, "V.J. Kumar" <> wrote:
> Tegiri Nenashi <> wrote
> > On Dec 6, 2:38 pm, Jonathan Leffler <> wrote:
> >> Tegiri Nenashi wrote:
> >> > On Dec 6, 9:40 am, (rpost) wrote:
> >> >> Another difference is that database tables are finite and
> >> >> variable,
> >> > Oh, relations in database world are certainly not restricted by
> >> > finite cardinality.
> >> I thought that computers are finite, so the relations containable in
> >> them are too - even if damn large. There's a big difference between
> >> very large and infinite.
> > This doesn't really matter. You can still reason about infinite
> > relations
> You can do that with your brain...
> with finite resources available on you computer platform.
> but not with that. The computer is an intrinsically finite gadget.
> Therefore, you'd better use the finite model apparatus to reason about
> things like the impossibility of expessing transitive closure in the
> relational algebra. A lot of stuff like the compactness theorem does
> not work with finite models which makes infinite model proofs
> inapplicable in the finite case.

Let's make a discussion al little bit more specific. Consider language recognition problem: given a word (that is a string of symbols) and a grammar, check if the word generated by the grammar. A naive evaluation would simply start by generating all the words of a (potentially infinite) langauge generated by the grammar, and stops as soon the given word is derived.

Likewise, given a query which involves infinite relations we can have multiple execution strategies, some of them are not terminating. For example, a join of the finite relation


with infinite relation


has two alternative executions. We can start enumerating all the tuples in the infinite relation x=y (assuming a countable domain)....

... and will never finish.

However, if we start with the finite relation x=1, the we can fetch all the matching tuples from x=y by "the index lookup". Received on Mon Dec 10 2007 - 19:59:40 CET

Original text of this message