=Paper= {{Paper |id=Vol-1193/paper_67 |storemode=property |title=Reasoning about Belief Uncertainty in DL Lite N bool |pdfUrl=https://ceur-ws.org/Vol-1193/paper_67.pdf |volume=Vol-1193 |dblpUrl=https://dblp.org/rec/conf/dlog/DjeddaiSK14 }} ==Reasoning about Belief Uncertainty in DL Lite N bool== https://ceur-ws.org/Vol-1193/paper_67.pdf

Reasoning About Belief Uncertainty in 𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍

Ala Djeddai, Hassina Seridi and Med Tarek Khadir

LabGED Laboratory, Computer Science Department, Badji Mokhtar-Annaba University P.O. Box
12, 23000 Annaba, Algeria.
{djeddai,seridi,khadir}@labged.net

Abstract. Dealing with uncertainty is a very important issue in description logics
𝑁
(DLs). In this paper, we present 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 a new probabilistic extension of
𝑁
𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 , known as a very expressive DL‐Lite, by supporting the belief degree
interval in a single axiom or a set of axioms connected with conjunction (by ∧) or
𝑁 𝑁
disjunction (by ∨) operators. The 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 semantics is based on 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙
𝑁
features which are a new alternative semantics for 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 having a finite struc-
𝑁
ture and its number is always finite unlike classical models. 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 also
supports terminological and assertional probabilistic knowledge and the main rea-
soning tasks: satisfiability, deciding the probabilistic axiom entailment and compu-
ting tight interval for entailment are achieved by solving linear constraints system. A
prototype is implemented using OWL API for knowledge base creation, Pellet for
reasoning and LpSolve for solving the linear programs.

Keywords: uncertainty, description logics, probabilistic reasoning, DL‐Lite, belief
probability.

1 Introduction

Dealing with uncertainty in knowledge representation and reasoning is a very important
issue and research direction. Uncertainty arises from various causes such as: automatically
extracting and processing data, integration of information from different heterogeneous
sources, inconsistency, incompleteness and incorrect information. Ontology merging, user
or automatic annotations, ontology alignment and information retrieval are also important
sources of uncertainty. An example of uncertain information is given as follows: “Roufai-
da is a postgraduate student with degree ≥ 0.7”. From the main languages used to
represent and reason about knowledge, there are description logics DLs [1] that are de-
signed for crisp and deterministic information. Thus, they are not able to deal with the
unknown and therefore must be extended in order to comply with uncertain knowledge.
DLs are the formal foundation of the ontology web language OWL which is a W3C stan-
dard used for knowledge modeling in the semantic web. To handle uncertainty, many
approaches proposed DLs extensions such as, probabilistic approaches when the degree of
uncertainty is interpreted as probability value. Most of them are difficult to use and based
on classical models or use graphical models (such as: Bayesian Network) and don't sup-
𝑁
porting the belief in terminological axioms. In this paper, 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 a novel proba-
𝑁
bilistic extension of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 [2] by using the belief probability is presented. An ex-
ample of probabilistic axiom is: a given professor is a PhD student with probability in
[0.7,0.9]. We choose working with intervals instead of single values because the probabil-
ities can be extracted from different sources and different agents can compute different
probabilities so intervals are a good choice for working under uncertainty. The
𝑁 𝑁
𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 semantics is based on 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 features which are a new alternative
𝑁
semantics for 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 . We use features instead of classical models because they have
𝑁
finite structure and its number is always finite unlike models. 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 supports
terminological and assertional probabilistic knowledge. Unlike approaches with graphical
𝑁
models when the model must be fully specified, 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 needs only the belief
interval in a single axiom or a set of axioms connected with ∧ or ∨. Using features with
belief is a new contribution compared to the work in [13] which uses probabilistic inter-
pretation on all features but with conditional probability that are interpreted as statistical
information and not belief.
𝑁
Section 2 presents the 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 language and the feature notion. In section 3 the
proposed probabilistic extension is presented and the syntax and semantics of
𝑁
𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge base based on features are explained. Section 4 details the
𝑁
reasoning tasks supported by 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 . The implementation and experimentation
are given in section 5. The section 6 is for the related works where the conclusion and
future works are presented in the last section.

2 𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍 Language and the Feature Notion

𝑁
In this section, we start by defining 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 , its syntax and semantics, then the notion
of types and features are detailed.

2.1 The 𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍 Language

Description logics [1] abbreviated by DLs from a family of languages that are used for
knowledge representation and reasoning. Their complexity increased with their expressiv-
ity. Therefore some researchers propose 𝐷𝐿‐ 𝐿𝑖𝑡𝑒 language [3,4] with very good computa-
tional property but less expressivity. It is behind OWL 2 QL which is OWL 2 profile.
𝑁
Thus, we focus on 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 [2] which is an expressive superset of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒 where the
latter is extended with full Booleans and number restrictions on roles. It contains or indi-
vidual, atomic concepts and atomic roles. General concepts and roles are defined as fol-
lows: 𝑅 ← 𝑃|𝑃− , 𝐵 ← ⊤ 𝐴 ≥ 𝑛 𝑅, 𝐶 ← 𝐵 ￢𝐶 𝐶1 ⊓ 𝐶2 , where 𝐴 is an atomic concept, 𝑃
is an atomic role, 𝑅 is a general role and 𝑛 ≥ 1. 𝐵 is called basic concept and 𝐶 is a gen-
eral concept. We abbreviate￢⊤, ≥ 1 𝑅,￢(￢𝐶1 ⊓ ￢𝐶2 ) and￢(≥ 𝑛 + 1 𝑅) respectively
by ⊥, ∃𝑅, 𝐶1 ⊔ 𝐶2 and ≤ 𝑛 𝑅.
A signature is a finite set 𝑆 = 𝑆𝐶 ∪ 𝑆𝑅 ∪ 𝑆𝐼 ∪ 𝑆𝑁 where 𝑆𝐶 is the set of atomic con-
cepts, 𝑆𝑅 is the set of atomic roles, 𝑆𝐼 is the set of individual names and 𝑆𝑁 is the set of
𝑁
natural numbers used in 𝑆𝐶 (1 is always in 𝑆𝑁 ). A 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 𝑇𝐵𝑜𝑥 𝑇 is a finite set of
concept inclusions on the form 𝐶1 ⊑ 𝐶2 , where 𝐶1 and 𝐶2 are general concepts. A
𝑁
𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 𝐴𝐵𝑜𝑥 𝐴 is a finite set of assertions of the form 𝐶(𝑎) (concept membership)
or 𝑅(𝑎, 𝑏) or ￢𝑅(𝑎, 𝑏) (role membership) where 𝑎 and 𝑏 are individuals names. The pair
𝑁 𝑁
(𝑇, 𝐴) forms a 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge base. The semantics of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 is given by
𝐼 𝐼 𝐼
an interpretation 𝐼 = (△ , . ) where △ is a non empty set called the interpretation domain
and .𝐼 is an interpretation function that associates every individual 𝑎 with an element
𝑎𝐼 ∈△𝐼 such that 𝑎𝐼 ≠ 𝑏𝐼 for every pair 𝑎, 𝑏 ∈ 𝑆𝐼 , every atomic concept 𝐴 with a subset
(unary relation) 𝐴𝐼 of △𝐼 and every atomic role 𝑃 with a subset (binary relation) 𝑃𝐼 of
△𝐼 ×△𝐼 . The interpretation 𝐼 is extended to general concepts and roles. Given an interpre-
tation 𝐼 , we write 𝐼 satifies 𝐶1 ⊑ 𝐶2 denoted by 𝐼 ⊨ 𝐶1 ⊑ 𝐶2 if 𝐶1 𝐼 ⊆ 𝐶2 𝐼 , 𝐼 ⊨ 𝐶(𝑎) if
𝑎𝐼 ∈ 𝐶 𝐼 , 𝐼 ⊨ 𝑅(𝑎, 𝑏) if 𝑎𝐼 , 𝑏𝐼 ∈ 𝑅𝐼 . 𝐼 satisfies a 𝑇𝐵𝑜𝑥 𝑇 if 𝐼 satisfies every inclusion in
𝑇, 𝐼 satisfies a 𝐴𝐵𝑜𝑥 𝐴 if it satisfies each assertion in 𝐴. Given a knowledge base 𝐾 =
𝑇, 𝐴 and an interpretation 𝐼, 𝐼 is called a model of 𝐾 if 𝐼 satisfies 𝑇 and 𝐴. A knowledge
base 𝐾 is satisfiable if it has at least one model. For a concept 𝐶, we say that 𝐾 satisfies 𝐶
if there is a model of 𝐾 satisfying 𝐶. For concept inclusion or assertion 𝑥, we say that 𝑥 is
entailed by 𝐾 and we write 𝐾 ⊨ 𝑥 if 𝑥 is satisfied by every model of 𝐾.
Terminological Box 𝑇: Assertion Box 𝐴:
1. 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 ⊑ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 5. 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟(FOFO)
2. 𝐶𝑜𝑢𝑟𝑠𝑒 ⊑ ￢𝑆𝑡𝑢𝑑𝑒𝑛𝑡 ⊓ ￢𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 6. 𝐶𝑜𝑢𝑟𝑠𝑒(DESCRIPTION LOGICS)
3. ∃𝑡𝑒𝑎𝑐𝑕 ⊑ 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 7. 𝑡𝑒𝑎𝑐𝑕(FOFO, DESCRIPTION LOGICS)
4. ∃𝑡𝑒𝑎𝑐𝑕− ⊑ 𝐶𝑜𝑢𝑟𝑠𝑒
𝑁
Fig. 1. An example of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge base
𝑁
Example 1. An example of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge base 𝐾 = 〈𝑇, 𝐴〉 is presented in fig.1
which contains the atomic concepts 𝑆𝑡𝑢𝑑𝑒𝑛𝑡, 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡, 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 and 𝐶𝑜𝑢𝑟𝑠𝑒. It
also contains the atomic role 𝑡𝑒𝑎𝑐𝑕. The TBox 𝑇 tells that all PhD students are students
(1) and a course is not a professor or a student. It also says that the atomic role 𝑡𝑒𝑎𝑐𝑕 has
𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 as domain (3) and 𝐶𝑜𝑢𝑟𝑠𝑒 as range (4). The ABox 𝐴 defining FOFO as a pro-
fessor teaches DESCRIPTION LOGICS (5) (6) (7). The signature of 𝐾 is 𝑆𝐶 ∪ 𝑆𝑅 ∪ 𝑆𝐼 ∪ 𝑆𝑁
where: 𝑆𝐶 = {𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡, 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡, 𝐶𝑜𝑢𝑟𝑠𝑒} , 𝑆𝑅 = {𝑡𝑒𝑎𝑐𝑕} , 𝑆𝐼 =
{FOFO, DESCRIPTION LOGICS}, 𝑆𝑁 = {1}.

2.2 𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍 Features

Working with models has some difficulties. Domains have complex (possibly infinite)
structures and DL knowledge bases may have infinitely many models. Thus an alternative
𝑁
semantics has been proposed called feature [15] which is prposed for the 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙
knowledge bases. In contrast to classical models the features have always finite structures
and every knowledge base has a finite set of features. According to these motivations, we
choose working with features instead of models. Another motivation is that we must con-
sider all possible knowledge base situations and the number of the latters must be finite.
The feature notion is based on the type notion proposed in [8]. We begin by presenting
types and then the feature is explained.
Given a finite signature 𝑆, an 𝑆‐ 𝑡𝑦𝑝𝑒 𝜏 is a set of basic concepts over 𝑆, such that:
⊤ ∈ 𝜏 and for any 𝑚, 𝑛 ∈ 𝑆𝑁 with 𝑚 < 𝑛 , 𝑅 ∈ 𝑆𝑅 ∪ {𝑃− |𝑃 ∈ 𝑆𝑅 } , ≥ 𝑛 𝑅 ∈ 𝜏 implies
≥ 𝑚 𝑅 ∈ 𝜏. In what follows, ⊤ ∈ 𝜏 is omitted for simplicity and 𝑆‐ 𝑡𝑦𝑝𝑒 will be specifies
as 𝑡𝑦𝑝𝑒. Type 𝜏 satisfies basic concept 𝐵 if 𝐵 ∈ 𝜏, 𝜏 satisfies ￢𝐶 if 𝜏 not satisfies 𝐶, and
𝜏 satisfies 𝐶1 ⊓ 𝐶2 if 𝜏 satisfies 𝐶1 and 𝐶2 . The satisfaction relation is denoted by ⊨. We
say that 𝜏 satisfies 𝐶1 ⊑ 𝐶2 ( 𝜏 ⊨ 𝐶1 ⊑ 𝐶2 ) if 𝜏 ⊨ ￢𝐶1 or 𝜏 ⊨ 𝐶2 . Thus 𝜏 satisfies a
𝑇𝐵𝑜𝑥 𝑇 if 𝜏 satisfies every concept inclusion axiom in 𝑇.
Types are sufficient to capture the semantics of the 𝑇𝐵𝑜𝑥, they are not able to capture
the semantics of the 𝐴𝐵𝑜𝑥 because they are not suited for individual, thus they must be
extended with additional set. The latter is dedicated to the concept and role memberships
and is called a 𝑆‐ 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set for the 𝐴𝐵𝑜𝑥, defined in [15] as:
Definition 1. An 𝑆‐ 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set 𝐻 (or 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑) is finite set of assertions of the form
𝐵(𝑎) or 𝑃(𝑎, 𝑏), where 𝑎, 𝑏 ∈ 𝑆𝐼 , 𝑃 ∈ 𝑆𝑅 and 𝐵 is a basic concept over 𝑆, satisfying the
following conditions:
 For each 𝑎 ∈ 𝑆𝐼 , ⊤(𝑎) ∈ 𝐻, and ≥ 𝑛 𝑅(𝑎) ∈ 𝐻 implies ≥ 𝑚 𝑅(𝑎) ∈ 𝐻 for 𝑚, 𝑛 ∈ 𝑆𝑁
with 𝑚 < 𝑛.
 For each 𝑃 ∈ 𝑆𝑅 , 𝑃(𝑎, 𝑏𝑖 ) ∈ 𝐻 (𝑖 = 1, … , 𝑛) implies ≥ 𝑚 𝑃(𝑎) ∈ 𝐻 for any 𝑚 ∈ 𝑆𝑁
such that 𝑚 ≤ 𝑛.
 For each 𝑃 ∈ 𝑆𝑅 , 𝑃(𝑏𝑖 , 𝑎) ∈ 𝐻 (𝑖 = 1, … , 𝑛) implies ≥ 𝑚 𝑃−(𝑎) ∈ 𝐻 for any 𝑚 ∈ 𝑆𝑁
such that 𝑚 ≤ 𝑛.
For a given individual 𝑎, the type 𝜏 = 𝐵1 , … 𝐵𝑗 (𝑗 ≥ 1) is called the type of 𝑎 in 𝐻,
where 𝐵1 (𝑎), … 𝐵𝑗 (𝑎) are all basic concept assertions associated with 𝑎 in 𝐻 . A
𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set 𝐻 satisfies 𝐶(𝑎) if the type of 𝑎 in 𝐻 satisfies 𝐶 , 𝐻 satisfies 𝑃(𝑎, 𝑏) or
𝑃− (𝑏, 𝑎) if 𝑃(𝑎, 𝑏) ∈ 𝐻 (the same is with ￢𝑃 𝑎, 𝑏 and ￢𝑃−(𝑏, 𝑎) ). 𝐻 satisfies an
𝐴𝐵𝑜𝑥 𝐴 if 𝐻 satisfies every assertions in 𝐴. The pair 〈𝜏, 𝐻〉 can be used to provide a se-
mantics characterization but it is proved in [15] that using this pair is not sufficient to
capture the connection between the 𝑇𝐵𝑜𝑥 and the 𝐴𝐵𝑜𝑥. Thus feature which is a set of
𝑁
types can provide a complete semantics of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge bases. The notion of
feature is defined in [15] as follows:
Definition 2. Given a signature 𝑆, an 𝑆‐ 𝑓𝑒𝑎𝑡𝑢𝑟𝑒 (or simply 𝑓𝑒𝑎𝑡𝑢𝑟𝑒) is a pair 𝐹 =
〈Ξ, 𝐻〉, where Ξ is a non empty set of 𝑆‐ 𝑡𝑦𝑝𝑒𝑠 and 𝐻 an 𝑆‐ 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set, satisfying the
following conditions:
 ∃𝑃 ∈ ⋃Ξ if ∃𝑃 − ∈ ⋃Ξ for each 𝑃 ∈ 𝑆𝑅 .
 For each 𝑎 ∈ 𝑆𝐼 we have 𝜏 ∈ Ξ, where 𝜏 is the type of 𝑎 in 𝐻.
Given a feature 𝐹 = 〈Ξ, 𝐻〉, 𝐹 satisfies 𝐶1 ⊑ 𝐶2 if every type in Ξ satisfies 𝐶1 ⊑ 𝐶2 , 𝐹
satisfies an assertion 𝐶(𝑎) or 𝑃(𝑎, 𝑏) if 𝐻 satisfies this assertion, 𝐹 satisfies a 𝑇𝐵𝑜𝑥 𝑇 if 𝐹
satisfies every inclusion in 𝑇, 𝐹 satisfies an 𝐴𝐵𝑜𝑥 𝐴 if 𝐹 satisfies every assertion in 𝐴.
𝑁
Given a 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge base 𝐾 = 〈𝑇, 𝐴〉 and a feature 𝐹, 𝐹 is a model feature of
𝐾 if 𝐹 satisfies 𝑇 and 𝐴. The set of all model features of 𝐾 is denoted by 𝑀𝑓 (𝐾). For a
concept inclusion or assertion 𝑥, 𝐾 ⊨𝑓 𝑥 if all model features of 𝐾 satisfies 𝑥 [15]. For
further reading, the readers are referred to [8] and [15].
Example 2. Given a feature 𝐹 = 〈Ξ, 𝐻〉 defined over the signature of 𝐾 such that:
Ξ = {𝜏1 , 𝜏2 } where: 𝜏1 = 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟, ∃𝑡𝑒𝑎𝑐𝑕 and 𝜏2 = {∃𝑡𝑒𝑎𝑐𝑕−, 𝐶𝑜𝑢𝑟𝑠𝑒} , 𝐻 =
{𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 FOFO , 𝐶𝑜𝑢𝑟𝑠𝑒(DESCRIPTION LOGICS), 𝑡𝑒𝑎𝑐𝑕(FOFO, DESCRIPTION LOGICS)}.
The feature 𝐹 = 〈Ξ, 𝐻〉 respects the conditions in definition 2 and the 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set
respects the definition 1. Every individual 𝑎 in 𝑆𝐼 has a type in 𝐻, 𝜏1 is for FOFO and 𝜏2 is
for DESCRIPTION LOGICS. 𝐹 is model feature of 𝐾 since every type satisfies every inclusion
in 𝑇 and 𝐻 satisfies every assertion in 𝐴. Thus 𝐹 = 〈Ξ, 𝐻〉 ∈ 𝑀𝑓 (𝐾).

3 Probabilistic Extension based on Features Using Belief
𝑁
A novel probabilistic extension of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 based on features is here presented. The
𝑁
𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 is extended to specify belief interval about its axioms. The extension is
𝑁 𝑁
called 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 . In this section, the syntax and semantics of 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 proba-
𝑁
bilistic knowledge bases using 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 features are given.

3.1 Syntax of 𝑷𝒓𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍 Probabilistic Knowledge Bases

𝑁
The Axioms in 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge bases can be annotated by belief degree interval.
The following types of probabilistic axioms are supported:
1. Probabilistic terminological axioms (𝑇𝐵𝑜𝑥 axioms): probabilistic concept inclusions
(PCI for short) about relationship between concepts. Each one has the form (𝐶 ⊑
𝐷)[𝛼,𝛽 ] which signifies that we have a belief degree in [𝛼, 𝛽] that the concept 𝐷 is sub-
sumed by 𝐶 or 𝐶 is sub class of 𝐷.
2. Probabilistic 𝐴𝐵𝑜𝑥 axioms: probabilistic assertions about concepts and roles instances:
𝐶(𝑎)[𝛼,𝛽 ] means that we have a belief degree in [𝛼, 𝛽] that the individual 𝑎 is an in-
stance of the concept 𝐶. 𝑅(𝑎, 𝑏)[𝛼,𝛽 ] means that the individual 𝑎 is related with the in-
dividual 𝑏 by the role 𝑅 with a belief degree in [𝛼, 𝛽].
3. Using conjunction (∧) or disjunction (∨) are not allowed in DLs, thus the satisfaction of
axioms that contain these notations is not defined for features. Therefore we define it as
𝑁
follow: for a given axiom 𝑥 = 𝑥1 ∧ 𝑥2 … ∧ 𝑥𝑛 where each 𝑥𝑖 is a 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 axiom,
we say that a feature 𝐹 = 〈Ξ, 𝐻〉 satisfied 𝑥 if 𝐹 ⊨ 𝑥𝑖 for every 𝑥𝑖 in 𝑥 and we write
𝐹 ⊨ 𝑥. We say that 𝐹 satisfies 𝑥 = 𝑥1 ∨ 𝑥2 … ∨ 𝑥𝑛 if 𝐹 satisfies at least one 𝑥𝑖 . Belief
𝑁
about these axioms is allowed in 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 . Thus, the probabilistic axiom
𝑥 = (𝑥1 ∧ 𝑥2 … ∧ 𝑥𝑛 )[𝛼,𝛽 ] means that we have a belief in [𝛼, 𝛽] that all 𝑥𝑖 can be satis-
fied in the same situation. The probabilistic axiom (𝑥1 ∨ 𝑥2 … ∨ 𝑥𝑛 )[𝛼,𝛽 ] means that we
have a belief in [𝛼, 𝛽] that at least one 𝑥𝑖 can be satisfied. This type of axioms is called
probabilistic conjunction and disjunction axioms (𝑃𝐶𝐷𝐴 for short). Using ∧ is not al-
lowed with ∨ in the same 𝑃𝐶𝐷𝐴 axiom
The values 𝛼 and 𝛽 are in [0,1] where 𝛼 ≤ 𝛽, 𝛼 is the lower bound and 𝛽 is the upper
𝑁
bound. In 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 , the probabilistic terminological box 𝑃𝑇 is a finite set of PCIs.
The probabilistic assertions box 𝑃𝐴 is a finite set of probabilistic assertions. 𝑃𝐶𝐷𝐴 is a set
of conjunction and disjunction axioms. A probabilistic knowledge base 𝐾𝐵 in
𝑁
𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 is defined as 𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉, the axioms of 𝑇⋃𝐴 are called
certain axioms whereas the axioms in 𝑃𝑇⋃𝑃𝐴⋃𝑃𝐶𝐷𝐴 are uncertain axioms. Probabilistic
Axiom with [1,1] are considered as certain axiom. Thus they are removed and added to
𝑇⋃𝐴. A single belief value is allowed, thus in this case 𝛼 = 𝛽 (see axiom 10 in fig.2).
𝑁
To model a 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 probabilistic knowledge, we must have an ontology (𝑇 and
𝑁
𝐴) in 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 and then extend it by adding probabilistic axioms.
Example 3. We present an example of probabilistic knowledge base
𝑁
𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉 in 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 which is an extension of 𝐾 = (𝑇, 𝐴) in
fig.1 with additional probabilistic axioms. Axioms numbered from 1 to 7 are the same in
𝐾. The PTBox 𝑃𝑇 tells that the concept professor is a subclass of the concept PhD student
with a belief degree in [0.44,0.65] (8). The 𝑃𝐴 defining RIDA and KAMEL as respectively a
PhD student (9) and a professor (10) with belief degree respectively in [0.55,0.60] and
[0.80,0.80]. The 𝑃𝐶𝐷𝐴 axiom 11 says that we have a belief degree in [0.45,0.67] that
LOTFI is a professor and teacher of DISCRIPTION LOGICS. Axiom 12 tell that ALA is a PhD
student or professor with a belief degree in [0.30,0.60].
Probabilistic Terminological Box 𝑃𝑇: Probabilistic Assertion Box 𝑃𝐴:
9. 𝑃𝑕𝑑𝑆𝑡𝑢𝑑𝑒𝑛𝑡(RIDA)[0.55,0.60]
8. (𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 ⊑ 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡)[0.44,0.65]
10. 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟(KAMEL)[0.80,0.80]
Probabilistic Conjunction and Disjunction Axioms 𝑃𝐶𝐷𝐴:
11. (𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟(LOTFI) ∧ 𝑡𝑒𝑎𝑐𝑕(LOTFI, DESCRIPTION LOGICS))[0.45,0.67]
12. (𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡(ALA) ∨ 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟(ALA))[0.30,0.60]
𝑁
Fig. 2. An example of 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 probabilistic knowledge base

3.2 Semantics of 𝑷𝒓𝑫𝑳‐ 𝑳𝒊𝒕𝒆𝑵
𝒃𝒐𝒐𝒍 Probabilistic Knowledge Bases

Given a probabilistic axiom, the certain axiom is specified by removing the belief interval.
The certain one of (𝐶 ⊑ 𝐷)[𝛼,𝛽 ] denoted by 𝑐𝑒𝑟( 𝐶 ⊑ 𝐷 𝛼 ,𝛽 ) is 𝐶 ⊑ 𝐷. Given a set of
PCIs 𝑃𝑇, the certain set of 𝑃𝑇 denoted by 𝑐𝑒𝑟(𝑃𝑇) is a set of concept inclusions. Proba-
bilistic assertion and the set of probabilistic assertions 𝑃𝐴 are treated in the same manner.
Because every axiom in 𝑃𝐶𝐷𝐴 has at least two axioms (∨ or ∧ must connects more than
an axiom), a set of certain axioms can be extracted from every 𝑃𝐶𝐷𝐴 axiom, this set can
includes concept inclusions and assertions. Therefore two functions: 𝑐𝑒𝑟_𝑐 and 𝑐𝑒𝑟_𝑑 are
defined to extract these sets where 𝑐𝑒𝑟_𝑐((𝑥1 ∧ 𝑥2 … ∧ 𝑥𝑛 )𝛼 ) is a set contains all 𝑐𝑒𝑟(𝑥𝑖 )
(all 𝑥𝑖 must be satisfied), and 𝑐𝑒𝑟_𝑑((𝑥1 ∨ 𝑥2 … ∨ 𝑥𝑛 )𝛼 ) is a set contains at least a
𝑐𝑒𝑟(𝑥𝑖 ) (at least one 𝑥𝑖 must be satisfied). Thus 𝑐𝑒𝑟(𝑃𝐶𝐷𝐴) is a set contains all sets of
certain axioms of all 𝑃𝐶𝐷𝐴 axioms.
A set of deterministic knowledge bases can be extracted from 𝐾𝐵, everyone must con-
tains 𝑇 ∪ 𝐴 and it can contains selected axioms from 𝑐𝑒𝑟(𝑃𝑇) ∪ 𝑐𝑒𝑟(𝑃𝐴) and selected
sets of axioms from 𝑐𝑒𝑟(𝑃𝐶𝐷𝐴). Axioms from 𝑐𝑒𝑟(𝑃𝑇) ∪ 𝑐𝑒𝑟(𝑃𝐴) are added directly.
For every selected set from 𝑐𝑒𝑟(𝑃𝐶𝐷𝐴), all its certain axioms are added. Each determinis-
𝑁
tic knowledge base respects the 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 language and every satisfiable knowledge
base is called 𝑝𝑜𝑠𝑠𝑖𝑏𝑙𝑒 𝑘𝑛𝑜𝑤𝑙𝑒𝑑𝑔𝑒 𝑏𝑎𝑠𝑒.
Definition 3 (𝒑𝒐𝒔𝒔𝒊𝒃𝒍𝒆 𝒌𝒏𝒐𝒘𝒍𝒆𝒅𝒈𝒆 𝒃𝒂𝒔𝒆𝒔 ). Given a probabilistic knowledge base
𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉. The possible knowledge bases of 𝐾𝐵, denoted by 𝑃𝑜𝑠𝐾𝐵 is
defined as follows: 𝑃𝑜𝑠𝐾𝐵 = {𝐾 = 〈𝑇 ∪ 𝑇 ′ , 𝐴 ∪ 𝐴′ 〉|𝐾 is satisfiable where 𝑇 ′ (resp. 𝐴′ )
contains selected axioms from 𝑐𝑒𝑟 𝑃𝑇 (resp. 𝑐𝑒𝑟 𝑃𝐴 ) and concept inclusions (resp.
assertions) in the selected certain sets from 𝑐𝑒𝑟(𝑃𝐶𝐷𝐴)}.
In other words, the possible knowledge base 𝐾 is a possible consistent situation of 𝐾𝐵.
In this situation, the actual world is a model of 𝐾. The satisfiability condition is important
for preventing inconsistencies and contradictions that may occur between the axioms in
𝑐𝑒𝑟(𝑃𝑇), 𝑐𝑒𝑟(𝑃𝐴) and 𝑐𝑒𝑟(𝑃𝐶𝐷𝐴). If there are probabilistic axioms that have certain
axioms which are inconsistent with 𝑇 ∪ 𝐴 then they can’t participated in creating 𝑃𝑜𝑠𝐾𝐵,
thus they are omitted and do not considered in reasoning.
Using definition 3, another notion is defined which is 𝑡𝑕𝑒 𝑝𝑜𝑠𝑠𝑖𝑏𝑙𝑒 𝑓𝑒𝑎𝑡𝑢𝑟𝑒:
Definition 4 𝒑𝒐𝒔𝒔𝒊𝒃𝒍𝒆 𝒇𝒆𝒂𝒕𝒖𝒓𝒆𝒔 . Given a probabilistic knowledge base 𝐾𝐵 =
〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉, let 𝑃𝑜𝑠𝐾𝐵 be the set of all possible knowledge bases of 𝐾𝐵. The
possible features related to 𝐾𝐵 , denoted by 𝑃𝑜𝑠ℱ is defined as follows: 𝑃𝑜𝑠ℱ =
{𝐹|𝐹 𝑖𝑠 𝑎 𝑚𝑜𝑑𝑒𝑙 𝑓𝑒𝑎𝑡𝑢𝑟𝑒 𝑜𝑓 𝐾 𝑠𝑢𝑐𝑕 𝑡𝑕𝑎𝑡 𝐾 ∈ 𝑃𝑜𝑠𝐾𝐵}.
From the definition, 𝑃𝑜𝑠ℱ contains all model features of all possible knowledge bases
in 𝑃𝑜𝑠𝐾𝐵. Like models, the possible features are used to describe the current 𝐾𝐵 situa-
tion. The signature of probabilistic knowledge base 𝐾𝐵 is defined as a finite set 𝑆 =
𝑠𝑖𝑔(𝑇) ∪ 𝑠𝑖𝑔(𝑐𝑒𝑟 𝑃𝑇 ) ∪ 𝑠𝑖𝑔(𝐴) ∪ 𝑠𝑖𝑔(𝑐𝑒𝑟 𝑃𝐴 ) ∪ 𝑠𝑖𝑔(𝑐𝑒𝑟𝑡 𝑃𝐷𝐶𝐴 ).
𝑁
The semantics of 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 probabilistic knowledge bases is given by probabilis-
tic interpretations. A probabilistic interpretation 𝑃𝑟 is a probability function on all possi-
ble features in 𝑃𝑜𝑠ℱ (𝑃𝑟: 𝑃𝑜𝑠ℱ → 0,1 ) such the sum of all 𝑃𝑟 𝐹 is equal to 1. We
have a probability distribution over 𝑃𝑜𝑠ℱ and 𝑃𝑟 distributed its probability values only on
possible features i.e. considering only possible situations of 𝐾𝐵. The probability of any
axiom 𝑥 is the sum of the probabilities associated with all features that satisfy 𝑥: 𝑃𝑟 𝑥 =
𝐹∈𝑃𝑜𝑠 ℱ 𝑎𝑛𝑑 𝐹⊨𝑥 𝑃𝑟(𝐹) . A probabilistic interpretation 𝑃𝑟 satisfies a PCI (𝐶 ⊑ 𝐷)[𝛼,𝛽 ]
denoted by 𝑃𝑟 ⊨ (𝐶 ⊑ 𝐷)[𝛼,𝛽 ] if and only if 𝑃𝑟 𝐶 ⊑ 𝐷 ∈ [𝛼, 𝛽]. 𝑃𝑟 satisfies a set of
PCIs 𝑃𝑇 denoted by 𝑃𝑟 ⊨ 𝑃𝑇 if 𝑃𝑟 satisfies all elements in 𝑃𝑇. The same is with a prob-
abilistic assertion and a set of probabilistic assertions 𝑃𝐴. 𝑃𝑟 satisfies 𝑃𝐷𝐶𝐴 denoted by
𝑃𝑟 ⊨ 𝑃𝐷𝐶𝐴 if 𝑃𝑟 satisfies all elements in 𝑃𝐶𝐷𝐴. 𝑃𝑟 satisfies a certain concept inclusion
𝐶 ⊑ 𝐷, denoted by 𝑃𝑟 ⊨ 𝐶 ⊑ 𝐷 if and only if for every feature with 𝑃𝑟 𝐹 > 0, we have
𝐹 ⊨ 𝐶 ⊑ 𝐷. 𝑃𝑟 satisfies a set of concept inclusions 𝑇 denoted by 𝑃𝑟 ⊨ 𝑇 if 𝑃𝑟 satisfies all
elements in 𝑇. The same is with certain assertion and certain set of assertions 𝐴. There-
fore, a probabilistic interpretation 𝑃𝑟 is a model of probabilistic knowledge base 𝐾𝐵 =
〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉 if and only if 𝑃𝑟 satisfies 𝑇, 𝐴 , 𝑃𝑇, 𝑃𝐴 and 𝑃𝐷𝐶𝐴. 𝐾𝐵 is satisfiable
(or consistent) if there is at least a model of 𝐾𝐵. Given a probabilistic axiom 𝑥[𝛼,𝛽 ] , 𝐾𝐵
entails 𝑥[𝛼,𝛽 ] , denoted by 𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] if for every 𝑃𝑟 such that 𝑃𝑟 ⊨ 𝐾𝐵 we have
𝑃𝑟 ⊨ 𝑥[𝛼,𝛽 ] . Before checking the satisfiability of 𝐾𝐵, 〈𝑇, 𝐴〉 must be consistent.
Example 4. The 𝐾𝐵 in fig.2 has the signature 𝑆 = 𝑆𝐶 ∪ 𝑆𝑅 ∪ 𝑆𝐼 ∪ 𝑆𝑁 where: 𝑆𝐶 , 𝑆𝑅 , and
𝑆𝑁 are the same of 𝐾 in fog.1 but 𝑆𝐼 = {FOFO, ALA, LOTFI , RIDA, KAMEL}. The set 𝑃𝑜𝑠𝐾𝐵 of
𝐾𝐵contains for example 𝐾1 = 〈𝑇 ∪ {𝑐𝑒𝑟 8 }, 𝐴 ∪ {𝑐𝑒𝑟 9 , 𝑐𝑒𝑟(10)}〉. We observe that 𝐾1
𝑁
is satisfiable and it respects the expressiveness of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 .

4 Reasoning and Inferences Tasks
𝑁
The main reasoning and inference tasks for 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 are the following:
 Probabilistic Knowledge Base Satisfiability (𝑃𝐾𝐵𝑆𝐴𝑇): Given a probabilistic know-
ledge base 𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉, decide whether 𝐾𝐵 is satisfiable.
 Tightest Belief interval for Logical Entailment (𝑇𝐵𝐼𝐿𝑜𝑔𝐸𝑛): Given a probabilistic
knowledge base 𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉 and an axiom 𝑥, compute the tightest be-
lief interval [𝛼, 𝛽] such tha𝑡 𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] .
 Logical Entailment ( 𝐿𝑜𝑔𝐸𝑛 ): Given a probabilistic knowledge base 𝐾𝐵 =
〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉 and probabilistic axiom 𝑥[𝛼,𝛽 ] associated with belief interval
[𝛼, 𝛽], decide whether 𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] or not.
The first task is achieved by using theorem 1. The second and the thirds uses theorem
2. Similarly to [9], the reasoning tasks use a system of linear constraints.
Theorem 1. Let 𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉 a probabilistic KB. This latter is satisfiable if
the next linear constraints system over variables 𝑝𝐹 (𝐹 ∈ 𝑝𝑜𝑠ℱ) is solvable:
𝑝𝐹 ≥ 𝛼 (𝑜𝑛𝑒 𝑓𝑜𝑟 𝑒𝑎𝑐𝑕 𝑥 𝛼,𝛽 𝑖𝑛 𝑃𝑇 𝑎𝑛𝑑 𝑃𝐴 𝑎𝑛𝑑 𝑃𝐶𝐷𝐴)
𝐹∈𝑝𝑜𝑠 ℱ,𝐹⊨𝑥

𝑝𝐹 ≤ 𝛽 (𝑜𝑛𝑒 𝑓𝑜𝑟 𝑒𝑎𝑐𝑕 𝑥 𝛼,𝛽 𝑖𝑛 𝑃𝑇 𝑎𝑛𝑑 𝑃𝐴 𝑎𝑛𝑑 𝑃𝐶𝐷𝐴)
𝐹∈𝑝𝑜𝑠 ℱ,𝐹⊨𝑥

