Re: RM formalism supporting partial information
Date: Sun, 18 Nov 2007 03:13:51 -0800 (PST)
On 17 nov, 13:30, David BL <davi..._at_iinet.net.au> wrote:
> On Nov 17, 7:54 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
> > As you already noted <=3 essentially represents your approach. You may
> > also have noticed that <=1 is Zaniolo's approach. The <=2 represents
> > the does-not-apply interpretation of null values. I strongly
> > conjecture (i.e. haven't formally verified) that <=1 and <=2 are the
> > same and <=3 is different, but ~1, ~2 and ~3 are all the same.
> I agree that ~1, ~2 and ~3 will probably all be the same.
> However I was thinking that if anything <=2 was the odd man out.
I'm glad one of us is paying attention :-). Yes, it is indeed <=1 and <=3 that are the same, and <=2 is the odd one out.
Let me be a bit more thorough this time. Recall the definitions:
- We define a binary relation <=1 over relations such that R1 <=1 R2 iff for every tuple t1 in R1 there is a tuple t2 in R2 such that t1 <= t2.
- We define a binary relation <=3 over relations such that R1 <=3 R2 iff for each relation R' in int(R1) there is a relation R" in int(R2) such that R' is a subset R".
I'll sketch a proof of their equivalence:
To see that R1 <=1 R2 implies R1 <=3 R3 consider that if R1 <=1 R2 then it holds for every set X of attribute names that NFP[X](R1) as a subset of NFP[X](R2). This can be shown as follows. Assume t in NFP[X] (R1) then there is a t1 in R1 such that dom(t1) a superset of X and t1[X] = t. Since R1 <=1 R2 there is a t2 in R2 that is a superset of t1. Since dom(t1) is a superset of X, t2[X] = t1[X] = t and dom(t2[X]) = X. It follows that t is in NFP[X](R2).
To see that R1 <=3 R2 implies R1 <=1 R2 consider the following. For each tuple t1 in R1 it holds that t1 is in R' = NFP[dom(t1)](R1). Since R1 <=3 R2 there is a set of attributes X" such that R' is a subset of R" = NFP[X"](R2). Since t1 is in R" and therefore also in R" it follows that X" = dom(t1). It follows that there is a tuple t2 in R2 such that t1 = t2[X] and so t1 <= t2.
QED So it seems your approach *is* in this respect equivalent with Zaniolo's.
- Jan Hidders