Research map / Learning theory and algorithms / Combinatorial and search optimization
Temporal Conjunctive Query Answering via Rewriting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a rewriting-based algorithm for answering temporal conjunctive queries over expressive ALC temporal knowledge bases, avoiding automata and unnecessary UCQ checks, and identifies a syntactic fragment answerable with CQs only.
Problem
Answering temporal conjunctive queries (LTLf combined with CQs) over temporal knowledge bases with expressive description logic ontologies, where existing automata-based methods rely heavily on costly UCQ entailment checks.
Approach
Rewrites the temporal query into a normal form using the until-expansion law and distributivity of next over disjunction, so answers are combined inductively over time points and only (possibly negated) CQ/UnCQ entailment checks are needed, instead of compiling into a finite automaton.
Key results
- Rewriting approach improves run time on all 70 benchmarks versus the FA-based tool, with an average speedup of 19.09 on non-timeout benchmarks (std 45.79) and up to two orders of magnitude gains.
- For three benchmarks where the FA-based implementation timed out, the rewriting approach answered queries in 3.52, 5.72, and 7.88 hours.
- Eliminated UCQ entailment checks altogether in four cases; the savings are largely due to reduced UCQ answering time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM T-crossing, Φ1 | runtime (s): 626.31 -> 17.17 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM T-crossing, Φ2 | runtime (s): 2 938.23 -> 133.23 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM T-crossing, Φ3 | runtime (s): 1 420.05 -> 904.20 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM T-crossing, Φ4 | runtime (s): 13 408.60 -> 4 970.80 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM X-crossing, Φ1 | runtime (s): 457.02 -> 23.88 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM X-crossing, Φ2 | runtime (s): 350.73 -> 1.46 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM X-crossing, Φ3 | runtime (s): 2 208.70 -> 1 500.33 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · TOBM X-crossing, Φ4 | runtime (s): 31 733.18 -> 7 206.80 | Helped |
| Replace the FA-based approach with rewriting (Algorithm 1) | TCQ answering · Two-wheeler benchmark, Φ1 | runtime (s): 20.19 -> 2.53 | Helped |
Surprising findings
- Some seemingly simple temporal queries, such as diamond of conjunction of A and next B, require UCQ answering even though the rewriting approach handles most queries with CQs only.
Limitations
- Restricted to tree-shaped queries and finite data; past temporal operators not supported.
- Worst-case exponential complexity; ExpTime-complete for ALC.
- Syntactic fragment TCQCQ* is a strict subset of the semantically defined CQ-only class; deciding full TCQCQ membership is open.
Experimental setup
Datasets: TOBM traffic ontology benchmark two-wheeler right-of-way benchmark
Benchmarks: TOBM traffic ontology benchmark two-wheeler right-of-way benchmark
Metrics: wall clock run time number of UCQ entailment checks number of CQ answering calls
Baselines: FA-based approach of Westhofen et al. (2024b)
Builds on: Baader et al. automata-based TCQ answering Westhofen et al. Topllet LTLf expansion laws Openllet
Closest papers by meaning
- Ontology-Based Query Answering for Probabilistic Temporal Data (AAAI 2019 · similarity 0.90)
- Query Rewriting for Ontology-Mediated Conditional Answers (AAAI 2020 · similarity 0.87)
- Revisiting Conjunctive Query Entailment for S (AAAI 2026 · similarity 0.87)
- First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics (AAAI 2022 · similarity 0.86)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.85)
- Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.