We present some initial results on ontology-based query answering with description logic ontologies that may employ temporal and probabilistic operators on concepts and axioms. Speci cally, we consider description logics extended with operators from linear temporal logic (LTL), as well as subjective probability operators, and an extended query language in which conjunctive queries can be combined using these operators. We rst show some complexity results for the setting in which either only temporal operators or only probabilistic operators may be used, both in the ontology and in the query, and then show a 2ExpSpace lower bound for the setting in which both types of operators can be used together.
Ontology-Based Query Answering (OBQA) received considerable attention in
the past, as it allows to query incomplete data in the presence of an ontology
providing background knowledge about the data domain. While classically, OBQA
considers a setting where the data is both static and certain, there are many
applications where this assumption does not hold, which lead to the development
of temporal query languages for OBQA [
10 P<0:2Excercising(x)U P>0:7HighBloodPressure(x) : While the mentioned works allow for an extended expressivity in the query language, they only consider ontologies that are formulated using a classical (atemporal and non-probabilistic) DL. Since the role of the ontology in OBQA is to provide additional background knowledge, temporal and/or probabilistic OBQA would bene t from ontology languages that provide both temporal and probabilistic language constructs. To stay with the current example, this could for instance be used to express that if a patient starts exercising, his blood pressure is likely to remain increased until the patient takes a break:
StartsExcercising v (P>0:7IncreasedBloodPressure) U StopsExcercising; where StartsExcercising and StopsExcercising are de ned in further axioms using temporal concept operators.
Temporal DLs have been well investigated in the literature, and may extend
classical DLs with LTL-operators on axioms and concepts [
The aim of this paper is to theoretically investigate a setting where
temporal operators, as well as operators expressing subjective probability, can be
used both as part of the ontology language and as part of the query language.
While some complexity bounds are still open at this point, we present initial
results towards understanding the complexity in such a setting. Speci cally, our
contributions are the following.
1. In Section 2, we combine the languages studied in [
Details of proofs and de nitions can be found in the extended version of the
paper [
We assume basic knowledge about expressive DLs. Our results concern DLs
ranging from ALC to ALCOQ and ALCOI. Details about the DLs relevant for
this paper, as well as on query answering, can be found in the extended version
of the paper. We assume DL concepts to be composed using the operators of the
respective DL based on the pair-wise disjoint, countably in nite sets NC, NR and
NI of respectively concept names, role names and individual names. We assume
DL axioms to be either general class inclusions (GCIs) of the form C v D,
or assertions of the forms C(a), r(a; b) with C and D being concepts in the
respective DL, r, s role names, and a, b individual names. We use C D as
abbreviation for the two GCIs C v D and D v C. Satis ability of sets K of
axioms is de ned in terms of interpretations I = h I ; I i, where I is a set
of domain elements and I is a function mapping individual names to domain
elements, concepts to subsets of I and roles to subsets of I I . Conjunctive
queries (CQs) and entailment of Boolean CQs are de ned as usual (eg., see [
To distinguish between di erent intervals relevant in this paper, we use the notation [i; j] to denote closed intervals over the reals, and the notation Ji; jK to denote closed intervals over the integers. A probability measure over a (possibly in nite) set W is a function P : W ! [0; 1], where W 2W is a -algebra (it contains W is is closed under complement and countable union), s.t. P (;) = 0, P (W ) = 1, and for any countable set W0 W of pairwise disjoint sets W 0 W , we have P (SW 02W W 0) = PW 02W P (W 0). 2.2
We consider extensions of classical DLs which additionally allow temporal concepts of the form C (next) and CUD (until), and probabilistic concepts of the form P~pC, where ~ 2 f<; =; >g, p 2 [0; 1] and C, D are concepts. These concepts may be used at any place within a concept, and we call the resulting concepts temporal probabilistic concepts. Here, we do not x a particular DL as basis, but may refer to the underlying DL which is extended by these operators. While classically, a DL knowledge base is build using DL axioms, against which queries are evaluated, it will be convenient to study queries and DL axioms not in separation, but to allow for an integrated language in which DL axioms and CQs can be arbitrarily mixed within a formula. This further expressivity can for instance be used to specify that a certain DL axiom holds until a Boolean CQ becomes satis ed. For this reason, we collectively call DL axioms and CQs generalised axioms. Temporal probabilistic DL formulae (TPDFs) are then built according to the following syntax rule, where X is a generalised axiom that may use temporal probabilistic concepts, ~ 2 f<; =; >g and p 2 [0; 1]: ::= X j : j ^ j j U j P~p :
The operators :, ^, and U are called temporal operators, while the operators P~p are called probability operators. We de ne further operators as the usual abbreviations, that is, for TPDFs and , we denote true := _ : (for some ), _ := :(: ^ : ), := trueU and := : : , ! := : _ and $ := ( ! ) ^ ( ! ), and similar for concepts. A TPDF is called Boolean if every CQ in it is Boolean.
As typical for temporal reasoning with DLs, we assume a set Nrig NC [ NR of rigid names, composed of a set NCrig = Nrig \ NC of rigid concepts and a set NRrig = Nrig \ NR of rigid roles, which denote concept and role names whose interpretation does not change over time. 2.3
To de ne the semantics of TPDFs, we have to take into consideration two dimensions: the temporal dimension and the probabilistic dimension. A temporal interpretation is a sequence (Ii)i 0 of interpretations Ii = h ; Ii i sharing the same domain J , such that for any rigid name X 2 Nrig and i; j 0, XIi = XIj . A probabilistic temporal interpretation is then a probability measure : J ! [0; 1], over a set J of temporal interpretations (Ii)i 0 sharing the same set of domain elements (J 2J is then a sigma algebra). We call J the possible worlds of .
To de ne the semantics of temporal and probabilistic operators, we de ne the function Ii; on concepts, where (Ij )j 0 2 J and i 0. Ii; is de ned as Ii for the concept operators of the underlying DL, and for the remaining operators by (
C)Ii; = CIi+1; (CUD)Ii; = fd 2 (P~pC)Ii; = fd 2 j 9j i : d 2 DIi; ; 8k 2 Ji; j 1K : d 2 CIk; g j (f(Ij0 )j 0 2 J j d 2 CIi0; g) ~ pg: Satisfaction of Boolean TPDFs is de ned by: 1. Ii; j= i Ii j= , where 2. Ii; j= C v D i CIi; 3. Ii; j= C(a) i aIi 2 CIi; , 4. Ii; j= i Ii+1; j= , 5. Ii; j= U i there exists j
Ik; j= , and 6. Ii; j= P~p i
is a Boolean CQ or a role assertion, DIi; , i s.t. Ij ; j= and for all k 2 Jj; i 1K, (f(Ij0 )j 0 2 J j Ii0; j= g) ~ p.1
We say that satis es a Boolean TPDF , in symbols j= , if for all (Ii)i 0 2 J , I0; j= , in which case is a model of . A Boolean TPDF is satis able i it has a model.
The paper focusses on showing complexity bounds for Boolean TPDF satis
ability. Note that other reasoning tasks that are more related to classical OBQA
can be easily reduced to TPDF satis ability. For instance, for the problem of
temporal probabilistic query answering, we are given a Boolean TPDF , and a
non-Boolean TPDF that contains only CQs and no DL axioms (a temporal
probabilistic query), and we want to nd an assignment of individual names to
the answer variables in so that the resulting TPDF is logically entailed by .
This problem can be reduced to deciding the unsatis ability of Boolean TPDFs
of the form ^ : 0, where 0 is obtained from by replacing answer variables
by individual names. As from now on, we focus on Boolean TPDFs only, we will
omit the \Boolean" and just call them TPDFs in the following.
Remark. There is a subtle di erence between our semantics and that of
ProbALC/Prob-E L as introduced in [
We rst consider the purely temporal case of TPDFs without probability
operators. This problem has so far only been studied for temporal queries and
temporal DLs, but not for the combination of both. Our rst result concerns
TPDFs without temporal concepts, that is, temporal operators can be used on
CQs and on axioms, but not within concepts. Here, complexity upper bounds
1 Note that we implicitly require that J contains all subsets of 2J relevant to these
de nitions.
directly follow from the complexity of temporal query entailment with classical
ontologies, as studied in [
Theorem 1. Satis ability of TPDFs without probability operators and temporal concepts, and with underlying DL L, is { PSpace-complete for L = E L and NCrig = NRrig = ;, { ExpTime-complete for L 2 fALC; ALCQg and NCrig = NRrig = ;, { NExpTime-complete for L 2 fE L; ALC; ALCQg and NRrig = ;, { NExpTime-complete L = E L and NRrig 6= ;, { 2ExpTime-complete for L 2 fALCI; ALCIQ; ALCOQ; ALCOIg, and { decidable for ALCOIQ.
If we also allow for temporal concept operators, we have to do a bit more. We
rst note that with rigid roles, using temporal operators on the level of concepts
leads to undecidability already if the underlying DL is E L [
Given a TPDF , let con( ) denote the set of (sub-)concepts occurring in , form( ) denote the set of sub-formulae of , and ind( ) denote the set of individual names occurring in . Furthermore, de ne tc( ) = fC; :C j C 2 con( )g [ ffag j a 2 ind( )g and tf ( ) = f ; : j 2 form( )g. A concept type is then a subset t tc( ) s.t.
C1 for every :C 2 tc( ), :C 2 t i C 62 t, and C2 for every C u D 2 tc( ), C u D 2 t i C; D 2 t.
If a concept type t contains a concept of the form fag, we call t a nominal type. A formula type is a subset t tf ( ) s.t.
F2 for every
2 tc( ), : 2 t i 62 t, and 1 ^ 2 2 tc( ), 1 ^ 2 2 t i 1; 2 2 t.
A quasistate is a set S of formula and concept types s.t. S contains exactly one formula type tS .
If the formula type only contains GCIs and their negation, there are easy syntactic conditions for when a quasistate can correspond to an element of a temporal interpretation. This becomes however more di cult when it can also contain CQs, which is why we instead formulate a semantic admissibility condition for quasistates. We rst introduce the notion of a conceptual abstraction. Since quasistates will also be used in Section 4, we de ne them here more general for quasistates that may also contain probability operators. Given a concept or TPDF X, its conceptual abstraction Xca is obtained by replacing every outermost concept C of the forms D, D1UD2, and P~pD by the fresh concept name AC , and every outermost TPDF of the forms 1, 1U 2 and P~p 1 by A (a), where A is fresh. A quasistate S is then admissible i there exists a (classical) interpretation I s.t.
S1 for every TPDF 2 form( ), I j= ca i 2 tS , and S2 for every concept type t tc( ), TC2t(Cca)I 6= ; i t 2 S.
While a quasistate can contain up to exponentially many concept types, we can show that for ALCOQ and ALCOI, it can still be decided in 2ExpTime wrt. to the input formula whether a given quasistate is admissible, while this can be done in ExpTime for ALCQ.
It remains to represent the temporal dimension, which we do in terms of runs and temporal quasimodels.
A concept/formula run is a sequence : N ! tc( )/tf ( ) of concept/formula types s.t. for all i 0, R1 for every 2 tc( )=tf ( ), R2 for every U 2 tc( )=tf ( ), U
and for all k 2 Ji; j 1K, 2 (i), R3 for every j 2 N, (i) \ NCrig = (j) \ NCrig, and R4 for every j 2 N and a 2 NI, fag 2 (i) i fag 2 2 (i) i 2 (i + 1), 2 (i) i there exists j (j).
A temporal quasimodel for is a tuple hQ; Ri, where Q is a sequence mapping each natural number to an admissible quasistate Q(i), and R is a set of runs s.t. i s.t.
2 (i) Q1 2 tQ(0), Q2 for each i Q3 for each run 0 and t 2 Q(i) , there exists a run 2 R, and i 0, (i) 2 Q(i).
2 R s.t. (i) = t, and
Temporal quasimodels witness the satis ability of TPDFs without
probability operators. Furthermore, we can use a regularity argument as in [
Q(0) : : : Q(n) Q(n + 1) : : : Q(n + m) !; with n and m double exponentially bounded in the size of . is satis able i
The proof of the lemma makes use of the fact that, in a classical DL
interpretation, if the underlying DL is ALCOQ or ALCOI, we can arbitrarily extend
the set of domain elements that belong to a given concept type without a ecting
entailment of CQs or the extension of other types. This is not so easily possible
for DLs that support both inverse roles and counting quanti ers, which is why
we do not have results for ALCIQ. Using lower bounds for CQ entailment in
ALCI [
We next consider the purely probabilistic case, that is, we allow probability
operators on the level of concepts, axioms and queries, but no temporal operators.
While [
Our method for deciding entailment of those TPDFs is again based on quasistates and types, over which we this time de ne probability measures.
A probabilistic quasistate is a probability measure P S : 2S ! [0; 1] over a set S of quasistates. It is admissible i for every quasistate S 2 S: PS1 S is admissible, and PS2 for every P~p 2 tf ( ), P~ 2 tS i P S(fS 2 S j 2 tS g) ~ p.
While every quasistate contains a set of concept types, we might need a more ne-grained probability measure for each concept type to verify the probabilistic concepts in them. For this, we de ne probabilistic concept types. A probabilistic concept type pt : 2T ! [0; 1] is a probability measure over a set T of concept types s.t PT for every P~pC 2 tc( ) and t 2 T , P~pC 2 t i pt(ft 2 T j C 2 tg) ~ p. It is compatible to a probabilistic quasistate P S : 2S ! [0; 1] i there exists a probability measure PP S;pt : 2WP S;pt ! [0; 1] over some set WP S;pt S T s.t.
We call PP S;pt a joined probability measure for P S and pt. A probabilistic quasimodel for is now a tuple hP S; PTi of a probabilistic quasistate P S : 2S ! [0; 1] and a set PT of probabilistic concept types s.t.
Note that in Condition PQ3, we only require hS; ti 2 WP S;pt, but not PP S;pt(fhS; tig) > 0. This is still su cient to ensure that the type t can be instantiated in every possible world corresponding to S, and in fact necessary to ensure completeness, because we allow for uncountable sets of possible worlds in our semantics.
Lemma 2. A TPDF without temporal operators, with underlying DL ALCOQ or ALCOI, is satis able i there exists a probabilistic quasimodel hP T; PTi for .
Probabilistic quasimodels are similar to temporal quasimodels, where instead of sequences, we use probability measures. For some DLs, this di erence in structure can be exploited to gain better complexity bounds. While there can be in general double exponentially many quasistates and probabilistic concept types, if the underlying DL is ALCQ, only exponentially many of each are needed. In contrast to the temporal quasimodels in Section 3, which indeed may always require a double exponential number of quasistates, probabilistic quasimodels bene t from a lack of order : this allows us to merge quasistates that agree on their formula type and nominal types, which is the reason why we can bound the size of probabilistic quasimodels for ALCQ.
Our decision procedure for TPDF satis ability consists of guessing and
verifying a probabilistic quasimodel of the appropriate size. Here, we make use of a
result from [
Since satis ability of Prob-ALC is still in ExpTime [
If we allow both temporal and probability operators, satis ability of TPDFs
becomes 2ExpSpace-hard, even if we disallow rigid names. We show this by
a reduction of the double-exponential corridor tiling problem. This problem is
formalised as follows. We are given a set T of tiles containing an initial tile type
t0 2 T and a nal tile type tf 2 T , two sets H T T and V T T
of respectively horizontal and vertical tiling conditions, and a natural number
n. The problem is then to decide whether there exists a natural number m
iian22dJJ1a1;;2t2i22lninnKgant1dK: jaJ1n2;d2J21jn; 2Km J1J1;1Km;, mKw,eKwh!eavhTeavhtse(.tih.;tj(t)i(;;1jt;()1i;;)tj(=i++1t)01i,; 2jt()1Vi; 2.mIt)Hf=o,lalotnfwd,sfffoorrro meevvteehrryye
relationship between corridor-tilings and space-bounded Turing machines shown
in [
While the full reduction is shown in the extended version of the paper, we sketch the main ideas here. We use 22n domain elements to represent the vertical dimension of the tiling, and the time line to represent the horizontal dimension. The probabilistic dimension is used to implement a double exponential counter on each domain element, which is used to identify which row of the tiling it represents. Here, we use temporal and probabilistic concepts to force the existence of exponentially many possible worlds per domain element, which at each time point store the di erent bit values of the double exponential counter using a
)sn 0 1 2 3 0 1 2 3 0 1 2 3 0 1 lsrd iitso 1 2 3 0 1 2 3 0 1 2 3 0 1 2 o o 2 3 0 1 2 3 0 1 2 3 0 1 2 3 w tp ib 3 0 1 2 3 0 1 2 3 0 1 2 3 0 ( time concept Bit. Speci cally, the individual satis es Bit in the ith possible world i the ith bit of the double exponential counter has the value 1.
A main challenge in the construction is the lack of order in temporal probabilistic models. The set of possible worlds in an interpretation is unordered, which means we cannot directly refer to the \ith" or \next" possible world. This is however neccessary to implement a double exponential counter, since we have to transfer information about carrier bits from one possible world to another. Furthermore, since we do not allow rigid roles, we cannot keep the relationship between the di erent domain elements stable throughout the time line. As a result, we cannot directly refer to the domain element that refers to the next row in order to test the vertical tiling conditions. For both challenges, we use a similar trick.
For the double-exponential counter, we need to be able to identify possible worlds for the respective domain element that correspond to neighbouring bit positions. To do this, we implement a single-exponential counter in each possible world, which is incremented along the time line, so that in each world, the counter has a di erent value. This is visualised in Figure 1. To implement these counters, we use concept names A1, : : :, An representing the bit value at the positions 1 to n of this counter. At each time point, two neighbouring possible worlds can be identi ed easily: the one with a counter value of 2n 1 satis es d unless it corresponds to the last bit position, the next bit positioin2Jc1o;nrrKeAs pi,oanndds to the world with a counter value of 0, which satis es d :Ai. Using this mechanism, we can for instance transfer the information oin2Jw1;hnKether the current bit has to be ipped using the following GCIs: l
Ai u Flip u Bit v P=1(( l :Ai) ! Flip) ( l i2J1;nK i2J1;nK
i2J1;nK Ai) u (:Flip t :Bit) v P=1(( l i2J1;nK :Ai) ! (FirstBit t :Flip)): Using further axioms, this allows us to implement a double exponential counter on each domain element, which is incremented every 2n time points.
The same technique is used on a di erent level to identify which domain elements correspond to neighbouring rows in the ceiling. We make sure that eventually, we have at each time point a di erent double exponential counter value represented by some domain element. At each time point, we can then identify two neighbouring domain elements easily: the one with a counter value of 0 satis es P=1:Bit, and the one with a counter value of 22n 1 satis es P=1Bit. We can thus test the vertical tiling conditions with the following axiom: ^ t2T :(t u P=1Bit v ?) !
(P=1:Bit v t0) : _ ht;t0i2V
The reduction allows us to establish the following theorem.
Theorem 4. Satis ability of TPDFs is 2ExpSpace-hard. This already holds if { no CQs are used, { the underlying DL is ALC, { probabilistic operators are only used on the level of concepts, { NCrig = NRrig = ;, and { on the axiom level, we only use Boolean connectives and the operator which does not occur under a negation operator.
In the context of description logics, temporal and probabilistic extensions have mostly been investigated in isolation, and similarly, such extensions on DL languages and query languages have not been investigated in combination. In this paper, we presented several results towards lling these gaps. First, we showed tight complexity bounds for a setting where temporal operators are used on the level of axioms and queries, as well as on queries, axioms and concepts in combination, showing that the overall complexity does not increase by such a combination for any DL between ALC and ALCOQ or ALCOI. Second, we considered the setting where probability operators may be used on the level of concepts, axioms and queries, obtaining an NExpTime upper bound if the underlying DL is ALCQ, and an N2ExpTime upper bound if the underlying DL is ALCOQ or ALCOI. Finally, we showed that the combination of both temporal and probabilistic operators on concepts and axioms results in 2ExpSpace-hardness. We believe that it might be possible to obtain matching upper bounds by a combination of the structures we used in this paper to show our upper bound.
While temporal ABoxes can be easily encoded into TPDFs, our results do
not generalise the settings with probabilistic ABoxes studied in [