Seminaive Materialisation in DatalogMTL
This work addresses performance bottlenecks in temporal reasoning for applications like ontology-based data access and stream reasoning, representing an incremental improvement over existing methods.
The paper tackles the inefficiency of naive materialisation-based reasoning in DatalogMTL, a temporal extension of Datalog, by proposing a seminaive algorithm that minimizes redundant computations, resulting in significantly reduced materialisation times as shown in experiments.
DatalogMTL is an extension of Datalog with metric temporal operators that has found applications in temporal ontology-based data access and query answering, as well as in stream reasoning. Practical algorithms for DatalogMTL are reliant on materialisation-based reasoning, where temporal facts are derived in a forward chaining manner in successive rounds of rule applications. Current materialisation-based procedures are, however, based on a naive evaluation strategy, where the main source of inefficiency stems from redundant computations. In this paper, we propose a materialisation-based procedure which, analogously to the classical seminaive algorithm in Datalog, aims at minimising redundant computation by ensuring that each temporal rule instance is considered at most once during the execution of the algorithm. Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.