Description logic
Description logics (DL) are a family of formal knowledge representation languages. Many DLs are more expressive than propositional logic but less expressive than firstorder logic. In contrast to the latter, the core reasoning problems for DLs are (usually) decidable, and efficient decision procedures have been designed and implemented for these problems. There are general, spatial, temporal, spatiotemporal, and fuzzy description logics, and each description logic features a different balance between expressive power and reasoning complexity by supporting different sets of mathematical constructors.^{[1]}
DLs are used in artificial intelligence to describe and reason about the relevant 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 Web Ontology Language (OWL) and its profiles are based on DLs. The most notable application of DLs and OWL is in biomedical informatics where DL assists in the codification of biomedical knowledge.
Introduction
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.^{[2]} This is a key difference from the frames paradigm where a frame specification declares and completely defines a class.^{[2]}
Nomenclature
Terminology compared to FOL and OWL
The description logic community uses different terminology than the firstorder 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.
FOL  OWL  DL 

constant  individual  individual 
unary predicate  class  concept 
binary predicate  property  role 
Naming convention
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:
[math]\displaystyle{ \mathcal{AL} }[/math]  Attributive language. This is the base language which allows: 
 
 
[math]\displaystyle{ \mathcal{EL} }[/math]  Existential language, allows: 

Followed by any of the following extensions:
[math]\displaystyle{ \mathcal{F} }[/math]  Functional properties, a special case of uniqueness quantification. 
[math]\displaystyle{ \mathcal{E} }[/math]  Full existential qualification (existential restrictions that have fillers other than [math]\displaystyle{ \top }[/math]). 
[math]\displaystyle{ \mathcal{U} }[/math]  Concept union. 
[math]\displaystyle{ \mathcal{C} }[/math]  Complex concept negation. 
[math]\displaystyle{ \mathcal{H} }[/math]  Role hierarchy (subproperties: rdfs:subPropertyOf ).

[math]\displaystyle{ \mathcal{R} }[/math]  Limited complex role inclusion axioms; reflexivity and irreflexivity; role disjointness. 
[math]\displaystyle{ \mathcal{O} }[/math]  Nominals. (Enumerated classes of object value restrictions: owl:oneOf , owl:hasValue ).

[math]\displaystyle{ \mathcal{I} }[/math]  Inverse properties. 
[math]\displaystyle{ \mathcal{N} }[/math]  Cardinality restrictions (owl:cardinality , owl:maxCardinality ), a special case of counting quantification

[math]\displaystyle{ \mathcal{Q} }[/math]  Qualified cardinality restrictions (available in OWL 2, cardinality restrictions that have fillers other than [math]\displaystyle{ \top }[/math]). 
[math]\displaystyle{ ^\mathcal{(D)} }[/math]  Use of datatype properties, data values or data types. 
Exceptions
Some canonical DLs that do not exactly fit this convention are:
[math]\displaystyle{ \mathcal{S} }[/math]  An abbreviation for [math]\displaystyle{ \mathcal{ALC} }[/math] with transitive roles. 
[math]\displaystyle{ \mathcal{FL^} }[/math]  A sublanguage of [math]\displaystyle{ \mathcal{FL} }[/math], which is obtained by disallowing role restriction. This is equivalent to [math]\displaystyle{ \mathcal{AL} }[/math] without atomic negation. 
[math]\displaystyle{ \mathcal{FL}_o }[/math]  A sublanguage of [math]\displaystyle{ \mathcal{FL^} }[/math], which is obtained by disallowing limited existential quantification. 
Examples
As an example, [math]\displaystyle{ \mathcal{ALC} }[/math] is a centrally important description logic from which comparisons with other varieties can be made. [math]\displaystyle{ \mathcal{ALC} }[/math] is simply [math]\displaystyle{ \mathcal{AL} }[/math] with complement of any concept allowed, not just atomic concepts. [math]\displaystyle{ \mathcal{ALC} }[/math] is used instead of the equivalent [math]\displaystyle{ \mathcal{ALUE} }[/math].
A further example, the description logic [math]\displaystyle{ \mathcal{SHIQ} }[/math] is the logic [math]\displaystyle{ \mathcal{ALC} }[/math] plus extended cardinality restrictions, and transitive and inverse roles. The naming conventions aren't purely systematic so that the logic [math]\displaystyle{ \mathcal{ALCOIN} }[/math] might be referred to as [math]\displaystyle{ \mathcal{ALCNIO} }[/math] and other abbreviations are also made where possible.
The Protégé ontology editor supports [math]\displaystyle{ \mathcal{SHOIN}^\mathcal{(D)} }[/math]. Three major biomedical informatics terminology bases, SNOMED CT, GALEN, and GO, are expressible in [math]\displaystyle{ \mathcal{EL} }[/math] (with additional role properties).
OWL 2 provides the expressiveness of [math]\displaystyle{ \mathcal{SROIQ}^\mathcal{(D)} }[/math], OWLDL is based on [math]\displaystyle{ \mathcal{SHOIN}^\mathcal{(D)} }[/math], and for OWLLite it is [math]\displaystyle{ \mathcal{SHIF}^\mathcal{(D)} }[/math].
History
Description logic was given its current name in the 1980s. Previous to this it was called (chronologically): terminological systems, and concept languages.
Knowledge representation
Frames and semantic networks lack formal (logicbased) semantics.^{[3]} DL was first introduced into knowledge representation (KR) systems to overcome this deficiency.^{[3]}
The first DLbased KR system was KLONE (by Ronald J. Brachman and Schmolze, 1985). During the '80s other DLbased systems using structural subsumption algorithms^{[3]} were developed including KRYPTON (1983), LOOM (1987), BACK (1988), KREP (1991) and CLASSIC (1991). This approach featured DL with limited expressiveness but relatively efficient (polynomial time) reasoning.^{[3]}
In the early '90s, the introduction of a new tableau based algorithm paradigm allowed efficient reasoning on more expressive DL.^{[3]} DLbased 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.^{[3]}
From the mid '90s, reasoners were created with good practical performance on very expressive DL with high worst case complexity.^{[3]} Examples from this period include FaCT,^{[4]} RACER (2001), CEL (2005), and KAON 2 (2005).
DL reasoners, such as FaCT, FaCT++,^{[4]} RACER, DLP and Pellet,^{[5]} implement the method of analytic tableaux. KAON2 is implemented by algorithms which reduce a SHIQ(D) knowledge base to a disjunctive datalog program.
Semantic web
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.^{[6]} In particular, the formal semantics and reasoning in OIL use the [math]\displaystyle{ \mathcal{SHIQ} }[/math] DL.^{[7]} The DAML+OIL DL was developed as a submission to^{[8]}—and formed the starting point of—the World Wide Web Consortium (W3C) Web Ontology Working Group.^{[9]} In 2004, the Web Ontology Working Group completed its work by issuing the OWL^{[10]} recommendation. The design of OWL is based on the [math]\displaystyle{ \mathcal{SH} }[/math] family of DL^{[11]} with OWL DL and OWL Lite based on [math]\displaystyle{ \mathcal{SHOIN}^\mathcal{(D)} }[/math] and [math]\displaystyle{ \mathcal{SHIF}^\mathcal{(D)} }[/math] respectively.^{[11]}
The W3C OWL Working Group began work in 2007 on a refinement of  and extension to  OWL.^{[12]} In 2009, this was completed by the issuance of the OWL2 recommendation.Cite error: Closing </ref>
missing for <ref>
tag
Examples
DL  ML 

[math]\displaystyle{ \mathcal{ALC} }[/math]  K^{[3]} 
[math]\displaystyle{ \mathcal{SR} }[/math]  PDL^{[13]} 
[math]\displaystyle{ \mathcal{FSR} }[/math]  DPDL (deterministic PDL)^{[13]} 
[math]\displaystyle{ \mathcal{TSL}\text{, or }\mathcal{SRI} }[/math]  ConversePDL^{[13]} 
[math]\displaystyle{ \mathcal{FSL}\text{, or }\mathcal{FSRI} }[/math]  ConverseDPDL (deterministic PDL)^{[13]} 
Temporal description logic
Temporal description logic represents—and allows reasoning about—time dependent concepts and many different approaches to this problem exist.^{[14]} For example, a description logic might be combined with a modal temporal logic such as linear temporal logic.
See also
References
 ↑ Sikos, Leslie F. (2017). Description Logics in Multimedia Reasoning. Cham: Springer International Publishing. doi:10.1007/9783319540665. ISBN 9783319540665. https://www.springer.com/us/book/9783319540658.
 ↑ ^{2.0} ^{2.1} Grau, B. C.; Horrocks, I.; Motik, B.; Parsia, B.; PatelSchneider, P. F.; Sattler, U. (2008). "OWL 2: The next step for OWL". Web Semantics: Science, Services and Agents on the World Wide Web 6 (4): 309–322. doi:10.1016/j.websem.2008.05.001. http://www.cs.ox.ac.uk/boris.motik/pubs/ghmppss08nextsteps.pdf.
 ↑ ^{3.0} ^{3.1} ^{3.2} ^{3.3} ^{3.4} ^{3.5} ^{3.6} ^{3.7} 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.
 ↑ ^{4.0} ^{4.1} Tsarkov, D.; Horrocks, I. (2006). "FaCT++ Description Logic Reasoner: System Description". Automated Reasoning. Lecture Notes in Computer Science. 4130. pp. 292–297. doi:10.1007/11814771_26. ISBN 9783540371878. http://www.cs.ox.ac.uk/ian.horrocks/Publications/download/2006/TsHo06a.pdf.
 ↑ Sirin, E.; Parsia, B.; Grau, B. C.; Kalyanpur, A.; Katz, Y. (2007). "Pellet: A practical OWLDL reasoner". Web Semantics: Science, Services and Agents on the World Wide Web 5 (2): 51–53. doi:10.1016/j.websem.2007.03.004. http://pellet.owldl.com/papers/sirin05pellet.pdf.
 ↑ Ian Horrocks and Ulrike Sattler Ontology Reasoning in the SHOQ(D) Description Logic, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.
 ↑ Fensel, D.; Van Harmelen, F.; Horrocks, I.; McGuinness, D. L.; PatelSchneider, P. F. (2001). "OIL: An ontology infrastructure for the Semantic Web". IEEE Intelligent Systems 16 (2): 38–45. doi:10.1109/5254.920598.
 ↑ Ian Horrocks and Peter F. PatelSchneider The Generation of DAML+OIL. In Proceedings of the 2001 Description Logic Workshop (DL 2001), volume 49 of CEUR <http://ceurws.org/>, pages 30–35, 2001.
 ↑ Web Ontology Working Group Charter, 2003
 ↑ W3C Press Release, 2004
 ↑ ^{11.0} ^{11.1} Horrocks, I.; PatelSchneider, Peter; van Harmelen, Frank (2003). "From SHIQ and RDF to OWL: The making of a Web Ontology Language". Web Semantics: Science, Services and Agents on the World Wide Web 1: 7–26. doi:10.1016/j.websem.2003.07.001. http://www.comlab.ox.ac.uk/people/ian.horrocks/Publications/download/2003/HoPH03a.pdf.
 ↑ OWL Working Group Charter, 2007
 ↑ ^{13.0} ^{13.1} ^{13.2} ^{13.3} Cite error: Invalid
