Description logic

Description logic (DL) is the dominant knowledge representation formalism, used by both OBO and OWL (Semantic Web).

Nomenclature

DL has a self-describing naming system [Baader et al, 2007, Appendix: DL Terminology]. Unfortunately, it is not entirely consistent across the literature.

My attempt at a summary is below. See also Evgeny Zolin’s encyclopedic page on complexity of reasoning in description logics .

  • \(\mathcal{A}\mathcal{L}\) [Attributive Concept Language, the most basic DL]
    • Atomic concept (\(A\)), universal concept (\(\top\)), bottom concept (\(\bot\))
    • Atomic negation (\(\neg A\))
    • Concept intersection (\(C \cap D\))
    • Value restriction (\(\forall R.C\))
    • Limited existential quantification (\(\exists R.\top\))
    • Concept hierarchy (\(C \subseteq D\), \(C \equiv D\))
  • \(\mathcal{A}\mathcal{L}\mathcal{C}\) (equivalently \(\mathcal{A}\mathcal{L}\mathcal{U}\mathcal{E}\))
    • \(\mathcal{C}\): Concept negation (\(\neg C\))
    • \(\mathcal{U}\): Concept union (\(C \cup D\))
    • \(\mathcal{E}\): “Full” existential quantification (\(\exists R.C\))
  • \(\mathcal{H}\): Role hierarchies (\(R \subseteq S\), \(R \equiv S\))
  • \(\mathcal{I}\): Inverse roles (\(R^{-}\))
  • \(\mathcal{N}\): (Unqualified) number restriction (\(\geq n~R\), \(\leq n~R\), \(= n~R\))
  • \(\mathcal{Q}\): Qualified number restriction (\(\geq n~R.C\), \(\leq n~R.C\), \(= n~R.C\))
  • \(\mathcal{O}\): Nominals [class literals] (\(\{x_1,x_2,\ldots,x_n\}\))
  • \(\mathcal{F}\): Depending on author, EITHER
    • Functional roles (\(\leq 1~R\)), a restricted form of \(\mathcal{Q}\), OR
    • Agreement and disagreement [Baader et al, 2007, Table A.1]
  • \(\mathcal{R}\): Depending on author, EITHER
    • Role intersection (\(R \cap S\)), OR
    • Regular role inclusion axioms [regular RIAs] (\(R_1 \circ R_2 \circ \cdots \circ R_n \subseteq S\))
      • Regular means acyclic, which ensures decidability
      • May include other features: disjoint roles, reflexive, irreflexive, etc.
  • \((\mathcal{D})\): Concrete domains, e.g., natural numbers with \(<,\leq,=,>,\geq\)

Languages

  • \(\mathcal{S}\) = \(\mathcal{A}\mathcal{L}\mathcal{C}\) + transitive relations [as declaration, not as transitive closure]
  • OWL 1 Lite = \(\mathcal{SHIF}\) (ref )
  • OWL 1 DL = \(\mathcal{SHION}\) (ref )
  • OWL 2 DL = \(\mathcal{SRIOQ}\) (ref )

Literature

Books

  • Baader et al, 2007: The Description Logic Handbook, 2nd ed.
    • Most comprehensive reference on DL
    • Covers OWL 1 (Ch. 14) but not OWL 2
  • Robinson & Bauer, 2011: Introduction to Bio-ontologies
    • DL from a bioinformatics perspective
  • Hitzler et al, 2010: Foundations of Semantic Web Technologies
    • Coverage of RDFS and OWL 2 with more mathematical formality than usual

Surveys and tutorials

  • Rudolf, 2011: Foundations of description logics (doi, pdf)
  • Krotzsch, Simancik, Horrocks, 2012: A description logic primer (arxiv)

DL in Semantic Web

  • Horrocks, Kutz, Sattler, 2005: The irresistible SRIQ (pdf)
  • Horrocks, Kutz, Sattler, 2006: The even more irresistible SROIQ (pdf)
  • Knorr, Alferes, Hitzler, 2011: Local closed world reasoning with description logics under the well-founded semantics (doi, pdf)
  • Sengupta, Krisnadhi, Hitzler: 2011: Local closed world semantics: Grounded circumscription for OWL (doi, pdf)

Critical perspectives on DL

  • Doyle & Patil, 1991: Two theses of KR: Language restrictions, taxonomic classification, and the utility of representation services (doi, pdf)
    • Cogent criticisms of the restricted language thesis and restricted classification thesis
  • Hitzler, 2009: Towards reasoning pragmatics (doi)