Description logic (DL) is a family of formal knowledge representation languages. It is more expressive than propositional logic but has more efficient decision problems than first-order predicate logic.

DL is used in artificial intelligence for formal reasoning on the concepts of an application domain (known as terminological knowledge). It is of particular importance in providing a logical formalism for ontologies and the Semantic Web. The most notable application outside information science is in bioinformatics where DL assists in the codification of medical knowledge.

Introduction[link]

A Description Logic (DL) models concepts, roles and individuals, and their relationships.

The fundamental modeling concept of a DL is the axiom - a logical statement relating roles and/or concepts.^[1] This is a key difference from the frames paradigm where a frame specification declares and completely defines a class.^[1]

Nomenclature[link]

Differences from OWL[link]

Naming convention[link]

There are many varieties of Description Logic and there is an informal naming convention, roughly describing the operators allowed. The expressivity is encoded in the label for a logic starting with one of the following basic logics:

Followed by any of the following extensions:

Exceptions[link]

Some canonical DLs that do not exactly fit this convention are:

with transitive roles.

without atomic negation.

Examples[link]

As an example, Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC}

is a centrally important description logic from which comparisons with other varieties can be made. Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC}
is simply Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{AL}
with complement of any concept allowed, not just atomic concepts.

A further example, the description logic Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHIQ}

is the logic Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC}
plus  extended cardinality restrictions, and transitive and inverse roles. The naming conventions aren't purely systematic so that the logic Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALCOIN}
might be referred to as Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALCNIO}
and abbreviations are made where possible, Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC}
is used instead of the equivalent Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALUE}

.

The Protégé ontology editor supports Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHOIN}^\mathcal{(D)} . Three major bioinformatic terminology bases, Snomed, Galen, and GO, are expressible in Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{EL}

(with additional role properties).

OWL 2 provides the expressiveness of Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SROIQ}^\mathcal{(D)} , OWL-DL is based on Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHOIN}^\mathcal{(D)} , and for OWL-Lite it is Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHIF}^\mathcal{(D)} .

History[link]

Description logic (DL) was given its current name in the 1980s. Previous to this it was called (chronologically): terminological systems, and concept languages.

Knowledge representation[link]

Frames and semantic networks lack formal (logic-based) semantics.^[4] DL was first introduced into Knowledge Representation (KR) systems to overcome this deficiency.^[4]

The first DL-based KR system was KL-ONE (by Ronald J. Brachman and Schmolze, 1985). During the '80s other DL-based systems using structural subsumption algorithms^[4] were developed including KRYPTON (1983), LOOM (1987), BACK (1988), K-REP (1991) and CLASSIC (1991). This approach featured DL with limited expressiveness but relatively efficient (polynomial time) reasoning.^[4]

In the early '90s, the introduction of a new tableau based algorithm paradigm allowed efficient reasoning on more expressive DL.^[4] DL-based systems using these algorithms - such as KRIS (1991) - show acceptable reasoning performance on typical inference problems even though the worst case complexity is no longer polynomial.^[4]

From the mid '90s, reasoners were created with good practical performance on very expressive DL with high worst case complexity.^[4] Examples from this period include FaCT,^[5] RACER (2001), CEL (2005), and KAON 2 (2005).

DL reasoners, such as FaCT, FaCT++,^[5] RACER, DLP and Pellet,^[6] implement the analytic tableau method. KAON2 is implemented by algorithms which reduce a SHIQ(D) knowledge base to a disjunctive datalog program.

Semantic Web[link]

The DARPA Agent Markup Language (DAML) and Ontology Inference Layer (OIL) ontology languages for the semantic web can be viewed as syntactic variants of DL.^[7] In particular, the formal semantics and reasoning in OIL use the Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHIQ}

DL.[8] The DAML+OIL DL was developed as a submission to[9] - and formed the starting point of - the World Wide Web Consortium (W3C) Web Ontology Working Group.[10] In 2004, the Web Ontology Working Group completed its work by issuing the OWL[11] recommendation. The design of OWL is based on the Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SH}
family of DL[12] with OWL DL and OWL Lite based on Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHOIN}^\mathcal{(D)}
and Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SHIF}^\mathcal{(D)}
respectively.[12]

The W3C OWL Working Group began work in 2007 on a refinement of - and extension to - OWL.^[13] In 2009, this was completed by the issuance of the OWL2 recommendation.^[14] OWL2 is based on the description logic Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{SROIQ}^\mathcal{(D)} .^[15] Practical experience demonstrated that OWL DL lacked several key features necessary to model complex domains.^[1]

Modeling[link]

In DL, a distinction is drawn between the so-called TBox (terminological box) and the ABox (assertional box). In general, the TBox contains sentences describing concept hierarchies (i.e., relations between concepts) while the ABox contains ground sentences stating where in the hierarchy individuals belong (i.e., relations between individuals and concepts). For example, the statement:

(1) Every employee is a person

belongs in the TBox, while the statement:

(2) Bob is an employee

belongs in the ABox.

Note that the TBox/ABox distinction is not significant, in the same sense that the two "kinds" of sentences are not treated differently in first-order logic (which subsumes most DL). When translated into first-order logic, a subsumption axiom like (1) is simply a conditional restriction to unary predicates (concepts) with only variables appearing in it. Clearly, a sentence of this form is not privileged or special over sentences in which only constants ("grounded" values) appear like (2).

So why was the distinction introduced? The primary reason is that the separation can be useful when describing and formulating decision-procedures for various DL. For example, a reasoner might process the TBox and ABox separately, in part because certain key inference problems are tied to one but not the other one ('classification' is related to the TBox, 'instance checking' to the ABox). Another example is that the complexity of the TBox can greatly affect the performance of a given decision-procedure for a certain DL, independently of the ABox. Thus, it is useful to have a way to talk about that specific part of the knowledge base.

The secondary reason is that the distinction can make sense from the knowledge base modeler's perspective. It is plausible to distinguish between our conception of terms/concepts in the world (class axioms in the TBox) and particular manifestations of those terms/concepts (instance assertions in the ABox). In the above example: when the hierarchy within a company is the same in every branch but the assignment to employees is different in every department (because there are other people working there), this distinction makes sense to reuse the TBox for different branches.

There are two features of Description Logic that are not shared by most other data description formalisms: DL does not make the Unique Name Assumption (UNA) or the Closed World Assumption (CWA). Not having UNA means that two concepts with different names may be allowed by some inference to be shown to be equivalent. Not having CWA, or rather having the Open World Assumption (OWA) means that lack of knowledge of a fact does not immediately imply knowledge of the negation of a fact.

Formal description[link]

Like first order logic (FOL), a syntax defines which collections of symbols are legal expressions in a Description Logic (DL), and semantics determine meaning. Unlike FOL, a DL may have several well known syntactic variants.^[7]

Syntax[link]

The syntax of a member of the description logic family is characterized by its recursive definition, in which the constructors that can be used to form concept terms are stated. Some constructors are related to logical constructors in first-order logic (FOL) such as intersection or conjunction of concepts, union or disjunction of concepts, negation or complement of concepts, universal restriction and existential restriction. Other constructors have no corresponding construction in FOL including restrictions on roles for example, inverse, transitivity and functionality.

Notation[link]

Let C and D be concepts, a and b be individuals, and R be a role.

The description logic ALC[link]

The prototypical DL Attributive Concept Language with Complements (Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC} ) was introduced by Manfred Schmidt-Schauß and Gert Smolka in 1991, and is the basis of many more expressive DL.^[4] The following definitions follow the treatment in Baader et al.^[4]

Let Failed to parse (Missing texvc executable; please see math/README to configure.): N_C , Failed to parse (Missing texvc executable; please see math/README to configure.): N_R

and Failed to parse (Missing texvc executable; please see math/README to configure.): N_O
 be (respectively) sets of concept names (also known as atomic concepts), role names and individual names (also known as individuals, nominals or objects). Then the ordered triple (Failed to parse (Missing texvc executable; please see math/README to configure.): N_C

, Failed to parse (Missing texvc executable; please see math/README to configure.): N_R , Failed to parse (Missing texvc executable; please see math/README to configure.): N_O

) is the signature.

Concepts[link]