𝑝𝐹 = 1
𝐹∈𝑝𝑜𝑠 ℱ
𝑝𝐹 ≥ 0 𝑓𝑜𝑟 𝑎𝑙𝑙 𝐹 ∈ 𝑝𝑜𝑠ℱ
Proof. The solver tries to find assignments to every 𝑝𝐹 such that all constraints are satis-
fied. Every 𝑝𝐹 is considered as probability of 𝐹 ∈ 𝑝𝑜𝑠ℱ. Thus the solver tries to find a
probability function on 𝑝𝑜𝑠ℱ that respects the constraints. The two first constraints are to
respect the satisfiability of every probabilistic axiom in 𝐾𝐵 i.e., the sum of probabilities of
the features that satisfy 𝑥 is in [𝛼, 𝛽]. The third one is to respect that the sum of all proba-
bilities associated with all features is 1. The condition of positive probabilities is specified
in the last constraint. By respecting the two last constraints, the condition that the proba-
bility ∈ [0,1] is also respected. If the solver get a solution i.e., value for every 𝑝𝐹 then the
solution respects the satisfiability conditions and 𝐾𝐵 has a model 𝑃𝑟 that assigns for
every 𝐹 ∈ 𝑝𝑜𝑠ℱ a value 𝑝𝐹 . Thus 𝐾𝐵 is satisfiable. We can proof by the same manner
that if 𝐾𝐵 is satifiable then the previous system of linear constraints is solvable.
Theorem 2. Given a probabilistic knowledge base 𝐾𝐵 = 〈𝑇, 𝑃𝑇, 𝐴, 𝑃𝐴, 𝑃𝐶𝐷𝐴〉. Suppose
𝐾𝐵 is satisfiable. Let 𝑥 be an axiom. The values 𝛼 and 𝛽 such that 𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] are taken
over all possible solutions of the system in Theorem 1 as follow:
𝛼 = 𝑚𝑖𝑛 𝑝𝐹 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑠𝑦𝑠𝑡𝑒𝑚 𝑖𝑛 𝑇𝑕𝑒𝑜𝑟𝑒𝑚 1
𝐹∈𝑝𝑜𝑠 ℱ,𝐹⊨𝑥

