Description logic


Description logics 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 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. It is of particular importance in providing a logical formalism for ontologies and the Semantic Web: the Web Ontology Language 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 community for operationally equivalent notions; some examples are given below. The Web Ontology Language uses again a different terminology, also given in the table below.
FOLOWLDLExamples
constantindividualindividualMickey Mouse, Walter Elias Mouse, Paris, France, etc.
unary predicateclassconcept person, a city, a country, etc.
binary predicatepropertyrolefather 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:
Followed by any of the following extensions:

Exceptions

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

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 .
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 : terminological systems, and concept languages.

Knowledge representation

Frames and semantic networks lack formal semantics. DL was first introduced into knowledge representation systems to overcome this deficiency.
The first DL-based KR system was KL-ONE. During the '80s other DL-based systems using structural subsumption algorithms were developed including KRYPTON, LOOM, BACK, K-REP and CLASSIC. This approach featured DL with limited expressiveness but relatively efficient 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 — 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, CEL, and KAON 2.
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 knowledge base to a disjunctive datalog program.

Semantic web

The DARPA Agent Markup Language and Ontology Inference Layer ontology languages for the Semantic Web can be viewed as
syntactic variants of DL. In particular, the formal semantics and reasoning in OIL use the DL. The DAML+OIL DL was developed as a submission to—and formed the starting point of—the World Wide Web Consortium Web Ontology Working Group. In 2004, the Web Ontology Working Group completed its work by issuing the OWL 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. 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 and the ABox. In general, the TBox contains sentences describing concept hierarchies while the ABox contains ground sentences stating where in the hierarchy, individuals belong. 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. When translated into first-order logic, a subsumption axiom like is simply a conditional restriction to unary predicates with only variables appearing in it. Clearly, a sentence of this form is not privileged or special over sentences in which only constants 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. 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 and particular manifestations of those terms/concepts. 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, 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 or the closed-world assumption. 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 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, 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 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.
SymbolDescriptionExampleRead
⊤ is a special concept with every individual as an instancetop
empty conceptbottom
intersection or conjunction of conceptsC and D
union or disjunction of conceptsC or D
negation or complement of conceptsnot C
universal restrictionall R-successors are in C
existential restrictionan R-successor exists in C
Concept inclusionall C are D
Concept equivalenceC is equivalent to D
Concept definitionC is defined to be equal to D
Concept assertiona is a C
Role assertiona is R-related to b

The description logic ALC

The prototypical DL Attributive Concept Language with Complements was introduced by Manfred Schmidt-Schauß and Gert Smolka in 1991, and is the basis of many more expressive DLs. The following definitions follow the treatment in Baader et al.
Let, and be sets of concept names, role names and individual names. Then the ordered triple is the signature.
Concepts
The set of concepts is the smallest set such that:
  • The following are concepts:
  • *
  • *
  • * Every
  • If and are concepts and then the following are concepts:
  • *
  • *
  • *
  • *
  • *
    Terminological axioms
A general concept inclusion has the form where and are concepts. Write when and. A TBox is any finite set of GCIs.
Assertional axioms
  • A concept assertion is a statement of the form where and C is a concept.
  • A role assertion is a statement of the form where and R is a role.
An ABox is a finite set of assertional axioms.
Knowledge base
A knowledge base is an ordered pair for TBox and ABox.

Semantics

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 description logic ALC

The following definitions follow the treatment in Baader et al.
A terminological interpretation over a signature consists of
  • a non-empty set called the domain
  • a interpretation function that maps:
  • * every individual to an element
  • * every concept to a subset of
  • * every role name to a subset of
such that'
  • '
Define as follows
TBox
  • if and only if
  • if and only if for every
    ABox
  • if and only if
  • if and only if
  • if and only if for every
    Knowledge base
Let be a knowledge base.
  • if and only if and

Inference

Decision problems

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 and relation checking, and the more global-database-questions like subsumption, and concept consistency. The more operators one includes in a logic and the more complicated the TBox, usually the higher the computational complexity is for each of these problems.

Relationship with other logics

First-order logic

Many DLs are decidable fragments of first-order logic 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 or an operator on roles for the transitive closure of that role.

Fuzzy description logic

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.

Modal logic

Description logic is related to—but developed independently of—modal logic. Many—but not all—DLs are syntactic variants of ML.
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 correspond to the modal operations used in dynamic logic.

Temporal description logic

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

Reasoners

There are some semantic reasoners that deal with OWL and DL. These are some of the most popular:
  • is an open source LISP-based reasoner.
  • was a commercial C++-based reasoner, acquired in 2006 by webMethods.
  • is a free open-source C++-based reasoner.
  • KAON2 is a free Java-based reasoner, offering fast reasoning support for OWL ontologies.
  • is a free open-source C reasoner for numerous DL models.
  • is a dual-licensed commercial, Java-based reasoner.
  • of Racer Systems was a commercial 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
  • 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.
  • is an open-source reasoner based on the "hypertableau" calculus. It is developed by the University of Oxford.
  • 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 . Owlready2 allows a transparent access to OWL ontologies.
  • . OWLAPY is an open-source Python framework for creating, manipulating, and reasoning with OWL ontologies. It includes a built-in StructuralReasoner for efficient, lightweight reasoning and wrappers for well-known Java-based reasoners like HermiT, Pellet, JFact, and Openllet.

Editors

Interfaces