Re: RA with MV attributes

Jon Heggland wrote:
> David wrote:
> > Example
> >
> > r1(Names,Cars)
> > bill, car1,car2,car4
> > john,fred car3
> >
> > r2(Cars,Colours)
> > car1,car3,car4 red
> > car2 green
> >
> > r1 |X| r2 (Names,Cars,Colours)
> > bill car1,car4 red
> > bill car2 green
> > john,fred car3 red
> > john,fred green
> >
> > [...]
> > For example the
> > last tuple of r1 |X| r2 above doesn't imply that John and Fred
> > don't own any cars.
>
> So what exactly does that last tuple mean?

It would appear that this tuple only states that John and Fred exist and the colour Green exists. This information is redundant with respect to the other tuples.

I don't even think the tuple should be regarded as implying John and Fred don't have any green cars. I would avoid using individual tuples to infer that a relationship doesn't exist in other tuples. I would say tuples can only add relationships, never remove them.

A challenge for the MV approach is to support updates effectively. In the general case it is far from clear how to properly assert new relationships or retract existing relationships. If we can define r1 union r2 effectively (and remove redundancy) then we have a basis of adding new relationships to an existing relation. Similarly defining r1 \ r2 properly provides a basis for retracting relationships.

Eg, consider that we have the tuple

r1(Names,Cars)

     bill,mary,fred car1,car2,car3,car4

and we want to retract the fact that mary owns car3. Therefore define

r2(Names,Cars)

     mary	                  car3

We want to calculate

r1\r2(Names,Cars)

     bill,fred    	                  car1,car2,car3,car4
     mary                             car1,car2,car4

Evidently after confirming that r1,r2 are union compatible we conceptually iterate over the tuples in r1 and find the tuples from r2 that intersect it. This may cause a tuple from r1 to be split into a number of pieces. A piece may split multiple times because of multiple intersecting tuples from r2. It would be interesting to turn this idea into a practical algorithm.

A more practical approach may be to require that every relation have a primary key and only support non-primary key MV attributes. I presume this would simplify the implementation of a relational algebra somewhat. Received on Wed Jan 17 2007 - 10:23:00 CET