𝛽 = 𝑚𝑎𝑥 𝑝𝐹 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑠𝑦𝑠𝑡𝑒𝑚 𝑖𝑛 𝑇𝑕𝑒𝑜𝑟𝑒𝑚 1
𝐹∈𝑝𝑜𝑠 ℱ,𝐹⊨𝑥

Proof. Suppose that 𝐾𝐵 is satisfiable, the system in Theorem 1 has at least one solution
i.e., probabilistic interpretation of 𝐾𝐵. Given an axiom 𝑥, for every solution i.e., probabil-
istic interpretation, the solver computes the sum of all values assigned with features that
satisfy 𝑥. To minimization, it keeps 𝛼 and 𝛽 for the maximization. Thus, in every interpre-
tation 𝑃𝑟 we have 𝑃𝑟 𝑥 ∈ [𝛼, 𝛽] so 𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] .
The interval computed by theorem 2 is called the tightest belief interval i.e., 𝛼 (resp., 𝛽) is
the min (resp., max) of 𝑃𝑟(𝑥) subject to all models 𝑃𝑟 of 𝐾𝐵. Theorem 2 can be used to
decide if a given probabilistic axiom is entailed by a satisfiable probabilistic 𝐾𝐵. Thus
𝐾𝐵 ⊨ 𝑥[𝛼,𝛽 ] if the tightest belief interval that 𝑥 is entailed by 𝐾𝐵 is in [𝛼, 𝛽].
Example 5. From the example 3, if 𝐾𝐵 is satisfiable using Theorem 1, then we can use
theorem 2 to compute 𝑇𝐵𝐼𝐿𝑜𝑔𝐸𝑛 of some given axioms such as: computing the tightest
belief interval [𝛼, 𝛽] such that 𝐾𝐵 ⊨ 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡(KAMEL)[𝛼,𝛽 ] , finding the 𝑇𝐵𝐼𝐿𝑜𝑔𝐸𝑛of
𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 ⊑ 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟. We can also decide whether 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 LOTFI [0.4,0.6] is a
logical consequence of 𝐾𝐵.

