Description logics (DL) are a family of formalknowledge representation languages. Many DLs are more expressive thanpropositional logic but less expressive thanfirst-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 betweenexpressive power andreasoningcomplexity by supporting different sets of mathematical constructors.[1]
DLs are used inartificial intelligence to describe and reason about the relevant concepts of an application domain (known asterminological knowledge). It is of particular importance in providing a logical formalism forontologies and theSemantic Web: theWeb Ontology Language (OWL) and its profiles are based on DLs. The most notable application of DLs and OWL is inbiomedical informatics where DL assists in the codification of biomedical knowledge.[citation needed]
A description logic (DL) modelsconcepts,roles andindividuals, and their relationships.
The fundamental modeling concept of a DL is theaxiom—a logical statement relating roles and/or concepts.[2] This is a key difference from theframes paradigm where aframe specification declares and completely defines a class.[2]
The description logic community uses different terminology than thefirst-order logic (FOL) community for operationally equivalent notions; some examples are given below. TheWeb Ontology Language (OWL) uses again a different terminology, also given in the table below.
FOL | OWL | DL | Examples |
---|---|---|---|
constant | individual | individual | Mickey Mouse, Walter Elias Mouse, Paris, France, etc. |
unary predicate | class | concept | (Being a) person, a city, a country, etc. |
binary predicate | property | role | father of, located in, etc. |
There are many varieties of description logics and there is an informal naming convention, roughly describing the operators allowed. Theexpressivity 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: | |
| |
Frame based description language,[3] allows: | |
| |
Existential language, allows: | |
|
Followed by any of the following extensions:
Functional properties, a special case ofuniqueness 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 ofcounting quantification | |
Qualified cardinality restrictions (available in OWL 2, cardinality restrictions that have fillers other than). | |
Use of datatype properties, data values or data types. |
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.[4] |
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.
Description logic was given its current name in the 1980s. Previous to this it was called (chronologically):terminological systems, andconcept languages.
Frames andsemantic networks lack formal (logic-based) semantics.[5] DL was first introduced intoknowledge representation (KR) systems to overcome this deficiency.[5]
The first DL-based KR system wasKL-ONE (byRonald J. Brachman and Schmolze, 1985). During the '80s other DL-based systems usingstructural 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 newtableau 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), andKAON 2 (2005).
DL reasoners, such as FaCT, FaCT++,[6] RACER, DLP and Pellet,[7] implement themethod of analytic tableaux. KAON2 is implemented by algorithms which reduce a SHIQ(D) knowledge base to a disjunctivedatalog program.
TheDARPA Agent Markup Language (DAML) andOntology Inference Layer (OIL)ontology languages for theSemantic Web can be viewed assyntactic variants of DL.[8] In particular, the formal semantics and reasoning in OIL use the DL.[9] TheDAML+OIL DL was developed as a submission to[10]—and formed the starting point of—theWorld Wide Web Consortium (W3C) Web Ontology Working Group.[11] In 2004, the Web Ontology Working Group completed its work by issuing theOWL[12] recommendation. The design of OWL is based on the family of DL[13] with OWL DL and OWL Lite based on and 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 theOWL2 recommendation.[15] OWL2 is based on the description logic.[16] Practical experience demonstrated that OWL DL lacked several key features necessary to model complex domains.[2]
In DL, a distinction is drawn between the so-calledTBox (terminological box) and theABox (assertional box). In general, the TBox contains sentences describing concept hierarchies (i.e., relations betweenconcepts) while the ABox containsground sentences stating where in the hierarchy, individuals belong (i.e., relations between individuals and concepts). For example, the statement:
Every employee is a person | 1 |
belongs in the TBox, while the statement:
Bob is an employee | 2 |
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 subsumptionaxiom like (1) is simply a conditional restriction tounarypredicates (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 theknowledge 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 theunique name assumption (UNA) or theclosed-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 theopen world assumption (OWA) means that lack of knowledge of a fact does not immediately imply knowledge of the negation of a fact.
Likefirst-order logic (FOL), asyntax defines which collections of symbols are legal expressions in a description logic, andsemantics determine meaning. Unlike FOL, a DL may have several well known syntactic variants.[8]
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 infirst-order logic (FOL) such asintersection orconjunction of concepts,union ordisjunction of concepts,negation orcomplement of concepts,universal restriction andexistential 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.
Symbol | Description | Example | Read |
---|---|---|---|
⊤ is a special concept with every individual as an instance | top | ||
empty concept | bottom | ||
intersection orconjunction of concepts | C and D | ||
union ordisjunction of concepts | C or D | ||
negation orcomplement of concepts | not C | ||
universal restriction | all R-successors are in C | ||
existential restriction | an R-successor exists in C | ||
Conceptinclusion | all C are D | ||
Conceptequivalence | C is equivalent to D | ||
Conceptdefinition | C is defined to be equal to D | ||
Conceptassertion | a is a C | ||
Roleassertion | a is R-related to b |
The prototypical DLAttributive Concept Language with Complements () 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, and be (respectively)sets ofconcept names (also known asatomic concepts),role names andindividual names (also known asindividuals,nominals orobjects). Then the ordered triple (,,) is thesignature.
The set ofconcepts is the smallest set such that:
Ageneral concept inclusion (GCI) has the form where and areconcepts. Write when and. ATBox is any finite set of GCIs.
AnABox is a finite set of assertional axioms.
Aknowledge base (KB) is an ordered pair forTBox andABox.
Thesemantics 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]
Aterminological interpretation over asignature consists of
such that
Define (readin I holds) as follows
Let be a knowledge base.
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 likeinstance checking (is a particular instance (member of an ABox) a member of a given concept) andrelation checking (does a relation/role hold between two instances, in other words doesa have propertyb), and the more global-database-questions likesubsumption (is a concept a subset of another concept), andconcept 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 (seeDescription Logic Complexity Navigator for examples).
Many DLs aredecidablefragments offirst-order logic (FOL)[5] and are usually fragments oftwo-variable logic orguarded logic. In addition, some DLs have features that are not covered in FOL; this includesconcrete domains (such as integer or strings, which can be used as ranges for roles such ashasAge orhasName) or an operator on roles for thetransitive closure of that role.[5]
Fuzzy description logics combinesfuzzy logic with DLs. Since many concepts that are needed forintelligent 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 apossible 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 indynamic logic.[17]
DL | ML |
---|---|
K[5] | |
PDL[17] | |
DPDL (deterministic PDL)[17] | |
Converse-PDL[17] | |
Converse-DPDL (deterministic PDL)[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 amodaltemporal logic such aslinear temporal logic.
There are somesemantic reasoners that deal with OWL and DL. These are some of the most popular: