 | |
Character string relation and functional dependencies
comp.databases.theory comp.databases.theory
 |
| | Thread Tools | Display Modes |
#21
 
| |||
| |||
|
Re: Character string relation and functional dependencies -
12-11-2007
, 12:20 PM
|
The formulas look very cute, no doubt about that, but immediate questions are: how do you propose to index infinite relations ? |
R(x,y) is a function. Given x=1 an index function returns all the
"matching" tuples, or a single tuple if there is a functional
dependency x->y. For an equality relation x=y this function is
identity: given x, return x.
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 ? |
no way to apply the ideas of pipelined execution flow there. Also, as
Marshal noted, it is perfectly allright for an intermediatory query
evaluation result to be infinite; it is the final result where a user
is expected to see the finite set.
#22
| |||
| |||
|
|
On Dec 11, 6:08 am, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: The formulas look very cute, no doubt about that, but immediate questions are: how do you propose to index infinite relations ? First, let's establish the idea that an index for a finite relation R(x,y) is a function. |
primitive, deus ex machina as it were, then in many cases you do not
need any of the finitely definable infinite relation apparatus. SQL
already has built-in or user-defined functions that make possible
evaluating queries over a finite tuple domain with embedded infinitary
structures. You need to try and express query evaluation in your model
with relations only -- that's the whole point !
Quote:
|
Given x=1 an index function returns all the "matching" tuples, or a single tuple if there is a functional dependency x->y. For an equality relation x=y this function is identity: given x, return x. 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 ? Well, let's not get into incountable domains, because there appeared no way to apply the ideas of pipelined execution flow there. |
case is what might actually motivate your research, as in the spacial-
temporal database area. The countable case by itself is not very
interesting especially if the user "is expected to see the finite set".
If you admit first-order formulas ("extended tuples") as a legitimate
query evaluation result, then your ideas coincide with Kanellakis's ideas
wrt constraint databases, a tree that has yet to bear practically usable
fruits !
Quote:
|
Also, as Marshal noted, it is perfectly allright for an intermediatory query evaluation result to be infinite; it is the final result where a user is expected to see the finite set. |
#23
| |||
| |||
|
|
Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote innews:f7283774-a81f-417a-9942-ca25012ff6d3 (AT) i29g2000prf (DOT) googlegroups.com: On Dec 11, 6:08 am, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: The formulas look very cute, no doubt about that, but immediate questions are: how do you propose to index infinite relations ? First, let's establish the idea that an index for a finite relation R(x,y) is a function. First of all, if you introduce the arbitrary function as an additional primitive, deus ex machina as it were, then in many cases you do not need any of the finitely definable infinite relation apparatus. SQL already has built-in or user-defined functions that make possible evaluating queries over a finite tuple domain with embedded infinitary structures. You need to try and express query evaluation in your model with relations only -- that's the whole point ! |
Likewise, I would like to keep functions hidden. After all there is
one relation
x + y = z
but there are three functions that can index it.
Anyway, this whole sub thread is a digression off the initial thought
about connection between objects and relations on one hand, and object
methods and functional dependencies on the other. I'm surprised nobody
objected the idea (pun intended) that object corresponds to the
relation, and not relation attribute.
In a word, are computers finite machines? Yes. Does it necessarily
restrict relations (and other structures) to be be finite ones? Not
necessarily. I suggest to close this rather unsophisticated
discussion.
#24
| |||
| |||
|
|
Well, in traditional databases index structures are auxiliary. Likewise, I would like to keep functions hidden. After all there is one relation x + y = z but there are three functions that can index it. |
query
x + y = z /\ x=1 /\ z=4
there is no functions there. As usual optimizer engine starts
enumerating and costing every join permutation. It would find out that
the execution below has a finite cost:
1. Evaluate x=1
2. Evaluate z=4
3. Build a Cartesian product result
4. Join with the relation x + y = z using the index (x,z)->z-x
#25
| |||
| |||
|
|
Anyway, this whole sub thread is a digression off the initial thought about connection between objects and relations on one hand, and object methods and functional dependencies on the other. I'm surprised nobody objected the idea (pun intended) that object corresponds to the relation, and not relation attribute. |
vaguely formulated. Yes, objects in some sense could be and have been
treated as relations, and vice versa, so what ? Some commercial SQL
databases even have both implementations, 'objects as relations' and
'objects as attributes'. Until and unless you define some sort of object
algebra and compare its features with the relational algebra or some
other algebra of relations, there is nothing to argue about !
Quote:
|
In a word, are computers finite machines? Yes. Does it necessarily restrict relations (and other structures) to be be finite ones? Not necessarily. I suggest to close this rather unsophisticated discussion. |
#26
| |||
| |||
|
|
On Dec 11, 12:37 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: Well, in traditional databases index structures are auxiliary. Likewise, I would like to keep functions hidden. After all there is one relation x + y = z but there are three functions that can index it. Let me elaborate a little more. Suppose we are asked to evaluate the query x + y = z /\ x=1 /\ z=4 there is no functions there. As usual optimizer engine starts enumerating and costing every join permutation. It would find out that the execution below has a finite cost: 1. Evaluate x=1 2. Evaluate z=4 3. Build a Cartesian product result 4. Join with the relation x + y = z using the index (x,z)->z-x |
x^2 + y^2 + z^2 =u^2 /\ u=25
?
#27
| |||
| |||
|
|
Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote in news:38860a21-e69a- 46a4-a798-cc16dde1c... (AT) e10g2000prf (DOT) googlegroups.com: On Dec 11, 12:37 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: Well, in traditional databases index structures are auxiliary. Likewise, I would like to keep functions hidden. After all there is one relation x + y = z but there are three functions that can index it. Let me elaborate a little more. Suppose we are asked to evaluate the query x + y = z /\ x=1 /\ z=4 there is no functions there. As usual optimizer engine starts enumerating and costing every join permutation. It would find out that the execution below has a finite cost: 1. Evaluate x=1 2. Evaluate z=4 3. Build a Cartesian product result 4. Join with the relation x + y = z using the index (x,z)->z-x What would your optimizer do in the following case: x^2 + y^2 + z^2 =u^2 /\ u=25 |
administrator creates them, even though the task is rather trivial.
(Remember, that long time ago DBMS were conceived to do it
automatically:-). The case of infinite relations is much more
challenging, therefore I expect a database programmer (or should I
better call him "relational programmer") to code the index function
*manually* and register each index with the corresponding relation.
#28
| |||
| |||
|
|
On Dec 11, 1:27 pm, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote in news:38860a21-e69a- 46a4-a798-cc16dde1c... (AT) e10g2000prf (DOT) googlegroups.com: On Dec 11, 12:37 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: Well, in traditional databases index structures are auxiliary. Likewise, I would like to keep functions hidden. After all there is one relation x + y = z but there are three functions that can index it. Let me elaborate a little more. Suppose we are asked to evaluate the query x + y = z /\ x=1 /\ z=4 there is no functions there. As usual optimizer engine starts enumerating and costing every join permutation. It would find out that the execution below has a finite cost: 1. Evaluate x=1 2. Evaluate z=4 3. Build a Cartesian product result 4. Join with the relation x + y = z using the index (x,z)->z-x What would your optimizer do in the following case: x^2 + y^2 + z^2 =u^2 /\ u=25 Well how indexes are created in the off-the-shelf databases? DB administrator creates them, even though the task is rather trivial. (Remember, that long time ago DBMS were conceived to do it automatically:-). The case of infinite relations is much more challenging, therefore I expect a database programmer (or should I better call him "relational programmer") to code the index function *manually* and register each index with the corresponding relation.- Hide quoted text - |
problematic whether more general problems fit into the system R
optimization method. For example given a system of equations:
x + y = 2
x - y = 0
the solution is
(x+y=z) /\ (z=2) /\ (x=y)
Assuming that we have 3 indexes on the first relation:
x,y -> z
x,z -> y
y,z -> x
and two indexes on the last one
x -> y
y -> x
we still can't evaluate this query. BTW, how Kanellakis solves it?
#29
| |||
| |||
|
|
On Dec 11, 1:47 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote: On Dec 11, 1:27 pm, "V.J. Kumar" <vjkm... (AT) gmail (DOT) com> wrote: Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote in news:38860a21-e69a- 46a4-a798-cc16dde1c... (AT) e10g2000prf (DOT) googlegroups.com: On Dec 11, 12:37 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com wrote: Well, in traditional databases index structures are auxiliary. Likewise, I would like to keep functions hidden. After all there is one relation x + y = z but there are three functions that can index it. Let me elaborate a little more. Suppose we are asked to evaluate the query x + y = z /\ x=1 /\ z=4 there is no functions there. As usual optimizer engine starts enumerating and costing every join permutation. It would find out that the execution below has a finite cost: 1. Evaluate x=1 2. Evaluate z=4 3. Build a Cartesian product result 4. Join with the relation x + y = z using the index (x,z)->z-x What would your optimizer do in the following case: x^2 + y^2 + z^2 =u^2 /\ u=25 Well how indexes are created in the off-the-shelf databases? DB administrator creates them, even though the task is rather trivial. (Remember, that long time ago DBMS were conceived to do it automatically:-). The case of infinite relations is much more challenging, therefore I expect a database programmer (or should I better call him "relational programmer") to code the index function *manually* and register each index with the corresponding relation.- Hide quoted text - The problem is, of course, identifiying the indexes. And it may be problematic whether more general problems fit into the system R optimization method. For example given a system of equations: x + y = 2 x - y = 0 the solution is (x+y=z) /\ (z=2) /\ (x=y) Assuming that we have 3 indexes on the first relation: x,y -> z x,z -> y y,z -> x and two indexes on the last one x -> y y -> x we still can't evaluate this query. BTW, how Kanellakis solves it? |
query placeholder variables. You always work with formulas representing
possibly infinite relations, you do not 'materialize' down to the actual
tuples; in finite cases such materialization clearly happens
automatically since any finite relation is representable with the
equality predicate and constants.
Quote:
| |
|
« 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.