Inconsistency Handling in DatalogMTL

1 Introduction

There has been significant recent interest in formalisms for reasoning over temporal data [Artale et al., 2017]. Since its introduction by Brandt et al. [2017; 2018], the DatalogMTL language, which extends Datalog [Abiteboul et al., 1995] with operators frommetric temporal logic (MTL) [Koymans, 1990], has risen to prominence. In DatalogMTL, facts are annotated by time intervals on which they are valid (e.g., R(a, b)@[1, 5]), and rules express dependencies between such facts (e.g., ⊞[0,2] Q ←-⋄{3} P states that if P holds at time t - 3, Q holds from t to t + 2). The complexity of reasoning in DatalogMTL has been extensively investigated for various fragments and extensions and for different semantics (continuous vs pointwise, rational vs integer timeline) [Brandt et al., 2018; Walega et al., 2019; Ryzhikov et al., 2019; Walega et al., 2020b; Walega et al., 2023a; Walega et al., 2024]. Moreover, there are also several implemented reasoning systems for (fragments of) DatalogMTL [Kalayci et al., 2019; Wang et al., 2022; Wang et al., 2024; Bellomarini et al., 2022; Walega et al., 2023b; Ivliev et al., 2024].

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 [Bertossi, 2019; Bienvenu, 2020]. The consistent query answering (CQA) approach considers that a (Boolean) query is true if it holds w.r.t. every repair [Arenas et al., 1999; Lembo et al., 2010]. Other natural semantics have also been proposed, such as the brave semantics, under which a query is true if it holds w.r.t. at least one repair [Bienvenu and Rosati, 2013], and the intersection semantics which evaluates queries w.r.t. the intersection of all repairs [Lembo et al., 2010]. It is also useful to consider the minimal subsets of the dataset that are inconsistent with the theory, called conflicts, to explain the inconsistency to a user or help with debugging.

It is natural to extend these notions to the temporal setting. First work in this direction was undertaken by Bourgaux et al. [2019], who considered queries with linear temporal logic (LTL) operators, an atemporal DL-Lite ontology, and a sequence of datasets stating what holds at different 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 different ways of minimally repairing an inconsistent dataset. For example, if a dataset states that P is true from 0 to 4 and Q from 2 to 6 (P@[0, 4], Q@[2, 6]), and a rule states that P and Q cannot hold at the same time (⊥ ← P ∧ Q), one can regain consistency by removing one of the two facts, adjusting their intervals, or treating intervals as their sets of points and conserving as much information as possible.

In this paper, we initiate the study of inconsistency handling in DatalogMTL. After some preliminaries, we formally introduce our framework in Section 3. We define three different notions of repair based upon deleting whole facts (srepairs), punctual facts (p-repairs), or minimally shrinking the time intervals of facts (i-repairs), which give rise to the xbrave, x-CQA, and x-intersection semantics (x ∈ {s, p, i}).

Likewise, we define notions of s-, p-, and i-conflict, which capture different ways to characterize minimal reasons for inconsistency. In Section 4, we study the properties of these notions. In particular, we show that p- and i-conflicts and repairs are not guaranteed to exist or be finite. In Section 5, we explore the computational properties of our framework. We provide a fairly comprehensive account of the data complexity of recognizing s-conflicts and s-repairs, generating a single s-conflict or s-repair, and testing query entailment under the s-brave, s-CQA, and s-intersection semantics. We obtain tight complexity results for several DatalogMTL fragments and identify tractable cases. We further provide some first complexity results for the i-and p-based notions.

Proofs of all claims are given in [Bienvenu et al., 2025].

2 Preliminaries: DatalogMTL

Intervals We consider a timeline (T,≤), (we will consider (Q, ≤), which is dense, and (Z, ≤), which is not), and call the elements of T timepoints. An interval takes the form ⟨t1, t2⟩, with t1, t2 ∈ T∪{-∞,∞}, bracket ⟨ being [ or (, and bracket ⟩ either ] or ), and denotes the set of timepoints

A punctual interval has the form [t, t] and will also be written {t}. A range ϱ is an interval with non-negative endpoints. Syntax Let P, C and V be three mutually disjoint countable sets of predicates, constants, and variables respectively. An atom is of the form P(⃗τ) where P ∈ P and ⃗τ is a tuple of terms from C ∪ V of matching arity. A literal A is an expression built according to the following grammar:

A ::= P(⃗τ) | ⊤ |⊞ϱ A |⊟ϱ A |+⋄ϱ A |-⋄ϱ A | AUϱA | ASϱA where P(⃗τ) is an atom and ϱ is a range. Intuitively, S stands for 'since', U for 'until', ⋄ for 'eventually', and ✷ for 'always', with + indicating the future and - the past. A DatalogMTL program Π is a finite set of rules of the form

B ←A1 ∧ ... ∧Ak or ⊥←A1 ∧ ... ∧Ak with k ≥ 1 where each Ai is a literal and B is a literal not mentioning any 'non-deterministic' operators +⋄ϱ, -⋄ϱ, Uϱ, and Sϱ. We call A1 ∧ ... ∧ Ak the body of the rule, and B or ⊥ its head. We assume that each rule is safe: each variable in its head occurs in its body, and this occurrence is not in a left operand of S or U. A (temporal) dataset D is a finite set of (temporal) facts of the form α@ι, with α a ground atom (i.e., α does not contain any variable) and ι a non-empty interval.

Fragments A program is propositional if all its predicates are nullary. It is core if each of its rules is either of the form ⊥ ← A1 ∧A2 or of the form B ← A. It is linear if each of its rules is either of the form ⊥ ← A1 ∧ A2 or of the form B ← A1∧...∧Ak where at most one Ai mentions some predicate that occurs in the head of some rule (intensional predicate). We denote by DatalogMTL-⋄ core (resp. DatalogMTL-⋄ lin ) the fragment where programs are core (resp. linear) and -⋄ is the only temporal operator allowed in literals. The relation ⋖ of dependence between predicates is defined by P ⋖ Q iff there is a rule with P in the head and Q in the body. A program is non-recursive if there is no predicate P such that P ⋖+ P , where ⋖+ is the transitive closure of ⋖. We denote by DatalognrMTL the fragment of non-recursive programs.

Semantics An interpretation M specifies for each ground atom α and timepoint t ∈ T whether α is true at t. If α is true at t in M, we write M, t |= α and say that M satisfies α at t. The satisfaction of a ground literal by M at t is then defined inductively as follows.

An interpretation M is a model of a rule H ← A1 ∧ ... ∧Ak if for every grounding assignment ν : V ↦→ C, for every t ∈ T, M, t |= ν(H) whenever M, t |= ν(Ai) for 1 ≤ i ≤ k, where ν(B) denotes the ground literal obtained by replacing each x ∈ V by ν(x) in B. M is a model of a program Π if it is a model of all rules in Π. It is a model of a fact α@ι if M, t |= α for every t ∈ ι, and it is a model of a (possibly infinite) set of facts B if it is a model of all facts in B. A program Π is consistent if it has a model. A set of facts B is Π-consistent if there exists a model M of both Π and B, written M |= (B, Π). A program Π and set of facts B entail a fact α@ι, written (B,Π) |= α@ι, if every model of both Π and B is also a model of α@ι. Finally, we write B |= α@ι if (B, ∅) |= α@ι and Π |= α@ι if (∅, Π) |= α@ι.

Queries A DatalogMTL query is a pair (Π, q(⃗v, r)) of a program Π and an expression q(⃗v, r) of the form Q(⃗τ)@r, where Q ∈ P, ⃗v = (v1, . . . , vn) is a tuple of variables, ⃗τ is a tuple of terms from C ∪ ⃗v, and r is an interval variable. We may simply use q(⃗v, r) as a query when the program has been specified. A certain answer to (Π, q(⃗v, r)) over a (possibly infinite) set of facts B is a pair (⃗c, ι) such that ⃗c = (c1, . . . , cn) is a tuple of constants, ι is an interval and, for every t ∈ ι and every model M of Π and B, we have M, t |= Q(⃗τ)[⃗v←⃗c], where Q(⃗τ)[⃗v←⃗c] is obtained from Q(⃗τ) by replacing each vi ∈ ⃗v by the corresponding ci ∈ ⃗c.

We will illustrate the notions we introduce on a running example about a blood transfusion scenario.

Example 1. In our scenario, we wish to query the medical records of blood transfusion recipients to detect patients who exhibited symptoms or risk factors of transfusion-related adverse reactions. For example, if a patient presents a fever during the transfusion or in the next four hours, while having a normal temperature for the past 24 hours, one can suspect a febrile non-haemolytic transfusion reaction (potential fnhtr). This is represented by the following rule, where, intuitively, x represents a patient and y a blood pouch:

Another rule detects more generally relevant fever episodes:

A patient cannot have a fever and no fever at the same time:

We may also wish to identify patients who once produced antiD antibodies, as they are at risk for adverse reactions to some blood types. This is represented as follows.

The following dataset provides information about a patient a who received transfusion from a blood pouch b, assuming that time 0 is the time they entered the hospital.

Let Π consist of the DatalogMTL rules above. One can check that D is Π-consistent, (a, {29}) is a certain answer to the query PotFnhtr(v)@r, (a, [29, 34]) is a certain answer to FevEp(v)@r, and (a, [-90,∞)) to AntiDRisk(v)@r.

3 Repairs and Conflicts on Time Intervals

In this section, we first define three kinds of repair and conflict for temporal datasets, then extend inconsistency-tolerant semantics to this context. Before delving into the formal definitions, we illustrate the impact of dealing with time intervals.

Example 2. Let Π be the program from Example 1 and

D is Π-inconsistent because in D, the patient a has both fever and no fever at t ∈ [14, 18] ∪ [29, 32]. To repair the data by removing facts from D, there are only two minimal possibilities: either remove NoFever(a)@[0, 32], or remove both Fever(a)@[14, 18] and Fever(a)@[29, 34]. This may be considered too drastic, since, e.g., the Fever facts do not contradict that the patient had no fever during [0, 14) or (18, 29).

Hence, it may seem preferable to consider each timepoint independently, so that a repair may contain, e.g., the two Fever facts as well as NoFever(a)@[0, 14) and NoFever(a)@(18, 29). However, with this approach, if T = Q, there are infinitely many possibilities to repair the dataset, and the number of facts in a repair may be infinite. For example, an option to repair the Fever and NoFever facts is:

{NoFever(a)@[0, 29), Fever(a)@[30, 34],

An intermediate approach consists in only modifying the endpoints of intervals, in order to keep more information than with fact deletion without splitting one fact into many. Again we may obtain infinitely many possibilities, e.g., the Fever and NoFever facts can be repaired by NoFever(a)@[0, t) and Fever(a)@[t, 34] for t ∈ [29, 32].

Manipulating sets of temporal facts To formalize conflicts and repairs of temporal datasets, we consider three ways of comparing (possibly infinite) sets of facts w.r.t. inclusion:

Definition 1 (Pointwise inclusion, subset comparison). We say that a fact α@ι is pointwise included in a set of facts B if for every t ∈ ι, there is α@ι′ ∈ B with t ∈ ι′ , i.e., if B |= α@ι. Given sets of facts B and B′ , we say that B′ is

• a pointwise subset of B, denotedB′ ⊑p B, if every α@ι ∈ B′ is pointwise included in B;
• an interval-based subset of B, denoted B′ ⊑i B, if B′ ⊑p B and for every α@ι ∈ B, there is at most one α@ι′ ∈ B′ such that ι′ ⊆ ι;
• a strong subset of B, writtenB′ ⊑s B, if B′ ⊑i B andB′ ⊆ B. We write B′ ⊏p B to indicate that B′ ⊑p B and B ̸⊑p B′ . For x ∈ {i, s}, we write B′ ⊏x B if B′ ⊑x B and B′ ⊏p B.

We also need to intersect (possibly infinite) sets of facts:

Definition 2 (Pointwise intersection). The pointwise intersection of a family (Bi)i∈I of sets of facts is �i∈I Bi = {α@{t} | Bi |= α@{t} for each i ∈ I}. The pointwise intersection of a fact α@ι and a set of facts B is {α@ι} ⊓ B.

Normal form A (possibly infinite) set of facts B is in normal form if for every pair of facts α@ι and α@ι′ over the same ground atom, if α@ι and α@ι′ are in B, then ι ∪ ι′ is not an interval.

Lemma 1. If B is in normal form, then (1) B′ ⊑s B iff B′ ⊆ B, and (2) B′ ⊑i B implies that the cardinality of B′ is bounded by that of B.

To see why normal form is necessary, consider (1) B = {P@[0, 4], P@[1, 2]}, which is such that B ̸⊑i B, so that B ̸⊑s B, and (2) B = {P@[0, 4], P@[3, 7]}, which is such that {P@[0, 1], P@[2, 5], P@[6, 7]} ⊑i B.

For every dataset D, there exists a dataset D′ in normal form such that for every t ∈ T, for every ground atom α, D |= α@{t} iff D′ |= α@{t}. Moreover, such D′ can be computed in polynomial time w.r.t. the size of D by merging every α@ι1 and α@ι2 such that ι1 ∪ι2 is an interval into α@ι with ι = ι1 ∪ ι2. In the rest of this paper, we assume that all datasets are in normal form and all programs are consistent.

Conflicts, repairs, and inconsistency-tolerant semantics We are now ready to formally state the definitions of conflicts and repairs of a temporal dataset w.r.t. a DatalogMTL program. We start with the notion of conflict, which is crucial to explain inconsistency.

Definition 3 (Conflicts). Let Π be a DatalogMTL program and D be a dataset. Given x ∈ {p, i, s}, a set of facts C is an x-conflict of D w.r.t. Π if C is in normal form, C ⊑x D, C is Π-inconsistent, and there is no Π-inconsistent C ′ ⊏x C. We denote by xConf (D, Π) the set of all x-conflicts of D w.r.t. Π.

Example 3. Consider Π and D from Example 2. The s-conflicts are {NoFever(a)@[0, 32], Fever(a)@[14, 18]} and {NoFever(a)@[0, 32], Fever(a)@[29, 34]}, while the pconflicts and i-conflicts are of the form {NoFever(a)@{t}, Fever(a)@{t}} with t ∈ [14, 18] ∪ [29, 32].

We define repairs in a similar manner.

Definition 4 (Repairs). Let Πbe aDatalogMTL programand D be a dataset. Given x ∈ {p, i, s}, a set of facts R is an x-repair of D w.r.t. Π if R is in normal form, R⊑x D, R is Π-consistent, and there is no Π-consistent R′ such that R⊏x R′ ⊑x D. We denote by xRep(D,Π) the set of all xrepairs of D w.r.t. Π.

The requirement that x-repairs are in normal form ensures that when D is Π-consistent, xRep(D, Π) = {D}.

Example 4. Π and D from Example 2 have two s-repairs:

Every p-repair R is such that J ⊑p R with

and for every t ∈ [14, 18] ∪ [29, 32], either Fever(a)@{t} or NoFever(a)@{t} is pointwise included in R.

Finally, every i-repair R is such that I ⊆ R and contains:

• either two facts NoFever(a)@[0, t⟩, Fever(a)@⟨t, 34], where ⟩, ⟨ are either ], ( or ), [ and t ∈ [29, 32];
• or three facts NoFever(a)@[0, t⟩, Fever(a)@⟨t, 18], and Fever(a)@[29, 34], where t ∈ [14, 18],
• ⟩, ⟨ are either ], ( or ), [ and
• if t = 18, then ⟩, ⟨ are ), [;
• or three facts Fever(a)@[14, t1⟩, NoFever(a)@⟨t1, t2⟩′ , Fever(a)@⟨′ t2, 34], where t1 ∈ [14, 18], t2 ∈ [29, 32],
• ⟩, ⟨ and ⟩′ , ⟨′ are either ], ( or ), [,
• if t1 = 14, then ⟩, ⟨ are ], (.

We can now extend the definitions of the brave, CQA and intersection semantics to use different kinds of repairs.

Definition 5. Consider a DatalogMTL query (Π, q(⃗v, r)), dataset D, tuple ⃗c of constants from D with |⃗c| = |⃗v|, and interval ι. Given x ∈ {p, i, s} such that xRep(D, Π) ̸= ∅, we say that ⃗c is an answer to (Π, q(⃗v, r)) under

• x-brave semantics, written (D,Π) |=xbrave q(⃗c, ι), if (R, Π) |= q(⃗c, ι) for some R ∈ xRep(D, Π);
• x-CQA semantics, written (D,Π) |=xCQA q(⃗c, ι), if (R, Π) |= q(⃗c, ι) for every R ∈ xRep(D, Π);
• x-intersection semantics, written (D,Π) |=x∩ q(⃗c, ι), if (I, Π) |= q(⃗c, ι) where I = �R∈xRep(D,Π) R.

Proposition 1. For every query (Π, q(⃗v, r)), dataset D, tuple of constants ⃗c, and interval ι, (D,Π) |=x∩ q(⃗c, ι) implies (D,Π) |=xCQA q(⃗c, ι), which implies (D,Π) |=xbrave q(⃗c, ι). None of the converse implications holds.

Example 5. Consider Π and D from Example 2. By examining the s-repairs given in Example 4, we can check that:

• (D,Π) |=s∩ AntiDRisk(a)@[-90,∞),
• (D,Π) ̸|=sbrave FevEp(a)@{t} for every t ∈ T,
• (D,Π) ̸|=sbrave PotFnhtr(a)@{t} for every t ∈ T.

With the p-repairs (Example 4), we obtain that:

• (D,Π) |=p∩ AntiDRisk(a)@[-90,∞),
• (D,Π) |=p∩ FevEp(a)@(32, 34],
• (D,Π) |=pbrave PotFnhtr(a)@{t} for all t ∈ [29, 30],
• (D,Π) ̸|=pCQA PotFnhtr(a)@{t} for every t ∈ T.

From the form of the i-repairs (Example 4), we obtain that:

• (D,Π) |=i∩ AntiDRisk(a)@[-90,∞),
• (D,Π) |=ibrave FevEp(a)@[29, 34],
• (D,Π) ̸|=iCQA FevEp(a)@{t} for each t ∈ T,
• (D,Π) |=ibrave PotFnhtr(a)@{t} for all t ∈ [29, 30],
• (D,Π) ̸|=iCQA PotFnhtr(a)@{t} for each t ∈ T.

4 Properties of the Framework

We study properties of x-conflicts, x-repairs, and semantics based upon them. The results hold for T = Q and T = Z.

4.1 Properties of Repairs and Conflicts

We will consider in particular the following properties, which are well known in the case of atemporal knowledge bases.

Definition 6. We say that Pi holds if it holds for every dataset D (in normal form) and (consistent) program Π.

P1: xRep(D,Π) ̸= ∅.

P2: D is Π-inconsistent iff xConf (D,Π) ̸= ∅.

P3: xRep(D,Π) and xConf (D,Π) are finite.

P4: Every B ∈ xRep(D, Π) ∪ xConf (D, Π) is finite.

• P5: For every fact α@ι pointwise included in D, α@ι is pointwise included in every x-repair of D w.r.t. Π iff α@ι has an empty pointwise intersection with every x-conflict of D w.r.t. Π.

The notions based on ⊑s have all these properties, while those based on ⊑p do not have any, and those based on ⊑i only one (i-repairs and i-conflicts are finite by Lemma 1).

Proposition 2. Properties P1-P5 hold for x = s.

Proposition 3. None of the properties P1-P5 hold for x = p. For x = i, P4 holds but properties P1-P3 and P5 do not.

In what follows, we will provide the counterexamples used to prove Proposition 3, as well as additional examples that illustrate the properties of x-repairs and x-conflicts.

Existence of p- and i-Repairs and Conflicts

A major difference between repairs and conflicts based on ⊑s and those based on ⊑p or ⊑i is that the latter need not exist.

Example 6. Consider the following dataset and program.

There is no p- or i-repair and no p- or i-conflict of D w.r.t. Π. For x ∈ {p, i}, every Π-inconsistent C ⊑x D in normal form is of the form {P@⟨t,∞)}. Since C ′ = {P@(t+1,∞)} is Π-inconsistent and C ′ ⊏x C, then C is not an x-conflict.

Every R⊑i D is either empty (hence not an i-repair since, e.g., {P@{1}} is Π-consistent) or of the form {P@⟨t1, t2⟩} with ⟨t1, t2⟩ ̸= ∅. If t2 = ∞, R is Π-inconsistent. Otherwise, R′ = {P@⟨t1, t2 +1⟩} is Π-consistent and R⊏i R′ ⊑i D. In both cases, R is not an i-repair.

For every R⊑p D in normal form, if there is only one t ∈ (0,∞) such that R ̸|= P@{t}, then R contains P@(t,∞) so R is Π-inconsistent. Hence, for every Π-consistent R⊑p D, there exist t1, t2 ∈ (0,∞) such that t1 < t2 and R ̸|= P@{t1}, R ̸|= P@{t2}. However, R′ = R ∪ {P@{t1}} is then Π-consistent and R⊏p R′ ⊑p D so R is not a p-repair.

Example 7 shows that there is no relationship between the existence of x-conflicts and the existence of x-repairs.

Example 7. Let Dc = D ∪ {R@{0}} and Πc = Π∪ {⊥← R} with D and Π from Example 6. We can show as in Example 6 that for x ∈ {p, i}, there is no x-repair of Dc w.r.t. Πc. However, {R@{0}} is an x-conflict of Dc w.r.t. Πc. Now, let

For x ∈ {p, i}, there is no x-conflict of Dr w.r.t. Πr. Indeed, every Πr-inconsistent C ⊑p D has to be such that C |= P@(t,∞) for some t > 0 and none of such C is minimal w.r.t. ⊑x . Yet, {P@[0,∞)} is an x-repair of Dr w.r.t. Πr.

The next examples show there is no relationship between the existence of p-repairs and the existence of i-repairs, nor between existence of p-conflicts and existence of i-conflicts.

Example 8. The following Di and Πi have no p-repair (cf. Example 6) but {P@(-2, 0), Q@{0}} is an i-repair.

In the other direction, let Dp = {P@(-∞, ∞), Q@{0}} and

One can check that {Q@{0}, P@(-10, 0), P@(0, 10)} is a p-repair, but one can show that there is no i-repair.

Example 9. Di = {P@[0,∞),Q@{0}} is an i-conflict of itself w.r.t. Πi = {⊥← P ∧Q∧ +⋄(0,∞)⊞(0,∞) P}. However, there is no p-conflict of Di w.r.t. Πi. Indeed, every Πi-inconsistent dataset C ⊑p Di in normal form has the form {Q@{0}, P@{0}, P@⟨t,∞)}, and {Q@{0}, P@{0}, P@⟨t + 1, ∞)} is also Πi-inconsistent.

In the other direction, let Dp = {P@[0,∞), Q@{0}} and

One can easily check that {Q@{0}, P@{k} | k ∈ N} is a p-conflict, but one can show that there is no i-conflict.

Size and Number of p- and i-Repairs and Conflicts

It follows from Lemma 1 that the i-repairs and i-conflicts of a dataset D w.r.t. a program Π contain at most as many facts as D, hence are finite. In contrast, we have seen in Example 2 that a p-repair may be infinite. Example 10 shows that some datasets have only infinite p-repairs w.r.t. some programs, and Example 11 shows a similar result for p-conflicts.

Example 10. Consider the following dataset and program.

There exist p-repairs of D w.r.t. Π, such as {P@(2k, 2k+2) | k ∈ N}, but one can show that they are all infinite.

Example 11. Consider the following dataset and program.

There are p-conflicts of D w.r.t. Π, such as {Q@{0}, P@{2k} | k ∈ N}, but one can show that they are all infinite.

Moreover, for both x = i and x = p, there can be infinitely many x-repairs / x-conflicts:

Example 12. The following D and Π have infinitely many pand i- repairs and conflicts even if the timeline is (Z,≤):

Indeed, for every t ∈ [0, ∞), {P@{t}, Q@{t}} is a p- and an i-conflict, and {P@[0, t), Q@[t,∞)} is a p- and an i-repair.

Absence of Link Between p/i- Repairs and Conflicts

Example 13 shows that a fact may be pointwise included in all p-, or i-, repairs while it is also pointwise included in a p-, or i-, conflict, respectively, and, symmetrically, that a fact may have an empty pointwise intersection with all p-, or i-, conflicts but also with some p-, or i-, repair.

Example 13. Consider Di and Πi defined in Example 8. There is only one i-repair, {P@(-2, 0),Q@{0}}, but Q@{0} belongs to the i-conflict {P@{0},Q@{0}}. Symmetrically, P@(0,∞) has an empty intersection with every i-conflict but also with every i-repair. Indeed, {P@(0,∞)} is Πi-inconsistent but is not minimal w.r.t. ⊑i .

For the p- case, we first consider again Di but extend Πi with ⊥ ← Q∧ +⋄[0,∞) P . Now {P@(-2, 0), Q@{0}} is the only p-repair but {P@{0}, Q@{0}} is a p-conflict so Q@{0} is in all p-repairs and in some p-conflict. For the other direction, consider D = {P@[0, ∞), Q@{0}, R@{0}} and

The only p-conflict of D w.r.t. Π is {R@{0}} (cf. Example 9) so Q@{0} has an empty intersection with every p-conflict. Yet, {P@[0,∞)} is a p-repair that does not contain Q@{0}.

Case of Bounded-Interval Datasets over Z

We have seen that p- and i-repairs and conflicts need not exist, and even when they do, they may be infinite in size and/or number. Moreover, this holds not only for the dense timeline (Q,≤), but also for (Z,≤). We observe, however, that the negative results for Z crucially rely upon using ∞ or -∞ as endpoints. This leads us to explore what happens when we adopt T = Z but restrict datasets to only use bounded intervals (i.e., finite integers as endpoints).

The following result summarizes the properties of repairs and conflicts in this setting, showing in particular that restricting to bounded-interval datasets suffices to ensure existence and finiteness of p- and i-repairs and conflicts:

Proposition 4. When T = Z and datasets D are restricted to only use bounded intervals, P1-P5 hold for x = p, P1-P4 hold for x = i, and P5 does not hold for x = i.

4.2 Comparing the Different Semantics

The remaining examples show the following proposition.

Proposition 5. For every Sem ∈ {brave, CQA, ∩} and x ̸= y ∈ {p, i, s}, there exist D and Π such that D has x- and yrepairs w.r.t. Π, (D, Π) |=ySem q(⃗c, ι) and (D, Π) ̸|=xSem q(⃗c, ι).

Example 14 shows the case y = p and x ∈ {i, s}.

Example 14. Consider our running example and recall from Example 5 that (D,Π) |=p∩ FevEp(a)@{34} (hence (D,Π) |=pCQA FevEp(a)@{34}) while (D,Π) ̸|=xCQA FevEp(a)@{34} (hence (D,Π) ̸|=x∩ FevEp(a)@{34}) for x ∈ {i, s}. Moreover, if we consider Π′ that extends Π with

The case y = s and x ∈ {p, i} is shown by Example 15 for Sem ∈ {∩, CQA} and Example 16 for Sem = brave.

It is easy to check that {Q@{5}} is the only s-repair so that (D,Π) |=s∩ Q@{5}. However, {P@(0, 10]} is a p- and irepair so for x ∈ {p, i}, (D, Π) ̸|=xCQA Q@{5}.

Example 16. Consider Dr and Πr from Example 7.

Since {Q@{0}} is an s-repair, (Dr,Πr) |=sbrave Q@{0}. However, for x ∈ {p, i}, one can show that the only x-repair is {P@[0,∞)}. Hence (Dr, Πr) ̸|=xbrave Q@{0}.

Example 17 illustrates the case y = i and x = s for Sem ∈ {∩, CQA} and Example 18 shows this case for Sem = brave. Example 17. In Example 16, the only i-repair is {P@[0,∞)} so (Dr,Πr) |=i∩ P@[0,∞). However, {Q@{0}} is an s-repair so (Dr, Πr) ̸|=sCQA P@[0,∞).

