Re: RA with MV attributes

From: David <davidbl_at_iinet.net.au>
Date: 18 Jan 2007 18:50:15 -0800
Message-ID: <1169175015.812874.298080@a75g2000cwd.googlegroups.com>

Aloha Kakuikanu wrote:
> David wrote:
> > Aloha Kakuikanu wrote:
> > > Never mind. Partial order is not enough. It has to be total order.
> > >
> > > Aloha Kakuikanu wrote:
> > > > David wrote:
> > > > > Here is a partial formalization of a relational algebra based on MV
> > > > > attributes. The approach appears simple and intuitive. In particular
> > > > > the join of two relations is rather elegant.
> > > > > ...
> > > >
> > > > IMO, RA with MV attributes is quite easy to formalize. I suggest a
> > > > nested relation as a formal definition for MV attribute. A critical
> > > > step is noticing that there is a (partial) order "<" among all the
> > > > relations. Formally:
> > > >
> > > > Q < R iff Q /\ R = R
> > > >
> > > > where "/\" is a symbol for relational join. (I don't quite like the
> > > > "&&" symbol that Marshall uses:-)
> > > >
> > > > Next,
> > > >
> > > > Q = R iff Q < R and R < Q
> > > >
> > > > Now that we can compare relational valued attributes, we can define all
> > > > the RA operations. Interestingly, set joins (and relational division)
> > > > are easily expressed in this framework. For example, given
> > > >
> > > > A = { <x=1, y={<t=a>,<t=b>}> , <x=2, y={<t=b>,<t=c>} > }
> > > >
> > > > B = { <y={<t=a>} }
> > > >
> > > > Then, inequality join
> > > >
> > > > A /\_a.y<b.y B
> > > >
> > > > is the same as relational division between "flattened" A and B
> > > > relations.
> >
> > Playing around with the definition of equality can't work because you
> > can't get away from the need to *intersect* the MV attributes (rather
> > than merely test them for equality, as done in the conventional RA) in
> > order to perform a join operation.

>

> Can you please be more specific? Which kind of join do you have in
> mind? Here is case by case analysis:

>

> 1. Set equality join. Since we do have well defined equality between
> relations, natural join between relations with RVA (relationally valued
> attributes) is the same as set equality join between equivalent
> "flattened" relations.

>

> 2. Set containment join. Theta join with inequality condition is the
> same as set containment join between equivalent "flattened" relations.
> However, since relations are only partially ordered, generalization of
> theta join to relations with "attribute incompatible" RVAs doesn't
> really work.

>

> 3. Set intersection join. Theta join with non empty RVA intersection
> condition is the same as set intersection join between equivalent
> "flattened" relations. "Intersection", of course, has to be generalized
> into "join" in order to accommodate "attribute incompatible" pairs of
> RVAs. Set intersection join is also the same as natural join between
> "flattened" relations.

If I understand you I'm interested in the natural join between the "flattened" relations. This seems to relate to the third case above. Let's ignore the possibility of "attribute incompatible" pairs of RVAs.

My understanding is that a theta join involves a cross product followed by selection, where the selection criteria is determined by theta.

The theta function only involves *testing* for non-empty intersection between RVAs. This is not enough. It is necessary to *store* the RVA intersections for the shared attributes in the join result. This is described in my OP. Received on Thu Jan 18 2007 - 20:50:15 CST