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