Description logics (DL) are a family of formal knowledge representation languages. Many DLs are more expressive than propositional logic but less expressive than first-order 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.
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. A major area of application of DLs and OWL is in biomedical informatics, where they assist in the codification of biomedical knowledge. DLs and OWL are also applied in other domains, including defense, climate modeling, and large-scale industrial knowledge graphs.
Introduction A 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. This is a key difference from the frames paradigm where a frame specification declares and completely defines a class.
Nomenclature Terminology compared to FOL and OWL 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.
+ Synonyms FOL OWL DLExamples constant individual individualMickey Mouse, Walter Elias Mouse, Paris, France, etc. unary predicate class concept(Being a) person, a city, a country, etc. binary predicate property rolefather of, located in, etc.
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: 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 Frame based description language, allows: Concept intersection Universal restrictions Limited existential quantification Role restriction Existential language, allows: Concept intersection Existential restrictions (of full existential quantification) Followed by any of the following extensions: Functional properties, a special case of uniqueness quantification. Full existential qualification (existential restrictions that have fillers other than ). Concept union. Complex concept negation. Role hierarchy (subproperties: rdfs:subPropertyOf). Limited complex role inclusion axioms; reflexivity and irreflexivity; role disjointness. Nominals. (Enumerated classes of object value restrictions: owl:oneOf, owl:hasValue). Inverse properties. Cardinality restrictions (owl:cardinality, owl:maxCardinality), a special case of counting quantification Qualified cardinality restrictions (available in OWL 2, cardinality restrictions that have fillers other than ). Use of datatype properties, data values or data types.
Exceptions Some canonical DLs that do not exactly fit this convention are: An abbreviation for with transitive roles. A sub-language of , which is obtained by disallowing role restriction. This is equivalent to without atomic negation. A sub-language of , which is obtained by disallowing limited existential quantification. Alias for .
Examples As an example, is a centrally important description logic from which comparisons with other varieties can be made. is simply with complement of any concept allowed, not just atomic concepts. is used instead of the equivalent .
A further example, the description logic is the logic plus extended cardinality restrictions, and transitive and inverse roles. The naming conventions aren't purely systematic so that the logic might be referred to as and other abbreviations are also made where possible.
The Protégé ontology editor supports . Three major biomedical informatics terminology bases, SNOMED CT, GALEN, and GO, are expressible in (with additional role properties).
OWL 2 provides the expressiveness of , OWL-DL is based on , and for OWL-Lite it is .
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 (logic-based) semantics.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. DL was first introduced into knowledge representation (KR) systems to overcome this deficiency.
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 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.
In the early '90s, the introduction of a new tableau based algorithm paradigm allowed efficient reasoning on more expressive DL. 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.
From the mid '90s, reasoners were created with good practical performance on very expressive DL with high worst case complexity. Examples from this period include FaCT, RACER (2001), CEL (2005), and KAON 2 (2005).
DL reasoners, such as FaCT, FaCT++, RACER, DLP and Pellet, 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.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. In particular, the formal semantics and reasoning in OIL use the DL. The DAML+OIL DL was developed as a submission toIan 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.—and formed the starting point of—the World Wide Web Consortium (W3C) Web Ontology Working Group.Web Ontology Working Group Charter, 2003 In 2004, the Web Ontology Working Group completed its work by issuing the OWLW3C Press Release, 2004 recommendation. The design of OWL is based on the family of DL with OWL DL and OWL Lite based on and respectively.
The W3C OWL Working Group began work in 2007 on a refinement of - and extension to - OWL.OWL Working Group Charter, 2007 In 2009, this was completed by the issuance of the OWL2 recommendation. OWL2 is based on the description logic . Practical experience demonstrated that OWL DL lacked several key features necessary to model complex domains.
Modeling
TBox vs Abox 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:
belongs in the TBox, while the statement:
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 () 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 ().
Motivation for having Tbox and Abox 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), it makes sense to reuse the TBox for different branches that do not use the same ABox.
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 Like first-order logic (FOL), a syntax defines which collections of symbols are legal expressions in a description logic, and semantics determine meaning. Unlike FOL, a DL may have several well known syntactic variants.
Syntax 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 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 ⊤ is a special concept with every individual as an instance top empty concept bottom intersection or conjunction of concepts C and D union or disjunction of concepts C or D negation or complement of concepts not C universal restriction all R-successors are in C existential restriction an R-successor exists in C Concept inclusion all C are D Concept equivalence C is equivalent to D Concept definition C is defined to be equal to D Concept assertion a is a C Role assertion a is R-related to b