Tractable Fragments

[Hide Review Comments]

[Show Review Comments]

Document title:

OWL 2 Web Ontology Language
Tractable Fragments (Second Edition)

Authors

Bernardo Cuenca Grau, The University of Manchester

Contributors

Diego Calvanese, Free University of Bolzano

Giuseppe De Giacomo, University of Rome ``La Sapienza''

Ian Horrocks, Oxford University

Carsten Lutz, TU Dresden

Boris Motik, Oxford University

Bijan Parsia, The University of Manchester

Peter F. Patel-Schneider, Bell Labs Research, Lucent Technologies

Abstract

OWL 1.1 extends the W3C OWL Web Ontology Language with a small but useful set of features that have been requested by users, for which effective reasoning algorithms are now available, and that OWL tool developers are willing to support. The new features include extra syntactic sugar, additional property and qualified cardinality constructors, extended datatype support, simple metamodelling, and extended annotations. This document provides a specification of different families of sub-languages of OWL 1.1, for which the main reasoning problems can be decided in polynomial time. This document is intended to serve as a useful guideline for developers and users.

Status

This document is an evolution of the OWL 1.1 Web Ontology Language: Tractable Fragments document that forms part of the OWL 1.1 Web Ontology Language W3C Member Submission.

Copyright © 2006-2007 by the Authors. This document is available under the W3C Document License. See the W3C Intellectual Rights Notice and Legal Disclaimers for additional information.

1 Introduction

This document provides a specification of a set of prominent logics that:

• can be regarded as fragments of OWL 1.1, and
• can handle at least some interesting inference service in polynomial time with respect to either the number of facts in the ontology or the size of the ontology as a whole.

The list provided in this document is not meant to be exhaustive.

The described logics have been recently identified by various groups of researchers. The interest of these logics to the OWL community relies on their nice scalability properties for certain reasoning tasks of special interest for Semantic Web applications. The goal of this document is to present these logics as sub-langages of OWL 1.1 and to describe their computational properties. Their semantics is provided directly by the semantics of OWL 1.1 [OWL 1.1 Semantics].

In this document, the parts of the language with no effect on the semantics, such as annotations, will be omitted for simplicity. The parts of the OWL 1.1 specification concerning datatypes have also been omitted, since the tractability results depend on the ability to reason within the datatype theory in polynomial time.

2 EL++

EL++ [EL++] is a lightweight description logic that admits sound and complete reasoning in polytime. It is a syntactic fragment of OWL 1.1. The design goals behind EL++ were two-fold:

• capture the expressive power that is used by large-scale ontologies from practical applications
• have polytime reasoning problems, in particular classification and instance checking

EL++ achieves both goals by dropping the (allValusFrom) restriction, whereas (someValuesFrom) is retained. It should be noted, however, that EL++ does admit (objectPropertyRange), which can be seen as an important case of (allValuesFrom). Among the ontologies that fall within EL++ are the following:

• SNOMED CT, the Systematized Nomenclature of Medizine, Clinical Terms. SNOMED is a large-scale commercial ontology that underlies the standardized terminology of the health-care systems in the US, the UK, and a couple of other countries. It comprises about half a million classes. For more information, see [1] and [2].
• NCI. The Thesaurus of the National Cancer Institute. An ontology that formalizes terms related to cancer research. Like SNOMED, it is constantly updated and extended. Comprises about 50000 classes. For more info, see [3].

• The Gene Ontology formalizes terms relating to genes and gene products. Currently comprises some 25000 classes. For more info, see [4].

More than 95% of the axioms of the GALEN ontology [5] can also be expressed in EL++.

A polytime classification algorithm for EL++ ontologies has been implemented in the CEL reasoner [6], which is freely available. CEL is capable of classifying large-scale ontologies such as SNOMED in only a few minutes. Note that this refers to ontology classification, not querying of instance data. It is likely that, using database technology, querying instance data w.r.t. EL++ ontologies can be carried out even much more efficiently.

Other implementations of EL++ reasoning include the one by the Australian E-Health research center [7] and by Arity corporation [8], see also [9] for the latter.

