# Re: Character string relation and functional dependencies

Date: Tue, 11 Dec 2007 06:57:43 -0800 (PST)

Message-ID: <267aa480-de9c-4bd2-ac9b-936169eaa848_at_e6g2000prf.googlegroups.com>

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