 | |
Character string relation and functional dependencies
comp.databases.theory comp.databases.theory
 |
| | Thread Tools | Display Modes |
#11
 
| |||
| |||
|
Re: Character string relation and functional dependencies -
12-09-2007
, 03:38 AM
|
There's a big difference between very large and infinite. |
In practical terms, there is nearly no difference
between a few hundred bits of precision and an infinite
number of bits of precision. Twenty three digits of pi
is sufficient to calculate the circumference of the Milky
Way from the diameter to within a centimeter.
Marshall
#12
| |||
| |||
|
|
On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 with finite resources available on you computer platform. |
http://cse.unl.edu/~revesz/cdb/index.htm
-- Jan Hidders
#13
| |||
| |||
|
|
On 7 dec, 01:24, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 with finite resources available on you computer platform. Indeed you can. In case anyone is interested in a concrete example: http://cse.unl.edu/~revesz/cdb/index.htm |
Marshall
#14
| |||
| |||
|
|
On 7 dec, 01:24, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 with finite resources available on you computer platform. Indeed you can. In case anyone is interested in a concrete example: |
link refers to works with a finite set of first-order formulas ("extended
tuples") that permit quantifier elimination rather than with a finite set
of actual tuples as the relational model would. It is a simple
observation that a first-order formula under certain conditions can
"represent" a possibly infinite set. However, formula-set
interpretation happens in the user brain only, not in the database
itself as would be the case with the traditional relational model which
probably explains along with other problems why constraint databases do
not enjoy much success.
Quote:
|
http://cse.unl.edu/~revesz/cdb/index.htm -- Jan Hidders |
#15
| |||
| |||
|
|
On Dec 9, 4:47 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote: On 7 dec, 01:24, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 with finite resources available on you computer platform. Indeed you can. In case anyone is interested in a concrete example: http://cse.unl.edu/~revesz/cdb/index.htm Looks very interesting. I bought the intro book. |
writes very nice papers and gives good talks, so I suspect he writes
well.
-- Jan Hidders
#16
| |||
| |||
|
|
Jan Hidders <hidd... (AT) gmail (DOT) com> wrote innews:dd39930a-d971-43a1-8d13-779cd635f632 (AT) s8g2000prg (DOT) googlegroups.com: On 7 dec, 01:24, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 with finite resources available on you computer platform. Indeed you can. In case anyone is interested in a concrete example: This kind of "reasoning" is an illusion. The constraint database the link refers to works with a finite set of first-order formulas ("extended tuples") that permit quantifier elimination rather than with a finite set of actual tuples as the relational model would. It is a simple observation that a first-order formula under certain conditions can "represent" a possibly infinite set. However, formula-set interpretation happens in the user brain only, not in the database itself as would be the case with the traditional relational model [...] |
contributions to this newsgroup than this kind of quibbling. Please
don't let your ego cloud the brightness of your mind.
-- Jan Hidders
#17
| |||
| |||
|
|
Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:cd2ad8bd-78ca-433d-bc0f-3e7ef0c0fe2a (AT) e6g2000prf (DOT) googlegroups.com: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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. |
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".
#18
| |||
| |||
|
|
On Dec 8, 8:05 pm, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:cd2ad8bd-78ca-433d-bc0f-3e7ef0c0fe2a (AT) e6g2000prf (DOT) googlegroups.co m: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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". |
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 ?
#19
| |||
| |||
|
|
Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:e0e52d62-c37f-4061-ab9d-3983a5ed31ca (AT) s12g2000prg (DOT) googlegroups.com: On Dec 8, 8:05 pm, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:cd2ad8bd-78ca-433d-bc0f-3e7ef0c0fe2a (AT) e6g2000prf (DOT) googlegroups.co m: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 ? |
for y is straightforward. :-)
Quote:
|
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 ? |
Marshall
#20
| |||
| |||
|
|
Tegiri Nenashi <TegiriNenashi (AT) gmail (DOT) com> wrote in news:e0e52d62-c37f-4061-ab9d-3983a5ed31ca (AT) s12g2000prg (DOT) googlegroups.com: On Dec 8, 8:05 pm, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:cd2ad8bd-78ca-433d-bc0f-3e7ef0c0fe2a (AT) e6g2000prf (DOT) googlegroups.co m: On Dec 6, 2:38 pm, Jonathan Leffler <jleff... (AT) earthlink (DOT) net> wrote: Tegiri Nenashi wrote: On Dec 6, 9:40 am, rp... (AT) pcwin518 (DOT) 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 ? |
|
« Previous Thread
|
Next Thread »
| Thread Tools | |
| Display Modes | |
Linear Mode
| |
Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.