• Internet search: combining query language, rule languages and scoped negation

This is one of the possible Use Cases.

1. Abstract

The use case below is expressing features which we would expect from a rule language with scoped negation in an internet search setting. It uses simple LP style rules and facts, 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 in the context of querying.

2. Status

Originally proposed by AxelPolleres, AndreasHarth.

We are currently working on a solution in the distributed RDF repository and query engine YARS, which tackles the issues raised in this use case towards an internet scale RDF search engine allowing semantic queries. We plan to take rules spanning multiple contexts into account.

3. Links to Related Use Cases

• Scoped negation, Encapsulation: We relate to this use case in that we also name scoped negation as a required feature of a useful rule and query language.

• RIF RuleML FOAF: We relate to this use case in the sense that it also proposes distributed rule bases on top of RDF data in this case specific to FOAF.

• Ontology Mapping with OWL and Rules: We strongly relate to this use case in thes sense that the eventual requirements are the same: Integration/Interoperability of full RDFS and OWL Rule Bases with RDF. However, we tackle a different aspect to start with, namely, RDF plus rules with contextually scoped negation, whereas this use case specifically deals with integration issues with OWL via a restricted form of rules, so called DL-safe rules.

• Filling the holes of OWL: This use case relates to ours in a similar sense as the previous one.

4. Relationship to OWL/RDF Compatibility

• Scoped negation and query languages need to eventually operate on top of RDFS and OWL.

For that reason we need to tackle interoperability of open world axioms such as introduced by Ontologies in RDF(S) and OWL with rules and queries involving scopes in a proper way. See also the issues list in the Commentary section at end of this use case description.

5. Examples of Rule Platforms Supporting this Use Case

For instance, FLORA-2's module mechanism allows a form of scoped negation as failure using the well-founded semantics. Negative queries can be posed to a certain module. However, since variable are allowed in the place of the module identifier the scope of the query (negation) being the union of all the modules registered with the system at that point in time is not stable against addition of knowledge bases. This unrestricted way for defining scoped negation does not necessarily always guarantee correct results with respect to what we call context-monotonicity (see Commentary section below).

Further, we are planning to implement a restricted form of queries with scoped negation in YARS.

6. Benefits of Interchange

• Rules can be authored in a decentralized way and enable further inferences over RDF data
• Rules from different sources are to be combined, which requires a common rules interchange format

7. Requirements on the RIF

• Support scoped rules and scoped negation
• We expect a rule interchange format which integrates query and rule language, just as datalog does for common query languages

• We expect the rule interchange format to be (partially?) mappable from to http://www.w3.org/TR/rdf-sparql-query/ SPARQL]

8. Breakdown

8.1. Actors and their Goals

• Client C - poses an open search query on the internet , possibly including scoped negation, addressed to a Search engine E

• Search Engine Agent E - provides sound answers to the user query.

• Rule/Data Providers P - make accessible rules and facts accessible at a unique URI.

8.2. Main Sequence

• Typical course of events:

• Provider IMDB publishes its data and rules at URI http://www.imdb.com:

  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). 
  

• Provider MOVIEREWIEWS publishes its data at URI http://moviereviews.com/ :

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

• Provider MOVIEFAN1 publishes its data at URI http://moviefan.com/fan1 :

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

• Provider MOVIEFAN2 publishes its data at URI http://moviefan.com/fan2 :

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

• Search engine MOVIESEARCH crawls such rule bases and is aware of IMDB and MOVIEREVIEWS, MOVIEFAN1.
• Client C asks MOVIESEARCH queries like:
  • “Give me movies which are rated as bad"
  • which is rewritten as a rule as follows:

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

• MOVIESEARCH will return m1, m2, and m3.

8.3. Alternate Sequences

8.3.1. Variation1: Monotonicly growing result sets upon context addition

• Additionally to the steps above, the following are added:
• Upon further crawling MOVIESEARCH will become aware of MOVIEFAN2 as well.
• Upon re-querying MOVIESEARCH will additionally return m4.

8.4. Variation2: Adding negation as failure

1. Client C modifies her query as follows:
   • “Give me movies which are not rated as bad" which is rewritten as a rule as follows:

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

2. Search engine MOVIESEARCH returns an error message, asking the client to specify the scope of negation.

8.5. Variation3: Queries with scoped negation as failure

1. C refines her query to:
   • “Give me movies which are not rated as bad by moviereviews.com"
   • which is written as a rule as follows:

     answer(X) :- movie(X), not rated(X, bad)@http://moviereviews.com.

2. Search engine MOVIESEARCH returns m4 plus an additional warning stating
   • that the evaluation of the negative query depends on an open rule.

9. Narratives

Michel Deutscher, a movie enthusiast, wants to find out tips for movies to rent using his favorite search engine moviesearch.com which is enabled by the new feature of "rule aware search" allowing rules and semantic data advertised at various different sites on the web to be taken into acount during search results. Michel's query for “Give me movies which are rated as bad" will be translated into a rule to be evaluated by moviesearch.com's internal rule engine which operates on the rules and RDF data crawled on the web, returning all movies which can be derived to be rated as bad by sites and users over the web, including sites such as reviews.com, a repository for moviereviews by journalists or individual sites of moviefan.com a fictitious social network of movie enthusiasts who publish their rules and ratings on individual sites.

This said, these distributed ratings can involve not only hard facts such as "Plan 9 from Outer Space is a bad movie", but also involve rules such as "All movies directed by Ed Wood are bad movies", etc. as shown in the original use case sequence above.

9.1. Implications of Variation 1 - Incompleteness of Knowledge

Depending on which rule bases moviesearch.com 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.

In the scenario from above moviesearch.com would return m1,m2,m3, if aware of reviews.com, moviefan.com/fan1, and moviefan.com/fan2. Moreover, E would return m4 as well, if additionally aware of example3.com.

9.2. Implications of Variation 2 - Negaitve queries and rules

Incompleteness, as it turns out, becomes fatal if Michel asks negative queries such as the one in Variation2 above. If the search engine is only "aware" of contexts, imdb.com, , and example2.com, it would return the possibly incorrect answer m4.

9.3. Implications of Variation 3 - Scoped Negation

Thus, we need enable the client to make the scope of negation explicit, as already mentioned in other use cases already.

However, since moviereviews.com itself contains an open/unscoped rule, still correctness of the query answer depends on the awareness of moviefan.com/fan2. I.e., if moviesearch.com was not aware of moviefan.com/fan2, it would still falsely return m4 as an answer if scoped negation was treated naively.

There are in principle two ways to fix this:

1. we syntactically guarantee contextually bounded use of scoped negation, i.e. no dependency on open rules is allowed or

2. we close off open rules referenced by scoped negation. Variation3 above shows this approach, by not taking m4 into account, but stating a warning that the result depends on an open rule. Remark: Our intention is that, still the result would not change, even if moviesearch becomes aware of moviefan.com/fan2.

10. Commentary

In our 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. We call this requirement context-monotonicity, since it says that query answers of an engine should not need to be retracted because the engine became aware of additional contexts, where each context is a closed knowledge base.

We can imagine such a rule language which guarantees context-monotonicity with a cautious form of scoped negation not necessarily on top of full expressive formalisms such as OWL which add additional features such classical negation, but rather for the beginning start on top of RDF and RDFS only and later tackle full OWL interoperability.

Issues:

• Trust, probably, scope and evaluation of distributed scoped and open rules should also take trust into account.
• As for scoped negation, we expect from the rules working group a solution for which allows us to define contectually "safe" form of scoped negation, i.e. that the evaluation of scoped negation is not again depending on open rules which would lead to non-monotonic effects in an open environment. Such a restricted form of scoped negation could, in our opinion already be part of phase I.
• As for compatibility with RDF/RDFS data, a solution has to be found to comply with full RDF and RDFS where issues might arise concerning blank nodes, ambiguous use of the RDF/RDFS vocabulary, etc.
• As for compatibility with OWL we propose for Phase II a solution which allows one to express preferences between possibly contradicting rule bases and ontologies. Note that, as long as we only deal with RDF and RDFS, contradiction is only partly an issue, as long as negation as failure is used in a safe, scoped way, whereas by classical negation introduced by OWL we might run into more severe conflicts.