# Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)

arXiv: https://arxiv.org/abs/1905.12990 · HTML: https://mlsanity.com/paper/1905.12990/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

## Built on by (most cited first, 5 of 5)

- [MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators](https://mlsanity.com/paper/2201.04596/) (2022)
- [On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)](https://mlsanity.com/paper/2501.13762/) (2025)
- [Query Evaluation in DatalogMTL -- Taming Infinite Query Results](https://mlsanity.com/paper/2109.10691/) (2021)
- [Seminaive Materialisation in DatalogMTL](https://mlsanity.com/paper/2208.07100/) (2022)
- [Inconsistency Handling in DatalogMTL](https://mlsanity.com/paper/2505.10394/) (2025)

## Abstract (arXiv)

We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes of ontology-mediated queries answering which can be done in AC0, NC1, L, NL, P, and coNP for data complexity, provide their rewritings to first-order logic and its extensions with primitive recursion, transitive closure or datalog, and establish lower complexity bounds.