<ref>
tag; no text was provided for refs namedCTTL
 ↑ Alessandro Artale and Enrico Franconi "Temporal Description Logics". In "Handbook of Temporal Reasoning in Artificial Intelligence", 2005.
Further reading
 F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. PatelSchneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003. ISBN:0521781760
 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. PatelSchneider: OIL: An Ontology Infrastructure for the Semantic Web. IEEE Intelligent Systems, 16(2):3845, 2001.
 Ian Horrocks and Peter F. PatelSchneider: The Generation of DAML+OIL. In Proceedings of the 2001 Description Logic Workshop (DL 2001), volume 49 of CEUR <http://ceurws.org/>, pages 30–35, 2001.
 Ian Horrocks, Peter F. PatelSchneider, and Frank van Harmelen: From SHIQ and RDF to OWL: The Making of a Web Ontology Language. Journal of Web Semantics, 1(1):726, 2003.
 Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter PatelSchneider, and Ulrike Sattler: OWL 2: The next step for OWL. Journal of Web Semantics, 6(4):309322, 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.
 Markus Krötzsch, František Simančík, Ian Horrocks: A Description Logic Primer. CoRR arXiv:1201.4089. 2012. 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.
 Jens Lehmann: DLLearner: Learning concepts in description logics, Journal of Machine Learning Research, 2009.
 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):5867, December 2008. A general overview of knowledge representation in Semantic Web technologies.
External links
 Description Logic Complexity Navigator, maintained by Evgeny Zolin at the Department of Computer Science
 List of Reasoners, OWL research at the University of Manchester
Reasoners
There are some semantic reasoners that deal with OWL and DL. These are some of the most popular:
 CEL is an open source LISPbased reasoner (Apache 2.0 License).
 Cerebra Engine was a commercial C++based reasoner, acquired in 2006 by webMethods.
 FaCT++ is a free opensource C++based reasoner.
 KAON2 is a free (for noncommercial use) Javabased reasoner, offering fast reasoning support for OWL ontologies.
 MSPASS is a free opensource C reasoner for numerous DL models.
 Pellet is a duallicensed (AGPL and proprietary) commercial, Javabased reasoner.
 RacerPro of Racer Systems was a commercial (free trials and research licenses are available) lispbased 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.
 SimDL is a free opensource Javabased 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 opensource reasoner based on the "hypertableau" calculus. It is developed by the University of Oxford.
 Owlready2 is a package for ontologyoriented 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 Javabased API).
Editors
 Protégé is a free, opensource ontology editor and a knowledge base framework, which can use DL reasoners offering DIG Interface as a back end for consistency checks.
 on GitHub, an OWL browser/editor that takes the standard web browser as the basic UI paradigm.
Interfaces
 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.
Original source: https://en.wikipedia.org/wiki/Description logic.
Read more 