Complexity of Temporal Query Abduction in DL-Lite Szymon Klarman and Thomas Meyer Centre for Artificial Intelligence Research, CSIR Meraka and University of KwaZulu-Natal, South Africa {sklarman,tmeyer}@csir.co.za Abstract. Temporal query abduction is the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowl- edge, warrants the entailment of the query. This problem formally un- derlies a variety of forms of explanatory and diagnostic reasoning in the context of time series data, data streams, or otherwise temporally an- notated structured information. In this paper, we consider (temporally ordered) data represented in Description Logics from the popular DL- Lite family and Temporal Query Language, based on the combination of LTL with conjunctive queries. In this defined setting, we study the complexity of temporal query abduction, assuming different restrictions on the problem and minimality criteria for abductive solutions. As a re- sult, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem. 1 Introduction The ubiquity and importance of time-related information in semantic applica- tions necessitates the need for novel representation and reasoning solutions for dealing with the temporal dimension of data. In particular, the task of query- ing temporal data in the presence of ontological constraints has in recent years gained considerable attention within the Semantic Web and Description Logic communities [20,4,12,2,13]. Query languages supporting complex temporal pat- terns are essential for enabling fine-grained retrieval and analysis of temporally annotated information, both in the static settings, such as involving historical or time series data, as well as in the dynamic ones, witnessed in the context of streaming data applications. One interesting derived problem which we study in this paper is temporal query abduction, i.e., the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowledge, warrants the entailment of the query. This type of inference is inherent to a va- riety of explanatory and diagnostic forms of reasoning applicable in the context of temporal data. For instance, suppose that the fact that the grass is frozen in some location x follows whenever the following query is satisfied: [rainIn(x)] X [∃y.(tempIn(y, x) ∧ below 0 (y))] meaning that the below-zero temperature occurred in location x immediately after a rainfall. Using abductive inference, one is then able to explain this fact with a hypothesis Ai+1 = {(tempIn(t, x), below 0 (t)}, provided he already knows that Ai = {rainIn(x)}, where Ai and Ai+1 represent the data sets that hold in some relative time points i and i + 1. Following the popular paradigm of ontology-based data access, we consider data expressed as Description Logic (DL) axioms, accessed through an ontolog- ical layer expressed in logics from the popular DL-Lite family [6]. Further, we use Temporal Query Language (TQL), originally introduced in [13], for querying temporally ordered DL data. TQL, based on the combination of Linear Tempo- ral Logic with conjunctive queries, offers a flexible means for interleaving data patterns with temporal constraints, thus providing a powerful framework for expressing interesting correlations in temporal data sets. Based on this founda- tion, we define the problem of temporal query abduction, which is the central conceptual contribution of this work. On the technical side, we analyse the com- putational complexity of the problem, considering different fragments of the temporal language and different restrictions on the space of abductive solutions. As a result, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem. A number of other types of abductive inference for DLs have been studied in the literature. These include: concept abduction [8,3], TBox and ABox abduc- tion [9,14,15,18] and query/rule abduction [10,7,21]. This last form of reasoning, dealing with the identification of minimal ABoxes satisfying a certain query/rule, is most closely related to the problem studied in this paper, although it does not consider the temporal dimension of DL data. To the best of our knowledge, the problem of temporal query abduction has never been formulated within the DL framework before, even though it has been properly recognized and investigated on the grounds of other formalisms [22,5]. The paper is organized as follows. In the next section we recap preliminaries of DLs and Temporal Query Language. In Section 3 we introduce the problem of temporal query abduction. Then, in Section 4 we present the complexity results and discuss their consequences on the main problem. The paper is concluded in Section 5. The proofs of the results are included in the online technical report [17]. The results reported in this paper are minor generalizations of those originally presented by the authors in [16]. 2 Preliminary Notions In this section, we introduce the basic nomenclature regarding Description Log- ics, conjunctive queries, and the representation and querying of temporal data. 2.1 DL-Lite and Conjunctive Queries A Description Logic (DL) language is given by a vocabulary Σ = (NI , NC , NR ) and a set of logical constructors [1]. The vocabulary consists of countably infinite sets of individual names (NI ), concept names (NC ) and role names (NR ). An ABox A is a finite set of assertions A(a) and r(a, b), for a, b ∈ NI , A ∈ NC and r ∈ NR . A TBox T is a finite set of terminological axioms, e.g., concept and role inclusions, whose precise syntax is determined by the given DL. The semantics is given in terms of DL interpretations I = (∆I , ·I ), defined as usual [1]. An interpretation I is a model of T and A, denoted as I |= T , A, iff it satisfies every axiom in T and A. If T and A have a common model they are said to be consistent. Abiding by the nomenclature of ontology-based data access paradigm, we consider the ABox as data and the TBox as the ontology, which provides an additional semantic layer over the data, thus enriching the querying capabili- ties. A conjunctive query (CQ) over a DL vocabulary Σ is a first-order formula ∃y.ϕ(x, y), where x, y are sequences of variables, from a countably infinite set of variables NV . The sequence x denotes the free (answer) variables in the query, while y the quantified ones. The formula ϕ is a conjunction of atoms over NC , NR of the form A(u), r(u, v), where u, v ∈ NV ∪ NI are called terms. By term(q) we denote the set of all terms occurring in a CQ q and by avar(q) the set of all its answer variables. We call q boolean whenever avar(q) = ∅. A boolean CQ q is satisfied in I iff there exists a mapping µ : term(q) 7→ ∆I , with µ(a) = aI for every a ∈ NI , such that for every A(u) and r(u, v) in q it is the case that µ(u) ∈ AI and (µ(u), µ(v)) ∈ rI . We say that q is entailed by a TBox T and an ABox A, denoted as T , A |= q iff q is satisfied in every model of T and A. An answer to q is a mapping σ such that σ : avar(q) 7→ NI . By σ(q) we denote the result of uniformly substituting every occurrence of x in q with σ(x), for every x ∈ avar(q). An answer σ is called certain over T , A iff T , A |= σ(q). The set of all certain answers to q over T , A is denoted by cert(q, T , A). By QΣ we denote the class of all conjunctive queries over the vocabulary Σ. In this paper, we focus on logics from the DL-Lite family [6], such as DL- Lite R , DL-Lite F or DL-Lite A , underlying the OWL 2 QL ontology language profile1 , for which CQs enjoy the so-called first-order rewritability property, de- fined as follows. Definition 1 (FO rewritability [6]). For every CQ q ∈ QΣ and a TBox T , there exists a FO formula q T such that for every ABox A and answer σ to q, it holds that σ ∈ cert(q, T , A) iff db(A) σ(q T ), where db(A) denotes A considered as a database/FO interpretation and is the FO satisfaction relation. Recall, that given T in any of such DLs and a boolean q, the FO rewriting q T of q is a union of possibly exponentially many CQs, including q. The number of these CQs is bounded by `(T )`(q) , where `(†) denotes the size of the input † measured in the total number of symbols used. Every CQ q 0 in q T is such that T ∪ {q 0 } |= q and its size is linear in `(q). The query entailment problem is NP-complete in the combined complexity, even when the TBox is empty, while checking consistency of T , A is in PTime [6]. 1 See http://www.w3.org/TR/owl2-profiles/. Regardless of this default focus, many of the results presented here can be naturally extended to other DLs with similar characteristics, such as other mem- bers of the DL-Lite family or logics in the EL family [19]. 2.2 Temporal Query Language We consider a discrete, linear time domain (Z, <), with integers representing time points ordered by the smaller-than relation. An interval over Z is a set I = [I − , I + ] = {i ∈ Z | I − ≤ i ≤ I + }, where I − ≤ I + ∈ Z ∪ {−∞, +∞} and −∞ < i < +∞ for every i ∈ Z. Definition 2 (A-sequence). An A-sequence A = (Ai )i∈I is a sequence of ABoxes, for some interval I over Z. A-sequences represent collections of datasets ordered w.r.t. the underlying time domain. The ordering of the ABoxes follows the smaller-than ordering of their indices. An A-sequence A is said to be consistent with a TBox T if every ABox in it is consistent with T . Consider A-sequences A = (Ai )i∈I and B = (Bi )i∈J . We use the following notation: – T , A |= B (A |= B) iff J ⊆ I and T , Ai |= Bi (Ai |= Bi ) for every i ∈ J, – A ] B, whenever I ∩ J 6= ∅, to denote the A-sequence (Ci )i∈I∪J such that: • Ci = Ai , for every i ∈ I \ J, • Ci = Bi , for every i ∈ J \ I, • Ci = Ai ∪ Bi , for every i ∈ I ∩ J, – A *n B, for some n ∈ I ∩ J, iff there exists a mapping f : I 7→ J, such that: • f (n) = n, • i < j iff f (i) < f (j), for every i, j ∈ I, • Ai = Bf (i) , for every i ∈ I, Next, we recall a variant of Temporal Query Language, proposed in [13], which we use for accessing A-sequences. It is a lightweight combination of Linear Temporal Logic (LTL) [23] with CQs, where CQs are embedded in the temporal language using the epistemic semantics. Definition 3 (Temporal Query Language). The temporal query language (TQL) over a class of conjunctive queries QΣ is the smallest set of formulas induced by the grammar: φ, ψ ::= [q] | ¬φ | φ ∧ ψ | φUψ | φSψ where q ∈ QΣ . By avar(φ) we denote the set of free variables in φ. A TQL formula φ is called boolean whenever avar(φ) = ∅. The entailment relation for boolean TQL formulas w.r.t. an A-sequence A = (Ai )i∈I under a TBox T in time i ∈ I is defined inductively as follows: T , A, i |= [q] iff T , Ai |= q, T , A, i |= ¬φ iff T , A, i 6|= φ, T , A, i |= φ ∧ ψ iff T , A, i |= φ and T , A, i |= ψ, T , A, i |= φUψ iff there exists j ∈ I with j > i such that T , A, j |= ψ and T , A, k |= φ for every k ∈ I with i < k < j, T , A, i |= φSψ iff there exists j ∈ I with j < i such that T , A, j |= ψ and T , A, k |= φ for every k ∈ I with i > k > j. An answer to a TQL formula φ is a mapping σ : avar(φ) 7→ NI . By σ(φ) we denote the result of uniformly substituting every occurrence of x in φ with σ(x), for every x ∈ avar(φ). An answer σ is called certain over T , A at i ∈ I iff T , A, i |= σ(φ). The set of all such answers is denoted by certi (φ, T , A). As usual, using the operators U (strict until ) and S (strict since), we can easily define other ones, such us Fφ = >Uφ (some time in future), Pφ = >Sφ (some time in past), Xφ = ⊥Uφ (next in future), X− φ = ⊥Sφ (next in past). In fact, LTL with U and S, which captures precisely the temporal component of TQL, is known to be expressively complete over (Z, <) [11]. Apart from the full TQL, in what follows we consider also some of its strict subsets. By TQLF,P we denote the fragment where U and S appear only in the forms allowed in the definitions of F and P. Further, with TQL+ we refer to the positive fragment of TQL, i.e., TQL without the negation operator. Finally, by TQLF,P,+ , we denote the intersection of TQLF,P and TQL+ . Observe that given the epistemic interpretation of the embedded CQs, [q] reads as “q is entailed in the given time instant”, for a boolean CQ q. We can immediately paraphrase this interpretation by invoking the FO rewriting of q, in the sense of Definition 1. Note that the following correspondences immediately hold: T , A, i |= [q] iff T , Ai |= q iff db(Ai ) qT . Consequently, the negation ¬[q] is naturally interpreted as negation-as-failure, reading “it is not true that q is entailed in the given time instant”. This warrants the following equivalences: T , A, i |= ¬[q] iff T , Ai 6|= q iff db(Ai ) 6 q T . These observations are critical for the work presented in this paper, as they allow to study satisfaction of TQL formulas by decoupling the temporal component of the problem from the CQ component, and addressing the latter, without loss of correctness, by applying the standard FO rewriting techniques and results, recalled in Section 2.1. Importantly, such lightweight combination of languages allows also for a modular reuse of existing temporal reasoners and highly opti- mized, efficient query answering engines [13]. In TQL+ the epistemic interpreta- tion of CQs becomes redundant, and the resulting language coincides with the one proposed in [4]. 3 Temporal Query Abduction Temporal queries can be naturally used for formalizing temporal data patterns and correlations between them, which are known to occur in a given domain. For instance, consider the TQL formulas φ and ψ: φ= ¬[∃y.(tempIn(y, x) ∧ above 0 (y))] S ([∃y.(tempIn(y, x) ∧ below 0 (y))] ∧ X− [rainIn(x)]) ψ = ∃y.(Grass(y) ∧ locIn(y, x) ∧ Frozen(y)) The first one describes a location x, which experienced a rainfall in the past, followed directly by a below-zero temperature, after which no above-zero tem- perature has been recorded. The second one states that grass is frozen in a certain location x. Suppose there actually exists a causal dependency reflected via the rule φ → ψ, so that for any answer σ = {x 7→ l}, whenever T , A, n |= σ(φ) then T , A, n |= σ(ψ). In common diagnostic scenarios, such rules can be further employed to guide the explanation-finding for the observed data: whenever σ(ψ) is true one might hypothesize a suitable collection of temporal data which makes σ(φ) true. This latter form of hypothetical inference, from a temporal query to temporal data, is a variant of classical abductive reasoning, which we study here and formalize it using the nomenclature coined in [9,15,7]. Definition 4 (Temporal query abduction). A temporal query abduction (TQA) problem is a tuple Ω = (T , A, φ, n), where T is a TBox, A = (Ai )i∈I is an A-sequence, for some finite I, φ is a boolean TQL formula, and n ∈ I. A solution to Ω is an A-sequence D = (Di )i∈Z , such that A ] D is consistent with T , and T , A ] D, n |= φ. The solution D is called: – e -minimal iff for every solution D0 , if D |= D0 then D0 |= D, – b -minimal iff for every solution D0 , if T , A ] D |= D0 then T , A ] D0 |= D, – s -minimal iff for every solution D0 , if D0 *n D then D = D0 . In the remainder of this paper, we assume w.l.o.g. that for every TQA prob- lem (T , A, φ, n), n = 0, and write (T , A, φ) for short. Intuitively, the pair (T , A) represents the background knowledge for the abductive inference over the TQL formula φ. The finiteness of A is one of the necessary conditions to ensure that the space of abductive solutions can be made finite. As usually in the context of abductive reasoning, we employ several min- imality criteria which help to reduce the solution space to a computationally manageable level. The first two are generalizations of criteria known in the clas- sical, atemporal abduction. Intuitively, e -minimality (for entailment) places the precedence over solutions which are logically weakest — they assume the least possible data in every given state — irrespectively of the background knowl- edge. The b -minimality (for entailment w.r.t. background knowledge) takes also into account the assumed TBox and A-sequence. Observe that b -minimality is strictly stronger than e -minimality, i.e., whenever a solution D is b -minimal it must be e -minimal, while the converse does not hold in general. Note that ... −4 −3 −2 −1 0 A: HeavyRainIn(l) tempIn(t, l) D1 : below 0 (t) D2 : RainIn(l) below 0 (t) D3 : HeavyRainIn(l) tempIn(t, l) below 0 (t) D4 : RainIn(l) tempIn(t, l) below 0 (t) Table 1. The A-sequence A and the solutions D1 -D4 to (T , A, φ), for T = {HeavyRainIn v RainIn}. whenever a problem has a solution at all, it must have a b -minimal (and thus an e -minimal) solution. The s -minimality criterion (for structure) is a novel one, tailored specifically for abduction problems whose solutions are sequential structures. It ensures that the solution D has no redundant subsequences. To rephrase it, D is not minimal in the sense of s whenever one can obtain a dis- tinct solution by simply removing some ABoxes from D — somewhere to the left or to the right from the fixed point n. In general, the abductive procedures devel- oped in the next section are complete w.r.t. s - and e -minimal solutions, while b -minimality can be optionally used in certain cases to ease the computation. For a more intuitive illustration of the setup and the employed minimality criteria, we consider a TQA problem Ω = (T , A, φ), with T = {HeavyRainIn v RainIn}, A as included in Table 1 and φ as defined in the beginning of this section. Table 1 presents several solutions to Ω at time 0. Note, that all empty and hidden cells in the table are empty ABoxes. Solutions D1 and D3 are both s - and e -minimal. D3 is not b -minimal, as replacing HeavyRainIn(l) with its consequence RainIn(l) results in a logically weaker solution w.r.t. T . Further, solution D2 is not e -minimal, as the assertion RainIn(l) is not in fact necessary for the query to be entailed. Finally, solution D4 is not s -minimal. Observe that by dropping ABoxes D−2 and D−1 , and “shifting” D−4 and D−3 to the right by two time points, we obtain a non-equivalent s -minimal solution. 4 Complexity Analysis In this section, we study the combined complexity of different variants of the temporal query abduction problem. The proofs are included in the appendix. Note that “recognition” results, w.r.t., a minimality criterion, signals that the underlying decision procedure is complete but not necessarily sound, i.e. we ensure that all minimal solutions are found by the procedure, but it might be still necessary to filter out some non-minimal ones which are also included in the outcome. A “computation” result implies soundness as well [7]. We start by addressing ABox abduction, i.e., the problem of abducing a minimal ABox ensuring entailment and non-entailment of selected CQs at a single time point. Definition 5 (ABox abduction). An ABox abduction problem is a tuple Ω = (T , A, P, N ), where T is a TBox, A an ABox, and P, N ⊆ QΣ are sets of boolean CQs. An ABox D is called a solution to problem Ω iff A ∪ D is consistent with T and: 1. T , A ∪ D |= [q], for every q ∈ P , 2. T , A ∪ D |= ¬[q], for every q ∈ N . Note, that e - and b -minimality criteria transfer immediately from Defini- tion 4, on considering a single ABox as an A-sequence with exactly one element. The s -minimality does not apply in the context of ABox abduction. The results obtained here rest on and extend some of those presented in [7]. Lemma 1 (Solving ABox abduction problems). Let Ω be an ABox abduc- tion problem and D an e -minimal solution to Ω. Then: 1. computing D for Ω = (T , ∅, P, ∅) is in PTime, if T = ∅ or D is b -minimal, 2. recognizing D for Ω = (T , A, P, ∅) is NP-complete, if T 6= ∅ or A =6 ∅, 3. computing D for Ω = (T , A, P, N ) is DP-complete, if P 6= ∅ and N 6= ∅, even when A = ∅ and irrespective of deciding b -minimality, where D is fixed up to renaming individuals in the included ABox assertions. The PTime result in the first case follows by observing that the addressed ABox abduction problems can be solved immediately by grounding the conjuncts of the CQs. Solving the second type of problems might involve NP-complete CQ entailment checks and/or a nondeterministic choice from an exponential number of queries in the FO rewriting of a CQ. For the last case, recall that DP denotes the intersection of the classes of NP and coNP problems. The result is due to the simultaneous presence of positive and negative CQs, which requires entailment and non-entailment checks, with the latter in coNP. Next, we focus on proper TQA problems in TQL. The central challenge to be addressed is that solutions to such problems are in principle of infinite length, which makes their computation generally impossible in finite time. However, we are able to identify certain finite structures which can be unambiguously unfolded into the corresponding A-sequences. Thus, rather than searching for A-sequences directly, we focus on finding their finite representations, called A-structures. Definition 6 (A-structures). An A-structure is a tuple S = (S, S0 , →), where S = S + ∪ S − is a finite set of ABoxes, S0 ∈ S + ∩ S − is the initial ABox, and → is a successor function, such that →: S + 7→ S + and →: S − 7→ S − . The unfolding of S is an A-sequence . . . , Sj−1 , Sj , . . . , S0 , . . . , Si , Si+1 , . . ., where for every i ≥ 0, Si → Si+1 , for some Si+1 ∈ S + , and for every j ≤ 0, Sj → Sj−1 , for some Sj−1 ∈ S − . The key to the abductive algorithms we develop here is ensuring existence of an upper bound on the size of the A-structures that are to be found. Tech- nically, the proofs rest on the construction of so-called quasimodels, which link A-structures with the input abductive problems. Intuitively, a quasimodel s = (si )i∈Z is an abstraction of an infinite model satisfying the query. Each si -th element (ti , B(ti )) in that sequence consists of the set ti of subformulas of φ that must be satisfied in i and the minimal ABox B(ti ) satisfying all positive and negative occurrences of CQs at i, i.e., [q], ¬[q] ∈ ti . Particularly instrumental are special quasimodels called ultimately periodic, comprised by two infinite subse- quences (one future, one past), where each subsequence consists of a finite initial sequence called the head, followed by an infinite repetition of some terminal sub- sequence of the head, called the period. We show that every e - and s -minimal solution to a TQA problem corresponds to an ultimately periodic quasimodel, which can be further associated with an A-structure of a particular size, linear in the length of the heads of the two sequences comprising the quasimodel. For TQA over TQL formulas the relevant A-structures consist of at most exponentially many states in the size of the given abduction problem. This res- onates closely with the “small model” property of LTL, which rests on similarly defined bounds [23]. Recall that by `(†) we denote the total size of the input †. Lemma 2 (A-sequence vs. A-structure). Let D be an e - and s -minimal solution to a TQA problem Ω = (T , A, φ), where A = (Ai )i∈I and φ is a TQL formula. Then there exists an A-structure S whose unfolding is D, such that |S| = f (`(Ω)), for some function f (x) ∈ O(2x ). The basic algorithm which recognizes e - and s -minimal solutions to TQA problems is an adaptation of Sistla and Clarke’s decision procedure for LTL [23]. In principle, the underlying computation model has to be changed from finite- state automata to finite-state transducers, i.e., Turing machines using additional write-only output tapes, as a recognized solution needs to be effectively pre- sented. This revision, however, does not affect the complexity of the algorithm, which remains PSpace-complete, irrespectively of the possibly exponential size of solutions. Theorem 1 (Recognizing TQA solutions). Recognizing an e - and s - minimal solution to a TQA problem (T , A, φ), where φ is a TQL formula, is PSpace-complete. As the hardness result transfers from the satisfiability problem in the under- lying LTL, it is easy to see that the result holds even for pure-future (only U operator) or pure-past TQL formulas. In case of TQLF,P and TQL+ we are able to show that the upper bound on the size of the relevant A-structures is smaller — in fact, linear in the size of the input. Lemma 3 (A-sequence vs. A-structure for TQLF,P , TQL+ ). Let D be an e - and s -minimal solution to a TQA problem (T , A, φ), where A = (Ai )i∈I and φ is a TQLF,P or TQL+ formula. Then there exists an A-structure S whose unfolding is D, such that |S| ≤ f (`(φ)), for some f (x) ∈ O(x). Given the linear size of the solutions, the worst case complexity of recogniz- ing TQA solutions for TQLF,P drops to DP. In this case, it is sufficient to guess a linearly long head of a candidate quasimodel and verify it satisfies all the neces- sary structural conditions. As states in the quasimodel can contain positive and negative occurrences of CQs, the abduction of the respective minimal ABoxes is DP-complete. Theorem 2 (Recognizing TQA solutions for TQLF,P ). Recognizing an e - and s -minimal solution to a TQA problem (T , A, φ), where φ is a TQLF,P formula, is DP-complete. In case of TQL+ , the complexity of abductive reasoning is even smaller, in fact NP-complete, as no negative CQs have to be considered. Reducing the TQL language further down to TQLF,P,+ does not yield any additional gain, even when b -minimality is considered and the A-sequence A is empty. This is a consequence of the non-determinism involved in choosing the order in which U-/S-formulas are fulfilled in the consecutive states. In the worst case, all permu- tations must be considered, which enables reduction from the NP-hard Hamil- tonian path problem. Theorem 3 (Recognizing TQA solutions for TQL+ , TQLF,P,+ ). Recogniz- ing a e - and s -minimal solution to a TQA problem (T , A, φ), where φ is a TQL+ or TQLF,P,+ formula, is NP-complete. The result holds even for b - minimal solutions and when A = ∅. Note that in most cases computing TQA solutions, as opposed to recognizing them, is bound to be of a higher complexity due to the necessity of conducting pairwise comparisons between exponentially many alternatives. The findings reported above, neatly reflect the modular character of TQL, which allows for handling the embedded CQs largely independently from rea- soning about the temporal dimension of the queries. In case of TQL entail- ment, this feature suggests a universal way of defining the upper complexity bound in different fragments of the language [13]. The bound is implied by the generic algorithm consisting of any (standard) decision procedure for the tem- poral language, augmented with an oracle deciding entailment/non-entailment of the CQs. Whenever the underlying LTL is in PSpace, then TQL entailment must be in PSpaceDP = PSpace. In TQLF,P the same argument leads to a procedure in NPDP =DP. Finally in TQLF,P,+ , where CQs occur only in positive form, we obtain NPNP =NP bound. These results clearly mirror the identified bounds for TQA problems in the corresponding fragments. The analysis conducted in this section shows that TQA problems are compu- tationally hard in general, but can be made easier by progressively simplifying the assumed setting. Notably, by restricting the expressiveness of temporal op- erators and eliminating negation from the underlying TQL, the complexity of reasoning can be reduced from PSpace- to NP-complete. The remaining non- determinism, warranting NP-hardness, can be mostly attributed to the size of FO rewritings of CQs and the number of alternative orders in which U/S-subformulas are to be fulfilled over time. Can these too be tamed granting an even lower com- plexity? Most likely, yes. We suspect that by considering b -minimal solutions and allowing only formulas whose structure unambiguously determines the or- der of fulfilment of U/S-subformulas, the combined complexity of prediction and explanation should drop further to PTime. 5 Conclusions In this paper, we have defined a novel problem of temporal query abduction in the context of data represented in DL-Lite. A number of complexity results, which we have delivered for different restricted fragments of the studied setting, imply concrete ways of constraining the problem in order to render abductive reasoning more feasible in practice. As processing temporal semantic data becomes an increasingly important task in many applications, understanding and being able to operationalize such constraints is crucial for efficient implementations. More generally, we believe that the use of TQL-like queries for representing and reasoning about temporal data patterns and their correlations defines a highly promising approach to bridging the gap between the semantic perspective on temporal data and the statistical view, endorsed in the data mining field. As initiated in [16], we intend to further the study of forms of reasoning which could naturally benefit from existence of such a link, such as prediction and explanation over time series and streaming semantic data. References 1. Baader, F., Calvanese, D., Mcguinness, D.L., Nardi, D., Patel-Schneider, P.F.: The description logic handbook: theory, implementation, and applications. Cambridge University Press (2003) 2. Batsakis, S., Stravoskoufos, K., Petrakis, E.G.M.: Temporal reasoning for support- ing temporal queries in OWL 2.0. In: Proc. of the Int. Conf. on Knowledge-based and Intelligent Information and Engineering Systems (KES-11) (2011) 3. Bienvenu, M.: Complexity of abduction in the EL family of lightweight descrip- tion logics. In: Proc. of the International Conference on Principles of Knowledge Representation and Reasoning (KR-08) (2008) 4. Borgwardt, S., Lippmann, M., Thost, V.: Temporal query answering in the de- scription logic DL-Lite. In: Proc. of the International Symposium on Frontiers of Combining Systems (FroCoS-13) (2013) 5. Brusoni, V., Console, L., Terenziani, P., Dupr, D.: An efficient algorithm for tem- poral abduction. In: Proc. of Advances in Artificial Intelligence (AI*IA-97) (1997) 6. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3), 385–429 (2007) 7. Calvanese, D., Ortiz, M., Simkus, M., Stefanoni, G.: The complexity of explaining negative query answers in DL-Lite. In: Proc. of the International Conference on the Principles of Knowledge Representation and Reasoning (KR-12) (2012) 8. Colucci, S., Noia, T.D., Sciascio, E.D., Donini, F.M., Mongiello, M.: A uniform tableaux-based approach to concept abduction and contraction in ALN. In: Proc. of the International Workshop on Description Logics (DL-04) (2004) 9. Elsenbroich, C., Kutz, O., Sattler, U.: A case for abductive reasoning over ontolo- gies. In: Proc. of the International Workshop on OWL: Experiences and Directions (OWLED-06) (2006) 10. Espinosa Peraldi, S., Kaya, A., Melzer, S., Möller, R., Wessel, M.: Multimedia interpretation as abduction. In: Proc. of the International Workshop on Description Logics (DL-07) (2007) 11. Gabbay, D.: The declarative past and imperative future: Executable temporal logic for interactive systems. In: Proc. of the Conference on Temporal Logic in Specifi- cation (TLS-87) (1987) 12. Grandi, F.: T-SPARQL: a TSQL2-like temporal query language for RDF. In: Proc. of the International Workshop on Querying Graph Structured Data (2010) 13. Gutiérrez-Basulto, V., Klarman, S.: Towards a unifying approach to representing and querying temporal data in description logics. In: Proc. of the Int. Conf. on Web Reasoning and Rule Systems (RR-12) (2012) 14. Halland, K., Britz, K.: Naive ABox abduction in ALC using a DL tableau. In: Proc. of the International Workshop on Description Logics (DL-12) (2012) 15. Klarman, S., Endriss, U., Schlobach, S.: ABox abduction in the description logic ALC. Journal of Automated Reasoning 46, 43–80 (2011) 16. Klarman, S., Meyer, T.: Prediction and explanation over DL-Lite data streams. In: Proc. of the International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR-19) (2013) 17. Klarman, S., Meyer, T.: Complexity of temporal query abduction in DL-Lite. Tech. rep., CAIR, UKZN/CSIR Meraka. http://klarman.synthasite.com/resources/ KlaMeyDL14.pdf (2014) 18. Lambrix, P., Wei-Kleiner, F., Dragisic, Z., Ivanova, V.: Repairing missing is-a structure in ontologies is an abductive reasoning problem. In: Proc. of the Interna- tional Workshop on Debugging Ontologies and Ontology Mappings (WoDOOM-13) (2013) 19. Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description logic EL using a relational database system. In: Proc. of the International Joint Conference on Artifical Intelligence (IJCAI-09) (2009) 20. Motik, B.: Representing and querying validity time in RDF and OWL: A logic- based approach. Web Semantics: Science, Services and Agents on the World Wide Web 12-13, 3–21 (2012) 21. Pan, J.Z., Du, J., Qi, G., Shen, Y.D.: Towards practical ABox abduction in large description logic ontologies. International Journal on Semantic Web and Informa- tion Systems 8(2), 1–33 (2012) 22. Ribeiro, C., Porto, A.: Abduction in temporal reasoning. In: Proc. of the Interna- tional Conference on Temporal Logic (ICTL-94) (1994) 23. Sistla, A.P., Clarke, E.M.: The complexity of propositional linear temporal logics. Journal of ACM 32(3), 733–749 (1985)