We propose a framework for querying probabilistic data in the presence of an ontology, arguing that the interplay of probabilities and ontologies is fruitful in applications such as managing data that was extracted from the web. The prime inference problem is computing answer probabilities, and we show that it can be implemented using standard probabilistic database systems, similar to traditional ontologybased data access. We demonstrate that query rewriting into rst-order logic is an important tool for our framework. First, it is used to establish a PTime vs. #P dichotomy for the data complexity of this problem by lifting a corresponding result from probabilistic databases. Then, we use it to characterize which pairs of query and TBox are in PTime. Finally, it is shown that non-existence of such a rewriting implies #P-hardness.
In recent years, ontology based data access (OBDA) has become an active area of
description logic research. In OBDA, an ontology provides a semantics for
incomplete data with the aim of facilitating the computation of more complete answers
to queries. There are applications, though, in which it is necessary to query data
that is not only incomplete, but also uncertain. For instance, data extracted
from web sources [
Framework. We consider probabilistic ABox formalisms that are inspired by
data models from the currently very active area of probabilistic databases [
Contributions. The main aim of this paper is to study the data complexity of
pOBDA. More precisely, we pursue a non-uniform approach as recently initiated
in [
Lifting also allows us to carry over the dichotomy between PTime and
#Phardness for computing the probabilities of answers to unions of conjunctive
queries (UCQs) over probabilistic databases recently obtained by Dalvi, Suciu,
and Schnaitter [
Related Work. The probabilistic ABox formalism studied in this paper is inspired
by the probabilistic database models in [
This paper is a condensed version of [
We use standard notation for the syntax and semantics of description logics
(DLs) and refer to [
As usual, an ABox is a nite set of concept assertions A(a) and role assertions r(a; b). We use Ind(A) to denote the set of individual names used in the ABox A and write r (a; b) 2 A for r(b; a) 2 A. The semantics of DLs is based on interpretations I = ( I ; I ); we adopt the unique name assumption (UNA), i.e., we require aI 6= bI for all individuals a 6= b.
Conjunctive queries (CQs) take the form 9y:'(x; y), with ' a conjunction of atoms of the form A(t) and r(t; t0) and where x; y denote (tuples of) variables and t; t0 denote terms, i.e., a variable or an individual name. We call the variables in x the answer variables and those in y the quanti ed variables. The set of all variables in a CQ q is denoted by var(q) and the set of all terms in q by term(q). A CQ q is n-ary if it has n answer variables and Boolean if it is 0-ary. Whenever convenient, we treat a CQ as a set of atoms and sometimes write r (t; t0) 2 q instead of r(t0; t) 2 q.
Let I be an interpretation and q a CQ with answer variables x1; : : : ; xk. For individual names a = a1 ak, an a-match for q in I is a mapping : term(q) ! I such that (xi) = ai for 1 i k, (a) = aI for all individual names a 2 term(q), (t) 2 AI for all A(t) 2 q, and ( (t1); (t2)) 2 rI for all r(t1; t2) 2 q. We write I j= q[a] if there is an a-match of q in I and let ans(q; I) denote the set of all a with I j= q[a]. For a TBox T and an ABox A, we write T ; A j= q[a] if I j= q[a] for all models I of T and A. The set certT (q; A) of all certain answers consists of all tuples a over Ind(A) with T ; A j= q[a]. 3
We introduce our framework for probabilistic OBDA, starting with the de nition of a rather general, probabilistic version of ABoxes. Let E be a countably in nite set of atomic (probabilistic) events. An event expression is built up from atomic events using the Boolean operators :, ^, _. We use expr(E ) to denote the set of all event expressions over E . A probability assignment for E E is a map E ! [0; 1].
De nition 1 (pABox). A probabilistic ABox (pABox) is of the form (A; e; p) with A an ABox, e a map A ! expr(E ), and p a probability assignment for EA, the atomic events in A.
Example 1. We consider as a running example an information extraction tool
that is gathering data from the web, see [
We now de nte the semantics of OBDA over pABoxes. Each E EA can be viewed as a truth assignment that makes all events in E true and all events in EA n E false.
De nition 2. Let (A; e; p) be a pABox. For each E EA, de ne a corresponding non-probabilistic ABox AE := f 2 A j E j= e( )g: The function p represents a probability distribution on 2EA , by setting for each E EA: p(E) =
Y p(e) e2E
Y e2EAnE (1 p(e)): The probability of an answer a 2 Ind(A)n to an n-ary conjunctive query q over a pABox A and TBox T is For Boolean CQs q, we write p(A; T j= q) instead of pA;T (() 2 q), where () denotes the empty tuple.
Example 2. Consider again the web data extraction example discussed above. To illustrate how ontologies can help to reduce uncertainty, we use the DL-Lite TBox
T = f
v SoccerClub
Player(messi) playsfor(villa; FCbarca) e1
playsfor(messi; FCbarca) e3 playsfor(pedro; FCbarca) e3 e3 with p(e1) = 0:7 and p(e3) = 0:5. Because of the statement 9playsfor v Player, using T (instead of an empty TBox) increases the probability of messi to be an answer to the query Player(x) from 0:7 to 0:85. (5) The resulting pABox is playsfor(villa; FCbarca) e5 playsfor(villa; realmadrid) :e5 with p(e5) = 0:5. Although Player(villa) does not occur in the data, the probability of villa to be an answer to the query Player(x) is 1 (again by the TBoxstatement 9playsfor v Player). (3)+(4) This results in the pABox with p(e3) = 0:5 and p(e4) = p(e04) = p(e040) = 0:8. Due to the last three CIs in T , each of messi, villa, pedro is an answer to the CQ 9y:playsfor(x; y) ^ SoccerClub(y) with probability 0:9.
Related Models in Probabilistic Databases. Nowadays, there is an abundance of
probabilistic data models that provide compact representation of distributions
over potentially large sets of possible worlds, see [
Goalie(messi)
e2
with p(e1) = 0:8 and p(e2) = 0:3 and the TBox Goalie u Striker v ?, then
messi is an answer to the query SoccerClub(x) with probability 0:24 while one
would probably expect it to be zero (which is the result when the empty TBox is
used). We follow Antova, Koch, and Olteanu and advocate a pragmatic solution
based on rescaling [
p(A; T j= ?) p(A; T j= ?) where ? is a Boolean query that is entailed exactly by those ABoxes A that are inconsistent w.r.t. T . The rescaled probability pbA;T (a 2 q) can be computed in PTime when this is the case both for pA;T (a 2 q) and p(A; T j= ?). Note that rescaling results in some e ects that might be unexpected such as reducing the probability of messi to be an answer to Striker(x) from 0:8 to 0:74 when the above TBox is added.
In the remainder of the paper, for simplicity we will only admit TBoxes T such that all ABoxes A are consistent w.r.t. T . 4
The aim of this section is to show that FO-rewriting, a prominent approach
to traditional OBDA, are fruitful also in the case of computing probabilities of
certain answers in probabilistic OBDA. In particular, we use it to lift the PTime
vs. #P dichotomy result on probabilistic databases recently obtained by Dalvi,
Suciu, and Schnaitter [
Lifting FO-Rewritings to probabilistic OBDA A rst-order query qT is an FO-rewriting of a CQ q and an FO-TBox T (i.e., a rst-order theory) if certT (q; A) = ans(qT ; IA) for every ABox A, where IA to denotes the ABox A viewed as an interpretation. The query rewriting approach to traditional OBDA consists of computing, given a CQ q and a TBox T , an FO-rewriting qT and then handing it over for execution to a relational database system that stores the ABox A.
The following observation states that FO-rewritings from traditional OBDA
are also useful in probabilistic OBDA. We use pdA(a 2 q) to denote the
probability that a is an answer to the query q given the pABox A viewed as a
probabilistic database in the sense of Dalvi and Suciu [
X E EA j a2ans(q;IAE ) p(E)
Theorem 1 (Lifting). Let T be an FO-TBox, A a pABox, q an n-ary CQ, a 2 Ind(A)n a candidate answer for q, and qT an FO-rewriting of q relative to T . Then pA;T (a 2 q) = pdA(a 2 qT ).
From an application perspective, Theorem 1 enables the use of probabilistic
database systems such as MayBMS, Trio, and MystiQ for implementing
probabilistic OBDA [
From a theoretical viewpoint, Theorem 1 establishes query rewriting as a
useful tool for analyzing data complexity in probabilistic OBDA. We say that
a CQ q is in PTime relative to a TBox T if there is a polytime algorithm
that, given an ABox A and a candidate answer a 2 Ind(A)n to q, computes
pA;T (a 2 q). We say that q is #P-hard relative to T if the afore mentioned
problem is hard for the counting complexity class #P [
Unsurprisingly, pABoxes are too strong a formalism to admit any tractable queries worth mentioning. An n-ary CQ q is trivial for a TBox T i for every ABox A, we have certT (A; q) = Ind(A)n.
Theorem 2. Over pABoxes, every CQ q is #P -hard relative to every rst-order TBox T for which it is nontrivial.
Theorem 2 motivates the study of more lightweight probabilistic ABox
formalisms. While pABoxes (roughly) correspond to c-tables, which are among
the most expressive probabilistic data models, we now move to the other end
of the spectrum and introduce ipABoxes as a counterpart of tuple independent
databases [
De nition 3 (ipABox). An assertion-independent pABox (or ipABox) is a probabilistic ABox in which all event expressions are atomic and where each atomic event expression is associated with at most one ABox assertion. To save notation, we write ipABoxes in the form (A; p) where A is an ABox and p is a map A ! [0; 1] that assigns a probability to each ABox assertion. In this representation, the events are implicit (one atomic event per ABox assertion) and we write p( ) to denote the probability of the event associated with the assertion . Analogously to pABoxes, all events (and thus all assertions) are independent. Note that the answer probability of a 2 Ind(A)n to an n-ary conjunctive query q over an ipABox (A; p) relative to a TBox T simpli es to
X
We now use Theorem 1 to lift a PTime vs. #P dichotomy recently obtained in
the area of probabilistic databases to probabilistic OBDA in DL-Lite. Note that,
for any CQ and DL-Lite TBox, an FO-rewriting is guaranteed to exist [
For two CQs q; q0 and a TBox T , we say that q T -implies q0 and write q vT q0
when certT (q; A) certT (q0; A) for all ABoxes A; we say that q and q0 are T
equivalent and write q T q0 if q vT q0 and q0 vT q; we say that q is T -minimal
if there is no q0 ( q such that q T q0. When T is empty, we simply drop it from
the introduced notation, writing for example q v q0 and speaking of minimality.
To have more control over the e ect of the TBox, we will generally work with
CQs q and TBoxes T such that q is T -minimal. This is without loss of generality
because for every CQ q and TBox T , we can nd a CQ q0 that is T -minimal
and such that q T q0 [
We now introduce a class of queries that will play a crucial role in our analysis. De nition 4 (Simple Tree Queries). A CQ q is a simple tree if there is a variable xr 2 var(q) that occurs in every atom in q, i.e., all atoms in q are of the form A(xr), r(xr; y), or r(y; xr) (y = xr is possible). Such a variable xr is called a root variable.
As examples, consider the CQs in Figure 1, which are all simple tree queries. The following result shows why simple tree queries are important. A UCQ qb is reduced if for all disjuncts q; q0 of qb, q v q0 implies q = q0. Theorem 4. Let q be a CQ and T a DL-Lite TBox such that q is T -minimal and not a simple tree query. Then q is #P-hard relative to T .
Proof. (sketch) Let qT be a UCQ that is an FO-rewriting of q relative to T . By
de nition of FO-rewritings, we can w.l.o.g. assume that q occurs as a disjunct
of qT . The following is shown in [
To nish anlyzing the dichotomy, it thus remains to analyze simple tree
queries. We say that a role R is T -generated in a CQ q if one of the following
holds: (i) there is an atom R(xr; y) 2 q and y 6= xr; (ii) there is an atom
A(xr) 2 q and T j= 9R v A; (iii) there is an atom S(x; y) 2 q with x a root
variable and such that y 6= x occurs only in this atom, and T j= 9R v 9S. The
concrete version of our dichotomy result is as follows. Its proof is based on a
careful analysis of FO-rewritings and the results in [
Theorem 5 (Concrete Dichotomy). Let T be a DL-Lite TBox. A T -minimal CQ q is in PTime relative to T i 1. q is a simple tree query, and 2. if r and r are T -generated in q, then fr(x; y)g vT q or q is of the form fS1(x; y); : : : ; Sk(x; y)g for roles S1; : : : ; Sk.
Otherwise, q is #P-hard relative to T .
As examples, consider again the queries q1, q2, and q3 in Figure 1 and let T; be the empty TBox. All CQs are T;-minimal, q1 and q2 are in PTime, and q3 is #P-hard (all relative to T;). Now consider the TBox T = f9s v 9 g r . Then q1 is T -minimal and still in PTime; q2 is T -minimal, and is now #P-hard because both s and s is T -generated. The CQ q3 can be made T -minimal by dropping the r-atom, and is in PTime relative to T .
Approximations. Theorems 4 and 5 show that only very simple pairs (q; T ) can
be answered in PTime. Hence, it is reasonable to consider the approximation
of answer probabilities. Of particular relevance are fully-polynomial randomized
approximation schemes (FPRASes), see [
A CQ q is FO-rewritable relative to a TBox T if there is an FO-rewriting of q relative to T . The aim of this section is to establish that, in a sense, FO-rewriting is a complete tool for proving PTime results for CQ answering in probabilistic OBDA: we show that whenever a CQ q is not FO-rewritable relative to a TBox T , then q is #P-hard relative to T ; thus, when a query is in PTime relative to a TBox T , then this can always be shown via FO-rewritability. To achieve this goal, we select E LI as the TBox language because it properly generalizes DL-Lite (as in the previous sections we disregard ?) and, unlike DL-Lite, also embraces non FO-rewritable CQs/TBoxes. Note that, in traditional OBDA, there is a drastic di erence in data complexity of CQ-answering between DL-Lite and E LI: the former is in AC0 while the latter is PTime-complete.
We focus on Boolean CQs q that are rooted, i.e., q involves at least one individual name and is connected. This is a natural case since, for any nonBoolean connected CQ q(x) and potential answer a, the probability pA;T (a 2 q(x)) that a is a certain answer to q w.r.t. A and T is identical to the probability p(A; T j= q[a]) that A and T entail the rooted Boolean CQ q[a]. The following theorem says that there is no hope for PTime algorithms in the case a query q is not FO-rewritable relative to T .
Theorem 6. If a Boolean rooted CQ q is not FO-rewritable relative to an E LITBox T , then q is #P-hard relative to T .
As a by-product of Theorem 6 we obtain the following dichotomy. Theorem 7 (E LI dichotomy). Let q be a rooted Boolean CQ and T an E LITBox. Then q is in PTime relative to T or #P-hard relative to T . 6
We have introduced a framework for ontology-based access to probabilistic data
that can be implemented using existing probabilistic database system, and we
have analyzed the data complexity of computing answer probabilities in this
framework. There are various opportunities for future work. For example, it
would be interesting to extend the concrete dichotomy: on the one hand, it can
be extended to CQs that involve constants and are not necessarily connected;
on the other hand, one could study more expressive versions of DL-Lite that, for
example, allow role hierarchy statements in the TBox. It would also be
worthwhile to add means to express uncertainty to the TBox formalism instead of
admitting it only in the ABox; this is done for example in [