RA with MV attributes

From: David <davidbl_at_iinet.net.au>
Date: 16 Jan 2007 00:40:09 -0800
Message-ID: <1168936809.048431.190520@38g2000cwa.googlegroups.com>

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.

Definition: An attribute a consists of an attribute-name N(a) and a domain-name D(a).

Definition: A relation-type is a set of attributes. The attribute names must all be unique.

Definition: A relation r consists of a relation-type A(r) together with a set of tuples T(r), where each tuple is a map from each attribute a inA(r) to a subset of D(a).

Definition: Let r be a relation and B be a subset of A(r). Then proj(r,B) is a relation r’ where A(r’) = B, and for each t’ in T(r’), t’ is the restriction of t on B.

Definition: Let r1,r2 be relations that are join compatible (ie where any attributes of the same name also have the same domain). We define the join r = r1 |X| r2 as follows.

    A(r) = (A(r1) union A(r2))

    T(r) =
    { t |

         there exists t1 in T(r1) &
         there exists t2 in T(r2) &
         for each a in A(r1) \ A(r2),  t(a) = t1(a)  &
         for each a in A(r2) \ A(r1),  t(a) = t2(a)  &
         for each a in (A(r1) intersect A(r2)), t(a) = (t1(a) intersect

t2(a))

    }

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

This is actually an outer join. An inner join requires removal of tuples with empty intersections on the common attributes.

Some advantages of MV attributes

1. Avoids redundancy. This could be significant – say when there are a large number of people that co-own a large number of cars.
2. It deals rather elegantly with missing information.

and some significant disadvantages

1. Each tuple only represents a *lower bound* on the known relationships. Therefore it is important to avoid making assumptions about what is not true when looking at a given tuple. For example the last tuple of r1 |X| r2 above doesn’t imply that John and Fred don’t own any cars.
2. The simple relationship back to propositions and FOPL is lost. Perhaps the meaning of a relation could be understood in terms of underlying 6NF predicates.
3. There is a non-uniqueness of representation because tuples can group values in different ways yet achieve the same set-theoretic result.

In the end I’m not sure whether MV attributes are a good idea or not. Received on Tue Jan 16 2007 - 02:40:09 CST