There are a couple of different versions of EL++. As a fragment of OWL, there is a unique version of EL++ that comes up naturally, which is the one included in this document. More details on EL++ can be found in [EL++].

EL++ provides the following main features:

• someValuesFrom restrictions,
• conjunction
• concept disjointness,
• hasValue restrictions
• oneOf enumerations involving a single element,
• complex inclusions between object properties (where complex refers to the fact that property chains may be used on the left-hand side),
• reflexive properties,
• transitive properties,
• domain and range restrictions on properties,
• a limited form of datatypes, and
• general concept inclusion axioms (GCIs).

The following features of OWL 1.1 are known to cause intractability, when added to EL++:

• allValuesFrom restrictions,
• cardinality restrictions,
• union (and also DisjointUnion),
• negation,
• inverse properties,
• symmetric properties,
• functional and inverse-functional properties, and
• oneOf enumerations involving multiple elements.

In what follows, a full specification of EL++ is provided.

2.1 Classes and Object Properties

Entities are defined just as in OWL 1.1. The definition of objectPropertyExpression simplifies to

The classes owl:Thing and owl:Nothing are both admitted.

Missing w.r.t. OWL 1.1 DL: objectUnionOf, objectComplementOf, objectOneOf with multiple elements, objectAllValuesFrom, objectMaxCardinality, objectMinCardinality, objectExactCardinality.

2.2 Axioms

2.2.1 Class Axioms

Missing w.r.t. OWL 1.1 DL: disjointUnion.

2.2.2 Property Axioms

Missing w.r.t. OWL 1.1 DL: disjointObjectProperties, irreflexiveObjectProperty, inverseObjectProperties, functionalObjectProperty, symetricObjectProperty, asymetricObjectProperty.

2.3 Facts

Regarding facts, EL++ provides exactly the same facilities as OWL 1.1.

2.3.1 Class Assertions

2.3.2 Property Assertions

2.4 Nonstructural Restrictions on Axioms

To obtain polytime reasoning problems, the axiom closure of an EL++ ontology must obey a certain nonstructural restriction, which is defined next. The reason for this restriction is a subtle interaction between role inclusions and range restrictions, which has to be controlled. Let us say that an EL++ ontology entails the axiom ObjectPropertyRange(PE1 CE) if its axiom closure contains axioms

• SubObjectPropertyOf(PE1 PE2),...,SubObjectPropertyOf(PEk-1 PEk)
• ObjectPropertyRange(PEk CE)

Then the restriction is as follows:

If

• the ontology contains SubObjectPropertyOf(SubObjectPropertyChain(PE1 ... PEn) PE) and
• the ontology entails ObjectPropertyRange(PE CE)

then the ontology entails ObjectPropertyRange(PEn CE).

Observe that the restriction is vacuously tree if the SubObjectPropertyOf is a role inclusion statement, i.e., if it does not contain SubObjectPropertyChain.

Two more remarks seem appropriate:

• We do allow range restrictions on reflexive and transitive roles, unless they are used in axioms following the forbidden pattern above
• EL++ inherits the acyclicity condition on complex property inclusions imposed by OWL 1.1 DL. However, in contrast to OWL 1.1 DL, this condition could in principle be dropped without losing decidability or tractability. Still, we should adopt that condition to be a real (syntactic) fragment.

3 DL-Lite

DL-Lite is a fragment of OWL DL especially tailored for handling efficiently large number of facts [DL-Lite]. The main focus is to provide efficient query answering on the data and to allow the use of Relational Database Managment technologies for such a purpose.

DL-Lite also includes most of the main features of conceptual models, like UML class diagrams and ER diagrams. More specifically, DL-Lite includes the following features of OWL DL:

• a constrained form of someValuesFrom restrictions,
• conjunction,
• concept disjointness,
• domains and ranges of properties,
• inverse properties,
• inclusion axioms for object properties.

The language DL-Lite, as presented here, is indeed a fragment of both OWL 1.1. and OWL DL. There are different variants of DL-Lite that have been described in the literature. The variant provided here is called DL-Lite_R since it allows for property inclusion axioms and therefore it is a proper super-set of the RDFS fragment of OWL DL. Other variants trade property inclusion axioms for functionality and inverse-functionality of object properties.

