We apply the distribution semantics for probabilistic ontologies (named DISPONTE) to the Datalog+/- language. In DISPONTE the 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, where an explanation is a set of possibly instantiated formulas that is su cient for entailing the query. The probability of a query is computed from the set of explanations by making them mutually exclusive. 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.
Many authors recognize that representing uncertain information is important
for the Semantic Web [
In a related research direction Cal et al. [
In the eld of logic programming, the distribution semantics [
In this paper we apply the distribution semantics to ontological languages and, in particular, to Datalog+/-. We call the approach DISPONTE for \DIstribution Semantics for Probabilistic ONTologiEs" (Spanish for \get ready"). The idea is to annotate formulas of a theory with a probability. We consider two types of probabilistic annotation, 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.
The paper is organized as follows. Section 2 provides some preliminaries on Datalog+/-. Section 3 presents DISPONTE while Section 4 describes related work. Section 5 concludes the paper. 2
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 D for R is a possibly in nite set of atoms with predicates from R and arguments 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 Y and constants (but no nulls). A Boolean CQ (BCQ) over R is a CQ having head predicate q of arity 0 (i.e., no variables in X).
We often write a BCQ omitting the quanti ers. Answers to CQs and BCQs are de ned via homomorphisms, which are mappings : [ N [ V ! [
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 over a database D is Yes, denoted D j= q, i q(D) 6= ;.
A tuple-generating dependency (or TGD) F is 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 F , respectively. Such F is satis ed in a database D for R i , whenever there 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.
Query answering under TGDs is de ned as follows. For a set of TGDs T on R 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 F 2 T is satis ed in B. The set of answers to a CQ q on D given T , denoted ans(q; D; T ), is the set of all tuples t such that t 2 q(B) for all B 2 mods(D; T ). The answer to a BCQ q over D given T is Yes, denoted D [ T j= q, i B j= q for all B 2 mods(D; T ).
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 Datalog+/- theory. An EGD F is a rst-order formula of the form 8X (X) ! Xi = Xj , where (X), called the body of F and denoted body(F ), is a conjunction of atoms, and Xi and Xj are variables from X. We call Xi = Xj the head of F , denoted head(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. An EGD F on R of the form (X) ! Xi = Xj is applicable to a database D for R i there exists a homomorphism : (X) ! D such that (Xi) and (Xj ) are di erent and not both constants. If (Xi) and (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 f (Xi); (Xj )g in D by the other element e0 (if e and e0 are both nulls, then e precedes e0 in the lexicographic order).
Example 1. Let us consider the following ontology for a real estate information
extraction system, a slight modi cation of the one presented in [
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); 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. In fact, even if loc(prop1; z1) with z1 2 N is entailed by formula F5, formula F7 imposes that summertown = z1. If F7 were absent, then q(L) = fsummertown; z1g.
The chase is a bottom-up procedure for repairing a database relative to a Datalog+/- theory and can be used for deriving atoms entailed by the database and the theory. If such a theory contains only TGDs, the chase consists of an exhaustive application of the TGD chase rule in a breadth- rst fashion. The TGD chase rule consists in adding to the database the head of a TGD if there is an homomorphism between the body and the current database. In order to ll the arguments of the head occupied by existentially quanti ed variables, \fresh" null values are used.
A BCQ can be answered by performing the chase and checking whether the query is entailed by the extended database that is obtained.
Answering BCQs q over databases, guarded TGDs and NC can be done by, for each constraint 8X (X) ! ?, checking that the BCQ (X) evaluates to false; 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.
The chase in the presence of both TGDs and EGDs is computed by
iteratively applying (1) a single TGD once and (2) the EGDs, as long as they are
applicable (i.e., until a x point is reached). EGDs are assumed to be separable
[
A guarded Datalog+/- ontology consists 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 [
A probabilistic ontology (D; T ) consists of a database D and a set T of certain formulas, that take the form of a Datalog+/- TGD, NC or EGD, of epistemic probabilistic formulas of the form where pi is a real number in [0; 1] and Fi is a TGD, NC or EGD, and of statistical probabilistic formulas 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) pi ::e Fi pi ::s Fi where pi is a real number in [0; 1] and Fi is a TGD.
In formulas of the form (1), pi is interpreted as an epistemic probability,
i.e., as the degree of our belief in formula Fi, while in formulas of the form
(2), pi is interpreted as a statistical probability, i.e., as information regarding
random individuals from certain populations. These two types of statements
can be related to the work of Halpern [
For example, an epistemic probabilistic concept inclusion TGD of the form (1) (2) (3) (4) instead means that a random individual of class c has probability p of belonging to d, thus representing the statistical information that a fraction p of the individuals of c belongs to d. In this way, the overlap between c and d is quanti ed. The di erence between the two formulas is that, if two individuals belong to class c, the probability that they both belong to d according to (3) is p while according to (4) is p p.
The idea of DISPONTE 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. Note that the assumption of independence of the random variables does not limit the set of distributions over the ground logical atoms that can be represented: by possibly introducing extra atoms, any distribution over the atoms that can be represented with a Bayesian network can be represented with a probabilistic ontology.
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 T , we include every certain formula in w. For each axiom of the form (1), we decide whether or not to include it in w. For each axiom of the form (2), we generate all the substitutions for the variables universally quanti ed in the outermost quanti er and for each instantiation we decide whether or not to include it in w.
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 [
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 one 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 ST the set of all selections. ST 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 WT the set of all worlds. A composite choice identi es a set of worlds ! = fw j 2 ST ; 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. A set K of composite choices is mutually incompatible if for all 1 2 K; 2 2 K; 1 6= 2 ) 1 and 2 are incompatible.
Explanations can be found by keeping track of the formulas that were used for adding atoms to the database in the chase procedure.
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 (1) W 2 , (2) is closed under complementation, i.e., ! 2 ! (W n !) 2 and (3) is closed under nite union, i.e., !1 2 ; !2 2 ! (!1 [ !2) 2 . The elements of are called measurable sets. Not every subset of W need be present in .
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: (1) (!) 0 for all ! 2 , (2) (W) = 1, (3) !1 \ !2 = ; ! (!1 [ !2) = (!1) + (!2) for all !1 2 ; !2 2 .
Poole [
These results also hold for the probabilistic ontologies we consider, so we can de ne a unique probability measure : T ! [0; 1] where T is de ned as the set of sets of worlds identi ed by nite sets of nite composite choices: T = f!K jK is a nite set of nite composite choicesg. It is easy to see that T is an algebra over WT .
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 is given by P (q) = (fwjw 2 WT ^D[w j= qg). If q has a nite set K of nite explanations such that K is covering then fwjw 2 WT ^ D [ w j= qg 2 T and P (q) is well-de ned.
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); 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. where z1 2 where
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
N . A mutually exclusive set of explanations is K0 = f 01; 02; 03g
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. [
F1 = 9Y hasAnimal(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 y g; 1)g 2 = f(F4; ;; 1); (F2; fX=tomg; 1)g which, after splitting, becomes K0 = f 01; 02; 03g: 01 = f(F3; ;; 1); (F2; fX= u y g; 1); (F4; ;; 1); (F2; fX=tomg; 0)g 02 = f(F3; ;; 1); (F2; fX= u y g; 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 4
Gottlob et al. [
A probabilistic Datalog+/- is of the form = (O; M ) where O is a set of annotated formulas and M is a MLN. An annotated formula holds when the event associated with its 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 5. Let us consider the following probabilistic Datalog+/- ontology from
[
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) F6 = hasCode(X; C) ! 9LcodeLoc(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 r(priceElem(e1)) = 0:492 and P r(f orSale(prop1)) = 0:339. 5
We have presented the application of the distribution semantics for probabilistic ontologies (named DISPONTE) to the Datalog+/- language. DISPONTE is inspired by the distribution semantics of probabilistic logic programming and is a minimal extension of the underlying ontology semantics to allow to represent and reason with uncertain knowledge.
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.
In the future we plan to design inference algorithms for probabilistic Datalog+/- under the DISPONTE semantics.