Introduction

Usually, complex domains are modeled using either Logic Programming (LP) languages or Description Logic (DL) languages. These languages share many similarities because they are both based on first order logic. On the other hand, the main and remarkable difference is the domain closure assumption: closedworld assumption for LP and open-world assumption for DLs. However, the management of many domains, such as in legal reasoning [1], requires different closure assumptions.

The combination of LP and DL have been proposed by several authors and one of the most effective approaches is called Minimal Knowledge with Negation as Failure (MKNF) [15]. MKNF was then applied to define hybrid knowledge bases (HKBs) [18], which are defined as the combination of a logic program and a DL KB.

A large number of works in LP show how many domains, especially those derived from the real world, are often characterized by uncertain information, and present approaches and semantics for allowing probabilistic reasoning, leading to the dawn of the Probabilistic Logic Programming (PLP) field. One of the most widespread approach is the distribution semantics [24], where a program defines a probability distribution over normal Logic Programs, called worlds, from which the probability of a query is obtained. The distribution semantics underlies many languages such as Probabilistic Logic Programs [10], Logic Programs with Annotated Disjunctions (LPADs) [27], CP-logic [25] and ProbLog [11].

Similarly, DLs also need to manage uncertainty. The combination with probability theory have been proposed by several works exploiting graphical models: [9] and [8] exploit Bayesian networks while [14] combines DLs with Markov networks. Other approaches exploit Nilsson's probabilistic logic [19]: [13,16,17,7] reason with intervals of probability values. Others make use of databases techniques to store and recover information such as [12].

In [5] we defined DISPONTE (for "DIstribution Semantics for Probabilistic ONTologiEs"), which applies the distribution semantics to DLs, allowing to associate probability values to axioms of a KB. The probability of queries is computed as for PLP languages.

In [2] we proposed an approach for defining DL-safe Probabilistic Hybrid KBs (PHKBs) under the distribution semantics combining LPADs with DLs under DISPONTE semantics. In a PHKB, if the logic program is stratified, each program has a unique model, thus query's probability is the sum of probabilities of each program that implies the query.

A similar approach is the one of [20] where a sigma-algebra over complex relational models is used to allow existentials in ontologies and to define probability values on such information. The proposals makes use of semantic trees to define its semantics, such trees model the sequence of random variables and specify the trace of a generative process with its associated probabilities. The semantics so defined can be applied to different languages, allowing the integration of existence, identity, roles and ontologies into a clean semantic framework. We believe our approach leads to the definition of the same sigma-algebra and semantics, we leave for future work a detailed comparison with this work.

In this paper, we show that the semantics proposed in [2] can be unintuitive for non-DL-safe PHKBs, and we propose a new semantics that behaves as, arguably, expected. We also show that the new semantics coincides with the previous one if the PHKB is DL-safe.

The paper is structured as follows. In Section 2, we provide some background notions and define MKNF HKBs. In Section 3, we introduce our probabilistic extension to hybrid MKNF knowledge bases, and in Section 4 we define their semantics. Section 5 concludes the paper.

Background

This section introduces the necessary background to understand PHKBs. In particular, Section 2.1 introduces HKBs as the combination of DLs with LP. Then, Sections 2.3 and 2.2 present probabilistic DLs and probabilistic LPs, which are combined in PHKBs.

MKNF Hybrid Knowledge Bases

The logic of Minimal Knowledge with Negation as Failure (MKNF) was introduced in [15]. An MKNF Hybrid Knowledge Base (HKB) [18] is a pair K = O, P where O is a DL knowledge base and P is a set of LP rules of the form h ← a 1 , . . . , a n , ∼b 1 , . . . , ∼b m , where a i and b i are atoms; ∼ represents default negation; a negative literal is a default negated atom.

DLs are a fragment of First Order Logic (FOL) used to model ontologies [4], thus they can be directly translated into FOL by exploiting a function π, which maps axioms to first order formulas. A DL knowledge base (KB) is defined using concepts, roles and individuals. A HKB is positive if no negative literals occur in it. Note that we simplify the definition in [18] by disallowing disjunctions, which we do not need, in LP rule heads.

Given a HKB K = O, P , an atom in P is a DL-atom if its predicate occurs in O, a non-DL-atom otherwise. An LP rule is DL-safe if each of its variables occurs in at least one positive non-DL-atom in the body; a HKB is DL-safe if all its LP-rules are DL-safe. If there exists at least one LP rule that is not DL-safe, we say that the HKB is non-DL-safe.

A Hybrid Knowledge Base is given semantics by transforming it into an MKNF formula. More precisely, the transform π defined for DLs is extended as follows to support LP rules (where π(O) is the translation of O by means of π):

-if C is a rule of the form h ← a 1 , . . . , a n , ∼b 1 , . . . , ∼b m and X is the vector of all variables in C, π(C) = ∀X(K a 1 ∧ . . . ∧ K a n ∧ not b 1 ∧ . . . ∧ . . . not b m ⊃ K h) -π(P) = C∈P π(C) -π( O, P ) = K π(O) ∧ π(P)

The syntax of MKNF is the syntax of first order logic augmented with modal operators K and not . In the following, ∆ is the Herbrand universe of the signature at hand. An MKNF structure is a triple (I, M, N ) where I as a first-order interpretation over ∆ and M and N are sets of first order interpretations over ∆. Entailment of a closed formula by an MKNF structure is defined as follows:

(I, M, N ) |= p ⇔ p ∈ I (I, M, N ) |= ¬ϕ ⇔ (I, M, N ) |= φ (I, M, N ) |= ϕ 1 ∧ ϕ 2 ⇔ (I, M, N ) |= ϕ 1 and (I, M, N ) |= ϕ 2 (I, M, N ) |= ∃x : ϕ ⇔ (I, M, N ) |= ϕ[α/x] for some α ∈ ∆ (I, M, N ) |= K ϕ ⇔(J, M, N ) |= ϕ for all J ∈ M (I, M, N ) |= not ϕ ⇔(J, M, N ) |= ϕ for some J ∈ N An MKNF interpretation is a set M of interpretations over ∆. An interpre- tation M is an MKNF model of a closed formula ϕ iff -(I, M, M ) |= ϕ for all I ∈ M -for all M ⊃ M , for some I ∈ M (I , M , M ) |= ϕ

A formula ϕ entails a formula φ, written ϕ |= MKNF φ, iff for all MKNF models M of ϕ and for all I ∈ M (I, M, M ) |= φ.

Probabilistic Logic Programs

We consider Logic Programs with Annotated Disjunctions (LPADs) [26], which consist of a finite set of annotated disjunctive clauses r i of the form h i1 : Π i1 ; . . . ; h ini : Π ini ← b i1 , . . . , b imi . Here, b i1 , . . . , b imi are logical literals which form the body of r i , denoted by body(r i ), while h i1 , . . . h ini are logical atoms and {Π i1 , . . . , Π ini } are real numbers in the interval [0, 1] such that

ni k=1 Π ik ≤ 1. If n i = 1 and Π i1 = 1 the clause is a non-disjunctive clause. If ni k=1 Π ik < 1,

the head of the annotated disjunctive clause implicitly contains an extra atom null that does not appear in the body of any clause and whose annotation is 1 − ni k=1 Π ik . The grounding of an LPAD P is denoted by ground(P). An atomic choice is a triple (r i , θ j , k) where r i ∈ P, θ j is a substitution that grounds r i and k ∈ {1, . . . , n i } identifies a head atom of r i . It corresponds to an assignment X ij = k, where X ij is a multi-valued random variable which corresponds to C i θ j .

A set of atomic choices κ is consistent if only one head is selected from a ground clause. In this case it is called a composite choice. The probability P (κ) of a composite choice κ is (ri,θj ,k)∈κ Π ik . A selection σ is a set of atomic choices that, for each clause r i θ j in ground(P), contains an atomic choice (r i , θ j , k). It identifies a world w σ of P, i.e., a normal logic program defined as

w σ = {(h ik ← body(r i ))θ j |(r i , θ j , k) ∈ σ}.

We consider only sound LPADs, where each possible world has a total wellfounded model, so w σ |= q means that the query q is true in the well-founded model of the program w σ . The probability of a query q given a world w σ is P (q|w σ ) = 1 if w σ |= q and 0 otherwise. The probability of q is then:

P (q) = wσ∈L T P (q, w σ ) = wσ∈L T P (q|w σ )P (w σ ) = wσ∈L T :wσ|=q P (w σ )(1)

Given an LPAD P, W P is the set of all P's possible worlds. A composite choice, or a set of composite choices, determine sets of worlds. In particular, given a composite choice κ, the set of worlds determined by κ is the set of worlds identified by total choices that are subsets of κ, i.e., ω κ = {w σ | κ ⊆ σ}. Given a set K of composite choices, the set of worlds determined by K is ω K = κ∈K ω κ ; two sets K 1 and K 2 of composite choices are equivalent if ω K1 = ω K2 .

We assign probabilities to sets of worlds, rather than to individual worlds, as follows. Given an LPAD P, let Ω P be the set of sets of worlds determined by countable sets of countable composite choices. As shown in [21], Ω P is a σalgebra over W P , so a probability measure µ : Ω K → [0, 1] can be defined over Ω P .

A set of composite choices is pairwise incompatible if any two choices from the set are incompatible; the probability of a pairwise incompatible set of composite choices is the sum of the probabilities of its elements.

Given a ground query q, a composite choice κ is an explanation for q if w |= q for all w ∈ ω κ . A set K of composite choices is covering for

q if {w | w |= q} ⊆ ω K .

The author of [21] shows that for each countable set K of countable composite choices, there exists a pairwise incompatible countable set K of countable composite choices that is equivalent to K, in the sense that they identify the same set of worlds.

For sound LPADs each query q has a countable covering set K of countable infinite explanations [21]; since there exists a pairwise incompatible set K that is equivalent to K, we can define the probability of q as µ(K ).

Probabilistic Description Logics

DISPONTE [5] applies the distribution semantics to probabilistic ontologies, allowing the definition of probabilistic knowledge bases O, that are sets of certain and probabilistic axioms. Certain axioms are regular DL axioms, while probabilistic axioms take the form Π :: a, where Π is a real number in [0, 1] and a is a DL axiom.

An atomic choice for an axiom a is a pair (a, i), where i is 1 if a is selected and 2 otherwise. Composite choices, set of composite choices and the other concepts from the previous subsection can be defined similarly. A world, here, is obtained by including in it all certain axioms and a subset of the uncertain axioms. The probability of the world is given by the product of the probability Π for the included axioms and 1 − Π for the excluded ones. The probability of a query is then the sum of the probabilities of the worlds where the query holds (see Eq. 1).

Probabilistic Hybrid Knowledge Bases

A Probabilistic Hybrid Knowledge Base (PHKB) is a pair K = O, P where O is a DISPONTE knowledge base and P is an LPAD without function symbols.

In [2], a PHKB's semantics is given by first grounding it over all the constants in the PHKB. A world is the deterministic ground HKB obtained by selecting, for each clause h i1 : Π i1 ; . . . ; h ini : Π ini ← b i1 , . . . , b imi , one of the disjuncts in the head and some of the DL axioms. The world's probability is the product of the probabilities of the selected head disjuncts and the selected axioms. In terms of the definitions given in Section 2.2, that is the probability of the set of worlds whose only element is the world at hand. Definition 1. Given a world w, the probability of a query q is defined as P (q|w) = 1 if w |= MKNF K q and 0 otherwise.

The probability of the query is its marginal probability:

P (q) = w P (w)P (q|w)(2)

Example 1. The following KB K models the insurgence of a protest against animal testing: P = (C 1 ) protest : 0.6 ← activist(X), ∼cruelT oAnimals(X). activist(kevin). (C 2 ) activist(nadia) : 0.3. O = ∃hasAnimal.pet ¬cruelT oAnimals (kevin, fluffy) : hasAnimal (E 1 ) 0.4 :: fluffy : cat cat pet This KB has 16 worlds and the query protest is true in four of them, those containing activist(nadia) and protest ← activist(nadia), ∼cruelT oAnimals(nadia), plus other two, those in which activist(nadia) is absent and fluffy : cat and protest ← activist(kevin), ∼cruelT oAnimals(kevin) are present.

So the probability of protest is 0.3 • 0.6 + 0.7 • 0.4 • 0.6 = 0.18 + 0.168 = 0.438.

This semantics is defined regardless of the PHKB's DL-safety, but it can give unintuitive results for non-DL-safe PHKBs, essentially because a non-DL-safe HKB may not have the same MKNF models of its grounding over its constants. Consider, for example, the following non-DL-safe HKB. In a model of K's, no individual is a dog in all interpretations, so each individual is a person. This means that in all interpretations, the guard that john commands is a person, and due to the first axiom, a soldier; in other words, in each interpretation john commands a soldier, and is a commander. Thus, K |= K commander(john).

