Description logic

From Wikipedia, the free encyclopedia

You have new messages (last change).

Description logics (DL) are a family of knowledge representation languages which can be used to represent the terminological knowledge of an application domain in a structured and formally well-understood way. The name description logic refers, on the one hand, to concept descriptions used to describe a domain and, on the other hand, to the logic-based semantics which can be given by a translation into first-order predicate logic. Description logic was designed as an extension to frames and semantic networks, which were not equipped with a formal logic-based semantics.

Description logic was given its current name in the 1980s. Previous to this it was called (chronologically): terminological systems, and concept languages. Today description logic has become a cornerstone of the Semantic Web for its use in the design of ontologies. The W3C-endorsed Web Ontology Language (OWL) is based on a description logic.

The first DL-based system was KL-ONE (by Brachman and Schmolze, 1985). Some other DL systems came later. They are LOOM (1987), BACK (1988), KRIS (1991), CLASSIC (1991), FaCT (1998) and lately RACER (2001), CEL (2005), and KAON 2 (2005).


Contents

[edit] Syntax

Syntax of description logics consists of

  • A set of unary predicate symbols that are used to denote concept names;
  • A set of binary predicate symbols that are used to denote role names;
  • A recursive definition for defining concept terms from concept names and role names using constructors.

In description logics, concept names are regarded as atomic concepts, role names are regarded as atomic roles. In general, a concept denotes the set of individual that belongs to it, and a role denotes a relationship between concepts.

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 common constructors include logical constructors in first-order logic such as intersection or conjunction of concepts, union or disjunction of concepts, negation or complement of concepts, value restriction (universal restriction), existential restriction, etc. Other constructors may also include restrictions on roles which are usual for binary relations, for example, inverse, transitivity, functionality, etc. Especially for intersection and union, description logics use the symbols \sqcap and \sqcup to distinguish them from ∧ and ∨ in first-order logic.

The following is an example of definition of the syntax of the description logic AL.

  • an atomic concept is an AL-concept;
  • the top concept (\top) is an AL-concept;
  • the bottom concept (\bot) is an AL-concept;
  • the complement of an AL-concept C is also an AL-concept (denoted by ¬C); C must be an atomic concept;
  • the intersection (conjunction) of two AL-concepts C and D is also an AL-concept (denoted by C\sqcap D);
  • if C is an AL-concept and R is a role name, then ∀R.C (value restriction) is also an AL-concept;
  • if R is a role name, then \exists R.\top (limited existential restriction) is also an AL-concept.

For example, A \sqcap B is an AL-concept, but A \sqcup B is not. Also, \exists S.\top is an AL-concept, but \exists S.A is not.

[edit] Semantics

The semantics of description logics is defined by interpreting concepts as sets of individuals and roles as sets of 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.

For example, given a set as the domain, an interpretation of AL-concepts is defined first over atomic concepts and roles as follows:

  • An atomic concept is interpreted as a set of individuals that is a subset of the domain.
  • An atomic role is interpreted as a set of pairs of individuals from the domain, i.e., a binary relation over the domain. In this case, if an individual x is related to y via a role R, then y is called an R-successor of x.

Next, this interpretation is extended to non atomic concept and role according to the constructors. This is done in the following.

  • The top concept is interpreted as the whole domain.
  • The bottom concept is interpreted as the empty set.
  • The interpretation of ¬C is the set of all individuals in the domain which does not belong to the interpretation of C.
  • Intersection of two concepts C and D is interpreted as set-intersection, i.e., the set of all individuals in the domain that belongs to both the interpretation of C and the interpretation of D.
  • The value restriction ∀R.C is interpreted as the set of all individuals in the domain whose all R-successor (if any) belong to the interpretation of C.
  • The limited existential restriction \exists R.\top is interpreted as the set of all individuals in the domain which has at least one R-successor.

Thus, according to the way concepts and roles interpreted above, if P is interpreted as the set of all persons and F is interpreted as the set of all female, then the set of all persons that are not female can be expressed by the concept

P\sqcap\neg F

[edit] Modelling in Description Logics

In DLs, 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:

(1) Every employee is a person

belongs in the TBox, while the statement:

(2) Bob is an employee

belongs in the ABox. Note that the TBox/ABox distinction is not significant in the same sense that in first-order logic (which subsumes most DLs). The two "kinds" of sentences are not treated differently. When translated into first-order logic, a subsumption axiom like (1) 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 (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 DLs. 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 modeller'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.)

[edit] Differences with OWL

[edit] Terminology

A concept in DL jargon is referred to as a class in OWL. A role in DL jargon is a property in OWL.

[edit] Names

Should add discussion of unique name assumption (UNA) versus no unique name assumption. OWL does not make the UNA.

[edit] DL Expressivity

Description Logic expressivity is denoted as follows.

\mathcal{AL} Attributive language. This is the base language which allows:
  • Atomic negation (negation of concepts that do not appear on the left hand side of axioms
  • Concept intersection
  • Universal restrictions
  • Limited existencial quantification
\mathcal{FL^-} A sub-langue of \mathcal{AL}, which is obtained by disallowing atomic negation.
\mathcal{FL}_o A sub-language of \mathcal{FL^-}, which is obtained by disallowing limited existential quantification.
\mathcal{C} Complex concept negation.
\mathcal{S} An abbreviation for \mathcal{AL} and \mathcal{C} with transitive properties.
\mathcal{H} Role hierarchy (subproperties - rdfs:subPropertyOf).
\mathcal{O} Nominals. (Enumerated classes of object value restrictions - owl:oneOf, owl:hasValue).
\mathcal{I} Inverse properties.
\mathcal{N} Cardinality restrictions (owl:Cardinality, owlMaxCardinality).
\mathcal{Q} Qualified cardinality restrictions (available in OWL 1.1).
\mathcal{F} Functional properties.
\mathcal{E} Full existencial qualification (Existencial restrictions that have fillers other than owl:thing).
\mathcal{U} Concept union.
^\mathcal{(D)} Use of datatype properties, data values or data types.

The Protégé ontology editor supports \mathcal{SHOIN}^\mathcal{(D)}

[edit] Description Logic Reasoners

There are some reasoners to deal with OWL and Description Logics. These are some of the most popular:

  • CEL is a free (for non-commercial use) LISP-based reasoner
  • Cerebra Engine is a commercial C++-based reasoner.
  • FaCT++ is a free open-source C++-based reasoner.
  • KAON2 is a free (free for non-commercial usage) Java reasoner.
  • MSPASS is a free open-source C reasoner for numerous description logics.
  • Pellet is a free open-source Java-based reasoner.
  • RacerPro is a commercial (free trials and research licenses are available) lisp-based reasoner

Other tools related to Description Logics include the following:

  • Protégé is a free, open source ontology editor and knowledge-base framework, which can use DL reasoners which offer a DIG interface as backends for consistency checks.
  • DIG Implementation. DIG is an XML interface to DL systems, recommended by the DL Implementation Group. DIG 2.0 is an ongoing effort for a new DIG interface standard.

[edit] See also

[edit] References

  • F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003. ISBN 0-521-78176-0

[edit] External links

Retrieved from "http://en.wikipedia.org../../../d/e/s/Description_logic.html"