Re: Relational query with path expressions

On Apr 3, 5:34 pm, cim..._at_hotmail.com wrote:
> <<the user only has to specify the start and end attributes and the
> DBMS is able to deduce the joins that are required>>

> There is no such thing as a *start and end* attribute in a relation.

I meant that the user specifies a "start attribute", and an "end attribute" and supposing there is a Universal Relation there would be a projection on those two attributes which is a binary relation connecting them. This means it's possible to define a unary function that maps sets of the "start attribute" to sets of the "end attribute".

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.

Of course, n-ary relations aren't generally decomposable to binary relations (in the sense of a JD) so this simplistic idea of composing unary functions cannot express many useful queries. In other words, path expressions that only try to navigate from attribute to attribute would be quite limiting.

That being said there are cases where the approach could be quite useful. For example, let x.f denote the application of unary function f to x, and let there be a many to many binary relation between parent and child, and we define corresponding parent and child unary functions.

We can use these functions to construct queries. For example, for any X we define:

        X.grandparent = X.parent.parent

or just

        grandparent = parent.parent

where the dot now denotes function composition rather than function application. The definition of the grandparent relation would conventionally require a self-join on the binary parent-child relation.

As another example, we could define a sibling function as follows

        X.sibling = X.parent.child \ X

where we have used a set difference operator to ensure a person is never regarded as his or her own sibling.

The sibling function helps us define the cousin function:

        X.cousin = X.parent.sibling.child

etc Received on Fri Apr 03 2009 - 13:31:13 CEST