Description logic

Last updated

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. [1]

Contents

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 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
FOLOWLDL
constantindividualindividual
unary predicateclassconcept
binary predicatepropertyrole

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, [3] 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 . [4]

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. [5] DL was first introduced into knowledge representation (KR) systems to overcome this deficiency. [5]

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 [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 new tableau 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), and KAON 2 (2005).

DL reasoners, such as FaCT, FaCT++, [6] RACER, DLP and Pellet, [7] 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. [8] In particular, the formal semantics and reasoning in OIL use the DL. [9] The DAML+OIL DL was developed as a submission to [10] —and formed the starting point of—the World Wide Web Consortium (W3C) Web Ontology Working Group. [11] In 2004, the Web Ontology Working Group completed its work by issuing the OWL [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 the OWL2 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]

Modeling

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:

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 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 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. [8]

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
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 restriction all R-successors are in C
existential restriction an 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. [5] The following definitions follow the treatment in Baader et al. [5]

Let , and be (respectively) sets of concept names (also known as atomic concepts), role names and individual names (also known as individuals, nominals or objects). Then the ordered triple (, , ) is the signature.

Concepts

The set of concepts is the smallest set such that:

  • The following are concepts:
    • (top is a concept)
    • (bottom is a concept)
    • Every (all atomic concepts are concepts)
  • If and are concepts and then the following are concepts:
    • (the intersection of two concepts is a concept)
    • (the union of two concepts is a concept)
    • (the complement of a concept is a concept)
    • (the universal restriction of a concept by a role is a concept)
    • (the existential restriction of a concept by a role is a concept)
Terminological axioms

A general concept inclusion (GCI) 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 (KB) 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. [5]

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

  • (union means disjunction)
  • (intersection means conjunction)
  • (complement means negation)

Define (read in I holds) 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 (is a particular instance (member of an ABox) a member of a given concept) and relation checking (does a relation/role hold between two instances, in other words does a have property b), and the more global-database-questions like subsumption (is a concept a subset of another concept), and concept 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 (see Description Logic Complexity Navigator for examples).

Relationship with other logics

First-order logic

Many DLs are decidable fragments of first-order logic (FOL) [5] 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 (such as integer or strings, which can be used as ranges for roles such as hasAge or hasName) or an operator on roles for the transitive closure of that role. [5]

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.

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 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 (such as composition, inversion, etc.) correspond to the modal operations used in dynamic logic. [17]

Examples

Syntactic variants
DLML
K [5]
PDL [17]
DPDL (deterministic PDL) [17]
Converse- PDL [17]
Converse-DPDL (deterministic PDL) [17]

Temporal description logic

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 a modal temporal logic such as linear temporal logic.

See also

Related Research Articles

Knowledge representation and reasoning is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can utilize to solve complex tasks such as diagnosing a medical condition or having a dialog in a natural language. Knowledge representation incorporates findings from psychology about how humans solve problems and represent knowledge in order to design formalisms that will make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning, such as the application of rules or the relations of sets and subsets.

The Semantic Web is an extension of the World Wide Web through standards set by the World Wide Web Consortium (W3C). The goal of the Semantic Web is to make Internet data machine-readable.

OIL can be regarded as an ontology infrastructure for the Semantic Web. OIL is based on concepts developed in Description Logic (DL) and frame-based systems and is compatible with RDFS.

The Web Ontology Language (OWL) is a family of knowledge representation languages for authoring ontologies. Ontologies are a formal way to describe taxonomies and classification networks, essentially defining the structure of knowledge for various domains: the nouns representing classes of objects and the verbs representing relations between the objects.

Patrick John Hayes FAAAI is a British computer scientist who lives and works in the United States. As of March 2006, he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida.

In computer science and artificial intelligence, ontology languages are formal languages used to construct ontologies. They allow the encoding of knowledge about specific domains and often include reasoning rules that support the processing of that knowledge. Ontology languages are usually declarative languages, are almost always generalizations of frame languages, and are commonly based on either first-order logic or on description logic.

In computer science, a TBox is a "terminological component"—a conceptualization associated with a set of facts, known as an ABox.

Semantic technology

