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 descriptions logics, and each description logic features a different balance between DL expressivity and reasoningcomplexity 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 profile is based on DLs. The most notable application of DLs and OWL is in biomedical informatics where DL assists in the codification of biomedical knowledge.
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. This is a key difference from the frames paradigm where a frame specification declares and completely defines a class.
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.
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)
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 abbreviations are 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 .
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.
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.
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
belongs in the TBox, while the statement:
Bob is an employee
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 unarypredicates (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.
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.
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 (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.
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.
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 A-box) 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 T-box (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).
Many DLs are decidablefragments of first-order logic (FOL) 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.
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.
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 modaltemporal logic such as linear temporal logic.
^ abcdefghijklmnoFranz 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.
^ abIan Horrocks and Ulrike Sattler Ontology Reasoning in the SHOQ(D) Description Logic, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.
^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. doi:10.1109/5254.920598.
^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.
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. ISBN0-521-78176-0
Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, and Ulrike Sattler: OWL 2: The next step for OWL. Journal of Web Semantics, 6(4):309-322, November 2008.
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.
Alessandro Artale and Enrico Franconi: Temporal Description Logics. In Handbook of Temporal Reasoning in Artificial Intelligence, 2005.
Franz Baader: Description Logics. In Reasoning Web: Semantic Technologies for Information Systems, 5th International Summer School, volume 5689 of Lecture Notes in Computer Science, pages 1–39. Springer, 2009. (springerlink) Introductory text with a focus on reasoning and language design, and an extended historical overview.
KAON2 is a free (for non-commercial use) Java-based reasoner, offering fast reasoning support for OWL ontologies.
MSPASS is a free open-source C reasoner for numerous DL models.
Pellet is a dual-licensed (AGPL and proprietary) commercial, Java-based reasoner.
RacerPro of Racer Systems is a commercial (free trials and research licenses are available) lisp-based reasoner.
Sim-DL 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.
None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.
All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.
The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.