In this paper, we construct a combination HS-LitehHorn of the Halpern-Shoham interval temporal logic HS [15] with the description logic DL-LitehHorn [12, 1], which is a Horn extension of the standard language OWL 2 QL. The temporal operators of HS are of the form hRi (`diamond') and [R] (`box'), where R is one of Allen's interval relations After, Begins, Ends, During, Later, Overlaps and their inverses (A, B, E, D, L, O). The propositional variables of HS are interpreted by sets of closed intervals [i; j] of some ow of time (e.g., Z, R), and a formula hRi' ([R]') is regarded to be true in [i; j] i ' is true in some (respectively, all) interval(s) [i0; j0] such that [i; j]R[i0; j0] in Allen's interval algebra. In HS-LitehHorn, we represent temporal data by means of assertions such as SummerSchool(RW; t1; t2) and teaches(US; DL; s1; s2), which say that RW is a summer school that takes place in the time interval [t1; t2] and US teaches DL in the time interval [s1; s2]. Note that temporal databases store data in a similar format [17]. Temporal concept and role inclusions are used to impose constraints on the data and introduce new concepts and roles. For example, AdvCourse u hDiMorningSession v ? says that advanced courses are not given in the morning sessions described by hBiLectureDay u hAiLunch v MorningSession; teaches v [D]teaches claims that the role teaches is downward hereditary (or stative) in the sense that if it holds in some interval then it also holds in all of its sub-intervals; [D](hOiteaches t hDiteaches) u hBiteaches u hEiteaches v teaches, on the contrary, states that teaches is coalesced (or upward hereditary). The inclusions teaches v [D]teaches and [D](hOiteaches t hDiteaches) v teaches ensure that teaches is both upward and downward hereditary. On the other hand, `rising stock market' and `high average speed' are typical examples of concepts that are not downward hereditary; for a discussion of these notions see [6, 21, 18]. Although the complexity of full HS-LitehHorn remains unknown, in this paper we de ne two fragments, HS-LitehHo=rnat and HS-LitehHo[rGn], where satis ability and instance checking are P-complete for both combined and data complexity. Our interest in tractable description logics with interval temporal operators is motivated by possible applications in ontology-based data access (OBDA) [12] to temporal databases. In this context, we naturally require reasonably expressive yet tractable ontology and query languages with temporal constructs (although
Introduction
? This extended abstract is an abridged version of [
Description Logic HS -LitehHorn The language of HS-LitehHorn contains individual names a0; a1; : : : , concept names A0; A1; : : : , and role names P0; P1; : : : . Basic roles R, basic concepts B, temporal roles S and temporal concepts C are given by the grammar
R ::= S ::=
Pk j R j [R]S
Pk ; j hRiS;
B ::= C ::=
Ak j 9R; B j [R]C j hRiC; where R is one of Allen's interval relations or the universal relation G. Over the closed intervals [i; j] = fn 2 Z j i n jg, for i j, we set: { [i; j]A[i0; j0] { [i; j]B[i0; j0] { [i; j]E[i0; j0] { [i; j]D[i0; j0] { [i; j]L[i0; j0] { [i; j]O[i0; j0] i i i i i i j = i0, i = i0 and j j0, i i0 and j = j0, i i0 and j0 j, j i0, i i0 j j0 (After) (Begins)
(Ends) (During)
(Later) (Overlaps) and de ne their inverses in the standard way. Note that we allow single-point intervals [i; i] and use non-strict instead of the more common < (in fact, one can show that the use of < would make reasoning non-tractable). An HS-LitehHorn TBox is a nite set of concept and role inclusions and disjointness constraints of the form
C1 u C1 u u Ck v C+; u Ck v ?;
S1 u S1 u u Sk v S+; u Sk v ?; where C+; R+ denote temporal concepts and roles without diamond operators hRi. An HS-LitehHorn ABox is a nite set of atoms of the form Ak(a; i; j) and Pk(a; b; i; j) in which temporal constants i j are given in binary. An HS-LitehHorn knowledge base (KB) is a pair K = (T ; A), where T is a TBox and A an ABox.
An HS-LitehHorn interpretation, I, consists of a family of standard (atemporal) DL interpretations I[i; j] = ( I ; I[i;j]), for all i; j 2 Z with i j, in which
I 6= ;, akI[i;j] = akI for some ( xed) akI 2 I , AkI[i;j] I and PkI[i;j] I I . The role and concept constructs are interpreted in I as follows: (Pk )I[i;j] = ([R]S)I[i;j] = (x; y) j (y; x) 2 PkI[i;j] ; \ SI[i0;j0];
(9R)I[i;j] = ([R]C)I[i;j] = x j (x; y) 2 RI[i;j] ; \ CI[i0;j0] [i;j]R[i0;j0] [i;j]R[i0;j0] and dually for the `diamond' operators hRi.
The satisfaction relation j= is de ned by taking:
I j= A(a; i; j) i I j= P (a; b; i; j) i I j= dk Ck v C
i I j= dk Sk v S i aI 2 AI[i;j]; (aI ; bI ) 2 P I[i;j]; Tk CkI[i;j] Tk SkI[i;j]
and similarly for disjointness constraints. Note that concept and role inclusions as well as disjointness constraints are interpreted globally. For a TBox inclusion or an ABox assertion , we write K j= if I j= , for all models I of K. 3
Propositional HS horn is Tractable
Denote by HShorn the fragment of HS-LitehHorn without role names and with
ABoxes that contain a single individual name. TBoxes in this restricted language
can be regarded as Horn formulas of the propositional interval temporal logic
HS, which is notorious for its nasty computational behaviour; for results on the
(un)decidability of various fragments of HS, see, e.g., [
Membership in P follows from the polynomial canonical model and P-hardness for (data) complexity is by reduction of the monotone circuit value problem.
So far, we have managed to lift this result to two proper interval temporal description logics, both of which are fragments of HS-LitehHorn. 4
Tractability of HS -LitehHo=rnat and HS -LitehHo[rGn] The rst fragment, denoted HS-LitehHo=rnat, only allows those HS-LitehHorn TBoxes that are at in the sense that their concept inclusions do not contain 9R on the right-hand side. Our second fragment, denoted HS-LitehHo[rGn], allows only the operator [G] in the de nition of temporal roles S (with no restrictions imposed on temporal concepts). Thus, unlike HS-LitehHo=rnat, the fragment HS-LitehHo[rGn] contains full DL-LitehHorn.
Theorem 2. (i ) The satis ability problem for HS-LitehHo=rnat and HS-LitehHo[rGn] KBs is P-complete for combined complexity.
(ii ) Instance checking for HS-LitehHo=rnat and HS-LitehHo[rGn] is P-complete for data complexity.
This result contrasts with the lower data complexity (AC0 and NC1) of
instance checking with point-based temporal DL-Lite [
In view of Theorem 2 (ii ), the temporal ontology languages HS-LitehHo=rnat and HS-LitehHo[rGn] cannot guarantee rst-order rewritability of even atomic queries, though we believe that datalog rewritings are possible. We leave the query rewritability issues, in particular, the design of DL-LitecHore-based fragments supporting rst-order rewritability as well as temporal extensions of the OWL 2 EL and OWL 2 RL pro les of OWL 2 for future research. 20. Montanari, A., Puppis, G., Sala, P.: Decidability of the interval temporal logic AABB over the rationals. In: Proc. MFCS 2014. LNCS, vol. 8634, pp. 451{463.
Springer (2014) 21. Terenziani, P., Snodgrass, R.T.: Reconciling point-based and interval-based semantics in temporal relational databases: A treatment of the Telic/Atelic distinction. IEEE Transactions on Knowledge and Data Engineering 16(5), 540{551 (2004)