The Bayesian Description Logic (BDL) BEL is a probabilistic DL, which extends the lightweight DL EL by de ning a joint probability distribution over EL axioms with the help of a Bayesian network (BN). In the recent work, extensions of standard logical reasoning tasks in BEL are shown to be reducible to inferences in BNs. This work concentrates on a more general reasoning task, namely on conjunctive query answering in BEL where every query is associated to a probability leading to di erent reasoning problems. In particular, we study the probabilistic query entailment, top-k answers, and top-k contexts as reasoning problems. Our complexity analysis suggests that all of these problems are tractable under certain assumptions.
Description Logics (DLs) [
The fact that classical DLs had severe limitations in representing and
reasoning under uncertainty led to a body of work [
BDLs [
The focus of this work is the DL BEL [
Nevertheless, problems related to query answering, and in particular conjunctive query (CQ) answering, has not been studied in the context of BDLs, so far. In this paper, we close this gap and focus on i) probabilistic query entailment: \What is the probability of a query to be entailed?" ii) probabilistic query answering: \What are the top-k answers to a query?" and nally iii) the most likely context: \What are the top-k contexts that entail a query?"
Consequently, we argue that these problems generalize the reasoning problems that have been considered so far. Unsurprisingly, reasoning in BEL is intractible as is CQ answering in EL and inference in BNs. Further analysis shows that tractability can be regained by xing the BN and the query. 2
We brie y review the DL EL [
The semantics of EL is given by an interpretation: that is a tuple I = ( I ; I ) where I is a non-empty domain and I is an interpretation function that maps every individual name a to an element aI 2 I ; every concept name A to a set AI I and every role name r to a binary relation rI I I . The interpretation function I is extended to EL concepts as shown in the upper part of Table 1.
The domain knowledge is encoded through a set of axioms, which restrict the interpretation domain of the concepts. A TBox T is a nite set of general concept inclusions (GCIs) of the form C v D, where C, D are concepts. An ABox is a nite set of concept assertions C(a) and role assertions r(a; b), where a; b 2 NI, C is a concept and r 2 NR. A knowledge base is a pair K = (T ; A) where T is a TBox and A is an ABox. We use the term axiom as a general expression for GCIs and assertions.
The interpretation I satis es an axiom i it satis es the conditions on the lower part of Table 1. It is a model of the TBox T if it satis es all GCIs in T and a model of the ABox A if it satis es all the assertions in A. An interpretation is a model of the KB K = (T ; A) i it is a model of both T and A. For the rest of this paper we will denote as NI(A) the set of all individual names that appear in the ABox A.
CQA is an important reasoning task for DLs that has been investigated in the context of EL. Let NV be a set of variables disjoint from NC, NR, and NI. An atom is an expression of the form A( ) or r( ; ), where A 2 NC, r 2 NR, and ; 2 NI [ NV. A conjunctive query (CQ) q is a non-empty set of atoms associated to a set DV(q) NV of distinguished variables. If DV(q) = ;, then q is called a Boolean CQ. A special case of a CQ is an instance query (IQ), which consists of only one atom A( ) with A 2 NC.
Let q be a Boolean CQ and IV(q) be the set of all individual names and variables appearing in q. The interpretation I satis es q if there exists a function : IV(q) ! I such that (i) (a) = aI for all a 2 NI\IV(q), (ii) ( ) 2 AI for all A( ) 2 q, and (iii) ( ( ); ( )) 2 rI for all r( ; ) 2 q. In this case, we call a match for I and q. The ontology O entails q (O j= q) i every model of O satis es q. For an arbitrary CQ q, a function a : DV(q) ! NI(A) is an answer to q w.r.t. O i O entails the Boolean CQ a(q) obtained by replacing every distinguished variable 2 DV(q) with a( ). Conjunctive query answering (CQA) is the task of nding all answers of a CQ, and query entailment is the problem of deciding whether an ontology entails a given Boolean CQ by replacing every distinguished variable 2 DV(q) with a( ).
It is well known that query entailment in EL is polynomial w.r.t. data and
KB complexity, but NP-complete w.r.t. combined complexity [
The Bayesian DL BEL [
BNs are widely studied probabilistic graphical models where the underlying graph G = (V; E) encodes a series of conditional independence assumptions between the random variables. Every variable x 2 V is known to be conditionally independent of its non-descendants given its parents. Thus, every BN B de nes a unique joint probability distribution (JPD) over V given by
PB(V ) = Y PB(x j (x)):
x2V
The concept language of BEL is the same as the EL concept language. The di erence appears in encoding the domain knowledge, i.e. in forming axioms. BEL generalizes classical TBoxes (resp. ABoxes) by annotating the GCIs (resp. assertions) with a context de ned by a set of literals belonging to a BN.
Formally, let NI be a set of individual names and V a nite set of boolean variables. A V -context is a conjunction of literals over V . A V -restricted general concept inclusion (V -GCI) is an expression of the form hC v D : i where C, D are BEL concepts and is a V -context. A V -restricted assertion (V -assertion) is an expression of the form hC(a) : i, or hr(a; b) : i where a; b 2 NI, C, D are BEL concepts and is a V -context. A V -TBox (resp.V -ABox) is a nite set of V -GCIs (resp.V -assertions). A BEL knowledge base (KB) is a tuple K = (B; T ; A) where B is a BN over V , T is a V -TBox and A is a V -ABox.
We will sometimes speak of contextual axioms to address both V -GCIs and V -assertions. The intuition behind the contextual axioms is to enforce an axiom to hold within a given context, but not necessarily in others. The semantic of such axioms is realized with the so-called contextual interpretations, which di erently from the classical interpretations also evaluate the context variables. Formally, given a nite set of Boolean variables V , (I; VI ) is a contextual interpretation where VI is a propositional interpretation over V , and I = ( I ; I ) is a classical EL interpretation. We will usually ignore the pre x and speak simply of e.g. a KB, a TBox, an ABox, or an interpretation.
The interpretation function I is extended to arbitrary BEL concepts as in EL, i.e. using the rules in Table 1. We say that the contextual interpretation (I; VI ) is a model of an axiom h : i denoted as (I; VI ) j= h : i, i either (i) VI 6j= , or (ii) I j= . It is a model of the TBox T (resp. ABox A) i it is a model of all the axioms in T (resp. A).
A contextual interpretation (I; VI ) needs to satisfy only the axioms asserted within a context for which it holds that VI j= . Formally, let K = (B; T ; A) be a BEL KB: Given a contextual interpretation (I; VI ) where VI = W, we de ne the EL KB KW = (TW ; AW ) that needs to be satis ed by I as: TW := fC v D j hC v D : 'i 2 T ; W j= 'g;
AW := fC(a) j hC(a) : 'i 2 A; W j= 'g [ fr(a; b) j hr(a; b) : 'i 2 A; W j= 'g: In BEL, uncertainty is represented through a BN that describes a joint probability distribution over the context variables. Semantically, BEL is linked to this distribution with the so called multiple world semantics : A probabilistic interpretation de nes a probability distribution over a set of (contextual) interpretations; this distribution is required to be consistent with the joint probability distribution provided by the BN. Formally, a probabilistic interpretation is a pair P = (I; PI), where I is a set of contextual interpretations and PI is a probability distribution over I such that PI(I; VI ) > 0 only for nitely many interpretations (I; VI ) 2 I. P is a model of the TBox T (resp. ABox A) if every (I; VI ) 2 I is a model of T (resp. A). P is consistent with the BN B if for every possible valuation W of the variables in V it holds that
X PI(I; VI ) = PB(W): (I;VI)2I; VI=W The probabilistic interpretation P is a model of the KB (B; T ; A) i it is a (probabilistic) model of T , A and consistent with B.
To provide a ne-grained analysis of the complexity of reasoning in BEL, we use di erent measures for the size of the input. In data complexity, we measure only the size of the ABox, and consider the rest of the KB and the query xed. For ontology complexity we use the size of the TBox and the ABox; in network complexity the relevant input is the BN, while the combined complexity considers the size of the whole input. 4
Di erent reasoning tasks have been studied in the context of Bayesian DLs;
perhaps the most prominent one being the probabilistic entailment [
Here we generalize these results and study probabilistic query entailment. In this setting, we are not just interested in the entailment of a query q but also in the probability of such entailment.
De nition 1 (probabilistic query entailment). Let K = (B; T ; A) be a BEL KB over V and P = (I; P ) a probabilistic interpretation. P de nes a probability distribution PP over all conjunctive queries q given by
PP (q) :=
X (I;VI)2I; Ij=q
P (I; VI ): The probability of the query q w.r.t. K is PK(q) := infPj=K PP (q): A query q is entailed with probability p 2 (0; 1] i PK(q) p.
Recall that every valuation W de nes an EL ontology that contains all the axioms that must be satis ed by any contextual interpretation using the valuation W. Given a Boolean CQ q, we can build a probabilistic model Pq = (I; P ) of K such that for every valuation W there is exactly one contextual interpretation IW 2 I, and it satis es that IW j= q i KW j= q. It is easy to see that every other model P of K is such that PP (q) PPq (q), which yields the following theorem.
x :x y 0:7 z x y x :y :x y :x :y z Given Theorem 2, one can compute the probability of any query by summing up the probabilities of the worlds that entail the query q. We illustrate probabilistic query entailment with a simple example.
Example 3. Consider the BEL KB K = ((TABC; AABC); BABC) where TABC := f hA v 9r:B : fygi ; hB v C : fxgig
AABC := f hA(a) : fxgi ; hr(a; b) : fzgi ; hC(b) : fx; zgi ; hA(c) : fygig BABC is the BN given in Figure 1 and the Boolean CQ q = fA( ); r( ; ); C( )g. Clearly, KW j= q only for worlds W such that W j= (x ^ y) _ (x ^ z). Hence, we get PK(q) = PBABC ((x ^ y) _ (x ^ z)) = 0:411.
Clearly the number of worlds might be exponential in jV j. In fact, this corresponds to exponentially many query entailment tests, which can be performed using polynomial space only.
Theorem 4. Probabilistic query entailment is polynomial w.r.t. data and ontology complexity; and in PSpace w.r.t. network and combined complexity.
The bounds for network and combined complexity can be improved if we
restrict the queries to instance queries only. It is then possible to use a novel
structure, called the proof structure such as the one presented in [
In a nutshell, a proof structure is a directed acyclic hyper-graph, in which
every node represents an axiom. It is constructed in a bottom up manner with
the help of a set of deduction rules. Starting from an initial set of axioms given
by the KB, it adds new nodes for the axioms resulting from 1-step application
of the deduction rules. Edges are used for denoting the axioms that have been
used for the deduction. This process continues until the rules are saturated under
the set of axioms. This structure enables us to trace back all the causes for a
consequence. Thus, once transformed into a BN, it represents all contexts for a
consequence, the probability of which can then be computed via the BN. For
the details, we refer to [
To provide a better complexity bound for probabilistic query entailment, we extend the proof structure to also handle the assertional knowledge, which was not present so far. Following a nave approach it is possible to introduce a new set of deduction rules; instead, we make use of nominals to handle the assertions.
Brie y, the DL ELO extends EL with nominals; that is, it allows special types
of concepts of the form fag with the semantics faI g. It is well-known that in the
presence of nominals, EL KBs can be represented without an ABox. Thus, for
an ELO KB it is possible to bene t from the deduction rules presented in [
A BEL KB can be transformed into a BELO KB in the obvious way. Let K = fB; T ; Ag be a BEL KB, we construct the BELO KB K0 = fB; T 0g where T 0 = T [ f hfag v C : i j hC(a) : i 2 A g
[ f hfag v 9:rfbg : i j hr(a; b) : i 2 A g:
Clearly, K j= c i K0 j= c for any consequence c. Hence, for any ABox assertion, it is possible to construct a proof structure of polynomial size. To check the probability of an instance query C( ) we construct a BN using the proof structures of C(a) where a is an individual appearing in the ABox. Observe that the number of proof structures is bound with the individuals available in the ABox and we obtain a polynomial construction w.r.t. the size of the input.
Together with the hardness of probabilistic entailment of simple consequences in BEL without ABoxes, we get the following result.
Lemma 5. Probabilistic query entailment restricted to IQs is PP-complete w.r.t. the combined complexity. 5
Query answering is the problem of nding mappings for a query, i.e. one is not just interested whether a query is entailed or not, but also with the witnesses of such entailment. Typically, data is assumed to be large and it is not always very feasible to return all answers to a query q to the user. One of the most important applications of query answering is returning the top-k answers to a given query q w.r.t. a measure. By this way users do not only get a feasible number of answers but also a ne grained view over the data. In the context of probabilities, we are interested in nding the answers that are most likely.
Let q be a query with the distinguished variables DV(q), and K = (B; T ; A) a BEL KB. We denote by Ind(A) the set of all individual names appearing in A. Recall that every function a : DV(q) ! Ind(A) de nes a CQ obtained by replacing every 2 DV(q) in q with a( ). Abusing the notation, we call this query a(q). We call any function a : DV(q) ! Ind(A) an answer to q w.r.t. K, and de ne its probability as PK(a) := PK(a(q)). Since an answer de nes a boolean CQ, all complexity results for CQs transfer immediately. Every answer to a query q, has a probability, which we use as a measure to distinguish the answers. We re ne the set of answers w.r.t. their probabilities and return top answers only.
De nition 6 (top-k answer). Let q be a query, K be a BEL KB, and k 2 N. A top-k answer to q w.r.t. K is a tuple (a1; : : : ; ak) of di erent answers to q w.r.t. K such that (i) for all i; 1 i < k, PK(ai) PK(ai+1), and (ii) for every other answer a, PK(ak) PK(a).
In other words, a top-k answer is an ordered tuple of the k answers with the highest probability. We assume that k is a constant that is xed a priori. Thus, it is not considered part of the input of the problem. Obviously, since di erent answers may have the same probability, top-k answers are not unique. Here we are only interested in nding one of them. Stating it as a decision problem, we want to verify whether a given tuple is a top-k answer.
Example 7. Consider the BEL KB K = ((TABC; AABC); BABC) provided in Example 3 and the query q = fA( )g with 2 DV. We are interested in identifying the top-1 answer to q w.r.t. K. Notice that both a0 : 7! a and a1 : 7! c are answers to q with positive probability. Clearly, a0 is the top-1 answer since PK(a0) > PK(a1).
Assuming that the size of q and the BN B are xed, there are polynomially many answers to q w.r.t. K, and for each answer a, we can compute PB(a) performing polynomially many EL query entailment tests. Thus, it is possible to verify whether (a1; : : : ; ak) is a top-k answer in polynomial time w.r.t. ontology complexity.
If we consider the combined complexity, the problem can be decided as follows. For every answer to the query, we only keep track of those answers that are best by checking the probabilities PB(a) of the individual answers iteratively. Since the latter can be done in PSpace, we obtain an upper bound. Theorem 8. Let A = (a1; : : : ; ak) be a tuple of answers to q w.r.t. K. Deciding whether A is a top-k answer is polynomial w.r.t. data and ontology complexity, in PSpace w.r.t. network complexity and combined complexity.
We show a lower bound for this problem w.r.t. the combined complexity.
by providing a reduction from the decision version of the maximum a-posteriori
(D-MAP) problem for BNs [
Consider an arbitrary but xed instance of D-MAP described by the BN B = ((V; E); ), the context , Q V , and p > 0. We introduce a new Boolean random variable z not appearing in V . Using this variable, we construct a new DAG (V 0; E) with V 0 = V [ fzg and a new BN B0 = ((V 0; E); 0), where PB0 (v j (v)) = PB(v j (x)) for all v 2 V , and PB0 (z) = p. Consider the BEL KB K = (B0; ;; A) where
A := fhAx(ax) : xi ; hAx(bx) : :xi ; hAx(c) : zi j x 2 Qg [
fhB(a) : i ; hB(c) : zig; and query q := fAx( x) j x 2 Qg [ fB( )g, where all the variables are distinguished; i.e., DV(q) = f x j x 2 Qg [ f g. It is easy to see that the mapping a0 : DV(q) ! fcg is an answer to this query and PK(a0) = p. Moreover, any other answer that maps any variable to c will have the probability at most p, since it can only be entailed in contexts satisfying z. Suppose that there is an answer a such that PK(a) > p. This answer must map every variable x to either ax or bx and to a. Let a := Va( x)=ax x ^ Va( x)=bx :x. By construction, a is a valuation of the variables in Q, PB( ^ a) > p, and a(q) is only entailed by valuations satisfying the context ^ a. Overall this means that a0 is not a top-1 answer i there is a valuation of the variables in Q such that PB( ^ ) > p. Theorem 9. Deciding whether a tuple A is a top-k answer is coNPPP-hard w.r.t. combined complexity.
Notice that the proof uses a very simple query which is in fact acyclic. Thus,
contrary to classical EL [
Obtaining most probable answers for a query is a crucial task for the domains where imprecise characterizations of knowledge is necessary. The next section is dedicated to another reasoning task that can be seen dual to top-k answers, namely top-k contexts. 6
Dually to nding the most likely answers to a query, we are also interested in nding the k most likely contexts that entail a given Boolean query q. More precisely, suppose that we have already observed that the query q holds; then, we are interested in nding out which is the current context. As in the previous section, we do not consider one, but search for a xed number of contexts that are the most likely to hold.
To de ne this reasoning task formally, we must generalize the notion of the ontology KW de ned to consider arbitrary contexts , which we denote as K . For any contextual interpretation (I; VI ) with VI j= it must hold that I j= K . If K entails the Boolean query q, then we say that q holds in context . We are interested in nding out the most likely contexts in which a given query holds. De nition 10 (top-k contexts). Let q be a CQ, K a BEL KB, and k 2 N.
1; : : : ; k are top-k contexts for q w.r.t. K if K i entails q for all i; 1 i k; PB( i) PB( i+1) for all i; 1 i k; and there is no other context such that K j= q and PB( ) > PB( k).
We illustrate top-k mlc with our continuing example. In this case, we are
interested in nding out the 2 most likely context that entail the query.
Example 11. Consider the BEL KB K = ((TABC; AABC); BABC) and query q provided
in Example 3. Clearly all contexts that entail q are such that j= fx; yg_fx; zg.
The top-2 contexts are then hfx; yg; fx; zgi since PBABC (fx; yg) > PBABC (fx; zg).
The problem of nding one most likely context has been studied for simple
queries. In those special cases, it was shown to be coNPPP-complete problem
w.r.t. combined complexity [
Theorem 12. Deciding whether 1; : : : ; k are top-k mlc for q w.r.t. the KB K is polynomial w.r.t. data, and ontology complexity, PP-hard and in NPPP w.r.t. network complexity, and NPPP-complete w.r.t. combined complexity.
Given the hardness of deciding top-k contexts, we consider a special case of this problem: Suppose now that all contexts are of a special form, i.e. they are valuations, we call this problem top-k worlds. In this case, we need to guess a world W and decide whether i) KW j= q and ii) PK(W) > PK(Wk), where the former requires an NP oracle whereas the latter can be decided in polynomial time using tha standard chain rule of BNs.
Notice that, top-k contexts and top-k answers are dual to each other, but they do not necessarily overlap. Consider for instance the case, where all top-k answers to a query q are retrieved from the same context . In this case, top-k contexts for q will contain other contexts than with the assumption that k > 1. Deciding top-k contexts is particularly informative for cases where the diversity of knowledge is important.
We have discussed several reasoning problems in BEL w.r.t. CQs which we considered as natural problems that could arise in several domains. For a summary of the results, see Table 2. 7
The literature on probabilistic extensions of DLs consists of various formalisms,
each of which with di erent characteristics [
P P P P P
P P P P P
PP-c PP-c combined PP/PSpace
PP-c.
coNP-c
coNP/ 2p
RDF graphs [
In the probabilistic extension of Datalog+/- [
We have studied probabilistic query entailment, top-k answers and top-k contexts as reasoning problems. Though not being complete, for each of these problems, we provided a complexity analysis. Moreover, we have shown that assuming that the given BN and query are relatively small, all problems become tractable. Removing this assumption immediately results in the loss of tractability, which is not surprising given the intractability results in BNs and CQA in EL.
As a future work, we want to obtain tight bounds w.r.t. all measures provided. We have shown tight complexity bounds for the query entailment problem of IQs. Restricting our attention to IQs, other problems might also get easier under widely accepted assumptions of complexity theory. It should be reminded that this is unfortunately not the case for acyclic queries.
On the practical side, we will consider optimizing the reasoning mechanisms
and we will implement a system for reasoning in BEL that will bene t both
from techniques in DLs, such as module extraction, query processing and from
techniques in reasoning with lifted BNs, mainly based on logic programming as
in [