Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries

TL;DR

This paper investigates the computational complexity of querying temporal data using a description logic called TEL. The authors establish that unrestricted TEL is undecidable for query answering, even in data complexity, and then identify several tractable fragments by imposing restrictions on role usage and ontology structure. These findings are crucial for developing practical systems that can efficiently query temporal information in areas like the Semantic Web and healthcare.

What Problem Does This Paper Address?

The Semantic Web relies heavily on ontologies to structure and query data. As more data becomes temporal (e.g., sensor readings, medical histories), there's a growing need to incorporate temporal reasoning into these ontologies. Description Logics (DLs) are a popular choice for ontology languages, and extensions to handle time are being developed. However, many temporal DLs suffer from high computational complexity, making them impractical for real-world applications.

This paper focuses on TEL, a temporal extension of the widely used EL (Existential) description logic, which underpins OWL 2 EL and SNOMED CT. The authors aim to map out the computational complexity landscape for answering "atomic queries" (simple queries about individuals and their properties at specific times) in TEL. They want to understand the limits of decidability and tractability, particularly in terms of "data complexity" (where the ontology is fixed and the data varies) and "combined complexity" (where both ontology and data can vary).

Methods

The core of the paper is a detailed complexity analysis of TEL and its fragments.

  • Undecidability Results: The authors first prove that answering atomic queries in full TEL is undecidable, even when considering only data complexity. This is a significant finding, as it highlights the inherent difficulty of temporal reasoning in this logic. They also show that TEL°, a fragment allowing only "next" and "previous" temporal operators, is non-elementary in combined complexity and PSPACE-hard in data complexity.
  • Fragments and Tractability: To overcome undecidability, the paper identifies and analyzes several tractable fragments of TEL:
  • Ultimately Periodic Traces: A semantic condition called "ultimate periodicity" on the traces of a knowledge base's canonical model is introduced. If a TEL°-TBox satisfies this condition, atomic query answering is PSPACE-complete in data complexity. This is achieved by rewriting queries into DATALOG₁s.
  • Restricted Use of Rigid Roles: TEL°loc, where only local roles are allowed, leads to PTIME-complete data complexity and PSPACE-complete combined complexity.
  • Acyclicity Conditions: Two novel acyclicity conditions are proposed:
  • DL-acyclic TEL°: This fragment, where the DL component is acyclic, results in NC¹-complete data complexity and k-EXPSPACE-complete combined complexity for depth k. This is a notable finding, as it's one of the first DLs shown to have NC¹-complete query answering.
  • Temporally acyclic TEL°: This fragment allows recursion in the DL dimension but not in the temporal dimension. It leads to PTIME-complete data and combined complexity.
  • Inflationary TEL: This fragment, restricting CIs to have temporal operators only on the left-hand side, also achieves PTIME-complete data and combined complexity.
  • Canonical Quasimodels: A key technical tool used throughout the paper is the concept of "canonical quasimodels." These are succinct abstract representations of the universal model of a knowledge base, generalizing canonical structures used in atemporal DLs. They are crucial for understanding the semantics and developing algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • Undecidability is the Norm: The paper demonstrates that temporalizing even a decidable logic like EL (via TEL) can quickly lead to undecidability, even for simple atomic queries. This underscores the challenge of temporal reasoning.
  • The Power of Acyclicity: The introduction of two novel acyclicity conditions (DL-acyclic and temporally acyclic) is a significant contribution. These conditions effectively tame the complexity of temporal DLs, leading to highly tractable fragments (NC¹ and PTIME). This suggests that carefully structured ontologies can be both expressive and efficient.
  • NC¹ for Temporal DLs: The DL-acyclic fragment achieving NC¹-complete data complexity is a particularly exciting result. It suggests that for certain temporal ontology structures, query answering can be extremely efficient and highly parallelizable.
  • Canonical Quasimodels as a Unifying Tool: The paper leverages canonical quasimodels as a central concept for both semantic understanding and algorithmic development across various TEL fragments. This provides a consistent framework for analyzing temporal DLs.
  • Practical Relevance: The identified tractable fragments are motivated by real-world applications (e.g., SNOMED CT, medical records, clinical trials) and the need for efficient query answering in ontology-based data access (OBDA) systems.

Key Results

  • TEL is Undecidable: Atomic query answering over full TEL is undecidable in data complexity.
  • TEL° Complexity: Atomic query answering over TEL° is non-elementary in combined complexity and PSPACE-hard in data complexity.
  • Ultimately Periodic TEL°: PSPACE-complete data complexity for query answering.
  • TEL°loc: PTIME-complete data complexity and PSPACE-complete combined complexity.
  • DL-acyclic TEL°: NC¹-complete data complexity and k-EXPSPACE-complete combined complexity (for depth k).
  • Temporally acyclic TEL°: PTIME-complete data and combined complexity.
  • Inflationary TEL: PTIME-complete data and combined complexity.

Limitations and Future Work

  • Decidability of Full TEL°: The decidability of atomic query answering over full TEL° (without the specific acyclicity or role restrictions) remains an open question.
  • Conjunctive Queries: The paper focuses on atomic queries. Extending the results to more complex query types, such as conjunctive queries (CQs), is a natural next step. The authors believe their framework can be adapted for this.
  • + Operator in Queries: The paper primarily considers queries with temporal operators like ◇* and *. Investigating queries involving the + operator (e.g., "exactly k time steps ago") is also a future direction.
  • Interval Encoding: The paper mentions exploring interval encoding of temporal ABoxes and handling infinite temporal periodic data, which are important for practical data representation.
  • Practical Implementations: While the theoretical results are strong, translating these findings into efficient, practical query answering systems for temporal ontologies is an ongoing challenge. The authors suggest that the identified tractable fragments are good candidates for such systems.

Summary updated

BibTeX
@inproceedings{2016temporalized,
  title = {{Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure