Ontology-mediated query answering over temporal and inconsistent data

Abstract

Stream-based reasoning systems process data stemming from different sources that are received over time. In this kind of applications, reasoning needs to cope with the temporal dimension and should be resilient against inconsistencies in the data. Motivated by such settings, this paper addresses the problem of handling inconsistent data in a temporal version of ontology-mediated query answering. We consider a recently proposed temporal query language that combines conjunctive queries with operators of propositional linear temporal logic (LTL), and consider these under three inconsistency-tolerant semantics that have been introduced for querying inconsistent description logic knowledge bases. We investigate their complexity for temporal ${EL}_{⊥}$ and ${DL-Lite}_{R}$ knowledge bases. In particular, we consider two different cases, depending on the presence of negations in the query. Furthermore, we complete the complexity picture for the consistent case. We also provide two approaches toward practical algorithms for inconsistency-tolerant temporal query answering.

Keywords

Temporal query answering inconsistency-tolerant reasoning description logics computational complexity

1. Introduction

For applications that rely on sensor data, such as context-aware applications, ontologies can enrich and abstract the (numerical) stream data by means of background knowledge. This richer view on the data often results in more query results than over the data alone. Since the collected data usually provides an incomplete description of the observed system, the closed world assumption employed by database systems, where facts not present are assumed to be false, is not appropriate. Most applications that rely on sensor streams observe some kind of running system over time. In order to be able to react to the behaviour of the observed system, they need to employ some representation of temporal information and a query mechanism that can reference this temporal information. If the sources of the collected data are not reliable, as it might be in case of faulty sensors, the internal representation of the observations may contain inconsistencies. In such cases, query mechanisms that rely on logical reasoning are effectively useless, as everything would follow from an inconsistent knowledge base. As a counter measure to this effect, inconsistency-tolerant semantics for answering ontology-mediated queries have been devised. In this paper, we investigate combinations of inconsistency-tolerant and temporal query answering w.r.t. ontologies. This setting is fairly abstract and deliberately neglects implementation details as it provides foundations on the combination of three aspects vital to most stream reasoning applications. First, stream reasoning requires background knowledge either on the streams used or on the context in which the information provided by the streams is to be handled. Both kinds of background knowledge can be represented by ontologies and be exploited by ontology reasoning systems. Second, stream reasoning inherently has to cope with the temporal dimension. This dimension is given by the sequence of observations that individual items in the streams provide. Thus, traditional reasoning services that are oblivious of the temporal dimension are hardly of use to stream reasoning applications. Naive combinations of such atemporal reasoning services can compute some forms of temporal consequences, but these combinations need not be complete and thus could miss consequences. To stream reasoning applications relying on such ad-hoc systems, it is not discernible when the naive reasoner does or does not provide a reliable answer. Third, and most importantly, the different streams or data sources need not be free of errors due to the methods by which the data is gathered or provided to the system. Moreover, an automatic combination of open stream sources to which a stream reasoning system can subscribe simply cannot guarantee a consistent combination of such sources. Thus, in general, the combination of the data used by a stream reasoning system can simply contain contradictory information. The combination of these three aspects is so far not investigated in the literature. This is why our setting abstracts from many application specific details and variations of stream reasoning systems, in order to concentrate on the combination of the three fundamental conditions inherent to most such systems. Our goal is to provide an initial orientation for selecting between the many design choices by which each of these factors can be addressed in a stream reasoning system, such as expressivity of the ontology and query language, treatment of temporal information, and different inconsistency-tolerant semantics. To this end we map out the landscape of the computational complexity for many combinations of the three design factors for stream reasoning systems in this paper. In preparation for this, we examine the three design aspects in more detail.

In many stream reasoning systems, the collected data is transformed into an abstract logical representation, and situation recognition is performed by some kind of logical inference over the abstract logical representation. There are stream reasoning approaches based on rules, such as answer set programming [8,10,31], (datalog) rules and approaches based on ontology languages [6,19,24,47]. The ontology-based approaches mostly employ the framework of ontology-mediated queries, where forms of conjunctive queries are answered over data that is enriched by an ontology, to perform situation recognition. The ontology languages that are investigated for situation recognition are usually those where reasoning is of lower computational complexity in order to obtain systems with low execution times.

In this paper, we investigate the lightweight description logics (DLs) ${EL}_{⊥}$ and ${DL-Lite}_{R}$ , for which answering conjunctive queries is tractable (respectively in P and ${AC}^{0}$ w.r.t. the size of the data). The low complexity for query answering in ${DL-Lite}_{R}$ made it the choice for the OWL 2 QL profile [45] in the latest version of OWL [46], the W3C-standardized ontology language for the Semantic Web. For similar reasons, the logic $EL$ was picked as the core of the OWL 2 EL profile. Both ${DL-Lite}_{R}$ and ${EL}_{⊥}$ admit to use database systems to answer conjunctive queries and are thus good candidates for implementing ontology-based stream reasoning. In ${DL-Lite}_{R}$ , the query can be rewritten using the information from the ontology such that the resulting query can be evaluated directly on the data, i.e. stored in a database [26]. For query answering in $EL$ , there are several approaches. In the combined approach [41] the data is augmented in a query-independent way to build a canonical model by adding information form the terminology. The query is then evaluated over this model and unsound answers are filtered out. Alternatively, a translation to datalog variants can be used [50] for query answering in $EL$ dialects.

In stream reasoning approaches in general, the temporal information is often represented by associating data with the time point at which it was collected. Regarding the language in which queries can be formulated, many variations that capture the temporal aspect have been studied in recent research [8–10,47]. Window-based approaches admit to concentrate on recent continuous substreams when answering queries over the data, and are the most prominent in implemented systems [8,10,47]. Ontology-based approaches mostly cover classical temporal logics such as linear temporal logic (LTL) [48] (see [2,4,6,18,34]) or metric variants of temporal logics [5,23] to enrich the query language. For a recent overview on temporal ontology-mediated querying see [3,5]. Note that window-based and ontology-based approaches can be combined. For example, it might often be convenient to first extract a time window of interest and then apply ontology-based query answering to its content. Or alternatively, it is possible to refer to subsequences of the time line using LTL operators, though with a semantics that differs from a standard window operator (see Section 2 for an example).

Ontology-based approaches for stream reasoning often admit the use of temporal operators only in the query language and use classical ontologies without any temporal operators together with sequences of datasets. Each dataset in such a sequence contains data collected at the same time point. The ontology together with the sequence of datasets constitute the temporal knowledge base. Queries can then refer to the different time points by means of temporal operators. This kind of setting has been intensively investigated for temporal conjunctive queries, that is, queries with temporal operators from LTL appearing in front of Boolean combinations of atoms, for expressive DLs in [6,7], for ${DL-Lite}_{R}$ in [19], and for $EL$ in [20]. We base our study in this paper on this general setting.

For stream reasoning systems, erroneous data can be a severe problem, as for instance pointed out in [43]. If inconsistencies arise in the knowledge base, the logical reasoning mechanisms are rendered useless. There are several directions of research to cope with this problem. While some employ non-monotonic reasoning techniques [44,49], others try to resolve the inconsistencies directly [36] or perform reasoning with respect to inconsistency-tolerant semantics (see [13] for a recent overview). We follow the latter road, since the techniques developed there are tailored to ontology-mediated queries and often of lower complexity than the other approaches for resolving inconsistencies.

A prominent approach for inconsistency-tolerant reasoning is to consider repairs of the knowledge base, i.e., maximal consistent subsets of the data, and then to perform query answering with respect to these subsets. Arguably the most natural and well-known inconsistency-tolerant semantics is the AR semantics [37,39], inspired by consistent query answering in the database setting [11], which considers the queries that hold in every repair. However, AR query answering is intractable even for very simple ontologies [12], which leads the authors of [37,39] to propose an approximation of AR tractable for ${DL-Lite}_{R}$ , namely the IAR semantics, which queries the intersection of the repairs. Beside its better computational properties, this semantics is more cautious, since it provides answers supported by facts that are not involved in any contradictions. It may therefore be interesting in our setting when the observed system should change its behaviour only if some situation has been recognized with a very high confidence. Finally, the brave semantics [16] returns every answer that holds in some repair, so is supported by some consistent set of facts. This less cautious semantics may be relevant for context recognition, when critical situations must imperatively be handled.

For the two DLs to be investigated in this paper, answering of (atemporal) conjunctive queries under these inconsistency-tolerant semantics has already been investigated for ${DL-Lite}_{R}$ in [16,37–39] and for ${EL}_{⊥}$ in [13,51]. Attention has then turned to the problem of designing algorithms and implementing these alternative semantics. Most work has focused on the IAR semantics and dialects of DL-Lite, due to the aforementioned tractability result [39,52,54]. A notable exception is the $CQAPri$ system, which implements all three mentioned semantics—AR, IAR and brave—for ${DL-Lite}_{R}$ knowledge bases [14,15].

So far, inconsistency-tolerant semantics have not been investigated in combination with temporal reasoning. In this paper, we lift inconsistency-tolerant semantics to the case of answering temporal conjunctive queries over lightweight DL temporal knowledge bases.

1.1. Contributions

This article extends the conference paper [21] on temporal query answering in ${DL-Lite}_{R}$ over inconsistent data, where the complexity of answering queries with LTL operators, but without negation, over ${DL-Lite}_{R}$ temporal knowledge bases was investigated. The considered ontologies admit the use of rigid predicates, which are predicates that do not change their interpretation over time. The initial results were obtained for the three inconsistency-tolerant semantics AR, IAR and brave and with respect to three cases of rigid predicates: no rigid predicates, rigid concepts only, and rigid concepts together with rigid roles.

Compared to the conference version, the present article includes new complexity results (all results for ${EL}_{⊥}$ , as well as some results for ${DL-Lite}_{R}$ ). It also extends the set of temporal operators, distinguishing bounded and unbounded variants of the future LTL operators, in order to cover the two different settings that have been investigated for temporal query answering in the literature, where temporal knowledge bases are interpreted w.r.t. finite or infinite sequences of interpretations. Furthermore, we investigate both cases: the one where negation is admitted in the query language and the one where it is not.

The complexity upper bounds are often obtained by non-deterministic procedures that require, for instance, to guess the right repairs which may not be feasibly computed in practice. Thus algorithms that lend themselves to implementation are still to be devised. We make two contributions toward practical algorithms for temporal inconsistency-tolerant query answering. The first is a polynomial reduction of reasoning in the presence of rigid predicates to reasoning without such predicates by propagating the rigid facts in the sequence of datasets. The second is to identify cases where in the absence of rigid predicates the well-known methods for classical temporal query answering and (atemporal) inconsistency-tolerant query answering can straightforwardly be combined. We show that for the IAR semantics, this yields a sound and complete algorithm. For the AR semantics, such a combination of the algorithms always yields a sound approximation, and additionally yields a sound and complete procedure if the query contains only a restricted set of operators.

This paper is structured as follows. In the next section, we introduce the basic notions of DLs, query answering, inconsistency-tolerant semantics for atemporal knowledge bases and the temporal setting. Furthermore, we discuss known complexity results for both inconsistency-tolerant and temporal query answering in the logics considered. In Section 3, we lift the introduced inconsistency-tolerant semantics to temporal query answering over inconsistent data. Section 4 gives an overview over the complexity results obtained. General versions of algorithms for testing (non-)entailment of temporal conjunctive queries under the different semantics are described in Section 5 in preparation of the complexity analysis. Section 6 shows data and combined complexity of inconsistency-tolerant temporal query answering for ${DL-Lite}_{R}$ and ${EL}_{⊥}$ for the case where the query language admits negation. In Section 7, we complete the complexity picture of temporal query answering under classical semantics by investigating the case where the query does not contain negation. We then built on these results to provide the complexity of inconsistency-tolerant temporal query answering for queries without negation in Section 8. Finally, Section 9 investigates two approaches for practical implementations that allow to employ well-known methods. The article finishes with a section on conclusions and future work.

To improve readability, some of the proofs have been moved to the appendix and are only sketched in the main text.

2. Preliminaries

We briefly recall the syntax and semantics of DLs and the three inconsistency-tolerant semantics that we consider, and then we introduce our setting of temporal query answering.

Syntax. A DL knowledge base (KB) $K$ consists of an ABox $A$ and a TBox $T$ , both constructed from three countably infinite sets: a set $N_{C}$ of concept names (unary predicates), a set $N_{R}$ of role names (binary predicates), and a set $N_{I}$ of individual names (constants). The ABox (dataset) is a finite set of concept assertions $A (a)$ and role assertions $R (a, b)$ , where $A \in N_{C}$ , $R \in N_{R}$ , $a, b \in N_{I}$ . The TBox (ontology) is a finite set of axioms whose form depends on the particular DL.

In ${DL-Lite}_{R}$ , TBox axioms are either concept inclusions $B ⊑ C$ or role inclusions $P ⊑ S$ , built according to the following syntax, where $A \in N_{C}$ and $R \in N_{R}$ : $\begin{matrix} B : = A ∣ \exists P C : = B ∣ \neg B \\ P : = R ∣ R^{-} S : = P ∣ \neg P . \end{matrix}$ Inclusions of the form $B_{1} ⊑ B_{2}$ or $P_{1} ⊑ P_{2}$ are called positive inclusions (PI), those of the form $B_{1} ⊑ \neg B_{2}$ or $P_{1} ⊑ \neg P_{2}$ are called negative inclusions (NI).

In ${EL}_{⊥}$ , the TBox contains concept inclusions of the form $C_{1} ⊑ C_{2}$ , where $C_{1}$ and $C_{2}$ are built according to the following syntax, where $A \in N_{C}$ and $R \in N_{R}$ : $\begin{matrix} C : = ⊤ ∣ ⊥ ∣ A ∣ \exists R . C ∣ C ⊓ C . \end{matrix}$ An ${EL}_{⊥}$ inclusion of the form $C_{1} ⊓ C_{2} ⊑ ⊥$ can also be written in the form of a negative inclusion $C_{1} ⊑ \neg C_{2}$ .

Semantics. An interpretation is a tuple of the form $I = ⟨ Δ^{I}, \cdot^{I} ⟩$ , where $Δ^{I}$ is a non-empty set and $\cdot^{I}$ maps each $a \in N_{I}$ to $a^{I} \in Δ^{I}$ , each $A \in N_{C}$ to $A^{I} \subseteq Δ^{I}$ , and each $R \in N_{R}$ to $R^{I} \subseteq Δ^{I} \times Δ^{I}$ . We adopt the unique name assumption, i.e., for all $a, b \in N_{I}$ , we require $a^{I} \neq b^{I}$ if $a \neq b$ . The function $\cdot^{I}$ is straightforwardly extended to general concepts and roles, e.g., $⊤^{I} = Δ^{I}$ , $⊥^{I} = \emptyset$ , ${(R^{-})}^{I} = {(d, e) ∣ (e, d) \in R^{I}}$ , ${(\neg R)}^{I} = Δ^{I} \times Δ^{I} ∖ R^{I}$ , ${(\exists P)}^{I} = {d ∣ \exists e : (d, e) \in P^{I}}$ , ${(\exists P . C)}^{I} = {d ∣ \exists e : (d, e) \in P^{I}, e \in C^{I}}$ ${(C_{1} ⊓ C_{2})}^{I} = C_{1}^{I} \cap C_{2}^{I}$ .

An interpretation $I$ satisfies an inclusion $G ⊑ H$ if $G^{I} \subseteq H^{I}$ ; it satisfies $A (a)$ (resp. $R (a, b)$ ) if $a^{I} \in A^{I}$ (resp. $(a^{I}, b^{I}) \in R^{I}$ ). We call $I$ a model of a KB $K = ⟨ T, A ⟩$ if $I$ satisfies all axioms in $T$ and all assertions in $A$ . A KB is consistent if it has a model, and we say that an ABox $A$ is $T$ -consistent (or simply consistent if $T$ is clear from the context), if the KB $⟨ T, A ⟩$ is consistent.

Queries. A conjunctive query (CQ) takes the form $q = \exists \vec{y} . ψ (\vec{x}, \vec{y})$ , where ψ is a conjunction of atoms of the form $A (t)$ or $R (t, t^{'})$ , with $t, t^{'}$ individual names or variables from $\vec{x} \cup \vec{y}$ . We call the variables in $\vec{x}$ the free variables in q. A CQ is called Boolean (BCQ) if it has no free variables (i.e., $\vec{x} = \emptyset$ ). A BCQ q is satisfied by an interpretation $I = ⟨ Δ^{I}, \cdot^{I} ⟩$ , written $I ⊧ q$ , if there is a homomorphism π mapping the variables and individual names of q into $Δ^{I}$ such that: $π (a) = a^{I}$ for every $a \in N_{I}$ , $π (t) \in A^{I}$ for every concept atom $A (t)$ in ψ, and $(π (t), π (t^{'})) \in R^{I}$ for every role atom $R (t, t^{'})$ in ψ. A BCQ q is entailed from $K$ , written $K ⊧ q$ , iff q is satisfied by every model of $K$ . Given a CQ q with free variables $\vec{x} = (x_{1}, \dots, x_{k})$ and a tuple of individuals $\vec{a} = (a_{1}, \dots, a_{k})$ , $\vec{a}$ is a certain answer to q over $K$ if $K ⊧ q (\vec{a})$ , where $q (\vec{a})$ is the BCQ resulting from replacing each $x_{j}$ in q by $a_{j}$ .

Inconsistency-tolerant semantics. A repair of $K = ⟨ T, A ⟩$ is an inclusion-maximal subset of $A$ that is $T$ -consistent. We consider three semantics based on repairs that have been previously introduced in the literature [16,37,39]. A tuple $\vec{a}$ is an answer to q over $K$ under

AR semantics, written $K ⊧_{AR} q (\vec{a})$ ,

iff $⟨ T, A^{'} ⟩ ⊧ q (\vec{a})$ for every repair $A^{'}$ of $K$ ;

IAR semantics, written $K ⊧_{IAR} q (\vec{a})$ ,

iff $⟨ T, A^{\cap} ⟩ ⊧ q (\vec{a})$ where $A^{\cap}$ is the intersection of all repairs of $K$ ;

brave semantics, written $K ⊧_{brave} q (\vec{a})$ ,

iff $⟨ T, A^{'} ⟩ ⊧ q (\vec{a})$ for some repair $A^{'}$ of $K$ .

Figure 1 summarizes the complexity of BCQ entailment under the different semantics for

{DL-Lite}_{R}

and

{EL}_{⊥}

. Data complexity is measured in the size of the ABox only, while combined complexity is measured in the size of the whole KB and the query. When complexity is measured w.r.t. the size of the KB (ABox and TBox), it is called KB complexity. For

{DL-Lite}_{R}

and

{EL}_{⊥}

, CQ answering under the classical semantics is in P w.r.t. KB complexity. We refer to Section 4 for a reminder on the definitions of the different complexity classes that appear in this work.

Fig. 1.

Complexity of BCQ entailment in ${DL-Lite}_{R}$ [16,37] and ${EL}_{⊥}$ [13,51].

Temporal query answering. We now present our temporal framework inspired from [6] and [18].

Definition 2.1 (TKB).

A temporal knowledge base (TKB) $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ consists of a TBox $T$ and a finite sequence of ABoxes ${(A_{i})}_{0 ⩽ i ⩽ n}$ . An infinite sequence $J = {(I_{i})}_{i ⩾ 0}$ of interpretations $I_{i} = ⟨ Δ, \cdot^{I_{i}} ⟩$ over a fixed non-empty domain Δ (constant domain assumption) is a model of $K$ iff for every $i \in [0, n]$ , $I_{i}$ is a model of $⟨ T, A_{i} ⟩$ , for every $i > n$ , $I_{i}$ is a model of $T$ , and for every $a \in N_{I}$ and all $i, j ⩾ 0$ , $a^{I_{i}} = a^{I_{j}}$ (rigidity of individual names). Rigid predicates are elements from the set $N_{R C} \subseteq N_{C}$ of rigid concepts and the set $N_{R R} \subseteq N_{R}$ of rigid roles. A sequence of interpretations $J = {(I_{i})}_{i ⩾ 0}$ respects rigid predicates iff for every $X \in N_{R C} \cup N_{R R}$ and all $i, j ⩾ 0$ , $X^{I_{i}} = X^{I_{j}}$ . A TKB is consistent if it has a model that respects rigid predicates. A sequence of ABoxes ${(A_{i})}_{0 ⩽ i ⩽ n}$ is $T$ -consistent, or simply consistent, if the TKB $⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ is consistent.

Example 2.2.
The following ${EL}_{⊥}$ TKB gives information useful to monitor a cluster of servers. The TBox $T$ defines that a server is overloaded when it executes a process with an increasing workload while its CPU is already maximally utilized. The sequence of ABoxes ${(A_{i})}_{0 ⩽ i ⩽ 2}$ records information on a server s. The set of rigid roles is $N_{R R} = {hasCPU}$ , which models the fact that the CPU of a server does not change over time. $\begin{array}{l} \begin{matrix} T = & {\exists executes . IncreasingWorkload ⊑ LoadRise, \\ \exists hasCPU . MaxUtilized ⊑ MaxLoaded, \\ LoadRise ⊓ MaxLoaded ⊑ Overloaded} \end{matrix} \\ \begin{matrix} A_{0} = & {hasCPU (s, c), MaxUtilized (c), \\ executes (s, p_{1}), IncreasingWorkload (p_{1})} \end{matrix} \\ \begin{matrix} A_{1} = & {MaxUtilized (c), executes (s, p_{1}), \\ executes (s, p_{2}), IncreasingWorkload (p_{2})} \end{matrix} \\ A_{2} = {executes (s, p_{2})} \end{array}$

It is sometimes convenient to represent a sequence of ABoxes as a set of assertions associated with timestamps, which we call timed assertions: ${(A_{i})}_{0 ⩽ i ⩽ n}$ then becomes ${(α, i) ∣ α \in A_{i}, 0 ⩽ i ⩽ n}$ .

A rigid concept is a concept which only uses rigid predicates. A rigid assertion is of the form $A (a)$ with $A \in N_{R C}$ or $R (a, b)$ with $R \in N_{R R}$ . We distinguish three cases depending on which predicates can be rigid: in the first case, we have no rigid predicates ( $N_{R C} = \emptyset$ and $N_{R R} = \emptyset$ ), in the second case, we do allow only for rigid concepts ( $N_{R C} \neq \emptyset$ and $N_{R R} = \emptyset$ ), and in the last case, we have both, rigid concepts and rigid roles ( $N_{R C} \neq \emptyset$ and $N_{R R} \neq \emptyset$ ). Because rigid concepts can be simulated with rigid roles using a pair of concept inclusions of the form $A ⊑ \exists R$ , $\exists R ⊑ A$ , these three cases cover all interesting combinations.

In the remainder of the paper, we always use n to denote the maximal timestamp of a TKB.
Definition 2.3 (TCQ).

Temporal conjunctive queries (TCQs) are built from CQs as follows: each CQ is a TCQ, and if $ϕ_{1}$ and $ϕ_{2}$ are TCQs, then so are $\neg ϕ_{1}$ (negation), $ϕ_{1} \land ϕ_{2}$ (conjunction), $ϕ_{1} \lor ϕ_{2}$ (disjunction), $◯ ϕ_{1}$ (next), $●^{b} ϕ_{1}$ (bounded next), $◯^{-} ϕ_{1}$ (strong previous), $●^{-} ϕ_{1}$ (weak previous), $□ ϕ_{1}$ (always), $□^{b} ϕ_{1}$ (bounded always), $□^{-} ϕ_{1}$ (always in the past), $♢ ϕ_{1}$ (eventually), $♢^{b} ϕ_{1}$ (bounded eventually), $♢^{-} ϕ_{1}$ (some time in the past), $ϕ_{1} U ϕ_{2}$ (until), $ϕ_{1} U^{b} ϕ_{2}$ (bounded until), and $ϕ_{1} S ϕ_{2}$ (since). We further may use $ψ_{1} \to ψ_{2}$ as a shortcut for $\neg ψ_{1} \lor ψ_{2}$ .

We impose the constraint that the past operators $◯^{-}$ , $□^{-}$ , $♢^{-}$ and $S$ cannot be nested under the unbounded future operators $◯$ , □, ♢ and $U$ (in second position) (see discussion later in this section).

Example 2.4 (Example 2.2 cont’d).

The following TCQ returns the list of servers which have been overloaded at least twice. $\begin{matrix} ϕ = ♢^{-} (Overloaded (x) \land ◯^{-} ♢^{-} Overloaded (x)) \end{matrix}$

Note that we can modify our query to speak about a window of 10 time units as follows: $\begin{matrix} ◯^{- 10} ♢ (Overloaded (x) \land ◯ ♢ Overloaded (x)) \end{matrix}$ where $◯^{- 10}$ abbreviates a sequence of ten $◯^{-}$ operators. Differently to window operators found in other settings however, subexpressions within such a window can refer to time points outside this window.

Given a TCQ ϕ, we refer to the TCQs that occur in ϕ as subformulas of ϕ. We sometimes use the notion of the propositional abstraction of a Boolean TCQ ϕ, which is the propositional LTL formula obtained by replacing each BCQ in ϕ by a propositional variable (e.g., the propositional abstraction of $◯ \exists x . A (x) \lor \exists x . B (x)$ is the propositional LTL formula $◯ x_{1} \lor x_{2}$ ).

Remark 2.5 (Choice of operators).

The additional LTL operators $W$ (weak until), $W^{-}$ (weak since), $R$ (release), and $R^{-}$ (past release) can be expressed by our set of operators as follows: $\begin{array}{l} ϕ_{1} W ϕ_{2} \equiv (ϕ_{1} U ϕ_{2}) \lor (□ ϕ_{1}), \\ ϕ_{1} W^{-} ϕ_{2} \equiv (ϕ_{1} S ϕ_{2}) \lor (□^{-} ϕ_{1}), \\ ϕ_{1} R ϕ_{2} \equiv ϕ_{2} W (ϕ_{2} \land ϕ_{1}), and \\ ϕ_{1} R^{-} ϕ_{2} \equiv ϕ_{2} W^{-} (ϕ_{2} \land ϕ_{1}) . \end{array}$ We will consider in Sections 7, 8 and 9 a special setting where TCQs do not contain negation symbols, which sometimes leads to a lower computational complexity. For this reason, we did not introduce $□ ϕ$ as a shortcut for $\neg ♢ \neg ϕ$ , as it is often done in the literature, but instead treat the operators □ and $□^{b}$ as native members of our query language. Similarly, since the top and bottom concepts ⊤ and ⊥ are not allowed in every DL, ♢ (resp. $♢^{b}$ ) cannot be defined using $U$ (resp. $U^{b}$ ) as usual in LTL ( $♢ ϕ_{1} \equiv true U ϕ_{1}$ ), unless we allow for negation (where we can express $true$ using $\exists x . A (x) \lor \neg \exists x . A (x)$ ). We thus keep all these operators in the set we consider.

Note also that since disjunctions are allowed, TCQs could be defined with unions of conjunctive queries (UCQs) instead of CQs. We use CQs for simplicity.

Definition 2.6 (TCQ answering).

Given a TCQ ϕ with free variables

\vec{x} = (x_{1}, \dots, x_{k})

and a tuple of individuals

\vec{a} = (a_{1}, \dots, a_{k})

ϕ (\vec{a})

denotes the Boolean TCQ (BTCQ) resulting from replacing each

x_{j}

a_{j}

. A tuple

\vec{a}

is an answer to ϕ in a sequence of interpretations

J = {(I_{i})}_{i ⩾ 0}

at time point p iff

J, p ⊧ ϕ (\vec{a})

, where the satisfaction of a BTCQ ϕ by a sequence of interpretations

J

is defined by induction on its structure as shown in Table 1. A tuple

\vec{a}

is a certain answer to ϕ over

K

at time point p, written

K, p ⊧ ϕ (\vec{a})

, iff

J, p ⊧ ϕ (\vec{a})

for every model

J

K

that respects rigid predicates.

Table 1
Satisfaction of BTCQs by a sequence of interpretations

ϕ	$J, p ⊧ ϕ$ iff
$\exists \vec{y} . ψ (\vec{y})$	$I_{p} ⊧ \exists \vec{y} . ψ (\vec{y})$
$\neg ϕ_{1}$	$J, p ⊭ ϕ_{1}$
$ϕ_{1} \land ϕ_{2}$	$J, p ⊧ ϕ_{1}$ and $J, p ⊧ ϕ_{2}$
$ϕ_{1} \lor ϕ_{2}$	$J, p ⊧ ϕ_{1}$ or $J, p ⊧ ϕ_{2}$
$◯ ϕ_{1}$	$J, p + 1 ⊧ ϕ_{1}$
$●^{b} ϕ_{1}$	$p < n$ implies $J, p + 1 ⊧ ϕ_{1}$
$◯^{-} ϕ_{1}$	$p > 0$ and $J, p - 1 ⊧ ϕ_{1}$
$●^{-} ϕ_{1}$	$p > 0$ implies $J, p - 1 ⊧ ϕ_{1}$
$□ ϕ_{1}$	$\forall k$ , $k ⩾ p$ , $J, k ⊧ ϕ_{1}$
$□^{b} ϕ_{1}$	$\forall k$ , $p ⩽ k ⩽ n$ , $J, k ⊧ ϕ_{1}$
$□^{-} ϕ_{1}$	$\forall k$ , $0 ⩽ k ⩽ p$ , $J, k ⊧ ϕ_{1}$
$♢ ϕ_{1}$	$\exists k$ , $k ⩾ p$ , $J, k ⊧ ϕ_{1}$
$♢^{b} ϕ_{1}$	$\exists k$ , $p ⩽ k ⩽ n$ , $J, k ⊧ ϕ_{1}$
$♢^{-} ϕ_{1}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $J, k ⊧ ϕ_{1}$
$ϕ_{1} U ϕ_{2}$	$\exists k$ , $k ⩾ p$ , $J, k ⊧ ϕ_{2}$ and $\forall j, p ⩽ j < k, J, j ⊧ ϕ_{1}$
$ϕ_{1} U^{b} ϕ_{2}$	$\exists k$ , $p ⩽ k ⩽ n$ , $J, k ⊧ ϕ_{2}$ and $\forall j, p ⩽ j < k, J$ , $j ⊧ ϕ_{1}$
$ϕ_{1} S ϕ_{2}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $J, k ⊧ ϕ_{2}$ and $\forall j, k < j ⩽ p, J$ , $j ⊧ ϕ_{1}$

Example 2.7 (Example 2.2 cont’d).

It follows from the semantics of TKBs and TCQs that s is a certain answer to the TCQ ϕ of Example 2.4 over the TKB of Example 2.2 at time point 2 and at time point 1, but not at time point 0. Note that the rigidity of the role $hasCPU$ is crucial to get this answer.

In addition to the standard LTL past and unbounded future operators, we introduce four bounded future operators that mimic the semantics based on finite sequences of interpretations used in [18] and similar to that of LTL on finite traces (see e.g., [29]). Indeed, while the standard way of interpreting TKBs is based on infinite sequences of interpretations, it can be relevant to limit the scope of querying to the known time points, especially in the context of data streams. For instance, a user may want to ask whether a server has been running some process since it started ( $♢^{-} (Start (s) \land □^{b} executes (s, p))$ ), rather than whether it will continue to run this process forever. Moreover, we will see in Section 9.1 that using the bounded semantics can be of practical interest, since it allows us to reduce TCQ answering in the presence of rigid predicates to TCQ answering without rigid predicates. We choose to keep both unbounded and bounded versions of future operators to cover the two settings that have been previously studied for TCQ answering.

The constraint that TCQs should not contain past operators in the scope of unbounded future operators allows us to take advantage of the fact that a TKB entails the same BCQs for every time point $i > n$ to get a lower complexity in the case where there is no negation in the query. Indeed, in this case, the unknown future ( $i > n$ ) can be entirely summarized in one time point $n + 1$ . This will also be useful to obtain the data complexity upper bound of brave semantics in the case where there are neither rigid predicates present nor negation in the queries. Moreover, it turns out that for some cases in our analysis, this restriction has no impact on our results. Indeed, [18] shows that Gabbay’s separation theorem [30] can be used to rewrite an LTL formula ϕ containing bounded operators into a logically equivalent LTL formula $ϕ^{'}$ that is a Boolean combination of pure-past and pure-future formulas, although with an exponential blow-up. It follows that the restriction we impose does not have any influence over the data complexity of BTCQ entailment, as long as negation is allowed in the query. Moreover, since past operators can still appear in the scope of bounded future operators, all time points that refer to observations having been made sofar ( $i ⩽ n$ ) can be referenced by the query language. This query language can thus still express most situations that might be meaningful to detect.

It follows from the definition of certain answers that TCQ answering can be straightforwardly reduced to BTCQ entailment (using polynomially many tests w.r.t. data complexity and exponentially many tests w.r.t. combined complexity). For this reason, we focus on the latter problem.

Figure 2 summarizes the complexity of BTCQ entailment for ${DL-Lite}_{R}$ and ${EL}_{⊥}$ in the different cases depending on which kind of predicates are rigid. Our setting is slightly different from those of [19] and [20], because we have additional bounded operators and the restriction that past operators cannot be nested under unbounded future operators. However, the results shown in those papers apply to our setting. Indeed, the proofs for the lower bounds do not use past operators nested under future operators, and for the upper bounds, we argue that it is possible to reduce the entailment of a BTCQ ϕ that contains bounded operators to the entailment of a BTCQ $ϕ^{'}$ without bounded operators independently from the size of the TKB and linearly w.r.t. the query size. To do that, we add an assertion $end (a)$ to the last ABox $A_{n}$ of the sequence, where $end$ and a are both fresh names, and rewrite the query without unbounded operators using the following equivalences: $\begin{array}{l} ●^{b} ϕ_{1} \equiv ◯ ϕ_{1} \lor end (a), \\ □^{b} ϕ_{1} \equiv ϕ_{1} U (end (a) \land ϕ_{1}), \\ ♢^{b} ϕ_{1} \equiv \neg end (a) U ϕ_{1}, and \\ ϕ_{1} U^{b} ϕ_{2} \equiv (ϕ_{1} \land \neg end (a)) U ϕ_{2} . \end{array}$

Fig. 2.

Complexity of BTCQ entailment in ${DL-Lite}_{R}$ [19] and ${EL}_{⊥}$ [20].

3. Temporal query answering over inconsistent data

We extend the three inconsistency-tolerant semantics to temporal query answering. The main difference to the atemporal case is that in the presence of rigid concepts or roles, a TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ may be inconsistent even if each KB $⟨ T, A_{i} ⟩$ is consistent. Indeed, in this case, there may not be a sequence of interpretations $J = {(I_{i})}_{i ⩾ 0}$ such that $I_{i}$ is a model of $⟨ T, A_{i} ⟩$ for every $i \in [0, n]$ and which also respects rigid predicates. That is why we have to consider as repairs the $T$ -consistent sequences of subsets of the initial ABoxes that are component-wise maximal.

Definition 3.1 (Repair of a TKB).

A repair of a TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ is a sequence of ABoxes ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ such that ${(α, i) ∣ α \in A_{i}^{'}, 0 ⩽ i ⩽ n}$ is a maximal $T$ -consistent subset of ${(α, i) ∣ α \in A_{i}, 0 ⩽ i ⩽ n}$ . We denote the set of repairs of $K$ by $Rep (K)$ .

The next example illustrates the impact which rigid predicates can have on repairs.

Example 3.2.
Consider the TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ 1} ⟩$ . The TBox expresses that web servers and application servers are two distinct kinds of servers, and the ABoxes provide information about a server a that executes two processes b and c. $\begin{array}{l} \begin{matrix} T = & {WebServer ⊑ Server, \\ AppServer ⊑ Server, \\ WebServer ⊑ \neg AppServer} \end{matrix} \\ A_{0} = {WebServer (a), executes (a, b)} \\ \begin{matrix} A_{1} = & {AppServer (a), WebServer (a), \\ executes (a, c)} \end{matrix} \end{array}$ Assume that no predicate is rigid. The TKB $K$ is inconsistent because the timed assertions $(AppServer (a), 1)$ and $(WebServer (a), 1)$ violate the negative inclusion in $T$ . Specifically, $AppServer (a)$ and $WebServer (a)$ cannot both be true at time point 1. It follows that $K$ has two repairs that correspond to the two different ways of restoring consistency: ${(A_{i}^{'})}_{0 ⩽ i ⩽ 1}$ and ${(A_{i}^{″})}_{0 ⩽ i ⩽ 1}$ , where $\begin{array}{l} A_{0}^{'} = A_{0}^{″} = A_{0} \\ A_{1}^{'} = {AppServer (a), executes (a, c)} \\ A_{1}^{″} = {WebServer (a), executes (a, c)} . \end{array}$

Now assume that $AppServer$ is rigid. There is then a new reason for $K$ being inconsistent: the timed assertions $(WebServer (a), 0)$ and $(AppServer (a), 1)$ violate the negative inclusion of $T$ due to the rigidity of $AppServer$ , which implies that $AppServer (a)$ and $WebServer (a)$ should be both entailed at time point 0. Therefore, $K$ has now the two repairs ${(A_{i}^{'})}_{0 ⩽ i ⩽ 1}$ and ${(A_{i}^{″})}_{0 ⩽ i ⩽ 1}$ , where $\begin{array}{l} A_{0}^{'} = {executes (a, b)} \\ A_{1}^{'} = {AppServer (a), executes (a, c)} \\ A_{0}^{″} = A_{0} \\ A_{1}^{″} = {WebServer (a), executes (a, c)} . \end{array}$ Note that even though ${(A_{i}^{'})}_{0 ⩽ i ⩽ 1}$ is maximal (adding $WebServer (a)$ to $A_{0}^{'}$ renders the TKB inconsistent), $A_{0}^{'}$ is not a repair of $⟨ T, A_{0} ⟩$ , because it is not maximal.

We extend the semantics AR, IAR, and brave to the temporal case in the natural way by regarding sequences of ABoxes.
Definition 3.3 (AR, IAR, brave semantics for TCQs).

A tuple $\vec{a}$ is an answer to a TCQ ϕ over a TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ at time point p under

AR semantics, written $K, p ⊧_{AR} ϕ (\vec{a})$ ,

iff $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ (\vec{a})$ for every repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ ;

IAR semantics, written $K, p ⊧_{IAR} ϕ (\vec{a})$ ,

iff $⟨ T, {(A_{i}^{ir})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ (\vec{a})$ ,

with $A_{i}^{ir} = ⋂_{{(A_{j}^{'})}_{0 ⩽ j ⩽ n} \in Rep (K)} A_{i}^{'}$ for all $i \in [0, n]$ ;

brave semantics, written $K, p ⊧_{brave} ϕ (\vec{a})$ ,

iff $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ (\vec{a})$ for some repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ .

The following relationships between the semantics, which already hold in the atemporal case, are implied by their definition: $\begin{array}{rcl} K, p ⊧_{IAR} ϕ (\vec{a}) & \Rightarrow & K, p ⊧_{AR} ϕ (\vec{a}) \\ \Rightarrow & K, p ⊧_{brave} ϕ (\vec{a}) . \end{array}$ In the following example, we illustrate the effect of the different semantics in the temporal case.

Example 3.4 (Example 3.2 cont’d).

Consider the following three temporal conjunctive queries. $\begin{array}{l} ϕ_{1} = □^{b} (\exists y . executes (x, y)) \\ ϕ_{2} = □^{b} (\exists y . Server (x) \land executes (x, y)) \\ ϕ_{3} = □^{b} (\exists y . AppServer (x) \land executes (x, y)) \end{array}$ If there are no rigid predicates, the intersection of the repairs is ${(A_{i}^{ir})}_{0 ⩽ i ⩽ 1}$ , with $A_{0}^{ir} = A_{0}$ and $A_{1}^{ir} = {executes (a, c)}$ . We have $K, 0 ⊧_{IAR} ϕ_{1} (a)$ , because in every model of the intersection of the repairs a executes b at time point 0 and c at time point 1. For $ϕ_{2}$ , $K, 0 ⊧_{AR} ϕ_{2} (a)$ , since every model of every repair assigns a to $WebServer$ at time point 0 and to either $AppServer$ (in models of ${(A_{i}^{'})}_{0 ⩽ i ⩽ 1}$ ) or $WebServer$ (in models of ${(A_{i}^{″})}_{0 ⩽ i ⩽ 1}$ ) at time point 1. However, $K, 0 ⊭_{IAR} ϕ_{2} (a)$ . Finally, $K, 0 ⊭_{brave} ϕ_{3} (a)$ , because no repair entails $AppServer (a)$ at time point 0.

If $AppServer$ is rigid, the intersection of the repairs is ${(A_{i}^{ir})}_{0 ⩽ i ⩽ 1}$ with $A_{0}^{ir} = {executes (a, b)}$ and $A_{1}^{ir} = {executes (a, c)}$ . So, still $K, 0 ⊧_{IAR} ϕ_{1} (a)$ . Since every model of every repair assigns a to $Server$ at time points 0 and 1 (either because a is a web server or because a is an application server), $K, 0 ⊧_{AR} ϕ_{2} (a)$ , but $K, 0 ⊭_{IAR} ϕ_{2} (a)$ . Finally, $K, 0 ⊧_{brave} ϕ_{3} (a)$ , because every model of $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ 1} ⟩$ assigns a to $AppServer$ at any time point by rigidity of $AppServer$ , but $K, 0 ⊭_{AR} ϕ_{3} (a)$ .

We conclude this section by pointing out some characteristics of the case without rigid predicates that will be useful later. If there are no rigid predicates, the interpretations $I_{i}$ of a model $J = {(I_{i})}_{i ⩾ 0}$ of $K$ that respects rigid predicates are independent, besides the interpretation of the individual names. We thus obtain the following proposition.

Proposition 3.5.
If $N_{R C} = N_{R R} = \emptyset$ , then a TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ is consistent iff every $⟨ T, A_{i} ⟩$ is consistent. Moreover, if $K$ is consistent, for every $p \in [0, n]$ , $I_{p}^{'}$ is a model of $⟨ T, A_{p} ⟩$ iff there exists a model $J = {(I_{i})}_{i ⩾ 0}$ of $K$ such that $I_{p} = I_{p}^{'}$ .
Proof.
If $N_{R C} = N_{R R} = \emptyset$ , a sequence of interpretations $J = {(I_{i})}_{i ⩾ 0}$ is a model of $K$ that respects rigid predicates iff it is a model of $K$ . It follows that $K$ is consistent iff there exists $J = {(I_{i})}_{i ⩾ 0}$ such that for every $i \in [0, n]$ , $I_{i}$ is a model of $⟨ T, A_{i} ⟩$ , for every $i > n$ , $I_{i}$ is a model of $T$ , and for every $a \in N_{I}$ and all $i, j ⩾ 0$ , $a^{I_{i}} = a^{I_{j}}$ . This already establishes one direction of the proposition. We show that also the other direction holds.

Assume that every $⟨ T, A_{i} ⟩$ is consistent, i.e., every $⟨ T, A_{i} ⟩$ has a model. Let $p \in [0, n]$ be any fixed index and $I_{p}^{'} = ⟨ Δ^{I_{p}^{'}}, \cdot^{I_{p}^{'}} ⟩$ be a model of $⟨ T, A_{p} ⟩$ . Since we adopt the unique name assumption and $N_{I}$ is unbounded, $Δ^{I_{p}^{'}}$ is an infinite set. Moreover, for every $i \in [0, n]$ , since $A_{i}$ is finite, by the Löwenheim–Skolem theorem, there exists a model $I_{i}^{″} = ⟨ Δ^{I_{i}^{″}}, \cdot^{I_{i}^{″}} ⟩$ of $⟨ T, A_{i} ⟩$ such that $Δ^{I_{i}^{″}}$ is countable. Thus $Δ^{I_{i}^{″}}$ can be mapped to $Δ^{I_{p}^{'}}$ by an injective function $f_{i}$ . For every i, we can then build a model $I_{i}^{'} = ⟨ Δ^{I_{i}^{'}}, \cdot^{I_{i}^{'}} ⟩$ of $⟨ T, A_{i} ⟩$ such that $Δ^{I_{i}^{'}} = Δ^{I_{p}^{'}}$ . For this, let $Δ = Δ^{I_{p}^{'}} ∖ f_{i} (Δ^{I_{i}^{″}})$ and select some domain element $d_{1} \in Δ^{I_{i}^{″}}$ . We define a mapping $m_{i} : Δ^{I_{i}^{″}} \to 2^{Δ^{I_{p}^{'}}}$ by setting $m_{i} (d) = {f_{i} (d)}$ for $d \neq d_{1}$ and $m_{i} (d_{1}) = {f_{i} (d_{1})} \cup Δ$ . It remains to set $a^{I_{i}^{'}} = f_{i} (a^{I_{i}^{″}})$ for all $a \in N_{I}$ , $A^{I_{i}^{'}} = ⋃_{d \in A^{I_{i}^{″}}} m_{i} (d)$ , and $R^{I_{i}^{'}} = {(d_{1}, d_{2}) \in Δ^{I_{i}^{'}} \times Δ^{I_{i}^{'}} ∣ (d_{1}^{'}, d_{2}^{'}) \in R^{I_{i}^{″}}, d_{1} \in m_{i} (d_{1}^{'}), d_{2} \in m_{i} (d_{2}^{'})}$ . Since $Δ^{I_{i}^{'}} = Δ^{I_{p}^{'}}$ for every $i \in [0, n]$ , there exists a bijection $b_{i} : Δ^{I_{i}^{'}} \to Δ^{I_{p}^{'}}$ such that for all $a \in N_{I}$ , $b_{i} (a^{I_{i}^{'}}) = a^{I_{p}^{'}}$ .

Using these bijections, we can construct a model $J = {(I_{i})}_{i ⩾ 0}$ of $K$ based on the interpretations $I_{0}^{'}, \dots, I_{n}^{'}$ as follows. For every $i > n$ , $I_{i} = I_{p}^{'}$ , $I_{p} = I_{p}^{'}$ , and for every $i \in [0, n]$ such that $i \neq p$ , $I_{i} = ⟨ Δ^{I_{p}^{'}}, \cdot^{I_{i}} ⟩$ , where $\cdot^{I_{i}}$ is defined by $a^{I_{i}} = a^{I_{p}^{'}}$ for every $a \in N_{I}$ , $A^{I_{i}} = {b_{i} (d) ∣ d \in A^{I_{i}^{'}}}$ for every $A \in N_{C}$ , and $R^{I_{i}} = {(b_{i} (d_{1}), b_{i} (d_{2})) ∣ (d_{1}, d_{2}) \in R^{I_{i}^{'}}}$ . Note that this construction ensures $a^{I_{i}} = a^{I_{j}}$ for all $i, j ⩾ 0$ . Furthermore, one easily establishes that for all $i \in [0, n]$ , $I_{i}$ is a model of $⟨ T, A_{i} ⟩$ , and for $i > n$ , $I_{i}$ is a model of $T$ . We obtain that $J$ is a model of $K$ such that $I_{p} = I_{p}^{'}$ . □

It follows that, if $N_{R C} = N_{R R} = \emptyset$ , CQs can be answered at time point p by answering them over the KB $⟨ T, A_{p} ⟩$ . Proposition 3.6.
If $N_{R C} = N_{R R} = \emptyset$ , then for every BCQ $q = \exists \vec{y} . ψ (\vec{y})$ and $p \in [0, n]$ , $K, p ⊧ q$ iff $⟨ T, A_{p} ⟩ ⊧ q$ .
Proof.
$K, p ⊧ q$ iff for every model $J = {(I_{i})}_{i ⩾ 0}$ of $K$ that respects rigid predicates, $I_{p} ⊧ q$ . By Proposition 3.5, this is the case iff for every model $I_{p}$ of $⟨ T, A_{p} ⟩$ , $I_{p} ⊧ q$ , which is equivalent to $⟨ T, A_{p} ⟩ ⊧ q$ . □

4. Complexity analysis overview

In the next four sections, we investigate the complexity of inconsistency-tolerant BTCQ entailment in ${DL-Lite}_{R}$ and ${EL}_{⊥}$ . Apart from the different DLs, we also consider two settings of query languages: in the first setting, all TCQs as defined in Section 2 are considered, in the second setting, we analyze the complexity for TCQs that do not use the negation operator. Furthermore, we investigate complexity depending on whether rigid symbols are present or absent and which of the 4 semantics are used (classical, AR, IAR or brave). All these investigations are carried out for combined or data complexity.

For classical semantics, some complexities have been investigated earlier for the different settings we consider. For the case where negations are allowed in the queries, the complexity of BTCQ entailment under the classical semantics has been studied in [19] for ${DL-Lite}_{R}$ and in [20] for $EL$ (cf. Section 2, Fig. 2). Furthermore, it has also been shown in [17,18] that in ${DL-Lite}_{R}$ , TCQs without negation (and with a bounded future semantics) can be rewritten into FO-queries for temporal databases, but this was shown only in a restricted setting without rigid names and only for rooted TCQs. In this case, rootedness of a CQ means that it contains at least a constant or an answer variable and all its terms are connected via chains of role atoms. A TCQ is rooted if every CQ in it is rooted.

Most of our complexity upper bounds are based on a set of general algorithms for BTCQ entailment under the different inconsistency-tolerant semantics, which we present in Section 5. Those allow us to obtain complexity upper bounds for the different settings based on the complexity of BTCQ entailment under classical semantics, on the complexity of recognizing repairs, and on the complexity of consistency checking. In Section 6, we establish the complexity of these basic tasks, and give complexity results for our two DLs of interest, ${EL}_{⊥}$ and ${DL-Lite}_{R}$ , regarding both data and combined complexity. In the cases where the general algorithms are insufficient to give tight bounds, we try to provide specialized algorithms.

We then restrict the query language and study the complexity of the entailment of BTCQs without negation. In Section 7, we first investigate this case under classical semantics, and observe that in some cases, disallowing negation leads to lower worst case complexities, even if we alleviate the limitations imposed in [17,18]. In Section 8 these lower complexities allow us to also improve the complexity bounds for inconsistency-tolerant reasoning when there is no negation in the TCQs. Furthermore, we take advantage of the absence of negation to tighten an upper bound for brave semantics without rigid predicates.

Synopsis of complexity classes. We recall the definitions of the complexity classes that appear in the following sections.

P: problems solvable in polynomial time.

NP: problems solvable in non-deterministic polynomial time.

coNP: problems whose complement is in NP.

$Δ_{2}^{p} [O (log n)]$ : problems solvable in polynomial time with at most logarithmically many calls to an NP oracle.

$Σ_{2}^{p}$ : problems solvable in non-deterministic polynomial time with an NP oracle.

$Π_{2}^{p}$ : problems whose complement is in $Σ_{2}^{p}$ .

${AC}^{0}$ : problems that can be solved by a uniform family of circuits of constant depth and polynomial size, with unbounded-fanin AND and OR gates. We have ${AC}^{0} \subseteq P$ .

ALogTime: problems solvable in logarithmic time by a random access alternating Turing machine. We have ${AC}^{0} \subseteq AL OG T IME \subseteq P$ .

PSpace: problems solvable in polynomial space.

ExpTime: problems solvable in exponential time.

NExpTime: problems solvable in non-deterministic exponential time.

coNExpTime: problems whose complement is in NExpTime.

For the remainder of this paper, $L$ is a DL which is interpreted w.r.t. standard interpretations, as defined in Section 2. We will consider in particular the cases $L$ = ${DL-Lite}_{R}$ and $L$ = ${EL}_{⊥}$ . Furthermore, we assume $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ to be the TKB we evaluate our query against, and ϕ to be the considered query.

5. General algorithms for inconsistency-tolerant BTCQ entailment

Our complexity bounds are based on a set of general algorithms for deciding BTCQ entailment under the different semantics, which are inspired from known algorithms for inconsistency-tolerant BCQ entailment in the atemporal case (see e.g., [51]). Depending on the semantics under consideration, it might be more natural to describe either a procedure for entailment or one for non-entailment, which is why these algorithms focus on different directions of the problem.

Non-entailment under AR semantics. The procedure $ARNonEntailment$ decides whether ϕ is not entailed by $K$ at time point p under AR semantics, and is defined as follows.

Guess a sequence ${(A_{i}^{'})}_{0 ⩽ i ⩽ n} \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}$ of ABoxes.

Verify that ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is a repair of $K$ and that $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊭ ϕ$ .

It is common to focus on non-entailment when studying the complexity of AR semantics, since this procedure needs to consider only one repair instead of all of them.

Entailment under brave semantics. The procedure $braveEntailment$ decides whether ϕ is entailed by $K$ at time point p under brave semantics, and is defined as follows.

Guess a sequence ${(A_{i}^{'})}_{0 ⩽ i ⩽ n} \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}$ of ABoxes.

Verify that ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is a repair of $K$ and that $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ$ .

Non-entailment under IAR semantics. The procedure $IARNonEntailment$ decides whether ϕ is not entailed by $K$ at time point p under IAR semantics, and is defined as follows.

Guess

a set $B = {(α_{1}, i_{1}), \dots, (α_{m}, i_{m})} \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}$ of timed assertions, together with

m subsets of the data ${(A_{i}^{' 1})}_{0 ⩽ i ⩽ n} \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}, \dots, {(A_{i}^{' m})}_{0 ⩽ i ⩽ n} \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}$ such that for every $j \in [1, m]$ , $α_{j} \notin A_{i_{j}}^{' j}$ .

Verify that

for every $j \in [1, m]$ , ${(A_{i}^{' j})}_{0 ⩽ i ⩽ n}$ is a repair of $K$ , and

$⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ∖ B ⟩, p ⊭ ϕ$ .

Note that

m ⩽ | {(A_{i})}_{0 ⩽ i ⩽ n} |

, Step 2(a) therefore has to verify only a linear number of repairs. We show that the algorithm decides non-entailment under IAR semantics. Indeed, if for every

(α_{j}, i_{j})

there exists a repair

{(A_{i}^{' j})}_{0 ⩽ i ⩽ n}

K

that does not contain

(α_{j}, i_{j})

, then

(α_{j}, i_{j})

is not in the intersection of the repairs of

K

. Thus

{(A_{i})}_{0 ⩽ i ⩽ n} ∖ {(α_{1}, i_{1}), \dots, (α_{m}, i_{m})}

is a superset of the intersection

{(A_{i}^{ir})}_{0 ⩽ i ⩽ n}

of the repairs of

K

. It follows that if

⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ∖ B ⟩, p ⊭ ϕ

, then

K, p ⊭_{IAR} ϕ

. For the other direction, assume that

K, p ⊭_{IAR} ϕ

, and let

B = {(α_{1}, i_{1}), \dots, (α_{m}, i_{m})} = {(A_{i})}_{0 ⩽ i ⩽ n} ∖ {(A_{i}^{ir})}_{0 ⩽ i ⩽ n}

. For each

(α_{j}, i_{j})

, there exists a repair

{(A_{i}^{' j})}_{0 ⩽ i ⩽ n}

K

that does not contain the timed assertion

(α_{j}, i_{j})

, and

⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ∖ B ⟩

p ⊭ ϕ

Similarly to the AR case, we use this procedure for non-entailment instead of a procedure for entailment. Deciding non-entailment allows us to consider a linear number of repairs instead of all of them, which can be exponentially many. However, for the IAR semantics, a direct procedure for IAR entailment is useful for showing combined complexity results for the DLs we consider. This procedure is based on the computation of the set of timed assertions that belong to some minimal inconsistent subset of the TKB.

Fig. 3.

Data [left] and combined [right] complexity of BTCQ entailment for BTCQs with negations. All complexities are tight, except those preceded by “in”, which are upper bounds. the results for the classical semantics are shown in [20] for ${EL}_{⊥}$ and in [19] for ${DL-Lite}_{R}$ .

Entailment under IAR semantics. We give an alternative procedure for IAR, $IAREntailment$ , which decides whether ϕ is entailed under IAR semantics at time point p.

For every $(α, j) \in {(A_{i})}_{0 ⩽ i ⩽ n}$ , check whether $(α, j)$ belongs to a minimal inconsistent subset of $K$ by asking an oracle whether there exists a $T$ -inconsistent set of timed assertions $B \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}$ such that $B ∖ {(α, j)}$ is consistent.

Call the oracle to determine whether ϕ is entailed at time point p by the TKB from which all timed assertions that belong to some minimal inconsistent subset have been removed.

We show that the intersection of the repairs of

K

is obtained by removing the minimal inconsistent subsets of

K

. Let

B \subseteq {(A_{i})}_{0 ⩽ i ⩽ n}

be a minimal inconsistent subset of

K

and

(α, i) \in B

. Since

B ∖ {(α, i)}

is consistent,

(α, i)

is not in the repairs that contain

B ∖ {(α, i)}

. In the other direction, if a timed assertion

(α, i)

does not appear in some repair

{(A_{i}^{'})}_{0 ⩽ i ⩽ n}

K

, since the repairs are maximal,

{(A_{i}^{'})}_{0 ⩽ i ⩽ n} \cup {(α, i)}

is inconsistent, and

(α, i)

occurs in some minimal inconsistent subset of

K

6. Complexity of inconsistency-tolerant BTCQ entailment with negation in the query

In this section, we investigate the complexity of BTCQ entailment for general BTCQs, that is, BTCQs that may contain negation. For this, we first establish the complexities of consistency checking and repair recognition, i.e., the task of deciding whether a sequence of ABoxes is a repair of $K$ . We then build on these results to prove the complexity of inconsistency-tolerant temporal query entailment using the general algorithms described in the last section, while showing matching lower bounds. We thus obtain the following theorem.

Theorem 6.1.
The results in Fig. 3 hold.

6.1. Consistency checking and repair recognition for TKBs

We reduce these tasks to the atemporal case by defining an atemporal KB $\tilde{K}$ based on $K$ . For $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ , $\tilde{K} = ⟨ \tilde{T}, \tilde{A} ⟩$ is defined in Fig. 4. We first show a correspondence between the models of $K$ that respect rigid predicates and the models of $\tilde{K}$ .

Fig. 4.

KB $\tilde{K} = ⟨ \tilde{T}, \tilde{A} ⟩$ representing $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ .

Lemma 6.2.

$K$ is consistent iff $\tilde{K}$ is consistent.

Proof.

(⇐) We construct a function $temp$ from the models of $\tilde{K}$ to those of $K$ that respect rigid predicates. Assume $\tilde{K}$ is consistent, and let $\tilde{I}$ be a model of $\tilde{K}$ . We define $temp (\tilde{I}) = J = {(I_{i})}_{i ⩾ 0}$ as follows. For every $i \in [0, n]$ , we set

$a^{I_{i}} = a^{\tilde{I}}$ for every $a \in N_{I}$ ,

$A^{I_{i}} = A^{\tilde{I}}$ for every $A \in N_{R C}$ ,

$R^{I_{i}} = R^{\tilde{I}}$ for every $R \in N_{R R}$ ,

$A^{I_{i}} = A_{i}^{\tilde{I}}$ for every $A \in N_{C} ∖ N_{R C}$ , and

$R^{I_{i}} = R_{i}^{\tilde{I}}$ for every $R \in N_{R} ∖ N_{R R}$ ,

and for every

i > n

, we set

$a^{I_{i}} = a^{\tilde{I}}$ for every $a \in N_{I}$ ,

$A^{I_{i}} = A^{\tilde{I}}$ for every $A \in N_{R C}$ ,

$R^{I_{i}} = R^{\tilde{I}}$ for every $R \in N_{R R}$ ,

$A^{I_{i}} = A_{n + 1}^{\tilde{I}}$ for every $A \in N_{C} ∖ N_{R C}$ , and

$R^{I_{i}} = R_{n + 1}^{\tilde{I}}$ for every $R \in N_{R} ∖ N_{R R}$ .

We show that the sequence $temp (\tilde{I})$ of interpretations is a model of $K$ that respects rigid predicates.

For every time-point $i \in [0, n]$ , $I_{i}$ is a model of $A_{i}$ . If $A (a) \in A_{i}$ , then either $A \in N_{R C}$ and $A (a) \in \tilde{A}$ , or $A \notin N_{R C}$ and $A_{i} (a) \in \tilde{A}$ . In both cases, $a^{I_{i}} = a^{\tilde{I}} \in A^{I_{i}}$ . The same argument holds for the role assertions in $A_{i}$ .

For every $i \in [0, n + 1]$ , $I_{i}$ is a model of $T$ . Slightly abusing notation and viewing an interpretation as an infinite set of assertions, we denote by $RenameNotRig (I_{i}, i)$ the interpretation obtained from $I_{i}$ by renaming every non-rigid predicate X by $X_{i}$ . The interpretations of all rigid predicates and of all $A_{i}$ and $R_{i}$ are the same in $RenameNotRig (I_{i}, i)$ and $\tilde{I}$ . Since $\tilde{I}$ is a model of $\tilde{T}$ , and $\tilde{T}$ does not contain any axiom that involves two non-rigid predicates $X_{i}$ and $X_{j}$ with $i \neq j$ , $RenameNotRig (I_{i}, i)$ is a model of $\tilde{T}$ . Moreover $RenameNotRig (T, i) \subseteq \tilde{T}$ , and therefore $RenameNotRig (I_{i}, i)$ is a model of $RenameNotRig (T, i)$ . Hence, $I_{i}$ is a model of $T$ .

For every $i > n + 1$ , $I_{i} = I_{n + 1}$ is a model of $T$ .

For every $i ⩾ 0$ , for every $A \in N_{R C}$ , $A^{I_{i}} = A^{\tilde{I}}$ , and for every $R \in N_{R C}$ , $R^{I_{i}} = R^{\tilde{I}}$ . Therefore, $J$ respects rigid predicates.

We obtain that

temp (\tilde{I})

is a model of

K

that respects rigid predicates.

(⇒) For the other direction, we construct a function $atemp$ from the models of $K$ that respect rigid predicates to those of $\tilde{K}$ . Assume $K$ is consistent, and let $J = {(I_{i})}_{i ⩾ 0}$ be a model of $K$ that respects rigid predicates. We define $atemp (J) = \tilde{I}$ as follows.

$a^{\tilde{I}} = a^{I_{0}}$ ( $= a^{I_{i}}$ for every $i ⩾ 0$ ) for every $a \in N_{I}$ ,

$A^{\tilde{I}} = A^{I_{0}}$ for every $A \in N_{R C}$ ,

$R^{\tilde{I}} = R^{I_{0}}$ for every $R \in N_{R R}$ ,

$A_{i}^{\tilde{I}} = A^{I_{i}}$ for every $A \in N_{C} ∖ N_{R C}$ and $i \in [0, n]$ , and

$R_{i}^{\tilde{I}} = R^{I_{i}}$ for every $R \in N_{R} ∖ N_{R R}$ and $i \in [0, n]$ .

Again, we show that

\tilde{I}

is a model of

\tilde{K}

by considering the ABox and the TBox separately.

$\tilde{I}$ is a model of $\tilde{A}$ . If $A (a) \in \tilde{A}$ with $A \in N_{R C}$ , then $a^{\tilde{I}} = a^{I_{0}} \in A^{\tilde{I}}$ , and if $A_{i} (a) \in \tilde{A}$ for some $A \notin N_{R C}$ , then $A (a) \in A_{i}$ and $a^{\tilde{I}} = a^{I_{i}} \in A^{\tilde{I}}$ . The situation is the same for the role assertions in $\tilde{A}$ .

$\tilde{I}$ is a model of $\tilde{T}$ . If we rename the non-rigid predicates, $RenameNotRig (I_{i}, i)$ coincides with $\tilde{I}$ on the interpretation of all rigid predicates and all $A_{i}$ and $R_{i}$ . Since each $I_{i}$ is a model of $T$ , each interpretation $RenameNotRig (I_{i}, i)$ is a model of $RenameNotRig (T, i)$ , and since $\tilde{T}$ does not contain any axiom that involves two non-rigid predicates $X_{i}$ and $X_{j}$ with $i \neq j$ , each $RenameNotRig (I_{i}, i)$ is a model of $\tilde{T}$ . It follows that $\tilde{I}$ is a model of $\tilde{T}$ .

We thus obtain a direct correspondence between the models of $K$ and those of $\tilde{K}$ , and that $K$ is satisfiable iff $\tilde{K}$ is satisfiable. □

It follows that consistency checking of TKBs can be polynomially reduced to consistency checking of KBs.

Lemma 6.3.

If for a DL $L$ , consistency checking of $L$ -KBs is inP, then consistency checking of $L$ -TKBs is inPas well.

Proof.

By Lemma 6.2, the TKB $K$ is consistent iff the KB $\tilde{K}$ is consistent. If consistency checking is in P for $L$ -KBs, the consistency of $K$ can then be checked in time polynomial in the size of $\tilde{T}$ and $\tilde{A}$ . Since the size of $\tilde{T}$ is polynomial in $| T |$ and n, and the size of $\tilde{A}$ is at most the size of ${(A_{i})}_{0 ⩽ i ⩽ n}$ , we obtain that TKB consistency checking is in P. □

We next show that repair recognition can be done with a polynomial number of consistency checks.

Lemma 6.4.

If for a DL $L$ , consistency checking of $L$ -TKBs is inP, then repair recognition, i.e., deciding whether a sequence of ABoxes ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is a repair of $K$ , is inP.

Proof.

Assume consistency checking of $L$ -TKBs is in P. Then, we can verify in P whether a sequence of ABoxes ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is a repair of $K$ as follows.

For every i, check that $A_{i}^{'} \subseteq A_{i}$ .

Check that ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is $T$ -consistent.

For every $(α, j) \in {(A_{i})}_{0 ⩽ i ⩽ n} ∖ {(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ , check that ${(A_{i}^{'})}_{0 ⩽ i ⩽ n} \cup {(α, j)}$ is $T$ -inconsistent. □

Note that Lemmas 6.3 and 6.4 apply to ${DL-Lite}_{R}$ and ${EL}_{⊥}$ alike.

6.2. Combined complexity

We are now ready to establish the complexity of BTCQ entailment under inconsistency-tolerant semantics. We start with the combined complexity. The following upper bounds follow straightforwardly from the procedures described in Section 5.

Proposition 6.5.
If repair recognition is in P and BTCQ entailment under the classical semantics is in PSpace w.r.t. combined complexity, then BTCQ entailment under AR, IAR, and brave semantics is in PSpace w.r.t. combined complexity.
Proof.
If verifying that a sequence of ABoxes is a repair is in P and verifying the entailment, and thus also verifying the non-entailment, of a BTCQ is in PSpace, then the procedures $ARNonEntailment$ , $IARNonEntailment$ and $braveEntailment$ all run in NPSpace=PSpace. □

Proposition 6.5 applies to ${DL-Lite}_{R}$ and ${EL}_{⊥}$ in all cases except for ${EL}_{⊥}$ with rigid roles, for which BTCQ entailment under classical semantics is coNExpTime-hard [20].
Proposition 6.6.
BTCQ entailment from an ${EL}_{⊥}$ -TKB under AR, IAR, and brave semantics is in coNExpTime w.r.t. combined complexity, even if $N_{R R} \neq \emptyset$ .
Proof.
For the AR and IAR semantics, we modify the procedures $ARNonEntailment$ and $IARNonEntailment$ described in Section 5 so that they also guess a certificate of the non-entailment of ϕ in the first step. Then, in the second step, the non-entailment of ϕ can be decided by simply verifying this certificate. The certificate can be checked in ExpTime, since the non-entailment of ϕ can be decided in NExpTime.

For the brave semantics’ upper bound, we give a NExpTime procedure to decide $K, p ⊭_{brave} ϕ$ . For every subset ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of ${(A_{i})}_{0 ⩽ i ⩽ n}$ , guess either “not a repair” or a certificate of the non-entailment of ϕ from $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩$ at time point p. Note that there are $2^{| {(A_{i})}_{0 ⩽ i ⩽ n} |}$ such subsets. For every such subset, verify in ExpTime whether it is indeed not a repair, or whether $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊭ ϕ$ . □

The matching PSpace and coNExpTime combined complexity lower bounds for ${EL}_{⊥}$ and ${DL-Lite}_{R}$ follow from the consistent case (cf. Section 2).
6.3. Data complexity for ${EL}_{⊥}$ -TKBs

We now prove the data complexity results, starting with ${EL}_{⊥}$ . We first consider the case without rigid predicates.

Proposition 6.7.
BTCQ entailment from an ${EL}_{⊥}$ -TKB with $N_{R C} = N_{R R} = \emptyset$ is
co NP -complete w.r.t. data complexity under AR and IAR semantics, and

NP -complete w.r.t. data complexity under brave semantics.

Proof.
The upper bounds follow from the procedures described in Section 5: since verifying that a sequence of ABoxes is a repair as well as verifying the non-entailment and entailment of a BTCQ take polynomial time w.r.t. data complexity, the procedures $ARNonEntailment$ , $IARNonEntailment$ , and $braveEntailment$ run in NP w.r.t. data complexity. The lower bounds follow from the atemporal case. □

Next, we prove the complexity of BTCQ entailment with rigid predicates. The following proposition establishes the upper bounds for the case where both rigid concepts and rigid roles are allowed.
Proposition 6.8.
BTCQ entailment from an ${EL}_{⊥}$ -TKB with $N_{R C} \neq \emptyset$ and $N_{R R} \neq \emptyset$ is
in co NP w.r.t. data complexity under AR and IAR semantics, and

in $Σ_{2}^{p}$ w.r.t. data complexity under brave semantics.

Proof.
For AR and IAR semantics, we modify the procedures described in Section 5 to also guess a certificate for the non-entailment of ϕ. This certificate can be checked in P, since the non-entailment of ϕ can be decided in NP. The upper bound for brave semantics is obtained using the procedure $braveEntailment$ described in Section 5. □

We show that these results are tight even if we only have rigid concepts. Proposition 6.9.
BTCQ entailment from an ${EL}_{⊥}$ -TKB with $N_{R C} \neq \emptyset$ is
co NP -hard w.r.t. data complexity under AR and IAR semantics, and

$Σ_{2}^{p}$ -hard w.r.t. data complexity under brave semantics.

Proof (Sketch).
The lower bounds for AR and IAR semantics follow from the atemporal case. For brave semantics, we show that the complement of brave TCQ entailment is $Π_{2}^{p}$ -hard by reduction from ${QBF}_{2, \forall}$ .

Let $Φ = \forall x_{1} \dots x_{m} \exists y_{1} \dots y_{r} φ$ be a ${QBF}_{2, \forall}$ -formula, where $φ = ⋀_{i = 0}^{h} ℓ_{i}^{0} \lor ℓ_{i}^{1} \lor ℓ_{i}^{2}$ is a 3-CNF formula over the propositional variables ${x_{1}, \dots, x_{m}, y_{1}, \dots, y_{r}}$ . Based on Φ, define the TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ 3 h + 2} ⟩$ and the TCQ ϕ as follows, where $N_{R C} = {T}$ . $\begin{array}{l} \begin{matrix} T = & {\exists Pos . T ⊑ Sat, \exists Neg . F ⊑ Sat, \\ \exists FromPos . Sat ⊑ T, \exists FromNeg . Sat ⊑ F, \\ \exists FromY . Sat ⊑ T, T ⊓ F ⊑ ⊥, \\ T ⊓ \exists ValY . T ⊑ ⊥} \end{matrix} \\ \begin{matrix} ϕ = & \neg □^{b} (NotFirst (c) \lor Sat (c) \\ \lor ◯ Sat (c) \lor ◯ ◯ Sat (c)) \end{matrix} \end{array}$ For each clause $ℓ_{i}^{0} \lor ℓ_{i}^{1} \lor ℓ_{i}^{2}$ , i.e., for every $i \in [0, h]$ , we define the following three ABoxes $A_{3 i + k}$ ( $0 ⩽ k ⩽ 2$ ): $\begin{array}{l} A_{3 i + 0} = B \cup B_{3 i + 0} \\ A_{3 i + k} = B \cup B_{3 i + k} \cup {NotFirst (c)}, 1 ⩽ k ⩽ 2, \end{array}$ where $\begin{array}{l} \begin{matrix} B = & {T (x_{j}), F (x_{j}) ∣ 1 ⩽ j ⩽ m} \\ \cup {ValY (y_{j}, \neg y_{j}), ∣ 1 ⩽ j ⩽ r} \end{matrix} \\ B_{3 i + k} = {Pos (c, x_{j}), FromPos (x_{j}, c)} if ℓ_{i}^{k} = x_{j} \\ B_{3 i + k} = {Neg (c, x_{j}), FromNeg (x_{j}, c)} if ℓ_{i}^{k} = \neg x_{j} \\ B_{3 i + k} = {FromY (y_{j}, c)} if ℓ_{i}^{k} = y_{j} \\ B_{3 i + k} = {FromY (\neg y_{j}, c)} if ℓ_{i}^{k} = \neg y_{j} . \end{array}$

We use the following claim, which we prove in detail in the appendix, and give the intuition behind the construction here. Claim.
Φ is valid iff $K, 0 ⊭_{brave} ϕ$ .

Recall that (i) Φ is valid iff for every valuation of the $x_{j}$ , there exists a valuation of the $y_{j}$ that satisfies φ, and that (ii) $K, 0 ⊭_{brave} ϕ$ iff every repair of $K$ has a model in which ϕ does not hold. The correspondence between valuations of variables of Φ and models of repairs of $K$ is ensured by $B$ . Intuitively, the rigid concept $T$ is used to encode that a variable is true. The disjoint concept $F$ encodes that a variable is false and is used to enforce that the repairs of $K$ correspond to the valuations of the $x_{j}$ . The role $ValY$ connects every pair of $y_{j}, \neg y_{j}$ , which ensures together with the inclusion $T ⊓ \exists ValY . T ⊑ ⊥$ that no model of a repair of $K$ assigns both $y_{j}$ and $\neg y_{j}$ to the rigid concept $T$ . As a consequence, each model of a repair of $K$ corresponds to a valuation of the $y_{j}$ .

Each clause $ℓ_{i}^{0} \lor ℓ_{i}^{1} \lor ℓ_{i}^{2}$ is represented by the three consecutive ABoxes $A_{3 i + 0}, A_{3 i + 1}$ and $A_{3 i + 2}$ , which each encode a literal of the clause in the $B_{3 i + k}$ part. The concept $NotFirst$ is used to indicate that the literal represented is not the first of the clause. The concept $Sat$ encodes the satisfaction of a clause, and the query expresses that it is not the case that every clause is satisfied (the disjunction is true iff the clause is satisfied by at least one of its three literals). Finally, the TBox expresses the conditions under which a clause is satisfied. In particular, the first two inclusions enforce that a clause is always satisfied if it contains a literal $x_{j}$ (resp. $\neg x_{j}$ ) assigned to true (resp. to false) in the repair, and the next three inclusions ensure that a clause is satisfied only if it contains a literal which is assigned to true (for the $\neg x_{j}$ , since the literals $x_{j}$ and $\neg x_{j}$ are represented with only one individual $x_{j}$ , the condition is that $x_{j}$ is assigned to false). □

6.4. Data complexity for ${DL-Lite}_{R}$ -TKBs

It remains to show the data complexity results for ${DL-Lite}_{R}$ . For AR and brave semantics, the upper bounds follow from the guess and check procedures described in Section 5. (Recall that the complexity of BTCQ entailment under classical semantics is ALogTime-complete for this DL, and thus in P.)

The lower bound for AR follows from the atemporal case, which establishes a tight coNP-bound even if $N_{R C} = N_{R R} = \emptyset$ .

In contrast, for brave semantics, BCQ entailment is tractable in the atemporal setting. However, we cannot directly extend this result to the temporal case. Indeed, the data complexity upper bound for brave CQ answering in ${DL-Lite}_{R}$ relies on the fact that the size of the minimal sets of assertions that support the query is bounded by the query size. This is not true in the temporal setting, as can already be seen by the query $ϕ = □^{-} A (a)$ , whose entailment at time point p can depend on p assertions in the TKB. In fact, we show that in the presence of rigid concepts, brave BTCQ entailment becomes NP-hard.

Proposition 6.10.
If $N_{R C} \neq \emptyset$ , then brave BTCQ entailment from ${DL-Lite}_{R}$ -TKBs is NP -hard w.r.t. data complexity. This already holds for BTCQs that do not contain negation.
Proof.
We show NP-hardness of brave BTCQ entailment from ${DL-Lite}_{R}$ -TKBs by reduction from SAT. Let $c_{0} \land \dots \land c_{n}$ be a CNF formula over variables $x_{1}, \dots, x_{m}$ . We define the following problem of BTCQ entailment under brave semantics, with two rigid concepts $T$ and $F$ . Let $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ be such that: $\begin{array}{l} \begin{matrix} T = & {\exists Pos ⊑ Sat, \exists Neg ⊑ Sat, \\ \exists {Pos}^{-} ⊑ T, \exists {Neg}^{-} ⊑ F, T ⊑ \neg F} \end{matrix} \\ \begin{matrix} A_{i} = & {Pos (a, x_{j}) ∣ x_{j} \in c_{i}} \\ \cup {Neg (a, x_{j}) ∣ \neg x_{j} \in c_{i}} for 0 ⩽ i ⩽ n \end{matrix} \end{array}$ Let $ϕ = □^{-} Sat (a)$ . We show that $c_{0} \land \dots \land c_{n}$ is satisfiable iff $K, n ⊧_{brave} ϕ$ . Note that ϕ does not contain negation. Indeed, since $T$ and $F$ are rigid, a repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ is such that each $x_{j}$ has either only $Pos$ or only $Neg$ incoming edges in ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ , i.e., $x_{j}$ occurs either only in assertions of the form $Pos (a, x_{j})$ or only in assertions of the form $Neg (a, x_{j})$ . We can thus define a valuation ν of the variables such that $ν (x_{j}) = true$ if ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ does not contain a timed assertion of the form $(Neg (c, x_{j}), k)$ , and $ν (x_{j}) = false$ otherwise. The clause $c_{i}$ is satisfied by ν iff there exists $x_{j}$ such that either $x_{j} \in c_{i}$ and $ν (x_{j}) = true$ or $\neg x_{j} \in c_{i}$ and $ν (x_{j}) = false$ , that is, iff there exists $x_{j}$ such that either $Pos (a, x_{j}) \in A_{i}^{'}$ or $Neg (a, x_{j}) \in A_{i}^{'}$ , which holds exactly iff $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, i ⊧ Sat (a)$ . It follows that $c_{0} \land \dots \land c_{n}$ is satisfiable iff there exists a repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ that entails ϕ at time point n. □

For the case $N_{R C} = N_{R R} = \emptyset$ , we have an ALogTime lower bound from the classical semantics, and it is open whether the NP upper bound for brave semantics can be improved. The challenge in obtaining a polynomial upper bound for BTCQ entailment under brave semantics lies intuitively in the non-trivial interaction between the brave semantics and the negation in the query (see also end of Section 8). While under brave semantics, it is more natural to focus on the positive problem of query entailment (one has to construct some subset of a repair), for entailment of BTCQs, it is more natural to focus on the negative problem of query non-entailment (one tries to find some counter-example for the entailment of the query [19]). While for both problems polynomial algorithms have been found, naive combinations of these approaches are not possible. However, since we did not manage to prove an NP lower bound either, it might still be possible to solve this problem in polynomial time.

In contrast, for IAR semantics, we can give a tractable upper bound even if $N_{R R} \neq \emptyset$ . The reason is that, in ${DL-Lite}_{R}$ -TKBs, the size of a minimal inconsistent subset is at most two, as in the atemporal case.
Fact 6.11 ([37], Lemma 1).

Due to the ${DL-Lite}_{R}$ syntax, the following holds: for every ${DL-Lite}_{R}$ TBox $T$ , the size of a minimal $T$ -inconsistent set of (timed) assertions is at most two.

Therefore, we can always compute the intersection of all repairs in polynomial time.

Proposition 6.12.
BTCQ entailment from a ${DL-Lite}_{R}$ -TKB under IAR semantics is in P w.r.t. data complexity, even if $N_{R R} \neq \emptyset$ and $N_{R C} \neq \emptyset$ .
Proof.
The size of the minimal $T$ -inconsistent subsets of ${(A_{i})}_{0 ⩽ i ⩽ n}$ is bounded by 2. We can thus skip the first step of the procedure $IAREntailment$ described in Section 5 and compute the minimal inconsistent subsets in P by checking the consistency of every timed assertion and pair of timed assertions (with a quadratic number of consistency checks), and then verify the entailment of the query in P w.r.t. data complexity over the TKB from which they have been removed. □

7. BTCQ entailment under classical semantics without negation in the query

This section completes the complexity picture for BTCQ entailment under the classical semantics by investigating the case where TCQs do not use negation. We show that the absence of negation in the query induces a complexity drop in several cases. These results are based on a more general property: we show that for any DL $L$ , if $L$ has the canonical model property for CQ answering over KBs, then $L$ has also the canonical model property for TCQ answering over TKBs for TCQs without negation. We use the canonical model to prove that for the classical semantics, the complexity upper bounds of the atemporal case transfer to the temporal case.

We first show that BCQ entailment from a TKB $K$ can be reduced to BCQ entailment from the KB $\tilde{K}$ defined Section 6, Fig. 4. For this, we define a similar transformation for BCQs as we did for TKBs. Let $q = \exists \vec{y} . ψ (\vec{y})$ be a BCQ and $p ⩾ 0$ be a time point. Consider $\begin{matrix} {\tilde{q}}_{p} = RenameNotRig (q, p) \end{matrix}$ where $RenameNotRig (q, p)$ replaces every non-rigid predicate X in q by $X_{p}$ if $p ⩽ n$ , and by $X_{n + 1}$ otherwise.

Lemma 7.1.
$K, p ⊧ q$ iff $\tilde{K} ⊧ {\tilde{q}}_{p}$ .
Proof.
The following proof is written for the case where $p \in [0, n + 1]$ . For the case $p > n + 1$ , p is replaced by $n + 1$ in the predicates names.

Assume that $K, p ⊧ q$ , and let $\tilde{I}$ be a model of $\tilde{K}$ . Let $J = {(I_{i})}_{i ⩾ 0} = temp (\tilde{I})$ be the corresponding model of $K$ that respects rigid predicates, as defined in the proof for Lemma 6.2. For any BCQ ψ without existential variables, we denote by $atoms (ψ)$ the set of (ground) atoms of ψ. Since $I_{p} ⊧ q$ , there then exists a mapping π from the set of constants and variables that appear in ψ into Δ such that for every $X (\vec{d}) \in atoms (ψ_{π})$ , where $ψ_{π}$ is the BCQ obtained by replacing the terms of ψ by their image by π, we have $\vec{d} \in X^{I_{p}}$ . It follows that for every $X (\vec{d}) \in atoms (ψ_{π})$ , if X is rigid then $\vec{d} \in X^{\tilde{I}}$ , and otherwise $\vec{d} \in X_{p}^{\tilde{I}}$ . Thus, $\tilde{I} ⊧ RenameNotRig (q, p)$ , i.e., $\tilde{I} ⊧ {\tilde{q}}_{p}$ . Hence $\tilde{K} ⊧ {\tilde{q}}_{p}$ .

For the other direction, assume that $\tilde{K} ⊧ {\tilde{q}}_{p}$ and let $J = {(I_{i})}_{i ⩾ 0}$ be a model of $K$ that respects rigid predicates. Let $\tilde{I} = atemp (J)$ be as defined in the proof for Lemma 6.2. Since $\tilde{I} ⊧ {\tilde{q}}_{p}$ , there exists a mapping π from the set of constants and variables that appear in ψ into Δ such that for every $X (\vec{d}) \in atoms (RenameNotRig (ψ_{π}, p))$ , we have $\vec{d} \in X^{\tilde{I}}$ . It follows that for every $X (\vec{d}) \in atoms (RenameNotRig (ψ_{π}, p))$ such that X is rigid, $\vec{d} \in X^{I_{p}}$ . Furthermore, we have $\vec{d} \in X^{I_{p}}$ for every $X_{p} (\vec{d}) \in atoms (RenameNotRig (ψ_{π}, p))$ such that X is not rigid. Thus, $I_{p} ⊧ q$ , and we obtain $K, p ⊧ q$ . □

Moreover, the size of ${\tilde{q}}_{p}$ is the same as q. We thus obtain the following lemma.
Lemma 7.2.
If BCQ entailment from an $L$ -KB is inPw.r.t. KB complexity, respectively inNPw.r.t. combined complexity, then so is BCQ entailment from an $L$ -TKB.
Proof.
If deciding whether $\tilde{K} ⊧ {\tilde{q}}_{p}$ is polynomial both in $| \tilde{T} |$ and in $| \tilde{A} |$ , then it is polynomial in $| T |$ and $| {(A_{i})}_{0 ⩽ i ⩽ n} |$ . It follows that deciding whether $K, p ⊧ q$ is in P w.r.t. KB complexity.

Moreover, if deciding whether $\tilde{K} ⊧ {\tilde{q}}_{p}$ is in NP w.r.t. $| \tilde{T} |$ , $| \tilde{A} |$ and $| {\tilde{q}}_{p} |$ , then verifying a certificate that $\tilde{K} ⊧ {\tilde{q}}_{p}$ can be done in polynomial time w.r.t. $| \tilde{T} |$ , $| \tilde{A} |$ and $| {\tilde{q}}_{p} |$ , so in polynomial time w.r.t. $| T |$ , n, $| {(A_{i})}_{0 ⩽ i ⩽ n} |$ and $| q |$ . It follows that deciding whether $K, p ⊧ q$ is in NP w.r.t. combined complexity. □

Next, we define the notion of canonical model property for BCQ entailment and for entailment of BTCQs without negation.
Definition 7.3 (Canonical model property).

A DL $L$ has the canonical model property for BCQ entailment iff for every consistent $L$ -KB $⟨ T, A ⟩$ , there exists a model $I_{⟨ T, A ⟩}$ such that for every BCQ q, $⟨ T, A ⟩ ⊧ q$ iff $I_{⟨ T, A ⟩} ⊧ q$ . We call $I_{⟨ T, A ⟩}$ the canonical model of KB $⟨ T, A ⟩$ .

A DL $L$ has the canonical model property for entailment of BTCQs without negation iff for any $L$ -TKB $⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ , there exists a model $J_{⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩}$ such that for every BTCQ without negation ϕ and every time point p, holds that $\begin{array}{l} ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ iff J_{⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩}, p ⊧ ϕ . \end{array}$ We call this model $J_{⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩}$ the canonical model of TKB $⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ .

Note that it is justified to speak of the canonical model of a KB or TKB $K$ because such a model can be homomorphically mapped into any other model of $K$ . Indeed, for every assertion α built over $N_{I}$ , $N_{C}$ and $N_{R}$ , if α holds in the canonical model of $K$ then it also holds in every model of $K$ .

The following theorem gives the relation between the canonical model property for BCQ entailment and the one for BTCQ entailment, and shows why the presence or absence of negation in the query matters.

Theorem 7.4.
If $L$ has the canonical model property for BCQ entailment, then $L$ also has the canonical model property for entailment of BTCQs without negation.
Proof (Sketch).
Let ${\tilde{I}}_{\tilde{K}}$ be the canonical model of $\tilde{K}$ and $J_{K} = {(I_{i})}_{i ⩾ 0} = temp ({\tilde{I}}_{\tilde{K}})$ . We show that $J_{K}$ is the canonical model of $K$ for BTCQs without negation, that is, for every BTCQ ϕ that does not contain any negation, $K, p ⊧ ϕ$ iff $J_{K}, p ⊧ ϕ$ .

Since $J_{K}$ is a model of $K$ that respects rigid predicates, if $K, p ⊧ ϕ$ then $J_{K}, p ⊧ ϕ$ . For the other direction, we show in the appendix by induction on the structure of ϕ that if $J_{K}, p ⊧ ϕ$ , then $K, p ⊧ ϕ$ . The interesting case is when ϕ is a BCQ. For a BCQ q, by Lemma 7.1, $K, p ⊧ q$ iff $\tilde{K} ⊧ {\tilde{q}}_{p}$ , which is exactly the case iff ${\tilde{I}}_{\tilde{K}} ⊧ {\tilde{q}}_{p}$ . By construction of $J_{K}$ , it follows that $K, p ⊧ q$ iff $J_{K}, p ⊧ q$ . □
Remark 7.5.
If ϕ contains negation, the preceding argument fails and $J_{K}$ is not a canonical model for TCQ answering, i.e., $J_{K}, p ⊧ \neg ϕ$ does not guarantee that $J, p ⊭ ϕ$ for every model $J$ that respects rigid predicates. As an example, consider the empty TKB, i.e. $T = \emptyset$ and $A_{i} = \emptyset$ for every $i \in [0, n]$ . We have $J_{K}, 0 ⊭ \exists x . A (x)$ , but we can easily construct a model $J$ for $⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ such that $J, 0 ⊧ \exists x . A (x)$ , so that $K ⊭ \neg \exists x . A (x)$ .

The following proposition is a direct consequence of the existence of a canonical model for entailment of BTCQs without negation.
Proposition 7.6.
Assume $L$ has the canonical model property for BCQ entailment. Then, for every $L$ -TKBs $K$ and $K^{'}$ , if $K$ and $K^{'}$ coincide for BCQ entailment, then $K$ and $K^{'}$ coincide for entailment of BTCQs without negation. I.e., if for every time point p and BCQ q, $K, p ⊧ q$ iff $K^{'}, p ⊧ q$ , then for every time point p and BTCQ ϕ without negation, $K, p ⊧ ϕ$ iff $K^{'}, p ⊧ ϕ$ .
Proof (Sketch).
We show this result in the appendix by induction on the structure of ϕ. We use the fact that by Theorem 7.4, $L$ has the canonical model property for entailment of BTCQs without negation, to apply the definitions of BTCQ satisfaction of Table 1 to the canonical models of $K$ and $K^{'}$ . □

We now prove a central proposition for TCQ answering over TKBs in DLs that have the canonical model property for entailment of BTCQs without negation. It amounts to reducing the entailment of BTCQs with unbounded future operators to the entailment of BTCQs with only bounded future operators. These can then be answered by considering only a finite number of time points.

Table 2
Entailment under classical semantics for DLs with the canonical model property for BCQ entailment

ϕ $K, p ⊧ ϕ$ iff $K^{}, p ⊧ ϕ$ iff

$\exists \vec{y} . ψ (\vec{y})$ $K^{}, p ⊧ \exists \vec{y} . ψ (\vec{y})$

$ϕ_{1} \land ϕ_{2}$ $K^{}, p ⊧ ϕ_{1}$ and $K^{}, p ⊧ ϕ_{2}$

$ϕ_{1} \lor ϕ_{2}$ $K^{}, p ⊧ ϕ_{1}$ or $K^{}, p ⊧ ϕ_{2}$

$◯ ϕ_{1}$ $K^{}, p + 1 ⊧ ϕ_{1}$

$●^{b} ϕ_{1}$ $p < n$ implies $K^{}, p + 1 ⊧ ϕ_{1}$

$◯^{-} ϕ_{1}$ $p > 0$ and $K^{}, p - 1 ⊧ ϕ_{1}$

$●^{-} ϕ_{1}$ $p > 0$ implies $K^{}, p - 1 ⊧ ϕ_{1}$

$□ ϕ_{1}$ $\forall k$ , $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{1}$

$□^{b} ϕ_{1}$ $\forall k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{1}$

$□^{-} ϕ_{1}$ $\forall k$ , $0 ⩽ k ⩽ p$ , $K^{}, k ⊧ ϕ_{1}$

$♢ ϕ_{1}$ $\exists k$ , $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{1}$

$♢^{b} ϕ_{1}$ $\exists k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{1}$

$♢^{-} ϕ_{1}$ $\exists k$ , $0 ⩽ k ⩽ p$ , $K^{}, k ⊧ ϕ_{1}$

$ϕ_{1} U ϕ_{2}$ $\exists k$ , $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{2}$

and $\forall j$ , $p ⩽ j < k, K^{}, j ⊧ ϕ_{1}$

$ϕ_{1} U^{b} ϕ_{2}$ $\exists k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K^{}, j ⊧ ϕ_{1}$

$ϕ_{1} S ϕ_{2}$ $\exists k$ , $0 ⩽ k ⩽ p$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $k < j ⩽ p, K^{}, j ⊧ ϕ_{1}$

Let $K^{}$ be the following TKB: $\begin{array}{l} K^{} = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} \cup (A_{n + 1}) ⟩ where \\ \begin{matrix} A_{n + 1} = & {A (a) ∣ A \in N_{R C}, A (a) \in \tilde{A}} \\ \cup {R (a, b) ∣ R \in N_{R R}, R (a, b) \in \tilde{A}} . \end{matrix} \end{array}$
Proposition 7.7.
If $L$ has the canonical model property for BCQ entailment, the relations in Table 2 hold for any $L$ -TKB $K$ .
Proof.
It is easy to see that $J_{K^{}} = J_{K}$ holds by construction. We obtain that $K, p ⊧ ϕ$ iff $K^{}, p ⊧ ϕ$ for every BTCQ without negation ϕ.

All relations in Table 2 but those for the operators □, ♢ and $U$ are straightforwardly obtained by applying the definitions of BTCQ satisfaction of Table 1 to this canonical model. To show the three remaining relations, we rely on the fact that $J_{K^{}}$ is such that for every $i > n$ , $I_{i} = I_{n + 1}$ , and there are no past operators nested under unbounded future operators by definition of TCQs. Indeed, if a BTCQ $ϕ_{1}$ does not contain any past operators and $i > n$ , $J_{K^{}}, i ⊧ ϕ_{1}$ iff $J_{K^{}}, n + 1 ⊧ ϕ_{1}$ . Hence we can show the following, from which the relations from Table 2 then follow straightforwardly.
$K^{}, p ⊧ □ ϕ_{1}$ iff for every $k ⩾ p$ , $K^{}, k ⊧ ϕ_{1}$ . Hence $K^{}, p ⊧ □ ϕ_{1}$ iff $\forall k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{1}$ and $K^{}, n + 1 ⊧ ϕ_{1}$ .

$K^{}, p ⊧ ♢ ϕ_{1}$ iff there exists $k ⩾ p$ , $K^{}, k ⊧ ϕ_{1}$ . Hence $K^{}, p ⊧ ♢ ϕ_{1}$ iff $\exists k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{1}$ or $K^{}, n + 1 ⊧ ϕ_{1}$ .

$K^{}, p ⊧ ϕ_{1} U ϕ_{2}$ iff $\exists k ⩾ p$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K^{}, j ⊧ ϕ_{1}$ . Hence $K^{}, p ⊧ ϕ_{1} U ϕ_{2}$ iff $\exists k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K^{}, j ⊧ ϕ_{1}$ , or $K^{}, n + 1 ⊧ ϕ_{2}$ and $\forall j$ , $p ⩽ j < n + 1, K^{}, j ⊧ ϕ_{1}$ .
□

In the next theorem, we transfer complexity upper bounds from the atemporal case to the temporal case, even with rigid predicates, for queries without negation and DLs that have the canonical model property for BCQ entailment. We consider DLs for which BCQ entailment is in P w.r.t. KB complexity and in NP w.r.t. combined complexity, such as ${DL-Lite}_{R}$ and ${EL}_{⊥}$ .
Theorem 7.8.
If $L$ has the canonical model property for BCQ entailment and is such that BCQ entailment from KBs is in* P w.r.t. KB complexity, respectively in NP w.r.t. combined complexity, then the entailment of BTCQs without negation from $L$ -TKBs is in P w.r.t. KB complexity, respectively in NP w.r.t. combined complexity.
Proof.
By Lemma 7.2, it is possible to decide whether $K^{}, p ⊧ q$ in P w.r.t. KB complexity for any BCQ q. Based on this, we can show by induction on the structure of ϕ that $K^{}, p ⊧ ϕ$ can be decided in P w.r.t. KB complexity. Assume that for two BTCQs $ϕ_{1}, ϕ_{2}$ and any $p ⩾ 0$ , it is possible to decide in P whether $K^{}, p ⊧ ϕ_{i}$ . Using the relations in Table 2, we can prove the following.
$K^{}, p ⊧ ϕ_{1} \land ϕ_{2}$ iff $K^{}, p ⊧ ϕ_{1}$ and $K^{}, p ⊧ ϕ_{2}$ . Therefore, deciding whether $K^{}, p ⊧ ϕ_{1} \land ϕ_{2}$ can be done in P by checking that $K^{}, p ⊧ ϕ_{1}$ and $K^{}, p ⊧ ϕ_{2}$ .

$K^{}, p ⊧ ϕ_{1} \lor ϕ_{2}$ iff $K^{}, p ⊧ ϕ_{1}$ or $K^{}, p ⊧ ϕ_{2}$ . Therefore, deciding whether $K^{}, p ⊧ ϕ_{1} \lor ϕ_{2}$ can be done in P by deciding whether $K^{}, p ⊧ ϕ_{1}$ and $K^{}, p ⊧ ϕ_{2}$ and checking that at least one is true.

$K^{}, p ⊧ ◯ ϕ_{1}$ iff $K^{}, p + 1 ⊧ ϕ_{1}$ . Therefore, deciding whether $K^{}, p ⊧ ◯ ϕ_{1}$ can be done in P by checking whether $K^{}, p + 1 ⊧ ϕ_{1}$ .

$K^{}, p ⊧ ●^{b} ϕ_{1}$ iff $p < n$ implies $K^{}, p + 1 ⊧ ϕ_{1}$ . Therefore, deciding whether $K^{}, p ⊧ ●^{b} ϕ_{1}$ can be done in P by checking whether $p ⩾ n$ or $K^{}, p + 1 ⊧ ϕ_{1}$ .

We show in the same way that we can decide in P whether $K^{}, p ⊧ ◯^{-} ϕ_{1}$ and whether $K^{}, p ⊧ ●^{-} ϕ_{1}$ .

$K^{}, p ⊧ □ ϕ_{1}$ iff for every k, $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{1}$ . Therefore, deciding whether $K^{}, p ⊧ □ ϕ_{1}$ can be done in P by checking for each $p ⩽ k ⩽ n + 1$ that $K^{}, k ⊧ ϕ_{1}$ .

We show in the same way that we can decide in P whether $K^{}, p ⊧ □^{b} ϕ_{1}$ and whether $K^{}, p ⊧ □^{-} ϕ_{1}$ .

$K^{}, p ⊧ ♢ ϕ_{1}$ iff there exists k, $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{1}$ . Therefore, deciding whether $K^{}, p ⊧ ♢ ϕ_{1}$ can be done in P by deciding for each $p ⩽ k ⩽ n + 1$ whether $K^{}, k ⊧ ϕ_{1}$ , and checking that this is true for at least one k.

We show in the same way that we can decide in P whether $K^{}, p ⊧ ♢^{b} ϕ_{1}$ and whether $K^{}, p ⊧ ♢^{-} ϕ_{1}$ .

$K^{}, p ⊧ ϕ_{1} U ϕ_{2}$ iff there exists k, $p ⩽ k ⩽ n + 1$ , $K^{}, k ⊧ ϕ_{2}$ , and for every j, $p ⩽ j < k$ , $K^{}, j ⊧ ϕ_{1}$ . Therefore, deciding whether $K^{}, p ⊧ ϕ_{1} U ϕ_{2}$ can be done in P by deciding for each $p ⩽ k ⩽ n + 1$ whether $K^{}, k ⊧ ϕ_{1}$ and whether $K^{}, k ⊧ ϕ_{2}$ , and checking that the condition holds.

We show in the same way that we can decide in P whether $K^{}, p ⊧ ϕ_{1} U^{b} ϕ_{2}$ and whether $K^{}, p ⊧ ϕ_{1} S ϕ_{2}$ .
The number of subqueries in ϕ is linear w.r.t. the size of ϕ, and independent from the TKB size. It follows that the total number of polynomial checks is also polynomially bounded. Therefore, we obtain that for every BTCQ ϕ without negation, $K^{}, p ⊧ ϕ$ can be decided in P w.r.t. the size of $K^{}$ . Since $K, p ⊧ ϕ$ iff $K^{}, p ⊧ ϕ$ and the size of $K^{}$ is polynomial in the size of $K$ , deciding whether $K, p ⊧ ϕ$ is in P w.r.t. KB complexity.

For the NP membership of entailment of BTCQs without negation w.r.t. combined complexity, we describe how to guess a certificate that $K, p ⊧ ϕ$ that can be checked in P. This certificate consists of:
a sequence of functions ${(ν_{i})}_{0 ⩽ i ⩽ n + 1}$ that associate to each BCQ q of ϕ true or false, and

for each BCQ q of ϕ and time point $i \in [0, n + 1]$ such that $ν_{i} (q) = true$ : a certificate that ${\tilde{q}}_{i} = RenameNotRig (q, i)$ is entailed from $\tilde{K}$ .
There are polynomially many pairs of a time point and a BCQ, and the certificate that ${\tilde{q}}_{i}$ is entailed from $\tilde{K}$ can be checked in polynomial time, since BCQ entailment is in NP. Moreover, we can show that, since ϕ contains neither negation nor past operators nested under unbounded future operators, deciding whether the propositional abstraction of ϕ is satisfied by the sequence of truth assignments that assign the propositional abstraction of q to $ν_{i} (q)$ for every $i \in [0, n + 1]$ and to $ν_{n + 1} (q)$ for every $i > n + 1$ can be done in polynomial time w.r.t. the size of the query and the length of the sequence of ABoxes. Indeed, identify ϕ and the BCQs in ϕ with their propositional abstractions, and denote by $w = w^{0} w^{1} \dots w^{n} w^{n + 1} \dots$ the trace over $2^{BCQ (ϕ)}$ , where $BCQ (ϕ)$ denotes the set of BCQs of ϕ, such that $w^{i} = {q ∣ ν_{i} (q) = true}$ for $i ⩽ n + 1$ , and $w^{i} = w^{n + 1}$ for $i > n + 1$ . Since $w^{i} = w^{n + 1}$ , for $i > n + 1$ , we can show similar relations as those in Table 2 for the entailment of LTL formulas without past operators nested under unbounded future operators or negations from w. We can then use a similar induction as we used in the proof for the data complexity to show that $w, p ⊧ ϕ$ can be decided by checking which queries are in $w^{i}$ . For this, the number of queries to be tested is polynomial in n and the size of ϕ. □

As a consequence of Theorems 7.4 and 7.8, and since ${EL}_{⊥}$ and ${DL-Lite}_{R}$ have the canonical model property for BCQ entailment (cf. [41] for ${EL}_{⊥}$ , and [40] for ${DL-Lite}_{R}$ ), we obtain the following theorem.
Theorem 7.9.
For* ${DL-Lite}_{R}$ and ${EL}_{⊥}$ , entailment of BTCQs without negation is in P w.r.t. KB complexity and in NP w.r.t. combined complexity, even if $N_{R R} \neq \emptyset$ .

Besides these results for ${DL-Lite}_{R}$ and ${EL}_{⊥}$ , Theorems 7.4 and 7.8 hold for all Horn-DLs satisfying the complexity constraints in the precondition of Theorem 7.8. For instance, they also hold for ${DL-Lite}_{horn}^{N}$ [35].
8. Complexity of inconsistency-tolerant BTCQ entailment without negation in the query

ϕ	$K, p ⊧ ϕ$ iff $K^{*}, p ⊧ ϕ$ iff
$\exists \vec{y} . ψ (\vec{y})$	$K^{*}, p ⊧ \exists \vec{y} . ψ (\vec{y})$
$ϕ_{1} \land ϕ_{2}$	$K^{}, p ⊧ ϕ_{1}$ and $K^{}, p ⊧ ϕ_{2}$
$ϕ_{1} \lor ϕ_{2}$	$K^{}, p ⊧ ϕ_{1}$ or $K^{}, p ⊧ ϕ_{2}$
$◯ ϕ_{1}$	$K^{*}, p + 1 ⊧ ϕ_{1}$
$●^{b} ϕ_{1}$	$p < n$ implies $K^{*}, p + 1 ⊧ ϕ_{1}$
$◯^{-} ϕ_{1}$	$p > 0$ and $K^{*}, p - 1 ⊧ ϕ_{1}$
$●^{-} ϕ_{1}$	$p > 0$ implies $K^{*}, p - 1 ⊧ ϕ_{1}$
$□ ϕ_{1}$	$\forall k$ , $p ⩽ k ⩽ n + 1$ , $K^{*}, k ⊧ ϕ_{1}$
$□^{b} ϕ_{1}$	$\forall k$ , $p ⩽ k ⩽ n$ , $K^{*}, k ⊧ ϕ_{1}$
$□^{-} ϕ_{1}$	$\forall k$ , $0 ⩽ k ⩽ p$ , $K^{*}, k ⊧ ϕ_{1}$
$♢ ϕ_{1}$	$\exists k$ , $p ⩽ k ⩽ n + 1$ , $K^{*}, k ⊧ ϕ_{1}$
$♢^{b} ϕ_{1}$	$\exists k$ , $p ⩽ k ⩽ n$ , $K^{*}, k ⊧ ϕ_{1}$
$♢^{-} ϕ_{1}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $K^{*}, k ⊧ ϕ_{1}$
$ϕ_{1} U ϕ_{2}$	$\exists k$ , $p ⩽ k ⩽ n + 1$ , $K^{*}, k ⊧ ϕ_{2}$
	and $\forall j$ , $p ⩽ j < k, K^{*}, j ⊧ ϕ_{1}$
$ϕ_{1} U^{b} ϕ_{2}$	$\exists k$ , $p ⩽ k ⩽ n$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K^{}, j ⊧ ϕ_{1}$
$ϕ_{1} S ϕ_{2}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $K^{}, k ⊧ ϕ_{2}$ and $\forall j$ , $k < j ⩽ p, K^{}, j ⊧ ϕ_{1}$

The following proposition gives general complexity upper bounds for BTCQ entailment under the AR, IAR, and brave semantics. By Theorem 7.9, they hold in particular for $L = {EL}_{⊥}$ and $L = {DL-Lite}_{R}$ , provided no negation is used in the TCQs.

Proposition 8.1.
If $L$ is such that consistency checking of a $L$ -TKB is in P and BTCQ entailment from a $L$ -TKB is in P w.r.t. data complexity and in NP w.r.t. combined complexity, then BTCQ entailment from a $L$ -TKB
under AR semantics is in co NP w.r.t. data complexity and in $Π_{2}^{p}$ w.r.t. combined complexity;

under IAR semantics is in co NP w.r.t. data complexity and in $Δ_{2}^{p} [O (log n)]$ w.r.t. combined complexity;

under brave semantics is in NP w.r.t. data complexity and in NP w.r.t. combined complexity.

Proof.
The data complexities follow from the procedures described in Section 5: since verifying that a sequence of ABoxes is a repair as well as non-entailment and entailment of a BTCQ can be decided in polynomial time, $ARNonEntailment$ , $IARNonEntailment$ and $braveEntailment$ take non-deterministic polynomial time.

For the combined complexity of brave BTCQ entailment, a certificate that $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ$ can be guessed together with ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ , and verified in P.

For the combined complexity of IAR, we use the procedure $IAREntailment$ from Section 5 with an NP oracle to decide whether a timed assertion belongs to some minimal inconsistent subset in the first step, and to decide the entailment of ϕ in the last step. Since the oracle calls can be structured as a tree, this procedure gives membership in $Δ_{2}^{p} [O (log n)]$ [32]. □

For ${EL}_{⊥}$ , matching lower bounds for all semantics follow from the atemporal case [13,51].

For ${DL-Lite}_{R}$ , we can obtain matching lower bounds from the atemporal case for the combined complexity of all semantics as well as for the data complexity of the AR semantics [16,37]. Regarding IAR semantics, entailment of BTCQs with negations under IAR semantics is already in P (see Fig. 3), so this better upper bound applies. Finally, we show that for brave semantics and ${DL-Lite}_{R}$ , in the case where there are no rigid predicates, we can improve the NP upper bound of Fig. 3 to a P bound. Recall that the lower bound established by Proposition 6.10 for brave semantics with rigid predicates already applies to BTCQs without negations, which means that no improvement of our bounds is possible in the presence of rigid predicates. The only remaining case is entailment under brave semantics where $N_{R C} = N_{R R} = \emptyset$ .

We describe a method for brave entailment of BTCQ without negation when $N_{R C} = N_{R R} = \emptyset$ . Our procedure proceeds by type elimination over a set of tuples built from the query and that represent the TCQs that are entailed at each time point.

First, we define the structure on which the method operates. We consider the set $BCQ (ϕ)$ of leaves of ϕ, that is, the set of all BCQs in ϕ, and the set $F (ϕ)$ of subformulas of ϕ. In what follows, we identify the BCQs of $BCQ (ϕ)$ and the BTCQs of $F (ϕ)$ with their propositional abstractions as defined in Section 2: if we write that a KB or a TKB entails some elements of $BCQ (ϕ)$ or $F (ϕ)$ , we consider them as BCQs or BTCQs, and if we write that some elements of $BCQ (ϕ)$ or $F (ϕ)$ entail others, we consider the elements of $BCQ (ϕ)$ as propositional variables and those of $F (ϕ)$ as propositional LTL formulas built over these variables.
Definition 8.2.
A brave-justification structure J for the BTCQ without negation ϕ in the TKB $K$ is a set of tuples of the form $(i, L_{now}, F_{now}, F_{prev}, F_{next})$ , where $0 ⩽ i ⩽ n$ , $L_{now} \subseteq BCQ (ϕ)$ , $F_{now} \subseteq F (ϕ)$ , $F_{prev} \subseteq F (ϕ)$ , and $F_{next} \subseteq F (ϕ)$ .

Note that the size of a brave-justification structure for ϕ in $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ is linearly bounded in n and independent of the size of the ABoxes. A tuple $(i, L_{now}, F_{now}, F_{prev}, F_{next})$ is justified in J iff it fulfils all of the following conditions.
$⟨ T, A_{i} ⟩ ⊧_{brave} ⋀_{q \in L_{now}} q$ .

If $i > 0$ , there exists $(i - 1, L_{now}^{'}, F_{now}^{'}, F_{prev}^{'}, F_{next}^{'}) \in J$ such that $F_{prev} = F_{now}^{'}$ and $F_{now} = F_{next}^{'}$ .

If $i < n$ , there exists $(i + 1, L_{now}^{'}, F_{now}^{'}, F_{prev}^{'}, F_{next}^{'}) \in J$ such that $F_{next} = F_{now}^{'}$ and $F_{now} = F_{prev}^{'}$ .

For every $ψ \in BCQ (ϕ)$ , if $F_{now} ⊧ ψ$ , then $ψ \in L_{now}$ .

For every $ψ \in F (ϕ)$ , if $F_{now} ⊧ ψ$ , then $ψ \in F_{now}$ .

For every $ψ \in F (ϕ)$ , if $⋀_{q \in L_{now}} q \land ◯^{-} (⋀_{χ \in F_{prev}} χ) \land ◯ (⋀_{χ \in F_{next}} χ) ⊧ ψ$ , then $ψ \in F_{now}$ .

For every $ψ, ψ^{'} \in F (ϕ)$ :

if $ψ \lor ψ^{'} \in F_{now}$ , then either $ψ \in F_{now}$ or $ψ^{'} \in F_{now}$ ,

if $♢ ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $♢ ψ \in F_{next}$ ,

if $♢^{b} ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $♢^{b} ψ \in F_{next}$ ,

if $♢^{-} ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $♢^{-} ψ \in F_{prev}$ ,

if $ψ^{'} U ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $ψ^{'} \in F_{now}$ and $ψ^{'} U ψ \in F_{next}$ ,

if $ψ^{'} U^{b} ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $ψ^{'} \in F_{now}$ and $ψ^{'} U^{b} ψ \in F_{next}$ ,

if $ψ^{'} S ψ \in F_{now}$ , then either $ψ \in F_{now}$ or $ψ^{'} \in F_{now}$ and $ψ^{'} S ψ \in F_{prev}$ , and

if ψ is of the form $□ φ$ , then either $ψ \notin F_{now}$ or $⟨ \emptyset, {(\emptyset)}_{0 ⩽ i ⩽ n} ⟩, n + 1 ⊧ □ φ$ .

If $i = n$ , then

for all $ψ \in F (ϕ)$ that are of the form $●^{b} φ$ , $ψ \in F_{now}$ ,

for all $ψ \in F (ϕ)$ that are of the form $◯ φ$ and such that $⟨ \emptyset, {(\emptyset)}_{0 ⩽ i ⩽ n} ⟩, n + 1 ⊭ □ φ$ , we have $ψ \notin F_{now}$ ,

for all $ψ \in F (ϕ)$ that are of the form $♢^{b} φ, □^{b} φ,$ or $φ^{'} U^{b} φ$ , $ψ \in F_{now}$ iff $φ \in F_{now}$ ,

for all $ψ \in F (ϕ)$ that are of the form $♢ φ, φ^{'} U φ$ and such that $⟨ \emptyset, {(\emptyset)}_{0 ⩽ i ⩽ n} ⟩, n + 1 ⊭ □ φ$ , $ψ \in F_{now}$ iff $φ \in F_{now}$ .

If $i = 0$ , then

for all $ψ \in F (ϕ)$ that are of the form $●^{-} φ$ , $ψ \in F_{now}$ ,

for all $ψ \in F (ϕ)$ that are of the form $◯^{-} φ$ , $ψ \notin F_{now}$ , and

for all $ψ \in F (ϕ)$ that are of the form $♢^{-} φ$ , $□^{-} φ$ , $φ^{'} S φ$ , $ψ \in F_{now}$ iff $φ \in F_{now}$ .
We give the intuition behind the elements of the tuples that fulfil these conditions. The first element i is the time point we are considering, $L_{now}$ is a set of BCQs whose conjunction is entailed under brave semantics by $⟨ T, A_{i} ⟩$ (Condition 1), and $F_{now}$ is the set of formulas that can be entailed together with $L_{now}$ , depending on what is entailed in the previous and next time points, this information being stored in $F_{prev}$ and $F_{next}$ respectively (Condition 6). Conditions 2 and 3 ensure that there is a sequence of tuples representing every time point from 0 to n such that this information is coherent between consecutive tuples. Condition 4 expresses that $L_{now}$ is exactly the set of BCQs contained in $F_{now}$ and Condition 5 that $F_{now}$ is maximal in the sense that it contains its consequences. Condition 7 enforces that $F_{now}$ , $F_{prev}$ and $F_{next}$ respect the semantics of LTL operators and Conditions 8 and 9 enforce this semantics at both ends of the finite sequence. (Note that we use here the fact that past operators cannot be nested under unbounded future operators, and that no BCQ can be entailed under brave semantics after time point n in the absence of rigid predicates.)

Fig. 5.
Data [left] and combined [right] complexity of BTCQ entailment for BTCQs without negation. All results are tight but those preceded by “in” which are upper bounds. The complexities lower than in the case of BTCQs with negation are in bold.

A brave-justification structure J is correct if every tuple is justified, and ϕ is justified at time point p by J if there is $(p, L_{now}, F_{now}, F_{prev}, F_{next}) \in J$ such that $ϕ \in F_{now}$ . We show that ϕ is entailed from $K$ at time point p under brave semantics iff there is a correct brave-justification structure for ϕ in $K$ that justifies ϕ at time point p. The main idea of the proof is to link the tuples of a sequence ${((i, L_{now}, F_{now}, F_{prev}, F_{next}))}_{0 ⩽ i ⩽ n}$ to a consistent TKB $K^{'} = ⟨ T, {(C_{i})}_{0 ⩽ i ⩽ n} ⟩$ such that for every i, we have $C_{i} \subseteq A_{i}$ and $⟨ T, C_{i} ⟩ ⊧ ⋀_{q \in L_{now}} q$ . We show in the appendix that there is such a $K^{'}$ such that $K^{'}, p ⊧ ϕ$ iff there is such a sequence of tuples that is a correct brave-justification structure for ϕ in $K$ and justifies ϕ at time point p.

The data complexity of brave entailment of BTCQ without negation when there are no rigid predicates follows from the characterization of brave BTCQ entailment with brave-justification structures.
Proposition 8.3.
For ${DL-Lite}_{R}$ , if $N_{R C} = N_{R R} = \emptyset$ , then entailment of BTCQs without negation under brave semantics is in P w.r.t. data complexity.
Proof.
We describe a polynomial procedure that decides the existence of a brave-justification structure for ϕ in $K$ that justifies ϕ at time point p. We start with a brave-justification structure J for ϕ in $K$ that contains all possible tuples. Note that the size of this initial structure J is linearly bounded in the number n of ABoxes, and otherwise independent of the data size. The reason is that, except for the time point, the elements of each justification tuple, namely the sets $L_{now}$ , $F_{now}$ , $F_{prev}$ and $F_{next}$ , only depend on the query.

From the initial, maximal, brave-justification structure, we remove the unjustified tuples one after the other as follows. (i) Remove every tuple that does not satisfy Conditions 1, 4, 5, 6, 7, 8 or 9, and (ii) repeat the following steps until a fix-point has been reached: iterate over the tuples from time point 0 to n, eliminating those which do not satisfy Condition 3, and then iterate from n to 0 eliminating those which do not satisfy Condition 2. For the resulting brave-justification structure, we check whether it contains a tuple $(p, L_{now}, F_{now}, F_{prev}, F_{next})$ such that $ϕ \in F_{now}$ . If yes, we return “entailed at time point p”, otherwise, we return “not entailed at time point p”. Since the size of J is linear in n, this process requires at most quadratically many steps. The verification that a given tuple is justified requires polynomial time w.r.t. data complexity (the verification of Condition 3 and Condition 2 is linear in n, and only the brave entailment of a BCQ from a ${DL-Lite}_{R}$ -KB for Condition 1 depends on the size of the ABox, which can be performed in ${AC}^{0}$ w.r.t. data complexity). Therefore, the complete procedure runs in polynomial time w.r.t. data complexity. □

Note that it is vital for this procedure that the BTCQ does not contain negation, as this allows to fully focus on the positive entailments of BCQs. In contrast, BTCQs with negation may require a case analysis over query entailments, as exemplified by the tautological BTCQ $□ (A (a) \lor \neg A (a))$ .

The following theorem summarizes the complexity results for the case without negation in the TCQ.
Theorem 8.4.
The results in Fig. 5 hold.
9. Toward practical algorithms

Until now, work on TCQ answering has primarily focused on complexity analysis for different DL languages [6,7,19]. Attempts towards practical algorithms or implementations are as of now scarce [17,27]. The only attempt toward more practical algorithms close to our scenario that we are aware of has been made for ${DL-Lite}_{R}$ and TCQs without negation in [17], and partially implemented [53]. Some of the results have then been generalized in [18] to query languages that are rewritable in the atemporal case. In this section, we mainly focus on ${DL-Lite}_{R}$ -TKBs and TCQs without negation, building on this previous work. However, some of our results also apply to other DLs and we discuss the case of ${EL}_{⊥}$ .

Three different algorithms for answering TCQs without negation over ${DL-Lite}_{R}$ -TKBs without rigid predicates are provided in [17,18]. The first algorithm rewrites the TCQ into a query in ATSQL [28], an SQL variant for temporal databases. The second algorithm first rewrites the TCQ into an equivalent TCQ that does not contain future operators, and then iteratively computes the answers for each time point. The third algorithm computes the answers of the TCQ iteratively as well, but does not eliminate the future operators beforehand. For this, it uses a data structure called answer formulas, which represents the TCQs in which some parts have already been evaluated. This structure contains sets of already computed answers to subqueries, as well as variables that serve as place-holders for subqueries that have to be evaluated at the next time point.

Our first contribution is a method for handling rigid predicates (both concepts and roles) in polynomial time for TCQ answering over ${DL-Lite}_{R}$ -TKBs under the classical semantics. Indeed, [17,18] consider only rigid concepts (but not rigid roles) for which they provide a method that is restricted to TCQs that are rooted, i.e., in which each CQ contains an individual or an answer variable that is connected to all the other terms through roles. As a second contribution, we show that in the absence of rigid predicates, it is sometimes possible to combine the algorithms for inconsistency-tolerant query answering in the atemporal case with algorithms for temporal query answering in the consistent case in order to perform inconsistency-tolerant temporal query answering.

9.1. TCQ answering under classical semantics with rigid predicates for ${DL-Lite}_{R}$ and TCQs without negation or unbounded future operators

In this section, we show how TCQ answering with rigid predicates can be reduced to TCQ answering without rigid predicates, enabling us to use the algorithms that have been proposed for this latter case. Throughout the section, $K$ is a ${DL-Lite}_{R}$ -TKB and ϕ a TCQ without negation and unbounded future operators ( $◯$ , □, ♢, $U$ ). This restriction amounts to using the setting of [17,18] in which the semantics is defined w.r.t. finite sequences of interpretations, and is necessary to reduce TCQ answering with rigid predicates to TCQ answering without rigid predicates. Indeed, consider for instance the query $□ A (a)$ . Such a query can be entailed with rigid predicates, e.g., if A is rigid, but not without rigid predicates since for $p > n$ , the interpretation of every predicate is empty in the pth component of the canonical model of a TKB without rigid predicates.

To the best of our knowledge, the only algorithm that has been proposed for TCQ answering with rigid predicates and aims at practicality is described as well in [17,18], and deals only with rigid concepts and rooted TCQs. We briefly describe this algorithm, which aims at handling streaming data by computing the answers to the query at the last available time point. The key idea is to check all sets of potentially rigid concept assertions and test their compatibility with each of the ABoxes from the sequence together with the TBox. Unfortunately, the original algorithm omits the test whether the checked set of rigid concept assertions covers also the rigid information from the tested ABox together with the TBox. As we found this small flaw in the original algorithm, we present here a mended variant.

In the following, let $N_{C}^{K}$ , $N_{R}^{K}$ , $N_{R C}^{K}$ , $N_{R R}^{K}$ , and $N_{I}^{K}$ denote respectively the sets of concepts, roles, rigid concepts, rigid roles, and individuals that occur in the TKB $K$ . The algorithm first constructs every possible set $R$ of assertions built from the rigid concepts and individuals in the TKB $K$ . Note that there are $2^{| N_{R C}^{K} | * | N_{I}^{K} |}$ such sets. It then runs, in parallel, for each such set $R$ an instance of the algorithm for TCQ answering without rigid predicates on the TKB that is obtained by adding the assertions in $R$ to every ABox of the TKB. For each time point i, it takes into account the new dataset available by eliminating the incompatible instances, i.e., those for which

$⟨ T, A_{i} \cup R ⟩$ is inconsistent, or

a rigid concept assertion entailed by $⟨ T, A_{i} ⟩$ does not belong to $R$ .1

¹
This condition is new and added after consultation with the authors of [17,18].

The answers at time point i are then obtained by taking the intersection of the answers returned by all active instances.

We follow a similar idea in the sense that we also add assertions to the TKB that propagate the effects of the rigid predicates. We show that this way, for ${DL-Lite}_{R}$ , TCQ answering with rigid predicates can be reduced to TCQ answering without rigid predicates in polynomial time.

In order to show that TCQ answering with rigid predicates can be reduced to TCQ answering without, we construct in polynomial time a set $R$ of assertions that captures all information about rigid concepts and roles that is relevant for consistency checking and TCQ answering. Then, TCQ answering over $K$ with $N_{R C} \neq \emptyset$ , $N_{R R} \neq \emptyset$ can be performed by TCQ answering over $⟨ T, {(A_{i} \cup R)}_{0 ⩽ i ⩽ n} ⟩$ with $N_{R C} = N_{R R} = \emptyset$ . Without any restriction on the TBox, $R$ may be infinite, as illustrated in the following example.

Example 9.1.

Consider the TKB $K$ with the TBox $T = {\exists R^{-} ⊑ \exists R, R ⊑ S}$ , where S is rigid, and the ABox sequence consisting of $A_{0} = {R (a, b)}$ , and $A_{i} = \emptyset$ for $i \in [1, n]$ .

Every model of $K$ that respects rigid predicates satisfies $ϕ = \exists x_{1} \dots x_{k + 1} . S (x_{1}, x_{2}) \land \dots \land S (x_{k}, x_{k + 1})$ for every $k > 0$ and at every time point. Since with $N_{R C} = N_{R R} = \emptyset$ , $K$ entails such a query only at time point 0, $R$ should be such that $⟨ T, R ⟩$ entails such a query, so that $⟨ T, {(A_{i} \cup R)}_{0 ⩽ i ⩽ n} ⟩$ entails it at every time point. Moreover, there exist models of $K$ that respect rigid predicates and for which neither $\exists x_{1} \dots x_{k} . S (x_{1}, x_{2}) \land \dots \land S (x_{k}, x_{1})$ nor $\exists x y . R (x, y)$ hold at any time point $i > 0$ . Therefore, $R$ cannot contain cycles of S, nor R-assertions. Consequently, $R$ has to contain an infinite chain of S-assertions.

This problem motivates us to disallow rigid roles that have non-rigid sub-roles. In other words, we restrict ourselves in the following to TBoxes $T$ that entail no role inclusions of the form $P_{1} ⊑ P_{2}$ with $P_{1} : = R_{1} | R_{1}^{-}$ , $R_{1} \in N_{R} ∖ N_{R R}$ and $P_{2} : = R_{2} | R_{2}^{-}$ , $R_{2} \in N_{R R}$ . This condition avoids chains of rigid roles in the anonymous part of the canonical model $J_{K}$ that cannot be entailed by a single rigid assertion. In the example above, if rigid roles are only allowed to have rigid sub-roles, then R has to be rigid. In this case, adding the single assertion $R (x, y)$ to every $A_{i}$ is sufficient for $\exists x_{1} \dots x_{k + 1} . R (x_{1}, x_{2}) \land \dots \land R (x_{k}, x_{k + 1})$ to be entailed at every time point and for every $k > 0$ .

As a first step, we explicitly construct the canonical model $J_{K}$ of the ${DL-Lite}_{R}$ -TKB $K$ . This model will be used to prove that $K$ with $N_{R C} \neq \emptyset$ , $N_{R R} \neq \emptyset$ and $⟨ T, {(A_{i} \cup R)}_{0 ⩽ i ⩽ n} ⟩$ with $N_{R C} = N_{R R} = \emptyset$ entail the same BTCQs that do not have negation or unbounded future operators.

We build a sequence of (possibly infinite) ABoxes ${({chase}_{rig}^{K} (A_{i}))}_{0 ⩽ i ⩽ n + 1}$ similar to the chase presented in [25] for KBs. Let $S$ be a set of ${DL-Lite}_{R}$ assertions. We say a positive inclusion (PI) α is applicable in $S$ to an assertion $β \in S$ if one of the following conditions is satisfied:

$α = A_{1} ⊑ A_{2}$ , $β = A_{1} (a)$ and $A_{2} (a) \notin S$ ,

$α = A ⊑ \exists P$ , $β = A (a)$ and there exists no b such that $P (a, b) \in S$ ,

$α = \exists P ⊑ A$ , $β = P (a, b)$ and $A (a) \notin S$ ,

$α = \exists P_{1} ⊑ \exists P_{2}$ , $β = P_{1} (a_{1}, a_{2})$ and there exists no b such that $P_{2} (a_{1}, b) \in S$ , or

$α = P_{1} ⊑ P_{2}$ , $β = P_{1} (a_{1}, a_{2})$ , and $P_{2} (a_{1}, a_{2}) \notin S$ .

A PI α is applied to an assertion β by adding a new assertion $β_{new}$ to $S$ such that α is not applicable to β in $S \cup {β_{new}}$ anymore.

Definition 9.2 (Rigid chase of a TKB).

Let $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ be a ${DL-Lite}_{R}$ -TKB. Let ${(A_{i}^{'})}_{0 ⩽ i ⩽ n + 1}$ be such that $A_{i}^{'} = A_{i} \cup {β ∣ \exists k, β \in A_{k} and β is rigid}$ for $i \in [0, n]$ and $A_{n + 1}^{'} = \emptyset$ . Finally, let $T_{p}$ be the set of positive inclusions in $T$ , and $N_{i}$ be the number of assertions in $A_{i}^{'}$ . Assume that the assertions in each $A_{i}^{'}$ are enumerated from $N_{1} + \dots + N_{i - 1} + 1$ to $N_{1} + \dots + N_{i}$ following their lexicographic order. Consider the sequences of sets $S^{j} = {(S_{i}^{j})}_{0 ⩽ i ⩽ n + 1}$ of assertions defined by $\begin{array}{l} S^{0} = {(A_{i}^{'})}_{0 ⩽ i ⩽ n + 1} \\ S^{j + 1} = S^{j} \cup S^{new} = {(S_{i}^{j} \cup S_{i}^{new})}_{0 ⩽ i ⩽ n + 1}, \end{array}$ where $S^{new}$ is defined in terms of the assertion $β_{new}$ obtained as follows: let $β \in S_{i_{β}}^{j}$ be the first assertion in $S^{j}$ such that there exists a PI in $T_{p}$ applicable in $S_{i_{β}}^{j}$ to β and let α be the lexicographically first PI applicable in $S_{i_{β}}^{j}$ to β. $β_{new}$ is then defined based on the syntactictal form of α and β. Specifically,

if $α = A_{1} ⊑ A_{2}$ and $β = A_{1} (a)$ , then $β_{new} = A_{2} (a)$ ,

if $α = A ⊑ \exists P$ and $β = A (a)$ , then $β_{new} = P (a, a_{new})$ ,

if $α = \exists P ⊑ A$ and $β = P (a, b)$ , then $β_{new} = A (a)$ ,

if $α = \exists P_{1} ⊑ \exists P$ and $β = P_{1} (a, b)$ , then $β_{new} = P (a, a_{new})$ , and

if $α = P_{1} ⊑ P_{2}$ and $β = P_{1} (a_{1}, a_{2})$ , then $β_{new} = P_{2} (a_{1}, a_{2})$ ,

where

a_{new}

is constructed from α and β as follows:

if $a \in N_{I}^{K},$ then $a_{new} = x_{a P}^{i_{β}}$ , and

otherwise $a \notin N_{I}^{K}$ , then a is of the form $x_{a^{'} P_{1} \dots P_{l}}^{i_{1} \dots i_{l}}$ and we define $a_{new} = x_{a^{'} P_{1} \dots P_{l} P}^{i_{1} \dots i_{l} i_{β}}$ .

β_{new}

is rigid, then

S^{new} = {({β_{new}})}_{0 ⩽ i ⩽ n + 1}

, otherwise,

S^{new} = {(S_{i}^{new})}_{0 ⩽ i ⩽ n + 1}

with

S_{i_{β}}^{new} = {β_{new}}

and

S_{i}^{new} = \emptyset

for

i \neq i_{β}

Let N be the total number of assertions in $S^{j}$ . The assertion(s) added are numbered as follows: if $β_{new}$ is not rigid, $β_{new}$ is numbered by $N + 1$ , otherwise for every $i \in [0, n + 1]$ , the assertion $β_{new} \in S_{i}^{new}$ added to $S_{i}^{j}$ is numbered by $N + 1 + i$ .

We call the rigid chase of the TKB $K$ , denoted by ${chase}_{rig} (K) = {({chase}_{rig}^{K} (A_{i}))}_{0 ⩽ i ⩽ n + 1}$ , the sequence of sets of assertions obtained as the infinite union of all $S^{j}$ , i.e., $\begin{matrix} {({chase}_{rig}^{K} (A_{i}))}_{0 ⩽ i ⩽ n + 1} = {(⋃_{j \in N} S_{i}^{j})}_{0 ⩽ i ⩽ n + 1} . \end{matrix}$

Based on the rigid chase of $K$ , we construct the sequence of interpretations $J_{K} = {(I_{i})}_{i ⩾ 0}$ , where $I_{i} = ⟨ Δ, \cdot^{I_{i}} ⟩$ is defined as follows.

$Δ = N_{I}^{K} \cup Γ_{N}$ , where $Γ_{N}$ is the set of individuals that appear in ${chase}_{rig} (K)$ and not in $K$ .

For every $a \in Δ$ , $a^{I_{i}} = a$ .

For every $A \in N_{C}$ , $A^{I_{i}} = {a ∣ A (a) \in {chase}_{rig}^{K} (A_{i})}$ if $i ⩽ n$ , $A^{I_{i}} = {a ∣ A (a) \in {chase}_{rig}^{K} (A_{n + 1})}$ if $i > n$ .

For every $R \in N_{R}$ , $R^{I_{i}} = {(a, b) ∣ R (a, b) \in {chase}_{rig}^{K} (A_{i})}$ if $i ⩽ n$ , $R^{I_{i}} = {(a, b) ∣ R (a, b) \in {chase}_{rig}^{K} (A_{n + 1})}$ if $i > n$ .

We show that

J_{K}

is a model of

K

that respects rigid predicates, and that for any BTCQ without negation ϕ such that

N_{I}^{ϕ} \subseteq N_{I}^{K}

K, p ⊧ ϕ

iff

J_{K}, p ⊧ ϕ

Lemma 9.3.
If $K$ is consistent, then $J_{K}$ is a model of $K$ that respects rigid predicates.
Proof (Sketch).
Since for every $i \in [0, n]$ , $A_{i} \subseteq {chase}_{rig}^{K} (A_{i})$ , we directly obtain $I_{i} ⊧ A_{i}$ . We can show that for every i, $I_{i}$ further satisfies every PI in $T$ with similar arguments as those used in [25]. Indeed, every PI applicable to an assertion β in $S_{i}^{j}$ at step j of the construction of the rigid chase becomes not applicable to β in $S_{i}^{k}$ for some $k ⩾ j$ , because there are neither infinitely many assertions before β, nor infinitely many PIs applied to some assertion that precedes β. Finally, we show that $I_{i}$ satisfies every negative inclusion of $T$ because otherwise $K$ would be inconsistent. Moreover, the model $J_{K}$ respects rigid predicates because, if an assertion β of ${chase}_{rig}^{K} (A_{i})$ is rigid, either $β \in A_{i}$ and by construction $β \in S_{k}^{0} = A_{k}^{'}$ for every k, or β has been derived at some step j by applying some PI to an assertion of $S^{j}$ and $β \in S_{k}^{j + 1}$ for every k. We obtain that in both cases, $β \in {chase}_{rig}^{K} (A_{k})$ for every k. □

Next, we show that $J_{K}$ is the canonical model of $K$ for entailment of BTCQ without negation.
Lemma 9.4.
If $K$ is consistent, then for every BTCQ without negation ϕ such that $N_{I}^{ϕ} \subseteq N_{I}^{K}$ , $K, p ⊧ ϕ$ iff $J_{K}, p ⊧ ϕ$ .
Proof (Sketch).
Since $J_{K} = {(I_{i})}_{i ⩾ 0}$ with $I_{i} = ⟨ Δ, \cdot^{I_{i}} ⟩$ is a model of $K$ that respects rigid predicates, the first direction is straightforward, and we only need to show that $J_{K}, p ⊧ ϕ$ implies $K, p ⊧ ϕ$ . Let $J = {(I_{i}^{'})}_{i ⩾ 0}$ with $I_{i}^{'} = ⟨ Δ^{'}, \cdot^{I_{i}^{'}} ⟩$ be a model of $K$ that respects rigid predicates. We show by structural induction on ϕ that if $J_{K}, p ⊧ ϕ$ , then $J, p ⊧ ϕ$ . For the case where ϕ is a CQ $\exists \vec{y} . ψ (\vec{y})$ , we show that if there exists a homomorphism π of $\exists \vec{y} . ψ (\vec{y})$ into $I_{p}$ , then $I_{p}^{'} ⊧ \exists \vec{y} . ψ (\vec{y})$ , by defining a homomorphism h from Δ into $Δ^{'}$ . □

We are now ready to introduce the set $R$ that, if added to every ABox of the TKB, allows us to reduce TCQ answering with rigid predicates to TCQ answering without.
Proposition 9.5.
Let $R$ be as defined in Fig. 6 . Then, $R$ is computable in polynomial time and such that
Fig. 6.
Set of rigid assertions added to every ABox of $K$ .

$K$ is consistent iff $K_{R} = ⟨ T, {(A_{i} \cup R)}_{0 ⩽ i ⩽ n} ⟩$ is consistent with $N_{R C} = N_{R R} = \emptyset$ , and

for any BTCQ ϕ without negation and unbounded future operators and such that $N_{I}^{ϕ} \subseteq N_{I}^{K}$ , $K, p ⊧ ϕ$ iff $K_{R}, p ⊧ ϕ$ with $N_{R C} = N_{R R} = \emptyset$ .

The size of $R$ is polynomial in the size of $N_{C}^{K}, N_{R}^{K}$ , and $N_{I}^{K}$ , and since query answering as well as subsumption checking are in P, $R$ can be computed in polynomial time. The first three parts of $R$ contain information about the participation of individuals of $N_{I}^{K}$ in rigid predicates. The last two witness the participation in rigid predicates of the role-successors w.r.t. non-rigid roles, and thus take into account also anonymous individuals that are created in ${chase}_{rig} (K)$ when applying PIs whose right-hand side is an existential restriction of a non-rigid role. The individuals created in ${chase}_{rig} (K)$ when applying such a PI with a rigid role are witnessed by the individuals $x_{a P}$ or $x_{P_{1} P_{2}}$ if they do not follow from a rigid role assertion, and do not need to be witnessed otherwise, since the assertion $P_{2} (x_{P_{1}}, x_{P_{1} P_{2}})$ is sufficient to trigger the generation of the whole anonymous part implied by the fact that $x_{P_{1} P_{2}}$ is in the range of $P_{2}$ .

We split the proof of Proposition 9.5 into several lemmas.
Lemma 9.6.
$K$ is consistent iff $K_{R}$ is consistent with $N_{R C} = N_{R R} = \emptyset$ .
Proof.
By Proposition 3.5, $K_{R}$ is consistent with $N_{R C} = N_{R R} = \emptyset$ iff each $⟨ T, A_{i} \cup R ⟩$ is consistent. We show that also $K$ is consistent iff each $⟨ T, A_{i} \cup R ⟩$ is consistent.

For the case where $K$ is not consistent, let $B$ be a minimal inconsistent subset of $K$ . Recall that by Fact 6.11, $B$ contains at most 2 assertions. Then $B$ is either internal to some $A_{i}$ , or is of the form $B = {(α, i), (β, j)}$ with $i \neq j$ . In the former case, $⟨ T, A_{i} \cup R ⟩$ is clearly inconsistent. In the latter case, ${α, β}$ violates some negative inclusion in the closure of the TBox that involves at least a rigid concept A or a rigid role R by assigning an individual a (or two individuals $a, b$ ) to two disjoint concepts (or roles). We can then assume w.l.o.g. that we are in one of the following cases: (i) $⟨ T, α ⟩ ⊧ A (a)$ , (ii) $⟨ T, α ⟩ ⊧ \exists x . R (a, x)$ , (iii) $⟨ T, α ⟩ ⊧ \exists x . R (x, a)$ , or (iv) $⟨ T, α ⟩ ⊧ R (a, b)$ . It follows that respectively (i) $⟨ T, A_{i} ⟩ ⊧ A (a)$ , (ii) $⟨ T, A_{i} ⟩ ⊧ \exists x . R (a, x)$ , (iii) $⟨ T, A_{i} ⟩ ⊧ \exists x . R (x, a)$ , or (iv) $⟨ T, A_{i} ⟩ ⊧ R (a, b)$ . By construction of $R$ , we then conclude that (i) $A (a) \in R$ , (ii) $R (a, x_{a R}) \in R$ , (iii) $R (x_{a R^{-}}, a) \in R$ , or (iv) $R (a, b) \in R$ respectively, and therefore that $⟨ T, A_{j} \cup R ⟩$ is inconsistent.

For the other direction, assume there exists $i \in [0, n]$ , such that $⟨ T, A_{i} \cup R ⟩$ is inconsistent, and let $B$ be a minimal inconsistent subset of $⟨ T, A_{i} \cup R ⟩$ . If $B$ is internal to $A_{i}$ , $K$ is clearly inconsistent. Otherwise, $B$ is of the form ${α, β}$ and involves at least one assertion from $R$ . The assertions α and β assign an individual x to two disjoint concepts $C_{1}, C_{2}$ , or a pair of individuals $x, y$ to two disjoint roles $R_{1}, R_{2}$ . We distinguish three cases.
In the case where $x = x_{a P}$ (resp. $x = x_{P_{1} P_{2}}$ ), since $P (a, x_{a P})$ (resp. $P_{2} (x_{P_{1}}, x_{P_{1} P_{2}})$ ) is the only assertion of $R$ that contains x, we obtain that $⟨ T, {P (a, x_{a P})} ⟩$ (resp. $⟨ T, {P_{2} (x_{P_{1}}, x_{P_{1} P_{2}})} ⟩$ ) is inconsistent, which implies that P (resp. $P_{2}$ ) is unsatisfiable, i.e., has an empty interpretation in every model of $T$ . Since there exists j such that $⟨ T, A_{j} ⟩ ⊧ \exists x . P (a, x)$ (resp. $⟨ T, A_{j} ⟩ ⊧ \exists x y . P_{1} (x, y)$ and $T ⊧ \exists P_{1}^{-} ⊑ \exists P_{2}$ ), it follows that $A_{j}$ is inconsistent.

In the case where $x = x_{P_{1}}$ , since $x_{P_{1}}$ appears only in concepts that subsume $\exists P_{1}^{-}$ , the fact that x is assigned to two disjoint concepts implies that $\exists P_{1}^{-}$ is unsatisfiable. Thus, and since there exists j such that $⟨ T, A_{j} ⟩ ⊧ \exists x y . P_{1} (x, y)$ , $A_{j}$ is inconsistent.

Finally, in the case where $x \in N_{I}^{K}$ , since α or β is in $R$ , at least one of $C_{1}, C_{2}$ (or $R_{1}, R_{2}$ ) is rigid. As the case where some ABox $A_{j}$ is inconsistent is trivial, we assume every $A_{j}$ to be consistent. If $α \notin A_{i}$ , let $c_{α} \in A_{j_{α}}$ be an assertion responsible for the entailment that triggered the addition of α to $R$ , and otherwise let $(c_{α}, j_{α}) = (α, i)$ . If $β \notin A_{i}$ , let $c_{β} \in A_{j_{β}}$ be an assertion responsible for the entailment that triggered the addition of β to $R$ , and otherwise $(c_{β}, j_{β}) = (β, i)$ . Then ${(c_{α}, j_{α}), (c_{β}, j_{β})}$ is inconsistent because $c_{α}$ and $c_{β}$ lead to a (or $a, b$ ) being assigned to two disjoint concepts (or disjoint roles) such that at least one of them is rigid. As a result, $K$ is inconsistent as well.
We obtain that in every case, if $K_{R}$ is inconsistent with $N_{R C} = N_{R R} = \emptyset$ , then $K$ is inconsistent with rigid predicates. □

We now assume that $K$ and $K_{R}$ are consistent. Note that if this is not the case, they both trivially entail any BTCQ. The following two lemmas show that if a Boolean conjunctive query $q = \exists \vec{y} . ψ (\vec{y})$ is such that $N_{I}^{q} \subseteq N_{I}^{K}$ , then for every $p \in [0, n]$ , $K_{R}, p ⊧ q$ iff $K, p ⊧ q$ .
Lemma 9.7.
Let $q = \exists \vec{y} . ψ (\vec{y})$ be such that $N_{I}^{q} \subseteq N_{I}^{K}$ . Then, for every $p \in [0, n]$ , if $K_{R}, p ⊧ q$ then $K, p ⊧ q$ .
Proof (Sketch).
By Lemma 9.4, it suffices to focus on the canonical model $J_{K} = {(I_{i})}_{i ⩾ 0}$ for testing entailments of $K$ . The lemma can be shown by defining a homomorphism from the canonical model of $⟨ T, A_{p} \cup R ⟩$ into $I_{p}$ , the pth component of $J_{K}$ . □
Lemma 9.8.
Let $q = \exists \vec{y} . ψ (\vec{y})$ be such that $N_{I}^{q} \subseteq N_{I}^{K}$ . For every $p \in [0, n]$ , if $K, p ⊧ q$ then $K_{R}, p ⊧ q$ .
Proof (Sketch).
Again, we make use of Lemma 9.4 and use the canonical model $J_{K} = {(I_{i})}_{i ⩾ 0}$ . The lemma can then be shown by considering some model $I_{p}^{R}$ of $⟨ T, A_{p} \cup R ⟩$ , and defining a homomorphism of $I_{p}$ into $I_{p}^{R}$ . □

Since by Lemmas 9.7 and 9.8, $K$ and $K_{R}$ with $N_{R C} = N_{R R} = \emptyset$ coincide on the entailment of BCQs for every time point $p \in [0, n]$ , we can show as in Proposition 7.6 that they coincide on entailment of BTCQs without negation nor unbounded future operators.
Lemma 9.9.
Let ϕ be a BTCQ with no negation or unbounded future operators such that $N_{I}^{ϕ} \subseteq N_{I}^{K}$ . Then, $K, p ⊧ ϕ$ iff $K_{R}, p ⊧ ϕ$ with $N_{R C} = N_{R R} = \emptyset$ .

It follows that TCQs can be answered in $K$ with rigid predicates by answering TCQs in $K_{R}$ without rigid predicates and pruning answers that contain individual names not in $N_{I}^{K}$ . Note that every model of $K_{R}$ is a model of $K$ , but does not respect rigid predicates in general. We can reduce BTCQ entailment over $K$ with rigid predicates to BTCQ entailment over $K_{R}$ without rigid predicates only because our TCQs do not allow LTL operators to be nested in existential quantifications. This prevents existentially quantified variables to link different time points. To see this, consider the query $\exists x y . □^{b} (R (a, x) \land R (x, y))$ and the TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ with $T = {B ⊑ \exists R, \exists R^{-} ⊑ \exists R}$ , $R \in N_{R R}$ and $A_{i} = {B (a)}$ . For this TKB, we would have $R = {R (a, x_{a R})}$ , and therefore $x_{a R}$ could have a different R-successors in each interpretation of a model of $K_{R}$ , thus y cannot be mapped to the same object at every time point.
Remark 9.10.
In the case of streaming data, if we want to take into account a newly available dataset, we do not need to fully recompute $R$ : we only need to add the new rigid assertions that can be derived from the new dataset. Moreover, if we only reason over a window of n time points from our stream, we can annotate the assertions in $R$ with a counter that is initialised with n and decremented with each new time point. If an existing assertion is derived again, it is reset to n. Assertions are then removed from $R$ if their counter reaches 0.
Remark 9.11.
The main goal of the approaches presented in [17,18] for TCQ answering in ${DL-Lite}_{R}$ is to obtain the query answers at the last time point without storing all the data for all previous time points. Their algorithm uses a bounded history encoding, which means that the space required by the algorithm is constant w.r.t. the number n of previous time points: only the current dataset and some auxiliary relations required for computing the query answers are stored and updated at each time point.

Unfortunately, with rigid predicates present, our approach does not achieve bounded history encoding, since the answers of the subqueries of ϕ at previous time points may change when new rigid assertions are derived from the last dataset. However, if the algorithm of [17,18] has this property, it requires exponential space w.r.t. $N_{R C}^{K}$ and $N_{I}^{K}$ which can also be problematic, while our algorithm requires only polynomial space and time. To achieve bounded history encoding (but in exponential time w.r.t. $N_{R C}^{K}$ , $N_{R R}^{K}$ and $N_{I}^{K}$ ), we could adapt the algorithm of [17,18] to support rigid roles. We would consider all possible sets $R$ built from $N_{R C}^{K}$ , $N_{R R}^{K}$ and $N_{I}^{K}$ following the form of Fig. 6, then verify at each time point whether $R$ is consistent with $A_{i}$ and $T$ and contains all rigid assertions that can be derived from $A_{i}$ as described in Fig. 6.

Our procedure only applies to TBoxes in which rigid roles do not have non-rigid subroles. A possible direction to alleviate these restrictions would be to use ideas similar to those developed in [40] for CQ answering over ${DL-Lite}_{R}$ -KB using the combined approach. This CQ answering approach saturates the data by adding to the ABox every assertion that can be derived, introducing individual names to witness existential role restrictions, and then uses a special rewriting to prune spurious answers. In our setting, we could model infinite chains of rigid roles by adding cycles of rigid roles to $R$ , then prune the spurious answers resulting from these cycles.

Regarding ${EL}_{⊥}$ , we conjecture that we could have a similar approach for rigid predicates. The main difference would be that since in ${EL}_{⊥}$ several assertions may be needed to derive one, $R$ would have to be computed iteratively, taking into account its own assertions to derive new ones until a fix-point is reached. Moreover, the problem of infinite chains of rigid roles that cannot be entailed by a polynomial set of assertions would appear as soon as $N_{R R} \neq \emptyset$ . The combined approach for $EL$ [41] could provide ideas to overcome this difficulty.
9.2. Inconsistency-tolerant TCQ answering without rigid predicates

In this section $K$ is a $L$ -TKB and ϕ a TCQ without negation.

When $N_{R C} = N_{R R} = \emptyset$ , an important consequence of Proposition 3.5 is that the repairs of $K$ are all possible sequences ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ where $A_{i}^{'}$ is a repair of $⟨ T, A_{i} ⟩$ , so the intersection of the repairs of $K$ is ${(A_{i}^{\cap})}_{0 ⩽ i ⩽ n}$ where $A_{i}^{\cap}$ is the intersection of the repairs of $⟨ T, A_{i} ⟩$ . This allows us to show that the entailment (resp. IAR entailment) of a BTCQ without negation from a consistent (resp. possibly inconsistent) TKB in a DL $L$ that has the canonical model property for BCQ entailment can be equivalently defined w.r.t. the entailment (resp. IAR entailment) of the BCQs it contains as follows.

Proposition 9.12.
If $L$ has the canonical model property for BCQ entailment and $N_{R C} = N_{R R} = \emptyset$ , then the entailments shown in Table 3 hold for $S = classical$ when $K$ is consistent, and for $S = IAR$ .
Table 3
Entailment under classical or IAR semantics from a $L$ -TKB without rigid predicates and such that $L$ has the canonical model property for BCQ entailment

ϕ $K, p ⊧_{S} ϕ$ iff

$\exists \vec{y} . ψ (\vec{y})$ $p ⩽ n$ and $⟨ T, A_{p} ⟩ ⊧_{S} \exists \vec{y} . ψ (\vec{y})$

$ϕ_{1} \land ϕ_{2}$ $K, p ⊧_{S} ϕ_{1}$ and $K, p ⊧_{S} ϕ_{2}$

$ϕ_{1} \lor ϕ_{2}$ $K, p ⊧_{S} ϕ_{1}$ or $K, p ⊧_{S} ϕ_{2}$

$◯ ϕ_{1}$ $K, p + 1 ⊧_{S} ϕ_{1}$

$●^{b} ϕ_{1}$ $p < n$ implies $K, p + 1 ⊧_{S} ϕ_{1}$

$◯^{-} ϕ_{1}$ $p > 0$ and $K, p - 1 ⊧_{S} ϕ_{1}$

$●^{-} ϕ_{1}$ $p > 0$ implies $K, p - 1 ⊧_{S} ϕ_{1}$

$□ ϕ_{1}$ $\forall k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{1}$

$□^{b} ϕ_{1}$ $\forall k$ , $p ⩽ k ⩽ n$ , $K, k ⊧ ϕ_{1}$

$□^{-} ϕ_{1}$ $\forall k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{1}$

$♢ ϕ_{1}$ $\exists k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{1}$

$♢^{b} ϕ_{1}$ $\exists k$ , $p ⩽ k ⩽ n$ , $K, k ⊧ ϕ_{1}$

$♢^{-} ϕ_{1}$ $\exists k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{1}$

$ϕ_{1} U ϕ_{2}$ $\exists k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{2}$ and $\forall j, p ⩽ j < k, K, j ⊧ ϕ_{1}$

$ϕ_{1} U^{b} ϕ_{2}$ $\exists k$ , $p ⩽ k ⩽ n$ , $K, k ⊧_{S} ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K, j ⊧_{S} ϕ_{1}$

$ϕ_{1} S ϕ_{2}$ $\exists k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{2}$ and $\forall j$ , $k < j ⩽ p, K, j ⊧_{S} ϕ_{1}$

Proof.
For the consistent case, all relations in Table 3 but the first one are straightforwardly obtained by applying the definitions of BTCQ satisfaction of Table 1 in Section 2 to the canonical model of $K$ . Moreover, by Proposition 3.6, if $p ⩽ n$ , then $K, p ⊧ \exists \vec{y} . ψ (\vec{y})$ iff $⟨ T, A_{p} ⟩ ⊧ \exists \vec{y} . ψ (\vec{y})$ . Finally, $K, p ⊭ \exists \vec{y} . ψ (\vec{y})$ if $p > n$ , because there exists a model of $K$ whose pth component interprets every predicate as the empty set.

For IAR semantics, let ${(A_{i}^{ir})}_{0 ⩽ i ⩽ n}$ denote the intersection of the repairs of $K$ and $A_{i}^{\cap}$ denote the intersection of the repairs of $⟨ T, A_{i} ⟩$ .
$K, p ⊧_{IAR} \exists \vec{y} . ψ (\vec{y})$ iff $⟨ T, {(A_{i}^{ir})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ \exists \vec{y} . ψ (\vec{y})$ , i.e., iff $p ⩽ n$ and $⟨ T, A_{p}^{ir} ⟩ ⊧ \exists \vec{y} . ψ (\vec{y})$ because ${(A_{i}^{ir})}_{0 ⩽ i ⩽ n}$ is consistent. Since the repairs of $K$ are the sequences of the repairs of the $⟨ T, A_{i} ⟩$ , $A_{p}^{ir} = A_{p}^{\cap}$ , so $K, p ⊧_{IAR} \exists \vec{y} . ψ (\vec{y})$ iff $p ⩽ n$ and $⟨ T, A_{p} ⟩ ⊧_{IAR} \exists \vec{y} . ψ (\vec{y})$ .

$K, p ⊧_{IAR} ϕ_{1} \land ϕ_{2}$ iff $⟨ T, {(A_{i}^{ir})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{1} \land ϕ_{2}$ , i.e., iff $⟨ T, {(A_{i}^{ir})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{1}$ and $⟨ T, {(A_{i}^{ir})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{2}$ because ${(A_{i}^{ir})}_{0 ⩽ i ⩽ n}$ is consistent. It follows that $K, p ⊧_{IAR} ϕ_{1} \land ϕ_{2}$ iff $K, p ⊧_{IAR} ϕ_{1}$ and $K, p ⊧_{IAR} ϕ_{2}$ .

We show all remaining relations in the same way, applying the definition of IAR semantics and using the fact that ${(A_{i}^{ir})}_{0 ⩽ i ⩽ n}$ is consistent.
□

This is an important result, since it implies that answering temporal CQs under IAR semantics can be done with the algorithms developed for the consistent case (see [17,18] for algorithms for ${DL-Lite}_{R}$ without unbounded future operators) by replacing classical CQ answering by IAR CQ answering (see [14,39,54] for algorithms for ${DL-Lite}_{R}$ ). The following example shows that this is unfortunately not true for brave or AR semantics.
Example 9.13.
Consider the TKB $K = ⟨ T, {(A_{i})}_{0 ⩽ i ⩽ n} ⟩$ and the TCQ ϕ defined as follows. $\begin{array}{l} T = {T ⊑ \neg F} \\ A_{i} = {T (a), F (a)} for 0 ⩽ i ⩽ n \\ ϕ = □^{-} (T (a) \land ●^{-} F (a)) \end{array}$ Now, $K, k ⊧_{brave} T (a) \land ●^{-} F (a)$ for every $0 ⩽ k ⩽ n$ , but $K, n ⊭_{brave} ϕ$ . This is because the same repair cannot entail $T (a) \land ●^{-} F (a)$ both at time point k and $k + 1$ , since it would contain both $(T (a), k)$ and $(F (a), k)$ which is not possible. For AR semantics, consider $ϕ = T (a) \lor F (a)$ over the TKB $K$ : while ϕ holds under AR semantics at each time point, neither $T (a)$ nor $F (a)$ does.

However, if the operators allowed in the TCQ are restricted to $\land, ◯, ●^{b}, ◯^{-}, ●^{-}, □, □^{b}$ , and $□^{-}$ , then AR TCQ answering can be done with the algorithms developed for the consistent case by simply replacing classical CQ answering by AR CQ answering (see [14] for algorithms for ${DL-Lite}_{R}$ ). Indeed, for these operators, the relations of Proposition 9.12 hold for $S = AR$ .
$K, p ⊧_{AR} \exists \vec{y} . ψ (\vec{y})$ iff for every repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ , $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ \exists \vec{y} . ψ (\vec{y})$ , i.e., iff for every repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ , $p ⩽ n$ and $⟨ T, A_{p}^{'} ⟩ ⊧ \exists \vec{y} . ψ (\vec{y})$ because ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is consistent. Since the repairs of $K$ are the sequences of the repairs of the $⟨ T, A_{i} ⟩$ , this is the case iff $p ⩽ n$ and for every repair $A_{p}^{'}$ of $⟨ T, A_{p} ⟩$ , $⟨ T, A_{p}^{'} ⟩ ⊧ \exists \vec{y} . ψ (\vec{y})$ , i.e., iff $p ⩽ n$ and $⟨ T, A_{p} ⟩ ⊧_{AR} \exists \vec{y} . ψ (\vec{y})$ .

$K, p ⊧_{AR} ϕ_{1} \land ϕ_{2}$ iff for every repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ , $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{1} \land ϕ_{2}$ , i.e., iff for every repair ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ of $K$ , $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{1}$ and $⟨ T, {(A_{i}^{'})}_{0 ⩽ i ⩽ n} ⟩, p ⊧ ϕ_{2}$ because ${(A_{i}^{'})}_{0 ⩽ i ⩽ n}$ is consistent. It follows that $K, p ⊧_{AR} ϕ_{1} \land ϕ_{2}$ iff $K, p ⊧_{AR} ϕ_{1}$ and $K, p ⊧_{AR} ϕ_{2}$ .

We show all remaining relations in the same way, applying the definition of AR semantics and using the fact that TKB repairs are consistent.
The following counter-examples show that this is not the case for the other operators: $\lor, ♢, ♢^{b}, ♢^{-}, U, U^{b},$ and $S$ .

$K, 0 ⊧_{AR} ϕ_{1} \lor ϕ_{2}$ but $K, 0 ⊭_{AR} ϕ_{1}$ and $K, 0 ⊭_{AR} ϕ_{2}$ : $\begin{array}{l} T = {A ⊑ \neg B} & A_{0} = {A (a), B (a)} \\ ϕ_{1} = A (a) & ϕ_{2} = B (a) \end{array}$

$K, 0 ⊧_{AR} ♢ ϕ_{1}$ (resp. $K, 0 ⊧_{AR} ♢^{b} ϕ_{1}$ ) but for every k (resp. such that $0 ⩽ k ⩽ 2$ ), $K, k ⊭_{AR} ϕ_{1}$ : $\begin{array}{l} T = {A ⊑ \neg B} & A_{0} = {A (a)} \\ A_{1} = {A (a), B (a)} & A_{2} = {B (a)} \\ ϕ_{1} = A (a) \land ◯ B (a) \end{array}$

$K, 0 ⊧_{AR} ϕ_{1} U ϕ_{2}$ (resp. $K, 0 ⊧_{AR} ϕ_{1} U^{b} ϕ_{2}$ ) but for every k (resp. such that $0 ⩽ k ⩽ 2$ ), either $K, k ⊭_{AR} ϕ_{2}$ or there exists j, such that $0 ⩽ j < k$ and $K, j ⊭_{AR} ϕ_{1}$ : $\begin{array}{l} T = {A ⊑ \neg B} & A_{0} = {A (a)} \\ A_{1} = {A (a), B (a)} & A_{2} = {B (a)} \\ ϕ_{1} = A (a) & ϕ_{2} = B (a) \end{array}$

We can construct similar counter-examples for $♢^{-}$ and $S$ .

Interestingly, contrary to the brave semantics, even for general TCQs the “if” direction of Proposition 9.12 is true.

If $K, p ⊧_{AR} ϕ_{1}$ or $K, p ⊧_{AR} ϕ_{2}$ , then $K, p ⊧_{AR} ϕ_{1} \lor ϕ_{2}$ .

If there exists $k ⩾ p$ such that $K, k ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ♢ ϕ_{1}$ .

If there exists k such that $p ⩽ k ⩽ n$ and $K, k ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ♢^{b} ϕ_{1}$ .

If there exists k such that $0 ⩽ k ⩽ p$ and $K, k ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ♢^{-} ϕ_{1}$ .

If there exists $k ⩾ p$ such that $K, k ⊧_{AR} ϕ_{2}$ and for every j such that $p ⩽ j < k$ , $K, j ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ϕ_{1} U ϕ_{2}$ .

If there exists k such that $p ⩽ k ⩽ n$ , $K, k ⊧_{AR} ϕ_{2}$ and for every j such that $p ⩽ j < k$ , $K, j ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ϕ_{1} U^{b} ϕ_{2}$ .

If there exists k such that $0 ⩽ k ⩽ p$ , $K, k ⊧_{AR} ϕ_{2}$ and for every j such that $k < j ⩽ p$ , $K, j ⊧_{AR} ϕ_{1}$ , then $K, p ⊧_{AR} ϕ_{1} S ϕ_{2}$ .

It follows that even for unrestricted TCQs, combining algorithms for TCQ answering with algorithms for AR query answering will provide a sound approximation of AR answers.

For brave semantics, it would be useful to characterize the queries for which this method would be correct. Indeed, for many pairs of a TBox and a query, the minimal subsets of the TKB such that the query can be mapped into them cannot be inconsistent. For instance, for ${DL-Lite}_{R}$ -TKBs, this is the case if no pair of predicates that may be involved at the same time point appears in an NI entailed by the TBox. Consider for instance $T = {A ⊑ \neg C, B ⊑ \neg C}$ and $ϕ = \exists x . A (x) \land ♢ (\exists x . B (x) \land ◯ (\exists x . C (x)))$ . For ϕ to be entailed at time point p, $\exists x . A (x)$ should hold at p, $\exists x . B (x)$ at time point $i ⩾ p$ and $\exists x . C (x)$ at $i + 1 > p$ , so there cannot be a conflict between the C and the A or B timed assertions used to satisfy the different CQs.
10. Conclusions and future work

ϕ	$K, p ⊧_{S} ϕ$ iff
$\exists \vec{y} . ψ (\vec{y})$	$p ⩽ n$ and $⟨ T, A_{p} ⟩ ⊧_{S} \exists \vec{y} . ψ (\vec{y})$
$ϕ_{1} \land ϕ_{2}$	$K, p ⊧_{S} ϕ_{1}$ and $K, p ⊧_{S} ϕ_{2}$
$ϕ_{1} \lor ϕ_{2}$	$K, p ⊧_{S} ϕ_{1}$ or $K, p ⊧_{S} ϕ_{2}$
$◯ ϕ_{1}$	$K, p + 1 ⊧_{S} ϕ_{1}$
$●^{b} ϕ_{1}$	$p < n$ implies $K, p + 1 ⊧_{S} ϕ_{1}$
$◯^{-} ϕ_{1}$	$p > 0$ and $K, p - 1 ⊧_{S} ϕ_{1}$
$●^{-} ϕ_{1}$	$p > 0$ implies $K, p - 1 ⊧_{S} ϕ_{1}$
$□ ϕ_{1}$	$\forall k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{1}$
$□^{b} ϕ_{1}$	$\forall k$ , $p ⩽ k ⩽ n$ , $K, k ⊧ ϕ_{1}$
$□^{-} ϕ_{1}$	$\forall k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{1}$
$♢ ϕ_{1}$	$\exists k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{1}$
$♢^{b} ϕ_{1}$	$\exists k$ , $p ⩽ k ⩽ n$ , $K, k ⊧ ϕ_{1}$
$♢^{-} ϕ_{1}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{1}$
$ϕ_{1} U ϕ_{2}$	$\exists k$ , $k ⩾ p$ , $K, k ⊧ ϕ_{2}$ and $\forall j, p ⩽ j < k, K, j ⊧ ϕ_{1}$
$ϕ_{1} U^{b} ϕ_{2}$	$\exists k$ , $p ⩽ k ⩽ n$ , $K, k ⊧_{S} ϕ_{2}$ and $\forall j$ , $p ⩽ j < k, K, j ⊧_{S} ϕ_{1}$
$ϕ_{1} S ϕ_{2}$	$\exists k$ , $0 ⩽ k ⩽ p$ , $K, k ⊧_{S} ϕ_{2}$ and $\forall j$ , $k < j ⩽ p, K, j ⊧_{S} ϕ_{1}$

For stream reasoning, handling the temporal dimension of the collected data and being resilient against errors in the data are expedient requirements. In the presence of erroneous data, handling inconsistencies is indispensable for logic-based approaches to stream reasoning. In this paper, we have lifted the standard inconsistency-tolerant semantics AR, IAR and brave to a temporal query answering setting that has been widely studied in the literature—namely, where the data is associated with time points and only the query language admits the use of temporal operators from LTL. We have presented complexity results and techniques to combine temporal with inconsistency-tolerant query answering over lightweight DL temporal knowledge bases suited for ontology-mediated situation recognition.

Our main contribution is a complexity analysis of the three semantics, focusing on the DLs ${EL}_{⊥}$ and ${DL-Lite}_{R}$ , where we distinguished the cases based on whether rigid concept or role names occur in the TKB, and on whether the query contains negation. We provided general algorithms that allow us to derive the complexity of temporal inconsistency-tolerant query answering from the complexities of consistency checking and classical entailment of temporal conjunctive queries. We furthermore completed the complexity picture for the classical semantics for TCQs without negations. Indeed, for the case where the query language does not provide negation, we devised a general approach to assess the complexity by the use of the canonical model property for B(T)CQ answering and thus not only limited to a particular DL. This approach allows us to derive the complexity of temporal query answering from the complexity of conjunctive query entailment for DLs that have this canonical model property.

Encouragingly, our analysis shows that either with or without negation in the query, in most cases, inconsistency-tolerant reasoning and temporal query answering can be combined without increasing the computational complexity. Furthermore, our results show that disallowing negation in the query language results in a drop in the combined complexity of TCQ answering, and, in the case of ${EL}_{⊥}$ with rigid predicates, even in the data complexity. This raises hope that ontology-based stream reasoning applications which are resilient against noise in the data can be feasibly implemented and used in practice.

As a second major contribution, we investigated two techniques useful for developing practical algorithms for inconsistency-tolerant temporal query answering. We first showed that in ${DL-Lite}_{R}$ , under the classical semantics and for queries without negation and unbounded temporal operators, rigid predicates can be handled by adding a set of assertions of polynomial size to each ABox from the TKB. However, our approach, which reduces TCQ answering with rigid predicates to TCQ answering without rigid predicates, works only for BTCQ entailment under the classical semantics.

We then showed that in the case without rigid predicates and for queries without negation, TCQ answering under IAR semantics can be implemented by combining algorithms developed for TCQ answering under the classical semantics with algorithms for CQ answering under IAR semantics over atemporal KBs. Moreover, we showed that when disallowing some of the operators in the queries, the same method can be used for AR semantics, while for full TCQs without negation, it provides for a sound approximation of the AR answers. Unfortunately, this is not the case for brave semantics, which is relevant for practical applications such as recognizing highly critical situations. Thus it would be useful to characterize the queries and TBoxes for which this method is correct. Now, fully fledged practical algorithms still remain to be found for inconsistency-tolerant temporal query answering with rigid predicates.

Another interesting open question is how the complexity changes if we admit not only the qualitative temporal operators from LTL, but also metric temporal operators as found in MTL or ${LTL}^{bin}$ [1,5,42]. In ${LTL}^{bin}$ , temporal operators can be annotated by time intervals over which they are evaluated. In a query language with these operators, it would for example be possible to directly express that a query was entailed at some point during the last 5–10 time units, using the expression $♢_{[5, 10]}^{-} ϕ$ . It is well-known that ${LTL}^{bin}$ formulas can be exponentially encoded in LTL (assuming a binary encoding of the intervals) [42], which would also apply to our setting. This immediately gives complexity upper bounds due to our results, tight in the case of data complexity, but with an exponential increase in the case of combined complexity. This blow-up might be unavoidable, since propositional ${LTL}^{bin}$ is ExpSpace-complete. In fact, combinations of ${LTL}^{bin}$ operators with description logics often lead to an exponential increase in complexity [5,33], and it would be interesting to investigate whether this also happens for the settings considered in this paper. Regarding MTL, an initial investigation of query answering with a Horn-fragment of MTL has been performed in [23].

Footnotes

Acknowledgements

This work has been supported by the DFG in CRC 912 (HAEC), the DAAD, and the grant ANR-16-CE23-0007-01 (“DICOS”). The authors would like to thank Stefan Borgwardt for helpful discussions and the anonymous reviewers for helpful comments.

Detailed proofs

We start by defining the notions of conflicts and causes that will be used in some proofs. A conflict for a KB $K = ⟨ T, A ⟩$ is a minimal $T$ -inconsistent subset of $A$ . A cause for a BCQ q w.r.t. $K$ is a minimal $T$ -consistent subset $C \subseteq A$ such that $⟨ T, C ⟩ ⊧ q$ . The following definitions extend these notions to the temporal setting.

The conflicts of a ${DL-Lite}_{R}$ -TKB are at most binary, i.e., contain at most two timed assertions (Fact 6.11).

Note that a KB (resp. TKB) is consistent iff it has no conflict, and that a BCQ (resp. BTCQ) is entailed from a KB (resp. a TKB) $K$ under brave semantics iff it has some cause in $K$ , since such a cause can be extended to a repair that entails the query.

References

Alur and

T.A.

Henzinger, A really temporal logic, J. ACM41(1) (1994), 181–204. doi:10.1145/174644.174651.

Artale,

Kontchakov,

Kovtunova,

Ryzhikov,

Wolter and

Zakharyaschev, First-order rewritability of temporal ontology-mediated queries, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25–31, 2015,

Yang and

Wooldridge, eds, AAAI Press, 2015, pp. 2706–2712, http://ijcai.org/Abstract/15/383 . ISBN 978-1-57735-738-4.

Artale,

Kontchakov,

Kovtunova,

Ryzhikov,

Wolter and

Zakharyaschev, Ontology-mediated query answering over temporal data: A survey (invited talk), in: 24th International Symposium on Temporal Representation and Reasoning, TIME 2017, Mons, Belgium, 2017, October 16–18,

Schewe,

Schneider and

Wijsen, eds, LIPIcs, Vol. 90, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2017, pp. 1:1–1:37, https://doi.org/10.4230/LIPIcs.TIME.2017.1 . ISBN 978-3-95977-052-1. doi:10.4230/LIPIcs.TIME.2017.1.

Artale,

Kontchakov,

Wolter and

Zakharyaschev, Temporal description logic for ontology-based data access, in: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3–9, 2013,

Rossi, ed., IJCAI/AAAI, 2013, pp. 711–717, http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6824 . ISBN 978-1-57735-633-2.

Baader,

Borgwardt,

Koopmann,

Ozaki and

Thost, Metric temporal description logics with interval-rigid names, in: Frontiers of Combining Systems – 11th International Symposium, Proceedings, FroCoS 2017, Brasília, Brazil, September 27–29, 2017,

Dixon and

Finger, eds, Lecture Notes in Computer Science, Vol. 10483, Springer, 2017, pp. 60–76, https://doi.org/10.1007/978-3-319-66167-4_4 . ISBN 978-3-319-66166-7. doi:10.1007/978-3-319-66167-4_4.

Baader,

Borgwardt and

Lippmann, Temporalizing ontology-based data access, in: Automated Deduction – CADE-24 – 24th International Conference on Automated Deduction, Proceedings, Lake Placid, NY, USA, June 9–14, 2013,

M.P.

Bonacina, ed., Lecture Notes in Computer Science, Vol. 7898, Springer, 2013, pp. 330–344, https://doi.org/10.1007/978-3-642-38574-2_23 . ISBN 978-3-642-38573-5. doi:10.1007/978-3-642-38574-2_23.

Baader,

Borgwardt and

Lippmann, Temporal query entailment in the description logic SHQ, J. Web Sem.33 (2015), 71–93, https://doi.org/10.1016/j.websem.2014.11.008 . doi:10.1016/j.websem.2014.11.008.

Beck,

Dao-Tran,

Eiter and

Fink, LARS: A logic-based framework for analyzing reasoning over streams, in: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, Texas, USA, January 25–30, 2015,

Bonet and

Koenig, eds, AAAI Press, 2015, pp. 1431–1438, http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9657 . ISBN 978-1-57735-698-1.

Beck,

Dao-Tran,

Eiter and

Fink, Towards Ideal Semantics for Analyzing Stream Reasoning, 2015, CoRR, http://arxiv.org/abs/1505.05365.

10.

Beck,

Eiter and

Folie, Ticker: A system for incremental ASP-based stream reasoning, TPLP17(5–6) (2017), 744–763, https://doi.org/10.1017/S1471068417000370 . doi:10.1017/S1471068417000370.

11.

L.E.

Bertossi, Database Repairing and Consistent Query Answering, Synthesis Lectures on Data Management, Morgan & Claypool Publishers, 2011, https://doi.org/10.2200/S00379ED1V01Y201108DTM020 . doi:10.2200/S00379ED1V01Y201108DTM020.

12.

Bienvenu, On the complexity of consistent query answering in the presence of simple ontologies, in: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22–26, 2012,

Hoffmann and

Selman, eds, AAAI Press, 2012, http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4928 .

13.

Bienvenu and

Bourgaux, Inconsistency-tolerant querying of description logic knowledge bases, in: Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering – 12th International Summer School 2016, Tutorial Lectures, Aberdeen, UK, September 5–9, 2016,

J.Z.

Pan,

Calvanese,

Eiter,

Horrocks,

Kifer,

Lin and

Zhao, eds, Lecture Notes in Computer Science, Vol. 9885, Springer, 2016, pp. 156–202, https://doi.org/10.1007/978-3-319-49493-7_5 . ISBN 978-3-319-49492-0. doi:10.1007/978-3-319-49493-7_5.

14.

Bienvenu,

Bourgaux and

Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, July 27–31, 2014,

C.E.

Brodley and

Stone, eds, AAAI Press, 2014, pp. 996–1002, http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8231 . ISBN 978-1-57735-661-5.

15.

Bienvenu,

Bourgaux and

Goasdoué, Explaining inconsistency-tolerant query answering over description logic knowledge bases, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, February 12–17, 2016,

Schuurmans and

M.P.

Wellman, eds, AAAI Press, 2016, pp. 900–906, http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12025 . ISBN 978-1-57735-760-5.

16.

Bienvenu and

Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3–9, 2013,

Rossi, ed., IJCAI/AAAI, 2013, pp. 775–781, http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6904 . ISBN 978-1-57735-633-2.

17.

Borgwardt,

Lippmann and

Thost, Temporal query answering in the description logic DL-Lite, in: Frontiers of Combining Systems – 9th International Symposium, FroCoS 2013, Proceedings, Nancy, France, September 18–20, 2013,

Fontaine,

Ringeissen and

R.A.

Schmidt, eds, Lecture Notes in Computer Science, Vol. 8152, Springer, 2013, pp. 165–180, https://doi.org/10.1007/978-3-642-40885-4_11 . ISBN 978-3-642-40884-7. doi:10.1007/978-3-642-40885-4_11.

18.

Borgwardt,

Lippmann and

Thost, Temporalizing rewritable query languages over knowledge bases, J. Web Sem.33 (2015), 50–70, https://doi.org/10.1016/j.websem.2014.11.007 . doi:10.1016/j.websem.2014.11.007.

19.

Borgwardt and

Thost, Temporal query answering in DL-Lite with negation, in: Global Conference on Artificial Intelligence, GCAI 2015, Tbilisi, Georgia, October 16–19, 2015,

Gottlob,

Sutcliffe and

Voronkov, eds, EPiC Series in Computing, Vol. 36, EasyChair, 2015, pp. 51–65, http://www.easychair.org/publications/paper/245305 .

20.

Borgwardt and

Thost, Temporal query answering in the description logic EL, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25–31, 2015,

Yang and

Wooldridge, eds, AAAI Press, 2015, pp. 2819–2825, http://ijcai.org/Abstract/15/399 . ISBN 978-1-57735-738-4.

21.

Bourgaux and

A.-Y.

Turhan, Temporal query answering in DL-Lite over inconsistent data, in: The Semantic Web – ISWC 2017 – 16th International Semantic Web Conference, Proceedings, Part I, Vienna, Austria, October 21–25, 2017,

d’Amato,

Fernández,

V.A.M.

Tamma,

Lécué,

Cudré-Mauroux,

J.F.

Sequeda,

Lange and

Heflin, eds, Lecture Notes in Computer Science, Vol. 10587, Springer, 2017, pp. 121–137, https://doi.org/10.1007/978-3-319-68288-4_8 . ISBN 978-3-319-68287-7. doi:10.1007/978-3-319-68288-4_8.

22.

Bourgaux and

A.-Y.

Turhan, Temporal Query Answering in DL-Lite over Inconsistent Data, 2017, LTCS-Report 17-06, Chair for Automata Theory, TU Dresden, available at: https://lat.inf.tu-dresden.de/research/reports.html.

23.

Brandt,

E.G.

Kalayci,

Kontchakov,

Ryzhikov,

Xiao and

Zakharyaschev, Ontology-based data access with a Horn fragment of metric temporal logic, in: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, USA, February 4–9, 2017,

S.P.

Singh and

Markovitch, eds, AAAI Press, 2017, pp. 1070–1076, http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14881 .

24.

Brandt,

E.G.

Kalayci,

Ryzhikov,

Xiao and

Zakharyaschev, A framework for temporal ontology-based data access: A proposal, in: New Trends in Databases and Information Systems – ADBIS 2017 Short Papers and Workshops, AMSD, BigNovelTI, DAS, SW4CH, DC, Proceedings, Nicosia, Cyprus, September 24–27, 2017,

Kirikova,

Nørvåg,

G.A.

Papadopoulos,

Gamper,

Wrembel,

Darmont and

Rizzi, eds, Communications in Computer and Information Science, Vol. 767, Springer, 2017, pp. 161–173, https://doi.org/10.1007/978-3-319-67162-8_17 . ISBN 978-3-319-67161-1. doi:10.1007/978-3-319-67162-8_17.

25.

Calvanese,

De Giacomo,

Lembo,

Lenzerini,

Poggi,

Rodriguez-Muro and

Rosati, Ontologies and databases: The DL-Lite approach, in: Reasoning Web. Semantic Technologies for Information Systems, 5th International Summer School 2009, Tutorial Lectures, Brixen-Bressanone, Italy, August 30–September 4, 2009,

Tessaris,

Franconi,

Eiter,

Gutiérrez,

Handschuh,

Rousset and

R.A.

Schmidt, eds, Lecture Notes in Computer Science, Vol. 5689, Springer, 2009, pp. 255–356, https://doi.org/10.1007/978-3-642-03754-2_7 . ISBN 978-3-642-03753-5. doi:10.1007/978-3-642-03754-2_7.

26.

Calvanese,

De Giacomo,

Lembo,

Lenzerini and

Rosati, Tractable reasoning and efficient query answering in description logics: The DL-Lite family, J. Autom. Reasoning39(3) (2007), 385–429, https://doi.org/10.1007/s10817-007-9078-x . doi:10.1007/s10817-007-9078-x.

27.

Calvanese,

E.G.

Kalayci,

Ryzhikov and

Xiao, Towards practical OBDA with temporal ontologies – (position paper), in: Web Reasoning and Rule Systems – 10th International Conference, RR 2016, Proceedings, Aberdeen, UK, September 9–11, 2016,

Ortiz and

Schlobach, eds, Lecture Notes in Computer Science, Vol. 9898, Springer, 2016, pp. 18–24, https://doi.org/10.1007/978-3-319-45276-0_2 . ISBN 978-3-319-45275-3. doi:10.1007/978-3-319-45276-0_2.

28.

Chomicki,

Toman and

M.H.

Böhlen, Querying ATSQL databases with temporal logic, ACM Trans. Database Syst.26(2) (2001), 145–178, http://portal.acm.org/citation.cfm?id=383891.383892 . doi:10.1145/383891.383892.

29.

De Giacomo,

De Masellis and

Montali, Reasoning on LTL on finite traces: Insensitivity to infiniteness, in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, July 27–31, 2014,

C.E.

Brodley and

Stone, eds, AAAI Press, 2014, pp. 1027–1033, http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8575 . ISBN 978-1-57735-661-5.

30.

D.M.

Gabbay, The declarative past and imperative future: Executable temporal logic for interactive systems, in: Temporal Logic in Specification, Proceedings, Altrincham, UK, April 8–10, 1987,

Banieqbal,

Barringer and

Pnueli, eds, Lecture Notes in Computer Science, Vol. 398, Springer, 1987, pp. 409–448, https://doi.org/10.1007/3-540-51803-7_36 . ISBN 3-540-51803-7. doi:10.1007/3-540-51803-7_36.

31.

Gebser,

Grote,

Kaminski,

Obermeier,

Sabuncu and

Schaub, Stream reasoning with answer set programming: Preliminary report, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10–14, 2012,

Brewka,

Eiter and

S.A.

McIlraith, eds, AAAI Press, 2012, http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4504 . ISBN 978-1-57735-560-1.

32.

Gottlob, NP trees and Carnap’s modal logic, J. ACM42(2) (1995), 421–457. doi:10.1145/201019.201031.

33.

Gutiérrez-Basulto,

J.C.

Jung and

Ozaki, On metric temporal description logics, in: ECAI 2016 – 22nd European Conference on Artificial Intelligence – Including Prestigious Applications of Artificial Intelligence (PAIS 2016), The Hague, The Netherlands, 29 August–2 September 2016,

G.A.

Kaminka,

Fox,

Bouquet,

Hüllermeier,

Dignum,

Dignum and

van Harmelen, eds, Frontiers in Artificial Intelligence and Applications, Vol. 285, IOS Press, 2016, pp. 837–845, https://doi.org/10.3233/978-1-61499-672-9-837 . ISBN 978-1-61499-671-2. doi:10.3233/978-1-61499-672-9-837.

34.

Klarman and

Meyer, Querying temporal databases via OWL 2 QL, in: Web Reasoning and Rule Systems – 8th International Conference, RR 2014, Proceedings, Athens, Greece, September 15–17, 2014,

Kontchakov and

Mugnier, eds, Lecture Notes in Computer Science, Vol. 8741, Springer, 2014, pp. 92–107, https://doi.org/10.1007/978-3-319-11113-1_7 . ISBN 978-3-319-11112-4. doi:10.1007/978-3-319-11113-1_7.

35.

Kontchakov,

Lutz,

Toman,

Wolter and

Zakharyaschev, The combined approach to query answering in DL-Lite, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9–13, 2010,

Lin,

Sattler and

Truszczynski, eds, AAAI Press, 2010, http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1282 .

36.

Lécué, Diagnosing changes in an ontology stream: A DL reasoning approach, in: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22–26, 2012,

Hoffmann and

Selman, eds, AAAI Press, 2012, http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4988 .

37.

Lembo,

Lenzerini,

Rosati,

Ruzzi and

D.F.

Savo, Inconsistency-tolerant semantics for description logics, in: Web Reasoning and Rule Systems – Fourth International Conference, RR 2010, Proceedings, Bressanone/Brixen, Italy, September 22–24, 2010,

Hitzler and

Lukasiewicz, eds, Lecture Notes in Computer Science, Vol. 6333, Springer, 2010, pp. 103–117, https://doi.org/10.1007/978-3-642-15918-3_9 . ISBN 978-3-642-15917-6. doi:10.1007/978-3-642-15918-3_9.

38.

Lembo,

Lenzerini,

Rosati,

Ruzzi and

D.F.

Savo, Query rewriting for inconsistent DL-Lite ontologies, in: Proceedings, Web Reasoning and Rule Systems – 5th International Conference, RR 2011, Galway, Ireland, August 29–30, 2011,

Rudolph and

Gutiérrez, eds, Lecture Notes in Computer Science, Vol. 6902, Springer, 2011, pp. 155–169, https://doi.org/10.1007/978-3-642-23580-1_12 . ISBN 978-3-642-23579-5. doi:10.1007/978-3-642-23580-1_12.

39.

Lembo,

Lenzerini,

Rosati,

Ruzzi and

D.F.

Savo, Inconsistency-tolerant query answering in ontology-based data access, J. Web Sem.33 (2015), 3–29, https://doi.org/10.1016/j.websem.2015.04.002 . doi:10.1016/j.websem.2015.04.002.

40.

Lutz,

Seylan,

Toman and

Wolter, The combined approach to OBDA: Taming role hierarchies using filters, in: The Semantic Web – ISWC 2013 – 12th International Semantic Web Conference, Proceedings, Part I, Sydney, NSW, Australia, October 21–25, 2013,

Alani,

Kagal,

Fokoue,

P.T.

Groth,

Biemann,

J.X.

Parreira,

Aroyo,

N.F.

Noy,

Welty and

Janowicz, eds, Lecture Notes in Computer Science, Vol. 8218, Springer, 2013, pp. 314–330, https://doi.org/10.1007/978-3-642-41335-3_20 . ISBN 978-3-642-41334-6. doi:10.1007/978-3-642-41335-3_20.

41.

Lutz,

Toman and

Wolter, Conjunctive query answering in the description logic EL using a relational database system, in: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009,

Boutilier, ed., 2009, pp. 2070–2075, http://ijcai.org/Proceedings/09/Papers/341.pdf .

42.

Lutz,

Walther and

Wolter, Quantitative temporal logics over the reals: PSpace and below, Inf. Comput.205(1) (2007), 99–123, https://doi.org/10.1016/j.ic.2006.08.006 . doi:10.1016/j.ic.2006.08.006.

43.

Margara,

Urbani,

van Harmelen and

H.E.

Bal, Streaming the web: Reasoning over dynamic data, J. Web Sem.25 (2014), 24–44, https://doi.org/10.1016/j.websem.2014.02.001 . doi:10.1016/j.websem.2014.02.001.

44.

Mileo,

Abdelrahman,

Policarpio and

Hauswirth, StreamRule: A nonmonotonic stream reasoning system for the semantic web, in: Web Reasoning and Rule Systems – 7th International Conference, RR 2013, Proceedings, Mannheim, Germany, July 27–29, 2013,

Faber and

Lembo, eds, Lecture Notes in Computer Science, Vol. 7994, Springer, 2013, pp. 247–252, https://doi.org/10.1007/978-3-642-39666-3_23 . ISBN 978-3-642-39665-6. doi:10.1007/978-3-642-39666-3_23.

45.

Motik,

Cuenca Grau,

Horrocks,

Wu,

Fokoue and

Lutz, OWL 2 Web Ontology Language Profiles, 2012, available at: http://www.w3.org/TR/owl2-profiles/.

46.

OWL Working Group, OWL 2 Web Ontology Language: Document Overview, W3C Recommendation, 2009, available at: https://www.w3.org/TR/owl2-overview/.

47.

Ö.L.

Özçep,

Möller and

Neuenstadt, A stream-temporal query language for ontology based data access, in: KI 2014: Advances in Artificial Intelligence – 37th Annual German Conference on AI, Proceedings, Stuttgart, Germany, September 22–26,

Lutz and

Thielscher, eds, Lecture Notes in Computer Science, Vol. 8736, Springer, 2014, pp. 183–194, https://doi.org/10.1007/978-3-319-11206-0_18 . ISBN 978-3-319-11205-3. doi:10.1007/978-3-319-11206-0_18.

48.

Pnueli, The temporal logic of programs, in: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October–1 November 1977, IEEE Computer Society, 1977, pp. 46–57, https://doi.org/10.1109/SFCS.1977.32 . doi:10.1109/SFCS.1977.32.

49.

Ren and

J.Z.

Pan, Optimising ontology stream reasoning with truth maintenance system, in: Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom, October 24–28, 2011,

Macdonald,

Ounis and

Ruthven, eds, ACM, 2011, pp. 831–836. ISBN 978-1-4503-0717-8. doi:10.1145/2063576.2063696.

50.

Rosati, On conjunctive query answering in EL, in: Proceedings of the 2007 International Workshop on Description Logics (DL2007), Brixen-Bressanone, Near Bozen-Bolzano, Italy, 8–10 June, 2007,

Calvanese,

Franconi,

Haarslev,

Lembo,

Motik,

Turhan and

Tessaris, eds, CEUR Workshop Proceedings, Vols 250, CEUR-WS.org, 2007, http://ceur-ws.org/Vol-250/paper_83.pdf .

51.

Rosati, On the complexity of dealing with inconsistency in description logic ontologies, in: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16–22, 2011,

Walsh, ed., IJCAI/AAAI, 2011, pp. 1057–1062, https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-181 . ISBN 978-1-57735-516-8. doi:10.5591/978-1-57735-516-8/IJCAI11-181.

52.

Rosati,

Ruzzi,

Graziosi and

Masotti, Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies, in: The Semantic Web – ISWC 2012 – 11th International Semantic Web Conference, Proceedings, Part II, Boston, MA, USA, November 11–15, 2012,

Cudré-Mauroux,

Heflin,

Sirin,

Tudorache,

Euzenat,

Hauswirth,

J.X.

Parreira,

Hendler,

Schreiber,

Bernstein and

Blomqvist, eds, Lecture Notes in Computer Science, Vol. 7650, Springer, 2012, pp. 337–349, https://doi.org/10.1007/978-3-642-35173-0_23 . ISBN 978-3-642-35172-3. doi:10.1007/978-3-642-35173-0_23.

53.

Thost,

Holste and

Ö.L.

Özçep, On implementing temporal query answering in DL-Lite (extended abstract), in: Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7–10, 2015,

Calvanese and

Konev, eds, CEUR Workshop Proceedings, Vols 1350, CEUR-WS.org, 2015, http://ceur-ws.org/Vol-1350/paper-63.pdf .

54.

Tsalapati,

Stoilos,

G.B.

Stamou and

Koletsos, Efficient query answering over expressive inconsistent description logics, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 2016, 9–15 July,

Kambhampati, ed., IJCAI/AAAI Press, 2016, pp. 1279–1285, http://www.ijcai.org/Abstract/16/185 . ISBN 978-1-57735-770-4.

Ontology-mediated query answering over temporal and inconsistent data

Abstract

Keywords

1. Introduction

1.1. Contributions

2. Preliminaries

Example 2.4 (Example 2.2 cont’d).

Remark 2.5 (Choice of operators).

Definition 2.6 (TCQ answering).

Table 1 Satisfaction of BTCQs by a sequence of interpretations

Definition 3.1 (Repair of a TKB).

Example 3.4 (Example 3.2 cont’d).

5. General algorithms for inconsistency-tolerant BTCQ entailment

Theorem 6.1. The results in Fig. 3 hold. 6.1. Consistency checking and repair recognition for TKBs

9.1. TCQ answering under classical semantics with rigid predicates for DL-Lite R and TCQs without negation or unbounded future operators

1 This condition is new and added after consultation with the authors of [17,18].

Footnotes

Acknowledgements

Detailed proofs

References

Table 1
Satisfaction of BTCQs by a sequence of interpretations

Theorem 6.1.
The results in Fig. 3 hold.

6.1. Consistency checking and repair recognition for TKBs

9.1. TCQ answering under classical semantics with rigid predicates for ${DL-Lite}_{R}$ and TCQs without negation or unbounded future operators

¹
This condition is new and added after consultation with the authors of [17,18].