Probabilistic Description Logics under the distribution semantics

Abstract

Abstract

Representing uncertain information is crucial for modeling real world domains. In this paper we present a technique for the integration of probabilistic information in Description Logics (DLs) that is based on the distribution semantics for probabilistic logic programs. In the resulting approach, that we called DISPONTE, the axioms of a probabilistic knowledge base (KB) can be annotated with a real number between 0 and 1. A probabilistic knowledge base then defines a probability distribution over regular KBs called worlds and the probability of a given query can be obtained from the joint distribution of the worlds and the query by marginalization. We present the algorithm BUNDLE for computing the probability of queries from DISPONTE KBs. The algorithm exploits an underlying DL reasoner, such as Pellet, that is able to return explanations for queries. The explanations are encoded in a Binary Decision Diagram from which the probability of the query is computed. The experimentation of BUNDLE shows that it can handle probabilistic KBs of realistic size.

1. Introduction

Representing uncertain information is of foremost importance in order to effectively model real world domains. This has been fully recognized in the field of Artificial Intelligence where uncertainty has been the focus of much research since its beginnings. In particular, the integration of logic and probability allows to model complex domains with many entities interconnected by uncertain relationships. This problem has been investigated by various authors both in the general case of first order logic [6,22,42] and in the case of restricted logics, such as Description Logics (DLs) and Logic Programming (LP).

DLs are fragments of first order logic particularly useful for knowledge representation. They are at the basis of the Semantic Web. The Web Ontology Language (OWL) is a family of languages that are syntactic variants of various DLs. Many proposals have appeared on the combination of probability theory and DLs [23,24,35,39,40]. Probabilistic DLs play an important role in the Semantic Web where knowledge may come from different sources and may have different reliability.

In LP, the distribution semantics [65] has emerged as one of the most effective approaches for representing probabilistic information. It underlies many probabilistic logic programming languages such as Probabilistic Horn Abduction [47], PRISM [65,66], Independent Choice Logic [48], Logic Programs with Annotated Disjunctions [74], ProbLog [50] and CP-logic [75]. A program in one of these languages defines a probability distribution over normal logic programs called worlds. This distribution is extended to queries and the probability of a query is obtained by marginalizing the joint distribution of the query and the programs. The languages following the distribution semantics differ in the way they define the distribution over logic programs but have the same expressive power: there are transformations with linear complexity that can convert each one into the others [16,73].

The distribution semantics was applied successfully in many domains [7,50,66] and various inference and learning algorithms are available for it [8,31,54].

In [9,60,61] we applied this approach to DLs obtaining DISPONTE for “DIstribution Semantics for Probabilistic ONTologiEs” (Spanish for “get ready”). The idea is to annotate axioms of a theory with a probability and assume that each axiom is independent of the others. A DISPONTE knowledge base (KB) defines a probability distribution over regular KBs (worlds) and the probability of a query is obtained from the joint probability of the worlds and the query. The DISPONTE semantics differs from previous proposals because it provides a unified framework for representing different types of probabilistic knowledge, from assertional to terminological knowledge. DISPONTE can be applied to any DL, here we present it for a prototypical expressive DL, $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ , that is the basis of OWL DL.

We also present the algorithm BUNDLE for “Binary decision diagrams for Uncertain reasoNing on Description Logic thEories” [62], that performs inference over DISPONTE DLs. BUNDLE exploits an underlying reasoner such as Pellet [69] that returns explanations for queries. BUNDLE uses the inference techniques developed for probabilistic logic programs under the distribution semantics, in particular Binary Decision Diagrams (BDDs), for computing the probability of queries from a covering set of explanations. BUNDLE first finds explanations for the query and then encodes them in a BDD from which the probability can be computed in time linear in the size of the diagram.

BUNDLE’s worst case complexity is high since the number of explanations may grow exponentially while the computation of the probability through BDDs has #P-complexity in the number of explanations. Nevertheless, we applied BUNDLE to various real world datasets and we found that it is able to handle domains of significant size.

The present paper extends previous work [9,60–62] in various ways. With respect to the most recent work [62], the DISPONTE semantics is described in more detail with several examples; inference under this semantics is illustrated according to different techniques; we discuss how a lower bound on the probability of a query can be computed, with the quality of the bound monotonically increasing as more time for inference is allowed; BUNDLE is presented in more detail together with an extended description of Pellet’s functions and a discussion about its computational complexity. Moreover, we elaborated a detailed comparison with related work and performed an extensive experimental analysis of BUNDLE in order to investigate its performance in practice. In particular we present a more in-depth comparison with PRONTO, a system for inference in the probabilistic DL $\mathrm{P}\text{-}\mathcal{SHIQ}\mathrm{(}\mathbf{D}\mathrm{)}$ , and an analysis on the inference time trend with increasing sizes of the Tbox, the Abox and the set of probabilistic axioms.

The paper is organized as follows. Section 2 introduces Description Logics with particular reference to $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ while Section 3 discusses DISPONTE. Section 4 illustrates how to compute the probability of queries to DISPONTE DLs and Section 5 describes the BUNDLE algorithm. Section 6 discusses the complexity of reasoning and Section 7 related work. Section 8 shows the results of experiments with BUNDLE and, finally, Section 9 concludes the paper.

2. Description Logics

Description Logics are knowledge representation formalisms that possess nice computational properties such as decidability and/or low complexity, see [3,5] for excellent introductions. DLs are particularly useful for representing ontologies and have been adopted as the basis of the Semantic Web.

While DLs are a fragment of predicate logic, they are usually represented using a syntax based on concepts and roles. A concept corresponds to a set of individuals of the domain while a role corresponds to a set of couples of individuals of the domain. In order to illustrate DLs, we describe $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ as a prototype of expressive description logics. In the rest of the paper we use A, R and I to indicate atomic concepts, atomic roles and individuals, respectively. A role is either an atomic role $\mathit{R}\in \mathbf{R}$ or the inverse ${\mathit{R}}^{-}$ of an atomic role $\mathit{R}\in \mathbf{R}$ . We use ${\mathbf{R}}^{-}$ to denote the set of all inverses of roles in R. Concepts are defined as follows. Each $\mathit{A}\in \mathbf{A}$ , ⊥ and ⊤ are concepts and if $\mathit{a}\in \mathbf{I}$ , then $\{\mathit{a}\}$ is a concept called a nominal. If C, ${\mathit{C}}_1$ and ${\mathit{C}}_2$ are concepts and $\mathit{R}\in \mathbf{R}\cup R^{-}$ , then $\mathrm{(}{\mathit{C}}_1\sqcap {\mathit{C}}_2\mathrm{)}$ , $\mathrm{(}{\mathit{C}}_1\bigsqcup {\mathit{C}}_2\mathrm{)}$ and $\neg \mathit{C}$ are concepts, as well as $\exists \mathit{R}.\mathit{C}$ and $\forall \mathit{R}.\mathit{C}$ and $\ge \mathit{n}\mathit{R}$ and $\le \mathit{n}\mathit{R}$ for an integer $\mathit{n}\ge 0$ .

An RBox $\mathcal{R}$ consists of a finite set of transitivity axioms $\mathit{Trans}\mathrm{(}\mathit{R}\mathrm{)}$ , where $\mathit{R}\in \mathbf{R}$ , and role inclusion axioms $\mathit{R}⊑\mathit{S}$ , where $\mathit{R}\mathrm{,}\mathit{S}\in \mathbf{R}\cup {\mathbf{R}}^{-}$ . A TBox $\mathcal{T}$ is a finite set of concept inclusion axioms $\mathit{C}⊑\mathit{D}$ , where C and D are concepts. We use $\mathit{C}\equiv \mathit{D}$ to abbreviate $\mathit{C}⊑\mathit{D}$ and $\mathit{D}⊑\mathit{C}$ . An ABox $\mathcal{A}$ is a finite set of concept membership axioms $\mathit{a}:\mathit{C}$ , role membership axioms $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}:\mathit{R}$ , equality axioms $\mathit{a}=\mathit{b}$ and inequality axioms $\mathit{a}\ne \mathit{b}$ , where C is a concept, $\mathit{R}\in \mathbf{R}$ and $\mathit{a}\mathrm{,}\mathit{b}\in \mathbf{I}$ . A knowledge base $\mathcal{K}=\mathrm{(}\mathcal{T}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{A}\mathrm{)}$ consists of a TBox $\mathcal{T}$ , an RBox $\mathcal{R}$ and an ABox $\mathcal{A}$ .

A $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ KB $\mathcal{K}$ is assigned a semantics in terms of interpretations $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ where ${\mathrm{\Delta }}^{\mathcal{I}}$ is a non-empty domain and ${·}^{\mathcal{I}}$ is the interpretation function that assigns an element in ${\mathrm{\Delta }}^{\mathcal{I}}$ to each $\mathit{a}\in \mathbf{I}$ , a subset of ${\mathrm{\Delta }}^{\mathcal{I}}$ to each $\mathit{A}\in \mathbf{A}$ and a subset of ${\mathrm{\Delta }}^{\mathcal{I}}\times {\mathrm{\Delta }}^{\mathcal{I}}$ to each $\mathit{R}\in \mathbf{R}$ . The mapping ${·}^{\mathcal{I}}$ is extended to all concepts (where ${\mathit{R}}^{\mathcal{I}}\mathrm{(}\mathit{x}\mathrm{)}=\{\mathit{y}|\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in {\mathit{R}}^{\mathcal{I}}\}$ and $\mathrm{\#}\mathit{X}$ denotes the cardinality of the set X) as: $$\begin{array}{ccc}\hfill {\mathrm{(}{\mathit{R}}^{-}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & \{\mathrm{(}\mathit{y}\mathrm{,}\mathit{x}\mathrm{)}|\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in {\mathit{R}}^{\mathcal{I}}\}\hfill \\ \hfill {\top }^{\mathcal{I}}& \hfill =\hfill & {\mathrm{\Delta }}^{\mathcal{I}}\hfill \\ \hfill {\perp }^{\mathcal{I}}& \hfill =\hfill & \varnothing \hfill \\ \hfill {\{\mathit{a}\}}^{\mathcal{I}}& \hfill =\hfill & \{{\mathit{a}}^{\mathcal{I}}\}\hfill \\ \hfill {\mathrm{(}{\mathit{C}}_1\sqcap {\mathit{C}}_2\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & {\mathit{C}}_1^{\mathcal{I}}\cap {\mathit{C}}_2^{\mathcal{I}}\hfill \\ \hfill {\mathrm{(}{\mathit{C}}_1\bigsqcup {\mathit{C}}_2\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & {\mathit{C}}_1^{\mathcal{I}}\cup {\mathit{C}}_2^{\mathcal{I}}\hfill \\ \hfill {\mathrm{(}\neg \mathit{C}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & {\mathrm{\Delta }}^{\mathcal{I}}\setminus {\mathit{C}}^{\mathcal{I}}\hfill \\ \hfill {\mathrm{(}\forall \mathit{R}.\mathit{C}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & \{\mathit{x}\in {\mathrm{\Delta }}^{\mathcal{I}}|{\mathit{R}}^{\mathcal{I}}\mathrm{(}\mathit{x}\mathrm{)}\subseteq {\mathit{C}}^{\mathcal{I}}\}\hfill \\ \hfill {\mathrm{(}\exists \mathit{R}.\mathit{C}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & \{\mathit{x}\in {\mathrm{\Delta }}^{\mathcal{I}}|{\mathit{R}}^{\mathcal{I}}\mathrm{(}\mathit{x}\mathrm{)}\cap {\mathit{C}}^{\mathcal{I}}\ne \varnothing \}\hfill \\ \hfill {\mathrm{(}\ge \mathit{n}\mathit{R}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & \{\mathit{x}\in {\mathrm{\Delta }}^{\mathcal{I}}|\mathrm{\#}{\mathit{R}}^{\mathcal{I}}\mathrm{(}\mathit{x}\mathrm{)}\ge \mathit{n}\}\hfill \\ \hfill {\mathrm{(}\le \mathit{n}\mathit{R}\mathrm{)}}^{\mathcal{I}}& \hfill =\hfill & \{\mathit{x}\in {\mathrm{\Delta }}^{\mathcal{I}}|\mathrm{\#}{\mathit{R}}^{\mathcal{I}}\mathrm{(}\mathit{x}\mathrm{)}\le \mathit{n}\}\hfill \end{array}$$

$\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ adds to $\mathcal{SHOIN}$ datatype roles, i.e., roles that map an individual to an element of a datatype such as integers, floats, etc. Then new concept definitions involving datatype roles are added that mirror those involving roles introduced above. We also assume that we have predicates over the datatypes.

The satisfaction of an axiom E in an interpretation $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ , denoted by $\mathcal{I}\models \mathit{E}$ , is defined as follows: (1) $\mathcal{I}\models \mathit{Trans}\mathrm{(}\mathit{R}\mathrm{)}$ iff ${\mathit{R}}^{\mathcal{I}}$ is transitive, (2) $\mathcal{I}\models \mathit{R}⊑\mathit{S}$ iff ${\mathit{R}}^{\mathcal{I}}\subseteq {\mathit{S}}^{\mathcal{I}}$ , (3) $\mathcal{I}\models \mathit{C}⊑\mathit{D}$ iff ${\mathit{C}}^{\mathcal{I}}\subseteq {\mathit{D}}^{\mathcal{I}}$ , (4) $\mathcal{I}\models \mathit{a}:\mathit{C}$ iff ${\mathit{a}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$ , (5) $\mathcal{I}\models \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}:\mathit{R}$ iff $\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{,}{\mathit{b}}^{\mathcal{I}}\mathrm{)}\in {\mathit{R}}^{\mathcal{I}}$ , (6) $\mathcal{I}\models \mathit{a}=\mathit{b}$ iff ${\mathit{a}}^{\mathcal{I}}={\mathit{b}}^{\mathcal{I}}$ , (7) $\mathcal{I}\models \mathit{a}\ne \mathit{b}$ iff ${\mathit{a}}^{\mathcal{I}}\ne {\mathit{b}}^{\mathcal{I}}$ . $\mathcal{I}$ satisfies a set of axioms $\mathcal{E}$ , denoted by $\mathcal{I}\models \mathcal{E}$ , iff $\mathcal{I}\models \mathit{E}$ for all $\mathit{E}\in \mathcal{E}$ . An interpretation $\mathcal{I}$ satisfies a knowledge base $\mathcal{K}=\mathrm{(}\mathcal{T}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{A}\mathrm{)}$ , denoted $\mathcal{I}\models \mathcal{K}$ , iff $\mathcal{I}$ satisfies $\mathcal{T}$ , $\mathcal{R}$ and $\mathcal{A}$ . In this case we say that $\mathcal{I}$ is a model of  $\mathcal{K}$ .

A knowledge base $\mathcal{K}$ is satisfiable iff it has a model. An axiom E is entailed by $\mathcal{K}$ , denoted $\mathcal{K}\models \mathit{E}$ , iff every model of $\mathcal{K}$ satisfies also E. A concept C is satisfiable relative to $\mathcal{K}$ iff $\mathcal{K}$ has a model $\mathcal{I}$ such that ${\mathit{C}}^{\mathcal{I}}\ne \varnothing$ .

A DL is decidable if the problem of checking the satisfiability of a KB is decidable. In particular, $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ is decidable iff there are no number restrictions on non-simple roles. A role is non-simple iff it is transitive or it has transitive subroles.

A query over a KB is usually an axiom for which we want to test the entailment from the KB. The entailment test may be reduced to checking the unsatisfiability of a concept in the KB, i.e., the emptiness of the concept. For example, the entailment of the axiom $\mathit{C}⊑\mathit{D}$ may be tested by checking the unsatisfiability of the concept $\mathit{C}\sqcap \neg \mathit{D}$ .

3. The DISPONTE semantics for DLs

DISPONTE applies the distribution semantics [65] of probabilistic logic programming to DLs. A program following this semantics defines a probability distribution over normal logic programs called worlds. Then the distribution is extended to queries and the probability of a query is obtained by marginalizing the joint distribution of the query and the programs.

3.1. Syntax and intuition

In DISPONTE, a probabilistic knowledge base $\mathcal{K}$ is a set of certain axioms or probabilistic axioms. Certain axioms take the form of regular DL axioms. Probabilistic axioms take the form $$\mathit{p}::\mathit{E}$$(1) where p is a real number in $[0\mathrm{,}1]$ and E is a DL axiom.

The idea of DISPONTE is to associate independent Boolean random variables to the probabilistic axioms. By assigning values to every random variable we obtain a world, the set of axioms whose random variables are assigned the value 1.

Every formula obtained from a certain axiom is included in a world w. For each probabilistic axiom, we decide whether to include it or not in w. A world therefore is a non probabilistic KB that can be assigned a semantics in the usual way. A query is entailed by a world if it is true in every model of the world.

The probability p can be interpreted as an epistemic probability, i.e., as the degree of our belief in axiom E. For example, a probabilistic concept membership axiom

$$\mathit{p}::\mathit{a}:\mathit{C}$$

means that we have degree of belief p in $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ . The statement that Tweety flies with probability 0.9 can be expressed as

$$0.9::\mathit{tweety}:\mathit{Flies}$$

A probabilistic concept inclusion axiom of the form $$\mathit{p}::\mathit{C}⊑\mathit{D}$$(2) represents the fact that we believe in the truth of $\mathit{C}⊑\mathit{D}$ with probability p. For example, the axiom $$0.9::\mathit{Bird}⊑\mathit{Flies}$$(3) means that birds fly with a 90% probability.

3.2. Semantics

We follow the approach of [49] and first give some definitions. An atomic choice is a couple $\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}\mathit{k}\mathrm{)}$ where ${\mathit{E}}_{\mathit{i}}$ is the ith probabilistic axiom and $\mathit{k}\in \{0\mathrm{,}1\}$ . k indicates whether ${\mathit{E}}_{\mathit{i}}$ is chosen to be included in a world ( $\mathit{k}=1$ ) or not ( $\mathit{k}=0$ ). A set of atomic choices κ is consistent if only one decision is taken for each probabilistic axiom; we assume independence between the different choices. A composite choice κ is a consistent set of atomic choices. The probability of a composite choice κ is $\mathit{P}\mathrm{(}\mathit{\kappa }\mathrm{)}={\prod }_{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\in \mathit{\kappa }}{\mathit{p}}_{\mathit{i}}{\prod }_{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}0\mathrm{)}\in \mathit{\kappa }}\mathrm{(}1-{\mathit{p}}_{\mathit{i}}\mathrm{)}$ , where ${\mathit{p}}_{\mathit{i}}$ is the probability associated with axiom ${\mathit{E}}_{\mathit{i}}$ . A selection σ is a total composite choice, i.e., it contains an atomic choice $\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}\mathit{k}\mathrm{)}$ for every probabilistic axiom of the theory. A selection σ identifies a theory ${\mathit{w}}_{\mathit{\sigma }}$ called a world in this way: ${\mathit{w}}_{\mathit{\sigma }}=\mathcal{C}\cup \{{\mathit{E}}_{\mathit{i}}|\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\in \mathit{\sigma }\}$ where $\mathcal{C}$ is the set of certain axioms. Let us indicate with ${\mathcal{S}}_{\mathcal{K}}$ the set of all selections and with ${\mathcal{W}}_{\mathcal{K}}$ the set of all worlds. The probability of a world ${\mathit{w}}_{\mathit{\sigma }}$ is $\mathit{P}\mathrm{(}{\mathit{w}}_{\mathit{\sigma }}\mathrm{)}=\mathit{P}\mathrm{(}\mathit{\sigma }\mathrm{)}={\prod }_{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\in \mathit{\sigma }}{\mathit{p}}_{\mathit{i}}{\prod }_{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}0\mathrm{)}\in \mathit{\sigma }}\mathrm{(}1-{\mathit{p}}_{\mathit{i}}\mathrm{)}$ . $\mathit{P}\mathrm{(}{\mathit{w}}_{\mathit{\sigma }}\mathrm{)}$ is a probability distribution over worlds, i.e., ${\sum }_{\mathit{w}\in {\mathcal{W}}_{\mathcal{K}}}\mathit{P}\mathrm{(}\mathit{w}\mathrm{)}=1$ .

We can now assign probabilities to queries. Given a world w, the probability of a query Qis defined as $\mathit{P}\mathrm{(}\mathit{Q}|\mathit{w}\mathrm{)}=1$ if $\mathit{w}\models \mathit{Q}$ and 0 otherwise. The probability of a query can be obtained by marginalizing the joint probability of the query and the worlds: $$\begin{array}{rclr}\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}& =& \sum _{\mathit{w}\in {\mathcal{W}}_{\mathcal{K}}}\mathit{P}\mathrm{(}\mathit{Q}\mathrm{,}\mathit{w}\mathrm{)}& \text{(4)}\\ & =& \sum _{\mathit{w}\in {\mathcal{W}}_{\mathcal{K}}}\mathit{P}\mathrm{(}\mathit{Q}|\mathit{w}\mathrm{)}\mathit{P}\mathrm{(}\mathit{w}\mathrm{)}& \text{(5)}\\ & =& \sum _{\mathit{w}\in {\mathcal{W}}_{\mathcal{K}}:\mathit{w}\models \mathit{Q}}\mathit{P}\mathrm{(}\mathit{w}\mathrm{)}& \text{(6)}\end{array}$$ where (4) and (5) follow for the sum and product rule of the theory of probability respectively and (6) holds because $\mathit{P}\mathrm{(}\mathit{Q}|\mathit{w}\mathrm{)}=1$ if $\mathit{w}\models \mathit{Q}$ and 0 otherwise.

Example 1.

Consider the following KB, inspired by the people+pets ontology proposed in [43]: $$\begin{array}{lll}\hfill 0.5::& \exists \mathit{hasAnimal}.\mathit{Pet}⊑\mathit{NatureLover}& \hfill \text{(7)}\\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{fluffy}\mathrm{)}:\mathit{hasAnimal}& \hfill \text{(8)}\\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{tom}\mathrm{)}:\mathit{hasAnimal}& \hfill \text{(9)}\\ \hfill & \mathit{fluffy}:\mathit{Cat}& \hfill \text{(10)}\\ \hfill & \mathit{tom}:\mathit{Cat}& \hfill \text{(11)}\\ \hfill 0.6::& \mathit{Cat}⊑\mathit{Pet}& \hfill \text{(12)}\end{array}$$ The KB indicates that the individuals that own an animal which is a pet are nature lovers with a 50% probability and that $\mathit{kevin}$ has the animals $\mathit{fluffy}$ and $\mathit{tom}$ . Fluffy and $\mathit{tom}$ are cats and cats are pets with probability 60%. The KB has four possible worlds, corresponding to the selections: $$\begin{array}{c}\{\mathrm{(}\mathrm{(}\text{7}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{12}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{7}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{12}\mathrm{)}\mathrm{,}0\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{7}\mathrm{)}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{12}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{7}\mathrm{)}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{12}\mathrm{)}\mathrm{,}0\mathrm{)}\}\hfill \end{array}$$ and the query axiom $\mathit{Q}=\mathit{kevin}:\mathit{NatureLover}$ is true in the first of them, while in the remaining ones it is false. Each pair in the selections contains the axiom identifier and the value of its selector (k).

The probability of the query is $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=0.5·0.6=0.3$ .

Example 2.

Let us consider a slightly different knowledge base: $$\begin{array}{llll}\hfill & \exists \mathit{hasAnimal}.\mathit{Pet}⊑\mathit{NatureLover}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{fluffy}\mathrm{)}:\mathit{hasAnimal}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{tom}\mathrm{)}:\mathit{hasAnimal}& \hfill & \\ \hfill 0.4::& \mathit{fluffy}:\mathit{Cat}& \hfill \text{(13)}\\ \hfill 0.3::& \mathit{tom}:\mathit{Cat}& \hfill \text{(14)}\\ \hfill 0.6::& \mathit{Cat}⊑\mathit{Pet}& \hfill \text{(15)}\end{array}$$ Here individuals that own an animal which is a pet are surely nature lovers and $\mathit{kevin}$ has the animals $\mathit{fluffy}$ and $\mathit{tom}$ . Moreover, we believe in the fact that $\mathit{fluffy}$ and $\mathit{tom}$ are cats and that cats are pets with a certain probability.

This KB has eight worlds and the query axiom $\mathit{Q}=\mathit{kevin}:\mathit{NatureLover}$ is true in three of them, those corresponding to the following selections: $$\begin{array}{c}\{\mathrm{(}\mathrm{(}\text{13}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{14}\mathrm{)}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{15}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{13}\mathrm{)}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{14}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{15}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{13}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{14}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{15}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \end{array}$$ so the probability is $$\begin{array}{rcl}\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}& =& 0.4·0.7·0.6+0.6·0.3·0.6+0.4·0.3·0.6\\ & =& 0.348.\end{array}$$

Note that if the regular DL KB obtained by stripping the probabilistic annotations is inconsistent, there will be worlds that are inconsistent too. These worlds will entail the query trivially, as does the regular KB. A DISPONTE KB with inconsistent worlds should not be used to derive consequences, just as a regular DL KB that is inconsistent should not.

However, apparently contradictory probabilistic information is allowed. For example, the KB $$\begin{array}{llll}\hfill 0.9::& \mathit{Bird}⊑\mathit{Flies}& \hfill & \\ \hfill 0.1::& \mathit{tweety}:\mathit{Flies}& \hfill & \\ \hfill & \mathit{tweety}:\mathit{Bird}& \hfill & \end{array}$$ states that the probability of flying for a bird is 0.9 and the probability of flying for $\mathit{tweety}$ , a particular bird, is 0.1. The two probabilistic statements are considered as independent evidence for $\mathit{tweety}$ flying and are combined giving the probability 0.91 for the query $\mathit{tweety}:\mathit{Flies}$ . In fact, this KB has four worlds and $\mathit{tweety}:\mathit{Flies}$ is true in three of them, giving $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=0.9·0.1+0.9·0.9+0.1·0.1=0.91$ . Thus knowledge about instances of the domain may reinforce general knowledge and vice-versa.

Example 3.

The knowledge base $$\begin{array}{llll}\hfill & \mathit{kevin}:\forall \mathit{friend}.\mathit{Person}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{laura}\mathrm{)}:\mathit{friend}& \hfill & \\ \hfill & \mathrm{(}\mathit{laura}\mathrm{,}\mathit{diana}\mathrm{)}:\mathit{friend}& \hfill & \\ \hfill 0.4::& \mathit{Trans}\mathrm{(}\mathit{friend}\mathrm{)}& \hfill & \end{array}$$ means that all individuals in the friend relationship with $\mathit{kevin}$ are persons, that $\mathit{kevin}$ is a friend of $\mathit{laura}$ , that $\mathit{laura}$ is a friend of $\mathit{diana}$ and that given three individuals a, b and c, there is a 40% probability that if a is a friend of b and b is a friend of c then a is a friend of c. In particular, we have a 40% probability that, if $\mathit{kevin}$ is a friend of $\mathit{laura}$ and $\mathit{laura}$ is a friend of $\mathit{diana}$ , then $\mathit{kevin}$ is a friend of $\mathit{diana}$ . Since the first two are certain facts, then $\mathit{kevin}$ is a friend of $\mathit{diana}$ with a 40% probability and $\mathit{diana}$ is a person also with a 40% probability.

The final report of the W3C Uncertainty Reasoning for the World Wide Web Incubator Group [71] discusses the challenge of reasoning with uncertain information on the World Wide Web. Moreover, it also highglights several use cases for the representation of uncertainty: combining knowledge from multiple, untrusted sources; discovering and using services in the presence of uncertain information on the user requirements and the service descriptions; recommending items to users; extracting and annotating information from the web; automatically performing tasks for users such as making an appointment, and handling healthcare and life sciences information and knowledge.

By introducing probability in an expressive description logic, such as $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ that is one of the bases of OWL, we are able to tackle these problems as shown in the following example. Example 4.

Consider a KB similar to the one of Example 2 but where we have a single cat, $\mathit{fluffy}$ . Suppose the user has the knowledge $$\begin{array}{llll}\hfill & \exists \mathit{hasAnimal}.\mathit{Pet}⊑\mathit{NatureLover}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{fluffy}\mathrm{)}:\mathit{hasAnimal}& \hfill & \\ \hfill & \mathit{Cat}⊑\mathit{Pet}& \hfill & \end{array}$$ and there are two sources of information with different reliability that provide the information that $\mathit{fluffy}$ is a cat. On one source the user has a degree of belief of 0.4, i.e., he thinks it is correct with a 40% probability, while on the other source he has a degree of belief 0.3, i.e., he thinks it is correct with a 30% probability. The user can reason on this knowledge by adding the following statements to his KB: $$\begin{array}{lll}\hfill 0.4::& \mathit{fluffy}:\mathit{Cat}& \hfill \text{(16)}\\ \hfill 0.3::& \mathit{fluffy}:\mathit{Cat}& \hfill \text{(17)}\end{array}$$ The two statements represent independent evidence on $\mathit{fluffy}$ being a cat.

The query axiom $\mathit{Q}=\mathit{kevin}:\mathit{NatureLover}$ is true in 3 out of the 4 worlds, those corresponding to the selections: $$\begin{array}{c}\{\mathrm{(}\mathrm{(}\text{16}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{17}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{16}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{17}\mathrm{)}\mathrm{,}0\mathrm{)}\}\hfill \\ \{\mathrm{(}\mathrm{(}\text{16}\mathrm{)}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{17}\mathrm{)}\mathrm{,}1\mathrm{)}\}\hfill \end{array}$$ So $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=0.4·0.3+0.4·0.7+0.6·0.3=0.58$ . This is reasonable if the two sources can be considered as independent. In fact, the probability comes from the disjunction of two independent Boolean random variables with probabilities respectively 0.4 and 0.3: $$\begin{array}{rcll}\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}& =& \mathit{P}\mathrm{(}{\mathit{X}}_1\vee {\mathit{X}}_2\mathrm{)}& \\ & =& \mathit{P}\mathrm{(}{\mathit{X}}_1\mathrm{)}+\mathit{P}\mathrm{(}{\mathit{X}}_2\mathrm{)}-\mathit{P}\mathrm{(}{\mathit{X}}_1\wedge {\mathit{X}}_2\mathrm{)}& \\ & =& \mathit{P}\mathrm{(}{\mathit{X}}_1\mathrm{)}+\mathit{P}\mathrm{(}{\mathit{X}}_2\mathrm{)}-\mathit{P}\mathrm{(}{\mathit{X}}_1\mathrm{)}\mathit{P}\mathrm{(}{\mathit{X}}_2\mathrm{)}& \\ & =& 0.4+0.3-0.4·0.3=0.58& \end{array}$$

4. Inference

We propose an approach for performing inference over DISPONTE DLs in which we first find explanations for the given query and then compute the probability of the query from them. In order to discuss the approach, we first need to introduce some definitions.

A composite choice κ identifies a set of worlds ${\mathit{\omega }}_{\mathit{\kappa }}=\{{\mathit{w}}_{\mathit{\sigma }}|\mathit{\sigma }\in {\mathcal{S}}_{\mathcal{K}}\mathrm{,}\mathit{\sigma }\supseteq \mathit{\kappa }\}$ , the set of worlds whose selection is a superset of κ, i.e., the set of worlds “compatible” with κ. We define the set of worlds identified by a set of composite choices K as ${\mathit{\omega }}_{\mathit{K}}={\bigcup }_{\mathit{\kappa }\in \mathit{K}}{\mathit{\omega }}_{\mathit{\kappa }}$ .

A composite choice κ is an explanation for a query Q if Q is entailed by every world of ${\mathit{\omega }}_{\mathit{\kappa }}$ . A covering set of explanations for Q is a set of composite choices K such that every world ${\mathit{w}}_{\mathit{\sigma }}$ in which the query is true is included in ${\mathit{\omega }}_{\mathit{K}}$ .

Two composite choices ${\mathit{\kappa }}_1$ and ${\mathit{\kappa }}_2$ are incompatible if their union is inconsistent. For example, the composite choices ${\mathit{\kappa }}_1=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\}$ and ${\mathit{\kappa }}_2=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}0\mathrm{)}\}$ are incompatible where ${\mathit{E}}_{\mathit{i}}$ is a probabilistic axiom. A set K of composite choices is pairwise incompatible if for all ${\mathit{\kappa }}_1\in \mathit{K}\mathrm{,}{\mathit{\kappa }}_2\in \mathit{K}\mathrm{,}{\mathit{\kappa }}_1\ne {\mathit{\kappa }}_2$ implies ${\mathit{\kappa }}_1$ and ${\mathit{\kappa }}_2$ are incompatible. For example $$\mathit{K}=\{{\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\}$$(18) with $${\mathit{\kappa }}_1=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\}$$ and $${\mathit{\kappa }}_2=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{E}}_{\mathit{l}}\mathrm{,}1\mathrm{)}\}$$(19) is pairwise incompatible.

We define the probability of a pairwise incompatible set of composite choices K as $$\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}=\sum _{\mathit{\kappa }\in \mathit{K}}\mathit{P}\mathrm{(}\mathit{\kappa }\mathrm{)}$$(20) Two sets of composite choices ${\mathit{K}}_1$ and ${\mathit{K}}_2$ are equivalent if ${\mathit{\omega }}_{{\mathit{K}}_1}={\mathit{\omega }}_{{\mathit{K}}_2}$ , i.e., if they identify the same set of worlds. For example, K in (18) is equivalent to $${\mathit{K}}^{\prime }=\{{\mathit{\kappa }}_1^{\prime }\mathrm{,}{\mathit{\kappa }}_2^{\prime }\}$$(21) with $${\mathit{\kappa }}_1^{\prime }=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\}$$ and $${\mathit{\kappa }}_2^{\prime }=\{\mathrm{(}{\mathit{E}}_{\mathit{l}}\mathrm{,}1\mathrm{)}\}$$(22)

4.1. Inference with the splitting algorithm

If E is an axiom and κ is a composite choice such that $\mathit{\kappa }\cap \{\mathrm{(}\mathit{E}\mathrm{,}0\mathrm{)}\mathrm{,}\mathrm{(}\mathit{E}\mathrm{,}1\mathrm{)}\}=\varnothing$ , the split of κ on E is the set of composite choices ${\mathit{S}}_{\mathit{\kappa }\mathrm{,}\mathit{E}}=\{\mathit{\kappa }\cup \{\mathrm{(}\mathit{E}\mathrm{,}0\mathrm{)}\}\mathrm{,}\mathit{\kappa }\cup \{\mathrm{(}\mathit{E}\mathrm{,}1\mathrm{)}\}\}$ . It is easy to see that κ and ${\mathit{S}}_{\mathit{\kappa }\mathrm{,}\mathit{E}}$ identify the same set of possible worlds, i.e., that ${\mathit{\omega }}_{\mathit{\kappa }}={\mathit{\omega }}_{{\mathit{S}}_{\mathit{\kappa }\mathrm{,}\mathit{E}}}$ . For example, the split of ${\mathit{\kappa }}_2^{\prime }$ in (22) on ${\mathit{E}}_{\mathit{i}}$ contains ${\mathit{\kappa }}_2$ in (19) and $\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{E}}_{\mathit{l}}\mathrm{,}1\mathrm{)}\}$ .

Poole [49] proved the following result.

Fig. 1.

Splitting algorithm.

Theorem 1.

Given a finite set K of finite composite choices, there exists a finite set ${\mathit{K}}^{\prime }$ of pairwise incompatible finite composite choices such that K and ${\mathit{K}}^{\prime }$ are equivalent.

Proof

Given a finite set of finite composite choices K, there are two possibilities to form a new set ${\mathit{K}}^{\prime }$ of composite choices so that K and ${\mathit{K}}^{\prime }$ are equivalent:

removing dominated elements: if ${\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\in \mathit{K}$ and ${\mathit{\kappa }}_1\subset {\mathit{\kappa }}_2$ , let ${\mathit{K}}^{\prime }=\mathit{K}\setminus \{{\mathit{\kappa }}_2\}$ .

splitting elements: if ${\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\in \mathit{K}$ are compatible (and neither is a superset of the other), there is a $\mathrm{(}\mathit{E}\mathrm{,}\mathit{k}\mathrm{)}\in {\mathit{\kappa }}_1\setminus {\mathit{\kappa }}_2$ . We replace ${\mathit{\kappa }}_2$ by the split of ${\mathit{\kappa }}_2$ on E. Let ${\mathit{K}}^{\prime }=\mathit{K}\setminus \{{\mathit{\kappa }}_2\}\cup {\mathit{S}}_{{\mathit{\kappa }}_2\mathrm{,}\mathit{E}}$ .

In both cases ${\mathit{\omega }}_{\mathit{K}}={\mathit{\omega }}_{{\mathit{K}}^{\prime }}$ . If we repeat these two operations until neither is applicable we obtain a splitting algorithm (see Fig. 1) that terminates because K is a finite set of finite composite choices. The resulting set ${\mathit{K}}^{\prime }$ is pairwise incompatible and is equivalent to the original set. For example, the splitting algorithm applied to ${\mathit{K}}^{\prime }$ (21) can return K (18).  □

Theorem 2 ([47]).

If ${\mathit{K}}_1$ and ${\mathit{K}}_2$ are both pairwise incompatible finite sets of finite composite choices such that they are equivalent then $\mathit{P}\mathrm{(}{\mathit{K}}_1\mathrm{)}=\mathit{P}\mathrm{(}{\mathit{K}}_2\mathrm{)}$ .

For example, K in (18) and ${\mathit{K}}^{″}=\{{\mathit{\kappa }}_1^{″}\mathrm{,}{\mathit{\kappa }}_2^{″}\}$ with ${\mathit{\kappa }}_1^{″}=\{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{E}}_{\mathit{l}}\mathrm{,}0\mathrm{)}\}$ and ${\mathit{\kappa }}_2^{″}=\{\mathrm{(}{\mathit{E}}_{\mathit{l}}\mathrm{,}1\mathrm{)}\}$ are equivalent and are both pairwise incompatible. Their probabilities are $$\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}={\mathit{p}}_{\mathit{i}}+\mathrm{(}1-{\mathit{p}}_{\mathit{i}}\mathrm{)}{\mathit{p}}_{\mathit{l}}={\mathit{p}}_{\mathit{i}}+{\mathit{p}}_{\mathit{l}}-{\mathit{p}}_{\mathit{i}}{\mathit{p}}_{\mathit{l}}$$ and $$\mathit{P}\mathrm{(}{\mathit{K}}^{″}\mathrm{)}={\mathit{p}}_{\mathit{i}}\mathrm{(}1-{\mathit{p}}_{\mathit{l}}\mathrm{)}+{\mathit{p}}_{\mathit{l}}={\mathit{p}}_{\mathit{i}}+{\mathit{p}}_{\mathit{l}}-{\mathit{p}}_{\mathit{i}}{\mathit{p}}_{\mathit{l}}$$ Note that if we compute the probability of ${\mathit{K}}^{\prime }$ in (21) with formula (20) we would obtain ${\mathit{p}}_{\mathit{i}}+{\mathit{p}}_{\mathit{l}}$ which is different from the probabilities of K and ${\mathit{K}}^{″}$ above, even if ${\mathit{K}}^{\prime }$ is equivalent to K and ${\mathit{K}}^{″}$ , because ${\mathit{K}}^{\prime }$ is not pairwise incompatible.

We can thus define the probability $\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}$ of a generic set of composite choices K as $\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}=\mathit{P}\mathrm{(}{\mathit{K}}^{\prime }\mathrm{)}$ , where ${\mathit{K}}^{\prime }$ is a mutually incompatible set of composite choices that is equivalent to K, i.e., such that ${\mathit{\omega }}_{{\mathit{K}}^{\prime }}={\mathit{\omega }}_{\mathit{K}}$ . Given a query Q, the set ${\mathit{K}}_{\mathit{Q}}=\{\mathit{\sigma }|\mathit{\sigma }\in {\mathcal{S}}_{\mathcal{K}}\wedge {\mathit{w}}_{\mathit{\sigma }}\models \mathit{Q}\}$ is a set of pairwise incompatible composite choices. Since $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}={\sum }_{\mathit{\sigma }\in {\mathit{K}}_{\mathit{Q}}}\mathit{P}\mathrm{(}\mathit{\sigma }\mathrm{)}$ , then $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=\mathit{P}\mathrm{(}{\mathit{K}}_{\mathit{Q}}\mathrm{)}$ .

If ${\mathit{K}}^{\prime }$ is a set of explanations for Q that is covering, then ${\mathit{K}}^{\prime }$ and ${\mathit{K}}_{\mathit{Q}}$ are equivalent so $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=\mathit{P}\mathrm{(}{\mathit{K}}_{\mathit{Q}}\mathrm{)}=\mathit{P}\mathrm{(}{\mathit{K}}^{\prime }\mathrm{)}$ . Thus we do not have to generate all worlds where a query is true in order to compute its probability, finding a mutually incompatible covering set of explanations is enough. Moreover, an additional result is given by the following theorem.

Theorem 3.

Given two finite sets of finite composite choices ${\mathit{K}}_1$ and ${\mathit{K}}_2$ , if ${\mathit{K}}_1\subseteq {\mathit{K}}_2$ , then $\mathit{P}\mathrm{(}{\mathit{K}}_1\mathrm{)}\le \mathit{P}\mathrm{(}{\mathit{K}}_2\mathrm{)}$ .

Proof

Let ${\mathit{K}}_1^{\prime }$ be the result of the application of the splitting algorithm to ${\mathit{K}}_1$ . We can apply the same operations of the algorithm to ${\mathit{K}}_2$ obtaining $\mathit{K}={\mathit{K}}_1^{\prime }\cup {\mathit{K}}^{\prime }$ for a certain ${\mathit{K}}^{\prime }$ . At this point, we can continue applying the splitting algorithm. If there exists a $\mathit{\kappa }\in \mathit{K}$ and a ${\mathit{\kappa }}^{\prime }\in \mathit{K}$ such that ${\mathit{\kappa }}^{\prime }\subseteq \mathit{\kappa }$ , at least one of κ and ${\mathit{\kappa }}^{\prime }$ must not belong to ${\mathit{K}}_1^{\prime }$ , otherwise κ would have been removed when splitting ${\mathit{K}}_1^{\prime }$ . κ is removed from K while ${\mathit{\kappa }}^{\prime }$ remains. If there is a compatible couple ${\mathit{\kappa }}_1$ and ${\mathit{\kappa }}_2$ in K, we can assume that one of the two, say ${\mathit{\kappa }}_2$ , does not belong to ${\mathit{K}}_1^{\prime }$ , since otherwise it would have been split before. We add to K the split of ${\mathit{\kappa }}_2$ on an atomic choice in ${\mathit{\kappa }}_1$ but not in ${\mathit{\kappa }}_2$ .

Let ${\mathit{K}}_2^{\prime }$ be the results of the splitting algorithm so applied. ${\mathit{K}}_2^{\prime }$ is such that, for each element ${\mathit{\kappa }}_1$ of ${\mathit{K}}_1^{\prime }$ , ${\mathit{K}}_2^{\prime }$ contains an element ${\mathit{\kappa }}_2$ such that ${\mathit{\kappa }}_2\subseteq {\mathit{\kappa }}_1$ . Therefore, in the summation in (20), for each term in $\mathit{P}\mathrm{(}{\mathit{K}}_1^{\prime }\mathrm{)}$ there will be a term in $\mathit{P}\mathrm{(}{\mathit{K}}_2^{\prime }\mathrm{)}$ with a larger or equal value so $\mathit{P}\mathrm{(}{\mathit{K}}_1^{\prime }\mathrm{)}\le \mathit{P}\mathrm{(}{\mathit{K}}_2^{\prime }\mathrm{)}$ . □

Thus, if K is a finite set of finite explanations for a query Q but we don’t know if K contains all possible explanations for Q, i.e., we don’t know whether K is covering, then $\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}$ will be a lower bound of $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ . So we can compute progressively more accurate estimates from below of $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ by considering an increasing set of explanations. Only when K contains all possible explanations, then $\mathit{P}\mathrm{(}\mathit{K}\mathrm{)}=\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ .

The problem of computing the probability of a query can thus be reduced to that of finding a covering set of explanations K and then making it pairwise incompatible, so that the probability can be computed with the summation of (20). To obtain a pairwise incompatible set of explanations, the splitting algorithm can be applied.

4.2. Inference through Binary Decision Diagrams

As an alternative to the splitting algorithm, given a covering set of explanations K for a query Q, we can define the Disjunctive Normal Form (DNF) Boolean formula ${\mathit{f}}_{\mathit{K}}$ as $${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}=\underset{\mathit{\kappa }\in \mathit{K}}{\vee }\underset{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}1\mathrm{)}\in \mathit{\kappa }}{\wedge }{\mathit{X}}_{\mathit{i}}\underset{\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}0\mathrm{)}\in \mathit{\kappa }}{\wedge }\overline{{\mathit{X}}_{\mathit{i}}}$$(23) The variables $\mathbf{X}=\{{\mathit{X}}_{\mathit{i}}|\mathrm{(}{\mathit{E}}_{\mathit{i}}\mathrm{,}\mathit{k}\mathrm{)}\in \mathit{\kappa }\mathrm{,}\mathit{\kappa }\in \mathit{K}\}$ are independent Boolean random variables whose probability of being true is ${\mathit{p}}_{\mathit{i}}$ for the variable ${\mathit{X}}_{\mathit{i}}$ . The probability that ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ assumes value 1 is equal to the probability of Q. We can now apply knowledge compilation to the propositional formula ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ [15], i.e. translate it to a target language that allows answering queries in polynomial time. A target language that was found to give good performances is the one of Binary Decision Diagrams (BDD). From a BDD we can compute the probability of the query with a dynamic programming algorithm that is linear in the size of the BDD [50]. Riguzzi [54] showed that this approach is faster than the splitting algorithm.

A BDD for a function of Boolean variables is a rooted graph that has one level for each Boolean variable. A node n in a BDD has two children: one corresponding to the 1 value of the variable associated with the level of n, indicated with ${\mathit{child}}_1\mathrm{(}\mathit{n}\mathrm{)}$ , and one corresponding to the 0 value of the variable, indicated with ${\mathit{child}}_0\mathrm{(}\mathit{n}\mathrm{)}$ . When drawing BDDs, the 0-branch – the one going to ${\mathit{child}}_0\mathrm{(}\mathit{n}\mathrm{)}$ – is distinguished from the 1-branch by drawing it with a dashed line. The leaves store either 0 or 1.

BDDs can be built by combining simpler BDDs using Boolean operators. While building BDDs, simplification operations can be applied that delete or merge nodes. Merging is performed when the diagram contains two identical sub-diagrams, while deletion is performed when both arcs from a node point to the same node. In this way a reduced BDD is obtained, often with a much smaller number of nodes with respect to the original BDD. The size of the reduced BDD depends on the order of the variables: finding an optimal order is an NP-complete problem [10] and several heuristic techniques are used in practice by highly efficient software packages such as CUDD.1 ¹

Available at http://vlsi.colorado.edu/~fabio/CUDD/.

Alternative methods involve learning variable order from examples [20].

For instance, a BDD for the function $$\mathit{f}\mathrm{(}\mathbf{X}\mathrm{)}=\mathrm{(}{\mathit{X}}_1\wedge {\mathit{X}}_3\mathrm{)}\vee \mathrm{(}{\mathit{X}}_2\wedge {\mathit{X}}_3\mathrm{)}$$(24) is shown in Fig. 2.

Fig. 2.

BDD for function (24).

A BDD performs a Shannon expansion of the Boolean formula ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ , so that, if X is the variable associated with the root level of a BDD, the formula ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ can be represented as ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}=\mathit{X}\wedge {\mathit{f}}_{\mathit{K}}^{\mathit{X}}\mathrm{(}\mathbf{X}\mathrm{)}\vee \overline{\mathit{X}}\wedge {\mathit{f}}_{\mathit{K}}^{\overline{\mathit{X}}}\mathrm{(}\mathbf{X}\mathrm{)}$ where ${\mathit{f}}_{\mathit{K}}^{\mathit{X}}\mathrm{(}\mathbf{X}\mathrm{)}$ ( ${\mathit{f}}_{\mathit{K}}^{\overline{\mathit{X}}}\mathrm{(}\mathbf{X}\mathrm{)}$ ) is the formula obtained by ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ by setting X to 1 (0). Now the two disjuncts are pairwise exclusive and the probability of ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ can be computed as $\mathit{P}\mathrm{(}{\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}\mathrm{)}=\mathit{P}\mathrm{(}\mathit{X}\mathrm{)}\mathit{P}\mathrm{(}{\mathit{f}}_{\mathit{K}}^{\mathit{X}}\mathrm{(}\mathbf{X}\mathrm{)}\mathrm{)}+\mathrm{(}1-\mathit{P}\mathrm{(}\mathit{X}\mathrm{)}\mathrm{)}\mathit{P}\mathrm{(}{\mathit{f}}_{\mathit{K}}^{\overline{\mathit{X}}}\mathrm{(}\mathbf{X}\mathrm{)}\mathrm{)}$ . In other words, BDDs make the explanations pairwise incompatible. Figure 3 shows function Prob that implements the dynamic programming algorithm for computing the probability of a formula encoded as a BDD.

The function should also store the value of already visited nodes in a table so that, if a node is visited again, its probability can be retrieved from the table. For the sake of simplicity Fig. 3 does not show this optimization but it is fundamental to achieve linear cost in the number of nodes, as without it the cost of the function Prob would be proportional to $2^{\mathit{n}}$ where n is the number of Boolean variables.

Fig. 3.

Function that computes the probability of a formula encoded as a BDD, where $\mathit{value}\mathrm{(}\mathit{node}\mathrm{)}$ is 0 or 1 and $\mathit{v}\mathrm{(}\mathit{node}\mathrm{)}$ is the variable associated with $\mathit{node}$ .

Let us discuss inference on some examples.

Example 5.

Let us consider the KB of Example 2. A covering set of explanations for the query axiom $\mathit{Q}=\mathit{kevin}:\mathit{NatureLover}$ is $\mathit{K}=\{{\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\}$ where ${\mathit{\kappa }}_1=\{\mathrm{(}\mathrm{(}\text{13}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{15}\mathrm{)}\mathrm{,}1\mathrm{)}\}$ and ${\mathit{\kappa }}_2=\{\mathrm{(}\mathrm{(}\text{14}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{15}\mathrm{)}\mathrm{,}1\mathrm{)}\}$ . If we associate the random variables ${\mathit{X}}_1$ to (13), ${\mathit{X}}_2$ to (14) and ${\mathit{X}}_3$ to (15), ${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}$ is shown in (24) and the BDD associated with the set K of explanations is shown in Fig. 2. By applying the algorithm in Fig. 3 we get $$\begin{array}{rcll}\mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_3\mathrm{)}& =& 0.6·1+0.4·0=0.6& \\ \mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_2\mathrm{)}& =& 0.4·0.6+0.6·0=0.24& \\ \mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_1\mathrm{)}& =& 0.3·0.6+0.7·0.24=0.348& \end{array}$$ so $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=\mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_1\mathrm{)}=0.348$ which corresponds to the probability given by the semantics.

Example 6.

Let us consider a slightly different knowledge base: $$\begin{array}{llll}\hfill & \exists \mathit{hasAnimal}.\mathit{Pet}⊑\mathit{NatureLover}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{fluffy}\mathrm{)}:\mathit{hasAnimal}& \hfill & \\ \hfill & \mathrm{(}\mathit{kevin}\mathrm{,}\mathit{tom}\mathrm{)}:\mathit{hasAnimal}& \hfill & \\ \hfill 0.4::& \mathit{fluffy}:\mathit{Dog}& \hfill \text{(25)}\\ \hfill 0.3::& \mathit{tom}:\mathit{Cat}& \hfill \text{(26)}\\ \hfill 0.6::& \mathit{Cat}⊑\mathit{Pet}& \hfill \text{(27)}\\ \hfill 0.5::& \mathit{Dog}⊑\mathit{Pet}& \hfill \text{(28)}\end{array}$$ A covering set of explanations for the query axiom $\mathit{Q}=\mathit{kevin}:\mathit{NatureLover}$ is $\mathit{K}=\{{\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\}$ where ${\mathit{\kappa }}_1=\{\mathrm{(}\mathrm{(}\text{25}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{28}\mathrm{)}\mathrm{,}1\mathrm{)}\}$ and ${\mathit{\kappa }}_2=\{\mathrm{(}\mathrm{(}\text{26}\mathrm{)}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathrm{(}\text{27}\mathrm{)}\mathrm{,}1\mathrm{)}\}$ . If we associate the random variables ${\mathit{X}}_1$ to (25), ${\mathit{X}}_2$ to (26), ${\mathit{X}}_3$ to (27) and ${\mathit{X}}_4$ to (28), the BDD associated with the set K of explanations is shown in Fig. 4. By applying the algorithm in Fig. 3 we get $$\begin{array}{rcll}\mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_4\mathrm{)}& =& 0.6·1+0.4·0=0.6& \\ \mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_3\mathrm{)}& =& 0.3·0.6+0.7·0=0.18& \\ \mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_2\mathrm{)}& =& 0.5·1+0.5·0.18=0.59& \\ \mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_1\mathrm{)}& =& 0.4·0.59+0.6·0.18=0.344& \end{array}$$ so $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}=\mathrm{P}\mathrm{ROB}\mathrm{(}{\mathit{n}}_1\mathrm{)}=0.344$ .

Fig. 4.

BDD for Example 6.

5. BUNDLE

The BUNDLE algorithm computes the probability of queries from a probabilistic knowledge base that follows the DISPONTE semantics. It first finds a covering set of explanations for the query and then makes them pairwise incompatible by using BDDs. Finally, it computes the probability from the BDD by using function Prob in Fig. 3.

The problem of finding explanations for a query has been investigated by various authors [21,27,29,30]. Schlobach and Cornet [67] called it axiom pinpointing and considered it a non-standard reasoning service useful for tracing derivations and debugging ontologies. In particular, they define minimal axiom sets or MinAs for short.

Definition 1 (MinAs).

Let $\mathcal{K}$ be a KB and Q an axiom that follows from it, i.e., $\mathcal{K}\models \mathit{Q}$ . We call a set $\mathit{M}\subseteq \mathcal{K}$ a minimal axiom set or MinA for Q in $\mathcal{K}$ if $\mathit{M}\models \mathit{Q}$ and M is minimal w.r.t. set inclusion. The set of all possible MinAs is called All-MinAs( $\mathit{Q}\mathrm{,}\mathcal{K}$ ). The problem of enumerating all MinAs is called min-a-enum.

All-MinAs( $\mathit{Q}\mathrm{,}\mathcal{K}$ ) can be used to derive a covering set of explanations. min-a-enum can be solved either with reasoner dependent (glass-box) approaches or reasoner independent (black-box) approaches [30]. Glass-box approaches are built on existing tableau-based decision procedures and modify the internals of the reasoner. Black-box approaches use the DL reasoner solely as a subroutine and the internals of the reasoner do not need to be modified.

The techniques of [21,28–30] for axiom pinpointing have been integrated into the Pellet reasoner [69]. By default, Pellet solves min-a-enum with a hybrid glass/black-box approach: it finds a single MinA using a modified tableau algorithm and then finds all the other MinAs using a black box method (the hitting set tree algorithm). The method involves removing an axiom of the MinA from the KB and looking for alternative explanations. By repeating this process until the query is not entailed, the set of all explanations is found.

BUNDLE is based on Pellet and uses it for solving the min-a-enum problem. In the following, we first illustrate Pellet’s algorithm for solving min-a-enum and then we show the whole BUNDLE algorithm.

5.1. Axiom pinpointing in Pellet

Pellet exploits a tableau algorithm [68] that decides whether an axiom is entailed or not by a KB $\mathcal{K}$ by refutation: axiom E is entailed if $\neg \mathit{E}$ has no model in the KB. The algorithm works on completion graphs also called tableaux: they are ABoxes that can also be seen as graphs, where each node represents an individual a and is labeled with the set of concepts $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}$ it belongs to. Each edge $⟨\mathit{a}\mathrm{,}\mathit{b}⟩$ in the graph is labeled with the set of roles $\mathcal{L}\mathrm{(}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}$ to which the couple $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ belongs to. The algorithm starts from a tableau that contains the ABox of the KB and the negation of the axiom to be proved. For example, if the query is a membership one, $\mathit{a}:\mathit{C}$ , it adds $\neg \mathit{C}$ to the label of a. If we query for the emptyness (unsatisfiability) of a concept C, the algorithm adds a new anonymous node a to the tableau and adds C to the label of a. The axiom $\mathit{C}⊑\mathit{D}$ can be proved by showing that $\mathit{C}\sqcap \neg \mathit{D}$ is unsatisfiable. The algorithm repeatedly applies a set of consistency preserving tableau expansion rules until a clash (i.e., a contradiction) is detected or a clash-free graph is found to which no more rules are applicable.

In the following we describe the tableau algorithm used by Pellet for concept unsatisfiability, which checks if it is possible or not for a class to have any instances. Instance and subclass checking can be performed similarly. The algorithm is shown in Fig. 5.

Fig. 5.

Tableau algorithm executed by Pellet.

The rules used by Pellet to answer queries to $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ knowledge bases are shown in Fig. 8. Some of the rules are non-deterministic, i.e., they generate a finite set of tableaux. Thus the algorithm keeps a set of tableaux T. If a non-deterministic rule is applied to a graph G in T, then G is replaced by the resulting set of graphs. For example, if the disjunction $\mathit{C}\bigsqcup \mathit{D}$ is present in the label of a node, the rule $\to \bigsqcup$ generates two graphs, one in which C is added to the node label and the other in which D is added to the node label.

An $\mathit{event}$ during the execution of the algorithm can be [27]: 1) $\mathit{Add}\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}$ , the addition of a concept C to $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}$ ; 2) $\mathit{Add}\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}$ , the addition of a role R to $\mathcal{L}\mathrm{(}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}$ ; 3) $\mathit{Merge}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , the merging of the nodes a, b;4) $\ne \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , the addition of the inequality $\mathit{a}\ne \mathit{b}$ to the relation ≠; 5) $\mathit{Report}\mathrm{(}\mathit{g}\mathrm{)}$ , the detection of a clash g. We use $\mathcal{E}$ to denote the set of events recorded during the execution of the algorithm. A clash is either:

a couple $\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}$ where C and $\neg \mathit{C}$ are present in the label of node a, i.e. $\{\mathit{C}\mathrm{,}\neg \mathit{C}\}\subseteq \mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}$ ;

a couple $\mathrm{(}\mathit{Merge}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\ne \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{)}$ , where the events $\mathit{Merge}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ and $\ne \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ belong to $\mathcal{E}$ .

Each time a clash is detected in a completion graph G, the algorithm stops applying rules to G. Once every completion graph in T contains a clash or no more expansion rules can be applied to it, the algorithm terminates. If all the completion graphs in the final set T contain a clash, the algorithm returns unsatisfiable as no model can be found. Otherwise, any one clash-free completion graph in T represents a possible model for $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ and the algorithm returns satisfiable.

Each expansion rule updates as well a tracing function τ, which associates sets of axioms with events in the derivation. For example, $\mathit{\tau }\mathrm{(}\mathit{Add}\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{)}$ , ( $\mathit{\tau }\mathrm{(}\mathit{Add}\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}\mathrm{)}$ ) is the set of axioms needed to explain the event $\mathit{A}\mathit{d}\mathit{d}\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}$ ( $\mathit{Add}\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}$ ). For the sake of brevity, we define τ for couples (concept, individual) and (role, couple of individuals) as $\mathit{\tau }\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}=\mathit{\tau }\mathrm{(}\mathit{Add}\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{)}$ and $\mathit{\tau }\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}=\mathit{\tau }\mathrm{(}\mathit{Add}\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}\mathrm{)}$ respectively. The function τ is initialized as the empty set for all the elements of its domain except for $\mathit{\tau }\mathrm{(}\mathit{C}\mathrm{,}\mathit{a}\mathrm{)}$ and $\mathit{\tau }\mathrm{(}\mathit{R}\mathrm{,}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}$ to which the values $\{\mathit{a}:\mathit{C}\}$ and $\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}:\mathit{R}\}$ are assigned if $\mathit{a}:\mathit{C}$ and $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}:\mathit{R}$ are in the ABox respectively. The expansion rules (Fig. 8) add axioms to values of τ.

If ${\mathit{g}}_1\mathrm{,}\dots \mathrm{,}{\mathit{g}}_{\mathit{n}}$ are the clashes, one for each tableau G of the final set, the output of the algorithm Tableau is $\mathit{S}={\bigcup }_{\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{n}\}}\mathit{\tau }\mathrm{(}{\mathit{g}}_{\mathit{i}}\mathrm{)}\setminus \{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\}$ where a is the anonymous individual initially assigned to C. However, this set may be redundant because additional axioms may also be included in τ, e.g., during the $\to \le$ rule, where axioms responsible for each of the successor edges are considered [27]. Thus S is pruned using a black-box approach shown in Fig. 6 [27]. This algorithm executes a loop on S in which it removes one axiom from S in each iteration and checks whether the concept C turns satisfiable w.r.t. S, in which case the axiom is reinserted into S. The idea is that, if the concept turns satisfiable, we can conclude that the axiom extracted is responsible for the unsatisfiability and hence has to be inserted back into S. Vice-versa, if the concept still remains unsatisfiable, we can conclude that the axiom is irrelevant and can be removed from S. The process continues until all axioms in S have been tested and then returns S.

The algorithm for computing a single MinA, shown in Fig. 7, first executes Tableau and then BlackBoxPruning.

Fig. 6.

Black-Box pruning algorithm.

Fig. 7.

SingleMinA algorithm.

Fig. 8.

Pellet tableau expansion rules for $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ from [27].

The output S of SingleMinA is guaranteed to be a MinA, as established by the following theorem, where $\mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ stands for the set of MinAs in which C is unsatisfiable.

Theorem 4 ([27]).

Let C be an unsatisfiable concept w.r.t. $\mathcal{K}$ and let S be the output of the algorithm SingleMinA with input C and $\mathcal{K}$ , then $\mathit{S}\in \mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ .

SingleMinA returns a single MinA, i.e. a single explanation. To solve min-a-enum and find the remaining ones, Pellet exploits the hitting set algorithm [52].

Reiter considers a universal set U and a set $\mathit{CS}\subseteq \mathcal{P}\mathit{U}$ of conflict sets, where $\mathcal{P}$ denotes the powerset operator. The set $\mathit{H}\subseteq \mathit{U}$ is a hitting set for $\mathit{CS}$ if each ${\mathit{c}}_{\mathit{i}}\in \mathit{CS}$ contains at least one element of H, i.e. if ${\mathit{c}}_{\mathit{i}}\cap \mathit{H}\ne \varnothing$ for all $1\le \mathit{i}\le \mathit{n}$ (in other words, H ‘hits’ or intersects each set in $\mathit{CS}$ ). H is a minimal hitting set for $\mathit{CS}$ if H is a hitting set for $\mathit{CS}$ and no ${\mathit{H}}^{\prime }\subset \mathit{H}$ is a hitting set for $\mathit{C}\mathit{S}$ . The hitting set problem with input $\mathit{CS}$ , U is to compute all the minimal hitting sets for $\mathit{CS}$ . The idea here is that the explanations for unsatisfiability correspond to minimal conflict sets and an algorithm that generates minimal hitting sets can also be used to find all minimal conflict sets [27,30]. The universal set corresponds to the total set of axioms in the KB, and an explanation (for a particular concept unsatisfiability) corresponds to a single conflict set.

The algorithm constructs a labeled tree called Hitting Set Tree (HST) starting from a single explanation, the MinA S; then it removes each of the axioms in S individually, thereby creating new branches of the HST, and finds new explanations along these branches. The first step consists of initializing an HST $\mathbf{T}=\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{,}\mathcal{L}\mathrm{)}$ with S in the label of its root node, i.e. $\mathit{V}=\{{\mathit{v}}_0\}\mathrm{,}\mathit{E}=\varnothing \mathrm{,}\mathcal{L}\mathrm{(}{\mathit{v}}_0\mathrm{)}=\mathit{S}$ . Then it selects an arbitrary axiom E in S, generates a new node w with an empty label in the tree and a new edge $⟨{\mathit{v}}_0\mathrm{,}\mathit{w}⟩$ with axiom E in its label. Then, the algorithm invokes SingleMinA with arguments C and the knowledge base ${\mathcal{K}}^{\prime }=\mathcal{K}-\{\mathit{E}\}$ , to test the unsatisfiability of C w.r.t. ${\mathcal{K}}^{\prime }$ . If C is still unsatisfiable it obtains a new explanation for C and it labels w with this set. The algorithm repeats this process (removing an axiom from S and executing SingleMinA to add a new node) until the unsatisfiability test returns negative (the concept turns satisfiable): in that case the algorithm labels the new node with $\mathit{OK}$ and makes it a leaf. The algorithm also eliminates extraneous unsatisfiability tests based on previous results: once a path leading to a node labeled $\mathit{OK}$ is found, any superset of that path is guaranteed to be a hitting set as well, and thus no additional unsatisfiability test is needed for that path, as indicated by a X in the node label. When the HST is fully built, all leaves of the tree are labeled with $\mathit{OK}$ or X. The distinct non leaf nodes of the tree collectively represent the set $\mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ of the unsatisfiable concept. The algorithm is shown in Fig. 9. The correctness and completeness of the hitting set algorithm are given by the following theorem.

Theorem 5 ([27]).

Let C be a concept unsatisfiable in $\mathcal{K}$ and let $\mathrm{E}\mathrm{XP}\mathrm{HST}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ be the set of explanations returned by Pellet’s hitting set algorithm. Then $$\mathrm{E}\mathrm{XP}\mathrm{HST}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}=\mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}.$$

Pellet’s $\mathrm{E}\mathrm{XP}\mathrm{HST}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ can also take as input a maximum number of explanations to be generated. If the limit is reached during the execution of the hitting set algorithm, Pellet stops and returns the set of explanations found so far.

Fig. 9.

Hitting set tree algorithm.

5.2. Overall BUNDLE

The main algorithm, shown in Fig. 10, first builds a data structure $\mathit{PMap}$ that associates each probabilistic DL axiom ${\mathit{E}}_{\mathit{i}}$ with its probability ${\mathit{p}}_{\mathit{i}}$ . Then it uses Pellet’s $\mathrm{E}\mathrm{XP}\mathrm{HST}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$ function to compute the MinAs for the unsatisfiability of a concept C. These MinAs correspond to all conflict sets found by the Hitting Set Algorithm. BUNDLE exploits the version of this procedure in which we can specify the maximum number of explanations to be found.

Fig. 10.

Function Bundle: computation of the probability of an axiom C given the KB $\mathcal{K}$ .

Two data structures are initialized: $\mathit{VarAx}$ is an array that maintains the association between Boolean random variables (whose index is the array index) and couples (axiom, probability), and $\mathit{BDD}$ stores a BDD. $\mathit{BDD}$ is initialized to the zero Boolean function (lines 8–9).

Then BUNDLE performs two nested loops that build a BDD representing the set of explanations. To manipulate BDDs we used JavaBDD2 ²

Available at http://javabdd.sourceforge.net/

that is an interface to a number of underlying BDD manipulation packages. As the underlying package we used CUDD.

In the inner loop, BUNDLE generates the BDD for a single explanation, indicated as $\mathit{BDDE}$ , which is initialized to the one Boolean function (lines 11–25). The axioms of each MinA are considered one by one. If the axiom is certain, then the one Boolean function is stored in $\mathit{BDDA}$ (line 14). Otherwise, the value p associated with the axiom $\mathit{Ax}$ is extracted from $\mathit{PMap}$ . The axiomis searched for in $\mathit{VarAx}$ to see if it has already been assigned a random variable. If not, a cell is added to $\mathit{VarAx}$ to store the couple (line 19). At this point we know the couple position i in the array $\mathit{VarAx}$ , that is the index of its Boolean random variable ${\mathit{X}}_{\mathit{i}}$ . We obtain a BDD representing ${\mathit{X}}_{\mathit{i}}=1$ with BDDGetIthVar in $\mathit{BDDA}$ . $\mathit{BDDA}$ is finally conjoined with the current $\mathit{BDDE}$ to get the BDD representing a single explanation (line 24).

In the outermost loop, BUNDLE combines BDDs for different explanations through disjunction between $\mathit{BDD}$ and the current explanation $\mathit{BDDE}$ (line 26).

After the two cycles, function Prob of Fig. 3 is called over $\mathit{BDD}$ to return the probability of the query to the user.

We now prove BUNDLE correctness.

Theorem 6 (BUNDLE correctness).

Given a DISPONTE knowledge base $\mathcal{K}$ , a query Q and a limit $\mathit{maxEx}$ for the number of explanations to find, the probability returned by BUNDLE, $\mathrm{B}\mathrm{UNDLE}\mathrm{(}\mathcal{K}\mathrm{,}\mathit{Q}\mathrm{,}\mathit{maxEx}\mathrm{)}$ is:

a lower bound on $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ if a maximum number of explanations to compute is set, i.e., $\mathrm{B}\mathrm{UNDLE}\mathrm{(}\mathcal{K}\mathrm{,}\mathit{Q}\mathrm{,}\mathit{maxEx}\mathrm{)}\le \mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$

equal to $\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ , i.e., $\mathrm{B}\mathrm{UNDLE}\mathrm{(}\mathcal{K}\mathrm{,}\mathit{Q}\mathrm{,}\infty \mathrm{)}=\mathit{P}\mathrm{(}\mathit{Q}\mathrm{)}$ otherwise

Proof

Let K be $\mathrm{E}\mathrm{XP}\mathrm{HST}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{maxEx}\mathrm{)}$ . By Theorem 5 $$\mathit{K}\subseteq \mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$$ if a maximum number of explanations is set and $$\mathit{K}=\mathrm{A}\mathrm{LL}\text{-}\mathrm{M}\mathrm{IN}\mathrm{A}\mathrm{S}\mathrm{(}\mathit{C}\mathrm{,}\mathcal{K}\mathrm{)}$$ otherwise. Since BUNDLE computes $\mathit{P}\mathrm{(}{\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}\mathrm{)}$ for the Boolean function $${\mathit{f}}_{\mathit{K}}\mathrm{(}\mathbf{X}\mathrm{)}=\underset{\mathit{\kappa }\in \mathit{K}}{\vee }\underset{\mathrm{(}\mathit{F}\mathrm{,}1\mathrm{)}\in \mathit{\kappa }}{\wedge }{\mathit{X}}_{\mathit{F}}$$ the theorem holds.  □

Example 7.

Let us consider the KB presented in Example 5 and the query $\mathit{C}=\mathit{kevin}:\mathit{NatureLover}$ . Let us also consider the corresponding $\mathit{PMap}=\{\mathrm{(}\mathit{fluffy}:\mathit{Cat}\mathrm{,}0.4\mathrm{)}\mathrm{,}\mathrm{(}\mathit{tom}:\mathit{Cat}\mathrm{,}0.3\mathrm{)}\mathrm{,}\mathrm{(}\mathit{Cat}⊑\mathit{Pet}\mathrm{,}0.6\mathrm{)}\}$ , $\mathit{VarAx}=\varnothing$ and the covering set of explanations $\mathit{K}=\{{\mathit{\kappa }}_1\mathrm{,}{\mathit{\kappa }}_2\}$ where ${\mathit{\kappa }}_1=\{\mathrm{(}\mathit{fluffy}:\mathit{Cat}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathit{Cat}⊑\mathit{Pet}\mathrm{,}1\mathrm{)}\}$ and ${\mathit{\kappa }}_2=\{\mathrm{(}\mathit{tom}:\mathit{Cat}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}\mathit{Cat}⊑\mathit{Pet}\mathrm{,}1\mathrm{)}\}$ . Here we restrict explanations to contain only probabilistic axioms for the sake of simplicity.

At the start, BUNDLE initializes $\mathit{BDD}$ to the zero Boolean function and starts to loop over the explanations. It enters the inner loop considering the explanation ${\mathit{\kappa }}_1$ and initializing $\mathit{BDDE}$ to the one Boolean function. At this time $\mathit{VarAx}$ is empty, thus random variable ${\mathit{X}}_1$ is associated to $\mathrm{(}\mathit{fluffy}:\mathit{Cat}\mathrm{,}0.4\mathrm{)}$ by adding this pair to $\mathit{VarAx}$ in position 1. Function BDDGetIthVar returns a BDD in $\mathit{BDDA}$ that corresponds to the expression ${\mathit{X}}_1=1$ . Then $\mathit{BDDA}$ is combined with $\mathit{BDDE}$ using the and operator. Now, the computation continues by analyzing the second axiom of ${\mathit{\kappa }}_1$ . The axiom $\mathit{Cat}⊑\mathit{Pet}$ does not have a random variable associated with it yet, so the new variable ${\mathit{X}}_2$ is created and the pair $\mathrm{(}\mathit{Cat}⊑\mathit{Pet}\mathrm{,}0.6\mathrm{)}$ is added to $\mathit{VarAx}$ in position 2. $\mathit{BDDA}$ is then generated and combined with the $\mathit{BDDE}$ corresponding to the current explanation using the and operator. Now all the axioms in ${\mathit{\kappa }}_1$ have been considered, so the final $\mathit{BDDE}$ is combined with $\mathit{BDD}$ with the or operator.

Then, BUNDLE starts to consider ${\mathit{\kappa }}_2$ . $\mathit{BDDE}$ is set to one. The axiom $\mathit{Tom}:\mathit{Cat}$ does not appear in $\mathit{VarAx}$ so variable ${\mathit{X}}_3$ is associated to $\mathrm{(}\mathit{Tom}:\mathit{Cat}\mathrm{,}0.3\mathrm{)}$ and $\mathit{BDDA}$ , representing ${\mathit{X}}_3=1$ , is joined with $\mathit{BDDE}$ . The axiom $\mathit{Cat}⊑\mathit{Pet}$ is found in $\mathit{VarAx}$ in position 2, so the function BDDGetIthVar returns the BDD representing ${\mathit{X}}_2=1$ . Finally $\mathit{BDDA}$ is combined with the current $\mathit{BDDE}$ . $\mathit{BDDE}$ corresponding to the second explanation is completed so it is combined with $\mathit{BDD}$ obtaining the one shown in Fig. 2. Now BUNDLE calls function Prob which computes the probability and returns $\mathit{P}\mathrm{(}\mathit{C}\mathrm{)}=0.348$ .

6. Computational complexity

Jung and Lutz [26] considered the problem of computing the probability of conjunctive queries to probabilistic databases in the presence of an ontology. Probabilities can occur only in the ABox while the TBox is certain. In the case where each ABox assertion is associated with a Boolean random variable independent of all the others, they prove that only very simple conjunctive queries can be answered in PTime, while most queries are #P-hard when the ontology is a DL-Lite TBox and even when the ontology is an $\mathcal{E}\mathcal{L}\mathcal{I}$ TBox.

The class #P [72] describes counting problems associated with decision problems in NP. More formally, #P is the class of function problems of the form “compute $\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}$ ”, where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. A prototypical #P problem is the one of computing the number of satisfying assignments of a CNF Boolean formula. #P problems were shown very hard. First, a #P problem must be at least as hard as the corresponding NP problem. Second, [70] showed that a polynomial-time machine with a #P oracle ( ${\mathrm{P}}^{\mathrm{\#P}}$ ) can solve all problems in PH, the entire polynomial hierarchy.

The setting considered by [26] is subsumed by DISPONTE as it is equivalent to having probabilistic axioms only in the ABox of a DISPONTE KB. So the complexity result provides a lower bound for DISPONTE.

In order to investigate the complexity of BUNDLE, we can consider the two problems that it solves for answering a query. The first one is axiom pinpointing. Its computational complexity has been studied in a number of works [44–46]. Baader et al. [4] showed that there can be exponentially many MinAs for a very simple DL that allows only concept intersection.

Example 8.

Given an integer $\mathit{n}\ge 1$ , consider the TBox $${\mathcal{T}}_{\mathit{n}}=\{{\mathit{B}}_{\mathit{i}-1}⊑{\mathit{P}}_{\mathit{i}}\sqcap {\mathit{Q}}_{\mathit{i}}\mathrm{,}{\mathit{P}}_{\mathit{i}}⊑{\mathit{B}}_{\mathit{i}}\mathrm{,}{\mathit{Q}}_{\mathit{i}}⊑{\mathit{B}}_{\mathit{i}}|1\le \mathit{i}\le \mathit{n}\}$$ The size of ${\mathcal{T}}_{\mathit{n}}$ is linear in n and ${\mathcal{T}}_{\mathit{n}}\models {\mathit{B}}_0⊑{\mathit{B}}_{\mathit{n}}$ . There are $2^{\mathit{n}}$ MinAs for ${\mathit{B}}_0⊑{\mathit{B}}_{\mathit{n}}$ since, for each $\mathit{i}\mathrm{,}1\le \mathit{i}\le \mathit{n}$ , it is enough to have ${\mathit{P}}_{\mathit{i}}⊑{\mathit{B}}_{\mathit{i}}$ or ${\mathit{Q}}_{\mathit{i}}⊑{\mathit{B}}_{\mathit{i}}$ in the set.

Thus the number of explanations for $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ may be even larger. Given this fact, we do not consider complexity with respect to the input only. We say an algorithm runs in output polynomial time [25] if it computes all the output in time polynomial in the overall size of the input and the output. Corollary 15 in [46] shows that min-a-enum cannot be solved in output polynomial time for $\mathit{DL}\text{-}{\mathit{Lite}}_{\mathit{bool}}$ TBoxes unless $\mathit{P}=\mathit{NP}$ . Since $\mathit{DL}\text{-}{\mathit{Lite}}_{\mathit{bool}}$ is a sublogic of $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ , this result also holds for $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ .

The second problem to be solved is computing the probability of a query, that can be seen as computing the probability of a sum-of-products, as explained below.

Definition 2 (Sum-of-products).

Given a Boolean expression S in disjunctive normal form (DNF), or a sum-of-products, in the variables $\{{\mathit{V}}_1\mathrm{,}\dots \mathrm{,}{\mathit{V}}_{\mathit{n}}\}$ and $\mathit{P}\mathrm{(}{\mathit{V}}_{\mathit{i}}\mathrm{)}$ , the probability that ${\mathit{V}}_{\mathit{i}}$ is true with $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ ,compute the probability $\mathit{P}\mathrm{(}\mathit{S}\mathrm{)}$ of S, assuming all variables are independent.

sum-of-products was shown to be #P-hard [see e.g. 51]. Given that the input of the sum-of-products problem is of at least exponential size in the worst case, this means that computing the probability of an axiom from a $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ knowledge base is intractable.

However, the algorithms that have been proposed for solving the two problems were shown to be able to work on inputs of real world size. For example, all MinAs have been found for various entailments over many real world ontologies within a few seconds [27,30]. As regards the sum-of-products problem, algorithms based on BDDs were able to solve problems with hundreds of thousands of variables (see e.g. the works on inference on probabilistic logic programs [31,50,53–59]). Also methods for weighted model counting [12,64] can be used to solve the sum-of-products problem.

Moreover, Section 8 shows that in practice we can compute the probability of entailments on KBs of real-world size with BUNDLE, too.

7. Related work

Bacchus [6] and Halpern [22] discuss first-order logics of probability and distinguish statistical statements from statements about degrees of belief. Halpern [22] presents two examples: the probability that a randomly chosen bird flies is 0.9 and the probability that Tweety (a particular bird) flies is 0.9. The first statement captures statistical information about the world while the second captures a degree of belief. In order to express the second type of statement, called a “Type 2” statement, Halpern proposes the notation $\mathit{w}\mathrm{(}\mathit{Flies}\mathrm{(}\mathit{tweety}\mathrm{)}\mathrm{)}=0.9$ , where the function w is used to indicate the probability, while in order to express the first, called a “Type 1” statement, he proposes the notation ${\mathit{w}}_{\mathit{x}}\mathrm{(}\mathit{Flies}\mathrm{(}\mathit{x}\mathrm{)}\wedge \mathit{Bird}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}=0.9{\mathit{w}}_{\mathit{x}}\mathrm{(}\mathit{Bird}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}$ . The latter formula can be read as: given a randomly chosen x in the domain, if x is a bird, the probability that x flies is 0.9, or the conditional probability that x flies given that it is a bird is 0.9. DISPONTE allows to define only “Type 2” statements since the probability associated with an axiom represents the degree of belief in that axiom as a whole.

Lutz and Schröder [41] proposed Prob- $\mathcal{ALC}$ that is derived directly from Halpern’s probabilistic first order logic and, as DISPONTE, considers only “Type 2” statements. They do so by adopting a possible world semantics and allowing concept expressions of the form ${\mathit{P}}_{\ge \mathit{n}}\mathit{C}$ and $\exists {\mathit{P}}_{\ge \mathit{n}}\mathit{R}.\mathit{C}$ in the language, the first expressing the set of individuals that belong to C with probability greater than n and the second the set of individuals a connected to at least another individual b of C by role R such that the probability of $\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ is greater than n. Moreover, the ABox may contain expressions of the form ${\mathit{P}}_{\ge \mathit{n}}\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ and ${\mathit{P}}_{\ge \mathit{n}}\mathit{R}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ directly expressing degrees of belief, together with ${\mathit{P}}_{\ge \mathit{n}}\mathcal{A}$ where $\mathcal{A}$ is an ABox. Prob- $\mathcal{ALC}$ is 2-EXPTIME-hard even when probability values are restricted to 0 and 1. Prob- $\mathcal{ALC}$ is complementary to DISPONTE $\mathcal{ALC}$ as it allows new concept and assertion expressions while DISPONTE allows probabilistic axioms.

Jung and Lutz [26] presented an approach for querying probabilistic databases in the presence of an OWL2 QL ontology. Each assertion is assumed to be stored in a database and associated with probabilistic events. All atomic events are assumed to be probabilistically independent, resulting in a semantics very similar to the distribution semantics. The authors are interested in computing the answer probabilities to conjunctive queries. Probabilities can occur only in the data, but neither in the ontology nor in the query. Two types of ABoxes are considered: a general one where events are Boolean combinations of atomic events, and a restricted one, where each assertion is associated with a distinct atomic event. For Boolean conjunctive queries, the latter setting is subsumed by DISPONTE. Only very simple conjunctive queries in the latter setting can be answered in PTime, while most queries are #P-hard. The authors underline the general interest and usefulness of the approach for a wide range of applications including the management of data extracted from the web, machine translation, and dealing with data that arise from sensor networks.

Heinsohn [23] proposed an extension of the description logic $\mathcal{ALC}$ that is able to express statistical information on the terminological knowledge such as partial concept overlapping. Similarly, Koller et al. [35] presented a probabilistic description logic based on Bayesian networks that deals with statistical terminological knowledge. Both Heinsohn and Koller et al. do not allow probabilistic assertional knowledge about concept and role instances. Jaeger [24] 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 “Type 2” statements as DISPONTE.

Ding and Peng [17] proposed a probabilistic extension of OWL that admits a translation into Bayesian networks. The semantics defines a probability distribution $\mathit{P}\mathrm{(}\mathit{a}\mathrm{)}$ over individuals, i.e. ${\sum }_{\mathit{a}}\mathit{P}\mathrm{(}\mathit{a}\mathrm{)}=1$ , and assigns a probability to a class C as $\mathit{P}\mathrm{(}\mathit{C}\mathrm{)}={\sum }_{\mathit{a}\in \mathit{C}}\mathit{P}\mathrm{(}\mathit{a}\mathrm{)}$ , while we assign a probability distribution to worlds. PR-OWL [11,13] is a probabilistic extension to OWL that consists of a set of classes, subclasses and properties that collectively form a framework for building probabilistic ontologies. It allows to use the first-order probabilistic logic MEBN [36] for representing uncertainty in ontologies.

DISPONTE differs from [23,24,35] because it provides a unified framework for representing different types of probabilistic knowledge: from assertional to terminological degree of belief knowledge.

DISPONTE differs from [17] because it specifies a distribution over worlds rather than individuals and from [11,13] because it does not resort to a full fledged first-order probabilistic language, allowing the reuse of inference technology from DLs.

Luna et al. [40] proposed an extension of $\mathcal{ALC}$ , called $\mathrm{CR}\mathcal{ALC}$ , that adopts an interpretation-based semantics. $\mathrm{CR}\mathcal{ALC}$ allows statistical axioms of the form $\mathit{P}\mathrm{(}\mathit{C}|\mathit{D}\mathrm{)}=\mathit{\alpha }$ , which means that for any element x in the domain $\mathcal{D}$ , the probability that x is in C given that it is in D is α, and of the form $\mathit{P}\mathrm{(}\mathit{R}\mathrm{)}=\mathit{\beta }$ , which means that for each couple of elements x and y in $\mathcal{D}$ , the probability that x is linked to y by the role R is β. The semantics of $\mathrm{CR}\mathcal{ALC}$ is based on probability measures over the space of interpretations with a fixed domain. $\mathrm{CR}\mathcal{ALC}$ allows to express “Type 1” knowledge but not “Type 2”. A $\mathrm{CR}\mathcal{ALC}$ KB $\mathcal{K}$ can be represented as a directed acyclic graph $\mathit{G}\mathrm{(}\mathcal{K}\mathrm{)}$ in which a node represents a concept or a role and the edges represent the relations between them: if a concept C directly uses concept D, then D is a parent of C in $\mathit{G}\mathrm{(}\mathcal{K}\mathrm{)}$ . Moreover, each restriction $\exists \mathit{R}.\mathit{C}$ and $\forall \mathit{R}.\mathit{C}$ is added as a node to $\mathit{G}\mathrm{(}\mathcal{K}\mathrm{)}$ . $\mathit{G}\mathrm{(}\mathcal{K}\mathrm{)}$ contains an edge from R to each restriction directly using it and from each restriction to the concept C appearing in it. $\mathit{G}\mathrm{(}\mathcal{K}\mathrm{)}$ is a template for generating, given the domain $\mathcal{D}$ , a ground graph in which each node represents an instantiated logical atom $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ or $\mathit{R}\mathrm{(}\mathit{a}.\mathit{b}\mathrm{)}$ . Inference can then be performed by a first order loopy belief propagation algorithm on the ground graph.

A different approach to the combination of DLs with probability is taken in [18,38,39]. The logic proposed in these papers is called $\mathrm{P}\text{-}\mathcal{SHIQ}\mathrm{(}\mathbf{D}\mathrm{)}$ and allows both terminological probabilistic knowledge as well as assertional probabilistic knowledge about instances of concepts and roles. Terminological probabilistic knowledge is expressed using conditional constraints of the form $\mathrm{(}\mathit{D}|\mathit{C}\mathrm{)}[\mathit{l}\mathrm{,}\mathit{u}]$ that informally mean “generally, if an object belongs to C, then it belongs to D with a probability in $[\mathit{l}\mathrm{,}\mathit{u}]$ ”. PRONTO [32,34] is a system that performs inference under this semantics. Similarly to [24], 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 [37]. These works are based on Nilsson’s probabilistic logic [42], where a probabilistic interpretation $\mathit{Pr}$ defines a probability distribution over the set of interpretations $\mathit{Int}$ . The probability of a logical formula F according to $\mathit{Pr}$ , denoted $\mathit{Pr}\mathrm{(}\mathit{F}\mathrm{)}$ , is the sum of all $\mathit{P}\mathit{r}\mathrm{(}\mathit{I}\mathrm{)}$ such that $\mathit{I}\in \mathit{Int}$ and $\mathit{I}\models \mathit{F}$ . A probabilistic knowledge base $\mathcal{K}$ is a set of probabilistic formulas of the form $\mathit{F}\ge \mathit{p}$ . A probabilistic interpretation $\mathit{Pr}$ satisfies $\mathit{F}\ge \mathit{p}$ iff $\mathit{Pr}\mathrm{(}\mathit{F}\mathrm{)}\ge \mathit{p}$ . $\mathit{Pr}$ satisfies $\mathcal{K}$ , or $\mathit{Pr}$ is a model of $\mathcal{K}$ , iff $\mathit{Pr}$ satisfies all $\mathit{F}\ge \mathit{p}\in \mathcal{K}$ . $\mathit{Pr}\mathrm{(}\mathit{F}\mathrm{)}\ge \mathit{p}$ is a tight logical consequence of $\mathcal{K}$ iff p is the infimum of $\mathit{Pr}\mathrm{(}\mathit{F}\mathrm{)}$ in the set of all models $\mathit{Pr}$ of $\mathcal{K}$ . Computing tight logical consequences from probabilistic knowledge bases can be done by solving a linear optimization problem.

Nilsson’s probabilistic logic differs from the distribution semantics: while the first considers sets of distributions, the latter computes a single distribution over possible worlds. Nilsson’s logic allows different conclusions: consider a DISPONTE KB composed of the axioms $0.4::\mathit{a}:\mathit{C}$ and $0.5::\mathit{b}:\mathit{C}$ and a probabilistic theory composed of $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\ge 0.4$ and $\mathit{C}\mathrm{(}\mathit{b}\mathrm{)}\ge 0.5$ ; DISPONTE allows to say that $\mathit{P}\mathrm{(}\mathit{a}:\mathit{C}\vee \mathit{b}:\mathit{C}\mathrm{)}=0.7$ , while with Nilsson’s logic the lowest p such that $\mathit{P}\mathit{r}\mathrm{(}\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\vee \mathit{C}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}\ge \mathit{p}$ holds is 0.5. This is due to the fact that, while in Nilsson’s logic no assumption about the independence of the statements is made, in the distribution semantics the probabilistic axioms are considered as independent. While independencies can be encoded in Nilsson’s logic by carefully choosing the values of the parameters, reading off the independencies from the theories becomes more difficult.

The assumption of independence of probabilistic axioms does not restrict expressiveness as one can specify any joint probability distribution over the logical ground atoms, possibly introducing new atoms if needed. This is testified by the fact that Bayesian networks can be encoded in probabilistic logic programs under the distribution semantics [74] and by the applications of the distribution semantics to a wide variety of domains [7,50,66].

Fig. 11.

Bayesian network.

For example, the Bayesian network in Fig. 11 can be encoded with the following ProbLog program burglary:0.1. earthquake:0.2. alarm :- burglary,earthquake. alarm :- burglary,\+ earthquake,al_tf. alarm :- \+ burglary,earthquake,al_ft. alarm :- \+ burglary,\+ earthquake,al_ff. al_tf:0.8. al_ft:0.8. al_ff:0.1. where an additional probabilistic fact has been added for each row of the conditional probability table for alarm (excluding the first that models a deterministic dependency).

Other approaches, such as [14,19], combine a lightweight ontology language, DL-Lite and Datalog $+\mathrm{/}-$ respectively, with graphical models, Bayesian networks and Markov networks respectively. In both cases, a KB is composed of a set of annotated axioms and a graphical model. The annotations are sets of assignments of random variables from the graphical model. The semantics is assigned by considering the possible worlds of the graphical model and by stating that an axiom holds in a possible world if the assignments in its annotation hold. The probability of a conclusion is then the sum of the probabilities of the possible worlds where the conclusion holds. Our approach represents a special case of these in which each probabilistic axiom is annotated with a single random variable and the graphical model encodes independence among the random variables. This special case is of interest as inference technology from DLs can be directly employed.

8. Experiments

In order to test the performance of BUNDLE we performed several experiments.

8.1. Comparison with PRONTO

We compared BUNDLE with PRONTO by running queries w.r.t. increasingly complex ontologies. The experiments have been performed on Linux machines with a 3.10 GHz Intel Xeon E5-2687W with 2GB memory allotted to Java.

In the first experiment we generated the test ontologies by randomly sampling axioms from a large probabilistic ontology that models breast cancer risk assessment (BRCA) as shown in [33]. The main idea behind the design of the ontology was to reduce risk assessment to probabilistic entailment in $\mathrm{P}\text{-}\mathcal{SHIQ}\mathrm{(}\mathbf{D}\mathrm{)}$ . The BRCA ontology contains a certain part and a probabilistic part. The tests were defined by randomly sampling axioms from the probabilistic part of this ontology which were then added to the certain part. So each sample is a probabilistic KB with the full certain part of the BRCA ontology and a subset of the probabilistic constraints. We varied the number of these constraints from 9 to 15, and, for each number, we generated 100 different consistent ontologies.

In order to generate a query, an individual a is added to the ontology: a is randomly assigned to each class that appears in the sampled conditional constraints with probability 0.6. If the class is composite, as for example PostmenopausalWomanTakingTestosterone, a is assigned to the component classes rather than to the composite one. In the example above, a will be added to PostmenopausalWoman and WomanTakingTestosterone. The ontologies were translated into DISPONTE by replacing each constraint $\mathrm{(}\mathit{D}|\mathit{C}\mathrm{)}[\mathit{l}\mathrm{,}\mathit{u}]$ with the axiom $\mathit{u}::\mathit{C}⊑\mathit{D}$ . For each ontology, we performed the query $\mathit{a}:\mathit{C}$ where the class C is randomly selected among those that represent women under increased and lifetime risk such as WomanUnderLifetimeBRCRisk and WomanUnderStronglyIncreasedBRCRisk. We then applied both BUNDLE and PRONTO to each generated test and we measured the execution time for inference and the memory used. Figure 12(a) shows the execution time averaged over the 100 KBs as a function of the number of probabilistic axioms and, similarly, Fig. 12(b) shows the average amount of memory used. As one can see, inference times are similar for small knowledge bases, while the difference between the two reasoners rapidly increases for larger knowledge bases. The memory usage for BUNDLE is always less than 53% than PRONTO.

Fig. 12.

Comparison between BUNDLE and PRONTO on the BRCA KB.

Table 1

Average execution time for the queries to the Cell, Teleost and NCI KBs and number of queries terminated with a time-out (TO). The first column reports the expressiveness of each KB and the size of the non-probabilistic TBox

Dataset & Infos		Size of the Probabilistic TBox
				0	250	500	750	1,000
Cell $\mathcal{ALE}+$ , 1,263 TBox axioms	runtime (s)	0.76	2.84	3.88	3.94	4.53
	TO	0	28	39	50	55
Teleost $\mathcal{ALEI}+$ , 3,406 TBox axioms	runtime (s)	2.11	8.87	31.80	33.82	36.33
	TO	0	7	32	32	44
NCI $\mathcal{ALE}+$ , 5,423 TBox axioms	runtime (s)	3.02	11.37	11.37	16.37	24.90
	TO	0	1	24	23	36

A second test was performed over larger KBs, following the method of [34]. We considered three different datasets: an extract from the Cell3 ³

http://cellontology.org/

ontology, an extract from the NCI Thesaurus4 ⁴

http://ncit.nci.nih.gov/

and an extract from the Teleost_anatomy5 ⁵

http://phenoscape.org/wiki/Teleost_Anatomy_Ontology

ontology. The Cell ontology represents cell types of the prokaryotic, fungal, and eukaryotic organisms. The NCI ontology is an extract from the NCI Thesaurus that describes human anatomy. The Teleost_anatomy (Teleost for short) ontology is a multi-species anatomy ontology for teleost fishes.

For each of these KBs, we considered the versions of increasing size used by [34]: they add 250, 500, 750 and 1,000 new probabilistic conditional constraints to the publicly available non-probabilistic version of each ontology. We converted these KBs into DISPONTE in the same way as for the BRCA ontology and we created a set of 100 different random subclass queries for each KB. For generating the queries we built the hierarchy of each KB and we randomly selected two classes connected in the hierarchy, so that each query had at least one explanation. We imposed a time limit of 5 minutes for BUNDLE to answer each query. If this limit is reached, BUNDLE’s answer is “time-out”.

In Table 1 we report, for each version of the datasets, the average execution time and the number of queries that terminated with a time-out (TO) for BUNDLE. The averages are computed on the queries that did not end with a time-out. In addition, for each KB we report its expressiveness and its number of non-probabilistic TBox axioms. In all these cases, PRONTO terminates with an out-of-memory error.

As can be seen, BUNDLE can manage larger KBs than PRONTO due to the lower amount of memory needed, as confirmed by the previous tests on BRCA. Moreover, BUNDLE answers most queries in a few seconds. However, some queries have a very high complexity that causes BUNDLE to reach the time-out, confirming the complexity results. In these cases, since the time-out is reached during the computation of the explanations, limiting the number of explanations is necessary, obtaining a lower bound on the probability that becomes tighter as more explanations are allowed.

8.2. Tests with not entailed queries

In a further test we investigated cases for which subsumption does not hold. Thus, for the same versions of increasing size of the Cell, NCI and Teleost KBs we randomly created 100 different subclass queries that do not have explanations. In Table 2 we report for each KB the runtime in seconds. As for the previous test, we setted a time-out of 5 minutes but this limit was never reached.

Table 2

Average execution time for the queries without explanations to the Cell, Teleost and NCI KBs

Dataset		Size of the Probabilistic TBox
				0	250	500	750	1,000
Cell	runtime (s)	0.47	1.52	2.43	2.52	3.14
Teleost	runtime (s)	1.15	4.51	12.76	14.69	15.27
NCI	runtime (s)	1.42	4.15	5.99	7.41	7.63

8.3. Inference with a limit on the number of explanations

We studied how the execution time and the probability of queries vary when imposing a limit on the number of explanations. The experiments have been performed on Linux machines with a 3.10 GHz Intel Xeon E5-2687W with 2GB memory allotted to Java.

We chose the Grid6

⁶

http://www.myGrid.org.uk/

KB that is part of the myGrid project. The Grid KB has already been used for testing the performances of Pellet in [30]. It belongs to the bioinformatics domain and contains concepts at a high level of abstraction. For the test, we used a version of the Grid KB with $\mathcal{SHOIN}$ expressiveness that contains 2,838 axioms, 550 atomic concepts, 69 properties and 13 individuals, downloaded from the Tonesrepository.7 ⁷

http://rpc295.cs.man.ac.uk:8080/repository/browser

We associated a probability of 0.5 to each axiom of the KB and then we ran 100 different subclass queries.

We first computed the correct probability of each query by using BUNDLE without a limit on the number of explanations. Then we ran each query several times, each time with an increasing limit. The maximum number of explanations is 16: there were 20 queries with 16 explanations but most of the queries have a number of explanations between 1 and 5. We computed the relative error e between the correct probability p of a query and the probability ${\mathit{p}}^{\prime }$ returned by BUNDLE with a limit on the number of explanations with the formula $\mathit{e}=\frac{\mathit{p}-{\mathit{p}}^{\prime }}{\mathit{p}}$ . Then we averaged the relative error over all the queries.

In Fig. 13 we show how the mean relative error varies with respect to the limit on the number of explanations. As can be seen, the quality of the answer increases as the limit on the number of explanations increases. Table 3 reports the execution times, averaged over all the 100 queries. The row of Table 3 with “–” in the first column contains the average execution time for BUNDLE without a limit on the number of explanations. Figure 14 shows the execution time as a function of the limit on the number of explanations, based on the values of Table 3.

Table 3

Average execution time depending on the limit on the number of explanations for the Grid KB. The last row reports the time spent for finding the set of all explanations

Limit on the explanations	Runtime (s)
0	0.81
2	1.40
4	1.44
6	1.46
8	1.49
10	1.52
12	1.55
14	2.10
16	9.36
–	18.44

Fig. 13.

Mean relative error of the probability of queries as a function of the limit on the number of explanations for the Grid KB.

Fig. 14.

Average execution time (s) as the limit on the number of explanations to the queries varies for the Grid KB.

8.4. Scalability of BUNDLE

Finally, we did a scalability test with two different KBs: the full version of the NCI Thesaurus (NCI_full for short) with $\mathcal{SH}$ expressiveness that contains 3,382,017 axioms and the Foundational Model of Anatomy Ontology (FMA for short)8

⁸

http://sig.biostr.washington.edu/projects/fm/index.html

with $\mathcal{ALCOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ expressiveness. FMA is a KB for biomedical informatics that models the phenotypic structure of the human body anatomy. It contains 88,252 axioms in the TBox and RBox and 237,382 individuals. The experiments have been performed on a Linux machine with a 2.33 GHz Intel Dual Core E6550 with 2GB memory allotted to Java.

For NCI_full we generated 10 ontologies of increasing size that contain $10\%\mathrm{,}\dots \mathrm{,}100\%$ of the axioms. Then we randomly selected an increasing number of certain axioms from these subontologies and made them probabilistic. We sampled 5,000, 10,000, 15,000, 20,000, 25,000 different probabilistic axioms, obtaining 50 different probabilistic KBs with total size from 338,201 to 3,382,017 axioms. Then we randomly created 100 subclass queries for each of the 50 subontologies and ran them. Figure 15 shows the trend of the runtime averaged over the queries with respect to the total size of the ontologies and the subset of probabilistic axioms. The maximum time spent for computing the probability of a query is 266.24 seconds with the KB that contains $90\%$ of the axioms.

Fig. 15.

Average execution time (s) for the queries to the NCI_full KB on versions of increasing size of the ontology and of the probabilistic part. On the x axis is reported the total number of axioms of the KB (including the probabilistic ones) and on the y axis the number of probabilistic axioms considered.

Finally, we exploited the FMA ontology for running a scalability test where only the size of the ABox varies. We generated versions of the ontology that contain the entire TBox and RBox, 500 probabilistic axioms and an increasing number of individuals. The size of the ABox varies between 50,000 and all the individuals contained in the full ABox with a step of 50,000. We generated 100 instance-of queries by randomly selecting an individual and a class among those to which it belongs. Figure 16 shows how the runtime averaged over the queries varies with respect to the size of the ABox. With 237382 individuals, that correspond to the entire ABox, BUNDLE raises an out-of-memory error. The maximum inference time reached is 298.98 seconds with 200,000 individuals.

Fig. 16.

Average execution time (s) for the queries to the FMA KB with respect to the increasing size of the ABox. BUNDLE cannot manage the entire ABox (237382 individuals).

As can be seen, BUNDLE can manage very large ontologies and answer queries in a relatively short time.

9. Conclusions

We have presented the DISPONTE semantics for probabilistic DLs that is inspired by the distribution semantics of probabilistic logic programming. We have discussed the application of DISPONTE to $\mathcal{SHOIN}\mathrm{(}\mathbf{D}\mathrm{)}$ , a prototype of an expressive DL. DISPONTE minimally extends the language to which it is applied and allows both assertional and terminological probabilistic knowledge. We have also presented the algorithm BUNDLE that is able to compute the probability of queries from DISPONTE KBs. BUNDLE has been both compared with the probabilistical reasoner PRONTO and tested for scalability on several real world KBs. The experiments show that BUNDLE is able to deal with ontologies of significant complexity, even if in some situations only an approximated answer takes a reasonable amount of time. BUNDLE is available for download from http://sites.unife.it/ml/bundle together with the datasets used in the experiments.

In the future, we plan to consider extensions of the semantics including statistical or “Type 1” knowledge in the terminology of [22]. Moreover, alternative approaches for inference will be considered, in particular reasoning algorithms returning a pinpointing formula [1,2]: such a formula compactly encodes explanations for the query and can be converted directly into a BDD. We will also consider non-Boolean conjunctive queries and develop inference algorithms for answering them. One possibility would be to first retrieve the instances satisfying the query and then compute explanations for each of them. We have also started to study the problem of learning the parameters [63] and we are planning to tackle the problem of learning the structure of probabilistic KBs.