5 Implementation and Experimentation
𝑁
A prototype of 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 is implemented in Java with Eclipse, using Pellet [18] for
reasoning, owlapi [19] for knowledge base creation, and LpSolve 5.5 [20] for solving the
𝑁
linear programs. 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 supportes only concept inclusion, concept and role asser-
tions. In owlapi the previous axioms are respectively created by OWL. 𝑠𝑢𝑏𝐶𝑙𝑎𝑠𝑠𝑂𝑓,
OWL. 𝑐𝑙𝑎𝑠𝑠𝐴𝑠𝑠𝑒𝑟𝑡𝑖𝑜𝑛 , OWL. 𝑝𝑟𝑜𝑝𝑒𝑟𝑡𝑦𝐴𝑠𝑠𝑒𝑟𝑡𝑖𝑜𝑛 . For example 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 ⊑
𝑆𝑡𝑢𝑑𝑒𝑛𝑡 is represented by OWL.𝑠𝑢𝑏𝐶𝑙𝑎𝑠𝑠𝑂𝑓(𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡). Therefore 𝑇, 𝐴,
𝑃𝑇, 𝑃𝐴 and 𝑃𝐶𝐷𝐴 are created using owlapi where every probabilistic axiom is associated
with its belief interval.
During the building of the possible knowledge bases, Pellet reasoner is used to test the
satisfiability of the latters. For a given probabilistic 𝐾𝐵, we can generate 2 𝑃𝑇 + 𝑃𝐴 + 𝑃𝐶𝐷𝐴
knowledge base, thus the one in fig.2 has 25 = 32 knowledge bases where all of the lat-
𝑁
ters are consistent so 𝑃𝑜𝑠𝐾𝐵 = 32 (tested by the 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 prototype). We con-
𝑃𝑇 + 𝑃𝐴 + 𝑃𝐶𝐷𝐴
clude that in worst cases, we have 𝑃𝑜𝑠𝐾𝐵 ≤ 2 . For every 𝐾 in 𝑃𝑜𝑠𝐾𝐵,
using its signature 𝑠𝑖𝑔(𝐾), we compute all types which satisfy its TBox, everyone is a set
of basic concepts represented using owlapi by a set of OWLClassExpression. From the
ABox of 𝐾, all basic concept and basic role assertions are extracted using Pellet. Thus
these assertions are used create the 𝐻𝑒𝑟𝑏𝑟𝑎𝑛𝑑 set 𝐻 of 𝐾 according to the definition 1 (𝐻
is created in owlapi as owl ontology). All possible combinations of the types associated
with 𝐾 are generated. For every individual in 𝑠𝑖𝑔(𝐾), its type in 𝐻 is extracted and added
to every combination. The latter is tested if it forms with 𝐻 a feature of 𝐾 using. Every
element in 𝑃𝑜𝑠𝐾𝐵 is treated with the same manner and all features are added to 𝑃𝑜𝑠𝐹.
𝑁
𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 Probabilistic DL-Lite in [13]
Semantics based on features Supported. Probabilistic Supported. Probabilistic in-
interpretation on only poss- terpretation on all features of
ible features. a given signature.
Terminological probabilis- Supports the belief in con- Supports the conditional
tic knowledge cept inclusions. constraints.
Probabilistic Assertions Supported Supported
Conjunction axioms supported Not supported
Disjunction axioms Supported Not supported
Reasoning tasks Strong conclusions by com- Weak conclusions. It uses an
puting the tightest belief inference rules that get only
interval. Deciding entail- lower bounds. In most cases,
ment is supported. The the upper bound is 1. The
reasoning tasks use linear inferences cover only special
programming for efficient cases. The tightest interval is
computation. not supported
Implementation and evalua- A prototype is implemented No implementation and eval-
tion and evaluated uation
𝑁
Table 1. Comparison between 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 and the work in [13]
One feature can model more than one knowledge base, thus the number of all possible
features can be reduced. Using the prototype, we found that the probabilistic KB in fig.2
has 1548 possible features and this proved that the number of features is finite. The linear
program Lp in theorem 1 is created using LpSolve, the variables number is 𝑃𝑜𝑠𝐹 be-
cause every 𝐹 ∈ 𝑃𝑜𝑠𝐹 is associated with one variable 𝑝𝐹 . Using 𝑃𝑇 , 𝑃𝐴 , 𝑃𝐶𝐷𝐴 and
𝑃𝑜𝑠𝐹, two constraints are created for every axiom 𝑥, one for its interval lower bound and
one for the upper bound. The coefficient of every variable 𝑝𝐹 in these constraints can be 1
(𝐹 satisfies 𝑥) or 0 (𝐹 does not satisfy 𝑥). The Lp for the KB in fig.2 has 1548 variables
and 12 constraints (10 for the probabilistic axioms).
Example 6. Using the prototype and the probabilistic KB in fig.2, we have found
that: 𝐾𝐵 ⊨ 𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡(KAMEL)[0.24,0.65] , (𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 ⊑ 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟)[0.0,0.45] and
𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 LOTFI [0.40,0.60] is not entailed by KB because the tightest belief interval of
𝑃𝑕𝐷𝑆𝑡𝑢𝑑𝑒𝑛𝑡 LOTFI is [0.45,0.67].
For comparison, our work and the one in [13] are used (see table 1) because the only
𝑁
probabilistic extension of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 which based on features is in [13]. The goal of
comparison is to understand the points of difference between the two works. We have not
presented this section in detail because of the limitation in paper length.

