Re: Character string relation and functional dependencies

From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Thu, 13 Dec 2007 02:17:56 +0100 (CET)
Message-ID: <Xns9A04CE94FFA46vdghher@194.177.96.26>

Tegiri Nenashi <TegiriNenashi_at_gmail.com> wrote in news:d786d9a9-b015-44e9-82b2-577a9790971f_at_e25g2000prg.googlegroups.com:

> On Dec 11, 1:47 pm, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:

>> On Dec 11, 1:27 pm, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>>
>>
>>
>>
>>
>> > Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote in
>> > news:38860a21-e69a- 
>> > 46a4-a798-cc16dde1c..._at_e10g2000prf.googlegroups.com: 
>>
>> > > On Dec 11, 12:37 pm, Tegiri Nenashi <TegiriNena..._at_gmail.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?

He does not ! All you do is just substitute relation definitions for the 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.

>
>
>
>
Received on Wed Dec 12 2007 - 19:17:56 CST