Description logic

The description logic community uses different terminology than the first-order logic (FOL) community for operationally equivalent notions; some examples are given below. The Web Ontology Language (OWL) uses again a different terminology, also given in the table below.

There are many varieties of description logics 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:

${\displaystyle {\mathcal {AL}}}$	Attributive language. This is the base language which allows:
	Atomic negation (negation of concept names that do not appear on the left-hand side of axioms) Concept intersection Universal restrictions Limited existential quantification
${\displaystyle {\mathcal {FL}}}$	Frame based description language,[3] allows:
	Concept intersection Universal restrictions Limited existential quantification Role restriction
${\displaystyle {\mathcal {EL}}}$	Existential language, allows:
	Concept intersection Existential restrictions (of full existential quantification)

Followed by any of the following extensions:

${\displaystyle {\mathcal {F}}}$	Functional properties, a special case of uniqueness quantification.
${\displaystyle {\mathcal {E}}}$	Full existential qualification (existential restrictions that have fillers other than ${\displaystyle \top }$).
${\displaystyle {\mathcal {U}}}$	Concept union.
${\displaystyle {\mathcal {C}}}$	Complex concept negation.
${\displaystyle {\mathcal {H}}}$	Role hierarchy (subproperties: rdfs:subPropertyOf).
${\displaystyle {\mathcal {R}}}$	Limited complex role inclusion axioms; reflexivity and irreflexivity; role disjointness.
${\displaystyle {\mathcal {O}}}$	Nominals. (Enumerated classes of object value restrictions: owl:oneOf, owl:hasValue).
${\displaystyle {\mathcal {I}}}$	Inverse properties.
${\displaystyle {\mathcal {N}}}$	Cardinality restrictions (owl:cardinality, owl:maxCardinality), a special case of counting quantification
${\displaystyle {\mathcal {Q}}}$	Qualified cardinality restrictions (available in OWL 2, cardinality restrictions that have fillers other than ${\displaystyle \top }$).
${\displaystyle ^{\mathcal {(D)}}}$	Use of datatype properties, data values or data types.

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

${\displaystyle {\mathcal {S}}}$	An abbreviation for ${\displaystyle {\mathcal {ALC}}}$ with transitive roles.
${\displaystyle {\mathcal {FL^{-}}}}$	A sub-language of ${\displaystyle {\mathcal {FL}}}$, which is obtained by disallowing role restriction. This is equivalent to ${\displaystyle {\mathcal {AL}}}$ without atomic negation.
${\displaystyle {\mathcal {FL}}_{o}}$	A sub-language of ${\displaystyle {\mathcal {FL^{-}}}}$, which is obtained by disallowing limited existential quantification.
${\displaystyle {\mathcal {EL^{++}}}}$	Alias for ${\displaystyle {\mathcal {ELRO}}}$.[4]

As an example, ${\displaystyle {\mathcal {ALC}}}$ is a centrally important description logic from which comparisons with other varieties can be made. ${\displaystyle {\mathcal {ALC}}}$ is simply ${\displaystyle {\mathcal {AL}}}$ with complement of any concept allowed, not just atomic concepts. ${\displaystyle {\mathcal {ALC}}}$ is used instead of the equivalent ${\displaystyle {\mathcal {ALUE}}}$.

A further example, the description logic ${\displaystyle {\mathcal {SHIQ}}}$ is the logic ${\displaystyle {\mathcal {ALC}}}$ plus extended cardinality restrictions, and transitive and inverse roles. The naming conventions aren't purely systematic so that the logic ${\displaystyle {\mathcal {ALCOIN}}}$ might be referred to as ${\displaystyle {\mathcal {ALCNIO}}}$ and other abbreviations are also made where possible.

The Protégé ontology editor supports ${\displaystyle {\mathcal {SHOIN}}^{\mathcal {(D)}}}$. Three major biomedical informatics terminology bases, SNOMED CT, GALEN, and GO, are expressible in ${\displaystyle {\mathcal {EL}}}$ (with additional role properties).

OWL 2 provides the expressiveness of ${\displaystyle {\mathcal {SROIQ}}^{\mathcal {(D)}}}$, OWL-DL is based on ${\displaystyle {\mathcal {SHOIN}}^{\mathcal {(D)}}}$, and for OWL-Lite it is ${\displaystyle {\mathcal {SHIF}}^{\mathcal {(D)}}}$.

Frames and semantic networks lack formal (logic-based) semantics.[5] DL was first introduced into knowledge representation (KR) systems to overcome this deficiency.[5]

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[5] 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.[5]

In the early '90s, the introduction of a new tableau based algorithm paradigm allowed efficient reasoning on more expressive DL.[5] 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.[5]

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

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

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.[8] In particular, the formal semantics and reasoning in OIL use the ${\displaystyle {\mathcal {SHIQ}}}$ DL.[9] The DAML+OIL DL was developed as a submission to[10]—and formed the starting point of—the World Wide Web Consortium (W3C) Web Ontology Working Group.[11] In 2004, the Web Ontology Working Group completed its work by issuing the OWL[12] recommendation. The design of OWL is based on the ${\displaystyle {\mathcal {SH}}}$ family of DL[13] with OWL DL and OWL Lite based on ${\displaystyle {\mathcal {SHOIN}}^{\mathcal {(D)}}}$ and ${\displaystyle {\mathcal {SHIF}}^{\mathcal {(D)}}}$ respectively.[13]

