First-Order Rewritability of Temporal Ontology-Mediated Queries

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, Michael ZakharyaschevIJCAI 2015

Introduction

Ontology-Based Data Access (OBDA) has revolutionized how we interact with heterogeneous data by providing a high-level conceptual layer. However, as data becomes increasingly dynamic—driven by sensor networks and industrial IoT—the need to extend OBDA to the temporal domain has become critical. This paper investigates the theoretical foundations of querying temporal data through ontologies, focusing on the concept of First-Order (FO) rewritability.

The Challenge of Temporal Rewritability

In standard OBDA, the goal is to "rewrite" a query and an ontology into a single query (typically SQL) that can be executed directly by a database engine. This ensures that query evaluation remains highly scalable, ideally falling within the complexity class $AC^0$ relative to data size.

When temporal operators like "always in the past" ($\boxminus$) or "next" ($\bigcirc$) are introduced, the logic becomes significantly more complex. The authors aim to identify which combinations of temporal operators and description logic (DL) fragments allow for efficient FO-rewritings, ensuring that query evaluation remains scalable even when dealing with long-term dependencies.

Methodological Framework

The research employs a two-step approach. First, the authors analyze Temporal Ontology-Mediated Queries (TOMQs) as Linear Temporal Logic (LTL) problems, abstracting away relationships between objects. They use automata-theoretic techniques to model how information propagates through time steps according to the ontology.

Illustration of information propagation across time steps using temporal operators.

Second, these LTL results are integrated with the $DL-Lite$ family of description logics, which underpins the OWL 2 QL profile. The study evaluates rewritability into three target languages: $FO(<)$ (precedence), $FO(<, +)$ (precedence and addition), and $MSO(<)$ (monadic second-order logic).

A Landscape of Tractability

The core contribution of the paper is a comprehensive classification of the rewritability of various TOMQ fragments. The authors provide a map of which logic combinations lead to specific complexity classes.

Summary of rewritability results for various temporal ontology-mediated query fragments.

Key findings include:

  • $DL-Lite_{core}$ Success: Queries based on the simplest fragment are shown to be $FO(<, +)$-rewritable.
  • The Role of Addition: To handle periodic events (e.g., "every 24 hours"), the target language must support addition ($FO(<, +)$).
  • The Parity Barrier: Some ontologies can implicitly calculate "parity" (e.g., checking if an event happened an even number of times). Since standard FO logic cannot express parity, these cases are not FO-rewritable.

Key Insights and Theoretical Boundaries

The authors utilize "canonical models" (or "chases") to show that for certain Horn-logic fragments, a single representative model can be used to answer all positive temporal queries. However, they also identify significant boundaries: while many Horn-based queries are $FO(<)$-rewritable, others are $NC^1$-hard, meaning they cannot be rewritten into FO logic.

Furthermore, the paper highlights a gap between theoretical tractability and practical feasibility. While a rewriting might exist, its size can grow triple-exponentially relative to the query and ontology, posing a major challenge for current database engines to execute efficiently.

Conclusion and Future Directions

This work successfully maps the "islands of tractability" for temporal OBDA. While it provides a solid theoretical foundation for $DL-Lite_{core}$ and $DL-Lite_{horn}$, future research must address the succinctness of rewritings and extend these results to full Conjunctive Queries (CQs) to bridge the gap between theory and industrial application.

Summary updated

BibTeX
@inproceedings{artale2015first,
  author = {Alessandro Artale and Roman Kontchakov and Alisa Kovtunova and Vladislav Ryzhikov and Frank Wolter and Michael Zakharyaschev},
  title = {{First-Order Rewritability of Temporal Ontology-Mediated Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure