This is an archive of an inactive wiki and cannot be modified.

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

4. Relationship to OWL/RDF Compatibility

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

7. Requirements on the RIF

8. Breakdown

8.1. Actors and their Goals

8.2. Main Sequence

8.3. Alternate Sequences

8.3.1. Variation1: Monotonicly growing result sets upon context addition

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"
    • which is written as a rule as follows:

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

  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 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'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, a repository for moviereviews by journalists or individual sites of 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 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 would return m1,m2,m3, if aware of,, and Moreover, E would return m4 as well, if additionally aware of

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,, , and, 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 itself contains an open/unscoped rule, still correctness of the query answer depends on the awareness of I.e., if was not aware of, 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

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.