Example 18. Consider our running example and recall from Example 5 that (D,Π) |=ibrave FevEp(a)@{29} while (D,Π) ̸|=sbrave FevEp(a)@{29}.

Example 19 illustrates the case y = i and x = p for Sem ∈ {∩, CQA} and Example 20 shows this case for Sem = brave. Example 19. Let D = {T@{0}, P@[0, 4],Q@[0, 4]} and

The i-repairs are of the form {T@{0}, P@[0, t⟩, Q@⟨t, 4]} or {T@{0},Q@[0, t⟩, P@⟨t, 4]} so (D,Π) |=i∩ T@{0}. However, R = {P@[0, 1], Q@(1, 3), P@[3, 4]} is a p-repair (note that (R, Π) |= R@{0}, so R ∪ {T@{0}} is Π-inconsistent). Hence (D,Π) ̸|=pCQA T@{0}.

Example 20. Consider D = {P@[0,∞),Q@{5}} and

Since {P@[0, 5),Q@{5}} is an i-repair, (D,Π) |=ibrave Q@{5}. However, one can show that the only p-repair is {P@[0,∞)}. Hence (D,Π) ̸|=pbrave Q@{5}.

5 Data Complexity Analysis

We explore the computational properties of our inconsistency handling framework. Specifically, we analyze the data complexity of recognizing x-conflicts and x-repairs, generating a single x-conflict or x-repair, and testing query entailment under the x-brave, x-CQA, and x-intersection semantics. For this initial study, we focus on cases where x-repairs are guaranteed to exist: (i) x = s, and (ii) bounded datasets over Z.

We recall that in DatalogMTL, consistency checking and query entailment are PSPACE-complete w.r.t. data complexity [Walega et al., 2019], and PSPACE-completeness holds for many fragments (such as core and linear) [Walega et al., 2020b] as well as for DatalogMTL over Z [Walega et al., 2020a]. We also consider some tractable fragments for which these tasks can be performed in PTIME w.r.t. data complexity: DatalognrMTL, DatalogMTL-⋄ core, and DatalogMTL-⋄ lin (over Q or Z) and propositional DatalogMTL over Z [Brandt et al., 2018; Walega et al., 2020b; Walega et al., 2020a].

All results stated in this section are w.r.t. data complexity, i.e. the input size is the size of D. We assume a binary encoding of numbers, with rationals given as pairs of integers.

5.1 Results for s-Repairs and s-Conflicts

We can obtain PSPACE upper bounds for all tasks by adapting known procedures for reasoning with subset repairs and conflicts in the atemporal setting, cf. [Bienvenu and Bourgaux, 2016]. Specifically, an s-repair or s-conflict can be generated by a greedy approach (add / delete facts one by one while preserving (in)consistency), and query entailment under the three semantics can be done via a 'guess and check' approach.

Proposition 6. For arbitrary DatalogMTL programs Π, (i) the size of B ∈ sConf (D, Π) ∪ sRep(D, Π) is polynomially bounded in the size of D, (ii) it can be decided in PSPACE whether B ∈ sConf (D,Π) or B ∈ sRep(D,Π), and (iii) a single s-conflict (resp. s-repair) can be generated in PSPACE. Moreover, for Sem ∈ {brave, CQA, ∩}, query entailment under s-Sem is PSPACE-complete.

If we consider tractable DatalogMTL fragments, we obtain better bounds for the recognition and generation tasks:

Proposition 7. For tractable DatalogMTL fragments, the tasks of testing whether B ∈ sConf (D,Π) (resp. B ∈ sRep(D,Π)) and generating a single s-conflict (resp. srepair) can be done in PTIME.

We can use the PTIME upper bounds on recognizing srepairs to obtain (co)NP upper bounds for query entailment in tractable DatalogMTL fragments. Moreover, for specific fragments, we can show these bounds are tight.

Proposition 8. For tractable DatalogMTL fragments: query entailment 1 under s-brave (resp. s-CQA, s-intersection) semantics is in NP (resp. coNP). Matching lower bounds hold in DatalognrMTL and DatalogMTL-⋄ lin (and in DatalogMTL-⋄ core in the case of s-CQA). The lower bounds hold even for bounded datasets and T = Z.

Proof sketch. To illustrate, we provide the reduction from SAT used to show NP-hardness of s-brave semantics in DatalognrMTL. Given a CNF φ = c1 ∧ ... ∧ cm over variables v1, ..., vn, consider the DatalognrMTL program and dataset:

