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 ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{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.

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) ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{R}}$ , for which answering conjunctive queries is tractable (respectively in P and ${\mathsf{AC}}^0$ w.r.t. the size of the data). The low complexity for query answering in ${\text{DL-Lite}}_{\mathcal{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 $\mathcal{EL}$ was picked as the core of the OWL 2 EL profile. Both ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ admit to use database systems to answer conjunctive queries and are thus good candidates for implementing ontology-based stream reasoning. In ${\text{DL-Lite}}_{\mathcal{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 $\mathcal{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 $\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$ in [19], and for $\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$ in [16,37–39] and for ${\mathcal{EL}}_{\perp }$ 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 $\mathsf{CQAPri}$ system, which implements all three mentioned semantics—AR, IAR and brave—for ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$ over inconsistent data, where the complexity of answering queries with LTL operators, but without negation, over ${\text{DL-Lite}}_{\mathcal{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 ${\mathcal{EL}}_{\perp }$ , as well as some results for ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ 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) $\mathcal{K}$ consists of an ABox $\mathcal{A}$ and a TBox $\mathcal{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 $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ and role assertions $\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , where $\mathit{A}\in N_C$ , $\mathit{R}\in N_R$ , $\mathit{a}\mathrm{,}\mathit{b}\in N_I$ . The TBox (ontology) is a finite set of axioms whose form depends on the particular DL.

In ${\text{DL-Lite}}_{\mathcal{R}}$ , TBox axioms are either concept inclusions $\mathit{B}⊑\mathit{C}$ or role inclusions $\mathit{P}⊑\mathit{S}$ , built according to the following syntax, where $\mathit{A}\in N_C$ and $\mathit{R}\in N_R$ : $$\begin{array}{cc}\hfill & \mathit{B}:=\mathit{A}\mid \exists \mathit{P}\mathit{C}:=\mathit{B}\mid \neg \mathit{B}\hfill \\ \hfill & \mathit{P}:=\mathit{R}\mid {\mathit{R}}^{-}\mathit{S}:=\mathit{P}\mid \neg \mathit{P}.\hfill \end{array}$$ Inclusions of the form ${\mathit{B}}_1⊑{\mathit{B}}_2$ or ${\mathit{P}}_1⊑{\mathit{P}}_2$ are called positive inclusions (PI), those of the form ${\mathit{B}}_1⊑\neg {\mathit{B}}_2$ or ${\mathit{P}}_1⊑\neg {\mathit{P}}_2$ are called negative inclusions (NI).

In ${\mathcal{EL}}_{\perp }$ , the TBox contains concept inclusions of the form ${\mathit{C}}_1⊑{\mathit{C}}_2$ , where ${\mathit{C}}_1$ and ${\mathit{C}}_2$ are built according to the following syntax, where $\mathit{A}\in N_C$ and $\mathit{R}\in N_R$ : $$\begin{array}{c}\mathit{C}:=\top \mid \perp \mid \mathit{A}\mid \exists \mathit{R}.\mathit{C}\mid \mathit{C}\sqcap \mathit{C}.\end{array}$$ An ${\mathcal{EL}}_{\perp }$ inclusion of the form ${\mathit{C}}_1\sqcap {\mathit{C}}_2⊑\perp$ can also be written in the form of a negative inclusion ${\mathit{C}}_1⊑\neg {\mathit{C}}_2$ .

Semantics. An interpretation is a tuple of the form $\mathcal{I}=⟨{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}⟩$ , where ${\mathrm{\Delta }}^{\mathcal{I}}$ is a non-empty set and ${·}^{\mathcal{I}}$ maps each $\mathit{a}\in N_I$ to ${\mathit{a}}^{\mathcal{I}}\in {\mathrm{\Delta }}^{\mathcal{I}}$ , each $\mathit{A}\in N_C$ to ${\mathit{A}}^{\mathcal{I}}\subseteq {\mathrm{\Delta }}^{\mathcal{I}}$ , and each $\mathit{R}\in N_R$ to ${\mathit{R}}^{\mathcal{I}}\subseteq {\mathrm{\Delta }}^{\mathcal{I}}\times {\mathrm{\Delta }}^{\mathcal{I}}$ . We adopt the unique name assumption, i.e., for all $\mathit{a}\mathrm{,}\mathit{b}\in N_I$ , we require ${\mathit{a}}^{\mathcal{I}}\ne {\mathit{b}}^{\mathcal{I}}$ if $\mathit{a}\ne \mathit{b}$ . The function ${·}^{\mathcal{I}}$ is straightforwardly extended to general concepts and roles, e.g., ${\top }^{\mathcal{I}}={\mathrm{\Delta }}^{\mathcal{I}}$ , ${\perp }^{\mathcal{I}}=\varnothing$ , ${\mathrm{(}{\mathit{R}}^{-}\mathrm{)}}^{\mathcal{I}}=\{\mathrm{(}\mathit{d}\mathrm{,}\mathit{e}\mathrm{)}\mid \mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}\in {\mathit{R}}^{\mathcal{I}}\}$ , ${\mathrm{(}\neg \mathit{R}\mathrm{)}}^{\mathcal{I}}={\mathrm{\Delta }}^{\mathcal{I}}\times {\mathrm{\Delta }}^{\mathcal{I}}\setminus {\mathit{R}}^{\mathcal{I}}$ , ${\mathrm{(}\exists \mathit{P}\mathrm{)}}^{\mathcal{I}}=\{\mathit{d}\mid \exists \mathit{e}:\mathrm{(}\mathit{d}\mathrm{,}\mathit{e}\mathrm{)}\in {\mathit{P}}^{\mathcal{I}}\}$ , ${\mathrm{(}\exists \mathit{P}.\mathit{C}\mathrm{)}}^{\mathcal{I}}=\{\mathit{d}\mid \exists \mathit{e}:\mathrm{(}\mathit{d}\mathrm{,}\mathit{e}\mathrm{)}\in {\mathit{P}}^{\mathcal{I}}\mathrm{,}\mathit{e}\in {\mathit{C}}^{\mathcal{I}}\}$ ${\mathrm{(}{\mathit{C}}_1\sqcap {\mathit{C}}_2\mathrm{)}}^{\mathcal{I}}={\mathit{C}}_1^{\mathcal{I}}\cap {\mathit{C}}_2^{\mathcal{I}}$ .

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

Queries. A conjunctive query (CQ) takes the form $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{x}}\mathrm{,}\overrightarrow{\mathit{y}}\mathrm{)}$ , where ψ is a conjunction of atoms of the form $\mathit{A}\mathrm{(}\mathit{t}\mathrm{)}$ or $\mathit{R}\mathrm{(}\mathit{t}\mathrm{,}{\mathit{t}}^{\prime }\mathrm{)}$ , with $\mathit{t}\mathrm{,}{\mathit{t}}^{\prime }$ individual names or variables from $\overrightarrow{\mathit{x}}\cup \overrightarrow{\mathit{y}}$ . We call the variables in $\overrightarrow{\mathit{x}}$ the free variables in q. A CQ is called Boolean (BCQ) if it has no free variables (i.e., $\overrightarrow{\mathit{x}}=\varnothing$ ). A BCQ q is satisfied by an interpretation $\mathcal{I}=⟨{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}⟩$ , written $\mathcal{I}\vDash \mathit{q}$ , if there is a homomorphism π mapping the variables and individual names of q into ${\mathrm{\Delta }}^{\mathcal{I}}$ such that: $\mathit{\pi }\mathrm{(}\mathit{a}\mathrm{)}={\mathit{a}}^{\mathcal{I}}$ for every $\mathit{a}\in N_I$ , $\mathit{\pi }\mathrm{(}\mathit{t}\mathrm{)}\in {\mathit{A}}^{\mathcal{I}}$ for every concept atom $\mathit{A}\mathrm{(}\mathit{t}\mathrm{)}$ in ψ, and $\mathrm{(}\mathit{\pi }\mathrm{(}\mathit{t}\mathrm{)}\mathrm{,}\mathit{\pi }\mathrm{(}{\mathit{t}}^{\prime }\mathrm{)}\mathrm{)}\in {\mathit{R}}^{\mathcal{I}}$ for every role atom $\mathit{R}\mathrm{(}\mathit{t}\mathrm{,}{\mathit{t}}^{\prime }\mathrm{)}$ in ψ. A BCQ q is entailed from $\mathcal{K}$ , written $\mathcal{K}\vDash \mathit{q}$ , iff q is satisfied by every model of $\mathcal{K}$ . Given a CQ q with free variables $\overrightarrow{\mathit{x}}=\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{k}}\mathrm{)}$ and a tuple of individuals $\overrightarrow{\mathit{a}}=\mathrm{(}{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{k}}\mathrm{)}$ , $\overrightarrow{\mathit{a}}$ is a certain answer to q over  $\mathcal{K}$ if $\mathcal{K}\vDash \mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ , where $\mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ is the BCQ resulting from replacing each  ${\mathit{x}}_{\mathit{j}}$ in q by ${\mathit{a}}_{\mathit{j}}$ .

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

AR semantics, written $\mathcal{K}{\vDash }_{\text{AR}}\mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}^{\prime }⟩\vDash \mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ for every repair ${\mathcal{A}}^{\prime }$ of $\mathcal{K}$ ;

IAR semantics, written $\mathcal{K}{\vDash }_{\text{IAR}}\mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}^{\cap }⟩\vDash \mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ where ${\mathcal{A}}^{\cap }$ is the intersection of all repairs of $\mathcal{K}$ ;

brave semantics, written $\mathcal{K}{\vDash }_{\text{brave}}\mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}^{\prime }⟩\vDash \mathit{q}\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ for some repair ${\mathcal{A}}^{\prime }$ of $\mathcal{K}$ .

Figure 1 summarizes the complexity of BCQ entailment under the different semantics for ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ . 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 ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ , 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 ${\text{DL-Lite}}_{\mathcal{R}}$ [16,37] and ${\mathcal{EL}}_{\perp }$ [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) $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ consists of a TBox $\mathcal{T}$ and a finite sequence of ABoxes ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ . An infinite sequence $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ of interpretations ${\mathcal{I}}_{\mathit{i}}=⟨\mathrm{\Delta }\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}}⟩$ over a fixed non-empty domain Δ (constant domain assumption) is a model of $\mathcal{K}$ iff for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , for every $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $\mathcal{T}$ , and for every $\mathit{a}\in N_I$ and all $\mathit{i}\mathrm{,}\mathit{j}⩾0$ , ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{{\mathcal{I}}_{\mathit{j}}}$ (rigidity of individual names). Rigid predicates are elements from the set $N_{RC}\subseteq N_C$ of rigid concepts and the set $N_{RR}\subseteq N_R$ of rigid roles. A sequence of interpretations $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ respects rigid predicates iff for every $\mathit{X}\in N_{RC}\cup N_{RR}$ and all $\mathit{i}\mathrm{,}\mathit{j}⩾0$ , ${\mathit{X}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{X}}^{{\mathcal{I}}_{\mathit{j}}}$ . A TKB is consistent if it has a model that respects rigid predicates. A sequence of ABoxes ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is $\mathcal{T}$ -consistent, or simply consistent, if the TKB $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ is consistent.

Example 2.2.

The following ${\mathcal{EL}}_{\perp }$ TKB gives information useful to monitor a cluster of servers. The TBox $\mathcal{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 ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽2}$ records information on a server s. The set of rigid roles is $N_{RR}=\{\mathsf{hasCPU}\}$ , which models the fact that the CPU of a server does not change over time. $$\begin{array}{ll}\hfill & \begin{array}{cc}\hfill \mathcal{T}=& \{\exists \mathsf{executes}.\mathsf{IncreasingWorkload}⊑\mathsf{LoadRise}\mathrm{,}\hfill \\ \hfill & \exists \mathsf{hasCPU}.\mathsf{MaxUtilized}⊑\mathsf{MaxLoaded}\mathrm{,}\hfill \\ \hfill & \mathsf{LoadRise}\sqcap \mathsf{MaxLoaded}⊑\mathsf{Overloaded}\}\hfill \end{array}\\ \hfill & \begin{array}{cc}\hfill {\mathcal{A}}_0=& \{\mathsf{hasCPU}\mathrm{(}\mathit{s}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathsf{MaxUtilized}\mathrm{(}\mathit{c}\mathrm{)}\mathrm{,}\hfill \\ \hfill & \mathsf{executes}\mathrm{(}\mathit{s}\mathrm{,}{\mathit{p}}_1\mathrm{)}\mathrm{,}\mathsf{IncreasingWorkload}\mathrm{(}{\mathit{p}}_1\mathrm{)}\}\hfill \end{array}\\ \hfill & \begin{array}{cc}\hfill {\mathcal{A}}_1=& \{\mathsf{MaxUtilized}\mathrm{(}\mathit{c}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{s}\mathrm{,}{\mathit{p}}_1\mathrm{)}\mathrm{,}\hfill \\ \hfill & \mathsf{executes}\mathrm{(}\mathit{s}\mathrm{,}{\mathit{p}}_2\mathrm{)}\mathrm{,}\mathsf{IncreasingWorkload}\mathrm{(}{\mathit{p}}_2\mathrm{)}\}\hfill \end{array}\\ \hfill & {\mathcal{A}}_2=\{\mathsf{executes}\mathrm{(}\mathit{s}\mathrm{,}{\mathit{p}}_2\mathrm{)}\}\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: ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ then becomes $\{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\mid \mathit{\alpha }\in {\mathcal{A}}_{\mathit{i}}\mathrm{,}0⩽\mathit{i}⩽\mathit{n}\}$ .

A rigid concept is a concept which only uses rigid predicates. A rigid assertion is of the form $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ with $\mathit{A}\in N_{RC}$ or $\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ with $\mathit{R}\in N_{RR}$ . We distinguish three cases depending on which predicates can be rigid: in the first case, we have no rigid predicates ( $N_{RC}=\varnothing$ and $N_{RR}=\varnothing$ ), in the second case, we do allow only for rigid concepts ( $N_{RC}\ne \varnothing$ and $N_{RR}=\varnothing$ ), and in the last case, we have both, rigid concepts and rigid roles ( $N_{RC}\ne \varnothing$ and $N_{RR}\ne \varnothing$ ). Because rigid concepts can be simulated with rigid roles using a pair of concept inclusions of the form $\mathit{A}⊑\exists \mathit{R}$ , $\exists \mathit{R}⊑\mathit{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 ${\mathit{\varphi }}_1$ and ${\mathit{\varphi }}_2$ are TCQs, then so are $\neg {\mathit{\varphi }}_1$ (negation), ${\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ (conjunction), ${\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$ (disjunction), $\text{◯}{\mathit{\varphi }}_1$ (next), ${\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$ (bounded next), ${\text{◯}}^{-}{\mathit{\varphi }}_1$ (strong previous), ${\text{●}}^{-}{\mathit{\varphi }}_1$ (weak previous), $\square {\mathit{\varphi }}_1$ (always), ${\square }^{\mathit{b}}{\mathit{\varphi }}_1$ (bounded always), ${\square }^{-}{\mathit{\varphi }}_1$ (always in the past), $♢{\mathit{\varphi }}_1$ (eventually), ${♢}^{\mathit{b}}{\mathit{\varphi }}_1$ (bounded eventually), ${♢}^{-}{\mathit{\varphi }}_1$ (some time in the past), ${\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ (until), ${\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$ (bounded until), and ${\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_2$ (since). We further may use ${\mathit{\psi }}_1\to {\mathit{\psi }}_2$ as a shortcut for $\neg {\mathit{\psi }}_1\vee {\mathit{\psi }}_2$ .

We impose the constraint that the past operators ${\text{◯}}^{-}$ , ${\square }^{-}$ , ${♢}^{-}$ and $\mathsf{S}$ cannot be nested under the unbounded future operators $\text{◯}$ , □, ♢ and $\mathsf{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{array}{c}\mathit{\varphi }={♢}^{-}\mathrm{(}\mathsf{Overloaded}\mathrm{(}\mathit{x}\mathrm{)}\wedge {\text{◯}}^{-}{♢}^{-}\mathsf{Overloaded}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}\end{array}$$

Note that we can modify our query to speak about a window of 10 time units as follows: $$\begin{array}{c}{\text{◯}}^{-10}♢\mathrm{(}\mathsf{Overloaded}\mathrm{(}\mathit{x}\mathrm{)}\wedge \text{◯}♢\mathsf{Overloaded}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}\end{array}$$ where ${\text{◯}}^{-10}$ abbreviates a sequence of ten ${\text{◯}}^{-}$ 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 $\text{◯}\exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}\vee \exists \mathit{x}.\mathit{B}\mathrm{(}\mathit{x}\mathrm{)}$ is the propositional LTL formula $\text{◯}{\mathit{x}}_1\vee {\mathit{x}}_2$ ).

Remark 2.5 (Choice of operators).

The additional LTL operators $\mathsf{W}$ (weak until), ${\mathsf{W}}^{-}$ (weak since), $\mathsf{R}$ (release), and ${\mathsf{R}}^{-}$ (past release) can be expressed by our set of operators as follows: $$\begin{array}{ll}\hfill & {\mathit{\varphi }}_1\mathsf{W}{\mathit{\varphi }}_2\equiv \mathrm{(}{\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2\mathrm{)}\vee \mathrm{(}\square {\mathit{\varphi }}_1\mathrm{)}\mathrm{,}\\ \hfill & {\mathit{\varphi }}_1{\mathsf{W}}^{-}{\mathit{\varphi }}_2\equiv \mathrm{(}{\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_2\mathrm{)}\vee \mathrm{\left(}{\square }^{-}{\mathit{\varphi }}_1\mathrm{\right)}\mathrm{,}\\ \hfill & {\mathit{\varphi }}_1\mathsf{R}{\mathit{\varphi }}_2\equiv {\mathit{\varphi }}_2\mathsf{W}\mathrm{(}{\mathit{\varphi }}_2\wedge {\mathit{\varphi }}_1\mathrm{)}\mathrm{,}\text{and }\\ \hfill & {\mathit{\varphi }}_1{\mathsf{R}}^{-}{\mathit{\varphi }}_2\equiv {\mathit{\varphi }}_2{\mathsf{W}}^{-}\mathrm{(}{\mathit{\varphi }}_2\wedge {\mathit{\varphi }}_1\mathrm{)}.\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 $\square \mathit{\varphi }$ as a shortcut for $\neg ♢\neg \mathit{\varphi }$ , as it is often done in the literature, but instead treat the operators □ and ${\square }^{\mathit{b}}$ as native members of our query language. Similarly, since the top and bottom concepts ⊤ and ⊥ are not allowed in every DL, ♢ (resp. ${♢}^{\mathit{b}}$ ) cannot be defined using $\mathsf{U}$ (resp. ${\mathsf{U}}^{\mathit{b}}$ ) as usual in LTL ( $♢{\mathit{\varphi }}_1\equiv \mathsf{true}\mathsf{U}{\mathit{\varphi }}_1$ ), unless we allow for negation (where we can express $\mathsf{true}$  using $\exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}\vee \neg \exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}$ ). 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 $\overrightarrow{\mathit{x}}=\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{k}}\mathrm{)}$ and a tuple of individuals $\overrightarrow{\mathit{a}}=\mathrm{(}{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{k}}\mathrm{)}$ , $\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ denotes the Boolean TCQ (BTCQ) resulting from replacing each ${\mathit{x}}_{\mathit{j}}$ by ${\mathit{a}}_{\mathit{j}}$ . A tuple $\overrightarrow{\mathit{a}}$ is an answer to ϕ in a sequence of interpretations $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ at time point p iff $\mathcal{J}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ , where the satisfaction of a BTCQ ϕ by a sequence of interpretations $\mathcal{J}$ is defined by induction on its structure as shown in Table 1. A tuple $\overrightarrow{\mathit{a}}$ is a certain answer to ϕ over $\mathcal{K}$ at time point p, written $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ , iff $\mathcal{J}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ for every model $\mathcal{J}$ of $\mathcal{K}$ that respects rigid predicates.

Table 1

Satisfaction of BTCQs by a sequence of interpretations

ϕ	$\mathcal{J}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff
$\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$	${\mathcal{I}}_{\mathit{p}}\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$
$\neg {\mathit{\varphi }}_1$	$\mathcal{J}\mathrm{,}\mathit{p}⊭{\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$	$\mathcal{J}\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and $\mathcal{J}\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$
${\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$	$\mathcal{J}\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ or $\mathcal{J}\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$
$\text{◯}{\mathit{\varphi }}_1$	$\mathcal{J}\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$
${\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{<}\mathit{n}$ implies $\mathcal{J}\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$
${\text{◯}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ and $\mathcal{J}\mathrm{,}\mathit{p}-1\vDash {\mathit{\varphi }}_1$
${\text{●}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ implies $\mathcal{J}\mathrm{,}\mathit{p}-1\vDash {\mathit{\varphi }}_1$
$\square {\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{\mathit{b}}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{-}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
$♢{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{\mathit{b}}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{-}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}\mathrm{,}\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}\mathcal{J}\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}\mathrm{,}\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}\mathcal{J}$ , $\mathit{j}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{J}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}\mathrm{,}\mathit{k}\mathrm{<}\mathit{j}⩽\mathit{p}\mathrm{,}\mathcal{J}$ , $\mathit{j}\vDash {\mathit{\varphi }}_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 $\mathsf{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 ( ${♢}^{-}\mathrm{(}\mathsf{Start}\mathrm{(}\mathit{s}\mathrm{)}\wedge {\square }^{\mathit{b}}\mathsf{executes}\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{)}\mathrm{)}$ ), 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 $\mathit{i}\mathrm{>}\mathit{n}$ to get a lower complexity in the case where there is no negation in the query. Indeed, in this case, the unknown future ( $\mathit{i}\mathrm{>}\mathit{n}$ ) can be entirely summarized in one time point $\mathit{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 ${\mathit{\varphi }}^{\prime }$ 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 ( $\mathit{i}⩽\mathit{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 ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ 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 ${\mathit{\varphi }}^{\prime }$ 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 $\mathsf{end}\mathrm{(}\mathit{a}\mathrm{)}$ to the last ABox ${\mathcal{A}}_{\mathit{n}}$ of the sequence, where $\mathsf{end}$ and a are both fresh names, and rewrite the query without unbounded operators using the following equivalences: $$\begin{array}{ll}\hfill & {\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1\equiv \text{◯}{\mathit{\varphi }}_1\vee \mathsf{end}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\\ \hfill & {\square }^{\mathit{b}}{\mathit{\varphi }}_1\equiv {\mathit{\varphi }}_1\mathsf{U}\mathrm{(}\mathsf{end}\mathrm{(}\mathit{a}\mathrm{)}\wedge {\mathit{\varphi }}_1\mathrm{)}\mathrm{,}\\ \hfill & {♢}^{\mathit{b}}{\mathit{\varphi }}_1\equiv \neg \mathsf{end}\mathrm{(}\mathit{a}\mathrm{)}\mathsf{U}{\mathit{\varphi }}_1\mathrm{,}\text{ and}\\ \hfill & {\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2\equiv \mathrm{(}{\mathit{\varphi }}_1\wedge \neg \mathsf{end}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}\mathsf{U}{\mathit{\varphi }}_2.\end{array}$$

Fig. 2.

Complexity of BTCQ entailment in ${\text{DL-Lite}}_{\mathcal{R}}$ [19] and ${\mathcal{EL}}_{\perp }$ [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 $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ may be inconsistent even if each KB $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ is consistent. Indeed, in this case, there may not be a sequence of interpretations $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ such that ${\mathcal{I}}_{\mathit{i}}$ is a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ and which also respects rigid predicates. That is why we have to consider as repairs the $\mathcal{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 $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ is a sequence of ABoxes ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ such that $\{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\mid \mathit{\alpha }\in {\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{,}0⩽\mathit{i}⩽\mathit{n}\}$ is a maximal $\mathcal{T}$ -consistent subset of $\{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\mid \mathit{\alpha }\in {\mathcal{A}}_{\mathit{i}}\mathrm{,}0⩽\mathit{i}⩽\mathit{n}\}$ . We denote the set of repairs of $\mathcal{K}$ by  $Rep\mathrm{(}\mathcal{K}\mathrm{)}$ .

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

Example 3.2.

Consider the TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{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}{ll}\hfill & \begin{array}{cc}\hfill \mathcal{T}=& \{\mathsf{WebServer}⊑\mathsf{Server}\mathrm{,}\hfill \\ \hfill & \mathsf{AppServer}⊑\mathsf{Server}\mathrm{,}\hfill \\ \hfill & \mathsf{WebServer}⊑\neg \mathsf{AppServer}\}\hfill \end{array}\\ \hfill & {\mathcal{A}}_0=\{\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\\ \hfill & \begin{array}{cc}\hfill {\mathcal{A}}_1=& \{\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\hfill \\ \hfill & \mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}\hfill \end{array}\end{array}$$ Assume that no predicate is rigid. The TKB $\mathcal{K}$ is inconsistent because the timed assertions $\mathrm{(}\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}1\mathrm{)}$ and $\mathrm{(}\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}1\mathrm{)}$ violate the negative inclusion in $\mathcal{T}$ . Specifically, $\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}$ and $\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}$ cannot both be true at time point 1. It follows that  $\mathcal{K}$ has two repairs that correspond to the two different ways of restoring consistency: ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽1}$ and ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{″}\mathrm{)}}_{0⩽\mathit{i}⩽1}$ , where $$\begin{array}{ll}\hfill & {\mathcal{A}}_0^{\prime }={\mathcal{A}}_0^{″}={\mathcal{A}}_0\\ \hfill & {\mathcal{A}}_1^{\prime }=\{\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}\\ \hfill & {\mathcal{A}}_1^{″}=\{\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}.\end{array}$$

Now assume that $\mathsf{AppServer}$ is rigid. There is then a new reason for $\mathcal{K}$ being inconsistent: the timed assertions $\mathrm{(}\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}0\mathrm{)}$ and $\mathrm{(}\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}1\mathrm{)}$ violate the negative inclusion of $\mathcal{T}$ due to the rigidity of $\mathsf{AppServer}$ , which implies that $\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}$ and $\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}$ should be both entailed at time point 0. Therefore, $\mathcal{K}$ has now the two repairs ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽1}$ and ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{″}\mathrm{)}}_{0⩽\mathit{i}⩽1}$ , where $$\begin{array}{ll}\hfill & {\mathcal{A}}_0^{\prime }=\{\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\\ \hfill & {\mathcal{A}}_1^{\prime }=\{\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}\\ \hfill & {\mathcal{A}}_0^{″}={\mathcal{A}}_0\\ \hfill & {\mathcal{A}}_1^{″}=\{\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}.\end{array}$$ Note that even though ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽1}$ is maximal (adding $\mathsf{WebServer}\mathrm{(}\mathit{a}\mathrm{)}$ to ${\mathcal{A}}_0^{\prime }$ renders the TKB inconsistent),  ${\mathcal{A}}_0^{\prime }$ is not a repair of $⟨\mathcal{T}\mathrm{,}{\mathcal{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 $\overrightarrow{\mathit{a}}$ is an answer to a TCQ ϕ over a TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ at time point p under

AR semantics, written $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ for every repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ ;

IAR semantics, written $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

with ${\mathcal{A}}_{\mathit{i}}^{\text{ir}}={\bigcap }_{{\mathrm{(}{\mathcal{A}}_{\mathit{j}}^{\prime }\mathrm{)}}_{0⩽\mathit{j}⩽\mathit{n}}\in Rep\mathrm{(}\mathcal{K}\mathrm{)}}{\mathcal{A}}_{\mathit{i}}^{\prime }$ for all $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ ;

brave semantics, written $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{brave}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ ,

iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}$ for some repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ .

The following relationships between the semantics, which already hold in the atemporal case, are implied by their definition: $$\begin{array}{rcl}\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}& \Rightarrow & \mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}\\ & \Rightarrow & \mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{brave}}\mathit{\varphi }\mathrm{(}\overrightarrow{\mathit{a}}\mathrm{)}.\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}{ll}\hfill & {\mathit{\varphi }}_1={\square }^{\mathit{b}}\mathrm{(}\exists \mathit{y}.\mathsf{executes}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}\\ \hfill & {\mathit{\varphi }}_2={\square }^{\mathit{b}}\mathrm{(}\exists \mathit{y}.\mathsf{Server}\mathrm{(}\mathit{x}\mathrm{)}\wedge \mathsf{executes}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}\\ \hfill & {\mathit{\varphi }}_3={\square }^{\mathit{b}}\mathrm{(}\exists \mathit{y}.\mathsf{AppServer}\mathrm{(}\mathit{x}\mathrm{)}\wedge \mathsf{executes}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}\end{array}$$ If there are no rigid predicates, the intersection of the repairs is ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽1}$ , with ${\mathcal{A}}_0^{\text{ir}}={\mathcal{A}}_0$ and ${\mathcal{A}}_1^{\text{ir}}=\{\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}$ . We have $\mathcal{K}\mathrm{,}0{\vDash }_{\text{IAR}}{\mathit{\varphi }}_1\mathrm{(}\mathit{a}\mathrm{)}$ , because in every model of the intersection of the repairs a executes b at time point 0 and c at time point 1. For ${\mathit{\varphi }}_2$ , $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{\mathit{\varphi }}_2\mathrm{(}\mathit{a}\mathrm{)}$ , since every model of every repair assigns a to $\mathsf{WebServer}$ at time point 0 and to either $\mathsf{AppServer}$ (in models of ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽1}$ ) or $\mathsf{WebServer}$ (in models of ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{″}\mathrm{)}}_{0⩽\mathit{i}⩽1}$ ) at time point 1. However, $\mathcal{K}\mathrm{,}0{⊭}_{\text{IAR}}{\mathit{\varphi }}_2\mathrm{(}\mathit{a}\mathrm{)}$ . Finally, $\mathcal{K}\mathrm{,}0{⊭}_{\text{brave}}{\mathit{\varphi }}_3\mathrm{(}\mathit{a}\mathrm{)}$ , because no repair entails $\mathsf{AppServer}\mathrm{(}\mathit{a}\mathrm{)}$ at time point 0.

If $\mathsf{AppServer}$ is rigid, the intersection of the repairs is ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽1}$ with ${\mathcal{A}}_0^{\text{ir}}=\{\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}$ and ${\mathcal{A}}_1^{\text{ir}}=\{\mathsf{executes}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\}$ . So, still $\mathcal{K}\mathrm{,}0{\vDash }_{\text{IAR}}{\mathit{\varphi }}_1\mathrm{(}\mathit{a}\mathrm{)}$ . Since every model of every repair assigns a to $\mathsf{Server}$ at time points 0 and 1 (either because a is a web server or because a is an application server), $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{\mathit{\varphi }}_2\mathrm{(}\mathit{a}\mathrm{)}$ , but $\mathcal{K}\mathrm{,}0{⊭}_{\text{IAR}}{\mathit{\varphi }}_2\mathrm{(}\mathit{a}\mathrm{)}$ . Finally, $\mathcal{K}\mathrm{,}0{\vDash }_{\text{brave}}{\mathit{\varphi }}_3\mathrm{(}\mathit{a}\mathrm{)}$ , because every model of $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽1}⟩$ assigns a to $\mathsf{AppServer}$ at any time point by rigidity of $\mathsf{AppServer}$ , but $\mathcal{K}\mathrm{,}0{⊭}_{\text{AR}}{\mathit{\varphi }}_3\mathrm{(}\mathit{a}\mathrm{)}$ .

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 ${\mathcal{I}}_{\mathit{i}}$ of a model $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ of $\mathcal{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_{RC}=N_{RR}=\varnothing$ , then a TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ is consistent iff every $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ is consistent. Moreover, if $\mathcal{K}$ is consistent, for every $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ , ${\mathcal{I}}_{\mathit{p}}^{\prime }$ is a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩$ iff there exists a model $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ of $\mathcal{K}$ such that ${\mathcal{I}}_{\mathit{p}}={\mathcal{I}}_{\mathit{p}}^{\prime }$ .

Proof.

If $N_{RC}=N_{RR}=\varnothing$ , a sequence of interpretations $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ is a model of $\mathcal{K}$ that respects rigid predicates iff it is a model of $\mathcal{K}$ . It follows that $\mathcal{K}$ is consistent iff there exists $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ such that for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , for every $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $\mathcal{T}$ , and for every $\mathit{a}\in N_I$ and all $\mathit{i}\mathrm{,}\mathit{j}⩾0$ , ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{{\mathcal{I}}_{\mathit{j}}}$ . This already establishes one direction of the proposition. We show that also the other direction holds.

Assume that every $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ is consistent, i.e., every $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ has a model. Let $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ be any fixed index and ${\mathcal{I}}_{\mathit{p}}^{\prime }=⟨{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}⟩$ be a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩$ . Since we adopt the unique name assumption and $N_I$ is unbounded, ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ is an infinite set. Moreover, for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , since  ${\mathcal{A}}_{\mathit{i}}$ is finite, by the Löwenheim–Skolem theorem, there exists a model ${\mathcal{I}}_{\mathit{i}}^{″}=⟨{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}^{″}}⟩$ of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ such that  ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}$ is countable. Thus ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}$ can be mapped to  ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ by an injective function ${\mathit{f}}_{\mathit{i}}$ . For every i, we can then build a model ${\mathcal{I}}_{\mathit{i}}^{\prime }=⟨{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}⟩$ of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ such that ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}={\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ . For this, let $\mathrm{\Delta }={\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}\setminus {\mathit{f}}_{\mathit{i}}\mathrm{(}{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}\mathrm{)}$ and select some domain element ${\mathit{d}}_1\in {\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}$ . We define a mapping ${\mathit{m}}_{\mathit{i}}:{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{″}}\to 2^{{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}}$ by setting ${\mathit{m}}_{\mathit{i}}\mathrm{(}\mathit{d}\mathrm{)}=\{{\mathit{f}}_{\mathit{i}}\mathrm{(}\mathit{d}\mathrm{)}\}$ for $\mathit{d}\ne {\mathit{d}}_1$ and ${\mathit{m}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_1\mathrm{)}=\{{\mathit{f}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_1\mathrm{)}\}\cup \mathrm{\Delta }$ . It remains to set ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}={\mathit{f}}_{\mathit{i}}\mathrm{(}{\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}^{″}}\mathrm{)}$ for all $\mathit{a}\in N_I$ , ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}={\bigcup }_{\mathit{d}\in {\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}^{″}}}{\mathit{m}}_{\mathit{i}}\mathrm{(}\mathit{d}\mathrm{)}$ , and ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}=\{\mathrm{(}{\mathit{d}}_1\mathrm{,}{\mathit{d}}_2\mathrm{)}\in {\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\times {\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\mid \mathrm{(}{\mathit{d}}_1^{\prime }\mathrm{,}{\mathit{d}}_2^{\prime }\mathrm{)}\in {\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}^{″}}\mathrm{,}{\mathit{d}}_1\in {\mathit{m}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_1^{\prime }\mathrm{)}\mathrm{,}{\mathit{d}}_2\in {\mathit{m}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_2^{\prime }\mathrm{)}\}$ . Since ${\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}={\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , there exists a bijection ${\mathit{b}}_{\mathit{i}}:{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\to {\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ such that for all $\mathit{a}\in N_I$ , ${\mathit{b}}_{\mathit{i}}\mathrm{(}{\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\mathrm{)}={\mathit{a}}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ .

Using these bijections, we can construct a model $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ of $\mathcal{K}$ based on the interpretations ${\mathcal{I}}_0^{\prime }\mathrm{,}\dots \mathrm{,}{\mathcal{I}}_{\mathit{n}}^{\prime }$ as follows. For every $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{I}}_{\mathit{i}}={\mathcal{I}}_{\mathit{p}}^{\prime }$ , ${\mathcal{I}}_{\mathit{p}}={\mathcal{I}}_{\mathit{p}}^{\prime }$ , and for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ such that $\mathit{i}\ne \mathit{p}$ , ${\mathcal{I}}_{\mathit{i}}=⟨{\mathrm{\Delta }}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}}⟩$ , where ${·}^{{\mathcal{I}}_{\mathit{i}}}$ is defined by ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{{\mathcal{I}}_{\mathit{p}}^{\prime }}$ for every $\mathit{a}\in N_I$ , ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}=\{{\mathit{b}}_{\mathit{i}}\mathrm{(}\mathit{d}\mathrm{)}\mid \mathit{d}\in {\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\}$ for every $\mathit{A}\in N_C$ , and ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}=\{\mathrm{(}{\mathit{b}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_1\mathrm{)}\mathrm{,}{\mathit{b}}_{\mathit{i}}\mathrm{(}{\mathit{d}}_2\mathrm{)}\mathrm{)}\mid \mathrm{(}{\mathit{d}}_1\mathrm{,}{\mathit{d}}_2\mathrm{)}\in {\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}\}$ . Note that this construction ensures ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{{\mathcal{I}}_{\mathit{j}}}$ for all $\mathit{i}\mathrm{,}\mathit{j}⩾0$ . Furthermore, one easily establishes that for all $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , and for $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{I}}_{\mathit{i}}$ is a model of $\mathcal{T}$ . We obtain that $\mathcal{J}$ is a model of  $\mathcal{K}$ such that ${\mathcal{I}}_{\mathit{p}}={\mathcal{I}}_{\mathit{p}}^{\prime }$ .  □

