=Paper=
{{Paper
|id=Vol-1193/paper_45
|storemode=property
|title=Complexity of Temporal Query Abduction in DL-Lite
|pdfUrl=https://ceur-ws.org/Vol-1193/paper_45.pdf
|volume=Vol-1193
|dblpUrl=https://dblp.org/rec/conf/dlog/KlarmanM14
}}
==Complexity of Temporal Query Abduction in DL-Lite==
https://ceur-ws.org/Vol-1193/paper_45.pdf
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)