[Mulgara-dev] No such variable

Andrae Muys andrae at netymon.com
Sat May 3 09:33:54 UTC 2008


On 03/05/2008, at 4:50 AM, David Moll wrote:
> I have several questions - I'm not certain how helpful they are to the
> discussion at hand as they are more for my own elucidation.

No Problem.

>> Actually we only agonized over disjunctions until Simon managed to
>> identify the isomorphism with FoL.
>
> What is FoL, and what is the isomorphism?  Am I correct in assuming it
> is an isomorphism between the abelian semiring that describes TQL and
> FoL?

First Order Logic.  Actually I overstate the relationship as the  
isomorphism isn't with full FoL with respect to which it is strictly  
speaking a monomorphism. Still the mapping is total to the subset of  
FoL that excludes Universal Quantification and Negation; hence an  
isomorphism, and yes this is with TQL's underlying algebra.

>> 2. UNBOUND is not a value; which immediately solved the type-
>> theoretic problems that NUC-Disjunction poses.
>
> What is the definition of a non-union compatible disjunction?  I am
> unable to find a definition for this, and I'm failing to come up with
> one through a combination of the terms.

We borrow the term from SQL.  The debate at the time was, what is the  
range and domain of disjunction in TQL?  The classification of the  
algebra made it clear that it they needed to be arbitrary Tuples;  
however at that time we were thinking of Tuples in relational terms,  
and that meant value-semantics for UNBOUND.  Even then we could  
anticipate the type-theoretic difficulties this posed, and hence the  
debate.  Fortunately Simon is smarter than I am in this area, and  
once he identified the isomorphism the marker-semantics for UNBOUND  
were obvious.

I still remember spending about 4 hours one afternoon with Simon at a  
whiteboard hammering out a mutual understanding of this.  There's  
nothing quite like going hammer and tongs for 4 hours like that  
before stepping back and realising that we'd managed to answer all  
the questions we had going in, and that suddenly there was nothing to  
argue about :).

> (Andrae)
>> We already draw a distinction between Answers and Tuples.  Tuples are
>> objects within an algebra.  Answers are globalized Tuples, but are
>> primarily an API concern.  Allowing Answers to have DONT_CARE columns
>> is alright, introducing them into Tuples though will cause problems.
> <snip>
>
> So, the projection operation is not in the algebra.  If a  
> projection is
> performed between two Tuples sets, is the resulting set an Answer?   
> I am
> wondering what specifically is meant by an Answer being a "globalized"
> Tuple.

There is a projection operation within the algebra that eliminates  
variables and replaces them in the tuple's tuple-predicate with  
existential quantification.

Ie.

Project currently has the type:

Project :: (Set Variable) -> Tuples -> Tuples ;
   where Tuples :: Pair Predicate (Set (Set (Pair Variable Value)))

Project {x} ( <uri> <pred1> $x and <uri> <pred2> $y, {{ x->'foo1'; y- 
 >'foo2'}, { x->'bar1'; y->'bar2'}} )

becomes

  (Exists $x . <uri> <pred1> $x and <uri> <pred2> $y, {{ y->'foo2'},  
{ y->'bar2'}} )

What is more problematic is a widening operation that extends the  
binding sets with DONT_CARE bindings.

Project {x,y,z} ( <uri> <pred1> $x and <uri> <pred2> $y, {{ x- 
 >'foo1'; y->'foo2'}, { x->'bar1'; y->'bar2'}} )

becomes

( <uri> <pred1> $x and <uri> <pred2> $y, {{ x->'foo1'; y->'foo2'},  
{ x->'bar1'; y->'bar2'}} )

which is unchanged!  However what people seem to want, and which will  
cause trouble is:

( <uri> <pred1> $x and <uri> <pred2> $y, {{ x->'foo1'; y->'foo2'; z- 
 >DONT_CARE}, { x->'bar1'; y->'bar2'; z->DONT_CARE}} )

Now you have z being bound to a value whose meaning is difficult to  
define sensibly.  Worse it becomes a *value* which means it needs a  
type.  Now everyone keeps assuming we can assign the type _|_  
(bottom) to it, but of course _|_ can't have values.  In fact it ends  
up having the type T (top), but this makes the RDF type system a  
lattice - a concept XSD (RDF's type system) doesn't support.  So this  
is what I meant by "problematic type theoretically".

> Also, is the algebra of the semiring for TQL defined somewhere, or  
> is it
> implicit in the TQL grammar definition file?

Simon did a whole lot of work on this, but I don't know what happened  
to it.  I have on several occasions thought about sitting down and  
preparing something on this for publication, but I've never really  
felt comfortable doing so.  It has always felt to me like taking  
credit for Simon's work.

Still it is implicit in the TuplesOperations class within Mulgara.   
And elements of it have been described in detail during the course of  
various arguments on Mulgara's architectural directions - not  
surprising really, it's what sparked this discussion ;).

> This is a very interesting discussion!

I'm glad :).

Andrae

P.S.
For interest, the most trivial example of a NUC-Disjunction in terms  
of the algebra is:

( <uri> <pred1> $x, {{ x->'foo' }} ) or ( <uri> <pred2> $y, {{ y- 
 >'foo'}} )
->  ( <uri> <pred1> $x or <uri> <pred2> $y, {{ x->'foo'}, { y->'foo'}} )

Note the complete absence of UNBOUND!  This is what we mean by  
UNBOUND being a 'marker', not a 'value'.

If we convert this to a TABLE to make the *API* simpler we get:

  $x      $y
'foo'
         'foo'

Which is a problem because now our table has 'holes'.  So we 'mark'  
them as absent from the result by padding the table with special  
markers, *API Artifacts* that do not actually exist in the algebra  
itself.

  $x      $y
'foo'  UNBOUND
UNBOUND 'foo'

Andrae

-- 
Andrae Muys
andrae at netymon.com
Senior RDF/Semantic-Web Consultant
Netymon Pty Ltd






More information about the Mulgara-dev mailing list