Re: atomic

On Nov 6, 3:45 pm, David BL <davi..._at_iinet.net.au> wrote:
>
> 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.

This isn't quite right. Instead the definition should be

    t1 <= t2 if both the following

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

        for each attrib a in (attribs(t1) \ attribs(t2)),
            t1(a) = {}

> 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

It seems more useful to define a project/extend operator in one step...

Projection

Definition: Let X be any set of attributes and t be an mv-tuple. Let t' = project(t,X)
represent the projection of t onto X where t' is an mv-tuple satisfying

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

Definition: Let X be any set of attributes and r be an mv-relation. Let r' = project(r,X) where r' is an mv-relation satisfying

    attribs(r') = X
    tuples(r') = { project(t,X) | t in tuples(r) }

It should be possible to prove the following

    t => project(t,X)
    if attribs(t) is a subset of X then project(t,X) <=> t

Information comparisons between mv-relations

Definition: Let r1,r2 be mv-relations. we write r2 => r1 (or equivalently r1 <= r2) if

    I(r1) is a subset of I( project(r2, attribs(r1) )

Definition. We say r1,r2 are information equivalent (written r1 <=> r2) if r1 => r2 and r2 => r1.

I think it would be possible to show that (r1 intersect r2) is uniquely characterised (up to information equivalence) as the largest amount of information consistent with

    r1 => (r1 intersect r2) and
    r2 => (r1 intersect r2)

ie there is no mv-relation r satisfying

    r1 => r and
    r2 => r and
    not ( (r1 intersect r2) => r )

There is a corresponding characterisation of (r1 union r2). Received on Wed Nov 07 2007 - 02:21:27 CET