Re: Character string relation and functional dependencies

From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Tue, 11 Dec 2007 15:08:34 +0100 (CET)
Message-ID: <Xns9A035D17BBDAAvdghher@194.177.96.26>

Tegiri Nenashi <TegiriNenashi_at_gmail.com> wrote in news:e0e52d62-c37f-4061-ab9d-3983a5ed31ca_at_s12g2000prg.googlegroups.com:

> 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.co
>> m: 
>>
>> > 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".

The formulas look very cute, no doubt about that, but immediate questions are:

how do you propose to index infinite relations ? what do you do when you join two infinite relations and the result is also an infinite relation: x < 5 join x > 1 where x ranges over reals ? Received on Tue Dec 11 2007 - 08:08:34 CST