Re: atomic

From: David BL <>
Date: Mon, 05 Nov 2007 22:45:52 -0800
Message-ID: <>

On Nov 6, 1:52 am, paul c <> wrote:
> David BL wrote:
> ...
> >> Not to say D&D's basic definitions are the only ones that can
> >> be used, but I think we'd have to have agreement on how the operators
> >> apply. For example, if I understand D&D, r1 |x| r2 above would be empty.
> > Consider that we have a function I (an "interpretation") that maps a
> > relation with MV attributes to an "equivalent" relation with SV
> > attributes. Formally this simply takes cross products. For example,
> > in the above example I(r1) is
> > Name Car
> > --------------------------
> > bill car1
> > bill car2
> > bill car4
> > john car3
> > fred car3
> > and I(r2) is
> > Car Colour
> > --------------------------
> > car1 red
> > car3 red
> > car4 red
> > car2 green
> > I think it is straightforward to prove the following in the general
> > case
> > I(r1 |x| r2) = I(r1) |x| I(r2)
> > where |x| on the LHS is the join operator on relations with MV
> > attributes, and |x| on the RHS is the conventional inner join on
> > relations with SV attributes.
> > ...
> Are you suggesting cross product as an additional fundamental operator?

Oops. That was silly. I should have said cartesian product.

> If we're instead talking about cartesian product, I take it that r1
> could be written like this:
> Name Car
> ----------- ------------
> {bill} {car1,car2,car4}
> {john,fred} {car3}
> and r2 like this:
> Car Colour
> ---------------- ---------
> {car1,car3,car4} {red}
> {car2} {green}
> if those make sense, by the D&D definition of "cartesian product", I
> think r1 |x| r2 would be empty and I presume so would I(r1 |x| r2).

I was treating mv-relations as formally different from sv-relations. D&D's definitions only apply to sv-relations.

The interpretation I() maps an mv-relation to an sv-relation. For each mv-tuple, we take the cartesian product of the sets of values for each attribute to yield a set of corresponding sv-tuples.

Definition: Let r' = I(r). Then

    attribs(r') = attribs(r)
    tuples(r') =

        { t' |  exists t in r and
                for all a in attribs(r), t'(a) is an element of t(a)

If r1,r2 are sv-relations then the attributes map to single values which are sets, and then I agree that r1 |x| r2 would be empty.

If r1,r2 are mv-relations then the attributes map to multiple values which are again represented using sets. However mv-relations have different semantics, a different join operator and r1 |x| r2 is not empty.

On another note, I've been thinking of an interesting partial ordering on mv-tuples that is associated with information redundancy :

    t1 <= t2 if

        attribs(t1) is a subset of attribs(t2)  and
        for each attrib a in attribs(t1),  t1(a) is a subset of t2(a)

t1 <= t2 means that t1 is (information) redundant with respect to t2.

It seems to me that missing values should be treated merely as fewer propositions in the context of a 2vl.

This provides a clue for how to define intersection, union and difference operators on mv-relations.

I'm thinking of the following...


Let t1,t2 be mv-tuples. Then t = (t1 intersect t2) is defined as follows

    attribs(t) = (attribs(t1) intersect attribs(t2))     for each a in attribs(t), t(a) = ( t1(a) intersect t2(a) )

This can be regarded as the largest amount of information consistent with

    t1 => (t1 intersect t2) and
    t2 => (t1 intersect t2)

Now an mv-relation is a union of mv-tuples, and evidently the union of all the information expressed by the mv-tuples. By the distributive laws (on union and intersection) it makes sense to define

    r1 intersect r2 = { t1 intersect t2 | t1 in r1 and t2 in r2 }

I think it should be possible to prove

    I(r1 intersect r2) = I(r1) intersect I(r2).


Let t1,t2 be mv-tuples. (t1 union t2) could be defined as the smallest amount of information consistent with

    (t1 union t2) => t1 and
    (t1 union t2) => t2

However that won't in general be reducible to a single tuple, so the analogy with the intersection case breaks down.

Definition: Let attribs(t) be a subset of X. Let t' = extend(t,X) represent the extension of t onto X by defining

for all a in attribs(t), t'(a) = t(a)
for all a in X\attribs(t), t'(a) = {}

Note that extending a tuple with empty sets doesn't change the information content. More formally

    extend(t,X) <=> t

Definition: r = r1 union r2 satisfies

    attribs(r) = attribs(r1) union attribs(r2)     tuples(r) =

        { extend(t1,attribs(r)) | t1 in r1 } union
        { extend(t2,attribs(r)) | t2 in r2 }

I think it should be possible to prove

    I(r1 union r2) = I(r1) union I(r2).

Note the nice feature that this union operator is defined on all mvrelations

  • ie r1,r2 don't need to be "union compatible".


The analogy with intersection doesn't carry over for a simple definition of r1\r2 in terms of t1\t2. I'm not surprised that it gets more complex here because negation in the presence of missing information is tricky! I think it should relate back to the idea of "negation as failure" in Prolog.

Very informally,

    r1 \ r2 =  (union(t1 in r1) t1) \ (union(t2 in r2) t2)
            =  intersection(t2 in r2) ( (union(t1 in r1) t1) \ t2 )
            =  intersection(t2 in r2) union(t1 in r1) (t1 \ t2)
            =  intersection(t2 in r2) union(t1 in r1) (t1 and not t2)

At the moment I don't have much idea how difference should be defined. It's possible that it's only meaningful on sv-relations, in which case it forces one to make an interpretation. Received on Tue Nov 06 2007 - 07:45:52 CET

Original text of this message