Re: Relational query with path expressions

On Apr 7, 1:09 am, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
> On Apr 3, 4:31 am, David BL <davi..._at_iinet.net.au> wrote:
>
> > For example, given binary relation R(x,y), one could define a unary
> > function f that maps a set of x values to a set of y values as follows
>
> > for all X, f(X) = {y | exists x in X, R(x,y)}
>
> > It can be shown that f distributes over union and this "additive"
> > property on sets is preserved over function composition. In fact it
> > is easy to show that composition of these unary functions is
> > equivalent to a join + projection on the associated binary relations.
>
> My interpretation of this is the following. You took binary named
> relation (Codd model operates named relations), and abstracted away
> named perspective. Then, you suggest that the join between binary
> relations is defined the same way as in algebra of binary relations.
> This allows you to express graph queries.

I'm afraid I didn't follow all of that. I'll explain what I was stating in more detail...

Let R1(x,y) and R2(y,z) be two named binary relations on named attributes.

Define unary function fxy that maps sets of x's to sets of y's using R1 as follows:

    for all X, fxy(X) = {y | exists x in X, R1(x,y)}

Similarly define fyz that maps sets of y's to sets of z's using R2

    for all Y, fyz(Y) = {z | exists y in Y, R2(y,z)}

Let R3(x,z) be the join of R1,R2 on y, projected onto {x,z}. Let fxz be derived from R3 as follows:

    for all X, fxz(X) = {z | exists x in X, R3(x,z)}

Then it turns out that fxz = fyz o fxy

This justifies the use of these unary functions to express certain queries, and a functional notation can be simple and intuitive. However there are serious limitations with the approach - due to the fact that

1. there is often more than one useful binary relation between a given pair of attributes; and
2. relations aren't generally decomposable into binary relations in the sense of a JD.

    for all X, f1(X) = {y | exists x in X, R(x,y)}
    for all Y, f2(Y) = {x | exists y in Y, R(x,y)}
    for all X, f3(X) = {y | for all x in X, R(x,y)}
    for all Y, f4(Y) = {x | for all y in Y, R(x,y)}

f1,f2 distribute over union (giving them an additive characteristic) whereas f3,f4 distribute over intersection (giving them a subtractive characteristic).

Each one of these preserves all the information in R:

    R(x,y) = { (x,y) |  y in f1({x}) }
           = { (x,y) |  x in f2({y}) }
           = { (x,y) |  y in f3({x}) }
           = { (x,y) |  x in f4({y}) }

    R1*R2 = { (y,z) in R2 | (x,y') in R1 => (y',z) in R2 }

That would allow for the path expression

    P*SP.S.S#

which finds supplier numbers of suppliers that ships /all/ the parts.

The following is interesting:

    P[COLOR='red']*SP.P#

This finds part numbers for any parts shipped by any supplier that ships all the red parts. This may include parts that are not red. Received on Tue Apr 07 2009 - 06:06:18 CEST