Tractable Diversity: Scalable Multiperspective Ontology Management via Standpoint EL

Lucía Gómez Álvarez, Sebastian Rudolph, Hannes StrassIJCAI 2023 · DOI

TL;DR

This paper introduces Standpoint EL (SEL), a novel description logic that allows for the integrated representation of knowledge from multiple, potentially conflicting perspectives. They demonstrate that SEL maintains the efficient polynomial-time reasoning capabilities of the EL family while enabling richer, context-dependent knowledge modeling, crucial for large-scale ontologies.

What Problem Does This Paper Address?

Modern ontologies, like SNOMED CT in healthcare, are massive and used by diverse groups. This diversity leads to inherent ambiguity and differing perspectives on the same concepts (e.g., "Tumour" as a process vs. a tissue). Existing description logics struggle to represent these conflicting viewpoints coherently. While some approaches exist for handling context or multiple viewpoints, they often sacrifice scalability or expressivity. The authors aim to bridge this gap by providing a formal framework that can manage multiperspective knowledge in a scalable and tractable manner.

Methods

The core contribution is the introduction of Standpoint EL (SEL), an extension of the EL description logic. SEL incorporates standpoint names and modal operators (box and diamond) to qualify statements with respect to specific viewpoints. For example, □s[Concept] means "according to standpoint s, Concept is unequivocally true."

Key methodological contributions include:

  • Syntax and Semantics: Defining a formal language and a Kripke-style semantics for SEL, where standpoints are mapped to sets of "precisifications" (essentially, possible worlds).
  • Normal Form: Developing a normalization procedure for SEL knowledge bases to simplify reasoning.
  • Tableau Algorithm: Presenting a PTIME tableau decision algorithm for checking satisfiability in SEL. This algorithm constructs a "completion graph" and applies local and global rules to detect inconsistencies.
  • Complexity Analysis: Proving that SEL satisfiability is PTIME-complete, matching the tractability of standard EL. They also show that adding features like empty standpoints, rigid roles, or nominal concepts can quickly lead to intractable reasoning (NP-hard or worse).

Datasets

Not discussed in the paper. The paper focuses on the formal language and reasoning algorithms, using illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tractable Multiperspectivity: The most significant insight is that it's possible to introduce multiperspective reasoning into a highly tractable description logic (EL) without losing its efficiency. This opens the door for managing complex, real-world knowledge with diverse viewpoints.
  • Standpoints as First-Class Citizens: By treating standpoints as explicit linguistic constructs (via modal operators), SEL provides a clean and formal way to manage conflicting information.
  • The Cost of Expressivity: The paper clearly delineates the boundaries of tractability. While SEL itself is efficient, adding common ontological features like nominals or rigid roles (even just one) drastically increases complexity, highlighting the trade-offs in knowledge representation.
  • Bridging Perspectives: The formalism allows for explicit statements about how different standpoints relate to each other (e.g., using "sharpening statements" like s < s'), enabling reasoned connections between diverse views.

Key Results

  • PTIME-Completeness of Standpoint EL: The paper establishes that satisfiability checking for Standpoint EL knowledge bases is PTIME-complete.
  • Worst-Case Optimal Tableau Algorithm: A tableau-based algorithm is presented that achieves this PTIME complexity.
  • Intractability of Extensions:
    • Allowing empty standpoints makes satisfiability NP-hard.
  • Introducing a single rigid role makes satisfiability CONP-hard.
  • Adding nominal concepts makes TBox satisfiability EXPTIME-hard.

Limitations and Future Work

  • Limitations: The paper acknowledges that while SEL is tractable, certain desirable extensions (rigid roles, nominals) lead to intractability. The current tableau algorithm is presented conceptually, with a full implementation and empirical evaluation left for future work.
  • Future Work:
    • Implementing the tableau algorithm, potentially by adapting existing systems.
  • Developing deduction calculi over normalized axioms that can be translated into datalog programs.
  • Investigating reductions to standpoint-free EL extensions.
  • Exploring the impact of standpoints on other lightweight formalisms like OWL 2 RL and OWL 2 QL.
  • Extending the framework to handle more complex role inclusions and self-concepts.

Summary updated

BibTeX
@inproceedings{alvarez2023tractable,
  author = {Lucía Gómez Álvarez and Sebastian Rudolph and Hannes Strass},
  title = {{Tractable Diversity: Scalable Multiperspective Ontology Management via Standpoint EL}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/363},
}
Figure