[Mulgara-dev] Re: Bug list and versions

[Andrae Muys]

On 14/11/2006, at 3:04 PM, Life is hard, and then you die wrote:

> On Tue, Nov 14, 2006 at 10:48:48AM +1000, Andrae Muys wrote:
>> On 14/11/2006, at 9:51 AM, Life is hard, and then you die wrote:
> Thanks for the detailed explanation. I tend to think in in terms of
> sets of tuples, hence my interpretation. The 'A or C' then becomes the
> union of an inverse-projection
>
>     -----        -----
>     pr_ab(A)  u  pr_ac(C)
>
> (where pr_ab is the projection from {(a,b,c)} to {(a,b)}), i.e. the
> DONTCARE's are all possible values. But like you say, the two views
> are (or should be) isomorphic.

That's a good way to think about it, and is almost equivalent to  
tuples as "sets of variable binding sets".  You will however find it  
easier if you avoid thinking in terms of projection down.  Rather A  
and C have variable-sets {a,b} and {a,c} respectively and the natural  
join of A and B have the variable-set vars(A) U vars(b)  (where vars  
is a functor from tuples to variable-set).

Another approach to the tuples algebra that I find particularly  
useful on occasion is as the untyped-relational-algebra[0].  So in  
this case, where a typed-relation consists of an attribute-set of  
(name,type) pairs, and a set of tuples.  The untyped-relation  
consists of an attribute-set of name's, and a set of tuples.  In the  
absence of NUC-disjunction, this is isomorphic to the typed- 
relational algebra, and therefore we get alot of semantics for free.

In the presence of NUC-disjunction we have to introduce  
'unconditionally true' as a value (which as you correctly point out,  
can be thought of as 'matching all possible values').

In the presence of Optional we have to introduce the 'unconditionally  
false value.

We can recover our algebra using the following four identities:

UNCON-FALSE and a === UNCON-FALSE    UNCON-TRUE and a === a
UNCON-FALSE or  a === a              UNCON-TRUE or  a === UNCON-TRUE

Which means that when generating a canonical Sum-of-Products form for  
a tuples

UNCON-FALSE eliminate the product-term
UNCON-TRUE eliminates all other product-terms that match the non- 
UNCON-TRUE attributes in the term.

We get to take this shortcut as long as we remember that the  
underlying semantics are defined in terms of a strict SoP proposition  
within FOL.

We currently support UNCON-TRUE, and call it UNBOUND; we don't  
currently support optional[1], therefore don't support UNCON-FALSE.

Andrae Muys

[0] It is worth noting that the tuples-algebra is a semi-ring, with  
[^,({},{{}})] as the multiplicative monoid, and [v,({},{})] as the  
additive monoid.

[1] Note that I don't believe we need to support optional as  
subqueries are a superior mechanism.

-- 
Andrae Muys
andrae at netymon.com
Principal Mulgara Consultant
Netymon Pty Ltd