The ultimate goal of semantic technology is to help machines understand data. To enable the encoding of semantics with the data, well-known technologies are RDF and OWL. These technologies formally represent the meaning involved in information. For example, ontology can describe concepts, relationships between things, and categories of things. These embedded semantics with the data offer significant advantages such as reasoning over data and dealing with heterogeneous data sources.

F-logic is a knowledge representation and ontology language. F-logic combines the advantages of conceptual modeling with object-oriented, frame-based languages and offers a declarative, compact and simple syntax, as well as the well-defined semantics of a logic-based language.

The Semantic Web Rule Language (SWRL) is a proposed language for the Semantic Web that can be used to express rules as well as logic, combining OWL DL or OWL Lite with a subset of the Rule Markup Language.

Ian Horrocks

Ian Robert Horrocks is a Professor of Computer Science at the University of Oxford in the UK and a Fellow of Oriel College, Oxford. His research focuses on knowledge representation and reasoning, particularly ontology languages, description logic and optimised tableaux decision procedures.

Frank van Harmelen

Frank van Harmelen is a Dutch computer scientist and professor in Knowledge Representation & Reasoning in the AI department at the Vrije Universiteit Amsterdam. Currently he is scientific director of the LarKC project, "aiming to develop the Large Knowledge Collider, a platform for very large scale semantic web reasoning."

Frames are an artificial intelligence data structure used to divide knowledge into substructures by representing "stereotyped situations". They were proposed by Marvin Minsky in his 1974 article "A Framework for Representing Knowledge". Frames are the primary data structure used in artificial intelligence frame language; they are stored as ontologies of sets.

Machine interpretation of documents and services in Semantic Web environment is primarily enabled by (a) the capability to mark documents, document segments and services with semantic tags and (b) the ability to establish contextual relations between the tags with a domain model, which is formally represented as ontology. Human beings use natural languages to communicate an abstract view of the world. Natural language constructs are symbolic representations of human experience and are close to the conceptual model that Semantic Web technologies deal with. Thus, natural language constructs have been naturally used to represent the ontology elements. This makes it convenient to apply Semantic Web technologies in the domain of textual information. In contrast, multimedia documents are perceptual recording of human experience. An attempt to use a conceptual model to interpret the perceptual records gets severely impaired by the semantic gap that exists between the perceptual media features and the conceptual world. Notably, the concepts have their roots in perceptual experience of human beings and the apparent disconnect between the conceptual and the perceptual world is rather artificial. The key to semantic processing of multimedia data lies in harmonizing the seemingly isolated conceptual and the perceptual worlds. Representation of the Domain knowledge needs to be extended to enable perceptual modeling, over and above conceptual modeling that is supported. The perceptual model of a domain primarily comprises observable media properties of the concepts. Such perceptual models are useful for semantic interpretation of media documents, just as the conceptual models help in the semantic interpretation of textual documents.

A semantic reasoner, reasoning engine, rules engine, or simply a reasoner, is a piece of software able to infer logical consequences from a set of asserted facts or axioms. The notion of a semantic reasoner generalizes that of an inference engine, by providing a richer set of mechanisms to work with. The inference rules are commonly specified by means of an ontology language, and often a description logic language. Many reasoners use first-order predicate logic to perform reasoning; inference commonly proceeds by forward chaining and backward chaining. There are also examples of probabilistic reasoners, including non-axiomatic reasoning systems, and probabilistic logic networks.

WSML or Web Service Modeling Language is a formal language that provides a syntax and semantics for the Web Service Modeling Ontology (WSMO).

Ontology engineering field which studies the methods and methodologies for building ontologies

In computer science, information science and systems engineering, ontology engineering is a field which studies the methods and methodologies for building ontologies, which are formal representations of a set of concepts within a domain and the relationships between those concepts. In a broader sense, this field also includes a knowledge construction of the domain using formal ontology representations such as OWL/RDF. A large-scale representation of abstract concepts such as actions, time, physical objects and beliefs would be an example of ontological engineering. Ontology engineering is one of the areas of applied ontology, and can be seen as an application of philosophical ontology. Core ideas and objectives of ontology engineering are also central in conceptual modeling.

In artificial intelligence and related fields, an argumentation framework is a way to deal with contentious information and draw conclusions from it using formalized arguments.

Ulrike Sattler

Ulrike M. Sattler is a Professor of Computer science in the information management group of the Department of Computer Science at the University of Manchester and a visiting Professor at the University of Oslo.

