# 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_at_194.177.96.26>

> Let's make a discussion al little bit more specific. Consider language

Date: Tue, 11 Dec 2007 15:08:34 +0100 (CET)

Message-ID: <Xns9A035D17BBDAAvdghher_at_194.177.96.26>

> 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 - 15:08:34 CET