Abstract
Modern context-aware systems require the ability to reason over data that evolves over time. This paper explores the efficiency of answering temporal queries using the lightweight description logic $\mathcal{EL}$ as a foundation for background knowledge. By mapping the computational complexity of Temporal Conjunctive Queries (TCQs) and $\mathcal{EL}$-LTL, the authors demonstrate how the introduction of "rigid" symbols—properties that do not change over time—significantly impacts performance. While $\mathcal{EL}$ is generally efficient, certain configurations can lead to high computational costs, providing a nuanced view of its suitability for real-time temporal reasoning.
Introduction
Context-aware systems, such as smart homes or operating systems, must recognize complex situations based on temporal sensor data. For instance, an OS might need to determine if a user has paused a video for a specific duration while another application was active. To address such needs, Ontology-Based Data Access (OBDA) uses a domain "dictionary" (an ontology) to supplement incomplete sensor data.
While expressive logics like $\mathcal{ALC}$ have been the focus of previous research, their high computational complexity (often EXPTIME or higher) limits their practical application. This paper focuses on $\mathcal{EL}$, a lightweight logic used in large-scale ontologies like SNOMED CT, to evaluate its potential for more efficient temporal reasoning.
Methods
The research investigates two primary formalisms:
- Temporal Conjunctive Queries (TCQs): These integrate standard database queries with Linear Temporal Logic (LTL) operators such as "always," "eventually," and "since."
- $\mathcal{EL}$-LTL: This logic allows the axioms of the ontology itself to be combined with temporal operators.
The authors employ a propositional abstraction methodology. This approach decouples the temporal reasoning from the description logic reasoning. Temporal formulas are treated as propositional variables to check for consistency, while specialized DL reasoners ensure these truth values are consistent with the ontology and the temporal data sequence.
Key Insights and Results
The study reveals that the primary driver of complexity is not the volume of data, but the presence of rigid symbols—concepts or roles that remain constant across all time points (e.g., a birth date).
The "Rigidity" Tax
The complexity of temporal reasoning increases significantly when rigid symbols are introduced. Without them, answering temporal queries is highly efficient. However, allowing rigid roles can push the combined complexity to extreme levels.
Complexity Map
The authors provide a detailed complexity map for various reasoning tasks under different constraints.
Key findings include:
- Data Complexity: In the absence of rigid symbols, TCQ entailment is in P (polynomial time). With rigid symbols, it becomes CO-NP-hard.
- Combined Complexity: Depending on the use of rigid roles, complexity ranges from PSPACE to CO-NEXPTIME.
- Satisfiability: $\mathcal{EL}$-LTL satisfiability is generally NEXPTIME-complete with rigid concepts but drops to PSPACE when using only global background knowledge.
Conclusion and Future Work
The research highlights a critical trade-off: the features most useful for real-world modeling (rigid roles and concepts) are the ones that increase computational overhead. While data complexity remains manageable in many scenarios, the combined complexity can become a bottleneck for complex rule sets.
Future research is directed toward DL-Lite, another lightweight logic family. The authors hypothesize that TCQs over DL-Lite might support first-order query rewriting, potentially enabling the use of optimized SQL databases for temporal query answering, further improving performance for real-time systems.
Summary updated