- From: Geoff Chappell <geoff@sover.net>
- Date: Thu, 24 Mar 2005 09:25:13 -0500
- To: <andy.seaborne@hp.com>
- Cc: <public-rdf-dawg-comments@w3.org>
> -----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