Re: Character string relation and functional dependencies

From: David Cressey <cressey73_at_verizon.net>
Date: Tue, 11 Dec 2007 16:50:48 GMT
Message-ID: <Idz7j.3196$R4.1264_at_trndny05>


"V.J. Kumar" <vjkmail_at_gmail.com> wrote in message news:Xns9A035D17BBDAAvdghher_at_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 ?

With an infinite index, of course. Received on Tue Dec 11 2007 - 17:50:48 CET

Original text of this message