Re: Disjunction vs. Optional ... and UNION

Bob MacGregor wrote:
> Geoff and Andy,
> 
> I have to recant somewhat. Now that its daylight, I can see that in
> a set of the bindings like
> 
> {?mbox =<alice>  and (?name="alice" or true) and (?nick="who" or true)} or
> {?mbox =<bert>  and (?name="bert" or true) and (false or true)} or
> {?mbox =<eve>  and (false or true) and (?nick="duck" or true)}
> 
> the 'and' and 'or' can't be treated like
> ordinary logical AND and OR to get the result that we want.
> 
> I've started a side-discussion to see how to get a logical
> formalism that delivers the ideal set of bindings.  Pat Hayes
> was kind enough to give me this pointer
>     http://www.w3.org/2001/sw/DataAccess/ftf5-bos.html#item02
> which I wasn't able to dig up myself, and that sheds some
> additional light on the committee's stance.  But more light
> is needed ...
> 
> Here is the base I'm starting from.  I assume a single
> logical AND operator (unlike the two ("." and "&&") in
> SPARQL), so that triple patterns and constraints work
> in all combinations.  I know that I can do this safely, because
> KIF does it.  I use a conventional disjunction operator,
> OR (unlike the strange SPARQL UNION operator).  Again, its
> a subset of KIF, so there are no semantic problems.  And
> then we want to tackle OPTIONAL.
> 
> There are no issues with ordering at this point.  The
> SPARQL document mutters about ordering here and there,
> and its unclear to me (1) why SPARQL has two AND operators;
> (2) why it has a non-standard disjunction, (3) whether this
> bizarreness relates to OPTIONAL somehow, or if it has its
> own origins, and (4) whether ordering issues arise with
> the ANDs and UNION.  The SPARQL document pretty much takes
> these things for granted, and drilling down by following
> URLs doesn't help much.  I'm sure there are discussions
> on each somewhere on the Web, but they aren't easy to locate
> (for me anyway).
> 
> So, my staring point is much cleaner, but also different,
> so I can't tell if that makes our approach to OPTIONAL
> less relevant.
> 
> Our query processor is a backchainer designed to handle
> a KIF-like language.  The implementation of OPTIONAL
> shares the same machinery as the implementation of the OR
> operator.  Our implementation of OPTIONAL takes nine (9)
> lines of Java code.  It might have been six lines, but
> one can implement either a "smart" or a "dumb" version
> of OPTIONAL.
> 
> The dumb version of OPTIONAL evaluates its argument,
> calls the continuation method to evaluate remaining
> clauses, and when the call returns, calls the
> continuation code again without evaluating the argument
> to OPTIONAL, thereby simulating what I refer to
> as the 'true' argument in the notionally disjunctive version
> of optional.  This version generates the excess
> rows containing too many occurrences of variables
> bound to "unbound".
> 
> The smart version of OPTIONAL evaluates its argument
> and calls the continuation code as before, but then
> it checks to see if any output rows were generated.  If so,
> it knows that evaluation of 'true' is unnecessary.
> Otherwise, it does the extra evaluation.  This version
> produces the more succinct output that has generally been deemed
> "correct" or "desirable" in the various e-mail discussions.
> 
> I have to admit that, because implementing OPTIONAL proved to be
> almost trivial, I may have incorrectly assumed that OPTIONAL
> can be safely embedded into a KIF-like logic.
> 
> OPTIONAL appears to combine several distinct issues.  Ideally,
> we could split them out, and address them individually.
> Here is an attempt at enumerating them:
> 
> (1) Is either the "dumb" version or the "smart" one semantically-valid,
> or is the whole idea untenable?

The intention is to have what you call the "smart" form.

 > The smart version of OPTIONAL evaluates its argument
 > and calls the continuation code as before, but then
 > it checks to see if any output rows were generated.  If so,
 > it knows that evaluation of 'true' is unnecessary.
 > Otherwise, it does the extra evaluation.

That definition is the same structure as the one in the SPARQL drafts.  In 
particular, there is an "if" in the middle of it based on whether the pattern 
matches or not.

I don't know how a logic engine with continuations works. Taking your definition 
and some data:


== Data:
:zz :q :bb .
:yy :p :aa .

== Part query:
  ?x :p ?a .
  OPTIONAL { ?x :q ?b }


Reading definition ....

Evaluate argument.
   ?x = :zz , ?b  = :bb
There were output rows so don't do the "true".

The output row does not provide a solution for "?x :p ?a".

What should the engine be doing about the fact ?x occurs in the fixed and 
optional parts? Is it because it (conceptually) tries all possibilities and so 
finds the other one where ?x = :yy and OPTIONAL is not adding anything?

	Andy

> 
> (2) If the answer to (1) is "yes", can we produce a semantics
> that conforms to the smart version?
> 
> (3) Do there need to be any restrictions on scoping of
> variables to make things work (i.e., as a by-product of
> finding a solution to issue (1))?
> 
> (4) Does the semantics for OPTIONAL (assuming there is one)
> require that we redefine AND and OR (as SPARQL does now),
> or are those issues decouplable?
> 
> (5) Do we need a special value representing 'unbound'?
> If so, does one value suffice, or do we need many
> (possibly, the bnode-as-unbound question derives from this one)?
> 
> Observation: The questions I was recently fielding mainly concerned
> issue (2).  If we don't have a definitive answer to (1),
> then (2) is irrelevant, so for the moment, we should really
> not be arguing that question.
> 
> A good starting point would be to investigate whether a
> simple version of OPTIONAL, say one with no nesting,
> no constraints, and only conjunction, has a semantic basis.
>  
> Cheers, Bob
> 

<snip/>

Received on Tuesday, 29 March 2005 17:01:07 UTC