Re: Character string relation and functional dependencies

On Dec 8, 8:05 pm, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
> Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote innews:cd2ad8bd-78ca-433d-bc0f-3e7ef0c0fe2a_at_e6g2000prf.googlegroups.com:
>
> > 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.

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

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