Re: RM formalism supporting partial information

On 16 nov, 02:51, David BL <davi..._at_iinet.net.au> wrote:
> On Nov 16, 8:31 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> > On 15 nov, 20:11, David BL <davi..._at_iinet.net.au> wrote:
>
> > > I'm sure your time is precious and I don't want to be presumptuous,
> > > but have you digested much of the document? Do you have any
> > > particular comments on the operators, such as the information
> > > comparison operator which gives a partial ordering and a concept of
> > > information equivalence?
>
> > It's actually not a partial order, but a preorder because it is not
> > antisymmetric.
>
> I didn't know partial order had that more specific meaning. Nor did I
> know that the term preorder was available for what I wanted to say.
> Thanks for pointing that out.

The term pseudo order is also sometimes used.

> > It's also a bit strange in that it says that the
> > following relation bodies (for simplicity the tuples are unlabeled)
> > all have the same information:
> > - { }
> > - { ({}, {}) }
> > - { ({a}, {}) }
> > - { ({}, {b}) }
>
> I don't think that's correct.

Indeed, my apologies, you are right. A case of "reading what I think it should say", I'm afraid. :-)

> Intuitively the information content can be regarded as the set of all
> conventional propositions that can be "read out" of the mv-relation,
> for all possible projections.

Aha! Now *that* makes more sense, and as far as I can tell that is roughly the "value does not apply" interpretation of null values. But I'm not really convinced that the equivalence relationship over relations that you derive from that really follows from it. I'd strongly advice you to read the following paper, "Database Relations with Null values" by Carlo Zaniolo, which starts more or less from the same principle, but works it out in a subtly different way:

http://citeseer.ist.psu.edu/534211.html

Let me give a brief summary of what he does to explain what my problem is. I'll give a formal but simplified version of what he does:

• We postulate the sets A (attribute names) and D (domain values)
• A *tuple* is a partial function from A to D, i.e., a subset t of AxD such that if (a1,d1) and (a1,d2) in t, then d1=2. An attribute name for which a tuple is not defined is informally assumed to represent a null value.
• We define an ordering <= over tuples such that t1 <= t2 iff t1 is a subset of t2. Intuitively t1 <= t2 means that t2 contains more information.
• Given a subset X of A the *restriction* of a tuple t to X, denoted as t[X], is defined as the partial function { (a,d) in t | a in X }
• The *domain* of tuple t, denoted as dom(t), is the subset of A for which t is defined
• A *relation* is a set of tuples
• 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 say that two relations R1 and R2 are *1-equivalent*, denoted as R1 ~1 R2, if R1 <=1 R2 and R2 <=1 R1

Do you see how this is similar but different from what you are doing? Let me try to make this link a bit more explicit.

• Given a relation R and a subset X of A we define the *null-free projection* of R on X, denoted as NFP[X](R), such that NFP[X](R) = { t[X] | t in R, dom(t[X])=X }.
• The *interpretation* of a relation R, denoted as int(R), is defined such that int(R) = { NFP[X](R) | X is a subset of A }.

I can now define an ordering based on this in two ways:

• We define a binary relation <=2 over relations such that R1 <=2 R2 iff int(R1) is a subset of int(R2)
• 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".
• As before we can use <=2 and <=3 to define the equivalence relations ~2 and ~3.

I'm running a bit out of time now, so I'm closing with the relevant questions:
- What is the relationship between the three equivalence relationships?
- Which corresponds to yours, and which to Zaniolo's? - Which is more intuitive?

To give a hint about my opinion on the final question. If you assume the closed world assumption, and we usually do in this context, then it is not true that a smaller relation necessarily contains less information. The absence of tuples then also carries information.

So far for now.

• Jan Hidders