6 Related Works
𝑁
Closest to our work, we have [13] where the 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 is extended to use conditional
constraints on concepts i.e., statistical information about concepts, it supports probabilistic
terminological knowledge and probabilistic assertions about concepts and roles. The
probabilistic interpretation is defined on the set of all features of a given signature, unlike
our work which uses only the possible features instead of all features. In [13], no reaso-
ning tasks and implementation are presented and the belief in concept inclusion is not
supported. Its inferences are weak and consider only special cases. PrDLs [14] is a proba-
bilistic description logic which supports the belief in DL axioms. From the probabilistic
knowledge, similarly to our approach, the last reference extracts a set of certain know-
ledge bases but using a discrete probability distribution on all possible worlds. The author
in [9] who proposed P-SHOIN(D), P-SHIQ(D) and P-DL-Lite that are probabilistic exten-
sions of the DL-SHOIN(D), SHIF(D) and DL-Lite respectively, he uses the lexicographic
entailment and his work is based on Nilsson’s probabilistic logic [11]. He defines a prob-
abilistic interpretation on possible objects (everyone contains concepts that are free of
probabilistic individuals), one for terminological probabilistic knowledge and one for
every probabilistic individual. PRONTO reasoner [6] is based on the works in [9]. Unlike
our work, [9] does not allow probabilistic role assertions and it uses a separation between
probabilistic interpretations for the individuals and this makes difficulties to draw conclu-
sions about relations between individuals. Another work is in [22] where probabilistic
DLs based on the DL-ALC are presented. The work does not allow probabilistic termino-
logical knowledge and its semantics is subjective by considering the probabilities as be-
lieve degrees. The authors use probability distributions on possible worlds where every-
one is associated with a FOL interpretation. The quasi model is defined to check the con-
sistency of the probabilistic KB. This model shares some similarities with the feature
because the former is a pair of two sets of types one contains ABox types and the other
contains types for the individual. Contrary to this model the feature includes TBox and
ABox types and this is important to capture the KB semantics. The authors in [22] use
linear constraint systems that help to construct the worlds. In contrast, our work uses only
one linear constraint system after the features construction. The work in [16] allows for
epistemic and statistical probabilistic annotations in DL axioms by transforming the anno-
tated axioms to predicate logics. The authors consider the epistemic probability as belief
degree. The BUNDLE [17] is a reasoner for the work in [16]. Other set of probabilistic
DLs use graphical models such as Bayesian network BN as underlying probabilistic for-
malisms, some of these works are [7] and [5]. P-CLASSIC [7] is a probabilistic DL based
on BN that supports terminological probabilistic knowledge about concepts and roles but
does not allow assertional knowledge about concepts and roles. The work in [5] is an
extension of DL-Lite that uses BN towards tractable probabilistic DL. For further reading
about probabilistic uncertainty in semantic web, readers are referred to [10], [12] and [21].

