# Re: atomic

Date: Mon, 05 Nov 2007 22:45:52 -0800

Message-ID: <1194331552.438207.272970_at_q3g2000prf.googlegroups.com>

On Nov 6, 1:52 am, paul c <toledobythe..._at_ooyah.ac> 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.

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...

Intersection

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).

Union

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.

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".

Difference

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