The set of Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{ALC}

concepts is the smallest set such that:

• The following are concepts:
  • Failed to parse (Missing texvc executable; please see math/README to configure.): \top

(top is a concept)

• • Failed to parse (Missing texvc executable; please see math/README to configure.): \bot

(bottom is a concept)

• • Every Failed to parse (Missing texvc executable; please see math/README to configure.): A \in N_C

(all atomic concepts are concepts)

• If Failed to parse (Missing texvc executable; please see math/README to configure.): C

and Failed to parse (Missing texvc executable; please see math/README to configure.): D
are concepts and Failed to parse (Missing texvc executable; please see math/README to configure.): R \in N_R
then the following are concepts:

• • Failed to parse (Missing texvc executable; please see math/README to configure.): C\sqcap D

(the intersection of two concepts is a concept)

• • Failed to parse (Missing texvc executable; please see math/README to configure.): C\sqcup D

(the union of two concepts is a concept)

• • Failed to parse (Missing texvc executable; please see math/README to configure.): \neg C

(the complement of a concept is a concept)

• • Failed to parse (Missing texvc executable; please see math/README to configure.): \forall R.C

(the universal restriction of a concept by a role is a concept)

• • Failed to parse (Missing texvc executable; please see math/README to configure.): \exists R.C

(the existential restriction of a concept by a role is a concept)

Terminological axioms[link]

A general concept inclusion (GCI) has the form Failed to parse (Missing texvc executable; please see math/README to configure.): C \sqsubseteq D

where Failed to parse (Missing texvc executable; please see math/README to configure.): C
and Failed to parse (Missing texvc executable; please see math/README to configure.): D
are concepts. Write Failed to parse (Missing texvc executable; please see math/README to configure.): C \equiv D
when Failed to parse (Missing texvc executable; please see math/README to configure.): C \sqsubseteq D
and Failed to parse (Missing texvc executable; please see math/README to configure.): D \sqsubseteq C

. A TBox is any finite set of GCIs.

Assertional axioms[link]

• A concept assertion is a statement of the form Failed to parse (Missing texvc executable; please see math/README to configure.): a : C

where  Failed to parse (Missing texvc executable; please see math/README to configure.): a \in N_O
and C is a concept.

• A role assertion is a statement of the form Failed to parse (Missing texvc executable; please see math/README to configure.): (a, b) : R

where Failed to parse (Missing texvc executable; please see math/README to configure.): a, b \in N_O
 and R is a role.

An ABox is a finite set of assertional axioms.

Knowledge base[link]

A knowledge base (KB) is an ordered pair Failed to parse (Missing texvc executable; please see math/README to configure.): (\mathcal{T}, \mathcal{A})

for TBox Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{T}
and ABox Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{A}

.

Semantics[link]

The semantics of description logic are defined by interpreting concepts as sets of individuals and roles as sets of ordered pairs of individuals. Those individuals are typically assumed from a given domain. The semantics of non atomic concepts and roles is then defined in terms of atomic concepts and roles. This is done by using a recursive definition similar to the syntax.

The description logic ALC[link]

The following definitions follow the treatment in Baader et al.^[4]

A terminological interpretation Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I}=(\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}})

over a signature Failed to parse (Missing texvc executable; please see math/README to configure.): (N_C,N_R,N_O)
consists of

• a non-empty set Failed to parse (Missing texvc executable; please see math/README to configure.): \Delta^{\mathcal{I}}

called the domain

• a interpretation function Failed to parse (Missing texvc executable; please see math/README to configure.): \cdot^{\mathcal{I}}

that maps:

• • every individual Failed to parse (Missing texvc executable; please see math/README to configure.): a

to an element Failed to parse (Missing texvc executable; please see math/README to configure.): a^{\mathcal{I}} \in \Delta^{\mathcal{I}}

• • every concept to a subset of Failed to parse (Missing texvc executable; please see math/README to configure.): \Delta^{\mathcal{I}}

• • every role name to a subset of Failed to parse (Missing texvc executable; please see math/README to configure.): \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}

such that

• Failed to parse (Missing texvc executable; please see math/README to configure.): \top^{\mathcal{I}} = \Delta^{\mathcal{I}}

