RE: Unbound vars as blank nodes

> -----Original Message-----
> From: Seaborne, Andy [mailto:andy.seaborne@hp.com]
> Sent: Wednesday, March 23, 2005 9:30 AM
> To: Geoff Chappell
> Cc: public-rdf-dawg-comments@w3.org
> Subject: Re: Unbound vars as blank nodes
> 
> > That's not to say NULLs won't work. I think a perfectly workable
> solution is
> > to require that all vars mentioned in a pattern element are bound to
> > something by that pattern element -- if not to an actual value, then to
> NULL
> > -- and that NULL != NULL. IMHO that would resolve the current execution
> > ordering mess (I've heard statements to the contrary but I've never seen
> a
> > counter example).
> 

So I took another look at this trying to figure out why optionals break the
commutative nature of AND. Not surprisingly, it has to do with the negation
as failure implicit in optional. It does seem, however, that you can modify
the definition of optional a bit to make results independent of the order of
evalutation. 

First an illustration of the problem using our favorite example:

 _:a  foaf:name       "Alice" .
 _:b  foaf:name       "Bob" .
 _:b  foaf:mbox       <mailto:bob@work.example> .
 _:c  foaf:mbox       <mailto:noname@work.example.org> .
 
 Query::
 PREFIX foaf: <http://xmlns.com/foaf/0.1/>
 SELECT ?name ?mbox
 WHERE
    { ?x foaf:name  ?name .
      OPTIONAL { ?x foaf:mbox ?mbox } .
      ?y foaf:mbox ?mbox .
    }


Looking at it from a relational perspective, each of those pattern elements
standing alone is representative of a table of variable bindings for which
the pattern element is true. The solution to the query is the join product
of all tables. The first pattern element's table is:

x   name
=== =======
_:a "Alice"
_:b "Bob"

and the last pattern element's table is:

y   mbox
=== ================================
_:b <mailto:bob@work.example>
_:c <mailto:noname@work.example.org>


Clearly order of joins should not matter as long as the tables have constant
values. But with the common notion of negation as failure, this is not the
case. Take this case:

	OPTIONAL { ?x foaf:mbox ?mbox}

Which we understand to mean:

	{ ?x foaf:mbox ?mbox} or not { ?x foaf:mbox ?mbox}

What would the table look like for this pattern element? The answer implicit
in all of our discussions so far is that it would depend upon what variables
have been bound prior to evaluating this factor. In effect naf has always
been treated as a filter, never a generator of solutions. But that approach
often disregards all of the other variable bindings that aren't true for the
pattern element (a finite set for a finite domain). We can fix that by
modifying our translation of this:

	OPTIONAL { ?x foaf:mbox ?mbox}

To this:

	{ ?x foaf:mbox ?mbox} or 
	{
		{{?x ?a1 ?b1} or {?a1 ?x ?b1} or {?a1 ?b1 ?x}}
		{{?mbox ?a2 ?b2} or {?a2 ?mbox ?b2} or {?a2 ?b2 ?mbox}}
		not { ?x foaf:mbox ?mbox}
	}

In other words, determine all of the possible values that x and mbox could
take. If those value come into this factor bound, things behave as they
always have. But if they don't, new valid solutions are produced (the
absence of which led to order dependencies in the past). 

One additional modification is necessary so that meaningless solutions
aren't returned -- possible values should only be introduced for variables
that are constrained elsewhere in the query. 

So:

 Query::
 PREFIX foaf: <http://xmlns.com/foaf/0.1/>
 SELECT ?name ?mbox
 WHERE
    { ?x foaf:name  ?name .
      OPTIONAL { ?x foaf:mbox ?mbox } .
    }

would yield for the optional factor:

	{ ?x foaf:mbox ?mbox} or 
	{
		{{?x ?a1 ?b1} or {?a1 ?x ?b1} or {?a1 ?b1 ?x}}
		not { ?x foaf:mbox ?mbox}
	}

The result of all of this is you get the answer you'd get if you evaluated
the optional last (regardless of what order you evaluate).

Thoughts?

Geoff

Received on Thursday, 24 March 2005 14:25:27 UTC