Requirements and Non-Requirements for a Semantic Web Rule Language

Peter F. Patel-Schneider
Bell Labs Research

In this position paper for the W3C Workshop on Rules Languages for Interoperability, I argue for certain characteristics that a Semantic Web rule language should have. More importantly, I also argue that certain other characters that have been proposed for a Semantic Web rule language may not be desirable.

My recommendations can be boiled down into two admonishments:

What do I mean by these admonishments?

Well, it is obvious that a Semantic Web rule language should fit into the evolving standards and principles of the Semantic Web and the world wide web. However, it is possible to damage the utility of a Semantic Web rule language by forcing it too conform with the evolving standards and principles of the Semantic Web and the world wide web where there are good reasons for it not too.

Playing well with others

Some of the obvious places where a Semantic Web rule language should play well with others are:

Not playing too well with others

However, there are not too many other requirements that have to be satisfied by a Semantic Web rule language.

Why do I make these claims?

There are many implemented rule languages, so why not pick one of them? Well, I claim that the major existing implemented rule languages, and thus the obvious candidates, are not particularly appropriate for the Semantic Web.

Rule systems deriving from OPS [Cooper and Wogrin, 1988] have an operational semantics, where rules have side effects and the order of rule execution is vitally important. Such rule systems are much more a programming language than a representation formalism and thus do not fit well into the representational Semantic Web.

The other major rule systems with optimized implementations fit into some generalization of the Prolog or Datalog paradigms. These paradigms have some unfortunate features with respect to the Semantic Web. Prolog has imperative features which make it almost as suspect as OPS rules. Many people use only the non-imperative features of Prolog, so it is possible to consider this fragment of Prolog as a candidate for Semantic Web rules. This fragment of Prolog is quite close to Datalog, Datalog further prohibits functions and a few other bits of Prolog, resulting in a decidable subset of Prolog. Neither Datalog nor Prolog allow disjunctive or existential information to be present. This severely limits their expressive power in ways that may make them less than ideal for use in the Semantic Web.

Prolog and Datalog, in particular, are often augmented with non-monontonic constructs. There have been claims that a Semantic Web rule language should be non-monotonic, because non-monotonicity helps with modelling. I claim that this is not necessarily the case, partly because of the open nature of the Semantic Web. If it is hard to determine when all relevant information has been gathered then it is hard to determine when to know that something is not derivable and that the conditions of a non-monotonic rule have been satisfied.

There has been a continuing effort to force all the Semantic Web languages into a underlying single syntax with a compatible semantics, namely RDF triples (whatever the surface syntax is) with a semantics that is upward-compatible with the RDF model theory. I claim that this is wrong-headed for two reasons:

  1. The use of such a simple syntax means that complex constructs have to be encoded into triples. If the higher level syntax has disjunction or negation its syntax has to be quoted to prevent the interior constructs from being asserted. Then there have to be comprehension principles to ensure that enough syntax is around to allow entailment to work properly. Then there needs to be a truth predicate to pick out the syntax that is true. However, this truth predicate quickly leads to paradoxes.
  2. Even if the language is not powerful enough for paradoxes to arise (e.g, OWL), the utility of the encoding is not particularly great. Yes, applications that can handle the lower level can glean something from the higher level, but much of the meaning of the higher level is carried in encoded syntax, which is inaccessible to the lower level. If the higher level is non-monotonic, this inaccessibility may lead to invalidity of the lower level inferences.

These problems with using the same syntax can be summed up in a catchy slogan.

Different syntax for different levels, its not just the law, its a good idea.

I finally claim that it is not necessary to build exactly on the semantics of the lower level of the Semantic Web. This is a somewhat surprising claim, as it appears to fly against the entire vision of the Semantic Web. However, it is possible to extend the meaning of a lower level of the Semantic Web without using the semantics of the lower level.

To see this, consider adding a level to the Semantic Web that has temporal constructs. A natural semantics for this level would have the notion of time as an integral part. The model theory for RDF does not have any such notion so directly extending the RDF model theory would require some very clever way of encoding temporal notions into the relations. (Let's ignore the fact that this is probably impossible–consider instead something like the situation calculus, which encodes temporal notions into an extra argument to all relations.) This kind of encoding almost always leads to fragile and hard to understand semantics. (See, for example, the RDF-compatible semantics for OWL Full as an example of some of the things that have to be done to get everything to work well.)

However, there is another way to proceed, which I claim is better. Instead build a natural temporal model theory, but ensure that if no temporal constructs are used that it acts the same as the lower-level semantics. (Actually, it would be best to do somewhat better than this and have the semantics reduce to the lower-level semantics in the absence of temporal constructs.) Then the lower level can be nicely injected into the higher level (e.g., by treating the lower level as true at the current point of time). In this way compatability can be maintained wihtout having to damage the semantic underpinnings of the higher level.


[Cooper and Wogrin, 1988]
Thomas A. Cooper and Nancy Wogrin. Rule-Based Programming with OPS5. Morgan Kaufmann, San Mateo, California, 1988.
[Dean et al, 2004]
Mike Dean, Guus Schreiber, Sean Bechhofer, Frank van Harmelen, Jim Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein. OWL Web Ontology Language Reference. W3C Recommendation 10 February 2004,
[Horrocks and Patel-Schneider, 2004]
Ian Horrocks and Peter F. Patel-Schneider. Reducing OWL Entailment to Description Logic Satisfiability. Journal of Web Semantics, 1:4, 2004, pages 345–357.
[Horrocks et al, 2005]
Ian Horrocks, Peter F. Patel-Schneider, Sean Bechhofer, and Dmitry Tsarkov. OWL Rules: A Proposal and Prototype Implementation. Accepted by Journal of Web Semantics.
[Horrocks et al, 2003]
Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. >From SHIQ and RDF to OWL: The Making of a Web Ontology Language. Journal of Web Semantics, 1:1, December 2003, pages 7–26.
[Parsia and Patel-Schneider, 2004]
Bijan Parsia and Peter F. Patel-Schneider. Meaning and the Semantic Web. The Thirteenth International World Wide Web Conference. New York, New York, May 2004, ACM Press.
[Patel-Schneider, 2004]
Peter F. Patel-Schneider The Semantic Web and Knowledge Representation. Invited talk for the Fifth Mexican International Conference on Computer Science (ENC 2004), Colima, Mexico, September 2004.
[Patel-Schneider, 2005]
Peter F. Patel-Schneider. Building the Semantic Web Tower from RDF Straw. Submitted to IJCAI-2005.
[Patel-Schneider, 2004]
Peter F. Patel-Schneider, Patrick Hayes, and Ian Horrocks. OWL Web Ontology Language Semantics and Abstract Syntax. W3C Recommendation 10 February 2004,