• Failed to parse (Missing texvc executable; please see math/README to configure.): \bot^{\mathcal{I}} = \emptyset

• Failed to parse (Missing texvc executable; please see math/README to configure.): (C \sqcup D)^{\mathcal{I}} = C^{\mathcal{I}} \cup D^{\mathcal{I}}

(union means disjunction)

• Failed to parse (Missing texvc executable; please see math/README to configure.): (C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}

(intersection means conjunction)

• Failed to parse (Missing texvc executable; please see math/README to configure.): (\neg C)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus C^{\mathcal{I}}

(complement means negation)

• Failed to parse (Missing texvc executable; please see math/README to configure.): (\forall R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} | \texttt{for} \; \texttt{every} \; y, (x,y) \in R^{\mathcal{I}} \; \texttt{implies} \; y \in C^{\mathcal{I}} \}

• Failed to parse (Missing texvc executable; please see math/README to configure.): (\exists R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} | \texttt{there} \; \texttt{exists} \; y, (x,y) \in R^{\mathcal{I}} \; \texttt{and} \; y \in C^{\mathcal{I}}\}

Define Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models

(read I models) as follows

TBox[link]

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models C \sqsubseteq D

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): C^{\mathcal{I}} \subseteq D^{\mathcal{I}}

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models \mathcal{T}

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models t
for every Failed to parse (Missing texvc executable; please see math/README to configure.): t \in \mathcal{T}

ABox[link]

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models a : C

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): a^{\mathcal{I}} \in C^{\mathcal{I}}

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models (a,b) : R

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): (a^{\mathcal{I}},b^{\mathcal{I}}) \in R^{\mathcal{I}}

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models \mathcal{A}

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models a
for every Failed to parse (Missing texvc executable; please see math/README to configure.): a \in \mathcal{A}

Knowledge base[link]

Let Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{K} = (\mathcal{T}, \mathcal{A})

be a knowledge base.

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models \mathcal{K}

if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models \mathcal{T}
and Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{I} \models \mathcal{A}

Inference[link]

Decision problems[link]

In addition to the ability to describe concepts formally, one also would like to employ the description of a set of concepts to ask questions about the concepts and instances described. The most common decision problems are basic database-query-like questions like instance checking (is a particular instance (member of an A-box) a member of a given concept) and relation checking (does a relation/role hold between two instances, in other words does a have property b), and the more global-database-questions like subsumption (is a concept a subset of another concept), and concept consistency (is there no contradiction among the definitions or chain of definitions). The more operators one includes in a logic and the more complicated the T-box (having cycles, allowing non-atomic concepts to include each other), usually the higher the computational complexity is for each of these problems (see Navigator on Description Logic Complexity for examples).

Relationship with other logic[link]

First order logic[link]

Many Description Logic models (DLs) are decidable fragments of first order logic (FOL).^[4] Some DLs now include operations (for example, transitive closure of roles) that allow efficient inference but cannot be expressed in FOL.^[4]

Fuzzy description logic[link]

Fuzzy description logic combines fuzzy logic with DLs. Since many concepts that are needed for intelligent systems lack well defined boundaries, or precisely defined criteria of membership, fuzzy logic is needed to deal with notions of vagueness and imprecision. This offers a motivation for a generalization of description logic towards dealing with imprecise and vague concepts.

Modal logic[link]

Description Logic is related to — but developed independently of — modal logic (ML).^[4] Many - but not all - DL are syntactic variants of ML.^[4]

Examples[link]

Temporal description logic[link]

Temporal description logic represents - and allows reasoning about - time dependent concepts and many different approaches to this problem exist.^[16] For example, a description logic might be combined with a modal temporal logic such as Linear temporal logic.

See also[link]

	Computer Science portal
	Logic portal
	Information science portal

• Formal concept analysis
• Lattice (order)
• Semantic parameterization
• Semantic reasoner
• SWRL

Notes[link]

References[link]