Jens Lehmann (scientist) Artificial Intelligence researcher

Jens Lehmann is a computer scientist, most noted for his work on knowledge graphs and Artificial Intelligence. He is a full professor at the University of Bonn, Germany, and leading the Smart Data Analytics research group. He is also a Lead Scientist for Conversational AI and Knowledge Graphs at Fraunhofer IAIS and a fellow of European Laboratory for Learning and Intelligent Systems.

References

  1. Sikos, Leslie F. (2017). Description Logics in Multimedia Reasoning. Cham: Springer International Publishing. doi:10.1007/978-3-319-54066-5. ISBN   978-3-319-54066-5.
  2. 1 2 3 Grau, B. C.; Horrocks, I.; Motik, B.; Parsia, B.; Patel-Schneider, P. F.; Sattler, U. (2008). "OWL 2: The next step for OWL" (PDF). Web Semantics: Science, Services and Agents on the World Wide Web. 6 (4): 309–322. doi:10.1016/j.websem.2008.05.001.
  3. Levesque, Hector J.; Brachmann, Ronald J. (1987). "Expressiveness and tractability in knowledge representation and reasoning". Computational Intelligence. 3 (3): 78–93. doi:10.1111/j.1467-8640.1987.tb00176.x.
  4. Maier, Frederick; Mutharaju, Raghava; Hitzler, Pascal (2010). "Distributed Reasoning with EL++ Using MapReduce". Computer Science and Engineering Faculty Publications. Technical Report, Kno.e.sis Center, Wright State University, Dayton, Ohio. Retrieved 2016-08-24.
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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.
  6. 1 2 Tsarkov, D.; Horrocks, I. (2006). "FaCT++ Description Logic Reasoner: System Description" (PDF). Automated Reasoning. Lecture Notes in Computer Science. 4130. pp. 292–297. CiteSeerX   10.1.1.65.2672 . doi:10.1007/11814771_26. ISBN   978-3-540-37187-8.
  7. Sirin, E.; Parsia, B.; Grau, B. C.; Kalyanpur, A.; Katz, Y. (2007). "Pellet: A practical OWL-DL reasoner" (PDF). Web Semantics: Science, Services and Agents on the World Wide Web. 5 (2): 51–53. doi:10.1016/j.websem.2007.03.004. Archived from the original (PDF) on 2007-06-27.
  8. 1 2 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.
  9. Fensel, D.; Van Harmelen, F.; Horrocks, I.; McGuinness, D. L.; Patel-Schneider, P. F. (2001). "OIL: An ontology infrastructure for the Semantic Web". IEEE Intelligent Systems. 16 (2): 38–45. CiteSeerX   10.1.1.307.9456 . doi:10.1109/5254.920598.
  10. Ian 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.
  11. Web Ontology Working Group Charter, 2003
  12. W3C Press Release, 2004
  13. 1 2 Horrocks, I.; Patel-Schneider, Peter; van Harmelen, Frank (2003). "From SHIQ and RDF to OWL: The making of a Web Ontology Language" (PDF). Web Semantics: Science, Services and Agents on the World Wide Web. 1: 7–26. CiteSeerX   10.1.1.2.7039 . doi:10.1016/j.websem.2003.07.001.
  14. OWL Working Group Charter, 2007
  15. Hitzler, Pascal; Krötzsch, Markus; Parsia, Bijan; Patel-Schneider, Peter F.; Rudolph, Sebastian (27 October 2009). "OWL 2 Web Ontology Language Primer". OWL 2 Web Ontology Language. World Wide Wed Consortium. Retrieved 2010-12-14.
  16. Pascal Hitzler; Markus Krötzsch; Sebastian Rudolph (August 25, 2009). Foundations of Semantic Web Technologies. CRCPress. ISBN   978-1-4200-9050-5.
  17. 1 2 3 4 5 Schild, Klaus. "Correspondence theory for terminological logics: Preliminary Report" (PDF). KIT Report 91. KIT-BACK. Retrieved 2012-10-25.
  18. Alessandro Artale and Enrico Franconi "Temporal Description Logics". In "Handbook of Temporal Reasoning in Artificial Intelligence", 2005.

Further reading

Reasoners

There are some semantic reasoners that deal with OWL and DL. These are some of the most popular:

Editors

Interfaces