This extended abstract summarizes our IJCAI'25 paper [1] on inconsistency handling in DatalogMTL, an extension of Datalog with metric temporal operators. Our work extends existing notions of conflicts and repairs to DatalogMTL and studies their properties. We also study the data complexity of the tasks of generating a single conflict / repair and query entailment under repair-based semantics.
There has been significant recent interest in formalisms for reasoning over temporal data [
One important issue that has yet to be addressed is how to handle the case where the temporal
dataset is inconsistent with the DatalogMTL program. Indeed, it is widely acknowledged that real-world
data typically contains many erroneous or inaccurate facts, and this is true in particular for temporal
sensor data, due to faulty sensors. In such cases, classical logical semantics is rendered useless, as
every query is entailed from a contradiction. A prominent approach to obtain meaningful information
from an atemporal dataset that is inconsistent w.r.t. a logical theory (e.g., an ontology or a set of
database integrity constraints) is to use inconsistency-tolerant semantics based on subset repairs, which
are maximal subsets of the dataset consistent with the theory [
It is natural to extend these notions to the temporal setting. First work in this direction was undertaken
in [23], which considered queries with linear temporal logic (LTL) operators, an atemporal DL-Lite
ontology, and a sequence of datasets stating what holds at diferent timepoints. In that work, however, it
was clear how to transfer definitions from the atemporal setting, and the main concerns were complexity
and algorithms. By contrast, in DatalogMTL, facts are annotated with time intervals, which may contain
exponentially or even infinitely many timepoints (if the timeline is dense or ∞/−∞ can be used as
interval endpoints). One can therefore imagine multiple diferent ways of minimally repairing an
inconsistent dataset. For example, if a dataset states that is true from 0 to 4 and from 2 to 6
( @[
Our first contribution is to explore how the basic notions of repair and conflict, which are well studied in the atemporal setting, can be suitably adapted to DatalogMTL. We first define three diferent notions of repair of a dataset w.r.t. a DatalogMTL program Π . We omit the formal definitions, which are somewhat tedious, as we must put datasets into a normal form and consider diferent ways of manipulating and comparing sets of DatalogMTL facts. Instead we give the main intuitions. The timepoints , ′1, ′2 considered below depend on the chosen timeline, typically (Q, ≤ ) or (Z, ≤ ). Strong or -repairs we view as a set of (indivisible) facts and delete a minimal subset to regain consistency with Π , straightforwardly adapting the notion of subset repairs Pointwise or -repairs we view as the possibly infinite set of punctual facts it represents, {(⃗)@[, ] | ∈ [1, 2], (⃗)@[1, 2] ∈ }, then minimally remove punctual facts until consistency with Π is achieved Interval-based or -repairs we consider the datasets obtained from by replacing each (⃗)@[1, 2] ∈ by a fact (⃗)@[′1, ′2] whose interval [′1, ′2] is included in [1, 2], or by nothing (we retain the option to delete a fact entirely), then compare such datasets w.r.t. how much information they retain, selecting the maximal ones consistent with Π While -repairs achieve the maximum preservation of information, an oft-desired property, they can lead to a single original fact being replaced by (possibly infinitely) many component facts, so repairs might be much larger in size than the original dataset. Both - and -repairs guarantee, by definition, that the number of facts does not increase, with -repairs striking a nice balance between preserving information and respecting the structure of the original dataset. In the same way, we can define -conflicts, -conflicts, and -conflicts of an inconsistent DatalogMTL knowledge base. Furthermore, we can use the new notions of repair to transfer existing definitions of repair-based semantics to DatalogMTL, yielding -brave, -CQA, and -intersection semantics for ∈ {, , }.
We study the formal properties of these notions. While -repairs and -conflicts possess similar properties to their atemporal analogs, - and -conflicts and repairs behave rather diferently. In particular, we show that - and -conflicts and repairs are not guaranteed to exist. Even when they do, -repairs and -conflicts might contain infinitely many facts, and some datasets might only give rise to -repairs and -conflicts of infinite size. Moreover, for both = and = , there can be infinitely many -repairs / -conflicts. One way to circumvent these negative results is to adopt the Z timeline and restrict datasets to only use bounded intervals (i.e., finite integers as endpoints).
Our second contribution is a data complexity analysis of the main computational tasks: recognizing -conflicts and -repairs, generating a single -conflict or -repair, and testing query entailment under the -brave, -CQA, and -intersection semantics. For this initial study, we focus on the two cases where -repairs are guaranteed to exist: (i) = , and (ii) bounded datasets over Z.
We recall that in DatalogMTL, consistency checking and query entailment are PSpace-complete
w.r.t. data complexity [
We briefly summarize our results concerning -repairs and -conflicts. For arbitrary DatalogMTL programs, we obtain PSpace upper bounds for all tasks (and PSpace-completeness for the decision problems) by adapting known procedures for reasoning with subset repairs and conflicts in the atemporal setting. If we consider tractable DatalogMTL fragments, then we can show that the -repair and conflict recognition are in PTime, and it is also in PTime to generate a single -repair or -conflict. We can use the PTime upper bounds on recognizing -repairs to obtain (co)NP upper bounds for query entailment under -brave, -CQA, and -intersection semantics for tractable DatalogMTL fragments. Moreover, we provide matching lower bounds for DatalognrMTL and DatalogMTL−l◇in (as well as for DatalogMTL−c◇ore in the case of the -CQA semantics), which hold even for bounded datasets and T = Z.
The hardness results for DatalognrMTL are somewhat surprising in view of the AC0 data complexity and FO<-rewritability of query entailment in DatalognrMTL, as a result from [22] shows how to transfer FO-rewritability results from classical to brave and intersection semantics. However, the latter result relies upon the fact that in the setting of atemporal ontologies, the existence of a rewriting guarantees a data-independent bound on the size of minimal inconsistent subsets and minimal query-entailing subsets. This property fails to hold in DatalognrMTL.
In DatalogMTL−c◇ore, by contrast, [
Let us also briefly summarize the preliminary results we obtained for bounded-interval datasets over Z. For general DatalogMTL programs, we obtain PSpace upper bounds for all tasks concerning -repairs and -conflicts. We further show that when we consider tractable fragments, one can tractably recognize or generate an -conflict, using binary search to identify optimal endpoints. The situation for pointwise notions is starkly diferent as even in this restricted setting, a single -conflict or -repair may be exponentially large.
We see many relevant avenues for future work. First, there remain several open questions regarding the complexity of reasoning with - and -repairs and conflicts in the bounded-interval Z setting. We are most interested in trying to extend our tractability results for -repair-based semantics to -repairs and are reasonably optimistic that this can be done (but at the cost of significantly more technical constructions). A nice theoretical question is to consider the decidability of - and -repair / conflict existence in unrestricted settings. It would also be interesting to consider DatalogMTL with negation or spatio-temporal predicates. A more practical direction is to try to devise practical SAT- or SMT-based algorithms for the identified (co) NP cases, as has been done in some atemporal settings, cf. [25]. There are also further variants of our notions that are worth exploring, such as quantitative notions of repairs, e.g. to take into account how much the endpoints have been adjusted in an -repair. Another natural direction would be to extend our study beyond DatalogMTL and explore how our proposed notions of repair and conflict can be used for reasoning with inconsistent temporal description logic knowledge bases whose assertions are annotated by time intervals. This work was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014) and the ANR PRAIRIE 3IA Institute (ANR-19-P3IA-0001).
The authors have not employed any Generative AI tools. [20] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in:
Proceedings of PODS, 1999. [21] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: Proceedings of RR, 2010. [22] M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: Proceedings of IJCAI, 2013. [23] C. Bourgaux, P. Koopmann, A. Turhan, Ontology-mediated query answering over temporal and inconsistent data, Semantic Web 10 (2019) 475–521. [24] P. A. Walega, B. Cuenca Grau, M. Kaminski, E. V. Kostylev, DatalogMTL over the integer timeline, in: Proceedings of KR, 2020. [25] M. Bienvenu, C. Bourgaux, Querying inconsistent prioritized data with ORBITS: algorithms, implementation, and experiments, in: Proceedings of KR, 2022.