The W3C OWL Working Group began work in 2007 on a refinement of - and extension to - OWL.[14] In 2009, this was completed by the issuance of the OWL2 recommendation.[15] OWL2 is based on the description logic ${\displaystyle {\mathcal {SROIQ}}^{\mathcal {(D)}}}$.[16] Practical experience demonstrated that OWL DL lacked several key features necessary to model complex domains.[2]

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.

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

If a is R-related to b, then b is called an R-successor of a.

Conventional Notation

Symbol	Description	Example	Read
${\displaystyle \top }$	⊤ is a special concept with every individual as an instance	${\displaystyle \top }$	top
${\displaystyle \bot }$	empty concept	${\displaystyle \bot }$	bottom
${\displaystyle \sqcap }$	intersection or conjunction of concepts	${\displaystyle C\sqcap D}$	C and D
${\displaystyle \sqcup }$	union or disjunction of concepts	${\displaystyle C\sqcup D}$	C or D
${\displaystyle \neg }$	negation or complement of concepts	${\displaystyle \neg C}$	not C
${\displaystyle \forall }$	universal restriction	${\displaystyle \forall R.C}$	all R-successors are in C
${\displaystyle \exists }$	existential restriction	${\displaystyle \exists R.C}$	an R-successor exists in C
${\displaystyle \sqsubseteq }$	Concept inclusion	${\displaystyle C\sqsubseteq D}$	all C are D
${\displaystyle \equiv }$	Concept equivalence	${\displaystyle C\equiv D}$	C is equivalent to D
${\displaystyle {\dot {=}}}$	Concept definition	${\displaystyle C{\dot {=}}D}$	C is defined to be equal to D
${\displaystyle$ :}	Concept assertion	${\displaystyle a:C}$	a is a C
${\displaystyle$ :}	Role assertion	${\displaystyle (a,b):R}$	a is R-related to b

The prototypical DL Attributive Concept Language with Complements (${\displaystyle {\mathcal {ALC}}}$) was introduced by Manfred Schmidt-Schauß and Gert Smolka in 1991, and is the basis of many more expressive DLs.[5] The following definitions follow the treatment in Baader et al.[5]

