1 Introduction

Knowledge representation for the semantic web requires an analysis of the universe of discourse in terms of concepts, definitions, objects, roles, etc., and then selecting a computer-usable version of the results. Ontologies play an important role for the success of the semantic web as they provide shared vocabularies for different domains, such as medicine and bio-informatics. There are many representation languages for ontologies. Among them, description logics [2] provide solid theoretical foundations to ontologies thanks to their clear semantics and formal properties. Moreover, despite its syntactical restrictions, the DL-Lite family enjoys good computational properties while still offering interesting capabilities in representing terminological knowledge [1]. This is why a large amount of works has been recently dedicated to this family and this paper is a contribution to this general research line.

The dynamic of information available on the web naturally leads to a continuous evolution of ontologies and to a permanent need to merge or to align them. As a result, we are often confronted to uncertainties in the used information. Proposing efficient methods for handling uncertainty in description logics, and particularly in the DL-Lite family, is an important research topic. Several recent works are devoted to fuzzy extensions of description logics (see e.g. [4, 8, 10]). Other works propose (min-based) possibilistic extensions of description logics and focus on standard reasoning services (see e.g. [3, 6, 7, 9]).

In some applications the nature of the encountered uncertainty is quantitative. This paper investigates the product-based possibilitic DL-Lite, denoted by Pb-\(\pi \)-DL-Lite, which has not been considered before. This paper shows that contrarily to the min-based possibilistic DL-Lite, query answering from a Pb-\(\pi \)-DL-Lite knowledge base is no longer tractable. We provide an encoding of computing the inconsistency degree of the product-based possibilistic DL-Lite knowledge base (the basis of query answering in Pb-\(\pi \)-DL-Lite) using a weighted maximum 2-Horn satisfiability problem.

2 Product-Based Possibilistic DL-Lite

DL-Lite is a family of DLs that aims to capture some of the most popular conceptual modeling formalisms. A DL KB \(K = \langle T, A\rangle \) consists of a set T of concept and role axioms (TBox) and a set A of assertional facts (ABox). In this paper, we only consider the DL-Lite\(_{core}\) and DL-Lite\(_{R}\) that underlie OWL2-QL [5]. The syntax of the DL-Lite\(_{core}\) language is defined as follows:

$$\begin{aligned} \begin{array}{c c c c} B \rightarrow A | \exists R &{} &{} &{} C \rightarrow B | \lnot B \\ R \rightarrow P | P^{-} &{} &{} &{} E \rightarrow R | \lnot R \\ \end{array} \end{aligned}$$
(1)

where A denotes an atomic concept, P an atomic role, \(P^-\) the inverse of the atomic role P, B (resp. C) are called basic (resp. complex) concepts and roles R (resp. E) are called basic (resp. complex) roles.

A DL-Lite\(_{core}\) TBox is a set of inclusion axioms of the form: \(B \sqsubseteq C\). An ABox is a set of membership assertions on atomic concepts and on atomic roles of the form: A(a) and P(a, b) respectively, where a and b are two individuals.

The DL-Lite\(_R\) language extends DL-Lite\(_{core}\) with the ability of specifying in the TBox inclusion axioms between roles of the form:

$$ E \sqsubseteq R $$

2.1 Weighted Assertional DL-Lite Knowledge Base

The syntax of product-based possibilistic DL-lite is represented by the concept of a Pb-\(\pi \)-DL-Lite knowledge base KB denoted by K.

Definition 1

A Pb-\(\pi \)-DL-Lite KB \(K = \{ \langle \phi _i,\alpha _i \rangle : i = 1, \dots , n \}\) is a finite set of possibilistic axioms of the form \(\langle \phi _i,\alpha _i \rangle \), where \(\phi _i\) is an axiom expressed in DL-Lite and \(\alpha _{i} \in ] 0, 1]\) represents the certainty degree of \(\phi _{i}\).

In Definition 1, only somewhat certain facts (having certainty degrees \(> 0\)) are considered. We consider that all the TBox axioms are fully certain. This means that there is no uncertainty about the general relationships between concepts and roles, but only about the ABox assertions. Hence, the terminological base is assumed to be stable and should not be questioned in the presence of inconsistencies.

Example 1

Let us consider the Pb-\(\pi \)-DL-Lite KB K composed of the following TBox T and ABox A, which will be used in the rest of the paper.

figure a

2.2 Semantics

A possibility distribution is a function that assigns to each DL-lite interpretation I, a real number in the interval [0, 1], called a possibility degree. \(\pi _K(I)\) represents the degree of compatibility of I with respect to the available information given in K. If an interpretation I is a model of each axiom of T and each assertion of A then its possibility degree is equal to 1. This reflects the fact that I is fully compatible with \(\langle T, A\rangle \). It also obviously means that \(\langle T, A\rangle \) is consistent. Now, if I falsifies some axioms of T or some fully certain assertions of A, then its possibility degree is equal to 0. This reflects the fact that I is impossible and should not be considered in the query answering process. More generally, if an interpretation I falsifies some assertions of the ABox, then its possibility degree is inversely proportional to the product of the weights of the assertions that it falsifies.

Definition 2

For all \(I \in \varOmega \),

$$\begin{aligned} \pi _K(I) = \left\{ \begin{array}{ll} 1 \ \ \ \ \ \ \ \ \ \ {if}\ \ \forall \langle \phi _i,\alpha _i \rangle \in K , I \models \phi _{i} \\ *\{ 1 - \alpha _{i} : \langle \phi _i,\alpha _i \rangle \in K , I \nvDash \phi _{i}\}\ \ \text {otherwise} \end{array} \right. \end{aligned}$$
(2)

where \(\models \) is the satisfaction relation between DL-lite interpretations and DL-Lite formulas.

Example 2

Let us consider again Example 1. The following table gives an example of the possibility degrees, obtained using Definition 2, for four interpretations over the domain \(\bigtriangleup =\{a, b\}\).

I

\(.^{\textit{I}}\)

\(\pi _K(I)\)

\(\textit{I}_1\)

\(PHD^I=\{a\},Super^I=\{b,h\}, Supervision\_a^I=\{(a,b),(a,h)\}\)

0.000

\(\textit{I}_2\)

\(PHD^I=\{a\},Super^I=\{b,h\}, Supervision\_a^I=\{(b,a),(h,a)\}\)

0.077

\(\textit{I}_3\)

\(PHD^I=\{a\},Super^I=\{b,h\}, Supervision\_a^I=\{(a,b),(a,h)\}\)

0.000

\(\textit{I}_4\)

\(PHD^I=\{b,h\},Super^I=\{a\}, Supervision\_a^I=\{(a,b),(a,h)\}\)

0.692

A Pb-\(\pi \)-DL-Lite KB K is said to be fully consistent if there exists an interpretation I such that \(\pi _K(I)=1\). Otherwise, K is said to be somewhat inconsistent. In the presence of certainty degrees associated with assertions, the concept of inconsistency becomes a graduated notion. More formally:

Definition 3

Let K be a Pb-\(\pi \)-DL-Lite KB and \(\pi _K\) be the possibility distribution induced by K obtained by Eq. 2. The inconsistency degree of K, denoted by Inc(K), is semantically defined as follows:

$$\begin{aligned} Inc(K) = 1- \max _{I\in \varOmega } (\pi _K(\textit{I})) \end{aligned}$$
(3)

Example 3

The inconsistency degree of the KB K, presented in Example 1 is: \(Inc(K)= 1- \max _{I\in \varOmega } (\pi _K(\textit{I}))\) = 0.30.

3 Inconsistency Degree as a Weighted Max-2-Horn-SAT Problem

3.1 Weighted Max-2-Horn-SAT (WM2HSAT)

The WM2HSAT problem consists in finding an assignment of boolean values to the propositional variables that maximizes the total weights of satisfied clauses. A weighted 2-Horn KB is a set of weighted formulas of the form : \(\theta = \{ (\phi _{i} , k_{i}) : i= 1,...,n \}\) where \(\phi _{i}\) is a clause with at most two literals and at most one non-negative literal. \(k_{i}\) is a natural number belonging to \(N \cup \{\infty \}\).

Definition 4

Let \(\theta \) be a weighted 2-Horn KB and R be a positive integer. The weighted Max-2-Horn-SAT decision problem is defined as follows:

Is there a sub-base \(\theta ' \subseteq \theta \) such that i) \(\{ \phi _i :(\phi _i, k_i) \in \theta '\}\) is consistent, ii) \(\theta '\) contains every \((\phi , k)\) of \(\theta \) such that \(k=\infty \) and iii) \(Weight(\theta ') \geqslant R ?\)

where \(Weight(\theta ')= \sum \{ k_i : (\phi _i , k_i) \in \theta '\ and\ k_i \ne \infty \}\).

Note that maximizing \(Weight(\theta ')\) is equivalent to minimizing \(Cost(\theta ')\) given by: \(Cost(\theta ')= \sum \{ k_i : (\phi _i , k_i) \in \theta \setminus \theta '\ and\ k_i \ne \infty \}\).

3.2 From an Inconsistent Pb-\(\pi \)-DL-Lite KB to a Weighted 2-Horn KB

A conflict is a minimal sub-base of A which is inconsistent with A. A set of assertions \({\mathcal {C}}\) is said to be a conflict if: i) \({\mathcal {C}}\subseteq A \), ii) \(\langle T, C\rangle \) is inconsistent and iii)\( \forall {\mathcal {C}}' \subseteq {\mathcal {C}}\), \(T \cup {\mathcal {C}}' \) is consistent. It has been shown in [1] that conflicts in a DL-Lite KB are composed of at most two ABox assertions.

The first step in computing Inc(K) is to encode the set of all conflicts and their corresponding weights by a weighted 2-Horn KB \(B_K\).

Definition 5

Let \(K = \langle T, A\rangle \) be a Pb-\(\pi \)-DL-Lite KB. Let \(\zeta \) be the set of all conflicts in A. Let M be a sufficiently large integer number. Let F be a scale changing function defined by: \(F(x) = - 10^M *(ln(1 - x))\). Each assertional fact X(a) is associated with a propositional symbol simply denoted by \(X_a\).

The weighted propositional 2-Horn KB corresponding to K, denoted by \(\mathbb {B}_K\), is defined as follows:

\(\mathbb {B}_K = \{(D_a, F(\alpha )), (B_a, F(\beta )), (\lnot D_a \vee \lnot B_a, \infty )\ | \) \(\{(D(a), \alpha ),(B(a), \beta )\} \in \zeta \}.\)

The function F is not unique. Recall that weights in K are expressed using the unit interval [0, 1] while the weights in \(\mathbb {B}_K\) are integers.

Example 4

The weighted 2-Horn KB corresponding to the Example 1 is:

figure b

Proposition 1

