A Proposal for an
OWL Rules Language

Semantics and Abstract Syntax

Draft Version of 11 August 2003

This version:
http://www.cs.man.ac.uk/~horrocks/DAML/Rules/WD-OWL-rules-20030811/
Latest version:
http://www.cs.man.ac.uk/~horrocks/DAML/Rules/WD-OWL-rules-20030811/
Authors:
Ian Horrocks, Department of Computer Science, University of Manchester
Peter F. Patel-Schneider, Bell Labs Research, Lucent Technologies

Abstract

This is a description of a proposed rules extension to the OWL Web Ontology Language. It includes a high-level abstract syntax for horn clause rules in both the OWL DL and OWL Lite sublanguages of OWL. A model-theoretic semantics is given to provide a formal meaning for OWL ontologies including rules written in this abstract syntax.

Status of this document

This is a Working Draft produced 11 August 2003 as part of the DARPA DAML Program.

Comments on this document are invited and should be sent to the authors (horrocks@cs.man.ac.uk and pfps@research.bell-labs.com).



Table of contents


1. Introduction

This document contains a proposal for a rules extension to the OWL DL and OWL Lite sublanguages of the OWL Web Ontology Language. The proposal extends the set of OWL axioms to include horn clause rules. A high-level abstract syntax is provided that extends the OWL abstract syntax described in the OWL Semantics and Abstract Syntax document [OWL S&AS]. An extension of the OWL model-theoretic semantics is also given to provide a formal meaning for OWL ontologies including rules written in this abstract syntax.

The proposed rules are of the form of an implication between an antecedant (body) and consequent (head). The intended meaning can be read as: whenever the conditions specified in the antecedent hold, then the conditions specified in the consequent must also hold.

Both the antecedent (body) and consequent (head) consist of zero or more atoms. An empty antecedent is treated as trivially true (i.e. satisfied by every interpretation), so the consequent must also be satisfied by every interpretation; an empty consequent is treated as trivially false (i.e., not satisfied by any interpretation), so the antecedent must also not be satisfied by any interpretation. Multiple atoms are treated as a conjunction. Note that rules with conjunctive consequents could easily transformed (via the Lloyd-Topor transformations [Lloyd87]) into multiple rules each with an atomic consequent.

Atoms can be of the form C(x), P(x,y), sameAs(x,y) or differentFrom(x,y), where C is an OWL description, P is an OWL property, and x,y are either variables, OWL individuals or OWL data values. It is easy to see that OWL DL becomes undecidable when extended in this way as rules can be used to simulate role value maps [Schmidt-Schauß89].



2. Abstract Syntax

The syntax for OWL Rules in this section abstracts from any exchange syntax for OWL and thus facilitates access to and evaluation of the language. This syntax extends the abstract syntax of OWL described in the OWL Semantcs and Abstract Syntax document [OWL S&AS].

The abstract syntax is specified here by means of a version of Extended BNF, very similar to the EBNF notation used for XML [XML]. Terminals are quoted; non-terminals are bold and not quoted. Alternatives are either separated by vertical bars (|) or are given in different productions. Components that can occur at most once are enclosed in square brackets ([…]); components that can occur any number of times (including zero) are enclosed in braces ({…}). Whitespace is ignored in the productions here.

Names in the abstract syntax are RDF URI references, [RDF Concepts]. These names may be abbreviated into qualified names, using one of the following namespace names:


Namespace nameNamespace
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
rdfshttp://www.w3.org/2000/01/rdf-schema#
xsdhttp://www.w3.org/2001/XMLSchema#
owlhttp://www.w3.org/2002/07/owl#

The meaning of each construct in the abstract syntax is informally described when it is introduced. The formal meaning of these constructs is given in Section 3 via an extension of the OWL DL model-theoretic semantics [OWL S&AS].

2.1. Rules

An OWL ontology in the abstract syntax contains a sequence of axioms and facts. Axioms may be of various kinds, e.g., subClass axioms and equivalentClass axioms. It is proposed to extend this with rule axioms.

axiom ::= rule 

A rule axiom consists of an antecedent (body) and a consequent (head), each of which consists of a (posibly empty) set of atoms.

rule ::= 'Implies(' antecedent consequent ')'
antecedent ::= 'Antecedent(' { atom } ')'
consequent ::= 'Consequent(' { atom } ')'

Informally, a rule may be read as meaning that if the antecedent holds (is "true"), then the consequent must also hold. An empty antecedent is treated as trivially holding (true), and an empty consequent is treated as trivially not holding (false). Non-empty atecedents and conseqents hold iff all of their constituent atoms hold, i.e., they are treated as conjunctions of their atoms. As mentioned above, rules with conjunctive consequents could easily transformed (via the Lloyd-Topor transformations [Lloyd87]) into multiple rules each with an atomic consequent.

