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.
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.
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