3.1 Axioms

3.1.1 Class Axioms

3.1.2 Property Axioms

3.2 Facts

Regarding facts, DL-Lite provides exactly the same facilities as OWL 1.1.

3.2.1 Class Assertions

3.2.2 Property Assertions

4 Description Logic Programs (DLP)

Description Logic Programs [DLP] is a Horn fragment of OWL 1.1. The distinguishing feature of DLP is that it is an existential-free fragment; that is, while reasoning, the universe is fixed in the sense that one only needs to consider the objects explicitly used in the facts of the ontology. Since DLP can be considered as a fragment of Horn logic, there is a connection, at least syntactic, with Logic Programs. However, it should be understood that; the logical consequences that an OWL 1.1 reasoner would draw from a DLP ontology differs from the ones that would be obtained using an LP engine. Typically, LP reasoners adopt the closed world assumption and are, consequently, non-monotonic. OWL 1.1, however, is monotonic and adopts the open-world assumption. DLP, as presented in this document, adopts the semantics of OWL 1.1 and not the semantics of LP.

DLP is able to express the following features of OWL DL:

• concept disjointness,
• domains and ranges of properties,
• inverse and symmetric properties,
• functional and inverse-functional properties,
• subproperty and equivalence relations between object properties,
• transitive properties, and
• a limited form of General Concept Inclusion axioms (GCIs).

4.1 Axioms

4.1.1 Class Axioms

4.1.2 Property Axioms

4.2 Facts

DLP provides exactly the same facts as OWL 1.1.

4.2.1 Class Assertions

4.2.2 Property Assertions

5 Horn-SHIQ

[Horn-SHIQ] is a fragment of both Horn Logic and the Description Logic SHIQ. The Horn-SHIQ language is not a fragment of OWL DL, since it allows qualified cardinality restrictions. For simplicity and ease of presentation, the definition provided here of the language is slightly more restrictive than the one proposed in [Horn-SHIQ].

Horn-SHIQ provides the following expressivity of OWL 1.1:

• concept disjointness,
• inverse properties,
• symmetric properties,
• subproperty and equivalence relations between object properties, and
• restricted forms of GCIs.

5.1 Axioms

5.1.1 Class Axioms

5.1.2 Property Axioms

5.2 Facts

Horn-SHIQ provides exactly the same facts as OWL 1.1.

5.2.1 Class Assertions

5.2.2 Property Assertions

6 RDF Schema

RDF Schema allows the construction of RDF graphs that are not permitted in OWL 1.1. This section describes the language given by the set of all RDF Schema ontologies that are syntactically correct OWL 1.1 ontologies.The language provides the following features:

• domains and ranges of properties,
• object property inclusion axioms, and
• subclass and equivalence relationships between named classes.

The language does not allow complex class descriptions.

6.1 Classes and Object Properties

6.2 Axioms

6.2.1 Class Axioms

6.2.2 Property Axioms

6.3 Facts

Regarding facts, the language provides for class assertions and object property assertions.

6.3.1 Class Assertions

6.3.2 Property Assertions

7 Computational Properties

This section describes the computational complexity of the most relevant reasoning problems in the languages introduced so far. The reasoning problems considered here are the following:

• Ontology Consistency: Check whether a given ontology has at least one model.
• Concept Satisfiability: Given an ontology O and a class A, verify whether there is a model of O in which the interpretation of A is a non-empty set.
• Concept Subsumption: Given an ontology O and two classes A, B, verify whether the interpretation of A is a subset of the interpretation of B in every model of O
• Instance Checking: Given an ontology, an individual a and a class A, verify whether a is an instance of A in every model of the ontology.
• Conjunctive Query Answering: Given an ontology O and a conjunctive query q, return the answers of the query with respect to O.

Note that in languages that are propositionally closed (i.e. that provide, either implicitly or explicitly, conjunction, union and negation of class descriptions), such as OWL DL, OWL Lite and OWL 1.1, the problems of ontology consistency, concept satisfiability, concept subsumption and instance checking can be reduced to each other in polynomial time. However, none of the languages described in this document is propositionally closed and thus these reasoning problems may have different complexity and require diferent algorithmic solutions.

