TL;DR
This paper introduces a novel approach to querying temporal knowledge bases using a rewriting technique that significantly outperforms existing methods in terms of speed. By transforming complex temporal queries into a more manageable form, the authors achieve substantial performance gains, making temporal data analysis more practical for AI systems.
What Problem Does This Paper Address?
Modern AI systems, especially in domains like autonomous driving, generate vast amounts of temporal data. To ensure safety and operational efficiency, it's crucial to analyze this data logically. This is often done using temporal knowledge bases (TKBs), which combine temporal data with background knowledge expressed in expressive description logics (DLs). Querying these TKBs, particularly with temporal conjunctive queries (TCQs), is computationally challenging. Existing methods, often relying on automata construction, can be inefficient. This paper addresses the need for a more performant and practical method for answering TCQs over expressive DL ontologies.
Methods
The core contribution is a novel rewriting-based approach to answering TCQs. Instead of building complex automata, the authors propose transforming a TCQ into a specific normal form. This normal form ensures that temporal disjunctions can be handled inductively, and the problem is reduced to answering unions of possibly negated conjunctive queries (UnCQs). The approach leverages two sets of rules: standard expansion laws for temporal operators and rules for distributing disjunctions. The query transformation process, called Transform(Φ), aims to simplify the query structure, ensuring that temporal operators are "wrapped" and disjunctions have at most one temporal disjunct. The actual answering is then performed by a recursive algorithm that either calls a specialized AnswerUnCQ function for non-temporal parts or recursively calls itself for temporal parts.
Datasets
The paper evaluates its approach on two benchmark sets:
- Traffic Ontology Benchmark (TOBM): This benchmark models pedestrians, bicyclists, and vehicles over 200 time points using a large ontology. It allows for scaling the number of individuals.
- Two-wheeler benchmark: This benchmark focuses on a single query related to granting right of way and uses TKBs with three time points, also allowing for scaling.
The authors note that these are the only two existing benchmark sets for temporal querying over expressive DLs known to them.
Key Insights and Ideas
- Rewriting is more efficient than automata: The paper strongly suggests that a query rewriting approach can be significantly faster than traditional automata-based methods for temporal query answering. This is attributed to a more precise use of underlying query answering engines.
- UCQ answering is a bottleneck: The performance of existing methods is often hampered by the need to answer complex Union of Conjunctive Queries (UCQs). The proposed rewriting approach aims to minimize or even eliminate the need for UCQ answering in certain cases.
- A decidable fragment for efficiency: The authors identify a syntactic fragment of TCQs, called
TCQcQ*, for which queries can be answered using only standard conjunctive query (CQ) answering, completely avoiding UCQ checks. This fragment is proposed as a guide for users to write more efficient queries. - Empirical evidence for performance: The experimental results provide strong evidence that the rewriting approach leads to substantial speedups, sometimes by orders of magnitude, compared to the state-of-the-art.
Key Results
- Significant Speedup: The proposed rewriting approach achieved an average speedup of 19.09x over the FA-based approach on the TOBM benchmarks, with some cases showing improvements by two orders of magnitude. In several instances, the FA-based approach timed out, while the new method completed the queries.
- Reduced UCQ Checks: The paper demonstrates that their approach significantly reduces the number of UCQ entailment checks. For the two-wheeler benchmark with a specific query
A(x) ∧ ◊B(x), their algorithm performed no UCQ checks, whereas the FA-based approach exhibited a linearly increasing number of UCQ checks with benchmark size. - Optimality for ALC: The approach is proven to be worst-case optimal for the description logic ALC, running in exponential time, which matches the known complexity of TCQ entailment.
Limitations and Future Work
- Focus on ALC: While the approach is applicable to other DLs, the theoretical analysis and experimental evaluation are primarily focused on ALC.
- Past Temporal Operators: The current work does not consider past temporal operators. The authors suggest extending the approach to include these.
- Deciding TCQcq: An open question is whether the
TCQcqfragment (queries answerable by CQs only) can be efficiently decided. - Restricted Negation: The authors plan to investigate extending the
TCQcq*fragment to include restricted forms of negation while preserving its favorable properties. - Stronger Rewritings: Exploring rewritings that transform not just the temporal component but the entire TCQ, potentially for Horn DLs or temporal Datalog, is another future direction.
Summary updated