Introduction
Datalog is a foundational logic programming language used to derive new facts from existing data. DatalogMTL extends this capability by incorporating Metric Temporal Logic (MTL) operators, enabling rules that reason over time. For example, a rule might state: "If a patient had a high fever in the last 24 hours and received medication 6 hours ago, monitor their vitals."
The primary challenge in DatalogMTL is recursion through time. Unlike standard Datalog, where the derivation process (materialisation) naturally reaches a fixpoint, temporal rules can trigger each other indefinitely across an infinite timeline. Traditional solutions often involve complex automata-based reasoning, which is theoretically sound but frequently inefficient and difficult to implement in practical database systems.
Methodology: Saturation and Periodicity
This research introduces a reasoning approach based on materialisation (forward chaining) that exploits the ultimately periodic nature of temporal models. The authors prove that even if a timeline is infinite, the facts derived by DatalogMTL rules eventually settle into a repeating pattern.
Detecting Saturation
The core of the algorithm is a "saturation check." The researchers defined specific conditions under which a partial materialisation can be considered "saturated." If the facts within two distinct time intervals are identical (modulo a time shift) and meet certain depth requirements, a periodic cycle has been identified.
Unfolding the Period
Once saturation is detected, the algorithm stops applying rules. To answer a query about any point in the infinite future or past, the system "unfolds" the discovered period. The query is mapped to its corresponding position within the repeating cycle, allowing for definitive answers without further computation. This "automata-free" method handles bounded intervals (fixed start and end points) and integrates seamlessly with standard forward-chaining engines.
Experimental Evaluation
The implementation was evaluated against MeTeoR, a state-of-the-art temporal reasoner, using benchmarks like the Lehigh University Benchmark (LUBM) extension and iTemporal.
Performance Stability
A key advantage of this approach is its independence from "query distance." In many systems, checking a fact 1,000 days in the future is significantly more expensive than checking one 10 days away. As shown in the results, once the proposed algorithm reaches saturation, query times remain flat and near-instant.
Scalability and Overhead
The algorithm demonstrates linear scalability with respect to both the number of facts and the temporal range. In tests with up to 100 million facts, the system remained robust. Furthermore, the overhead of performing saturation checks during materialisation was found to be negligible, ensuring that the algorithm performs as efficiently as standard forward chaining until a periodic shortcut is found.
Conclusion and Future Work
By proving that saturation can be detected during standard materialisation, this work provides a practical path for temporal reasoning in large-scale databases without the need for heavy automata machinery. While currently limited to bounded intervals and programs without unrestricted negation, the "ultimately periodic" insight offers a powerful foundation for future extensions in temporal logic programming.
Summary updated