Let ${\displaystyle N_{C}}$, ${\displaystyle N_{R}}$ and ${\displaystyle 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 (${\displaystyle N_{C}}$, ${\displaystyle N_{R}}$, ${\displaystyle N_{O}}$) is the signature.

The set of ${\displaystyle {\mathcal {ALC}}}$ concepts is the smallest set such that:

• The following are concepts:
  • ${\displaystyle \top }$ (top is a concept)
  • ${\displaystyle \bot }$ (bottom is a concept)
  • Every ${\displaystyle A\in N_{C}}$ (all atomic concepts are concepts)
• If ${\displaystyle C}$ and ${\displaystyle D}$ are concepts and ${\displaystyle R\in N_{R}}$ then the following are concepts:
  • ${\displaystyle C\sqcap D}$ (the intersection of two concepts is a concept)
  • ${\displaystyle C\sqcup D}$ (the union of two concepts is a concept)
  • ${\displaystyle \neg C}$ (the complement of a concept is a concept)
  • ${\displaystyle \forall R.C}$ (the universal restriction of a concept by a role is a concept)
  • ${\displaystyle \exists R.C}$ (the existential restriction of a concept by a role is a concept)

A general concept inclusion (GCI) has the form ${\displaystyle C\sqsubseteq D}$ where ${\displaystyle C}$ and ${\displaystyle D}$ are concepts. Write ${\displaystyle C\equiv D}$ when ${\displaystyle C\sqsubseteq D}$ and ${\displaystyle D\sqsubseteq C}$. A TBox is any finite set of GCIs.

• A concept assertion is a statement of the form ${\displaystyle a:C}$ where ${\displaystyle a\in N_{O}}$ and C is a concept.
• A role assertion is a statement of the form ${\displaystyle (a,b):R}$ where ${\displaystyle a,b\in N_{O}}$ and R is a role.

An ABox is a finite set of assertional axioms.

A knowledge base (KB) is an ordered pair ${\displaystyle ({\mathcal {T}},{\mathcal {A}})}$ for TBox ${\displaystyle {\mathcal {T}}}$ and ABox ${\displaystyle {\mathcal {A}}}$.

The semantics of description logics 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 following definitions follow the treatment in Baader et al.[5]

A terminological interpretation ${\displaystyle {\mathcal {I}}=(\Delta ^{\mathcal {I}},\cdot ^{\mathcal {I}})}$ over a signature ${\displaystyle (N_{C},N_{R},N_{O})}$ consists of

• a non-empty set ${\displaystyle \Delta ^{\mathcal {I}}}$ called the domain
• a interpretation function ${\displaystyle \cdot ^{\mathcal {I}}}$ that maps:
  • every individual ${\displaystyle a}$ to an element ${\displaystyle a^{\mathcal {I}}\in \Delta ^{\mathcal {I}}}$
  • every concept to a subset of ${\displaystyle \Delta ^{\mathcal {I}}}$
  • every role name to a subset of ${\displaystyle \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$

such that

• ${\displaystyle \top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}}$
• ${\displaystyle \bot ^{\mathcal {I}}=\emptyset }$
• ${\displaystyle (C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}}$ (union means disjunction)
• ${\displaystyle (C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}}$ (intersection means conjunction)
• ${\displaystyle (\neg C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\setminus C^{\mathcal {I}}}$ (complement means negation)
• ${\displaystyle (\forall R.C)^{\mathcal {I}}=\{x\in \Delta ^{\mathcal {I}}|{\text{for}}\;{\text{every}}\;y,(x,y)\in R^{\mathcal {I}}\;{\text{implies}}\;y\in C^{\mathcal {I}}\}}$
• ${\displaystyle (\exists R.C)^{\mathcal {I}}=\{x\in \Delta ^{\mathcal {I}}|{\text{there}}\;{\text{exists}}\;y,(x,y)\in R^{\mathcal {I}}\;{\text{and}}\;y\in C^{\mathcal {I}}\}}$

Define ${\displaystyle {\mathcal {I}}\models }$ (read in I holds) as follows

• ${\displaystyle {\mathcal {I}}\models C\sqsubseteq D}$ if and only if ${\displaystyle C^{\mathcal {I}}\subseteq D^{\mathcal {I}}}$
• ${\displaystyle {\mathcal {I}}\models {\mathcal {T}}}$ if and only if ${\displaystyle {\mathcal {I}}\models \Phi }$ for every ${\displaystyle \Phi \in {\mathcal {T}}}$

• ${\displaystyle {\mathcal {I}}\models a:C}$ if and only if ${\displaystyle a^{\mathcal {I}}\in C^{\mathcal {I}}}$
• ${\displaystyle {\mathcal {I}}\models (a,b):R}$ if and only if ${\displaystyle (a^{\mathcal {I}},b^{\mathcal {I}})\in R^{\mathcal {I}}}$
• ${\displaystyle {\mathcal {I}}\models {\mathcal {A}}}$ if and only if ${\displaystyle {\mathcal {I}}\models \phi }$ for every ${\displaystyle \phi \in {\mathcal {A}}}$

Let ${\displaystyle {\mathcal {K}}=({\mathcal {T}},{\mathcal {A}})}$ be a knowledge base.

• ${\displaystyle {\mathcal {I}}\models {\mathcal {K}}}$ if and only if ${\displaystyle {\mathcal {I}}\models {\mathcal {T}}}$ and ${\displaystyle {\mathcal {I}}\models {\mathcal {A}}}$

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 ABox) 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 TBox (having cycles, allowing non-atomic concepts to include each other), usually the higher the computational complexity is for each of these problems (see Description Logic Complexity Navigator for examples).

Many DLs are decidable fragments of first-order logic (FOL)[5] and are usually fragments of two-variable logic or guarded logic. In addition, some DLs have features that are not covered in FOL; this includes concrete domains (such as integer or strings, which can be used as ranges for roles such as hasAge or hasName) or an operator on roles for the transitive closure of that role.[5]

Fuzzy description logics 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.

Description logic is related to—but developed independently of—modal logic (ML).[5] Many—but not all—DLs are syntactic variants of ML.[5]

In general, an object corresponds to a possible world, a concept corresponds to a modal proposition, and a role-bounded quantifier to a modal operator with that role as its accessibility relation.

Operations on roles (such as composition, inversion, etc.) correspond to the modal operations used in dynamic logic.[17]

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

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

• CEL is an open source LISP-based reasoner (Apache 2.0 License).
• 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 (for non-commercial use) Java-based reasoner, offering fast reasoning support for OWL ontologies.
• MSPASS is a free open-source C reasoner for numerous DL models.
• Pellet is a dual-licensed (AGPL and proprietary) commercial, Java-based reasoner.
• RacerPro of Racer Systems was a commercial (free trials and research licenses are available) lisp-based reasoner, today both an open source version of RACER exists from the original developers at Lübeck University using the BSD 3 license, and also a commercialized version, still named RacerPro by Franz Inc.
• 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 "hypertableau" calculus. It is developed by the University of Oxford.
• Owlready2 is a package for ontology-oriented programming in Python. It can load OWL 2.0 ontologies as Python objects, modify them, save them, and perform reasoning via HermiT (included). Owlready2 allows a transparent access to OWL ontologies (contrary to usual Java-based API).

• Protégé is a free, open-source ontology editor and a knowledge base framework, which can use DL reasoners offering DIG Interface as a back end for consistency checks.
• SWOOP on GitHub, an OWL browser/editor that takes the standard web browser as the basic UI paradigm.

• DIG Interface on SourceForge.net, a standardized XML interface to DLs systems developed by the DL Implementation Group (DIG).
• OWL API on SourceForge.net, a Java interface and implementation for the Web Ontology Language, used to represent Semantic Web ontologies.