=Paper=
{{Paper
|id=Vol-1350/paper-06
|storemode=property
|title=Interval
Temporal Description Logics
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-06.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/ArtaleKRZ15
}}
==Interval
Temporal Description Logics==
https://ceur-ws.org/Vol-1350/paper-06.pdf
Interval Temporal Description Logics?
A. Artale1 , R. Kontchakov2 , V. Ryzhikov1 , and M. Zakharyaschev2
1
Faculty of Computer Science, Free University of Bozen-Bolzano, Italy
2
Department of Computer Science and Information Systems
Birkbeck, University of London, U.K.
1 Introduction
In this paper, we construct a combination HS-LiteH horn of the Halpern-Shoham
interval temporal logic HS [15] with the description logic DL-LiteH horn [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 (Ā, B̄, Ē, D̄, L̄, Ō). The propositional variables of HS are interpreted
by sets of closed intervals [i, j] of some flow of time (e.g., Z, R), and a formula
hRiϕ ([R]ϕ) is regarded to be true in [i, j] iff ϕ is true in some (respectively, all)
interval(s) [i0 , j 0 ] such that [i, j]R[i0 , j 0 ] in Allen’s interval algebra.
In HS-LiteH horn , 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 hD̄iMorningSession v ⊥ says that advanced courses are not given in
the morning sessions described by hB̄iLectureDay 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 hD̄iteaches) 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 hD̄iteaches) 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-LiteH horn remains unknown, in this paper
we define two fragments, HS-LiteH/flat horn and HS-Lite H[G]
horn , where satisfiability 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
?
This extended abstract is an abridged version of [4] presented at AAAI 2015.
some authors advocate the use of standard atemporal OWL 2 QL with temporal
queries [16, 7]). Our choice of HS as the temporal component of HS-LiteH horn
is explained by the fact that modern temporal databases adopt the (downward
hereditary) interval-based model of time [17, 13] and use coalescing to group time
points into intervals [6]. We show that, unfortunately, the logics HS-LiteH/flat
horn
and HS-LiteH[G]
horn cannot guarantee first-order rewritability of even atomic queries,
though we conjecture that datalog rewritings are possible.
2 Description Logic HS-LiteH
horn
The language of HS-LiteH horn 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 ::= Pk | Pk− , B ::= Ak | ∃R,
S ::= R | [R]S | hRiS, C ::= B | [R]C | hRiC,
where R is one of Allen’s interval relations or the universal relation G. Over the
closed intervals [i, j] = {n ∈ Z | i ≤ n ≤ j}, for i ≤ j, we set:
– [i, j]A[i0 , j 0 ] iff j = i0 , (After)
– [i, j]B[i0 , j 0 ] iff i = i0 and j ≥ j 0 , (Begins)
– [i, j]E[i0 , j 0 ] iff i ≤ i0 and j = j 0 , (Ends)
– [i, j]D[i0 , j 0 ] iff i ≤ i0 and j 0 ≤ j, (During)
– [i, j]L[i0 , j 0 ] iff j ≤ i0 , (Later)
– [i, j]O[i0 , j 0 ] iff i ≤ i0 ≤ j ≤ j 0 (Overlaps)
and define 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-LiteH horn
TBox is a finite set of concept and role inclusions and disjointness constraints of
the form
C1 u · · · u Ck v C + , S1 u · · · u Sk v S + ,
C1 u · · · u Ck v ⊥, S1 u · · · u Sk v ⊥,
where C + , R+ denote temporal concepts and roles without diamond operators
hRi. An HS-LiteH horn ABox is a finite 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-LiteH horn
knowledge base (KB) is a pair K = (T , A), where T is a TBox and A an ABox.
An HS-LiteH horn interpretation, I, consists of a family of standard (atemporal)
DL interpretations I[i, j] = (∆I , ·I[i,j] ), for all i, j ∈ Z with i ≤ j, in which
∆I 6= ∅, aI[i,j]
k = aIk for some (fixed) aIk ∈ ∆I , AI[i,j]
k ⊆ ∆I and PkI[i,j] ⊆ ∆I ×∆I .
The role and concept constructs are interpreted in I as follows:
(Pk− )I[i,j] = (x, y) | (y, x) ∈ PkI[i,j] , (∃R)I[i,j] = x | (x, y) ∈ RI[i,j] ,
\ 0 0 \ 0 0
([R]S)I[i,j] = S I[i ,j ] , ([R]C)I[i,j] = C I[i ,j ]
[i,j]R[i0 ,j 0 ] [i,j]R[i0 ,j 0 ]
and dually for the ‘diamond’ operators hRi.
The satisfaction relation |= is defined by taking:
I |= A(a, i, j) iff aI ∈ AI[i,j] ,
I |= P (a, b, i, j) iff (aI , bI ) ∈ P I[i,j] ,
T I[i,j]
⊆ C I[i,j] , for all intervals [i, j],
d
I |= k Ck v C iff Ck
Tk I[i,j]
⊆ S I[i,j] , for all intervals [i, j],
d
I |= k Sk v S iff k Sk
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 |= α if I |= α, for all models I of K.
3 Propositional HS horn is Tractable
Denote by HS horn the fragment of HS-LiteH horn 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., [14, 10, 9, 8, 19, 11, 20]. The
designed logic HS horn appears to be the first tractable fragment of HS:
Theorem 1. HS horn is P-complete for both combined and data complexity.
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-LiteH
horn .
4 Tractability of HS-LiteH/flat
horn
H[G]
and HS-Litehorn
The first fragment, denoted HS-LiteH/flat H
horn , only allows those HS-Litehorn TBoxes
that are flat in the sense that their concept inclusions do not contain ∃R on
the right-hand side. Our second fragment, denoted HS-LiteH[G] horn , allows only the
operator [G] in the definition of temporal roles S (with no restrictions imposed
on temporal concepts). Thus, unlike HS-LiteH/flat
horn , the fragment HS-Litehorn
H[G]
H
contains full DL-Litehorn .
H/flat
Theorem 2. (i ) The satisfiability problem for HS-Litehorn and HS-LiteH[G]
horn
KBs is P-complete for combined complexity.
(ii ) Instance checking for HS-LiteH/flat H[G]
horn and HS-Litehorn 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 [5, 3, 2].
In view of Theorem 2 (ii ), the temporal ontology languages HS-LiteH/flat
horn and
HS-LiteH[G]
horn cannot guarantee first-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-LiteH core -based fragments sup-
porting first-order rewritability as well as temporal extensions of the OWL 2 EL
and OWL 2 RL profiles of OWL 2 for future research.
References
1. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family
and relations. Journal of Artificial Intelligence Research (JAIR) 36, 1–69 (2009)
2. Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., Zakharyaschev,
M.: First-order rewritability of temporal ontology-mediated queries. In: Proc.
IJCAI 2015. AAAI (2015)
3. Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., Zakharyaschev,
M.: Temporal OBDA with LTL and DL-Lite. In: Proc. DL 2014. CEUR-WS,
vol. 1193, pp. 21–32. (2014)
4. Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: Tractable interval
temporal propositional and description logics. In: Proc. AAAI 2015. (2015)
5. Artale, A., Kontchakov, R., Wolter, F., Zakharyaschev, M.: Temporal descrip-
tion logic for ontology-based data access. In: Proc. IJCAI 2013. pp. 711–717.
IJCAI/AAAI (2013)
6. Böhlen, M.H., Snodgrass, R.T., Soo, M.D.: Coalescing in temporal databases. In:
Proc. VLDB’96. pp. 180–191. Morgan Kaufmann (1996)
7. Borgwardt, S., Lippmann, M., Thost, V.: Temporal query answering in the descrip-
tion logic DL-Lite. In: Proc. FroCoS 2013. LNCS, vol. 8152, pp. 165–180. Springer
(2013)
8. Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: The
dark side of interval temporal logic: marking the undecidability border. Annals of
Mathematics and Artificial Intelligence 71(1–3), 41–83 (2014)
9. Bresolin, D., Della Monica, D., Montanari, A., Sala, P., Sciavicco, G.: Interval
temporal logics over finite linear orders: the complete picture. In: Proc. ECAI 2012.
pp. 199–204. IOS Press (2012)
10. Bresolin, D., Della Monica, D., Montanari, A., Sala, P., Sciavicco, G.: Interval
temporal logics over strongly discrete linear orders: the complete picture. In: Proc.
GandALF 2012. EPTCS, vol. 96, pp. 155–168 (2012)
11. Bresolin, D., Della Monica, D., Montanari, A., Sciavicco, G.: The light side of interval
temporal logic: the Bernays-Schönfinkel fragment of CDT. Annals of Mathematics
and Artificial Intelligence 71(1–3), 11–39 (2014)
12. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable
reasoning and efficient query answering in description logics: The DL-Lite family.
Journal of Automated Reasoning 39(3), 385–429 (2007)
13. Date, C.J., Darwen, H., Lorentzos, N: Temporal data and the relational model.
Elsevier. (2002)
14. D. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev. Many-dimensional modal
logics: theory and applications. Studies in Logic. Elsevier, 2003.
15. Halpern, J.Y., Shoham, Y.: A propositional modal logic of time intervals. Journal
of the ACM 38(4), 935–962 (1991)
16. Klarman, S.: Practical querying of temporal data via OWL 2 QL and SQL:2011.
In: Short Papers Proc. LPAR 2013. EPiC Series 26, pp. 52–61. Easychair (2014)
17. Kulkarni, K.G., Michels, J.E.: Temporal features in SQL:2011. SIGMOD Record
41(3), 34–43 (2012)
18. Leo, J., Parsia, B., Sattler, U.: Temporalising EL concepts with time intervals. In:
Proc. DL. CEUR-WS, vol. 1193, pp. 620–632. (2014)
19. Marcinkowski, J., Michaliszyn, J.: The undecidability of the logic of subintervals.
Fundamenta Informaticae 131(2), 217–240 (2014)
20. Montanari, A., Puppis, G., Sala, P.: Decidability of the interval temporal logic
AĀB B̄ 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 seman-
tics in temporal relational databases: A treatment of the Telic/Atelic distinction.
IEEE Transactions on Knowledge and Data Engineering 16(5), 540–551 (2004)