On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic (Extended Abstract)

Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, Michael ZakharyaschevIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of querying time-series data using ontologies. The authors propose using Linear Temporal Logic (LTL) for ontologies and monadic first-order logic with ordering (<) for queries. They provide a classification of these "ontology-mediated queries" (OMQs) based on their "first-order rewritability," which determines how efficiently they can be answered. This work is crucial for enabling more sophisticated temporal data analysis in areas like industrial monitoring.

What Problem Does This Paper Address?

Managing and querying temporal data, especially in complex systems like industrial sensors, is a significant challenge. While ontology-mediated query answering (OMQA) has been successful for static data, it struggles with temporal aspects. Existing approaches often lead to computationally intractable reasoning or ruin the desirable property of "first-order (FO-) rewritability." FO-rewritability is key because it allows complex ontology-mediated queries to be translated into standard database queries, making them efficient to execute. The problem is how to extend OMQA to temporal data without sacrificing this efficiency and expressiveness. The authors aim to bridge this gap by developing a framework that combines temporal logic for ontologies with temporal logic-based queries, while still allowing for efficient rewritability.

Methods

The core of this paper is the formalization of a temporal OMQA framework. They propose using:

  • Linear Temporal Logic (LTL) for ontology definitions. LTL is a well-established logic for reasoning about sequences of events over time. The axioms are presented in a clausal normal form, which is standard for logical reasoning.
  • Monadic First-Order Logic with ordering (<) (MFO(<)) for query formulation. This logic allows expressing relationships between time points, like "before" or "after," and can handle multiple variables.

The central concept is FO-rewritability. An OMQ is FO-rewritable if it can be translated into an equivalent first-order logic formula that can be evaluated directly over the data. The paper classifies OMQs based on the type of FO-rewriting they admit (e.g., FO(<), FO(<,=)) and the complexity class of their evaluation (e.g., AC⁰, NC¹, PSPACE). They achieve this by analyzing the structure of the LTL ontologies (Boolean, Horn, Krom, Core clauses) and the MFO(<) queries (atomic, quasi-positive).

Datasets

Not discussed in the paper. The paper focuses on the theoretical classification of query types and their rewritability, rather than empirical evaluation on specific datasets. The examples use hypothetical data instances (e.g., sensor readings from gas turbines).

Key Insights and Ideas

  • LTL as a practical ontology language for temporal data: The authors argue that LTL, despite being a fragment of MFO(<), is more intuitive for expressing temporal domain knowledge than full first-order logic. This is supported by Kamp's Theorem, which shows equivalence for single-variable formulas.
  • MFO(<) is necessary for expressive temporal queries: While LTL is good for ontologies, MFO(<) is needed for queries that involve complex temporal patterns or multiple answer variables, which cannot be easily expressed in LTL.
  • A uniform classification scheme: The paper provides a systematic way to classify temporal OMQs based on the ontology's structure, the query's complexity, and the temporal operators used. This classification helps predict the computational complexity of answering these queries.
  • The "curse of many-dimensional logics" can be avoided: By carefully choosing LTL for ontologies and MFO(<) for queries, the authors show that it's possible to maintain FO-rewritability, a property often lost when temporal operators are added to more expressive ontology languages.

Key Results

The paper presents several theorems that classify the FO-rewritability of temporal OMQs:

  • Theorem 3: OMQs with LTL ontologies and MFO(<) queries are always rewritable to FO(RPR) and MSO(<), meaning they can be answered in NC¹ for data complexity. This is a significant result, placing these queries in a computationally efficient class.
  • Theorem 5: This theorem provides a detailed classification based on the ontology's clause type and the query's complexity:
  • Atomic queries with Boolean LTL ontologies are FO(<)-rewritable.
  • Atomic queries with Horn LTL ontologies and quasi-positive MFO(<) queries are FO(<)-rewritable.
  • Some OMQs with Krom or Core ontologies are FO(<,=)-rewritable, but not always FO(<)-rewritable, indicating a trade-off between expressiveness and efficiency.
  • Certain combinations (e.g., Horn ontologies with atomic queries, Krom ontologies with quasi-positive queries) lead to NC¹-hard complexity, suggesting that these are among the most computationally demanding temporal OMQs.

Limitations and Future Work

  • Open-world vs. Epistemic Semantics: The paper primarily uses an "open-world" semantics for OMQA. While they briefly mention "epistemic semantics" (ES) as an alternative that can lead to decidability for some cases, a full exploration of ES for their framework is left for future work.
  • Discrete vs. Continuous Time: The current framework is based on discrete time (integers). The authors acknowledge that for scenarios with asynchronous sensor readings, continuous time formalisms like Metric Temporal Logic (MTL) might be more appropriate, but this presents a significantly greater challenge for classification and rewritability.
  • Beyond MFO(<) and LTL: The paper hints at the need to extend the framework for n-ary relations and more expressive DL constructs, suggesting future work in combining temporal logic with description logics.
  • Practical System Implementation: While the theoretical classification is valuable, building practical OBDA systems that can leverage these rewritability results for efficient temporal query answering remains an ongoing challenge.

Summary updated

BibTeX
@inproceedings{artale2022first,
  author = {Alessandro Artale and Roman Kontchakov and Alisa Kovtunova and Vladislav Ryzhikov and Frank Wolter and Michael Zakharyaschev},
  title = {{On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/794},
}
Figure