Let K be a Pb-\(\pi \)-DL-Lite KB and \(\mathbb {B}_K\) be its associated weighted propositional 2-Horn KB. \(Inc(K) = \alpha \) if and only if there exists a consistent sub-base \(\mathbb {B}_K' \subseteq \mathbb {B}_K\) such that i) \(Cost(\mathbb {B}_K') = F(\alpha )\) and ii) for every consistent sub-base \(\mathbb {B}_K'' \subseteq \mathbb {B}_K\), \(Cost(\mathbb {B}_K'') \ge Cost(\mathbb {B}_K')\).

Proposition 1 is important since it shows that the inconsistency degree of a Pb-\(\pi \)-DL-Lite KB can be redefined using the cost of a solution of the WM2HSAT problem on the associated weighted propositional KB. This gives us a practical mean to compute inconsistency degree using a WM2HSAT solver.

For the sake of simplicity, we assume that full inconsistency cannot occur, namely we assume that \(Inc(K) <1\).

Assumption 1

Let \( K= \langle T, A\rangle \) be a Pb-\(\pi \)-DL-Lite KB. Then, we assume that \(T \cup \{(f, 1): (f, 1) \in A \}\) is consistent.

The following algorithm accepts as input a Pb-\(\pi \)-DL-Lite KB and returns its inconsistency degree.

figure c

Example 5

Let us consider the KB K from Example 1. Its corresponding weighted 2-Horn KB \(\mathbb {B}_K\) is given in Example 4. The next step consists in a dichotomic search in the interval ranging from the minimum value \(l = 4082\) and the maximum value \(u = 293201\). The solver WM2HSAT is invoked with the sub-base \(\mathbb {B}_K\). The last call of the solver returns the consistent sub-base \(\mathbb {B}_K'\) which minimizes the sum of the degrees of formulas outside \(\mathbb {B}_K'\) \(cost(\mathbb {B}_K')= 36807\). The last step consists in computing \(Inc(K) =1 - e^{(-36807\div 10^5)} = 0.30 \).

4 Query Answering in a Product-Based Possibilistic DL-Lite

The problem of standard query answering is closely related to the ontology-based data access problem which takes as inputs a set of assertions, an ontology and a conjunctive query q and aims to find all answers to q over the set of data. We will limit ourselves to boolean queries. This is not a restriction since a conjunctive query can be equivalently redefined from a family of boolean queries, each of them is a result of instantiating the vector of distinguished variables.

A basic boolean query is called a grounded query, has the form:

\(q \leftarrow \exists \overrightarrow{y} \bigwedge _{i=1}^{n} B_i(\overrightarrow{y_i})\), where \(B_i\) is either an atomic concept or an atomic role or an individual and \(\overrightarrow{y_i}\) is either a variable (if \(B_i\) is a concept) or a pair of variables or a variable and an individual (if \(B_i\) is a role). Given a boolean query q, we first need to define the concept of a necessity measure, defined by:

$$\begin{aligned} N(q)= 1 - \max \{ \pi _K(I) : I\nvDash q \}. \end{aligned}$$
(4)

N(q) represents to what extent q is certain given the available knowledge.

If \(\pi _K(I)\) is fully consistent, then \(N(q) >0\) holds (namely q is somewhat accepted) if and only if each model of axioms of T and assertions of A is also a model of q. Similarly, \(N(q)= 1\) (q is fully accepted) if and only if for all I such that \(I\nvDash q\) we have \(\pi (I)= 0\) (namely, all counter models of q are declared as impossible). Now, when \(\pi \) is sub-normalized or inconsistent, then q is said to be somewhat accepted if and only if \(N(q) > Inc(K)\).

Definition 6

Let K be a Pb-\(\pi \)-DL-Lite KB, \(\pi _K\) be the possibility distribution associated with K using Eq. 2. Let \(N_{\pi }\) be the necessity measure induced by \(\pi _K\) using Eq. 5. Let q be a boolean query. Then \(K \models _{\pi } q\) if and only if \(N_{\pi }(q) > Inc(K)\).

Query answering process comes down first to the reformulation of the query q over the TBox in order to enrich it while eliminating all redundancies using the algorithm PerfectRef proposed in [5]. This step leads to obtain a set of queries Q where the union of the answer sets of these queries will be the answer of the initial query. Hence, querying q comes down to evaluate each query \(q_i \in Q\).

A very basic case in query answering is instance checking. The instance checking problem, in standard DL-Lite consists in deciding, given an individual a (or a pair of individuals (a, b)) a concept B or a role R and a DL-Lite KB \(K=\langle T, A\rangle \), whether B(a)(resp. R(a, b)) follows from \(\langle T, A\rangle \).

Proposition 2

Let \(K=\langle T, A\rangle \) be a Pb-\(\pi \)-DL-Lite KB, B be a concept (resp. R be a role) and a, b be two individuals. \(D_B\) (resp. \(D_R\)) is an atomic concept (resp. an atomic role) not appearing in T. Then :

  1. 1

    \(N(B(a)) = Inc(K_1)\) (resp. \(N(R(a,b)) = Inc(K_1)\)) where \(K_1 = \langle T_1, A_1 \rangle \) with \(T_1 = T \cup \{ ( D_B\sqsubseteq \lnot B, 1) \}\) (resp. \(T_1 = T \cup \{ ( D_R\sqsubseteq \lnot R, 1) \}\)) and \(A_1 = A \cup \{ (D_B(a), 1)\}\) (resp. \(A_1 = A \cup \{ (D_R(a, b), 1)\}\)).

  2. 2

    B(a) (resp. R(a, b)) is a consequence of K, denoted by \(K \models _\pi B(a)\) (resp. \(K \models _\pi R(a, b)\)) if \(Inc(K_1)>Inc(K)\).

Proposition 2 shows how to evaluate the query by using the concept of inconsistency degree. If a query is composed of a conjunction of assertions (grounded queries), then its enough to apply Proposition 2 to each assertion. This is possible thanks to the following propriety of necessity measures:

$$\begin{aligned} N(q_1 \wedge q_2) = \min (N(q_1 ), N(q_2)). \end{aligned}$$
(5)

5 Conclusions and Future Work

This paper developed an extension of lightweight ontologies, encoded in DL-Lite language, to the product-based possibility theory framework. The resulting language is denoted Pb-\(\pi \)-DL-Lite. The paper first introduced the syntax and the semantics of Pb-\(\pi \)-DL-Lite. Then, it addressed the problem of query answering and showed that it comes down to the problem of computing inconsistency degree in product-based Pb-\(\pi \)-DL-Lite knowledge bases. This problem is intractable in product-based DL-Lite setting contrarily to min-based DL-lite. An encoding of the inconsistency degree computing problem as a WM2HSAT problem has been proposed. This transformation was then used to propose an algorithm using a WM2HSAT solver to compute the inconsistency degree. As a future work, we plan to generalize our framework to arbitrary DL-Lite bases where the TBox axioms are not fully certain.