Description Logics

Description Logics

Logic-based knowledge representations implement mathematical logic, a subfield of mathematics dealing with formal expressions, reasoning, and formal proof. Description logics (DL) constitute a family of formal knowledge representation languages that provide a logical underpinning for OWL ontologies. Many description logics are more expressive than propositional logic, which deals with declarative propositions and does not use quantifiers, and more efficient in decision problems than first-order predicate logic, which uses predicates and quantified variables over nonlogical objects. A crucial design principle in description logics is to establish favorable trade-offs between expressivity and computational complexity to suit different applications. The expressivity of each description logic is determined by the supported mathematical constructors. There are crisp general-purpose DLs, spatial, temporal, and spatiotemporal DLs, probabilistic and possibilistic DLs, and fuzzy DLs.

DL-based ontologies do not specify a particular interpretation based on a default assumption or a state of the world. Instead, they consider all possible cases in which the axioms are satisfied. This characteristic makes it possible to handle incomplete information, such as statements that have not been explicitly made yet, by keeping unspecified information open, which is called the open world assumption (OWA). The truth value of a description logic statement may be true irrespective of whether or not it is known to be true, and irrespective of whether we believe that it is true or not. Consequently, the open world assumption limits semantic reasoners in terms of deduction potential, but also prevents them from making false deductions: from the absence of a statement alone a deductive reasoner will not infer that the statement is false.

Description logics can model concepts, roles and individuals, and their relationships. A core description logic is AL, the Attributive Language, which supports atomic negation, concept intersection, universal restrictions, and limited existential quantification. An extension of AL is the Attributive Language with Complements, the description logic abbreviated as ALC. ALC supports terminological knowledge representations (TBox axioms) using subclass relationships (⊑) and equivalence (≡), conjunction (⊓), disjunction (⊔), negation (¬), property restrictions (∀, ∃), tautology (⊤), and contradiction (⊥). ALC can also represent assertional knowledge (ABox axioms), such as individual assertions (e.g., WannaCry is a ransomware) and property assertions (e.g., the severity rating of the CVE-2017-0144 vulnerability is 9.3). The naming convention of description logics is to indicate additional constructors by appending a corresponding letter, as shown in Table 1.

Table 1. Common Letters in Description Logic Names
Symbol Constructor(s) Example
AL Atomic negation, concept union, concept intersection, universal restrictions, limited existential quantification ThreatActor ≡ Individual ⊔ Organization
C Complex class expressions by combining mathematical operators such as subclass relationships, equivalence, conjunction, disjunction, negation, property restrictions, tautology, and contradiction Hacker ≡ Expert ⊓ ¬(ThreatActor ⊔ Attacker)
S ALC with transitive roles compromisedBy ◦ compromisedBy ⊑ compromisedBy
E Full existential quantification ∃hasVulnerability.Software
F Functional properties, a special case of uniqueness quantification ⊤⊑⩽1hasMD5Checksum.⊤
U Concept union AttackerKnowledge ≡ PerfectKnowledge ⊔ LimitedKnowledge ⊔ ZeroKnowledge
H Role hierarchy/subproperties hasViolatedIntegrity ⊑ isCompromised
R Complex role inclusion, reflexivity and irreflexivity, role disjointness Disjoint(isTargeted, isDiscriminate)
O Enumerated classes of object value restrictions (nominals) SHA-3 ≡ { SHA3-224, SHA3-256,
SHA3-384, SHA3-512, SHAKE128, SHAKE256 }
I Inverse properties exploitedBy ≈ exploitorOf
N Unqualified cardinality restrictions AttackSeries ≡ ≥2hasAttack.⊤
Q Qualified cardinality restrictions Key ⊑= 1hasHash.Input
(D) Data type properties, data values, or data types ⊤⊑∀⩾0cvvs.float

Note that supersets of ALC defining transitive roles denote the underlying constructs with S. Some DL languages have overlapping constructs, as, for example, union and full existential quantification can be expressed using negation, therefore U and E are never used together in DL names, and C is used instead.

By extending ALC and transitivity roles (i.e., S) with role hierarchies (H), inverse roles (I), functional properties (F), and datatypes (D), we get the SHIF(D) description logic, which roughly corresponds to OWL Lite. By adding nominals (O) and cardinality restrictions (N) to SHIF(D), we get SHOIN(D), the description logic underlying OWL DL. After industrial applications highlighted several key features missing from SHOIN(D) to model complex knowledge domains, SHOIN(D) has been extended with complex role inclusion axioms, reflexive and irreflexive roles, asymmetric roles, disjoint roles, the universal role, self-constructs, negated role assertions, and qualified number restrictions, leading to SROIQ(D), one of the most expressive description logic whose decidability is proven, and which largely corresponds to OWL 2 DL. Furthermore, SROIQ(D) supports not only TBox and ABox axioms, but also so-called Role Boxes (RBox) to collect all statements related to roles and the interdependencies between roles. Each RBox consists of a role hierarchy (including generalized role inclusion axioms) and a set of role assertions.

Notable Description Logic Subfamilies

  • General Description Logics
    • Basic Description Logics and Their Derivatives: AL, ALC, ALCHIF, ALCIQ, etc.
    • The EL Family of Description Logics: EL, ELRO (EL++), etc.
    • The DL-Lite Family of Description Logics: DL-Litecore, DL-Litebool, DL-Litekrom, DL-Litehorn, etc.
    • Frame-Based Description Logics (FL)
    • The SH Family of Description Logics: SHOIN, SROIQ, etc.
  • Spatial Description Logics: ALCRP(D), ALCRP3(D), ALC(DRCC8), etc.
  • Temporal Description Logics
  • Spatiotemporal Description Logics
  • Probabilistic Description Logics
  • Possibilistic Description Logics
  • Fuzzy Description Logics

Relation to Other Logics

Many description logics are decidable fragments of first-order logic (FOL), also known as first-order predicate calculus (FOPC), and are fully-fledged logics with formal semantics. Description logics are closely related to propositional modal logic, which extends classical propositional and predicate logic to include operators expressing modality in the form of necessity, possibility, impossibility, and related notions, and guarded fragments, which generalize modal quantification through finding relative patterns of quantification.

Description Logic Books

  • Sikos, L. F. (2017) Description Logics in Multimedia Reasoning. Cham, Switzerland: Springer. doi: 10.1007/978-3-319-54066-5
  • Baader, F., Horrocks, I., Lutz, C., Sattler, U. (2017) An Introduction to Description Logic. Cambridge University Press, New York. DOI: 10.1017/9781139025355
  • Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., Patel-Schneider, P. F. (2010) The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition. Cambridge University Press, New York

Description Logic Conferences