[Use Case] Internet search: combining query language, rule languages and scoped negation

Sorry for the late contribution, FWIW, maybe it can still be interesting 
for the use case discussions on use cases on Friday.

The use case below is expressing a feature which I would expect from
a rule language with scoped negation in an internet search setting.
It uses simple LP style rules and facts for the moment,
but we can also provide it in a more RDF/RDFS based version.
  It shall showcase possible problems of combining scoped negation
with open rules.

=====================================================================

Use Case: Internet search:
combining query language, rule languages,
scoped negation and open rules from ontologies

Let us assume distributed rule bases on the internet storing rules and 
facts about movies:

http://www.imdb.com/ :

  sciFiMovie(m1).
  hasTitle(m1,"Plan 9 from Outer Space").
  directedBy(m1,"Ed Wood").
  sciFiMovie(m2).
  hasTitle(m2,"Matrix Revolutions").
  directedBy(m2,"Andy Wachowski").
  directedBy(m2,"Larry Wachowski").
  sciFiMovie(m3).
  hasTitle(m3,"Bride of the Monster").
  directedBy(m3,"Ed Wood").
  movie(X) :- sciFiMovie(X).
  hasTitle(m4,"Star Wars").
  sciFiMovie(m4).

http://example1.com/
  rated(m1,bad).
  rated(X,bad) :- directedBy(X,"Ed Woood").

http://example2.com/
  rated(m2,bad). movie(m2).

http://example3.com/
  directedby(m4,"Ed Wood").


Let us assume a search engine E crawling such rule bases.

You can ask such an engine E queries like:
  “Give me movies which are rated as bad"

could be written as a rule as follows:

  answer(X) :- movie(X), rated(X,bad).

and depending on which rule bases it is aware of, it will give sound
but probably incomplete answers. This incompleteness is usually 
acceptable in search scenarios, as long as I can be sure all answers are 
sound at least. Assuming that all sources provide correct information,
E would return m1,m2,m3, if aware of imdb.com, example1.com, and 
example2.com.
Moreover, E would return m4 as well, if additionally aware of example3.com.


However, incompleteness becomes fatal if if you ask negative queries:

  “Give me movies which are not rated as bad"

  answer(X) :- movie(X), not rated(bad).


  If the search engine is only "aware" of contexts, imdb.com, 
example1.com, and example2.com, it would return the possibly incorrect 
answer m4. Thus, we need to scope off negation, as already mentioned in 
several discussions and other use cases.


  However, as it turns out, it is not enough to simple ask the query

  “Give me movies which are not rated as bad by example1.com"

  answer(X) :- movie(X), not rated(bad)@example1.com.


  Since example1.com itself contains an open/unscoped rule, and still 
correctness of the query answer is dependent of awareness of 
example3.com. I.e. An engine not aware of example3.com would still 
falsely return m4 as an answer if scoped negation was treated naively.

There are tywo ways to fix this:
(a) we syntactically guarantee contextually bounded use of scoped 
negation, i.e. no dependency on open rules is allowed or
(b) we close off open rules referenced by scoped negation.


Implications:

   In my opinion, the combination of a query/rule language with scoped 
negation should ensure soundness of query answers, by disallowing
open scopes, but still allowing maximum flexibility of open rules 
published in distributed rule bases. This should also be considered as a 
goal of the interaction/exchange of results of other workinggroups such 
as the SPARQL WG.

  We require a useful rule language for web search to either define
appropriate restrictions or by definition of the semantics guarantee a 
"safe" interplay of open rules with scoped negation in a way 
guaranteeing soundness of query answers.
I call this requirement context-monotonicity, since it says that query 
answers of an engine should not need to be retracted bacause the engine 
  became aware of additional contexts, where each context is a closed 
knowledge base.

  I could imagine such a rule language which guarantees 
context-monotonicity with a cautious form of scoped negation not
nexcessarily on top of full expressive formalisms such as OWL which add 
additional features such classical negation, but rather for the 
beginning on top of RDF and RDFS only.

Received on Wednesday, 7 December 2005 21:05:06 UTC