• F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003. ISBN 0-521-78176-0
• Ian Horrocks, Ulrike Sattler: Ontology Reasoning in the SHOQ(D) Description Logic, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.
• D. Fensel, F. van Harmelen, I. Horrocks, D. McGuinness, and P. F. Patel-Schneider: OIL: An Ontology Infrastructure for the Semantic Web. IEEE Intelligent Systems, 16(2):38-45, 2001.
• Ian Horrocks and Peter F. Patel-Schneider: The Generation of DAML+OIL. In Proceedings of the 2001 Description Logic Workshop (DL 2001), volume 49 of CEUR <http://ceur-ws.org/>, pages 30–35, 2001.
• 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):7-26, 2003.
• Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, and Ulrike Sattler: OWL 2: The next step for OWL. Journal of Web Semantics, 6(4):309-322, November 2008.
• Franz Baader, Ian Horrocks, and Ulrike Sattler: Chapter 3 Description Logics. In Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter, editors, Handbook of Knowledge Representation. Elsevier, 2007.
• Alessandro Artale and Enrico Franconi: Temporal Description Logics. In Handbook of Temporal Reasoning in Artificial Intelligence, 2005.
• Web Ontology (WebONT) Working Group Charter. W3C, 2003
• World Wide Web Consortium Issues RDF and OWL Recommendations. Press Release. W3C, 2004.
• OWL Working Group Charter. W3C, 2007.
• OWL 2 Connects the Web of Knowledge with the Web of Data. Press Release. W3C, 2009.

Further reading[link]

• Markus Krötzsch, František Simančík, Ian Horrocks: A Description Logic Primer. CoRR abs/1201.4089. 2012. (PDF) A very first introduction for readers without a formal logic background.
• Sebastian Rudolph: Foundations of Description Logics. In Reasoning Web: Semantic Technologies for the Web of Data, 7th International Summer School, volume 6848 of Lecture Notes in Computer Science, pages 76–136. Springer, 2011. (springerlink)Introductory text with a focus on modelling and formal semantics. There are also slides.
• Franz Baader: Description Logics. In Reasoning Web: Semantic Technologies for Information Systems, 5th International Summer School, volume 5689 of Lecture Notes in Computer Science, pages 1–39. Springer, 2009. (springerlink) Introductory text with a focus on reasoning and language design, and an extended historical overview.
• Enrico Franconi: Introduction to Description Logics. Course materials. Faculty of Computer Science, Free University of Bolzano, Italy, 2002. Lecture slides and many literature pointers, somewhat dated.
• Ian Horrocks: Ontologies and the Semantic Web. Communications of the ACM, 51(12):58-67, December 2008. A general overview of knowledge representation in Semantic Web technologies.

External links[link]

• Description Logics, the official web page of the community
• Navigator on Description Logic Complexity at the University of Manchester
• A list of DL reasoners at the University of Manchester

Tools[link]

Reasoners

There are some reasoners that deal with OWL and Description Logic. These are some of the most popular:

• CEL is a free (for non-commercial use) LISP-based reasoner
• Cerebra Engine was a commercial C++-based reasoner, acquired in 2006 by webMethods.
• FaCT++ is a free open-source C++-based reasoner.
• KAON2 is a free (free for non-commercial usage) Java reasoner.
• MSPASS is a free open-source C reasoner for numerous description logic models.
• Pellet is a dual-licensed (AGPL and proprietary) commercial, Java-based reasoner.
• RacerPro of Racer Systems is a commercial (free trials and research licenses are available) lisp-based reasoner.
• Sim-DL is a free open-source Java-based reasoner for the language ALCHQ. It also provides a similarity measurement functionality between concepts. To access this functionality a Protégé plugin can be used.
• HermiT is an open source reasoner based on the hypertableaux calculus. It is developed by the University of Oxford.

Editors

• Protégé is a free, open source ontology editor and knowledge-base framework, which can use DL reasoners which offer a DIG interface as backends for consistency checks.
• SWOOP is an open source ontology editor originally developed at the University of Maryland.

Interfaces

• DIG Implementation. DIG is an XML interface to DL systems, recommended by the DL Implementation Group. DIG 2.0 is an ongoing effort for a new DIG interface standard.
• OWL API is an open source Java interface to the W3C Web Ontology Language OWL developed by the University Of Manchester