7 Conclusion and Future Works
𝑁 𝑁
In this paper, 𝑃𝑟𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 a novel probabilistic extension for 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 knowledge
𝑁
bases is presented. The proposed work allows belief interval in a single 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙
𝑁
axiom or a set of 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 axioms that are connected with ∧ or ∨. Its semantics is
𝑁
based on 𝐷𝐿‐ 𝐿𝑖𝑡𝑒𝑏𝑜𝑜𝑙 features. Both terminological and assertion probabilistic knowledge
are supported. Using this work, meaningful conclusions can be drawn from the probabilis-
tic knowledge. Analysing the computational complexity of our work and implementing
efficient reasoner are the main future work directions. Another future work consists in
using specific application domains such as: medical.

References
1. Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., Patel-Schneider, P. F. (eds.): The De-
scription Logic Handbook: Theory, Implementation, and Applications. Cambridge University
Press (2003).
2. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite Family and Rela-
tions. J. Artif. Intell. Res. (JAIR) 36: 1-69 (2009).
3. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R. : DL-lite: Tractable des-
cription logics for ontologies. In: Proceedings of the 20th AAAI Conference on Artificial Intel-
ligence, AAAI 2005, pp. 602-607 (2005)
4. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and
efficient query answering in description logics: The DL-lite family. Journal of Automated Rea-
soning, 39(3), 385-429 (2007).
5. d'Amato, C., Fanizzi, N., & Lukasiewicz, T.: Tractable reasoning with Bayesian description lo-
gics. In: International Conference on Scalable Uncertainty Management. LNCS, vol. 5291, pp.
146-159. Springer (2008).
6. Klinov, P.: Pronto: A Practical Probabilistic Description Logic Reasoner. In proceedings of the
International Workshop on Uncertainty in Description Logics, vol. 613. CEUR-WS.org (2010).
7. Koller, D., Levy, A., Pfeffer, A. P-CLASSIC: A tractable probabilistic description logic. In
Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innova-
tive Applications of Artificial Intelligence Conference, pp. 390-397 . AAAI Press / The MIT
Press (1997).
8. Kontchakov, R., Wolter, F., Zakharyaschev, M.: Can you tell the difference between DL-lite
ontologies? In: Proceedings of the 11th International Conference on Principles of Knowledge
Representation and Reasoning, KR, pp. 285-295 (2008)
9. Lukasiewicz, T.: Expressive probabilistic description logics. Artificial Intelligence journal.
172(6-7), 852-883 (2008).
10. Lukasiewicz, T., Straccia, U. Managing uncertainty and vagueness in description logics for the
semantic web. Journal of Web Semantics, 6(4), pp. 291-308 (2008)
11. Nilsson, N. J.: Probabilistic logic. Artificial Intelligence journal, 28(1). p. 71-87 (1986)
12. Predoiu, L.: Probabilistic Models for the Semantic Web: A Survey. The Semantic Web for
Knowledge and Data Management, pp. 74-105. IGI global (2009)
13. Ramachandran, R., Qi G., Wang, K., Wang, J. Thornton, J.: Probabilistic Reasoning in DL-
Lite. In Proceedings of The Pacific Rim International Conference on Artificial Intelligence,
PRICAI, pp. 480-491, Springer (2012).
14. Tao, J., Wen, Z., Hanpin, W., Lifu, W.: PrDLs: A new kind of probabilistic description logics
about belief. In Okuno, H. G., Ali, M. (eds.) Proceedings of the 20th international conference
on Industrial, engineering, and other applications of applied intelligent systems, IEA/AIE’07,
pp. 644-654. Springer-Verlag Berlin Heidelberg (2007)
15. Wang, Z., Wang, K., Topor, R.W.: A new approach to knowledge base revision in DL-lite. In
Fox, M., Poole D., (eds.) Proceedings of the 24th AAAI Conference on Artificial Intelligence,
pp. 369-374. AAAI Press (2010).
16. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Epistemic and Statistical Probabilistic Ontolo-
gies. Proceedings of the International Workshop on Uncertainty Reasoning for the Semantic
Web, URSW, pp. 3-14, CEUR-WS.org (2012).
17. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: BUNDLE: A Reasoner for Probabilistic Ontolo-
gies. In Faber, W., Lembo, D., (ed.), Web Reasoning and Rule Systems: 7th International Con-
ference, Vol. 7994, pp. 183-197. Springer (2013).
18. Sirin, E., Parsia, B., Grau, B., Kalyanpur, A., and Katz, Y. Pellet: A Practical OWL-DL Rea-
soner. Journal of Web Semantics 5(2), pp. 51-53 (2007).
19. OWL API, http://owlapi.sourceforge.net/.
20. Lp solve (linear programming solver), http://lpsolve.sourceforge.net/.
21. The Ninth International Workshop on Uncertainty Reasoning for the Semantic web,
http://c4i.gmu.edu/ursw/2013/.
22. Lutz, C., and Schröder, L: Probabilistic Description Logics for Subjective Uncertainty. In Lin,
F., Sattler, U., and Truszczynski, M., (eds.), Proceedings of the Twelfth International Confer-
ence on Principles of Knowledge Representation and Reasoning, KR, AAAI Press, (2010).