When evaluating the complexity, the following parameters will be considered:

• The Data Complexity: the complexity measured with respect to the number of facts in the ontology.
• The Taxonomic complexity: the complexity measured with respect to the size of the axioms in the ontology.
• The Query Complexity: the complexity measured with respect to the number of conjuncts in the conjunctive query.
• The Combined Complexity: the complexity measured with respect to both the size of the axioms and the number of facts. In the case of conjunctive query answering, the combined complexity also includes the query complexity.

Table 1 summarizes the known complexity results for OWL DL, OWL Lite, EL++, DL-Lite, Horn-SHIQ and RDF Schema. Whenever the complexity for a given problem is described as Open, with a star, (*), it is meant that its decidability is still an open question; if the star (*) is omitted, then the problem is known to be decidable but precise complexity bounds have not yet been established. If a problem is labeled as trivial, it is meant that the language is not expressive enough for allowing to different possible answers to the problem, e.g. every RDF Schema ontology is known to be consistent.

The fact that data complexity stays LOGSPACE, means that one can exploit relational database technology for instance checking and conjunctive query answering.The fact that data complexity goes beyond LOGSPACE means that query answering and instance checking require more powerful engines than the ones provided by relational database technologies. PTIME-hardness essentially requires Datalog technologies. For the CoNP cases, Disjunctive Datalog technologies could be adopted.

8 Relationships with Other Formalisms

Figure 1 shows the relationship between the different languages mentioned in this document, including OWL DL, OWL 1.1 and OWL Lite. Two languages L1, L2 are connected by an arrow L1-->L2 if L1 is polynomially reducible to L2. The reader should note that in most of the cases the reduction is trivial, since L1 is just a syntactic fragment of L2 and thus every syntactically valid ontology written in L1 is also valid in L2. However,if L2 is OWL Lite, the reduction requires some work, since some of the constructs available in DL-Lite are not explicitly provided by OWL Lite. The reader should note that the absence of an arrow does not indicate that there is no reduction, not even that there is no easy one.

9 References

[OWL 1.1 Specification]

OWL 1.1 Web Ontology Language: Structural Specification and Functional-Style Syntax. Peter F. Patel-Schneider, Ian Horrocks, and Boris Motik, eds., 2006.

[Description Logics]

The Description Logic Handbook. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, Peter Patel-Schneider, editors. Cambridge University Press, 2003; and Description Logics Home Page.

[OWL 1.1 Semantics]

OWL 1.1 Web Ontology Language: Model-Theoretic Semantics. Bernardo Cuenca Grau and Boris Motik, eds., 2006.

[OWL Abstract Syntax and Semantics]

OWL Web Ontology Language Semantics and Abstract Syntax. Peter F. Patel-Schneider, Pat Hayes, and Ian Horrocks, eds., W3C Recommendation, 10 February 2004

[EL++]

Pushing the EL Envelope. Franz Baader, Sebastian Brandt, and Carsten Lutz. In Proc. of the 19th Joint Int. Conf. on Artificial Intelligence (IJCAI 2005), 2005.

[DLP]

Description Logic Programs: Combining Logic Programs with Description Logics. Benjamin Grosof, Raphael Volz, Ian Horrocks and Stefan Decker. In Proc. of the 12th International World Wide Web Conference (WWW 2003), 2003.

[Horn-SHIQ]

Data Complexity in Very Expressive Description Logics. Ullrich Hustand, Boris Motik, and Ulrike Sattler. In Proc. of the 19th Joint Int. Conf. on Artificial Intelligence (IJCAI 2005), 2005.

[DL-Lite]

Tailoring OWL for Data Intensive Ontologies. Diego Calvanese, Giuseppe de Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati. In Proceedings of the 1st OWL: Experiences and Directions Workshop (OWL-ED 2005), 2005.

[Complexity]

Complexity Results and Practical Algorithms for Logics in Knowledge Representation. Stephan Tobies. Ph.D Dissertation, 2002