atom ::= description '(' i-object ')'
	 | individualvaluedPropertyID '(' i-object i-object ')'
	 | datavaluedPropertyID '(' i-object d-object ')'
	 | sameAs '(' i-object i-object ')'
	 | differentFrom '(' i-object i-object ')'

Atoms can be of the form C(x), P(x,y), sameAs(x,y) or differentFrom(x,y), where C is an OWL description, P is an OWL property, and x,y are either variables, OWL individuals or OWL data values. In the context of OWL Lite, descriptions in atoms of the form C(x) may be restricted to class names.

Informally, an atom C(x) holds if x is an instance of the class description C, an atom P(x,y) holds if x is related to y by property P, an atom sameAs(x,y) holds if x is interpreted as the same object as y, and an atom differentFrom(x,y) holds if x and y are interpreted as different objects. Note that the latter two forms can be seen as "syntactic sugar": they are convenient, but do not increase the expressive power of the language (i.e., such (in)equalities can already be expressed using the combined power of OWL and rules without explicit (in)equality atoms).

i-object ::= i-variable | individualID
d-object ::= d-variable | dataLiteral

Atoms may refer to individuals, data literals, individual variables or data variables. Variables are treated as universally quantified, with their scope limited to a given rule. As usual, only variables that occur in the antecedent of a rule may occur in the consequent (a condition usualy refered to as "safety"). This safety condition does not, in fact, restrict the expressive power of the language (because existentials can already be captured using OWL someValuesFrom restrictions).

i-variable ::= 'I-variable(' URIreference ')'
d-variable ::= 'D-variable(' URIreference ')'

3. Direct Model-Theoretic Semantics

The model-theoretic semantics for OWL rules is a straightforward extension of the semantics for OWL given in [OWL S&AS]. The basic idea is that we define bindings, extensions of OWL interpretations that also map variables to elements of the domain. A rule is satisfied by an interpretation iff every binding that satisfies the antecedent also satisfies the consequent. The semantic conditions relating to axioms and ontologies are unchanged, e.g., an interpretation satisfies an ontology iff it satisfies every axiom (including rules) and fact in the ontology.

3.1. Interpreting Rules

Given an abstract OWL interpretation I, a binding B(I) is an abstract OWL interpretation that extends I such that function S maps i-variables to elements of R and d-variables to elements of LVT respectively.

We recall that an Abstract OWL interpretation is a tuple of the form: I = <R, V, EC, ER, S> [OWL S&AS]. An atom is satisfied by an interpretation I under the conditions given in Interpretation Conditions Table.


Interpretation Conditions Table
AtomCondition on Interpretation
description(x) S(x) ∈ EC(description)
property(x,y) <S(x),S(y)> ∈ ER(property)
sameAs(x,y) S(x) = S(y)
differentFrom(x,y) S(x) ≠ S(y)

A binding B(I) satisfies an antecedent A iff A is empty or B(I) satisfies every atom in A. A binding B(I) satisfies a consequent C iff C is not empty and I satisfies every atom in C. A rule is satisfied by an interpretation I iff for every binding B such that B(I) satisfies the antecedent, B(I) also satisfies the consequent.

The semantic conditions relating to axioms and ontologies are unchanged. In particular, an interpretation satisfies an ontology iff it satisfies every axiom (including rules) and fact in the ontology; an ontology is consistent iff it is satisfied by at least one interpretation; an ontology O2 is entailed by an ontology O1 iff every interpretation that satisfies O1 also satisfies O2.


4. Mapping to RDF Graphs

Problem: Rules have variables so treating them as a semantic extension of RDF is very difficult, and maybe even impossible.

Solution1: Don't treat them as a semantic extension to RDF. Don't even give them an RDF encoding. Instead use an XML syntax for OWL rules that extends the XML syntax for OWL.

Solution2: Don't treat them as a semantic extension to RDF. Give them an RDF encoding that extends the RDF encoding of OWL, but don't expect OWL rules entailments to be a superset of RDF entailments.



References

[OWL S&AS]
OWL Web Ontology Language Semantics and Abstract Syntax. Peter F. Patel-Schneider, Pat Hayes and Ian Horrocks, eds.
[OWL Reference]
OWL Web Ontology Language 1.0 Reference. Mike Dean, Dan Connolly, Frank van Harmelen, James Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein. W3C Working Draft 12 November 2002. Latest version is available at http://www.w3.org/TR/owl-ref/.
[Lloyd87]
Foundations of logic programming (second, extended edition). J. W. Lloyd. Springer series in symbolic computation. Springer-Verlag, New York, 1987.
[Schmidt-Schauß89]
Subsumption in KL-ONE is Undecidable. M. Schmidt-Schauß. Proc. of KR'89, pages 421-431, Morgan Kaufmann.