Re: RA with MV attributes

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. Received on Thu Jan 18 2007 - 14:57:29 CST