It follows that, if $N_{RC}=N_{RR}=\varnothing$ , CQs can be answered at time point p by answering them over the KB $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩$ . Proposition 3.6.

If $N_{RC}=N_{RR}=\varnothing$ , then for every BCQ $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ and $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ , $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩\vDash \mathit{q}$ .

Proof.

$\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff for every model $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ of  $\mathcal{K}$ that respects rigid predicates, ${\mathcal{I}}_{\mathit{p}}\vDash \mathit{q}$ . By Proposition 3.5, this is the case iff for every model ${\mathcal{I}}_{\mathit{p}}$ of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩$ , ${\mathcal{I}}_{\mathit{p}}\vDash \mathit{q}$ , which is equivalent to $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩\vDash \mathit{q}$ .  □

4. Complexity analysis overview

In the next four sections, we investigate the complexity of inconsistency-tolerant BTCQ entailment in ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ . 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 ${\text{DL-Lite}}_{\mathcal{R}}$ and in [20] for $\mathcal{EL}$ (cf. Section 2, Fig. 2). Furthermore, it has also been shown in [17,18] that in ${\text{DL-Lite}}_{\mathcal{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, ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{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.

• ${\mathrm{\Delta }}_2^{\mathit{p}}[\mathit{O}\mathrm{(}log\mathit{n}\mathrm{)}]$ : problems solvable in polynomial time with at most logarithmically many calls to an NP oracle.

• ${\mathrm{\Sigma }}_2^{\mathit{p}}$ : problems solvable in non-deterministic polynomial time with an NP oracle.

• ${\mathrm{\Pi }}_2^{\mathit{p}}$ : problems whose complement is in  ${\mathrm{\Sigma }}_2^{\mathit{p}}$ .

• ${\mathsf{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 ${\mathsf{AC}}^0\subseteq \mathrm{\text{P}}$ .

• ALogTime: problems solvable in logarithmic time by a random access alternating Turing machine. We have ${\mathsf{AC}}^0\subseteq \mathrm{\text{AL}}\mathrm{\text{OG}}\mathrm{\text{T}}\mathrm{\text{IME}}\subseteq \mathrm{\text{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, $\mathcal{L}$ is a DL which is interpreted w.r.t. standard interpretations, as defined in Section 2. We will consider in particular the cases $\mathcal{L}$ = ${\text{DL-Lite}}_{\mathcal{R}}$ and $\mathcal{L}$ = ${\mathcal{EL}}_{\perp }$ . Furthermore, we assume $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{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 $\mathsf{ARNonEntailment}$ decides whether ϕ is not entailed by  $\mathcal{K}$ at time point p under AR semantics, and is defined as follows.

Guess a sequence ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of ABoxes.

Verify that ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is a repair of $\mathcal{K}$ and that $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}⊭\mathit{\varphi }$ .

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 $\mathsf{braveEntailment}$ decides whether ϕ is entailed by  $\mathcal{K}$ at time point p under brave semantics, and is defined as follows.

1. Guess a sequence ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of ABoxes.

2. Verify that ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is a repair of $\mathcal{K}$ and that $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ .

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

Guess

• a set $\mathcal{B}=\{\mathrm{(}{\mathit{\alpha }}_1\mathrm{,}{\mathit{i}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\mathit{\alpha }}_{\mathit{m}}\mathrm{,}{\mathit{i}}_{\mathit{m}}\mathrm{)}\}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of timed assertions, together with

• m subsets of the data ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime 1}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\mathrm{,}\dots \mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime \mathit{m}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ such that for every $\mathit{j}\in [1\mathrm{,}\mathit{m}]$ , ${\mathit{\alpha }}_{\mathit{j}}\notin {\mathcal{A}}_{{\mathit{i}}_{\mathit{j}}}^{\prime \mathit{j}}$ .

Verify that

• for every $\mathit{j}\in [1\mathrm{,}\mathit{m}]$ , ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime \mathit{j}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is a repair of $\mathcal{K}$ , and

• $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus \mathcal{B}⟩\mathrm{,}\mathit{p}⊭\mathit{\varphi }$ .

Note that $\mathit{m}⩽|{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{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 $\mathrm{(}{\mathit{\alpha }}_{\mathit{j}}\mathrm{,}{\mathit{i}}_{\mathit{j}}\mathrm{)}$ there exists a repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime \mathit{j}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ that does not contain $\mathrm{(}{\mathit{\alpha }}_{\mathit{j}}\mathrm{,}{\mathit{i}}_{\mathit{j}}\mathrm{)}$ , then $\mathrm{(}{\mathit{\alpha }}_{\mathit{j}}\mathrm{,}{\mathit{i}}_{\mathit{j}}\mathrm{)}$ is not in the intersection of the repairs of  $\mathcal{K}$ . Thus ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus \{\mathrm{(}{\mathit{\alpha }}_1\mathrm{,}{\mathit{i}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\mathit{\alpha }}_{\mathit{m}}\mathrm{,}{\mathit{i}}_{\mathit{m}}\mathrm{)}\}$ is a superset of the intersection ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of the repairs of  $\mathcal{K}$ . It follows that if $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus \mathcal{B}⟩\mathrm{,}\mathit{p}⊭\mathit{\varphi }$ , then $\mathcal{K}\mathrm{,}\mathit{p}{⊭}_{\text{IAR}}\mathit{\varphi }$ . For the other direction, assume that $\mathcal{K}\mathrm{,}\mathit{p}{⊭}_{\text{IAR}}\mathit{\varphi }$ , and let $\mathcal{B}=\{\mathrm{(}{\mathit{\alpha }}_1\mathrm{,}{\mathit{i}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\mathit{\alpha }}_{\mathit{m}}\mathrm{,}{\mathit{i}}_{\mathit{m}}\mathrm{)}\}={\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus {\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ . For each $\mathrm{(}{\mathit{\alpha }}_{\mathit{j}}\mathrm{,}{\mathit{i}}_{\mathit{j}}\mathrm{)}$ , there exists a repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime \mathit{j}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ that does not contain the timed assertion $\mathrm{(}{\mathit{\alpha }}_{\mathit{j}}\mathrm{,}{\mathit{i}}_{\mathit{j}}\mathrm{)}$ , and $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus \mathcal{B}⟩$ , $\mathit{p}⊭\mathit{\varphi }$ .

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 ${\mathcal{EL}}_{\perp }$ and in [19] for ${\text{DL-Lite}}_{\mathcal{R}}$ .

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

For every $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{j}\mathrm{)}\in {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ , check whether $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{j}\mathrm{)}$ belongs to a minimal inconsistent subset of  $\mathcal{K}$ by asking an oracle whether there exists a $\mathcal{T}$ -inconsistent set of timed assertions $\mathcal{B}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ such that $\mathcal{B}\setminus \{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{j}\mathrm{)}\}$ 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 $\mathcal{K}$ is obtained by removing the minimal inconsistent subsets of $\mathcal{K}$ . Let $\mathcal{B}\subseteq {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ be a minimal inconsistent subset of $\mathcal{K}$ and $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\in \mathcal{B}$ . Since $\mathcal{B}\setminus \{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\}$ is consistent, $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}$ is not in the repairs that contain $\mathcal{B}\setminus \{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\}$ . In the other direction, if a timed assertion $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}$ does not appear in some repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ , since the repairs are maximal, ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\cup \{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\}$ is inconsistent, and $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}$ occurs in some minimal inconsistent subset of $\mathcal{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  $\mathcal{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{\mathcal{K}}$ based on  $\mathcal{K}$ . For $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ , $\tilde{\mathcal{K}}=⟨\tilde{\mathcal{T}}\mathrm{,}\tilde{\mathcal{A}}⟩$ is defined in Fig. 4. We first show a correspondence between the models of $\mathcal{K}$ that respect rigid predicates and the models of $\tilde{\mathcal{K}}$ .

Fig. 4.

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

Lemma 6.2.

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

Proof.

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

${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{\tilde{\mathcal{I}}}$ for every $\mathit{a}\in N_I$ ,

${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{A}}^{\tilde{\mathcal{I}}}$ for every $\mathit{A}\in N_{RC}$ ,

${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{R}}^{\tilde{\mathcal{I}}}$ for every $\mathit{R}\in N_{RR}$ ,

${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{A}}_{\mathit{i}}^{\tilde{\mathcal{I}}}$ for every $\mathit{A}\in N_C\setminus N_{RC}$ , and

${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{R}}_{\mathit{i}}^{\tilde{\mathcal{I}}}$ for every $\mathit{R}\in N_R\setminus N_{RR}$ ,

and for every $\mathit{i}\mathrm{>}\mathit{n}$ , we set

• ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{a}}^{\tilde{\mathcal{I}}}$ for every $\mathit{a}\in N_I$ ,

• ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{A}}^{\tilde{\mathcal{I}}}$ for every $\mathit{A}\in N_{RC}$ ,

• ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{R}}^{\tilde{\mathcal{I}}}$ for every $\mathit{R}\in N_{RR}$ ,

• ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{A}}_{\mathit{n}+1}^{\tilde{\mathcal{I}}}$ for every $\mathit{A}\in N_C\setminus N_{RC}$ , and

• ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}={\mathit{R}}_{\mathit{n}+1}^{\tilde{\mathcal{I}}}$ for every $\mathit{R}\in N_R\setminus N_{RR}$ .

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

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

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

For every $\mathit{i}\mathrm{>}\mathit{n}+1$ , ${\mathcal{I}}_{\mathit{i}}={\mathcal{I}}_{\mathit{n}+1}$ is a model of $\mathcal{T}$ .

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

We obtain that $\mathsf{temp}\mathrm{(}\tilde{\mathcal{I}}\mathrm{)}$ is a model of $\mathcal{K}$ that respects rigid predicates.

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

${\mathit{a}}^{\tilde{\mathcal{I}}}={\mathit{a}}^{{\mathcal{I}}_0}$ ( $={\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}$ for every $\mathit{i}⩾0$ ) for every $\mathit{a}\in N_I$ ,

${\mathit{A}}^{\tilde{\mathcal{I}}}={\mathit{A}}^{{\mathcal{I}}_0}$ for every $\mathit{A}\in N_{RC}$ ,

${\mathit{R}}^{\tilde{\mathcal{I}}}={\mathit{R}}^{{\mathcal{I}}_0}$ for every $\mathit{R}\in N_{RR}$ ,

${\mathit{A}}_{\mathit{i}}^{\tilde{\mathcal{I}}}={\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}$ for every $\mathit{A}\in N_C\setminus N_{RC}$ and $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , and

${\mathit{R}}_{\mathit{i}}^{\tilde{\mathcal{I}}}={\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}$ for every $\mathit{R}\in N_R\setminus N_{RR}$ and $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ .

Again, we show that $\tilde{\mathcal{I}}$ is a model of  $\tilde{\mathcal{K}}$ by considering the ABox and the TBox separately.

1. $\tilde{\mathcal{I}}$ is a model of $\tilde{\mathcal{A}}$ . If $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in \tilde{\mathcal{A}}$ with $\mathit{A}\in N_{RC}$ , then ${\mathit{a}}^{\tilde{\mathcal{I}}}={\mathit{a}}^{{\mathcal{I}}_0}\in {\mathit{A}}^{\tilde{\mathcal{I}}}$ , and if ${\mathit{A}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}\in \tilde{\mathcal{A}}$ for some $\mathit{A}\notin N_{RC}$ , then $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in {\mathcal{A}}_{\mathit{i}}$ and ${\mathit{a}}^{\tilde{\mathcal{I}}}={\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}\in {\mathit{A}}^{\tilde{\mathcal{I}}}$ . The situation is the same for the role assertions in $\tilde{\mathcal{A}}$ .

2. $\tilde{\mathcal{I}}$ is a model of $\tilde{\mathcal{T}}$ . If we rename the non-rigid predicates, $\mathsf{RenameNotRig}\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{,}\mathit{i}\mathrm{)}$ coincides with $\tilde{\mathcal{I}}$ on the interpretation of all rigid predicates and all  ${\mathit{A}}_{\mathit{i}}$ and ${\mathit{R}}_{\mathit{i}}$ . Since each ${\mathcal{I}}_{\mathit{i}}$ is a model of $\mathcal{T}$ , each interpretation $\mathsf{RenameNotRig}\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{,}\mathit{i}\mathrm{)}$ is a model of $\mathsf{RenameNotRig}\mathrm{(}\mathcal{T}\mathrm{,}\mathit{i}\mathrm{)}$ , and since $\tilde{\mathcal{T}}$ does not contain any axiom that involves two non-rigid predicates ${\mathit{X}}_{\mathit{i}}$ and ${\mathit{X}}_{\mathit{j}}$ with $\mathit{i}\ne \mathit{j}$ , each $\mathsf{RenameNotRig}\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{,}\mathit{i}\mathrm{)}$ is a model of $\tilde{\mathcal{T}}$ . It follows that $\tilde{\mathcal{I}}$ is a model of $\tilde{\mathcal{T}}$ .

We thus obtain a direct correspondence between the models of $\mathcal{K}$ and those of $\tilde{\mathcal{K}}$ , and that $\mathcal{K}$ is satisfiable iff $\tilde{\mathcal{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  $\mathcal{L}$ , consistency checking of $\mathcal{L}$ -KBs is inP, then consistency checking of $\mathcal{L}$ -TKBs is inPas well.

Proof.

By Lemma 6.2, the TKB  $\mathcal{K}$ is consistent iff the KB  $\tilde{\mathcal{K}}$ is consistent. If consistency checking is in P for $\mathcal{L}$ -KBs, the consistency of $\mathcal{K}$ can then be checked in time polynomial in the size of $\tilde{\mathcal{T}}$ and $\tilde{\mathcal{A}}$ . Since the size of $\tilde{\mathcal{T}}$ is polynomial in $|\mathcal{T}|$ and n, and the size of $\tilde{\mathcal{A}}$ is at most the size of ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{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  $\mathcal{L}$ , consistency checking of $\mathcal{L}$ -TKBs is inP, then repair recognition, i.e., deciding whether a sequence of ABoxes ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is a repair of  $\mathcal{K}$ , is inP.

Proof.

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

For every i, check that ${\mathcal{A}}_{\mathit{i}}^{\prime }\subseteq {\mathcal{A}}_{\mathit{i}}$ .

Check that ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is $\mathcal{T}$ -consistent.

For every $\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{j}\mathrm{)}\in {\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\setminus {\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ , check that ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\cup \{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{j}\mathrm{)}\}$ is $\mathcal{T}$ -inconsistent.  □

Note that Lemmas 6.3 and 6.4 apply to ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ 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 $\mathsf{ARNonEntailment}$ , $\mathsf{IARNonEntailment}$ and $\mathsf{braveEntailment}$ all run in NPSpace=PSpace.  □

Proposition 6.5 applies to ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ in all cases except for ${\mathcal{EL}}_{\perp }$ with rigid roles, for which BTCQ entailment under classical semantics is coNExpTime-hard [20].

Proposition 6.6.

BTCQ entailment from an ${\mathcal{EL}}_{\perp }$ -TKB under AR, IAR, and brave semantics is in coNExpTime w.r.t. combined complexity, even if $N_{RR}\ne \varnothing$ .

Proof.

For the AR and IAR semantics, we modify the procedures $\mathsf{ARNonEntailment}$ and $\mathsf{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 $\mathcal{K}\mathrm{,}\mathit{p}{⊭}_{\text{brave}}\mathit{\varphi }$ . For every subset ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ , guess either “not a repair” or a certificate of the non-entailment of ϕ from $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ at time point p. Note that there are $2^{|{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}|}$ such subsets. For every such subset, verify in ExpTime whether it is indeed not a repair, or whether $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}⊭\mathit{\varphi }$ .  □

The matching PSpace and coNExpTime combined complexity lower bounds for ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{R}}$ follow from the consistent case (cf. Section 2).

6.3. Data complexity for ${\mathcal{EL}}_{\perp }$ -TKBs

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

Proposition 6.7.

BTCQ entailment from an ${\mathcal{EL}}_{\perp }$ -TKB with $N_{RC}=N_{RR}=\varnothing$ 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 $\mathsf{ARNonEntailment}$ , $\mathsf{IARNonEntailment}$ , and $\mathsf{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 ${\mathcal{EL}}_{\perp }$ -TKB with $N_{RC}\ne \varnothing$ and $N_{RR}\ne \varnothing$ is

in co NP w.r.t. data complexity under AR and IAR semantics, and

in ${\mathrm{\Sigma }}_2^{\mathit{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 $\mathsf{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 ${\mathcal{EL}}_{\perp }$ -TKB with $N_{RC}\ne \varnothing$ is

co NP -hard w.r.t. data complexity under AR and IAR semantics, and

${\mathrm{\Sigma }}_2^{\mathit{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 ${\mathrm{\Pi }}_2^{\mathit{p}}$ -hard by reduction from ${\mathrm{QBF}}_{2\mathrm{,}\forall }$ .

Let $\mathrm{\Phi }=\forall {\mathit{x}}_1\dots {\mathit{x}}_{\mathit{m}}\exists {\mathit{y}}_1\dots {\mathit{y}}_{\mathit{r}}\mathit{\phi }$ be a ${\mathrm{QBF}}_{2\mathrm{,}\forall }$ -formula, where $\mathit{\phi }={\bigwedge }_{\mathit{i}=0}^{\mathit{h}}{\ell }_{\mathit{i}}^0\vee {\ell }_{\mathit{i}}^1\vee {\ell }_{\mathit{i}}^2$ is a 3-CNF formula over the propositional variables $\{{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{m}}\mathrm{,}{\mathit{y}}_1\mathrm{,}\dots \mathrm{,}{\mathit{y}}_{\mathit{r}}\}$ . Based on Φ, define the TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽3\mathit{h}+2}⟩$ and the TCQ ϕ as follows, where $N_{RC}=\{\mathsf{T}\}$ . $$\begin{array}{ll}\hfill & \begin{array}{cc}\hfill \mathcal{T}=& \{\exists \mathsf{Pos}.\mathsf{T}⊑\mathsf{Sat}\mathrm{,}\exists \mathsf{Neg}.\mathsf{F}⊑\mathsf{Sat}\mathrm{,}\hfill \\ \hfill & \exists \mathsf{FromPos}.\mathsf{Sat}⊑\mathsf{T}\mathrm{,}\exists \mathsf{FromNeg}.\mathsf{Sat}⊑\mathsf{F}\mathrm{,}\hfill \\ \hfill & \exists \mathsf{FromY}.\mathsf{Sat}⊑\mathsf{T}\mathrm{,}\mathsf{T}\sqcap \mathsf{F}⊑\perp \mathrm{,}\hfill \\ \hfill & \mathsf{T}\sqcap \exists \mathsf{ValY}.\mathsf{T}⊑\perp \}\hfill \end{array}\\ \hfill & \begin{array}{cc}\hfill \mathit{\varphi }=& \neg {\square }^{\mathit{b}}\mathrm{(}\mathsf{NotFirst}\mathrm{(}\mathit{c}\mathrm{)}\vee \mathsf{Sat}\mathrm{(}\mathit{c}\mathrm{)}\hfill \\ \hfill & \vee \text{◯}\mathsf{Sat}\mathrm{(}\mathit{c}\mathrm{)}\vee \text{◯}\text{◯}\mathsf{Sat}\mathrm{(}\mathit{c}\mathrm{)}\mathrm{)}\hfill \end{array}\end{array}$$ For each clause ${\ell }_{\mathit{i}}^0\vee {\ell }_{\mathit{i}}^1\vee {\ell }_{\mathit{i}}^2$ , i.e., for every $\mathit{i}\in [0\mathrm{,}\mathit{h}]$ , we define the following three ABoxes ${\mathcal{A}}_{3\mathit{i}+\mathit{k}}$ ( $0⩽\mathit{k}⩽2$ ): $$\begin{array}{ll}\hfill & {\mathcal{A}}_{3\mathit{i}+0}=\mathcal{B}\cup {\mathcal{B}}_{3\mathit{i}+0}\\ \hfill & {\mathcal{A}}_{3\mathit{i}+\mathit{k}}=\mathcal{B}\cup {\mathcal{B}}_{3\mathit{i}+\mathit{k}}\cup \{\mathsf{NotFirst}\mathrm{(}\mathit{c}\mathrm{)}\}\mathrm{,}1⩽\mathit{k}⩽2\mathrm{,}\end{array}$$ where $$\begin{array}{ll}\hfill & \begin{array}{cc}\hfill \mathcal{B}=& \{\mathsf{T}\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mathrm{,}\mathsf{F}\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mid 1⩽\mathit{j}⩽\mathit{m}\}\hfill \\ \hfill & \cup \{\mathsf{ValY}\mathrm{(}{\mathit{y}}_{\mathit{j}}\mathrm{,}\neg {\mathit{y}}_{\mathit{j}}\mathrm{)}\mathrm{,}\mid 1⩽\mathit{j}⩽\mathit{r}\}\hfill \end{array}\\ \hfill & {\mathcal{B}}_{3\mathit{i}+\mathit{k}}=\{\mathsf{Pos}\mathrm{(}\mathit{c}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mathrm{,}\mathsf{FromPos}\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}\}\text{if }{\ell }_{\mathit{i}}^{\mathit{k}}={\mathit{x}}_{\mathit{j}}\\ \hfill & {\mathcal{B}}_{3\mathit{i}+\mathit{k}}=\{\mathsf{Neg}\mathrm{(}\mathit{c}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mathrm{,}\mathsf{FromNeg}\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}\}\text{if }{\ell }_{\mathit{i}}^{\mathit{k}}=\neg {\mathit{x}}_{\mathit{j}}\\ \hfill & {\mathcal{B}}_{3\mathit{i}+\mathit{k}}=\{\mathsf{FromY}\mathrm{(}{\mathit{y}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}\}\text{if }{\ell }_{\mathit{i}}^{\mathit{k}}={\mathit{y}}_{\mathit{j}}\\ \hfill & {\mathcal{B}}_{3\mathit{i}+\mathit{k}}=\{\mathsf{FromY}\mathrm{(}\neg {\mathit{y}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}\}\text{if }{\ell }_{\mathit{i}}^{\mathit{k}}=\neg {\mathit{y}}_{\mathit{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 $\mathcal{K}\mathrm{,}0{⊭}_{\mathit{\text{brave}}}\mathit{\varphi }$ .

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

Each clause ${\ell }_{\mathit{i}}^0\vee {\ell }_{\mathit{i}}^1\vee {\ell }_{\mathit{i}}^2$ is represented by the three consecutive ABoxes ${\mathcal{A}}_{3\mathit{i}+0}\mathrm{,}{\mathcal{A}}_{3\mathit{i}+1}$ and ${\mathcal{A}}_{3\mathit{i}+2}$ , which each encode a literal of the clause in the ${\mathcal{B}}_{3\mathit{i}+\mathit{k}}$ part. The concept $\mathsf{NotFirst}$ is used to indicate that the literal represented is not the first of the clause. The concept $\mathsf{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 ${\mathit{x}}_{\mathit{j}}$ (resp. $\neg {\mathit{x}}_{\mathit{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 {\mathit{x}}_{\mathit{j}}$ , since the literals ${\mathit{x}}_{\mathit{j}}$ and $\neg {\mathit{x}}_{\mathit{j}}$ are represented with only one individual ${\mathit{x}}_{\mathit{j}}$ , the condition is that ${\mathit{x}}_{\mathit{j}}$ is assigned to false).  □

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

It remains to show the data complexity results for ${\text{DL-Lite}}_{\mathcal{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_{RC}=N_{RR}=\varnothing$ .

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 ${\text{DL-Lite}}_{\mathcal{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 $\mathit{\varphi }={\square }^{-}\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ , 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_{RC}\ne \varnothing$ , then brave BTCQ entailment from ${\mathit{\text{DL-Lite}}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$ -TKBs by reduction from SAT. Let ${\mathit{c}}_0\wedge \cdots \wedge {\mathit{c}}_{\mathit{n}}$ be a CNF formula over variables ${\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{m}}$ . We define the following problem of BTCQ entailment under brave semantics, with two rigid concepts $\mathsf{T}$ and $\mathsf{F}$ . Let $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ be such that: $$\begin{array}{ll}\hfill & \begin{array}{cc}\hfill \mathcal{T}=& \{\exists \mathsf{Pos}⊑\mathsf{Sat}\mathrm{,}\exists \mathsf{Neg}⊑\mathsf{Sat}\mathrm{,}\hfill \\ \hfill & \exists {\mathsf{Pos}}^{-}⊑\mathsf{T}\mathrm{,}\exists {\mathsf{Neg}}^{-}⊑\mathsf{F}\mathrm{,}\mathsf{T}⊑\neg \mathsf{F}\}\hfill \end{array}\\ \hfill & \begin{array}{cc}\hfill {\mathcal{A}}_{\mathit{i}}=& \{\mathsf{Pos}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mid {\mathit{x}}_{\mathit{j}}\in {\mathit{c}}_{\mathit{i}}\}\hfill \\ \hfill & \cup \{\mathsf{Neg}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mid \neg {\mathit{x}}_{\mathit{j}}\in {\mathit{c}}_{\mathit{i}}\}\text{for }0⩽\mathit{i}⩽\mathit{n}\hfill \end{array}\end{array}$$ Let $\mathit{\varphi }={\square }^{-}\mathsf{Sat}\mathrm{(}\mathit{a}\mathrm{)}$ . We show that ${\mathit{c}}_0\wedge \cdots \wedge {\mathit{c}}_{\mathit{n}}$ is satisfiable iff $\mathcal{K}\mathrm{,}\mathit{n}{\vDash }_{\text{brave}}\mathit{\varphi }$ . Note that ϕ does not contain negation. Indeed, since $\mathsf{T}$ and $\mathsf{F}$ are rigid, a repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ is such that each ${\mathit{x}}_{\mathit{j}}$ has either only $\mathsf{Pos}$ or only $\mathsf{Neg}$ incoming edges in ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ , i.e., ${\mathit{x}}_{\mathit{j}}$ occurs either only in assertions of the form $\mathsf{Pos}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}$ or only in assertions of the form $\mathsf{Neg}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}$ . We can thus define a valuation ν of the variables such that $\mathit{\nu }\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}=\mathsf{true}$ if ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ does not contain a timed assertion of the form $\mathrm{(}\mathsf{Neg}\mathrm{(}\mathit{c}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\mathrm{,}\mathit{k}\mathrm{)}$ , and $\mathit{\nu }\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}=\mathsf{false}$ otherwise. The clause ${\mathit{c}}_{\mathit{i}}$ is satisfied by ν iff there exists ${\mathit{x}}_{\mathit{j}}$ such that either ${\mathit{x}}_{\mathit{j}}\in {\mathit{c}}_{\mathit{i}}$ and $\mathit{\nu }\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}=\mathsf{true}$ or $\neg {\mathit{x}}_{\mathit{j}}\in {\mathit{c}}_{\mathit{i}}$ and $\mathit{\nu }\mathrm{(}{\mathit{x}}_{\mathit{j}}\mathrm{)}=\mathsf{false}$ , that is, iff there exists ${\mathit{x}}_{\mathit{j}}$ such that either $\mathsf{Pos}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\in {\mathcal{A}}_{\mathit{i}}^{\prime }$ or $\mathsf{Neg}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{j}}\mathrm{)}\in {\mathcal{A}}_{\mathit{i}}^{\prime }$ , which holds exactly iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{i}\vDash \mathsf{Sat}\mathrm{(}\mathit{a}\mathrm{)}$ . It follows that ${\mathit{c}}_0\wedge \cdots \wedge {\mathit{c}}_{\mathit{n}}$ is satisfiable iff there exists a repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ that entails ϕ at time point n.  □

For the case $N_{RC}=N_{RR}=\varnothing$ , 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_{RR}\ne \varnothing$ . The reason is that, in ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{R}}$  syntax, the following holds: for every ${\text{DL-Lite}}_{\mathcal{R}}$  TBox  $\mathcal{T}$ , the size of a minimal $\mathcal{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 ${\mathit{\text{DL-Lite}}}_{\mathcal{R}}$ -TKB under IAR semantics is in P w.r.t. data complexity, even if $N_{RR}\ne \varnothing$ and $N_{RC}\ne \varnothing$ .

Proof.

The size of the minimal $\mathcal{T}$ -inconsistent subsets of ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is bounded by 2. We can thus skip the first step of the procedure $\mathsf{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 $\mathcal{L}$ , if $\mathcal{L}$ has the canonical model property for CQ answering over KBs, then $\mathcal{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 $\mathcal{K}$ can be reduced to BCQ entailment from the KB $\tilde{\mathcal{K}}$ defined Section 6, Fig. 4. For this, we define a similar transformation for BCQs as we did for TKBs. Let $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ be a BCQ and $\mathit{p}⩾0$ be a time point. Consider $$\begin{array}{c}{\tilde{\mathit{q}}}_{\mathit{p}}=\mathsf{RenameNotRig}\mathrm{(}\mathit{q}\mathrm{,}\mathit{p}\mathrm{)}\end{array}$$ where $\mathsf{RenameNotRig}\mathrm{(}\mathit{q}\mathrm{,}\mathit{p}\mathrm{)}$ replaces every non-rigid predicate X in q by ${\mathit{X}}_{\mathit{p}}$ if $\mathit{p}⩽\mathit{n}$ , and by ${\mathit{X}}_{\mathit{n}+1}$ otherwise.

Lemma 7.1.

$\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff $\tilde{\mathcal{K}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ .

Proof.

The following proof is written for the case where $\mathit{p}\in [0\mathrm{,}\mathit{n}+1]$ . For the case $\mathit{p}\mathrm{>}\mathit{n}+1$ , p is replaced by $\mathit{n}+1$ in the predicates names.

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

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

Moreover, the size of ${\tilde{\mathit{q}}}_{\mathit{p}}$ is the same as q. We thus obtain the following lemma.

Lemma 7.2.

If BCQ entailment from an  $\mathcal{L}$ -KB is inPw.r.t. KB complexity, respectively inNPw.r.t. combined complexity, then so is BCQ entailment from an  $\mathcal{L}$ -TKB.

Proof.

If deciding whether $\tilde{\mathcal{K}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ is polynomial both in $|\tilde{\mathcal{T}}|$ and in $|\tilde{\mathcal{A}}|$ , then it is polynomial in $|\mathcal{T}|$ and $|{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}|$ . It follows that deciding whether $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ is in P w.r.t. KB complexity.

Moreover, if deciding whether $\tilde{\mathcal{K}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ is in NP w.r.t.  $|\tilde{\mathcal{T}}|$ , $|\tilde{\mathcal{A}}|$ and $|{\tilde{\mathit{q}}}_{\mathit{p}}|$ , then verifying a certificate that $\tilde{\mathcal{K}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ can be done in polynomial time w.r.t.  $|\tilde{\mathcal{T}}|$ , $|\tilde{\mathcal{A}}|$ and $|{\tilde{\mathit{q}}}_{\mathit{p}}|$ , so in polynomial time w.r.t.  $|\mathcal{T}|$ , n, $|{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}|$ and $|\mathit{q}|$ . It follows that deciding whether $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{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 $\mathcal{L}$ has the canonical model property for BCQ entailment iff for every consistent $\mathcal{L}$ -KB $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ , there exists a model ${\mathcal{I}}_{⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩}$ such that for every BCQ q, $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩\vDash \mathit{q}$ iff ${\mathcal{I}}_{⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩}\vDash \mathit{q}$ . We call ${\mathcal{I}}_{⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩}$ the canonical model of KB $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ .

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

Note that it is justified to speak of the canonical model of a KB or TKB $\mathcal{K}$ because such a model can be homomorphically mapped into any other model of  $\mathcal{K}$ . Indeed, for every assertion α built over $N_I$ , $N_C$ and $N_R$ , if α holds in the canonical model of $\mathcal{K}$ then it also holds in every model of $\mathcal{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 $\mathcal{L}$ has the canonical model property for BCQ entailment, then $\mathcal{L}$ also has the canonical model property for entailment of BTCQs without negation.

Proof (Sketch).

Let ${\tilde{\mathcal{I}}}_{\tilde{\mathcal{K}}}$ be the canonical model of $\tilde{\mathcal{K}}$ and ${\mathcal{J}}_{\mathcal{K}}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}=\mathsf{temp}\mathrm{(}{\tilde{\mathcal{I}}}_{\tilde{\mathcal{K}}}\mathrm{)}$ . We show that ${\mathcal{J}}_{\mathcal{K}}$ is the canonical model of $\mathcal{K}$ for BTCQs without negation, that is, for every BTCQ ϕ that does not contain any negation, $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ .

Since ${\mathcal{J}}_{\mathcal{K}}$ is a model of $\mathcal{K}$ that respects rigid predicates, if $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ then ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ . For the other direction, we show in the appendix by induction on the structure of ϕ that if ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ , then $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ . The interesting case is when ϕ is a BCQ. For a BCQ q, by Lemma 7.1, $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff $\tilde{\mathcal{K}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ , which is exactly the case iff ${\tilde{\mathcal{I}}}_{\tilde{\mathcal{K}}}\vDash {\tilde{\mathit{q}}}_{\mathit{p}}$ . By construction of ${\mathcal{J}}_{\mathcal{K}}$ , it follows that $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{q}$ .  □

Remark 7.5.

If ϕ contains negation, the preceding argument fails and ${\mathcal{J}}_{\mathcal{K}}$ is not a canonical model for TCQ answering, i.e., ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \neg \mathit{\varphi }$ does not guarantee that $\mathcal{J}\mathrm{,}\mathit{p}⊭\mathit{\varphi }$ for every model $\mathcal{J}$ that respects rigid predicates. As an example, consider the empty TKB, i.e. $\mathcal{T}=\varnothing$ and ${\mathcal{A}}_{\mathit{i}}=\varnothing$ for every $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ . We have ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}0⊭\exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}$ , but we can easily construct a model $\mathcal{J}$ for $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ such that $\mathcal{J}\mathrm{,}0\vDash \exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}$ , so that $\mathcal{K}⊭\neg \exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}$ .

The following proposition is a direct consequence of the existence of a canonical model for entailment of BTCQs without negation.

Proposition 7.6.

Assume $\mathcal{L}$ has the canonical model property for BCQ entailment. Then, for every $\mathcal{L}$ -TKBs  $\mathcal{K}$ and  ${\mathcal{K}}^{\prime }$ , if $\mathcal{K}$ and ${\mathcal{K}}^{\prime }$ coincide for BCQ entailment, then  $\mathcal{K}$ and  ${\mathcal{K}}^{\prime }$ coincide for entailment of BTCQs without negation. I.e., if for every time point p and BCQ q, $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff ${\mathcal{K}}^{\prime }\mathrm{,}\mathit{p}\vDash \mathit{q}$ , then for every time point p and BTCQ ϕ without negation, $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}^{\prime }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ .

Proof (Sketch).

We show this result in the appendix by induction on the structure of ϕ. We use the fact that by Theorem 7.4, $\mathcal{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 $\mathcal{K}$ and ${\mathcal{K}}^{\prime }$ .  □

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

ϕ	$\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff
$\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$	${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$
${\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$	${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$
${\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$	${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ or ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$
$\text{◯}{\mathit{\varphi }}_1$	${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$
${\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{<}\mathit{n}$ implies ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$
${\text{◯}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}-1\vDash {\mathit{\varphi }}_1$
${\text{●}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ implies ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}-1\vDash {\mathit{\varphi }}_1$
$\square {\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{\mathit{b}}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{-}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
$♢{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{\mathit{b}}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{-}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$
	and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{k}\mathrm{<}\mathit{j}⩽\mathit{p}\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$

Let ${\mathcal{K}}^{\ast }$ be the following TKB: $$\begin{array}{ll}\hfill & {\mathcal{K}}^{\ast }=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}\cup \mathrm{(}{\mathcal{A}}_{\mathit{n}+1}\mathrm{)}⟩\text{where}\\ \hfill & \begin{array}{cc}\hfill {\mathcal{A}}_{\mathit{n}+1}=& \{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\mid \mathit{A}\in N_{RC}\mathrm{,}\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in \tilde{\mathcal{A}}\}\hfill \\ \hfill & \cup \{\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mid \mathit{R}\in N_{RR}\mathrm{,}\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \tilde{\mathcal{A}}\}.\hfill \end{array}\end{array}$$

Proposition 7.7.

If $\mathcal{L}$ has the canonical model property for BCQ entailment, the relations in Table  2 hold for any $\mathcal{L}$ -TKB $\mathcal{K}$ .

Proof.

It is easy to see that ${\mathcal{J}}_{{\mathcal{K}}^{\ast }}={\mathcal{J}}_{\mathcal{K}}$ holds by construction. We obtain that $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ for every BTCQ without negation ϕ.

All relations in Table 2 but those for the operators □, ♢ and $\mathsf{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 ${\mathcal{J}}_{{\mathcal{K}}^{\ast }}$ is such that for every $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{I}}_{\mathit{i}}={\mathcal{I}}_{\mathit{n}+1}$ , and there are no past operators nested under unbounded future operators by definition of TCQs. Indeed, if a BTCQ ${\mathit{\varphi }}_1$ does not contain any past operators and $\mathit{i}\mathrm{>}\mathit{n}$ , ${\mathcal{J}}_{{\mathcal{K}}^{\ast }}\mathrm{,}\mathit{i}\vDash {\mathit{\varphi }}_1$ iff ${\mathcal{J}}_{{\mathcal{K}}^{\ast }}\mathrm{,}\mathit{n}+1\vDash {\mathit{\varphi }}_1$ . Hence we can show the following, from which the relations from Table 2 then follow straightforwardly.

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \square {\mathit{\varphi }}_1$ iff for every $\mathit{k}⩾\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ . Hence ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \square {\mathit{\varphi }}_1$ iff $\forall \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{n}+1\vDash {\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash ♢{\mathit{\varphi }}_1$ iff there exists $\mathit{k}⩾\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ . Hence ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash ♢{\mathit{\varphi }}_1$ iff $\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ or ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{n}+1\vDash {\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ iff $\exists \mathit{k}⩾\mathit{p}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$ . Hence ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ iff $\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$ , or ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{n}+1\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{n}+1\mathrm{,}{\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_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 ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ .

Theorem 7.8.

If $\mathcal{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 $\mathcal{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 ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{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 ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ can be decided in P w.r.t. KB complexity. Assume that for two BTCQs ${\mathit{\varphi }}_1\mathrm{,}{\mathit{\varphi }}_2$ and any $\mathit{p}⩾0$ , it is possible to decide in P whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_{\mathit{i}}$ . Using the relations in Table 2, we can prove the following.

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ can be done in P by checking that ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ or ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$ can be done in P by deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ and checking that at least one is true.

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \text{◯}{\mathit{\varphi }}_1$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \text{◯}{\mathit{\varphi }}_1$ can be done in P by checking whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$ iff $\mathit{p}\mathrm{<}\mathit{n}$ implies ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$ can be done in P by checking whether $\mathit{p}⩾\mathit{n}$ or ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}+1\vDash {\mathit{\varphi }}_1$ .

We show in the same way that we can decide in P whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\text{◯}}^{-}{\mathit{\varphi }}_1$ and whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\text{●}}^{-}{\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \square {\mathit{\varphi }}_1$ iff for every k, $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \square {\mathit{\varphi }}_1$ can be done in P by checking for each $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ that ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ .

We show in the same way that we can decide in P whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\square }^{\mathit{b}}{\mathit{\varphi }}_1$ and whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\square }^{-}{\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash ♢{\mathit{\varphi }}_1$ iff there exists k, $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash ♢{\mathit{\varphi }}_1$ can be done in P by deciding for each $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_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 ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {♢}^{\mathit{b}}{\mathit{\varphi }}_1$ and whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {♢}^{-}{\mathit{\varphi }}_1$ .

${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ iff there exists k, $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ , and for every j, $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}$ , ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$ . Therefore, deciding whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ can be done in P by deciding for each $\mathit{p}⩽\mathit{k}⩽\mathit{n}+1$ whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$ and whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ , and checking that the condition holds.

We show in the same way that we can decide in P whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$ and whether ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_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, ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ can be decided in P w.r.t. the size of ${\mathcal{K}}^{\ast }$ . Since $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}^{\ast }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ and the size of ${\mathcal{K}}^{\ast }$ is polynomial in the size of $\mathcal{K}$ , deciding whether $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ 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 $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ that can be checked in P. This certificate consists of:

a sequence of functions ${\mathrm{(}{\mathit{\nu }}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ that associate to each BCQ q of ϕ true or false, and

for each BCQ q of ϕ and time point $\mathit{i}\in [0\mathrm{,}\mathit{n}+1]$ such that ${\mathit{\nu }}_{\mathit{i}}\mathrm{(}\mathit{q}\mathrm{)}=\mathsf{true}$ : a certificate that ${\tilde{\mathit{q}}}_{\mathit{i}}=\mathsf{RenameNotRig}\mathrm{(}\mathit{q}\mathrm{,}\mathit{i}\mathrm{)}$ is entailed from $\tilde{\mathcal{K}}$ .

There are polynomially many pairs of a time point and a BCQ, and the certificate that ${\tilde{\mathit{q}}}_{\mathit{i}}$ is entailed from $\tilde{\mathcal{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 ${\mathit{\nu }}_{\mathit{i}}\mathrm{(}\mathit{q}\mathrm{)}$ for every $\mathit{i}\in [0\mathrm{,}\mathit{n}+1]$ and to ${\mathit{\nu }}_{\mathit{n}+1}\mathrm{(}\mathit{q}\mathrm{)}$ for every $\mathit{i}\mathrm{>}\mathit{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 $\mathit{w}={\mathit{w}}^0{\mathit{w}}^1\dots {\mathit{w}}^{\mathit{n}}{\mathit{w}}^{\mathit{n}+1}\dots$ the trace over $2^{BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}}$ , where $BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ denotes the set of BCQs of ϕ, such that ${\mathit{w}}^{\mathit{i}}=\{\mathit{q}\mid {\mathit{\nu }}_{\mathit{i}}\mathrm{(}\mathit{q}\mathrm{)}=\mathsf{true}\}$ for $\mathit{i}⩽\mathit{n}+1$ , and ${\mathit{w}}^{\mathit{i}}={\mathit{w}}^{\mathit{n}+1}$ for $\mathit{i}\mathrm{>}\mathit{n}+1$ . Since ${\mathit{w}}^{\mathit{i}}={\mathit{w}}^{\mathit{n}+1}$ , for $\mathit{i}\mathrm{>}\mathit{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 $\mathit{w}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ can be decided by checking which queries are in ${\mathit{w}}^{\mathit{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 ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{R}}$ have the canonical model property for BCQ entailment (cf. [41] for ${\mathcal{EL}}_{\perp }$ , and [40] for ${\text{DL-Lite}}_{\mathcal{R}}$ ), we obtain the following theorem.

Theorem 7.9.

For ${\mathit{\text{DL-Lite}}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ , entailment of BTCQs without negation is in P w.r.t. KB complexity and in NP w.r.t. combined complexity, even if $N_{RR}\ne \varnothing$ .

Besides these results for ${\text{DL-Lite}}_{\mathcal{R}}$ and ${\mathcal{EL}}_{\perp }$ , 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 ${\text{DL-Lite}}_{\mathrm{horn}}^{\mathcal{N}}$  [35].

8. Complexity of inconsistency-tolerant BTCQ entailment without negation in the query

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 $\mathcal{L}={\mathcal{EL}}_{\perp }$ and $\mathcal{L}={\text{DL-Lite}}_{\mathcal{R}}$ , provided no negation is used in the TCQs.

Proposition 8.1.

If $\mathcal{L}$ is such that consistency checking of a $\mathcal{L}$ -TKB is in P and BTCQ entailment from a $\mathcal{L}$ -TKB is in P w.r.t. data complexity and in NP w.r.t. combined complexity, then BTCQ entailment from a $\mathcal{L}$ -TKB

under AR semantics is in co NP w.r.t. data complexity and in ${\mathrm{\Pi }}_2^{\mathit{p}}$ w.r.t. combined complexity;

under IAR semantics is in co NP w.r.t. data complexity and in ${\mathrm{\Delta }}_2^{\mathit{p}}[\mathit{O}\mathrm{(}log\mathit{n}\mathrm{)}]$ 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, $\mathsf{ARNonEntailment}$ , $\mathsf{IARNonEntailment}$ and $\mathsf{braveEntailment}$ take non-deterministic polynomial time.

For the combined complexity of brave BTCQ entailment, a certificate that $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ can be guessed together with ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ , and verified in P.

For the combined complexity of IAR, we use the procedure $\mathsf{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 ${\mathrm{\Delta }}_2^{\mathit{p}}[\mathit{O}\mathrm{(}log\mathit{n}\mathrm{)}]$ [32].  □

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

For ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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_{RC}=N_{RR}=\varnothing$ .

We describe a method for brave entailment of BTCQ without negation when $N_{RC}=N_{RR}=\varnothing$ . 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\mathrm{(}\mathit{\varphi }\mathrm{)}$ of leaves of ϕ, that is, the set of all BCQs in ϕ, and the set $\mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ of subformulas of ϕ. In what follows, we identify the BCQs of $BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ and the BTCQs of $\mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ with their propositional abstractions as defined in Section 2: if we write that a KB or a TKB entails some elements of $BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ or $\mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ , we consider them as BCQs or BTCQs, and if we write that some elements of $BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ or $\mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ entail others, we consider the elements of $BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ as propositional variables and those of $\mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ as propositional LTL formulas built over these variables.

Definition 8.2.

A brave-justification structure J for the BTCQ without negation ϕ in the TKB $\mathcal{K}$ is a set of tuples of the form $\mathrm{(}\mathit{i}\mathrm{,}{\mathit{L}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{prev}}\mathrm{,}{\mathit{F}}_{\text{next}}\mathrm{)}$ , where $0⩽\mathit{i}⩽\mathit{n}$ , ${\mathit{L}}_{\text{now}}\subseteq BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ , ${\mathit{F}}_{\text{now}}\subseteq \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ , ${\mathit{F}}_{\text{prev}}\subseteq \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ , and ${\mathit{F}}_{\text{next}}\subseteq \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ .

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

$⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩{\vDash }_{\text{brave}}{\bigwedge }_{\mathit{q}\in {\mathit{L}}_{\text{now}}}\mathit{q}$ .

If $\mathit{i}\mathrm{>}0$ , there exists $\mathrm{(}\mathit{i}-1\mathrm{,}{\mathit{L}}_{\text{now}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{now}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{prev}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{next}}^{\prime }\mathrm{)}\in \mathit{J}$ such that ${\mathit{F}}_{\text{prev}}={\mathit{F}}_{\text{now}}^{\prime }$ and ${\mathit{F}}_{\text{now}}={\mathit{F}}_{\text{next}}^{\prime }$ .

If $\mathit{i}\mathrm{<}\mathit{n}$ , there exists $\mathrm{(}\mathit{i}+1\mathrm{,}{\mathit{L}}_{\text{now}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{now}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{prev}}^{\prime }\mathrm{,}{\mathit{F}}_{\text{next}}^{\prime }\mathrm{)}\in \mathit{J}$ such that ${\mathit{F}}_{\text{next}}={\mathit{F}}_{\text{now}}^{\prime }$ and ${\mathit{F}}_{\text{now}}={\mathit{F}}_{\text{prev}}^{\prime }$ .

For every $\mathit{\psi }\in BCQ\mathrm{(}\mathit{\varphi }\mathrm{)}$ , if ${\mathit{F}}_{\text{now}}\vDash \mathit{\psi }$ , then $\mathit{\psi }\in {\mathit{L}}_{\text{now}}$ .

For every $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ , if ${\mathit{F}}_{\text{now}}\vDash \mathit{\psi }$ , then $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ .

For every $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ , if ${\bigwedge }_{\mathit{q}\in {\mathit{L}}_{\text{now}}}\mathit{q}\wedge {\text{◯}}^{-}\mathrm{(}{\bigwedge }_{\mathit{\chi }\in {\mathit{F}}_{\text{prev}}}\mathit{\chi }\mathrm{)}\wedge \text{◯}\mathrm{(}{\bigwedge }_{\mathit{\chi }\in {\mathit{F}}_{\text{next}}}\mathit{\chi }\mathrm{)}\vDash \mathit{\psi }$ , then $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ .

For every $\mathit{\psi }\mathrm{,}{\mathit{\psi }}^{\prime }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ :

if $\mathit{\psi }\vee {\mathit{\psi }}^{\prime }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${\mathit{\psi }}^{\prime }\in {\mathit{F}}_{\text{now}}$ ,

if $♢\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or $♢\mathit{\psi }\in {\mathit{F}}_{\text{next}}$ ,

if ${♢}^{\mathit{b}}\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${♢}^{\mathit{b}}\mathit{\psi }\in {\mathit{F}}_{\text{next}}$ ,

if ${♢}^{-}\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${♢}^{-}\mathit{\psi }\in {\mathit{F}}_{\text{prev}}$ ,

if ${\mathit{\psi }}^{\prime }\mathsf{U}\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${\mathit{\psi }}^{\prime }\in {\mathit{F}}_{\text{now}}$ and ${\mathit{\psi }}^{\prime }\mathsf{U}\mathit{\psi }\in {\mathit{F}}_{\text{next}}$ ,

if ${\mathit{\psi }}^{\prime }{\mathsf{U}}^{\mathit{b}}\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${\mathit{\psi }}^{\prime }\in {\mathit{F}}_{\text{now}}$ and ${\mathit{\psi }}^{\prime }{\mathsf{U}}^{\mathit{b}}\mathit{\psi }\in {\mathit{F}}_{\text{next}}$ ,

if ${\mathit{\psi }}^{\prime }\mathsf{S}\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ , then either $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ or ${\mathit{\psi }}^{\prime }\in {\mathit{F}}_{\text{now}}$ and ${\mathit{\psi }}^{\prime }\mathsf{S}\mathit{\psi }\in {\mathit{F}}_{\text{prev}}$ , and

if ψ is of the form $\square \mathit{\phi }$ , then either $\mathit{\psi }\notin {\mathit{F}}_{\text{now}}$ or $⟨\varnothing \mathrm{,}{\mathrm{(}\varnothing \mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{n}+1\vDash \square \mathit{\phi }$ .

If $\mathit{i}=\mathit{n}$ , then

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form ${\text{●}}^{\mathit{b}}\mathit{\phi }$ , $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ ,

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form $\text{◯}\mathit{\phi }$ and such that $⟨\varnothing \mathrm{,}{\mathrm{(}\varnothing \mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{n}+1⊭\square \mathit{\phi }$ , we have $\mathit{\psi }\notin {\mathit{F}}_{\text{now}}$ ,

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form ${♢}^{\mathit{b}}\mathit{\phi }\mathrm{,}{\square }^{\mathit{b}}\mathit{\phi }\mathrm{,}$ or ${\mathit{\phi }}^{\prime }{\mathsf{U}}^{\mathit{b}}\mathit{\phi }$ , $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ iff $\mathit{\phi }\in {\mathit{F}}_{\text{now}}$ ,

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form $♢\mathit{\phi }\mathrm{,}{\mathit{\phi }}^{\prime }\mathsf{U}\mathit{\phi }$ and such that $⟨\varnothing \mathrm{,}{\mathrm{(}\varnothing \mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{n}+1⊭\square \mathit{\phi }$ , $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ iff $\mathit{\phi }\in {\mathit{F}}_{\text{now}}$ .

If $\mathit{i}=0$ , then

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form ${\text{●}}^{-}\mathit{\phi }$ , $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ ,

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form ${\text{◯}}^{-}\mathit{\phi }$ , $\mathit{\psi }\notin {\mathit{F}}_{\text{now}}$ , and

for all $\mathit{\psi }\in \mathit{F}\mathrm{(}\mathit{\varphi }\mathrm{)}$ that are of the form ${♢}^{-}\mathit{\phi }$ , ${\square }^{-}\mathit{\phi }$ , ${\mathit{\phi }}^{\prime }\mathsf{S}\mathit{\phi }$ , $\mathit{\psi }\in {\mathit{F}}_{\text{now}}$ iff $\mathit{\phi }\in {\mathit{F}}_{\text{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, ${\mathit{L}}_{\text{now}}$ is a set of BCQs whose conjunction is entailed under brave semantics by $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ (Condition 1), and ${\mathit{F}}_{\text{now}}$ is the set of formulas that can be entailed together with ${\mathit{L}}_{\text{now}}$ , depending on what is entailed in the previous and next time points, this information being stored in ${\mathit{F}}_{\text{prev}}$ and ${\mathit{F}}_{\text{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 ${\mathit{L}}_{\text{now}}$ is exactly the set of BCQs contained in ${\mathit{F}}_{\text{now}}$ and Condition 5 that ${\mathit{F}}_{\text{now}}$ is maximal in the sense that it contains its consequences. Condition 7 enforces that ${\mathit{F}}_{\text{now}}$ , ${\mathit{F}}_{\text{prev}}$ and ${\mathit{F}}_{\text{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 $\mathrm{(}\mathit{p}\mathrm{,}{\mathit{L}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{prev}}\mathrm{,}{\mathit{F}}_{\text{next}}\mathrm{)}\in \mathit{J}$ such that $\mathit{\varphi }\in {\mathit{F}}_{\text{now}}$ . We show that ϕ is entailed from $\mathcal{K}$ at time point p under brave semantics iff there is a correct brave-justification structure for ϕ in $\mathcal{K}$ that justifies ϕ at time point p. The main idea of the proof is to link the tuples of a sequence ${\mathrm{(}\mathrm{(}\mathit{i}\mathrm{,}{\mathit{L}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{prev}}\mathrm{,}{\mathit{F}}_{\text{next}}\mathrm{)}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ to a consistent TKB ${\mathcal{K}}^{\prime }=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{C}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ such that for every i, we have ${\mathcal{C}}_{\mathit{i}}\subseteq {\mathcal{A}}_{\mathit{i}}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{C}}_{\mathit{i}}⟩\vDash {\bigwedge }_{\mathit{q}\in {\mathit{L}}_{\text{now}}}\mathit{q}$ . We show in the appendix that there is such a ${\mathcal{K}}^{\prime }$ such that ${\mathcal{K}}^{\prime }\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff there is such a sequence of tuples that is a correct brave-justification structure for ϕ in $\mathcal{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 ${\mathit{\text{DL-Lite}}}_{\mathcal{R}}$ , if $N_{RC}=N_{RR}=\varnothing$ , 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 $\mathcal{K}$ that justifies ϕ at time point p. We start with a brave-justification structure J for ϕ in $\mathcal{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 ${\mathit{L}}_{\text{now}}$ , ${\mathit{F}}_{\text{now}}$ , ${\mathit{F}}_{\text{prev}}$ and ${\mathit{F}}_{\text{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 $\mathrm{(}\mathit{p}\mathrm{,}{\mathit{L}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{now}}\mathrm{,}{\mathit{F}}_{\text{prev}}\mathrm{,}{\mathit{F}}_{\text{next}}\mathrm{)}$ such that $\mathit{\varphi }\in {\mathit{F}}_{\text{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 ${\text{DL-Lite}}_{\mathcal{R}}$ -KB for Condition 1 depends on the size of the ABox, which can be performed in ${\mathsf{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 $\square \mathrm{(}\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\vee \neg \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}$ .

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 ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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 ${\mathcal{EL}}_{\perp }$ .

Three different algorithms for answering TCQs without negation over ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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, $\mathcal{K}$ is a ${\text{DL-Lite}}_{\mathcal{R}}$ -TKB and ϕ a TCQ without negation and unbounded future operators ( $\text{◯}$ , □, ♢, $\mathsf{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 $\square \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ . Such a query can be entailed with rigid predicates, e.g., if A is rigid, but not without rigid predicates since for $\mathit{p}\mathrm{>}\mathit{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^{\mathcal{K}}$ , $N_R^{\mathcal{K}}$ , $N_{RC}^{\mathcal{K}}$ , $N_{RR}^{\mathcal{K}}$ , and $N_I^{\mathcal{K}}$  denote respectively the sets of concepts, roles, rigid concepts, rigid roles, and individuals that occur in the TKB  $\mathcal{K}$ . The algorithm first constructs every possible set $\mathcal{R}$ of assertions built from the rigid concepts and individuals in the TKB $\mathcal{K}$ . Note that there are $2^{|N_{RC}^{\mathcal{K}}|\ast |N_I^{\mathcal{K}}|}$ such sets. It then runs, in parallel, for each such set $\mathcal{R}$ an instance of the algorithm for TCQ answering without rigid predicates on the TKB that is obtained by adding the assertions in $\mathcal{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

$⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ is inconsistent, or

a rigid concept assertion entailed by $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ does not belong to $\mathcal{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 ${\text{DL-Lite}}_{\mathcal{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  $\mathcal{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 $\mathcal{K}$ with $N_{RC}\ne \varnothing$ , $N_{RR}\ne \varnothing$ can be performed by TCQ answering over $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ with $N_{RC}=N_{RR}=\varnothing$ . Without any restriction on the TBox, $\mathcal{R}$ may be infinite, as illustrated in the following example.

Example 9.1.

Consider the TKB $\mathcal{K}$ with the TBox $\mathcal{T}=\{\exists {\mathit{R}}^{-}⊑\exists \mathit{R}\mathrm{,}\mathit{R}⊑\mathit{S}\}$ , where S is rigid, and the ABox sequence consisting of ${\mathcal{A}}_0=\{\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}$ , and ${\mathcal{A}}_{\mathit{i}}=\varnothing$ for $\mathit{i}\in [1\mathrm{,}\mathit{n}]$ .

Every model of $\mathcal{K}$ that respects rigid predicates satisfies $\mathit{\varphi }=\exists {\mathit{x}}_1\dots {\mathit{x}}_{\mathit{k}+1}.\mathit{S}\mathrm{(}{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\mathrm{)}\wedge \cdots \wedge \mathit{S}\mathrm{(}{\mathit{x}}_{\mathit{k}}\mathrm{,}{\mathit{x}}_{\mathit{k}+1}\mathrm{)}$ for every $\mathit{k}\mathrm{>}0$ and at every time point. Since with $N_{RC}=N_{RR}=\varnothing$ , $\mathcal{K}$ entails such a query only at time point 0, $\mathcal{R}$ should be such that $⟨\mathcal{T}\mathrm{,}\mathcal{R}⟩$ entails such a query, so that $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ entails it at every time point. Moreover, there exist models of  $\mathcal{K}$ that respect rigid predicates and for which neither $\exists {\mathit{x}}_1\dots {\mathit{x}}_{\mathit{k}}.\mathit{S}\mathrm{(}{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\mathrm{)}\wedge \cdots \wedge \mathit{S}\mathrm{(}{\mathit{x}}_{\mathit{k}}\mathrm{,}{\mathit{x}}_1\mathrm{)}$ nor $\exists \mathit{x}\mathit{y}.\mathit{R}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ hold at any time point $\mathit{i}\mathrm{>}0$ . Therefore, $\mathcal{R}$ cannot contain cycles of S, nor R-assertions. Consequently, $\mathcal{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 $\mathcal{T}$ that entail no role inclusions of the form ${\mathit{P}}_1⊑{\mathit{P}}_2$ with ${\mathit{P}}_1:={\mathit{R}}_1|{\mathit{R}}_1^{-}$ , ${\mathit{R}}_1\in N_R\setminus N_{RR}$ and ${\mathit{P}}_2:={\mathit{R}}_2|{\mathit{R}}_2^{-}$ , ${\mathit{R}}_2\in N_{RR}$ . This condition avoids chains of rigid roles in the anonymous part of the canonical model ${\mathcal{J}}_{\mathcal{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 $\mathit{R}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ to every ${\mathcal{A}}_{\mathit{i}}$ is sufficient for $\exists {\mathit{x}}_1\dots {\mathit{x}}_{\mathit{k}+1}.\mathit{R}\mathrm{(}{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\mathrm{)}\wedge \cdots \wedge \mathit{R}\mathrm{(}{\mathit{x}}_{\mathit{k}}\mathrm{,}{\mathit{x}}_{\mathit{k}+1}\mathrm{)}$ to be entailed at every time point and for every  $\mathit{k}\mathrm{>}0$ .

As a first step, we explicitly construct the canonical model ${\mathcal{J}}_{\mathcal{K}}$ of the ${\text{DL-Lite}}_{\mathcal{R}}$ -TKB $\mathcal{K}$ . This model will be used to prove that $\mathcal{K}$ with $N_{RC}\ne \varnothing$ , $N_{RR}\ne \varnothing$ and $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ with $N_{RC}=N_{RR}=\varnothing$ entail the same BTCQs that do not have negation or unbounded future operators.

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

• $\mathit{\alpha }={\mathit{A}}_1⊑{\mathit{A}}_2$ , $\mathit{\beta }={\mathit{A}}_1\mathrm{(}\mathit{a}\mathrm{)}$ and ${\mathit{A}}_2\mathrm{(}\mathit{a}\mathrm{)}\notin \mathcal{S}$ ,

• $\mathit{\alpha }=\mathit{A}⊑\exists \mathit{P}$ , $\mathit{\beta }=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ and there exists no b such that $\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{S}$ ,

• $\mathit{\alpha }=\exists \mathit{P}⊑\mathit{A}$ , $\mathit{\beta }=\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ and $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\notin \mathcal{S}$ ,

• $\mathit{\alpha }=\exists {\mathit{P}}_1⊑\exists {\mathit{P}}_2$ , $\mathit{\beta }={\mathit{P}}_1\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ and there exists no b such that ${\mathit{P}}_2\mathrm{(}{\mathit{a}}_1\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{S}$ , or

• $\mathit{\alpha }={\mathit{P}}_1⊑{\mathit{P}}_2$ , $\mathit{\beta }={\mathit{P}}_1\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ , and ${\mathit{P}}_2\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}\notin \mathcal{S}$ .

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

Definition 9.2 (Rigid chase of a TKB).

Let $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ be a ${\text{DL-Lite}}_{\mathcal{R}}$ -TKB. Let ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ be such that ${\mathcal{A}}_{\mathit{i}}^{\prime }={\mathcal{A}}_{\mathit{i}}\cup \{\mathit{\beta }\mid \exists \mathit{k}\mathrm{,}\mathit{\beta }\in {\mathcal{A}}_{\mathit{k}}\text{ and }\mathit{\beta }\text{ is rigid}\}$ for $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ and ${\mathcal{A}}_{\mathit{n}+1}^{\prime }=\varnothing$ . Finally, let ${\mathcal{T}}_{\mathit{p}}$ be the set of positive inclusions in $\mathcal{T}$ , and ${\mathit{N}}_{\mathit{i}}$ be the number of assertions in ${\mathcal{A}}_{\mathit{i}}^{\prime }$ . Assume that the assertions in each ${\mathcal{A}}_{\mathit{i}}^{\prime }$ are enumerated from ${\mathit{N}}_1+\cdots +{\mathit{N}}_{\mathit{i}-1}+1$ to ${\mathit{N}}_1+\cdots +{\mathit{N}}_{\mathit{i}}$ following their lexicographic order. Consider the sequences of sets ${\mathcal{S}}^{\mathit{j}}={\mathrm{(}{\mathcal{S}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ of assertions defined by $$\begin{array}{ll}\hfill & {\mathcal{S}}^0={\mathrm{\left(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{\right)}}_{0⩽\mathit{i}⩽\mathit{n}+1}\\ \hfill & {\mathcal{S}}^{\mathit{j}+1}={\mathcal{S}}^{\mathit{j}}\cup {\mathcal{S}}^{\text{new}}={\mathrm{(}{\mathcal{S}}_{\mathit{i}}^{\mathit{j}}\cup {\mathcal{S}}_{\mathit{i}}^{\text{new}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}\mathrm{,}\end{array}$$ where ${\mathcal{S}}^{\text{new}}$ is defined in terms of the assertion ${\mathit{\beta }}_{\text{new}}$ obtained as follows: let $\mathit{\beta }\in {\mathcal{S}}_{{\mathit{i}}_{\mathit{\beta }}}^{\mathit{j}}$ be the first assertion in  ${\mathcal{S}}^{\mathit{j}}$ such that there exists a PI in ${\mathcal{T}}_{\mathit{p}}$ applicable in  ${\mathcal{S}}_{{\mathit{i}}_{\mathit{\beta }}}^{\mathit{j}}$ to β and let α be the lexicographically first PI applicable in  ${\mathcal{S}}_{{\mathit{i}}_{\mathit{\beta }}}^{\mathit{j}}$ to β. ${\mathit{\beta }}_{\text{new}}$ is then defined based on the syntactictal form of α and β. Specifically,

if $\mathit{\alpha }={\mathit{A}}_1⊑{\mathit{A}}_2$ and $\mathit{\beta }={\mathit{A}}_1\mathrm{(}\mathit{a}\mathrm{)}$ , then ${\mathit{\beta }}_{\text{new}}={\mathit{A}}_2\mathrm{(}\mathit{a}\mathrm{)}$ ,

if $\mathit{\alpha }=\mathit{A}⊑\exists \mathit{P}$ and $\mathit{\beta }=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ , then ${\mathit{\beta }}_{\text{new}}=\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{a}}_{\text{new}}\mathrm{)}$ ,

if $\mathit{\alpha }=\exists \mathit{P}⊑\mathit{A}$ and $\mathit{\beta }=\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , then ${\mathit{\beta }}_{\text{new}}=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ ,

if $\mathit{\alpha }=\exists {\mathit{P}}_1⊑\exists \mathit{P}$ and $\mathit{\beta }={\mathit{P}}_1\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , then ${\mathit{\beta }}_{\text{new}}=\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{a}}_{\text{new}}\mathrm{)}$ , and

if $\mathit{\alpha }={\mathit{P}}_1⊑{\mathit{P}}_2$ and $\mathit{\beta }={\mathit{P}}_1\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ , then ${\mathit{\beta }}_{\text{new}}={\mathit{P}}_2\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ ,

where ${\mathit{a}}_{\text{new}}$ is constructed from α and β as follows:

• if $\mathit{a}\in N_I^{\mathcal{K}}\mathrm{,}$ then ${\mathit{a}}_{\text{new}}={\mathit{x}}_{\mathit{a}\mathit{P}}^{{\mathit{i}}_{\mathit{\beta }}}$ , and

• otherwise $\mathit{a}\notin N_I^{\mathcal{K}}$ , then a is of the form ${\mathit{x}}_{{\mathit{a}}^{\prime }{\mathit{P}}_1\dots {\mathit{P}}_{\mathit{l}}}^{{\mathit{i}}_1\dots {\mathit{i}}_{\mathit{l}}}$ and we define ${\mathit{a}}_{\text{new}}={\mathit{x}}_{{\mathit{a}}^{\prime }{\mathit{P}}_1\dots {\mathit{P}}_{\mathit{l}}\mathit{P}}^{{\mathit{i}}_1\dots {\mathit{i}}_{\mathit{l}}{\mathit{i}}_{\mathit{\beta }}}$ .

If ${\mathit{\beta }}_{\text{new}}$ is rigid, then ${\mathcal{S}}^{\text{new}}={\mathrm{(}\{{\mathit{\beta }}_{\text{new}}\}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ , otherwise, ${\mathcal{S}}^{\text{new}}={\mathrm{(}{\mathcal{S}}_{\mathit{i}}^{\text{new}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ with ${\mathcal{S}}_{{\mathit{i}}_{\mathit{\beta }}}^{\text{new}}=\{{\mathit{\beta }}_{\text{new}}\}$ and ${\mathcal{S}}_{\mathit{i}}^{\text{new}}=\varnothing$ for $\mathit{i}\ne {\mathit{i}}_{\mathit{\beta }}$ .

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

We call the rigid chase of the TKB $\mathcal{K}$ , denoted by ${\mathit{\text{chase}}}_{\text{rig}}\mathrm{(}\mathcal{K}\mathrm{)}={\mathrm{(}{\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}$ , the sequence of sets of assertions obtained as the infinite union of all  ${\mathcal{S}}^{\mathit{j}}$ , i.e., $$\begin{array}{c}{\mathrm{(}{\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}+1}={\mathrm{\left(}{\displaystyle \bigcup }_{\mathit{j}\in \mathbb{N}}{\mathcal{S}}_{\mathit{i}}^{\mathit{j}}\mathrm{\right)}}_{0⩽\mathit{i}⩽\mathit{n}+1}.\end{array}$$

Based on the rigid chase of $\mathcal{K}$ , we construct the sequence of interpretations ${\mathcal{J}}_{\mathcal{K}}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ , where ${\mathcal{I}}_{\mathit{i}}=⟨\mathrm{\Delta }\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}}⟩$ is defined as follows.

$\mathrm{\Delta }=N_I^{\mathcal{K}}\cup {\mathrm{\Gamma }}_{\mathit{N}}$ , where ${\mathrm{\Gamma }}_{\mathit{N}}$ is the set of individuals that appear in ${\mathit{\text{chase}}}_{\text{rig}}\mathrm{(}\mathcal{K}\mathrm{)}$ and not in $\mathcal{K}$ .

For every $\mathit{a}\in \mathrm{\Delta }$ , ${\mathit{a}}^{{\mathcal{I}}_{\mathit{i}}}=\mathit{a}$ .

For every $\mathit{A}\in N_C$ , ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}=\{\mathit{a}\mid \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in {\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}\}$ if $\mathit{i}⩽\mathit{n}$ , ${\mathit{A}}^{{\mathcal{I}}_{\mathit{i}}}=\{\mathit{a}\mid \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in {\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{n}+1}\mathrm{)}\}$ if $\mathit{i}\mathrm{>}\mathit{n}$ .

For every $\mathit{R}\in N_R$ , ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mid \mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}\}$ if $\mathit{i}⩽\mathit{n}$ , ${\mathit{R}}^{{\mathcal{I}}_{\mathit{i}}}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mid \mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{\text{chase}}}_{\text{rig}}^{\mathcal{K}}\mathrm{(}{\mathcal{A}}_{\mathit{n}+1}\mathrm{)}\}$ if $\mathit{i}\mathrm{>}\mathit{n}$ .

We show that ${\mathcal{J}}_{\mathcal{K}}$ is a model of $\mathcal{K}$ that respects rigid predicates, and that for any BTCQ without negation ϕ such that $N_I^{\mathit{\varphi }}\subseteq N_I^{\mathcal{K}}$ , $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ .

Lemma 9.3.

If  $\mathcal{K}$ is consistent, then  ${\mathcal{J}}_{\mathcal{K}}$ is a model of  $\mathcal{K}$ that respects rigid predicates.

Proof (Sketch).

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

Next, we show that ${\mathcal{J}}_{\mathcal{K}}$ is the canonical model of $\mathcal{K}$ for entailment of BTCQ without negation.

Lemma 9.4.

If $\mathcal{K}$ is consistent, then for every BTCQ without negation ϕ such that $N_I^{\mathit{\varphi }}\subseteq N_I^{\mathcal{K}}$ , $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ .

Proof (Sketch).

Since ${\mathcal{J}}_{\mathcal{K}}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ with ${\mathcal{I}}_{\mathit{i}}=⟨\mathrm{\Delta }\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}}⟩$ is a model of $\mathcal{K}$ that respects rigid predicates, the first direction is straightforward, and we only need to show that ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ implies $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ . Let $\mathcal{J}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}^{\prime }\mathrm{)}}_{\mathit{i}⩾0}$ with ${\mathcal{I}}_{\mathit{i}}^{\prime }=⟨{\mathrm{\Delta }}^{\prime }\mathrm{,}{·}^{{\mathcal{I}}_{\mathit{i}}^{\prime }}⟩$ be a model of $\mathcal{K}$ that respects rigid predicates. We show by structural induction on ϕ that if ${\mathcal{J}}_{\mathcal{K}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ , then $\mathcal{J}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ . For the case where ϕ is a CQ $\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ , we show that if there exists a homomorphism π of $\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ into ${\mathcal{I}}_{\mathit{p}}$ , then ${\mathcal{I}}_{\mathit{p}}^{\prime }\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ , by defining a homomorphism h from Δ into ${\mathrm{\Delta }}^{\prime }$ .  □

We are now ready to introduce the set $\mathcal{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 $\mathcal{R}$ be as defined in Fig.  6 . Then, $\mathcal{R}$ is computable in polynomial time and such that

Fig. 6.

Set of rigid assertions added to every ABox of $\mathcal{K}$ .

1. $\mathcal{K}$ is consistent iff ${\mathcal{K}}_{\mathcal{R}}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ is consistent with $N_{RC}=N_{RR}=\varnothing$ , and

2. for any BTCQ ϕ without negation and unbounded future operators and such that $N_I^{\mathit{\varphi }}\subseteq N_I^{\mathcal{K}}$ , $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}_{\mathcal{R}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ with $N_{RC}=N_{RR}=\varnothing$ .

The size of $\mathcal{R}$ is polynomial in the size of $N_C^{\mathcal{K}}\mathrm{,}{N}_R^{\mathcal{K}}$ , and $N_I^{\mathcal{K}}$ , and since query answering as well as subsumption checking are in P, $\mathcal{R}$ can be computed in polynomial time. The first three parts of $\mathcal{R}$ contain information about the participation of individuals of $N_I^{\mathcal{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 ${\mathit{\text{chase}}}_{\text{rig}}\mathrm{(}\mathcal{K}\mathrm{)}$ when applying PIs whose right-hand side is an existential restriction of a non-rigid role. The individuals created in ${\mathit{\text{chase}}}_{\text{rig}}\mathrm{(}\mathcal{K}\mathrm{)}$ when applying such a PI with a rigid role are witnessed by the individuals ${\mathit{x}}_{\mathit{a}\mathit{P}}$ or ${\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}$ if they do not follow from a rigid role assertion, and do not need to be witnessed otherwise, since the assertion ${\mathit{P}}_2\mathrm{(}{\mathit{x}}_{{\mathit{P}}_1}\mathrm{,}{\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}\mathrm{)}$ is sufficient to trigger the generation of the whole anonymous part implied by the fact that ${\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}$ is in the range of ${\mathit{P}}_2$ .

We split the proof of Proposition 9.5 into several lemmas.

Lemma 9.6.

$\mathcal{K}$ is consistent iff ${\mathcal{K}}_{\mathcal{R}}$ is consistent with $N_{RC}=N_{RR}=\varnothing$ .

Proof.

By Proposition 3.5, ${\mathcal{K}}_{\mathcal{R}}$ is consistent with $N_{RC}=N_{RR}=\varnothing$ iff each $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ is consistent. We show that also $\mathcal{K}$ is consistent iff each $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ is consistent.

For the case where $\mathcal{K}$ is not consistent, let $\mathcal{B}$ be a minimal inconsistent subset of $\mathcal{K}$ . Recall that by Fact 6.11, $\mathcal{B}$ contains at most 2 assertions. Then $\mathcal{B}$ is either internal to some  ${\mathcal{A}}_{\mathit{i}}$ , or is of the form $\mathcal{B}=\{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{\beta }\mathrm{,}\mathit{j}\mathrm{)}\}$ with $\mathit{i}\ne \mathit{j}$ . In the former case, $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ is clearly inconsistent. In the latter case, $\{\mathit{\alpha }\mathrm{,}\mathit{\beta }\}$ 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 $\mathit{a}\mathrm{,}\mathit{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) $⟨\mathcal{T}\mathrm{,}\mathit{\alpha }⟩\vDash \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ , (ii) $⟨\mathcal{T}\mathrm{,}\mathit{\alpha }⟩\vDash \exists \mathit{x}.\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{x}\mathrm{)}$ , (iii) $⟨\mathcal{T}\mathrm{,}\mathit{\alpha }⟩\vDash \exists \mathit{x}.\mathit{R}\mathrm{(}\mathit{x}\mathrm{,}\mathit{a}\mathrm{)}$ , or (iv) $⟨\mathcal{T}\mathrm{,}\mathit{\alpha }⟩\vDash \mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ . It follows that respectively (i) $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩\vDash \mathit{A}\mathrm{(}\mathit{a}\mathrm{)}$ , (ii) $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩\vDash \exists \mathit{x}.\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{x}\mathrm{)}$ , (iii) $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩\vDash \exists \mathit{x}.\mathit{R}\mathrm{(}\mathit{x}\mathrm{,}\mathit{a}\mathrm{)}$ , or (iv) $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩\vDash \mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ . By construction of $\mathcal{R}$ , we then conclude that (i) $\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\in \mathcal{R}$ , (ii) $\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{a}\mathit{R}}\mathrm{)}\in \mathcal{R}$ , (iii) $\mathit{R}\mathrm{(}{\mathit{x}}_{\mathit{a}{\mathit{R}}^{-}}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ , or (iv) $\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ respectively, and therefore that $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{j}}\cup \mathcal{R}⟩$ is inconsistent.

For the other direction, assume there exists $\mathit{i}\in [0\mathrm{,}\mathit{n}]$ , such that $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ is inconsistent, and let $\mathcal{B}$ be a minimal inconsistent subset of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}\cup \mathcal{R}⟩$ . If $\mathcal{B}$ is internal to ${\mathcal{A}}_{\mathit{i}}$ , $\mathcal{K}$ is clearly inconsistent. Otherwise,  $\mathcal{B}$ is of the form $\{\mathit{\alpha }\mathrm{,}\mathit{\beta }\}$ and involves at least one assertion from  $\mathcal{R}$ . The assertions α and β assign an individual x to two disjoint concepts ${\mathit{C}}_1\mathrm{,}{\mathit{C}}_2$ , or a pair of individuals $\mathit{x}\mathrm{,}\mathit{y}$ to two disjoint roles ${\mathit{R}}_1\mathrm{,}{\mathit{R}}_2$ . We distinguish three cases.

In the case where $\mathit{x}={\mathit{x}}_{\mathit{a}\mathit{P}}$ (resp. $\mathit{x}={\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}$ ), since $\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{a}\mathit{P}}\mathrm{)}$ (resp. ${\mathit{P}}_2\mathrm{(}{\mathit{x}}_{{\mathit{P}}_1}\mathrm{,}{\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}\mathrm{)}$ ) is the only assertion of $\mathcal{R}$ that contains x, we obtain that $⟨\mathcal{T}\mathrm{,}\{\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{a}\mathit{P}}\mathrm{)}\}⟩$ (resp. $⟨\mathcal{T}\mathrm{,}\{{\mathit{P}}_2\mathrm{(}{\mathit{x}}_{{\mathit{P}}_1}\mathrm{,}{\mathit{x}}_{{\mathit{P}}_1{\mathit{P}}_2}\mathrm{)}\}⟩$ ) is inconsistent, which implies that P (resp. ${\mathit{P}}_2$ ) is unsatisfiable, i.e., has an empty interpretation in every model of  $\mathcal{T}$ . Since there exists j such that $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{j}}⟩\vDash \exists \mathit{x}.\mathit{P}\mathrm{(}\mathit{a}\mathrm{,}\mathit{x}\mathrm{)}$ (resp. $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{j}}⟩\vDash \exists \mathit{x}\mathit{y}.{\mathit{P}}_1\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ and $\mathcal{T}\vDash \exists {\mathit{P}}_1^{-}⊑\exists {\mathit{P}}_2$ ), it follows that ${\mathcal{A}}_{\mathit{j}}$ is inconsistent.

In the case where $\mathit{x}={\mathit{x}}_{{\mathit{P}}_1}$ , since ${\mathit{x}}_{{\mathit{P}}_1}$ appears only in concepts that subsume $\exists {\mathit{P}}_1^{-}$ , the fact that x is assigned to two disjoint concepts implies that $\exists {\mathit{P}}_1^{-}$ is unsatisfiable. Thus, and since there exists j such that $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{j}}⟩\vDash \exists \mathit{x}\mathit{y}.{\mathit{P}}_1\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ , ${\mathcal{A}}_{\mathit{j}}$ is inconsistent.

Finally, in the case where $\mathit{x}\in N_I^{\mathcal{K}}$ , since α or β is in  $\mathcal{R}$ , at least one of ${\mathit{C}}_1\mathrm{,}{\mathit{C}}_2$ (or ${\mathit{R}}_1\mathrm{,}{\mathit{R}}_2$ ) is rigid. As the case where some ABox ${\mathcal{A}}_{\mathit{j}}$ is inconsistent is trivial, we assume every ${\mathcal{A}}_{\mathit{j}}$ to be consistent. If $\mathit{\alpha }\notin {\mathcal{A}}_{\mathit{i}}$ , let ${\mathit{c}}_{\mathit{\alpha }}\in {\mathcal{A}}_{{\mathit{j}}_{\mathit{\alpha }}}$ be an assertion responsible for the entailment that triggered the addition of α to $\mathcal{R}$ , and otherwise let $\mathrm{(}{\mathit{c}}_{\mathit{\alpha }}\mathrm{,}{\mathit{j}}_{\mathit{\alpha }}\mathrm{)}=\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{i}\mathrm{)}$ . If $\mathit{\beta }\notin {\mathcal{A}}_{\mathit{i}}$ , let ${\mathit{c}}_{\mathit{\beta }}\in {\mathcal{A}}_{{\mathit{j}}_{\mathit{\beta }}}$ be an assertion responsible for the entailment that triggered the addition of β to $\mathcal{R}$ , and otherwise $\mathrm{(}{\mathit{c}}_{\mathit{\beta }}\mathrm{,}{\mathit{j}}_{\mathit{\beta }}\mathrm{)}=\mathrm{(}\mathit{\beta }\mathrm{,}\mathit{i}\mathrm{)}$ . Then $\{\mathrm{(}{\mathit{c}}_{\mathit{\alpha }}\mathrm{,}{\mathit{j}}_{\mathit{\alpha }}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{c}}_{\mathit{\beta }}\mathrm{,}{\mathit{j}}_{\mathit{\beta }}\mathrm{)}\}$ is inconsistent because  ${\mathit{c}}_{\mathit{\alpha }}$ and  ${\mathit{c}}_{\mathit{\beta }}$ lead to a (or $\mathit{a}\mathrm{,}\mathit{b}$ ) being assigned to two disjoint concepts (or disjoint roles) such that at least one of them is rigid. As a result, $\mathcal{K}$ is inconsistent as well.

We obtain that in every case, if ${\mathcal{K}}_{\mathcal{R}}$ is inconsistent with $N_{RC}=N_{RR}=\varnothing$ , then $\mathcal{K}$ is inconsistent with rigid predicates.  □

We now assume that $\mathcal{K}$ and ${\mathcal{K}}_{\mathcal{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 $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ is such that $N_I^{\mathit{q}}\subseteq N_I^{\mathcal{K}}$ , then for every $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ , ${\mathcal{K}}_{\mathcal{R}}\mathrm{,}\mathit{p}\vDash \mathit{q}$ iff $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ .

Lemma 9.7.

Let $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ be such that $N_I^{\mathit{q}}\subseteq N_I^{\mathcal{K}}$ . Then, for every $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ , if ${\mathcal{K}}_{\mathcal{R}}\mathrm{,}\mathit{p}\vDash \mathit{q}$ then $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ .

Proof (Sketch).

By Lemma 9.4, it suffices to focus on the canonical model ${\mathcal{J}}_{\mathcal{K}}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ for testing entailments of $\mathcal{K}$ . The lemma can be shown by defining a homomorphism from the canonical model of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}\cup \mathcal{R}⟩$ into ${\mathcal{I}}_{\mathit{p}}$ , the pth component of ${\mathcal{J}}_{\mathcal{K}}$ .  □

Lemma 9.8.

Let $\mathit{q}=\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ be such that $N_I^{\mathit{q}}\subseteq N_I^{\mathcal{K}}$ . For every $\mathit{p}\in [0\mathrm{,}\mathit{n}]$ , if $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{q}$ then ${\mathcal{K}}_{\mathcal{R}}\mathrm{,}\mathit{p}\vDash \mathit{q}$ .

Proof (Sketch).

Again, we make use of Lemma 9.4 and use the canonical model ${\mathcal{J}}_{\mathcal{K}}={\mathrm{(}{\mathcal{I}}_{\mathit{i}}\mathrm{)}}_{\mathit{i}⩾0}$ . The lemma can then be shown by considering some model ${\mathcal{I}}_{\mathit{p}}^{\mathcal{R}}$ of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}\cup \mathcal{R}⟩$ , and defining a homomorphism of ${\mathcal{I}}_{\mathit{p}}$ into  ${\mathcal{I}}_{\mathit{p}}^{\mathcal{R}}$ .  □

Since by Lemmas 9.7 and 9.8, $\mathcal{K}$ and ${\mathcal{K}}_{\mathcal{R}}$ with $N_{RC}=N_{RR}=\varnothing$ coincide on the entailment of BCQs for every time point $\mathit{p}\in [0\mathrm{,}\mathit{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^{\mathit{\varphi }}\subseteq N_I^{\mathcal{K}}$ . Then, $\mathcal{K}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ iff ${\mathcal{K}}_{\mathcal{R}}\mathrm{,}\mathit{p}\vDash \mathit{\varphi }$ with $N_{RC}=N_{RR}=\varnothing$ .

It follows that TCQs can be answered in $\mathcal{K}$ with rigid predicates by answering TCQs in ${\mathcal{K}}_{\mathcal{R}}$ without rigid predicates and pruning answers that contain individual names not in $N_I^{\mathcal{K}}$ . Note that every model of  ${\mathcal{K}}_{\mathcal{R}}$ is a model of  $\mathcal{K}$ , but does not respect rigid predicates in general. We can reduce BTCQ entailment over  $\mathcal{K}$ with rigid predicates to BTCQ entailment over ${\mathcal{K}}_{\mathcal{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 \mathit{x}\mathit{y}.{\square }^{\mathit{b}}\mathrm{(}\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{x}\mathrm{)}\wedge \mathit{R}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{)}$ and the TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ with $\mathcal{T}=\{\mathit{B}⊑\exists \mathit{R}\mathrm{,}\exists {\mathit{R}}^{-}⊑\exists \mathit{R}\}$ , $\mathit{R}\in N_{RR}$ and ${\mathcal{A}}_{\mathit{i}}=\{\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}$ . For this TKB, we would have $\mathcal{R}=\{\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{x}}_{\mathit{a}\mathit{R}}\mathrm{)}\}$ , and therefore ${\mathit{x}}_{\mathit{a}\mathit{R}}$ could have a different R-successors in each interpretation of a model of ${\mathcal{K}}_{\mathcal{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 $\mathcal{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 $\mathcal{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 $\mathcal{R}$ if their counter reaches 0.

Remark 9.11.

The main goal of the approaches presented in [17,18] for TCQ answering in ${\text{DL-Lite}}_{\mathcal{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_{RC}^{\mathcal{K}}$ and $N_I^{\mathcal{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_{RC}^{\mathcal{K}}$ , $N_{RR}^{\mathcal{K}}$ and $N_I^{\mathcal{K}}$ ), we could adapt the algorithm of [17,18] to support rigid roles. We would consider all possible sets $\mathcal{R}$ built from $N_{RC}^{\mathcal{K}}$ , $N_{RR}^{\mathcal{K}}$ and $N_I^{\mathcal{K}}$ following the form of Fig. 6, then verify at each time point whether $\mathcal{R}$ is consistent with  ${\mathcal{A}}_{\mathit{i}}$ and  $\mathcal{T}$ and contains all rigid assertions that can be derived from ${\mathcal{A}}_{\mathit{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 ${\text{DL-Lite}}_{\mathcal{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 $\mathcal{R}$ , then prune the spurious answers resulting from these cycles.

Regarding ${\mathcal{EL}}_{\perp }$ , we conjecture that we could have a similar approach for rigid predicates. The main difference would be that since in ${\mathcal{EL}}_{\perp }$ several assertions may be needed to derive one, $\mathcal{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_{RR}\ne \varnothing$ . The combined approach for $\mathcal{EL}$ [41] could provide ideas to overcome this difficulty.

9.2. Inconsistency-tolerant TCQ answering without rigid predicates

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

When $N_{RC}=N_{RR}=\varnothing$ , an important consequence of Proposition 3.5 is that the repairs of $\mathcal{K}$ are all possible sequences ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ where ${\mathcal{A}}_{\mathit{i}}^{\prime }$ is a repair of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , so the intersection of the repairs of $\mathcal{K}$ is ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\cap }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ where ${\mathcal{A}}_{\mathit{i}}^{\cap }$ is the intersection of the repairs of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{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 $\mathcal{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 $\mathcal{L}$ has the canonical model property for BCQ entailment and $N_{RC}=N_{RR}=\varnothing$ , then the entailments shown in Table  3 hold for $\mathit{\text{S}}=\mathit{\text{classical}}$ when $\mathcal{K}$ is consistent, and for $\mathit{\text{S}}=\mathit{\text{IAR}}$ .

Table 3

Entailment under classical or IAR semantics from a $\mathcal{L}$ -TKB without rigid predicates and such that $\mathcal{L}$ has the canonical model property for BCQ entailment

ϕ	$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{S}}\mathit{\varphi }$ iff
$\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$	$\mathit{p}⩽\mathit{n}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩{\vDash }_{\text{S}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$
${\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$	$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{S}}{\mathit{\varphi }}_1$ and $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{S}}{\mathit{\varphi }}_2$
${\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$	$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{S}}{\mathit{\varphi }}_1$ or $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{S}}{\mathit{\varphi }}_2$
$\text{◯}{\mathit{\varphi }}_1$	$\mathcal{K}\mathrm{,}\mathit{p}+1{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
${\text{●}}^{\mathit{b}}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{<}\mathit{n}$ implies $\mathcal{K}\mathrm{,}\mathit{p}+1{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
${\text{◯}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ and $\mathcal{K}\mathrm{,}\mathit{p}-1{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
${\text{●}}^{-}{\mathit{\varphi }}_1$	$\mathit{p}\mathrm{>}0$ implies $\mathcal{K}\mathrm{,}\mathit{p}-1{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
$\square {\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{\mathit{b}}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{K}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${\square }^{-}{\mathit{\varphi }}_1$	$\forall \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
$♢{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{\mathit{b}}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{K}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_1$
${♢}^{-}{\mathit{\varphi }}_1$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{k}⩾\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}\vDash {\mathit{\varphi }}_2$ and $\forall \mathit{j}\mathrm{,}\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{j}\vDash {\mathit{\varphi }}_1$
${\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{S}}{\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{j}{\vDash }_{\text{S}}{\mathit{\varphi }}_1$
${\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_2$	$\exists \mathit{k}$ , $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{S}}{\mathit{\varphi }}_2$ and $\forall \mathit{j}$ , $\mathit{k}\mathrm{<}\mathit{j}⩽\mathit{p}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{j}{\vDash }_{\text{S}}{\mathit{\varphi }}_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 $\mathcal{K}$ . Moreover, by Proposition 3.6, if $\mathit{p}⩽\mathit{n}$ , then $\mathcal{K}\mathrm{,}\mathit{p}\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ iff $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ . Finally, $\mathcal{K}\mathrm{,}\mathit{p}⊭\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ if $\mathit{p}\mathrm{>}\mathit{n}$ , because there exists a model of $\mathcal{K}$ whose pth component interprets every predicate as the empty set.

For IAR semantics, let ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ denote the intersection of the repairs of $\mathcal{K}$ and ${\mathcal{A}}_{\mathit{i}}^{\cap }$ denote the intersection of the repairs of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ .

$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ , i.e., iff $\mathit{p}⩽\mathit{n}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}^{\text{ir}}⟩\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ because ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is consistent. Since the repairs of $\mathcal{K}$ are the sequences of the repairs of the $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , ${\mathcal{A}}_{\mathit{p}}^{\text{ir}}={\mathcal{A}}_{\mathit{p}}^{\cap }$ , so $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ iff $\mathit{p}⩽\mathit{n}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩{\vDash }_{\text{IAR}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ .

$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}{\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ , i.e., iff $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ because ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is consistent. It follows that $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}{\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ iff $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}{\mathit{\varphi }}_1$ and $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{IAR}}{\mathit{\varphi }}_2$ .

We show all remaining relations in the same way, applying the definition of IAR semantics and using the fact that ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\text{ir}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{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 ${\text{DL-Lite}}_{\mathcal{R}}$ without unbounded future operators) by replacing classical CQ answering by IAR CQ answering (see [14,39,54] for algorithms for ${\text{DL-Lite}}_{\mathcal{R}}$ ). The following example shows that this is unfortunately not true for brave or AR semantics.

Example 9.13.

Consider the TKB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩$ and the TCQ ϕ defined as follows. $$\begin{array}{ll}\hfill & \mathcal{T}=\{\mathit{T}⊑\neg \mathit{F}\}\\ \hfill & {\mathcal{A}}_{\mathit{i}}=\{\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}\}\text{for }0⩽\mathit{i}⩽\mathit{n}\\ \hfill & \mathit{\varphi }={\square }^{-}\mathrm{(}\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\wedge {\text{●}}^{-}\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}\end{array}$$ Now, $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{brave}}\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\wedge {\text{●}}^{-}\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}$ for every $0⩽\mathit{k}⩽\mathit{n}$ , but $\mathcal{K}\mathrm{,}\mathit{n}{⊭}_{\text{brave}}\mathit{\varphi }$ . This is because the same repair cannot entail $\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\wedge {\text{●}}^{-}\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}$ both at time point k and $\mathit{k}+1$ , since it would contain both $\mathrm{(}\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{k}\mathrm{)}$ and $\mathrm{(}\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{k}\mathrm{)}$ which is not possible. For AR semantics, consider $\mathit{\varphi }=\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}\vee \mathit{F}\mathrm{(}\mathit{a}\mathrm{)}$ over the TKB $\mathcal{K}$ : while ϕ holds under AR semantics at each time point, neither $\mathit{T}\mathrm{(}\mathit{a}\mathrm{)}$ nor $\mathit{F}\mathrm{(}\mathit{a}\mathrm{)}$ does.

However, if the operators allowed in the TCQ are restricted to $\wedge \mathrm{,}\text{◯}\mathrm{,}{\text{●}}^{\mathit{b}}\mathrm{,}{\text{◯}}^{-}\mathrm{,}{\text{●}}^{-}\mathrm{,}\square \mathrm{,}{\square }^{\mathit{b}}$ , and ${\square }^{-}$ , 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 ${\text{DL-Lite}}_{\mathcal{R}}$ ). Indeed, for these operators, the relations of Proposition 9.12 hold for $\text{S}=\text{AR}$ .

$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ iff for every repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ , $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ , i.e., iff for every repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ , $\mathit{p}⩽\mathit{n}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}^{\prime }⟩\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ because ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is consistent. Since the repairs of $\mathcal{K}$ are the sequences of the repairs of the $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{i}}⟩$ , this is the case iff $\mathit{p}⩽\mathit{n}$ and for every repair  ${\mathcal{A}}_{\mathit{p}}^{\prime }$ of $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩$ , $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}^{\prime }⟩\vDash \exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ , i.e., iff $\mathit{p}⩽\mathit{n}$ and $⟨\mathcal{T}\mathrm{,}{\mathcal{A}}_{\mathit{p}}⟩{\vDash }_{\text{AR}}\exists \overrightarrow{\mathit{y}}.\mathit{\psi }\mathrm{(}\overrightarrow{\mathit{y}}\mathrm{)}$ .

$\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ iff for every repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ , $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ , i.e., iff for every repair ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ of $\mathcal{K}$ , $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_1$ and $⟨\mathcal{T}\mathrm{,}{\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}⟩\mathrm{,}\mathit{p}\vDash {\mathit{\varphi }}_2$ because ${\mathrm{(}{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{)}}_{0⩽\mathit{i}⩽\mathit{n}}$ is consistent. It follows that $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\wedge {\mathit{\varphi }}_2$ iff $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ and $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_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: $\vee \mathrm{,}♢\mathrm{,}{♢}^{\mathit{b}}\mathrm{,}{♢}^{-}\mathrm{,}\mathsf{U}\mathrm{,}{\mathsf{U}}^{\mathit{b}}\mathrm{,}$ and $\mathsf{S}$ .

• $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$ but $\mathcal{K}\mathrm{,}0{⊭}_{\text{AR}}{\mathit{\varphi }}_1$ and $\mathcal{K}\mathrm{,}0{⊭}_{\text{AR}}{\mathit{\varphi }}_2$ : $$\begin{array}{llll}\hfill & \mathcal{T}=\{\mathit{A}⊑\neg \mathit{B}\}& \hfill & {\mathcal{A}}_0=\{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}\\ \hfill & {\mathit{\varphi }}_1=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}& \hfill & {\mathit{\varphi }}_2=\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\end{array}$$

• $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}♢{\mathit{\varphi }}_1$ (resp. $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{♢}^{\mathit{b}}{\mathit{\varphi }}_1$ ) but for every k (resp. such that $0⩽\mathit{k}⩽2$ ), $\mathcal{K}\mathrm{,}\mathit{k}{⊭}_{\text{AR}}{\mathit{\varphi }}_1$ : $$\begin{array}{llll}\hfill & \mathcal{T}=\{\mathit{A}⊑\neg \mathit{B}\}& \hfill & {\mathcal{A}}_0=\{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\}\\ \hfill & {\mathcal{A}}_1=\{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}& \hfill & {\mathcal{A}}_2=\{\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}\\ \hfill & {\mathit{\varphi }}_1=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\wedge \text{◯}\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\end{array}$$

• $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ (resp. $\mathcal{K}\mathrm{,}0{\vDash }_{\text{AR}}{\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$ ) but for every k (resp. such that $0⩽\mathit{k}⩽2$ ), either $\mathcal{K}\mathrm{,}\mathit{k}{⊭}_{\text{AR}}{\mathit{\varphi }}_2$ or there exists j, such that $0⩽\mathit{j}\mathrm{<}\mathit{k}$ and $\mathcal{K}\mathrm{,}\mathit{j}{⊭}_{\text{AR}}{\mathit{\varphi }}_1$ : $$\begin{array}{llll}\hfill & \mathcal{T}=\{\mathit{A}⊑\neg \mathit{B}\}& \hfill & {\mathcal{A}}_0=\{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\}\\ \hfill & {\mathcal{A}}_1=\{\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}& \hfill & {\mathcal{A}}_2=\{\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\}\\ \hfill & {\mathit{\varphi }}_1=\mathit{A}\mathrm{(}\mathit{a}\mathrm{)}& \hfill & {\mathit{\varphi }}_2=\mathit{B}\mathrm{(}\mathit{a}\mathrm{)}\end{array}$$

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

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

• If $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ or $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_2$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\vee {\mathit{\varphi }}_2$ .

• If there exists $\mathit{k}⩾\mathit{p}$ such that $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}♢{\mathit{\varphi }}_1$ .

• If there exists k such that $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ and $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{♢}^{\mathit{b}}{\mathit{\varphi }}_1$ .

• If there exists k such that $0⩽\mathit{k}⩽\mathit{p}$ and $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{♢}^{-}{\mathit{\varphi }}_1$ .

• If there exists $\mathit{k}⩾\mathit{p}$ such that $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_2$ and for every j such that $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}$ , $\mathcal{K}\mathrm{,}\mathit{j}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\mathsf{U}{\mathit{\varphi }}_2$ .

• If there exists k such that $\mathit{p}⩽\mathit{k}⩽\mathit{n}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_2$ and for every j such that $\mathit{p}⩽\mathit{j}\mathrm{<}\mathit{k}$ , $\mathcal{K}\mathrm{,}\mathit{j}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1{\mathsf{U}}^{\mathit{b}}{\mathit{\varphi }}_2$ .

• If there exists k such that $0⩽\mathit{k}⩽\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{k}{\vDash }_{\text{AR}}{\mathit{\varphi }}_2$ and for every j such that $\mathit{k}\mathrm{<}\mathit{j}⩽\mathit{p}$ , $\mathcal{K}\mathrm{,}\mathit{j}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1$ , then $\mathcal{K}\mathrm{,}\mathit{p}{\vDash }_{\text{AR}}{\mathit{\varphi }}_1\mathsf{S}{\mathit{\varphi }}_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 ${\text{DL-Lite}}_{\mathcal{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 $\mathcal{T}=\{\mathit{A}⊑\neg \mathit{C}\mathrm{,}\mathit{B}⊑\neg \mathit{C}\}$ and $\mathit{\varphi }=\exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}\wedge ♢\mathrm{(}\exists \mathit{x}.\mathit{B}\mathrm{(}\mathit{x}\mathrm{)}\wedge \text{◯}\mathrm{(}\exists \mathit{x}.\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}\mathrm{)}$ . For ϕ to be entailed at time point p, $\exists \mathit{x}.\mathit{A}\mathrm{(}\mathit{x}\mathrm{)}$ should hold at p, $\exists \mathit{x}.\mathit{B}\mathrm{(}\mathit{x}\mathrm{)}$ at time point $\mathit{i}⩾\mathit{p}$ and $\exists \mathit{x}.\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}$ at $\mathit{i}+1\mathrm{>}\mathit{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

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 ${\mathcal{EL}}_{\perp }$ and ${\text{DL-Lite}}_{\mathcal{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 ${\mathcal{EL}}_{\perp }$ 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 ${\text{DL-Lite}}_{\mathcal{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 ${\text{LTL}}^{\text{bin}}$  [1,5,42]. In ${\text{LTL}}^{\text{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\mathrm{,}10]}^{-}\mathit{\varphi }$ . It is well-known that ${\text{LTL}}^{\text{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 ${\text{LTL}}^{\text{bin}}$ is ExpSpace-complete. In fact, combinations of ${\text{LTL}}^{\text{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].