=Paper=
{{Paper
|id=Vol-1350/paper-14
|storemode=property
|title=Temporal
Query Answering in EL
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-14.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/BorgwardtT15
}}
==Temporal
Query Answering in EL==
https://ceur-ws.org/Vol-1350/paper-14.pdf
Temporal Query Answering in EL∗
Stefan Borgwardt and Veronika Thost
Theoretical Computer Science, TU Dresden, Germany
firstname.lastname@tu-dresden.de
Motivation Context-aware systems use data collected at runtime to recognize
predefined situations and trigger adaptations; e.g., an operating system may use
sensors to recognize that a video application is out of user focus, and then adapt
application parameters to optimize the energy consumption. Using ontology-
based data access [12, 19], the situations can be encoded into queries that are
answered over an ABox containing the sensor data. In the TBox, we can encode
background knowledge about the domain. For example, if the user has been
working with another application on a second screen for a longer period, then
we may assume that he does not need the video to be displayed in the highest
resolution.
In this paper, we focus on the lightweight DL EL. We can state static knowl-
edge about applications (VideoApplication(app1)), dynamic knowledge about the
current context (NotWatchingVideo(user1)), as well as background knowledge like
VideoApplication u ∃hasUser.NotWatchingVideo v ∃hasState.OutOfFocus,
saying that a video application whose user is currently not watching the video
is out of user focus. Given such a knowledge base, we can use the conjunctive
query (CQ) ψ(x) := ∃y.hasState(x, y) ∧ OutOfFocus(y) to identify applications x
that can potentially be assigned a lower priority. More complex situations typi-
cally depend also on the behavior of the environment in the past—the operating
system should not switch configurations every time the user is not watching for
one second, but only after this has been the case for a longer period.
For that reason, we investigate temporal conjunctive queries (TCQs), origi-
nally proposed in [3, 4]. They combine conjunctive queries via the operators of
the propositional linear temporal logic LTL [14, 18]. We can use the TCQ
#− ψ(x) ∧ #− #− ψ(x) ∧ #− #− #− ψ(x) ∧
¬ ∃y.GotPriority(y) ∧ notEqual(x, y) S GotPriority(x)
to obtain all applications that were out of user focus during the three previous
(#− ) moments of observation, were prioritized by the operating system at some
point in time, and the priority has not (¬) changed since (S) then. The semantics
of TCQs is based on temporal knowledge bases (TKBs), which, in addition to the
TBox (which is assumed to hold globally, i.e., at every point in time), contains
a sequence of ABoxes A0 , A1 , . . . , An , representing the data collected at specific
∗
Partially supported by the DFG in CRC 912 (HAEC).
points in time. We designate with n the most recent time of observation (the
current time point), at which the situation recognition is performed. We also
investigate the related temporalized formalism EL-LTL, in which axioms, i.e.,
assertions or GCIs, are combined using LTL-operators.
Related Work The axioms in a TKB do not explicitly refer to time, but are
written in a classical (atemporal) DL; only the query is temporalized. In contrast,
[1,2,13,17] extend classical DLs by temporal operators that occur within concepts
and axioms. However, most of these logics yield high reasoning complexities, even
if the underlying atemporal DL is tractable. Lower complexities are obtained by
considerably restricting either the temporal operators or the underlying DL.
Regarding temporal properties formulated over atemporal DLs, ALC-LTL,
a variant of EL-LTL over the more expressive DL ALC, was first considered
in [6]. This was the basis for introducing TCQs over ALC-TKBs in [3], which
was extended to SHQ in [4]. However, reasoning in ALC is not tractable, and
context-aware systems often need to deal with large quantities of data and adapt
fast. TCQs over several lightweight logics have been regarded in [7], but only
over a fragment of LTL without negation. In [1], the complexity of LTL over
axioms of several members of the DL-Lite family of DLs has been investigated.
However, nothing is known about TCQs over these logics.
Results We investigate the combined and data complexity of the TCQ en-
tailment problem over TKBs formulated in EL. Moreover, we determine the
complexity of satisfiability of EL-LTL-formulae, and additionally consider the
special case where only global GCIs are allowed [6]. As usual, we consider rigid
concepts and roles, whose interpretation does not change over time. In this re-
gard, we distinguish three different settings, depending on whether concepts or
roles (or both) are allowed to be rigid. Since rigid concepts can be simulated by
rigid roles [6], only three cases need to be considered: (i) no symbols are allowed
to be rigid, (ii) only rigid concepts are allowed, and (iii) both concepts and roles
can be rigid. Tables 1 and 2 summarize our results and provide a comparison
to related work. The only previously known results that directly apply here are
P-hardness of CQ entailment in EL w.r.t. data complexity [11] and PSpace-
hardness of LTL [20]. Hence, we needed to prove three additional complexity
lower bounds.
With a single exception, the complexity of TCQ entailment in EL turns out to
be lower than that in ALC (and SHQ) [4]. Regarding satisfiability in EL-LTL,
Table 2 shows that rigid symbols lead to an increase in complexity that does
not affect DL-Lite krom -LTL [1], and even matches the complexity of ALC-LTL
and SHOQ-LTL in case (ii) [6, 15]. Thus, we partially confirm and refute the
conjecture of [6] that EL-LTL is as hard as ALC-LTL. In the following, we shortly
describe some of the ideas behind them. More details can be found in [8–10].
The upper bounds are obtained by a combination of techniques that were
developed for ALC-LTL [6] and refined for TCQs over SHQ-TKBs [4], methods
for checking LTL-satisfiability [4,20,21], and algorithms for atemporal reasoning
Table 1. The complexity of TCQ entailment. All results except the one for the data
complexity of case (iii) from [4] are tight.
Data Complexity Combined Complexity
(i) (ii) (iii) (i) (ii) (iii)
EL P co-NP co-NP PSpace PSpace co-NExpTime
ALC/SHQ [4] co-NP co-NP ExpTime ExpTime co-NExpTime 2-ExpTime
Table 2. The complexity of satisfiability in LTL over DL axioms.
Global GCIs
(i) (ii) (iii) (i) (ii) (iii)
DL-Lite krom [1] PSpace PSpace PSpace PSpace PSpace PSpace
EL PSpace NExpTime NExpTime PSpace PSpace PSpace
ALC [6] ExpTime NExpTime 2-ExpTime ExpTime ExpTime 2-ExpTime
in EL [5,16]. However, considerable work was necessary to obtain tight complexity
bounds in all cases we considered. The main approach is to separate the temporal
operators from the CQs (or axioms), which leaves us to solve a variant of the
satisfiability problem for LTL (in P w.r.t. data complexity and in PSpace w.r.t.
combined complexity), as well as the following problem for the DL part.
Definition 1. Let K = hT , (Ai )0≤i≤n i be a TKB and α1 , . . . , αm be CQs.1 A set
S = {X1 , . . . , Xk } ⊆ 2{α1 ,...,αm } is r-satisfiable w.r.t. a mapping ι : {0, . . . , n} →
{1, . . . , k} and K if there are interpretations J1 , . . . , Jk and I0 , . . . , In such that
– they share the same domain and interpret
V all
V rigid symbols in the same way;
– each Ji is a model of T and χi := Xi ∧ {¬αj | αj ∈ / Xi }; and
– each Ii is a model of hT , Ai i and χι(i) .
Individually, the satisfiability of the conjunctions χi can be tested in P w.r.t. data
complexity and in PSpace w.r.t. combined complexity. However, the problem is
to ensure the first condition, namely that all rigid names are interpreted in the
same way by all relevant interpretations.
In case (i), this restriction is obviously irrelevant. For case (iii), one can an-
swer an exponentially large UCQ over an exponentially large atemporal knowl-
edge base instead to obtain the upper bounds. The most difficult cases were
case (ii) for the combined complexity of TCQ entailment, and the case of global
GCIs in EL-LTL, where we needed to obtain PSpace upper bounds in the pres-
ence of rigid names. For these cases, we proved that it suffices to guess additional
data of polynomial size that can be added to the knowledge bases in order to
separate the satisfiability tests in Definition 1. These tests can then be integrated
into a PSpace-Turing machine for LTL-satisfiability [20] without increasing the
complexity.
Acknowledgements We want to thank Franz Baader, Marcel Lippmann, and
Carsten Lutz for fruitful discussions on the topic of this paper.
1
In the case of EL-LTL, these are axioms.
References
1. Artale, A., Kontchakov, R., Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal-
ising tractable description logics. In: Proc. of the 14th Int. Symp. on Temporal
Representation and Reasoning (TIME’07), pp. 11–22. IEEE Press (2007)
2. Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: A cookbook for
temporal conceptual data modelling with description logics. ACM Transactions on
Computational Logic 15(3), 25:1–25:50 (2014)
3. Baader, F., Borgwardt, S., Lippmann, M.: Temporalizing ontology-based data ac-
cess. In: Proc. of the 24th Int. Conf. on Automated Deduction (CADE’13). pp.
330–344. Springer-Verlag (2013)
4. Baader, F., Borgwardt, S., Lippmann, M.: Temporal query entailment in the de-
scription logic SHQ. Journal of Web Semantics (2015), doi:10.1016/j.websem.
2014.11.008, in press.
5. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proc. of the 19th Int.
Joint Conf. on Artificial Intelligence (IJCAI’05). pp. 364–369. Professional Book
Center (2005)
6. Baader, F., Ghilardi, S., Lutz, C.: LTL over description logic axioms. ACM Trans-
actions on Computational Logic 13(3), 21:1–21:32 (2012)
7. Borgwardt, S., Lippmann, M., Thost, V.: Temporalizing rewritable query languages
over knowledge bases. Journal of Web Semantics (2015), doi:10.1016/j.websem.
2014.11.007, in press.
8. Borgwardt, S., Thost, V.: LTL over EL axioms. LTCS-Report 15-07, Chair for
Automata Theory, TU Dresden (2015), see http://lat.inf.tu-dresden.de/
research/reports.html.
9. Borgwardt, S., Thost, V.: Temporal query answering in EL. LTCS-Report 15-
08, Chair for Automata Theory, TU Dresden (2015), see http://lat.inf.
tu-dresden.de/research/reports.html.
10. Borgwardt, S., Thost, V.: Temporal query answering in the description logic EL.
In: Yang, Q. (ed.) Proc. of the 24th Int. Joint Conf. on Artificial Intelligence
(IJCAI’15). AAAI Press (2015), to appear.
11. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data com-
plexity of query answering in description logics. In: Proc. of the 10th Int. Conf.
on Principles of Knowledge Representation and Reasoning (KR’06). pp. 260–270.
AAAI Press (2006)
12. Decker, S., Erdmann, M., Fensel, D., Studer, R.: Ontobroker: Ontology based access
to distributed and semi-structured information. In: Database Semantics: Semantic
Issues in Multimedia Systems. pp. 351–369. Kluwer Academic Publisher (1998)
13. Gutiérrez-Basulto, V., Jung, J.C., Schneider, T.: Lightweight description logics
and branching time: A troublesome marriage. In: Proc. of the 14th Int. Conf.
on Principles of Knowledge Representation and Reasoning (KR’14). AAAI Press
(2014)
14. Lichtenstein, O., Pnueli, A., Zuck, L.: The glory of the past. In: Proc. of the
Workshop on Logics of Programs. pp. 196–218. Springer-Verlag (1985)
15. Lippmann, M.: Temporalised Description Logics for Monitoring Partially Observ-
able Events. Ph.D. thesis, TU Dresden, Germany (2014), http://nbn-resolving.
de/urn:nbn:de:bsz:14-qucosa-147977
16. Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description
logic EL using a relational database system. In: Proc. of the 21st Int. Joint Conf.
on Artificial Intelligence (IJCAI’09). pp. 2070–2075. AAAI Press (2009)
17. Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal description logics: A survey.
In: Proc. of the 15th Int. Symp. on Temporal Representation and Reasoning
(TIME’08). pp. 3–14. IEEE Press (2008)
18. Pnueli, A.: The temporal logic of programs. In: Proc. of the 18th Annual Symp.
on Foundations of Computer Science (SFCS’77). pp. 46–57. IEEE Press (1977)
19. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.:
Linking data to ontologies. Journal of Data Semantics 10, 133–173 (2008)
20. Sistla, A.P., Clarke, E.M.: The complexity of propositional linear temporal logics.
Journal of the ACM 32(3), 733–749 (1985)
21. Wolper, P., Vardi, M.Y., Sistla, A.P.: Reasoning about infinite computation
paths. In: Proc. of the 24th Annual Symp. on Foundations of Computer Science
(SFCS’83). pp. 185–194. IEEE Press (1983)