The hardness results for DatalognrMTL are somewhat surprising in view of the AC0 data complexity and FO<- rewritability of query entailment in DatalognrMTL [Brandt et al., 2018], as a result from [Bienvenu and Rosati, 2013] 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 considered setting of atemporal ontologies, the existence of a rewriting guarantees a data-independent bound on the size of minimal inconsistent subsets and minimal consistent query-entailing subsets. As the preceding reduction shows, such a property fails to hold in DatalognrMTL (observe that the minimal consistent queryentailing subsets in D′ have size m+ 1).

In DatalogMTL-⋄ core, by contrast, Walega et al. [2020b; 2020a] have shown that every minimal Π-inconsistent subset contains at most two facts, and query entailment can be traced back to a single fact. This is the key to our next result:

Proposition 9. DatalogMTL-⋄ core query entailment1 under sbrave and s-intersection semantics is in PTIME.

For propositional DatalogMTL, we even get tractability for s-CQA semantics - notable in view of the notorious intractability of CQA semantics even in restricted atemporal settings. The proof relies upon rather intricate automata constructions, which build upon and significantly extend those given in [Walega et al., 2020a] for consistency checking.

Proposition 10. When T = Z, propositional DatalogMTL query entailment under s-brave, s-CQA, and s-intersection semantics is in PTIME (more precisely, NC1-complete).

5.2 Results for Bounded-Interval Datasets over Z

We start by considering interval-based notions and observe that even if the binary encoding of endpoint integers leads to exponentially many choices for which sub-interval to retain for a given input fact, i-conflicts and i-repairs are of polynomial size and can be effectively recognized and generated. This allows us to establish the same general upper bounds for x = i as we obtained for x = s.

Proposition 11. When T = Z and only bounded-interval datasets are considered, the results stated in Proposition 6 for the case x = s hold in the case x = i.

1 Restricted to queries with punctual intervals for DatalogMTL-⋄lin and DatalogMTL-⋄core: Walega et al. [2020b] give results for consistency checking, and reductions from query entailment to consistency checking for non-punctual queries use constructs not available in these two fragments, cf. discussion in [Walega et al., 2020b].

We further show that when we consider tractable fragments, one can tractably recognize or generate an i-conflict, using binary search to identify optimal endpoints.

Proposition 12. For tractable DatalogMTL fragments: when T = Z and only bounded-interval datasets are considered, it can be decided in PTIME whether B ∈ iConf (D,Π) and a single i-conflict can be generated in PTIME.

The argument does not apply to i-repairs, and we leave open the precise complexity of i-repair recognition in this case (we only get a coNP upper bound). However, we can still obtain a tight complexity result for i-brave semantics since we do not need to get a complete i-repair in this case.

Proposition 13. For tractable DatalogMTL fragments: when T = Z and only bounded-interval datasets are considered, query entailment1 under i-brave (resp. i-CQA, iintersection) is in NP (resp. in Πp2 ). Lower NP (resp. coNP) bounds hold for DatalognrMTL and DatalogMTL-⋄ lin (and for DatalogMTL-⋄ core in the case of i-CQA semantics).

The situation for pointwise notions is starkly different:

Proposition 14. When T = Z and only bounded-interval datasets are considered, there exist D and Π such that every B ∈ pConf (D,Π) (resp. B ∈ pRep(D,Π)) is exponentially large w.r.t. the size of D.

We thus only obtain EXPSPACE complexity upper bounds. Proposition 15. When T = Z and only bounded-interval datasets are considered, all tasks considered in Proposition 6 for x = s can be done in EXPSPACE in the case x = p.

6 Conclusion and FutureWork

This paper provides a first study of inconsistency handling in DatalogMTL, a prominent formalism for reasoning on temporal data. Due to facts having associated time intervals, there are different natural ways to define conflicts and repairs. Our results show that these alternative notions can differ significantly with regards to basic properties (existence, finiteness, or size). For s-conflicts and s-repairs, we provided a detailed picture of the data complexity landscape, with tight complexity results for several DatalogMTL fragments. Notably, we proved that query entailment in propositional DatalogMTL over Z is tractable for all three s-repair-based semantics.

We see many relevant avenues for future work. First, there remain several open questions regarding the complexity of reasoning with i- and p-repairs and conflicts in the boundedinterval Z setting. We are most interested in trying to extend our tractability results for s-repair-based semantics to irepairs and are reasonably optimistic that this can be done (with significantly more involved constructions). It would also be interesting to consider DatalogMTL with negation or spatio-temporal predicates. A nice theoretical question is to consider the decidability of i- and p-repair / conflict existence in unrestricted settings. 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. [Bienvenu and Bourgaux, 2022]. There are also further variants of our notions that are worth exploring, such as quantitative notions of x-repairs, e.g. to take into account how much the endpoints have been adjusted in an i-repair.

Acknowledgments

This work was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014) and the ANR PRAIRIE 3IA Institute (ANR-19-P3IA-0001).