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

Víctor Gutiérrez-Basulto, Jean Christoph Jung, Roman Kontchakov

Introduction

Ontology-Based Data Access (OBDA) has become a cornerstone of the Semantic Web, enabling users to query heterogeneous data through high-level conceptual models. While well-established for static data, extending OBDA to temporal domains—such as electronic health records (EHRs) or sensor networks—presents significant challenges. This paper investigates $T\mathcal{EL}$, a temporal extension of the $\mathcal{EL}$ family of description logics, which is widely used in large-scale medical ontologies like SNOMED CT.

The primary hurdle in temporalizing $\mathcal{EL}$ is the "undecidability trap": adding standard temporal operators (e.g., "next", "always", "sometime in the past") often renders reasoning tasks computationally infeasible. This research aims to identify tractable fragments of $T\mathcal{EL}$ that balance expressivity with efficiency for data-intensive applications.

Methodology: Canonical Models and Traces

To analyze the complexity of temporal atomic queries (TAQs), the authors introduce Canonical Quasimodels. These structures represent the "universal model" of a temporal knowledge base using "traces"—abstract representations of how an individual's properties evolve over discrete time steps.

Illustration of temporal traces and projections in a canonical model.

Key methodological components include:

  • Ultimate Periodicity: A semantic condition where traces eventually become repetitive, ensuring decidability for certain fragments.
  • Syntactic Restrictions: The introduction of novel acyclicity conditions, such as DL-Acyclicity (restricting recursion in the description logic) and Temporal Acyclicity (restricting recursion through temporal operators).
  • Datalog Rewriting: Demonstrating that queries in specific fragments can be rewritten into DATALOG$_{1S}$ (Datalog with a successor function), facilitating the use of existing deductive database engines.

The Complexity Landscape of TAQs

The core contribution of this work is a detailed mapping of the computational complexity for various $T\mathcal{EL}$ fragments. The authors prove that while the full logic $T\mathcal{EL}^\diamond$ is undecidable, several practical restrictions lead to tractability.

Complexity landscape of Temporal Atomic Queries (TAQs) for various $T\mathcal{EL}$ fragments.

Key Findings:

  • Rigid Roles: Relationships that remain constant over time are a primary source of complexity. Restricting their interaction with temporal operators is crucial for maintaining efficiency.
  • Acyclicity as a Scalpel: By constraining only one dimension of the logic (either DL or temporal), the authors identify fragments like Acyclic $T\mathcal{EL}^\bigcirc$ that reside in $AC^0$ for data complexity. This allows for highly efficient query execution via standard SQL translation.
  • Tractable Fragments: Fragments such as Temporally Acyclic $T\mathcal{EL}^\bigcirc$ and $T\mathcal{EL}^\bigcirc_{loc}$ (using only local roles) are shown to be PTIME-complete in data complexity, making them suitable for real-world data scales.

Conclusion and Future Directions

This research provides the mathematical foundation for temporal OBDA using $\mathcal{EL}$. While identifying several tractable paths, it also highlights open challenges:

  • Decidability Gap: The decidability of the full $T\mathcal{EL}^\bigcirc$ fragment remains an open question.
  • Query Expressivity: Future work will extend these results from Atomic Queries to more complex Conjunctive Queries (CQs).
  • Data Representation: Investigating binary-encoded timestamps and interval-based temporal data will be essential for aligning these theoretical results with practical database implementations.

Summary updated

BibTeX
@inproceedings{gutierrezbasulto2016temporalized,
  author = {Víctor Gutiérrez-Basulto and Jean Christoph Jung and Roman Kontchakov},
  title = {{Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure