Re: RA with MV attributes

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.

>

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.