However, the grounding over the known individuals yields the following clause:

P = person(john) ←∼dog(john).

so the only individual known to be a person is john, and (except in the worlds where john commands himself) the guard that john commands cannot be inferred to be a soldier . So the grounding of the HKB does not entail K soldier (john).

Semantics for non-DL-safe PHKBs

In this section, we propose a generalization of the semantics that is given by grounding the PHKB not only over the constants occurring in it, but also on the countable supply of constants provided by the standard name assumption [18]. We call ∆ the resulting countable set of constants.

Intuitively, a possible world is obtained by selecting one annotated disjunct for each ground clause in P, and some of the axioms in O, as in the semantics proposed in [2], but since worlds are obtained from infinite choice and so their probability is 0, in order to have a non-zero probability for a query we assign probabilities to sets of worlds, rather than to individual worlds.

We do so by extending to PHKBs the semantics for LPADs with function symbols recalled in Section 2.2. In particular, we extend the notion of atomic choice to axioms: an atomic choice for an axiom a determines whether a is selected, and is of the form (a, ∅, i), where i is 1 if a is selected and 2 otherwise. The second element, ∅, of the triple is there so atomic choices for rules and axioms are syntactically uniform.

A selection σ determines the world w σ , i.e., the HKB composed of:

-one rule for each grounding substitution θ of each rule r in P, where (r, θ, i) ∈ σ, whose head is the i-th disjunct of r/θ and whose body is r/θ's body; -the axioms a for which (a, ∅, 1) is in the selection.

Given a PHKB K, W K is the set of all K's possible worlds. A composite choice, or a set of composite choices, determine sets of worlds, as for LPADs. Given a PHKB K, let Ω K be the set of sets of worlds determined by finite or countable sets of finite or countable composite choices; a probability measure µ :

Ω K → [0, 1] is defined over Ω K .

If a query q has a countable covering set K of countable explanations, then there exists a pairwise incompatible set K with the same property, and whose probability µ(K ) is defined; that is defined as q's probability given K. Definition 2. Let K be a PHKB and K be a (finite or countable) covering set of (finite or countable) explanations for a query q. Then q's probability given K P K (q) is the probability of a pairwise incompatible set K of explanations equivalent to K, which is guaranteed to exist. In the last axiom there is an (unknown) individual that is a guard and that john commands. Let us call her u.

K |= K commander(john) is entailed by the worlds where the clause with substitution X/u for the first disjunct is selected. So {{(C 1 , X/u, 1)}} is a (finite) covering set of (finite) explanations. Its probability is 0.5.

Next, we show that the semantics proposed here generalizes the one presented in [2] for the PHKBs allowed there, i.e., DL-safe PHKBs without function symbols.

Proposition 1. Given a DL-safe PHKB without function symbols, the probability of any query is the same under the semantics in Definition 1 and the one in Definition 2.

Proof. A DL-safe KB is equivalent to its grounding over the constants that occur in it, and if function symbols are not allowed there are finitely many worlds; each world that entails the query is identified by a selection. The set of such selections is a pairwise incompatible covering set of explanations for the query, and its probability is identical to the one given Definition 1.

Conclusions

In this paper, we define a semantics for Probabilistic Hybdrid Knowledge Bases, which is equivalent to that given in [2], but that is applicable also for non-DLsafe PHKBs. We also show that in case of a DL-safe PHKB the two semantics coincide.

For the future we plan to provide a reasoner for such semantics. The idea is to follow [3], where is defined the SLG(O) procedure for HKBs under the well founded semantics. SLG(O) integrates a DL reasoner into the SLG procedure in the form of an oracle in order to manage the DL part of the HKBs. The oracle returns the LP atoms that would have to be true for the query to succeed.

We intend to follow a similar approach for PHKBs, integrating the TRILL probabilistic DL reasoner [29,28] with the PITA algorithm [23] for PLP reason-ing. We also plan to develop a web application for using the system, similarly to what we have done for TRILL 3 [6] and PITA 4 [22].

Moreover, we plan to perform a detailed comparison with alternative approaches for existential constructs in probabilistic logics, such as the one of [20].