W3C home > Mailing lists > Public > www-archive@w3.org > September 2004

RE: UNSAID : issues in interpretting a query

From: Tim Berners-Lee <timbl@w3.org>
Date: Fri, 10 Sep 2004 13:31:04 -0400
To: Andy Seaborne <Andy_Seaborne@hplb.hpl.hp.com>
Message-Id: <3144538A-034F-11D9-ABE5-000A9580D8C0@w3.org>
Cc: Dan Connolly <connolly@w3.org>, Eric Prud'hommeaux <eric@w3.org>, Public W3C <www-archive@w3.org>
>
>
> Intersting.  I tried cwm from CVS (--revision => )
>    cwm= $Revision: 1.162 $ llyn= $Revision: 1.118 $
>
> --------------------------------
> @prefix log:   <http://www.w3.org/2000/10/swap/log#> .
> @prefix d:     <http://example.org/dawg/> .
>
> :doc :is {
>   d:a d:p d:b .
>   d:a d:q d:c .
> } .
>
> { :doc :is ?d .
>   ?d log:notIncludes { d:a d:p d:xxx } .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> cwm D.n3 --think --strings
> and got "yes"
>

Right.

> When I tried a variable in log:notIncludes:
> --------------------------------
> @prefix log:   <http://www.w3.org/2000/10/swap/log#> .
> @prefix d:     <http://example.org/dawg/> .
>
> :doc :is {
>   d:a d:p d:b .
>   d:a d:q d:c .
> } .
>
> @forAll :x .
>
> { :doc :is ?d .
>   ?d log:notIncludes { d:a d:p :x } .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> I got no output.  No variable testing.

Cwm will insert variables which are bound elsewhere in the LHS.
If this had been a positive log:includes, it would have searched for a 
match.
However, it never tries the infinite set of things and returns those 
for which the search fails.

> --------------------------------
> @prefix log:   <http://www.w3.org/2000/10/swap/log#> .
> @prefix d:     <http://example.org/dawg/> .
>
> :doc :is {
>   d:a d:p d:b .
>   d:a d:q d:c .
> } .
>
> # Sorry - had to repeat the data to force :x to be bound.
> d:a d:p d:b .
> d:a d:q d:c .
>
> @forAll :x .
>
> { :doc :is ?d .
>   ?d log:notIncludes { d:a d:p :x } .         # 1
>   d:a d:q :x .                                # 2
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> gives "yes"

Yes, x is bound to c, so c is a finite solution set it can try on the 
notIncludes,
and one which works.

> as does reversing 1 and 2.

Reversing should have no effect -- all graphs are unordered.

>   This is the same as the logical
> assertion interpretation.
>
> ========================================================
> Trying log:includes:
>
> I tried:
> --------------------------------
> @prefix log:   <http://www.w3.org/2000/10/swap/log#> .
> @prefix d:     <http://example.org/dawg/> .
>
> :doc :is {
>   d:a d:p d:b .
>   d:a d:q d:c .
> } .
>
> d:a d:p d:b .
> d:a d:q d:c .
>
> @forAll :x .
>
> { :doc :is ?d .
>   ?d log:includes { d:a d:p :x } .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> and go "yes".  Seems log:includes works for patterns and 
> log:notIncludes
> does not.

Well, not quite as in 2 above. Basically, cwm will deal with finite 
sets of bindings at each stage.
That is, by the time notIncludes is run -- by the time the query is 
delegated to a sub-search,
the results of which are to be negated, the variables must all be bound.


>
> --------------------------------
> { :doc :is ?d .
>   ?d log:includes { d:a d:p :x } .
>   d:a d:p :x .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> says "yes" as does

yes, because you give it a limited set of what to try to for ?x.

> --------------------------------
> { :doc :is ?d .
>   d:a d:p :x .
>   ?d log:includes { d:a d:p :x } .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> but
> --------------------------------
> { :doc :is ?d .
>   ?d log:includes { d:a d:p :x } .
>   d:a d:q :x .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
> does not print anything.  So we have the unordered interpretation.

yes, there is no ordering (without collections).

> Checking, removing the "d:a d:q :x ." we get one of the runs above: so
> removing a statement increases the number of solutions.
>
> --------------------------------
> { :doc :is ?d .
>   ?d log:includes { d:a d:p :x } .
>  } => { :doc log:outputString "yes\n" . } .
> --------------------------------
>
>
> Dan - what's cwm's execution algorithm here for matching the LHS of
> log:implies?

1. It first looks at the  set of triples which are being matches 
against the knowledge base.
2. Then for each one which is log:includes it considers the set of 
triples being matches against another formula.
3. It considers the set of all such (large formula, triple being looked 
for in it).
4. Within that set it looks for easy things - easy built-in functions 
whose arguments are bound,
   or failing that triples with only one variable unbound, etc.... 
failing which nasty looking built-in functions
   which involve web access etc.  It does the easiest, possibly creating 
bindings which are applied to other occurrences in the database formula 
and any nested formulae.  Builtin functions are only evaluated when 
there are no unbound variables in their inputs.
log:notIncludes is like a builtin recursive invokation of log:implies, 
except built-in evaluation is not performed in log:includes.
5. Rinse and repeat, eventually eliminating all the lines of the query.


>         Andy
Received on Friday, 10 September 2004 17:31:07 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 7 November 2012 14:17:46 GMT