# Re: Character string relation and functional dependencies

From: Tegiri Nenashi <TegiriNenashi_at_gmail.com>
Date: Mon, 10 Dec 2007 10:59:40 -0800 (PST)

On Dec 8, 8:05 pm, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>
> > On Dec 6, 2:38 pm, Jonathan Leffler <jleff..._at_earthlink.net> wrote:
> >> Tegiri Nenashi wrote:
> >> > On Dec 6, 9:40 am, rp..._at_pcwin518.campus.tue.nl (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.

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

x=1

with infinite relation

x=y

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