We study access to temporal data with TEL, a temporal extension of the tractable description logic EL. Our aim is to establish a clear computational complexity landscape for the atomic query answering problem, in terms of both data and combined complexity. Atomic queries in full TEL turn out to be undecidable even in data complexity. Motivated by the negative result, we identify well-behaved yet expressive fragments of TEL. Our main contributions are a semantic and sufficient syntactic conditions for decidability and three orthogonal tractable fragments, which are based on restricted use of rigid roles, temporal operators, and novel acyclicity conditions on the ontologies.
Due to the increasing need to account for the temporal dimension of data available on the
Web [
In this paper, we study T EL, a temporal extension of EL [
(1) (2) Our main objective is to establish the limits of decidability and tractability of the query answering problem over T EL ontologies, in terms of both data and combined complexity. In order to set the foundations, we focus on temporal atomic queries. On the one hand, an atomic query like ViableParticipant(x; t) together with the temporal concept inclusion (1) effectively encodes a tree-shaped temporal conjunctive query. On the other hand, using (1) to extend the vocabulary with the concept ViableParticipant is closer to the spirit of the OBDA paradigm than repeating the same conjunction in similar user queries. Moreover, the recurrent pattern RequiresBloodTest is expressible as an atomic query RequiresBloodTest(x; t) with the temporal concept inclusion (2) but not expressible as a query without temporal concept inclusions such as (2). As we shall see, even for the atomic queries rather surprising (and challenging) results are obtained.
Our main contributions are complexity bounds, algorithms, and rewritability into DATALOG1S for atomic query answering in fragments of T EL. Since query answering over full T EL turns out to be undecidable even in data complexity, we investigate its fragments to attain decidability and tractability. First, for T EL , which allows only the ‘next-’
F and ‘previous-time’ P operators, we identify ultimate periodicity as a natural
semantic condition ensuring decidability, more precisely, PSPACE data complexity (the question
of decidability of the full T EL is left open for future work). Then, we identify a number
of fragments with better computational properties. (a) For the fragment of T EL without
rigid (not changing over time) roles on the right-hand side of concept inclusions, we
construct a polynomial rewriting into DATALOG1S , and so, establish PSPACE-completeness
for data complexity. This fragment contains all EL ontologies as well as both (1) and (2).
(b) Over temporally acyclic T EL -ontologies (with rigid roles), query answering is
PTIME-complete in both data and combined complexity. This tractable fragment
contains (1) and fully captures all atemporal EL ontologies and may prove particularly useful
in applications; it, however, does not contain (2). (c) Query answering over DL-acyclic
T EL -ontologies is NC1-complete for data complexity (in principle, highly
parallelizable). This fragment contains all acyclic EL ontologies as well as both (1) and (2) (a large
part of SNOMED CT is in fact acyclic). We remark that our two novel acyclicity
conditions (each constraining only one dimension) relax the ‘traditional’ notion of acyclicity
in (temporal) DLs [
We begin by introducing T EL, a temporal extension of the classical DL E L. Let NC, NR, NI be countably infinite sets of concept, role and individual names, respectively. We assume that NR is partitioned into two infinite sets, NrRig and NlRoc, of rigid and local role names, respectively. T EL-concepts are defined by the following grammar: C; D ::=
A j C u D j 9r:C j
C j 3 C; where A 2 NC, r 2 NR, and 2 fF; P g. A T EL-TBox is a finite set of concept inclusions (CIs) C v D and concept definitions (CDs) C D, for T EL-concepts C; D.
Data is given in terms of temporal ABoxes A, which are finite sets of assertions of the form A(a; n) and r(a; b; n), where A 2 NC, r 2 NR, a; b 2 NI, and n 2 Z. We denote by ind(A) the set of individual names occurring in A, and by tem(A) the set fn 2 Z j min A n max Ag, where min A and max A are, respectively, the minimal and maximal time points in A. The size, jT j and jAj, of T and A is the number of symbols required to write T and A, resp., with time points n 2 Z encoded in unary.
An interpretation I is a structure ( I; (In)n2ZI),awnhderrIeneach In is a classical DL interpretation with domain I: we have AIn I I. Rigid roles r 2 Nrig do not change their interpretation in time: rIn = rI0 for all n 2 Z. We usually write AR I;n and rI;n instead of AIn and rIn , respectively, and extend I;n as follows: (C u D)I;n = CI;n \ DI;n; (9r:C)I;n = d j there is e 2 CI;n with (d; e) 2 rI;n ; (
C)I;n = CI;n op 1; (3 C)I;n = d j d 2 CI;n op k for some k > 0 ; where op stands for + if = F and for if = P . Although we use strict 3 , our results do not depend on the choice.
TBoxes are interpreted globally: an interpretation I is a model of C v D, written I j= C v D, if CI;n DI;n, for all n 2 Z; and a model of C D if CI;n = DI;n, for all n 2 Z. We call I a model of a TBox T , written I j= T , if I j= for all 2 T . For ABoxes A we adopt the standard name assumption: aI;n = a for all a 2 ind(A), n 2 Z; thus, ind(A) I. The relation j= is extended to ABoxes: I j= A(a; n) iff a 2 AI;n and I j= r(a; b; n) iff (a; b) 2 rI;n; then, I j= A if I j= for all 2 A. An interpretation I is a model of a temporal knowledge base (KB) K = (T ; A), written I j= K, if I j= T and I j= A. Finally, K j= A(a; n) if I j= A(a; n) in every I j= K.
A temporal atomic query (TAQ) is of the form A(x; t), where A 2 NC, x an individual variable and t a temporal variable. A certain answer to A(x; t) over (T ; A) is a pair (a; n) 2 ind(A) tem(A) with (T ; A) j= A(a; n). We study the problem of TAQ answering:
Input: TBox T , ABox A, TAQ A(x; t) and a pair (a; n).
Question: Is (a; n) a certain answer to A(x; t) over (T ; A)? Our results concern both the combined and data complexity of the problem: for data complexity, the TBox is fixed. As usual, for a complexity class C and a class X of TBoxes, we say that TAQ answering over X is C-hard in data complexity if there is some T 2 X such that answering TAQs over T is C-hard. Conversely, TAQ answering over X is in C in data complexity if answering TAQs over T is in C for all T 2 X .
As classes X , we will in particular look at full T EL and its fragments T EL3 and T EL , in which, respectively, only the temporal operators 3 and are allowed. Note that 3 on the left-hand side (and 2 with the usual semantics on the right-hand side) of CIs can be expressed in T EL , e.g., instead of 3P A v C or, equivalently, A v 2F C, take A v A0 and P A0 v A0 u C, for a fresh concept name A0. Observe also that rigid concepts, which do not change their interpretation in time, can be expressed in these two fragments using 3P 3F C v C and F C C, respectively.
Query Answering in T EL: Undecidability We first pinpoint different sources of complexity for the query answering problem in T EL in order to identify computationally well-behaved fragments later.
We begin by showing that TAQ answering over T EL3 is undecidable. The known
undecidability of subsumption in T EL3 [
Theorem 2. TAQ answering over T EL PSPACE-hard in data complexity.
is non-elementary in combined complexity and
The proof of PSPACE-hardness is close in spirit to that for DATALOG1S [
Decidability of TAQ answering over full T EL is left open as interesting and challenging future work; more insights on the difficulty of the problem are given in Section 4. Nevertheless, we show that extending T EL with certain DL constructs that are harmless for data complexity of atemporal query answering [26] immediately leads to undecidability. Let T ELI and T ELF be the extensions of T EL with inverse roles r and functionality axioms func(r), respectively.1 For both languages, we reduce the halting problem for the universal Turing machine to prove: Theorem 3. TAQ answering over T ELI and T ELF is undecidable in data complexity. 4
Foundations of Query Answering in T EL
In the rest of the paper, we study decidability and complexity of TAQ answering in
various fragments of T EL and T EL3. To this end, we first lay the groundwork for
the development of algorithms for query answering in those fragments by introducing
canonical quasimodels, which are succinct abstract representations of the universal
models of the KBs, see also [
We assume that T EL -TBoxes are in normal form: they consist of CIs of the form A u A0 v B;
A v 9r:B;
X v A; where A; A0; B 2 NC and X is a basic concept of the form A, A, or 9r:A, for A 2 NC. Observe that, without loss of generality, is restricted to the left-hand side of CIs: e.g., 1 with the usual semantics: (r )I;n = f(e; d) j (d; e) 2 rI;ng and I j= func(r) iff e1 = e2, for all (d; e1); (d; e2) 2 rI;n and n 2 Z.
A v F B is equivalent to P A v B. It is routine to show that every T EL -TBox can
be transformed into the normal form by introducing fresh concept names; see, e.g., [
Fix a KB (T ; A) with a T EL -TBox T in normal form. Let CN be the set of concept names in (T ; A). A map : Z ! 2CN is a trace for T if it satisfies the following: (t1) if A u A0 v B 2 T and A; A0 2 (n), then B 2 (n); (t2) if A v B 2 T and A 2 (n), then B 2 (n op 1).
Traces are the building blocks of quasimodels and are used to represent the temporal evolution of individual domain elements. For example, for T = f P C v B; P B v Cg, the map such that (i) = fBg for odd i and (i) = fCg for even i is a trace for T .
In order to describe interactions of domain elements, we require more notation. Let be a trace for T . For a rigid role r 2 NrRig, the r-projection of is a map projr( ) : Z ! 2CN that sends each i 2 Z to fA j 9r:B v A 2 T ; B 2 (i)g; for a local role r 2 NlRoc, projr( ) is defined in the same way on 0 but is ; for all other i 2 Z. Given a map % : Z ! 2CN and n 2 Z, we say that contains the n-shift of % and write % n if %(i n) (i), for all i 2 Z. For example, let T = f9r:B v B0g with rigid role r. In the picture below, trace a contains the 1-shift of the r-projection of B: B B0
B0
C
B B0
B0
C
B B0
B0
B projr( B) a
-1 0 1 A 2 3 4 Note that, if r were local then a would have to contain B0 only at 1 (but not at 3, etc.).
We are now fully equipped to define quasimodels. Henceforth, let D = ind(A) [ CN. A quasimodel Q for (T ; A) is a set of traces d for T (d 2 D) such that (q1) A 2 a(n), for all A(a; n) 2 A; (q2) B 2 B(0), for all B 2 CN; (q3) projr( b) 0 a, for all r(a; b; n) 2 A; (q4) if A 2 d(n) then projr( B) n d, for all d 2 D, n 2 Z and A v 9r:B in T . Intuitively, quasimodels represent models of (T ; A): each a stands for the ABox individual a; each B, on the other hand, represents all individuals that witness B for CIs A v 9r:B in T . The latter is, in fact, the crucial abstraction underlying quasimodels. Note that traces B are normalized: B occurs at time point 0, which has to be compensated by the shift operation in (q4). For example, in the picture above, if A v 9r:B 2 T then, in any model, a has an r-successor that belongs to B at moment 1. Such a successor can be obtained as a ‘copy’ of trace B shifted by 1 so that its origin, 0, matches moment 1 for a. Then, by (q4), a belongs to B0 at all odd moments.
For the purposes of query answering we need to identify canonical (minimal)
quasimodels. We define the canonical quasimodel as the limit of the following saturation
(chase-like) procedure. Start with initially empty maps d, for d 2 D, and apply (t1)–
(t2), (q1)–(q4) as rules: (q3), for example, says ‘if r(a; b; n) 2 A and A 2 projr( b)(i),
then add A to a(i).’ Then we have the following characterization:
Theorem 4. Let T be a T EL -TBox and Q = f d j d 2 Dg the canonical quasimodel
of (T ; A). Then, (T ; A) j= A(a; i) iff A 2 a(i), for any A 2 CN, a 2 ind(A), i 2 Z.
The procedure for constructing the canonical quasimodel deals with infinite data
structures (traces) and is generally not terminating. So, although Theorem 4 provides a
criterion for certain answers, it does not immediately yield a decision algorithm for
full T EL . We remark that known techniques for dealing with such infinite structures
cannot be easily applied: for example, MSO (over Z), a standard tool for decidability
proofs in temporal DLs [
The starting point of the rest of the paper is a semantic condition on the canonical quasimodel, ultimate periodicity, which ensures decidability, at least in data complexity. Let T be a T EL -TBox and Q the canonical quasimodel for (T ; ;). We say that T is ultimately periodic, if there is p 2 N such that all B, B 2 CN, in Q are ultimately p-periodic, that is, for each B 2 CN, there are positive integers mP ; pP ; mF ; pF p satisfying the following conditions:
B(n pP ) =
B(n); for all n mP ;
B(n + pF ) =
B(n); for all n mF : Intuitively, an ultimately p-periodic trace has repeating sections on the left and on the right: mP 2pP mP pP mP 0 mF mF +pF mF +2pF The condition of ultimate periodicity is rather natural. On the practical side, it is motivated by applications with recurrent patterns such as health care support [31], see concept inclusions (1) and (2) in Section 1. From the theoretical point of view, any satisfiable LTL formula has an ultimately periodic model [28].
Theorem 5. TAQ answering over ultimately periodic T EL -TBoxes is PSPACE-complete in data complexity.
PSPACE-hardness follows from (the proof of) Theorem 2. We prove the matching upper
bound by rewriting an ultimately periodic T EL -TBox T into DATALOG1S [
r(x; y; t); A(x; t); A0(x; t); r(x; y; t); A(y; t); for r 2 NrRig in T ; Second, we observe that, for any trace a in the canonical quasimodel Q of any (T ; A), if A 2 a(n) and A v 9r:B 2 T then, by (q4), a contains the n-shift not only of projr( B) but also of A. Since T is ultimately periodic, for each trace B, we fix integers mP , pP , mF , pF and take the following rules with a fresh predicate FB: A(x; t + i) A(x; t + i)
B(x; t);
FB(x; t); FB(x; t + mF )
B(x; t) and
FB(x; t + pF ) for 0 for 0 i < mF and A 2 i < pF and A 2
FB(x; t);
B(i); B(mF + i); and symmetric rules with mP , pP and fresh PB. Intuitively, the rules in the first line replicate the (irregular) part of B from 0 to mF . The last two rules add recurring markers FB at the start of each period while the rules in the second line replicate the period of B starting from each marker FB.
The required DATALOG1S -program T contains all the rules above (note that CIs
of the form A v B are also covered by the rules for traces B). Using the canonical
quasimodel and Theorem 4, it is readily seen that T is equivalent to T : for every
temporal ABox A, the answers to T over A coincide with the certain answers to
(T ; A). Theorem 5 follows from the PSPACE data complexity in DATALOG1S [
Observe that Theorem 5 does not imply decidability of full T EL , since it is open whether every T EL -TBox is ultimately periodic. We thus turn our attention to sufficient syntactic conditions for ultimate periodicity and obtain tight complexity bounds for both data and combined complexity for the resulting fragments. We consider two types of conditions: restricted use of rigid roles and acyclicity of concept inclusions. 5
We consider T ELloc, the restriction of T EL in which only local roles are allowed. Due to the reduced interaction between temporal and DL component, we obtain data tractability. Theorem 6. TAQ answering over T ELloc is PSPACE-complete in combined and PTIMEcomplete in data complexity.
Lower bounds follow from PSPACE- and PTIME-hardness of entailment in
HornLTL [
PA;d ! PB;d); nPA;a; PB;B; nPB;b !
nPA;a; PB0;B ! 2(PA;d ! PA0;d); where n is Fn if n 0 and P n if n < 0 and 2 is the ‘globally’ operator. It is readily verified that 'T ;A is as required (crucially, (q4) for local roles boils down to the last formula above). Since entailment in LTL is in PSPACE [32] and 'T ;A is polynomial in the size of (T ; A), we obtain membership in PSPACE for combined complexity.
For PTIME data complexity, observe that traces B, for B 2 CN, are ultimately 2jT jperiodic because they are traces of the canonical quasimodel for (T ; ;); so, they can be stored in constant space. Next, traces a, a 2 ind(A), are ultimately 2jT j+jAj-periodic, but a closer inspection reveals that the middle irregular section, mP + mF , is bounded by jAj + 2jT j, while both periods, pP and pF , by 2jT j; see [3, Lemma 3]. So, Q requires space bounded by a polynomial in jAj. Since each rule application extends the traces, the saturation procedure constructing Q terminates in polynomial time in jAj.
Since TBoxes without rigid roles at all may be too restrictive for applications, we consider T ELl-rig-TBoxes: rigid roles are allowed only in CIs of the form 9r:B v A. In the following theorem, the lower bound follows from (the proof of) Theorem 2; for the upper bounds, we construct rewritings into DATALOG1S , similarly to T in Section 4. Theorem 7. TAQ answering over T ELl-rig is PSPACE-complete in data complexity and in EXPTIME in combined complexity. 6
It is known that acyclicity conditions often lead to better complexity. For example,
acyclic TBoxes are a way of obtaining CTL-based temporal extensions of EL that have
rigid roles and enjoy PTIME subsumption [
Acyclic TBoxes are finite sets of CDs A C, A 2 NC, such that no two CDs have the same left-hand side, and there are no CDs A1 C1; : : : ; Ak Ck in T such that Ai+1 occurs in Ci, for all 1 i k (where Ak+1 := A1). We say A is defined in T if A C 2 T and primitive otherwise. We obtain the following basic tractability result. Theorem 8. TAQ answering over acyclic T EL is in LOGTIME-uniform AC0 in data complexity and in PTIME in combined complexity.
The PTIME upper bound in combined complexity is subsumed by Theorem 10 below.
We establish the LOGTIME-uniform AC0 upper bound by rewriting into FO(+). More
precisely, for a given TAQ A(x; t) and TBox T , we construct a two-sorted first-order
formula 'T ;A(x; t) with functions 1 on temporal terms such that (T ; A) j= A(a; i) iff
A (viewed as an interpretation) is a model of 'T ;A(a; i), for all ABoxes A, a 2 ind(A),
i 2 Z. We construct 'T ;A(x; t) by adapting the strategy developed for atemporal EL [
B(x; t) = 'T ;B(x; t op 1); if A is primitive; if A
C 2 T ; where SA(x; t) is a disjunction of all B(x; t), for a concept name B, with T j= B v A, and Rr(x; y; t) is r(x; y; t) for r 2 Nloc and 9t0 r(x; y; t0) for r 2 NrRig. Note that 'T ;A is
R
an FOZ-rewriting in the terminology of Artale et al. [
To address the restricted expressiveness of acyclic TBoxes, we next introduce novel weaker notions of acyclicity that restrict only one dimension, either DL or temporal. DL Acyclicity First, we introduce DL-acyclic T EL -TBoxes, which are well-suited as temporal extensions of, say, biomedical ontologies that may require recurrent patterns but have an acyclic DL component. A T EL -TBox T with concept names CN is called DL-acyclic if there is a mapping `DL : CN ! N such that: (i) A v 9r:B or 9r:B v A 2 T implies `DL(A) > `DL(B); (ii) A v B implies `DL(A) = `DL(B); (iii) A u A0 v B 2 T implies `DL(A) = `DL(A0) = `DL(B).
We say that a DL-acyclic TBox is of depth k if k is the smallest integer m such that there is such a mapping `DL satisfying `DL(B) m for all B 2 CN.
Theorem 9. TAQ answering over DL-acyclic T EL -TBoxes of depth k, k 1, is
k-EXPSPACE-complete in combined complexity and NC1-complete in data complexity.
A closer inspection of the non-elementary lower bound proof in Theorem 2 reveals
that the TBox used is DL-acyclic and TAQ answering over TBoxes of depth k is
k-EXPSPACE-hard. NC1-hardness in data complexity follows by reduction of the word
problem of NFAs to TAQ answering (even without the DL dimension); see [
For the matching upper bounds, fix (T ; A) with T of depth k. We devise a completion procedure, which is based on special LTL-formulas and implies ultimate periodicity of all traces in the canonical quasimodel of (T ; A); cf. Section 5. Given any A, let Ai consist of all A(a; i) and r(a; b; i) in A as well as all assertions r(a; b; i) such that r 2 Nrig and r(a; b; j) 2 A, for some j 2 Z. The algorithm separates consequences
R coming from the role structure in the ABox and local temporal consequences of T . In particular, it exhaustively adds assertions A(a; i) to A if either (T ; Ai) j= A(a; i) or
B(a; i op 1) 2 A and
B v A 2 T : (3)
It turns out that Ai in (3) can be replaced by its suitably defined quotient Bi. Intuitively, the logic can only distinguish distinct trees of depth k, whose number depends on jT j only; so, the size of Bi is independent of jAj. By induction on depth k, we define LTL-formulas 'a;i of k-fold-exponential size characterizing all A 2 CN such that (T ; Bi) j= A(a; i): we start from formulas as in Theorem 6; the induction step takes account of the structure of Bi and incurs an exponential blowup.
For the combined complexity upper bound, observe that each of the polynomially many 'a;i can be analyzed in k-EXPSPACE. For the data complexity upper bound, note that checking (T ; Bi) j= A(a; i) can be done in constant time. The second option in (3), however, cannot be implemented directly as the number of steps depends on jAj. Instead, by using Bu¨chi automata, we show that the question of whether all traces extending A have A at position i is a regular property and so, is in NC1.
Temporal Acyclicity We next look at an orthogonal restriction that admits recursion in the DL dimension; it generalizes not only acyclic T EL -TBoxes but also general EL-TBoxes. A T EL -TBox T with concept names CN is temporally acyclic if there is ` : CN ! N such that (i) P A v B or F B v A 2 T implies ` (B) = ` (A) + 1; (ii) 9r:B v A or A v 9r:B 2 T implies ` (A) = ` (B); (iii) A u A0 v B 2 T implies ` (A) = ` (A0) = ` (B).
Theorem 10. TAQ answering over temporally acyclic T EL is PTIME-complete in data and combined complexity.
The lower bounds are inherited from EL. To prove the upper bounds, we show that KBs with a temporally acyclic T EL -TBox T enjoy a small quasimodel property: for every trace d in the canonical quasimodel Q of any (T ; A), we have d(j) = ;; if j > max A + jT j or j < min A jT j.
Intuitively, it means that the canonical quasimodel has a very restricted temporal extension that stretches at most jT j time points beyond the ABox. It follows that the procedure for constructing the quasimodel can be implemented in polynomial time: traces d require only polynomial space, and rules (q1)–(q4) extend the traces.
Inflationary TEL3
In this section, we follow an approach suggested by Artale et al. [
WtemedpeonraolteDtLhi-sLfirtaeg)manendtrbeystTriEcLtTi3nEL,3for inflationary T EL (which is related to inflationary
DATALOG1S [
We need to show only the upper bounds. Let T be a T ELi3n -TBox with concept names 3 in CN. Observe that T ELin can still be viewed as a fragment of T EL ; see Section 2. In fact, one can show an analogue of Theorem 4 with the following replacement of (t2): (t20) if 3 A v B 2 T and A 2 d(n), then B 2 d(n op k) for all k > 0. We establish a special shape of the traces in the canonical model of any (T ; A). Let % : Z ! 2CN be a map and let l; u 2 Z with l u. We say that % is an [l; u]-bow tie if %(i + 1), and if %(i + 1) = %(i) then all %(i0), for – for all i > u, we have %(i)
i0 i, coincide; – symmetrically, for all i < l, we have %(i) all %(i0), for i0 i, coincide. %(i 1), and if %(i 1) = %(i) then These properties mean that % grows monotonically to the right of u and to the left of l; in other words, % has inflationary behaviour. We prove that the traces d in the canonical quasimodel Q of (T ; A), for any A, enjoy the following properties: – – a is a [min A; max A]-bow tie, for each a 2 ind(A);
B is a [0; 0]-bow tie, for each B 2 CN.
Thus, the traces in Q can be represented in polynomial space because only the middle section and at most jCNj steps at both ends need to be stored. Since the traces are extended with every rule application, the procedure terminates after polynomially many steps; Theorem 11 follows.
We summarize the fragments of T EL, their relationships and the obtained complexity results in the following diagram:
PSPACE PSPACE NC1 AC0
DL-acyclic TEL
non-elem acyclic TEL in PTIME
TEL non-elem ultim. period. TEL non-elem
TELl-rig in EXPTIME temp. acyclic TEL
PTIME acyclic EL in PTIME
TELloc PSPACE
EL PTIME undecidable
3
TEL undecidable
3 TELin PTIME PTIME where the solid lines are inclusions between DLs, the dashed line is a reduction that preserves answers to all queries (model conservative extension). The data complexity is indicated by shading and the combined complexity is specified below the language.
We briefly remark that although acyclic and temporally acyclic T EL -TBoxes cannot express rigid concepts (cf. Section 2), we conjecture that our techniques can be extended to handle them without affecting the complexity results in the diagram. In contrast, DL-acyclic TBoxes can express rigid concepts and the results in the diagram above thus hold for this case.
Our data-tractability results show theoretical adequacy of the identified fragments of
T EL for data-intensive applications. Our two novel forms of acyclicity, DL- and temporal,
are somewhat close in spirit to multi-separability [
As our immediate future work, we will address decidability of (full) T EL and
then consider CQs with the + operation on temporal terms. We expect that our positive
results can be lifted to CQs using the combined approach [27], which utilizes a structure
similar to our canonical quasimodel to compute CQ certain answers in atemporal EL. We
will also study succinct and expressive representations of temporal data. For example,
the only known algorithm for DATALOG1S with binary encoding of timestamps in
the data runs in EXPTIME in the size of the data [
92–107 (2014) 26. Krisnadhi, A., Lutz, C.: Data complexity in the E L family of description logics. In: Proc.
LPAR-07. pp. 333–347 (2007) 27. Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description logic E L using a relational database system. In: Proc. IJCAI-09 (2009) 28. Manna, Z., Wolper, P.: Synthesis of communicating processes from temporal logic specifications. ACM Trans.Program.Lang. Syst. 6(1), 68–93 (1984) 29. O’Connor, M.J., Shankar, R.D., Parrish, D.B., Das, A.K.: Knowledge-data integration for temporal reasoning in a clinical trial system. Int. J. Med. Inform. 78, S77–S85 (2009) 30. Roth, M., Tan, W.: Data integration and data exchange: It’s really about time. In: Proc.
CIDR-13 (2013) 31. Shankar, R.D., Martins, S.B., O’Connor, M.J., Parrish, D.B., Das, A.K.: Representing and reasoning with temporal constraints in clinical trials using semantic technologies. In: BIOSTEC08, Revised Selected Papers. pp. 520–530 (2008) 32. Sistla, A.P., Clarke, E.M.: The complexity of propositional linear temporal logics. J. ACM 32(3), 733–749 (1985) 33. Stockmeyer, L.J.: The Complexity of Decision Problems in Automata Theory and Logic.
Ph.D. thesis, MIT, Cambridge, Massachusetts, USA (1974)