Re: Character string relation and functional dependencies

On Dec 11, 6:08 am, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
> Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote innews: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 ?

By formula. For the infinite relation x=y, given x, the formula for y is straightforward. :-)

> 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 ?

You leave it unevaluated until something extensional comes along.

Marshall Received on Tue Dec 11 2007 - 15:57:43 CET