In logic programming the distribution semantics is one of the most popular approaches for dealing with uncertain information. In this paper we apply the distribution semantics to the Datalog+/- language that is grounded in logic programming and allows tractable ontology querying. In the resulting semantics, called DISPONTE, formulas of a probabilistic ontology can be annotated with an epistemic or a statistical probability. The epistemic probability represents a degree of con dence in the formula, while the statistical probability considers the populations to which the formula is applied. The probability of a query is de ned in terms of nite set of nite explanations for the query. We also compare the DISPONTE approach for Datalog+/- ontologies with that of Probabilistic Datalog+/- where an ontology is composed of a Datalog+/theory whose formulas are associated to an assignment of values for the random variables of a companion Markov Logic Network.
Representing uncertain information is fundamental for ensuring that the Semantic Web achieves its full potential [36, 29, 25]. Ontologies are a decisive component of the Semantic Web and recently Datalog was extended for modeling ontologies [5, 6]. Answering conjunctive queries in the resulting language, Datalog+/-, has a polynomial data complexity, thus allowing tractable query answering.
Probabilistic Datalog+/- [15, 14] has been proposed for representing uncertainty in Datalog+/-. In this approach an ontology is composed of a Datalog+/theory and a Markov Logic Network (MLN) [30] and each Datalog+/- formula is associated to an assignment of values to (a subset of) the random variables that are modeled by the MLN. This assignment, called scenario, controls the activation of the formulas: they hold only in worlds where the scenario is satis ed.
In the eld of logic programming, the distribution semantics [35] has emerged as one of the most e ective approaches for integrating logic and probability and underlies many languages such as PRISM [35], ICL [28], Logic Programs with Annotated Disjunctions [37] and ProbLog [11]. In this semantics the clauses of a probabilistic logic program contain alternative choices annotated with probabilities. Each grounding of a probabilistic clause represents a random variable that can assume a value from the nite set of alternatives. In order to compute the probability of a query, its explanations have to be found, where an explanation is a set of choices that ensure the entailment of the query. The set of explanations must be covering, i.e., it must represent all possible ways of entailing the query. The probability is computed from a covering set of explanations by solving a disjoint sum problem, either using an iterative splitting algorithm [28] or Binary Decision Diagrams [19, 31].
In Bellodi et al. [1] we have applied the distribution semantics to ontology languages based on Description Logic. We called the approach DISPONTE for \DIstribution Semantics for Probabilistic ONTologiEs" (Spanish for \get ready"). In this paper we apply DISPONTE to Datalog+/-. The idea is to annotate formulas of a theory with a probability and assume that each formula is independent of the others. Moreover, we extend [1] by allowing two types of probabilistic annotations, an epistemic type, that represents a degree of belief in the formula as a whole, and a statistical type, that considers the populations to which the formula is applied. While in the rst case the choice is whether to include or not a formula in an explanation, in the latter case the choice is whether to include instantiations of the formula for speci c individuals. The probability of a query is again computed from a covering set of explanations by solving the disjoint sum problem. We call the resulting language DISPONTE Datalog+/-.
The paper is organized as follows. Section 2 provides some preliminaries on Datalog+/-. Section 3 presents DISPONTE Datalog+/-. Section 4 describes related work and Section 5 concludes the paper. 2
Datalog+/- extends Datalog by allowing existential quanti ers, the equality predicate and the truth constant false in rule heads. Datalog+/- can be used for representing lightweight ontologies and is able to express the DL-Lite family of ontology languages [5]. By suitably restricting the language syntax, Datalog+/achieves tractability [4].
In order to describe Datalog+/-, let us assume (i) an in nite set of data constants , (ii) an in nite set of labeled nulls N (used as \fresh" Skolem terms), and (iii) an in nite set of variables V . Di erent constants represent di erent values (unique name assumption), while di erent nulls may represent the same value. We assume a lexicographic order on [ N , with every symbol in
N following all symbols in . We denote by X vectors of variables X1; : : : ; Xk with k 0. A relational schema R is a nite set of relation names (or predicates). A term t is a constant, null or variable. An atomic formula (or atom) has the form p(t1; : : : ; tn), where p is an n-ary predicate, and t1; : : : ; tn are terms. A database
from [ N . A conjunctive query (CQ) over R has the form q(X) = 9Y (X; Y), where (X; Y) is a conjunction of atoms having as arguments variables X and
head predicate q of arity 0 (i.e., no variables in X).
We often write a BCQ as the set of all its atoms, having constants and variables as arguments, and omitting the quanti ers. Answers to CQs and BCQs are de ned via homomorphisms, which are mappings :
N [ V such that (i) c 2 implies (c) = c, (ii) c 2 N implies (c) 2 [ N , and (iii) is naturally extended to term vectors, atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ q(X) = 9Y (X; Y) over a database D, denoted q(D), is the set of all tuples t over for which there exists a homomorphism : X [ Y ! [ N such that ( (X; Y)) D and (X) = t. The answer to a BCQ q = 9Y (Y) over a database D, denoted q(D), is Yes, denoted D j= q, i there exists a homomorphism : Y ! [ N such that ( (Y)) D, i.e., if q(D) 6= ;.
a rst-order formula of the form 8X8Y (X; Y) ! 9Z (X; Z), where (X; Y) and (X; Z) are conjunctions of atoms over R, called the body and the head of
exists a homomorphism h such that h( (X; Y)) D, there exists an extension h0 of h such that h0( (X; Z)) D. We usually omit the universal quanti ers in TGDs. A TGD is guarded i it contains an atom in its body that involves all variables appearing in the body.
and a database D for R, the set of models of D given T , denoted mods(D; T ), is the set of all (possibly in nite) databases B such that D B and every
A Datalog+/- theory may contain also negative constraints (or NC), which are rst-order formulas of the form 8X (X) ! ?, where (X) is a conjunction of atoms (not necessarily guarded). The universal quanti ers are usually left implicit.
Equality-generating dependencies (or EGDs) are the third component of a
Xi = Xj , where (X), called the body of F , is a conjunction of atoms, and Xi and Xj are variables from X. We call Xi = Xj the head of F . Such F is satis ed in a database D for R i , whenever there exists a homomorphism h such that h( (X)) D, it holds that h(Xi) = h(Xj ). We usually omit the universal quanti ers in EGDs.
The chase is a bottom-up procedure for deriving atoms entailed by a database and a Datalog+/- theory. The chase works on a database through the so-called
a TGD F on R of the form 8X8Y (X; Y) ! 9Z (X; Z), F is applicable to D if there is a homomorphism h that maps the atoms of (X; Y) to atoms of D. Let F be applicable and h1 be a homomorphism that extends h as follows: for each Xi 2 X, h1(Xi) = h(Xi); for each Zj 2 Z, h1(Zj ) = zj , where zj is a \fresh" null, i.e., zj 2 N ; zj 62 D, and zj lexicographically follows all other labeled nulls already introduced. The result of the application of the TGD chase rule for F is the addition to D of all the atomic formulas in h1( (X; Z)) that are not already in D.
The EGD chase rule is de ned as follows. An EGD F on R of the form (X) ! Xi = Xj is applicable to a database D for R i there exists a homomorphism h : (X) ! D such that h(Xi) and h(Xj ) are di erent and not both constants. If h(Xi) and h(Xj ) are di erent constants in , then there is a hard violation of F . Otherwise, the result of the application of F to D is the database h(D) obtained from D by replacing every occurrence of a non-constant element e 2 fh(Xi); h(Xj )g in D by the other element e0 (if e and e0 are both nulls, then e precedes e0 in the lexicographic order).
The chase algorithm consists of an exhaustive application of the TGD and
EGD chase rules that may lead to an in nite result. The chase rules are applied
iteratively, in each iteration (
The two problems of CQ and BCQ evaluation under TGDs and EGDs are logspace-equivalent [6]. Moreover, query answering under TGDs is equivalent to query answering under TGDs with only single atoms in their heads [4]. Henceforth, we focus only on the BCQ evaluation problem and we assume that every TGD has a single atom in its head. A BCQ q on a database D, a set TT of TGDs and a set TE of EGDs can be answered by performing the chase and checking whether the query is entailed by the extended database that is obtained. In this case we write D [ TT [ TE j= q.
Example 1. Let us consider the following ontology for a real estate information extraction system, a slight modi cation of the one presented in Gottlob et al. [15]:
F1 = ann(X; label); ann(X; price); visible(X) ! priceElem(X) If X is annotated as a label, as a price and is visible, then it is a price element.
F2 = ann(X; label); ann(X; priceRange); visible(X) ! priceElem(X) If X is annotated as a label, as a price range, and is visible, then it is a price element.
F3 = priceElem(E); group(E; X) ! f orSale(X) If E is a price element and is grouped with X, then X is for sale.
F4 = f orSale(X) ! 9P price(X; P ) If X is for sale, then there exists a price for X.
F5 = hasCode(X; C); codeLoc(C; L) ! loc(X; L) If X has postal code C, and C's location is L, then X's location is L.
F6 = hasCode(X; C) ! 9LcodeLoc(C; L); loc(X; L) If X has postal code C, then there exists L such that C has location L and so does X.
F7 = loc(X; L1); loc(X; L2) ! L1 = L2 If X has the locations L1 and L2, then L1 and L2 are the same.
F8 = loc(X; L) ! advertised(X) If X has a location L then X is advertised.
Suppose we are given the database codeLoc(ox1; central); codeLoc(ox1; south); codeLoc(ox2; summertown) hasCode(prop1; ox2); ann(e1; price); ann(e1; label); visible(e1); group(e1; prop1) The atomic BCQs priceElem(e1), f orSale(prop1) and advertised(prop1) evaluate to true, while the CQ loc(prop1; L) has answers q(L) = fsummertowng.
mula F7 imposes that summertown = z1. If F7 were absent then q(L) = fsummertown; z1g.
Answering BCQs q over databases and ontologies containing NCs can be performed by rst checking whether the BCQ (X) evaluates to false for each NC of the form 8X (X) ! ?. If one of these checks fails, then the answer to the original BCQ q is positive, otherwise the negative constraints can be simply ignored when answering the original BCQ q.
A guarded Datalog+/- ontology is a quadruple (D; TT ; TC ; TE) consisting of a database D, a nite set of guarded TGDs TT , a nite set of negative constraints TC and a nite set of EGDs TE that are separable from TT . The data complexity (i.e., the complexity where both the query and the theory are xed) of evaluating BCQs relative to a guarded Datalog+/- theory is polynomial [4].
In the case in which the EGDs are key dependencies and the TGDs are inclusion dependencies, Cal et al. [8] proposed a backward chaining algorithm for answering BCQ. A key dependency is a set of EGDs of the form fr(X; Y1; : : : ; Ym); r(X; Y10; :::; Y m0) ! Yi = Yi0g1 i m A TGD of the form r1(X; Y) ! 9Zr2(X; Z), where r1 and r2 are predicate names and no variable appears more than once in the body nor in the head, is called an inclusion dependency. The key dependencies must not interact with the inclusion dependencies, similarly to the semantic separability condition mentioned above for TGDs and EGDs. In this case once it is known that no hard violation occurs, queries can be answered by considering the inclusion dependencies only, ignoring the key dependencies. A necessary and su cient syntactic condition for non interaction is based on the construction of CD-graphs [8]. 3
The DISPONTE Semantics for Probabilistic Ontologies The distribution semantics [35] is one of the most widely used semantics for probabilistic logic programming. In this semantics a probabilistic logic program de nes a probability distribution over a set of normal logic programs (called worlds). The distribution is extended to a joint distribution over worlds and a query and the probability of the query is obtained from this distribution by marginalization.
In this section we discuss how we applied this approach to give a semantics to a probabilistic version of Datalog+/- that we call DISPONTE Datalog+/-.
A probabilistic DISPONTE Datalog+/- ontology (or simply probabilistic
ontology ) consists of a database D and a set of certain formulas, that take the form
of a Datalog+/- TGD, NC or EGD, of epistemic probabilistic formulas of the
form
pi ::e Fi
(
Let us call TT the set of all TGD formulas (certain, epistemic or statistical), TC the set of NC formulas (certain or epistemic) and TE the set of EGD formulas (certain or epistemic). Thus a probabilistic ontology O is a quadruple O = (D; TT ; TC ; TE ). Let us indicate with T the union TT [ TC [ TE .
In formulas of the form (
For example, an epistemic probabilistic concept inclusion TGD of the form
represents the fact that we believe in the truth of c d, where c and d are
interpreted as sets of individuals, with probability p. A statistical probabilistic
concept inclusion TGD of the form
p ::e c(X) ! d(X)
p ::s c(X) ! d(X)
(
The idea of DISPONTE Datalog+/- is to associate independent Boolean random variables to (instantiations of) the formulas. By assigning values to every random variable we obtain a world, the set of logic formulas whose random variable is assigned to 1.
To clarify what we mean by instantiations, we now de ne substitutions. Given a formula F , a substitution is a set of couples X=x where X is a variable universally quanti ed in the outermost quanti er in F and x 2 [ N . The application of to F , indicated by F , is obtained by replacing X with x in F and by removing X from the external quanti cation for every couple X=x in . An instantiation of a formula F is the result of applying a substitution to F .
To obtain a world w of a probabilistic ontology O, we include every certain
formula in w. For each axiom of the form (
There may be an in nite number of instantiations. For each instantiated formula, we decide whether or not to include it in w. In this way we obtain a Datalog+/- theory which can be assigned a semantics as seen in Section 2.
To formally de ne the semantics of a probabilistic ontology we follow the
approach of Poole [28]. An atomic choice in this context is a triple (Fi; j ; k)
where Fi is the i-th formula, j is a substitution and k 2 f0; 1g. k indicates
whether Fi j is chosen to be included in a world (k = 1) or not (k = 0). If Fi
is obtained from a certain formula, then j = ; and k = 1. If Fi is obtained
from a formula of the form (
A composite choice is a consistent set of atomic choices, i.e., (Fi; j ; k) 2 ; (Fi; j ; m) 2 ) k = m (only one decision for each formula). The probability of composite choice is P ( ) = Q(Fi; j;1)2 pi Q(Fi; j;0)2 (1 pi). A selection is a total composite choice, i.e., it contains an atomic choice (Fi; j ; k) for every instantiation Fi j of formulas of the theory. Since the domain is in nite, every selection is, too. Let us indicate with SO the set of all selections. SO is in nite as well. A selection identi es a theory w called a world in this way: w = fFi j j(Fi; j ; 1) 2 g. Let us indicate with WO the set of all worlds. A composite choice identi es a set of worlds ! = fw j 2 SO; g. We de ne the set of worlds identi ed by a set of composite choices K as !K = S 2K ! .
A composite choice is an explanation for a BCG query q if q is entailed by the database and every world of ! . A set of composite choices K is covering with respect to q if every world w in which q is entailed is such that w 2 !K . Two composite choices 1 and 2 are incompatible if their union is inconsistent.
Kolmogorov de ned probability functions (or measures) as real-valued
functions over an algebra of subsets of a set W called the sample space. The
set is an algebra of W i (
Given a sample space W and an algebra of subsets of W, a probability
measure is a function : ! R that satis es the following axioms: (
These results also hold for the probabilistic ontologies we consider so we can de ne a unique probability measure : O ! [0; 1] where O is de ned as the set of sets of worlds identi ed by nite sets of nite composite choices: O = f!K jK is a nite set of nite composite choicesg. It is easy to see that
Then is de ned by (!K ) = P 2K0 P ( ) where K0 is a nite mutually incompatible set of nite composite choices such that !K = !K0 . hWT ; T ; i is a probability space according to Kolmogorov's de nition.
The probability of a BCQ query q = 9Y (Y), where (Y) is a conjunction of atoms having as arguments variables Y and constants (but no nulls) is P (q) = (fwjw 2 WO ^ D [ w j= qg). If q has a nite set K of nite explanations such that K is covering then fwjw 2 WO ^ D [ w j= qg 2 O and P (q) is well-de ned.
Let H(Q) be the set of all homomorphisms of the form h : Y ! [ N such that fwjw 2 WO ^ D [ w j= h( (Y))g is not empty. Then fwjw 2 WO ^ D [ w j= qg =
[ fwjw 2 WO ^ D [ w j= h( (Y))g: h2H(q) [28] also proposed an algorithm, called splitting algorithm, to obtain a set of mutually incompatible composite choices from any set of composite choices. Example 2. Let us consider the following probabilistic ontology, obtained from the one presented in Example 1 by adding probabilistic annotations: 0:4 ::s F1 = ann(X; label); ann(X; price); visible(X) ! priceElem(X) 0:5 ::s F2 = ann(X; label); ann(X; priceRange); visible(X) ! priceElem(X) 0:6 ::s F3 = priceElem(E); group(E; X) ! f orSale(X)
F4 = f orSale(X) ! 9P price(X; P ) F5 = hasCode(X; C); codeLoc(C; L) ! loc(X; L)
F6 = hasCode(X; C) ! 9LcodeLoc(C; L); loc(X; L) 0:8 ::e F7 = loc(X; L1); loc(X; L2) ! L1 = L2 0:7 ::s F8 = loc(X; L) ! advertised(X) and the database of Example 1: codeLoc(ox1; central); codeLoc(ox1; south); codeLoc(ox2; summertown); hasCode(prop1; ox2); ann(e1; price); ann(e1; label); visible(e1); group(e1; prop1) A covering set of explanations for the query q = priceElem(e1) is K = f 1g where 1 = f(F1; fX=e1g; 1)g. K is also mutually exclusive so P (Q) = 0:4.
A covering set of explanations for the query q = f orSale(prop1) is K = f 1; 2g where 1 = f(F1; fX=prop1g; 1); (F3; fX=prop1g; 1)g and 2 = f(F2; fX=prop1g; 1); (F3; fX=prop1g; 1)g.
An equivalent mutually exclusive set of explanations obtained by applying the splitting algorithm is K0 = f 01; 02g where 01 = f(F1; fX=prop1g; 1); (F3; fX=prop1g; 1); (F2; fX=prop1g; 0)g and 02 = f(F2; fX=prop1g; 1); (F3; fX=prop1g ; 1)g so P (q) = 0:4 0:6 0:5 + 0:5 0:6 = 0:42.
A covering set of explanations for the query q = advertised(prop1) is K = f 1; 2; 3g with 1 = f(F8; fX=prop1; L=summertowng; 1); (F7; ;; 1)g 2 = f(F8; fX=prop1; L=summertowng; 1); (F7; ;; 0)g 3 = f(F8; fX=prop1; L=z1g; 1); (F7; ;; 0)g where z1 2 N and certain formulas have been omitted. A mutually exclusive set of explanations is K0 = f 01; 02; 03g where 01 = f(F8; fX=prop1; L=summertowng; 1); (F7; ;; 1)g 02 = f(F8; fX=prop1; L=summertowng; 1); (F7; ;; 0); (F8; fX=prop1; L=z1g; 0)g 03 = f(F8; fX=prop1; L=z1g; 1); (F7; ;; 0)g so P (q) = 0:7 0:8 + 0:7 0:2 0:3 + 0:7 0:2 = 0:742.
Example 3. Let us consider the following ontology, inspired by the people+pets ontology proposed in Patel-Schneider et al. [27]:
F1 = hasAnimal(X; Y ); pet(Y ) ! petOwner(X) 0:6 ::e F2 = cat(X) ! pet(X) and the database hasAnimal(kevin; u y); hasAnimal(kevin; tom); cat( u y); cat(tom). A covering set of explanations for the query q = petOwner(kevin) is K = f 1g where 1 = f(F2; ;; 1)g and certain formulas have been omitted. This is also a mutually exclusive set of explanations so P (q) = 0:6.
Example 4. If the axiom 0:6 ::e F2 = cat(X) ! pet(X) in Example 3 is replaced by 0:6 ::s F2 = cat(X) ! pet(X) then the query would have the set of explanations K = f 1; 2g where 1 = f(F2; fX= u yg; 1)g and 2 = f(F2; fX=tomg; 1)g which, after splitting, becomes K0 = f 01; 02g with 01 = f(F1; fX= u yg; 1); (F1; fX=tomg; 0)g 02 = f(F1; fX=tomg; 1)g and certain formulas have been omitted, so P (q) = 0:6 0:4 + 0:6 = 0:84. Example 5. Let us consider a slightly di erent ontology: 0:5 ::s F1 = hasAnimal(X; Y ); pet(Y ) ! petOwner(X) 0:6 ::s F2 = cat(X) ! pet(X) and the database of Example 3. A covering set of explanations for the query q = petOwner(kevin) is K = f 1; 2g where: 1 = f(F1;fX=keving;1);(F2;fX= u yg;1)g 2 = f(F1;fX=keving;1);(F2;fX=tomg;1)g An equivalent mutually exclusive set of explanations is K0 = f 01; 02g where: 01 = f(F1;fX=keving;1);(F2;fX= u yg;1);(F2;fX=tomg;0)g 02 = f(F1;fX=keving;1);(F2;fX=tomg;1)g so P(q) = 0:5 0:6 0:4 + 0:5 0:6 = 0:42.
Example 6. Let us consider the following ontology:
F1 = 9hasAnimal(X;Y );pet(Y ) ! petOwner(X) 0:6 ::s F2 = cat(X) ! pet(X) 0:4 ::e F3 = cat( u y) 0:3 ::e F4 = cat(tom) and the database hasAnimal(kevin; u y);hasAnimal(kevin;tom). A covering set of explanations for the query axiom q = petOwner(kevin) is: K = f 1; 2g where 1 = f(F3;;;1);(F2;fX= u yg;1)g 2 = f(F4;;;1);(F2;fX=tomg;1)g and certain formulas have been omitted. After splitting K becomes K0 = f 01; 02; 03g with: 01 = f(F3;;;1);(F2;fX= u yg;1);(F4;;;1);(F2;fX=tomg;0)g 02 = f(F3;;;1);(F2;fX= u yg;1);(F4;;;0)g 03 = f(F4;;;1);(F2;fX=tomg;1)g so P(q) = 0:4 0:6 0:3 0:4 + 0:4 0:6 0:7 + 0:3 0:6 = 0:3768.
Example 7. Let us consider a further ontology:
F1 = 0:7 ::s schoolchild(X) ! european(X) F2 = 0:3 ::s schoolchild(X) ! onlyChild(X) F3 = 0:6 ::s european(X) ! goodInMath(X)
F4 = 0:5 ::s onlyChild(X) ! goodInMath(X) and the database schoolchild(anna). A covering set of explanations for the query q = goodInM ath(anna) is K = f 1; 2g where: 1 = f(F1; fX=annag; 1); (F3; fX=annag; 1)g 2 = f(F2; fX=annag; 1); (F4; fX=annag; 1)g After splitting we get K0 = f 01; 02; 03g where:
(F4; fX=annag; 0)g 01 = f(F1; fX=annag; 1); (F3; fX=annag; 1); (F2; fX=annag; 1); 02 = f(F1; fX=annag; 1); (F3; fX=annag; 1); (F2; fX=annag; 0)g 03 = f(F2; fX=annag; 1); (F4; fX=annag; 1)g So P (q) = 0:7 0:6 0:3 0:5 + 0:7 0:6 0:7 + 0:3 0:5 = 0:507. 4
This work builds on Bellodi et al. [1] that presented a version of DISPONTE applied to Description Logics and where only epistemic probabilities were present.
Gottlob et al. [15, 14] presented Probabilistic Datalog+/-, a version of Datalog+/- that allows the representation of probabilistic information by combining Markov Logic Networks with Datalog+/-. Each Probabilistic Datalog+/formula F is annotated with a probabilistic scenario , an assignment of values to a set of random variables from the MLN associated to the ontology. A full probabilistic scenario assigns a value to all the random variables of the MLN. A probabilistic scenario represents an event that happens when the random variables described by the MLN assume the values indicate in the scenario. Probabilistic formulas then take the form F : .
A Probabilistic Datalog+/- ontology is of the form = (O; M ) where O is a set of annotated formulas and M is an MLN. An annotated formula holds when the event associated with their probabilistic annotation holds.
If a is a ground atom, its probability in a Probabilistic Datalog+/- ontology = (O; M ), denoted P r(a), is obtained by summing the probabilities according to M of all full scenarios such that the atom is entailed by the annotated formulas that hold in the scenario.
Example 8. Let us consider the following probabilistic Datalog+/- ontology from [14]
F1 = visible(X) ! priceElem(X) : fann(X; label); ann(X; price)g F2 = visible(X) ! priceElem(X) : fann(X; label); ann(X; priceRange)g F3 = priceElem(E); group(E; X) ! f orSale(X) : fsaleg F4 = f orSale(E) ! 9P price(X; P ) F5 = hasCode(X; C); codeLoc(C; L) ! loc(X; L)
F7 = loc(X; L1); loc(X; L2) ! L1 = L2 : funiqueLocg and the MLN 0:3 ann(X; label) ^ ann(X; price) 0:4 ann(X; label) ^ ann(X; priceRange) 0:8 sale 1:1 uniqueLoc Suppose that this network is grounded with respect to the only constant e1. The resulting ground network has 5 Boolean random variables, each corresponding to a logical atom. Therefore, there are 25 full scenarios.
In this theory P (priceElem(e1)) = 0:492 and P (f orSale(prop1)) = 0:339. DISPONTE di ers from Probabilistic Datalog+/- because the probabilistic interactions among the atoms are modeled directly by means of Datalog+/- formulas rather than by a separate entity. The parameters of DISPONTE Datalog+/are easier to interpret as they are probabilities (statistical or epistemic) while MLN parameters are weights not directly interpretable as probabilities.
Moreover, DISPONTE does not require the prior grounding of the probabilistic atoms, for which the set of constants has to be de ned by the user, but allows an on demand grounding on the basis of the terms that are used for inference.
Heinsohn [17] proposed an extension of the description logic ALC that is able to express statistical information on the terminological knowledge such as partial concept overlapping. Similarly, Koller et al. [21] presented a probabilistic description logic based on Bayesian networks that deals with statistical terminological knowledge. [17, 21] do not allow probabilistic assertional knowledge about concept and role instances. Jaeger [18] allows assertional knowledge about concept and role instances together with statistical terminological knowledge and combines the resulting probability distributions using cross-entropy minimization but does not allow epistemic statements.
Ding et al. [12] proposed a probabilistic extension of OWL that admits a translation into Bayesian networks. The semantics that is proposed assigns a probability distribution P (i) over individuals, i.e. Pi P (i) = 1, and assigns a probability to a class C as P (C) = Pi2C P (i), while we assign a probability measure to sets of worlds. PR-OWL [10, 9] is an upper ontology that provides a framework for building probabilistic ontologies. It allows to use the rst-order probabilistic logic MEBN [22] for representing uncertainty in ontologies. The use of a full edged rst-order probabilistic logic distinguishes this work from ours, where we tried to provide a minimal extension to Datalog+/-.
A di erent approach to the combination of ontologies with probability is taken by Giugno et al. [13] and Lukasiewicz [23, 24], who use probabilistic lexicographic entailment from probabilistic default reasoning. The description logics proposed in these papers allows both terminological probabilistic knowledge as well as assertional probabilistic knowledge about instances of concepts and roles. PRONTO [20] is one of the systems that allows to perform inference in this semantics. Similarly to Jaeger [18], the terminological knowledge is interpreted statistically while the assertional knowledge is interpreted in an epistemic way by assigning degrees of beliefs to assertions. Moreover it also allows to express default knowledge about concepts that can be overridden in subconcepts and whose semantics is given by Lehmann's lexicographic default entailment. These works are based on Nilsson's probabilistic logic [26] where a probabilistic interpretation P r de nes a probability distribution over the set of interpretations Int. The probability of a logic formula F according to P r, denoted P r(F ), is the sum of all P r(I) such that I 2 Int and I j= F .
A probabilistic knowledge base K in Nilsson's logic is a set of probabilistic formulas of the form F p. A probabilistic interpretation P r satis es F p i
We say P (F ) p is a tight logical consequence of K i p is the in mum of P r(F ) subject to all models P r of K. Computing tight logical consequences from probabilistic knowledge bases can be done by solving a linear optimization problem.
In fact Nilsson's logic allows weaker conclusions than the distribution semantics. For example, consider a probabilistic ProbLog [11] program composed of 0:4 :: a: and 0:5 :: b: and a probabilistic knowledge base composed of a 0:4 and b 0:5. The distribution semantics allows to say that P (a _ b) = 0:7, while with Nilsson's logic the lowest p such that P r(a _ b) p holds is 0.5. This is due to the fact that in the distribution semantics the probabilistic atoms are considered as independent, which allows to make stronger conclusions. However, note that this does not restrict expressiveness as one can specify any joint probability distribution over the atoms interpreted as Boolean random variables, possibly introducing new random facts if needed.
Alternative approaches to modeling imperfect and incomplete knowledge in ontologies are based on fuzzy logic. A good survey of these approaches is presented in [25]. 5
We have presented the DISPONTE semantics for probabilistic ontologies in Datalog+/- that is inspired by the distribution semantics of probabilistic logic programming and is a minimal extension of the underlying ontology semantics to allow for representing and reasoning with uncertain knowledge.
In the future we plan to develop inference algorithm for DISPONTE
Datalog+/-, both bottom-up, on the basis of the chase procedure, and top-down,
by applying PITA [34] to non interacting inclusion and key dependencies.
Moreover, we will investigate the possibility of annotating also NCs and EGDs with
a statistical probability. Finally, we will work towards the automatic learning
of DISPONTE Datalog+/- ontologies, exploiting the techniques developed in
Riguzzi [32], Riguzzi et al. [33], Bellodi et al. [3, 2].
18. Jaeger, M.: Probabilistic reasoning in terminological logics. In: International
Conference on Principles of Knowledge Representation and Reasoning. pp. 305{316
(1994)
19. Kimmig, A., Demoen, B., Raedt, L.D., Costa, V.S., Rocha, R.: On the
implementation of the probabilistic logic programming language ProbLog. Theory and
Practice of Logic Programming 11(
Logic Journal of the IGPL 17(