Data in real world applications is often subject to some kind of uncertainty, which can be due to incompleteness, unreliability or inconsistency. This poses a great challenge for ontology-based data access (OBDA) applications, which are expected to provide a meaningful answers to queries, even under uncertain domains. Several extensions of classical OBDA systems has been proposed to address this problem, with probabilistic, possibilistic, and fuzzy OBDA being the most relevant ones. However, these extensions present some limitations with respect to their applicability. Probabilistic OBDA deal only with categorical assertions, possibilistic logic is better suited to make a ranking of axioms, and fuzzy OBDA addresses the problem of modelling vagueness, rather than uncertainty. In this paper we propose Subjective DL-Lite (SDL-Lite), an extension of DL-Lite with Subjective Logic. Subjective DL-Lite allows us to model uncertainty in the data through the application of opinions, which encapsulate our degrees of belief, disbelief and uncertainty for each given assertion. We explore the semantics of Subjective DL-Lite, clarify the main differences with respect to its classical DL-Lite counterpart, and construct a canonical model of the ontology by means of a chase that will serve as the foundation for a future construction of an OBDA system supporting opinions.
Semantic applications that model real world scenarios often have to deal with uncertainty in the data. This is usually the case when extracting data from web sources, where information might be incomplete or unreliable. Even the method used for extracting the data creates another point of uncertainty, as it is quite common to rely on heuristic algorithms that are prone to errors.
In order for a semantic application to address all these issues, such an application should be able to comply with the following list of requirements: – Models uncertainty in the data – Understands the meaning of the underlying data – Provides answering services over custom user queries – Determines the reliability of the answers given the available information
In this paper we explore some of the theoretical foundations required to develop a logic capable of supporting ontology-based data access (OBDA) applications that can fulfil these requirements.
Our contributions in this paper are twofold: A) We define the semantics for Subjective DL-Lite in section 4, and B) We present a methodology to build a chase-based canonical interpretation of subjective ontologies in section 5. 2
Several relevant approaches to model Uncertainty have been proposed in different areas
of research. Probabilistic Logic [
These approaches have become popular for the results that they yielded, and many
implementations for specific solutions have been produced based on their premises [
The use of Probabilistic Logic does not naturally allow the user to assign some
amount of believe to the fact that we might be missing some information about a
certain statement. We propose the use of Subjective Logic [
We will use this approach to model uncertainty in ontologies, extending ABox assertions with subjective opinions. In this manner, we will be able to encapsulate how much information is already known about the validity of a certain axiom, as well as how much information is currently unknown. The application of opinions to axioms will result in some constraints that must hold for the ontology to make sense. These constraints will form the foundation for our reasoning, since they will let us propagate our beliefs through the ontology. 3 3.1
We will follow the standard syntax and semantics for classical (that is, without
uncertainty) description logics, and due to space constraints, will refer the reader to [
As usual, A denotes atomic concept names, and r denotes atomic role names. B denotes basic concepts, and R denotes roles or their inverses. All valid expressions for DL-Litecore are built using the following production rules: P ::= r j r , B ::= A j 9P j 9P .
A TBox T is a finite set of concept inclusions (CIs) B v B’, or B v :B’. An ABox A is a finite set of membership assertions of the form A(a), P(a,b). A DL-Litecore ontology O is a pair (T , A), where T is a DL-Litecore TBox, and A is a DL-Litecore ABox.
Following the standard semantics of description logics [
There are a number of common reasoning services that are usually provided when developing an application that deals with ontologies. Among these services, we can name: – Instance checking: Given an individual x and an concept C, determine whether or not x is a member of C. – Instance retrieval: Given a concept C, retrieve all the individuals that are members of C. – Consistency checking: Given a knowledge base KB, determine whether or not a model for KB exists. – Query answering: Given a knowledge base KB and a query q, determine all the answers for q that satisfy every model of KB. 3.2
Subjective ABoxes A subjective DL-Litecore ABox SA is an extension of a DL-Litecore ABox A in which every assertion in A is extended with an opinion. An opinion w over a statement x is a triple of positive numbers (b, d, u) such that b + d + u = 1; and in which b represents the degree of belief assigned to the truth of x, d represents the degree assigned to the falsehood of x, and u measures the degree of uncertainty associated with x. If, during the execution of any reasoning task, an opinion w is produced such that b + d + u > 1, we say that w is invalid. We denote with b(w), d(w), and u(w) the degrees of belief, disbelief and uncertainty associated with an opinion w, respectively, and with W the set of all possible opinions.
Definition 1. Let w1 = (b1; d1; u1) and w2 = (b2; d2; u2) be two opinions about the same assertion . We call w1 a specialisation of w2 (w1 w2) iff b2 b1 and d2 d1 (implies u1 u2). Similarly, we call w1 a generalisation of w2 (w2 w1) iff b1 b2 and d1 d2 (implies u2 u1). 3.3
Example Scenario In order to help us illustrate the many properties of the different aspects of Subjective DL-Lite, we present in this subsection a running example set in a medical domain. More specifically, we will consider a medical clinic, in which patients come seeking for a doctor to treat their illnesses. We can have the knowledge domain modelled by an ontology, with relevant relations represented in the TBox, and data for patients and clinical cases instantiated in the ABox. Table 1 illustrates the ontology that we are going to use for our example.
In our scenario, a patient sees the doctor due to an acute abdominal pain that he is suffering. Being the main reason for the visit, and having no reason to doubt the patient, the doctor proceeds to instantiate with total certainty the fact that the patient suffers an abdominal pain. This is covered by axiom a1.
Next, our patient tells the doctor that he also suffers something that he cannot describe very well, midway between a nausea or a migraine. This uncertain claim, stemming from the fact that the patient lacks the expertise to differentiate two distinct symptoms, can be easily modelled in a subjective ontology with axioms a2 and a3. The rational for this approach is based on the doctor having some reasons to belief that the patient suffers one of the symptoms, but not having enough information that could justify the choice of one over the other. It could be argued that, since either outcome is equally probable, both axioms should be extended with the opinion (0.5,0,0.5) instead. However, this is where the potential of Subjective Logic becomes clear, since such an opinion would reject any other option as the cause of the discomfort. By choosing to have a buffer of 0.1 degree in our uncertainty, we are leaving an door open for any other possible symptom that could be responsible for the malady. Indeed, it could be easily the case that the patient was suffering neither a nausea or a migraine, and instead had an ear infection. This capability of modelling what is unknown to us at the moment is what mainly differentiates Subjective Logic from similar approaches.
Continuing with our example, the doctor wants to know whether the Irritable Bowel Syndrome is present in any member of his relatives. Not even knowing about the disease itself, the patient finds himself unable to confirm, nor discard, any presence of it in his family. This is modelled by axiom a4, in which there is no commitment towards the truth nor the falsehood of the claim. The opinion (0,0,1), representing total uncertainty about an axiom, is the most general opinion possible, since any other opinion must necessarily be a specialisation of it. We will call (0,0,1) the default opinion, and assume that any axioms that do not explicitly appear in our ABox are extended with it. With this approach, we reflect the fact that anything not stated in our ontology is unknown, rather than false.
Finally, the doctor decides to run a blood test on the patient, to discard possible diseases that could be responsible for the symptoms. After a couple of days the results arrive, and the test shows that all the values for the patient fall within standard nominal ranges. However, the doctor is aware that these tests have an error margin of five percent, in which either a false positive or negative can be delivered instead of the real result. Knowing this limitation of the tests, the doctor only commits 90% of his confidence to axiom a5, reflecting the fact that the test itself is fallible by assigning 5% of his confidence to the disbelief degree of the axiom, and covering for some possible exceptional situations with the use of some uncertainty. 4 4.1
The semantics for a S DL-Litecore ABox is given in terms of subjective interpretations. A subjective interpretation I is a pair (4I , I ), where the domain 4I is a non-empty set of objects, and I is a subjective function that maps: – an individual a to an element aI 2 4I – a named class A to a function AI : 4I ! W – a named property R to a function RI : 4I 4I ! W
Following the example set in [
One interesting point to remark is that, in subjective environments, positive inclusions can lead to inconsistencies. This is not the case for classical knowledge bases, where inconsistencies were produced by violation of negative inclusions. We can illustrate this property going back to our example scenario. Imagine that the flu for 2015 gets declared a pandemic due to the high rate of spread in the population. Since we apply a series of guidelines and well-defined rules to check the criteria for the declaration of pandemics, we can state that the flu falls within the category of pandemia with total confidence using the following axiom a8 : P andemicDisease(f lu2015) : (1; 0; 0). It is clear that this axiom introduces an inconsistency in the ontology. Intuitively, it does not make sense to declare f lu2015 to be a minor disease with 90% of confidence at the same time that we state with total certainty that f lu2015 is also a grave disease (as inferred through t6). A direct application of the semantic constraint s7 lets us spot the inconsistency.
One last note before continuing to the formal definition of inconsistencies for subjective ontologies. In our example, the inconsistency arose due to some dynamic behaviour present in our ontology. That is, there was some initial statement that was refined at a later stage. Although extremely interesting, the task of introducing some dynamic aspect to our ontologies will be left for a future work. We will consider our ABoxes to be static in nature, and the only inconsistencies will arise due to the implicit relations given by axioms at the TBox level.
Let K = (T ; A) be a SDL-Litecoreknowledge base, be an axiom of K, and I and interpretation of K. The following will provide a formal definition of consistency for subjective ontologies: Definition 2. I is a model of , denoted I j= presented in table 2. , if I satisfies all the constraints Definition 3. I is a model of K, denoted I j= K, if I j= for each 2 K Definition 4. K is consistent if it has at least one model Definition 5. K models , denoted K j= , if I j= for every model I of K.
Definition 6. is an answer for a query q over K, denoted K j=q , if is an answer of q for every possible model of K.
Finally we need to redefine the meaning of some common reasoning tasks for a subjective ontology K: – Instance checking: Given an individual x and an concept C, determine the most general opinion ! such that K j= C(x) : !. – Instance retrieval: Given a concept C, return the set fC(x) : ! j ! is the most general opinion such that K j= C(x) : !g. – Query answering: Given a query q, return the set f : ! j ! is the most general opinion such that K j=q : !g.
Following the example presented in [
P (b; a); if R = P (1) Definition 7. Let S be a set of DL-Litecore membership assertions, and let T be a set of DL-Litecore TBox axioms. Then, an axiom 2 T is applicable in S to a membership assertion f 2 S if – (cr1) = A1 v A2; f = A1(a) : w; and A2(a) : w0 2 S, with b(w) > b(w0) – (cr2) = A1 v A2; f = A2(a) : w; and A1(a) : w0 2 S, with d(w) > d(w0) – (cr3) = A v 9R; f = A(a) : w, and there does not exist any constant b such that ga(R,a,b) : w’ 2 S, with b(w0) > b(w) – (cr4) = 9R v A, f = ga(R,a,b) : w, and A(a) : w’ 2 S, with b(w) > b(w0) – (cr5) = 9R v A, f = ga(R,a,b) : w, and A(a) : w’ 2 S, with d(w0) > d(w) – (cr6) = A1 v :A2; f = A1(a) : w; and A2(a) : w0 2 S, with b(w0) > d(w) – (cr7) = A2 v :A1; f = A1(a) : w; and A2(a) : w0 2 S, with b(w0) > d(w) – (cr8) = A v :9R; f = ga(R; a; b) : w; and A(a) : w0 2 S, with b(w0) > d(w) – (cr9) = A v :9R; f = A(a) : w; and ga(R; a; b) : w0 2 S, with b(w0) > d(w) – (cr10) = 9R v :A; f = ga(R; a; b) : w; and A(a) : w0 2 S, with b(w) > d(w0) – (cr11) = 9R v :A; f = A(a) : w; and ga(R; a; b) : w0 2 S, with b(w) > d(w0)
Applicable axioms can be used, i.e., applied, in oder to construct the chase of a knowledge base. The chase of a SDL-LitecoreKB is a (possibly infinite) set of membership assertions, constructed step-by-step starting from the ABox A. At each step of the process, an axiom 2 T is applied to a membership assertion f 2 S. Applying an axiom means refining our opinion about a certain f 0, that might not appear explicitly in S. The outcome of the application is a new set S0 in which is no longer applicable to f .
This construction process heavily depends on the order in which we select both the TBox axiom and the membership assertion in each iteration, as well as what constants we introduce when required. Therefore, we can produce a number of syntactically distinct sets of membership assertions following this process. However, it is possible to show that the result is unique up to renaming of constants occurring in each such set. In order to achieve this, we select TBox axioms, membership assertions and constant symbols in lexicographic order. We denote with A the set of all constant symbols occurring in A. We assume to have an infinite set N of constant symbols not occurring in A. Finally, the set C = A [ N is ordered in lexicographic order. Definition 8. Let K = hT ; Ai be a SDL-LitecoreKB, let T be the set of assertions in T , let n be the number of membership assertions in A, and let N be the set of constants defined above. Assume that the membership assertions in A are numbered from 1 to n following their lexicographic order, and consider the following definition – S0 = A – Sj+1 = fSj n foldg [ ffnewg
Then, we call chase of K, denoted chase(K), the set of membership assertions obtained as the (possibly infinite) union of all Sj , i.e., chase(K) = [
Sj
(2) j2N
The element fold, presented in definition 8, is the axiom whose opinion is being refined by fnew. The membership assertion fnew, numbered with n + j + 1 in Sj+1, is obtained as follows: Definition 9. Let f be the first membership assertion in Sj such that there exists a 2 T applicable in Sj to f , let be the lexicographically first TBox axiom applicable in Sj to f , and let anew be the constant of N that follows lexicographically all constants occurring in Sj case ; f of (cr1) = A1 v A2; f = A1(a) : w; A2(a) : w0 2 S
then fnew = A2(a) : (b(w); d(w0); 1 b(w) d(w0)) (cr2) = A1 v A2; f = A2(a) : w; A1(a) : w0 2 S
then fnew = A1(a) : (b(w0); d(w); 1 b(w0) d(w)) (cr3) = A v 9R; f = A(a) : w; 9R(a) : w0 2 S
then fnew = ga(R; a; anew) : (b(w); d(w0); 1 b(w) d(w0)) (cr4) = 9R v A; f = ga(R; a; b) : w; A(a) : w0 2 S
then fnew = A(a) : (b(w); d(w0); 1 b(w) d(w0)) (cr5) = 9R v A, f = ga(R,a,b) : w, and A(a) : w’ 2 S
then fnew = ga(R; a; b) : (b(w); d(w0); 1 b(w) d(w0)) (cr6) = A1 v :A2; f = A1(a) : w; and A2(a) : w0 2 S
then fnew = A1(a) : (b(w); b(w0); 1 b(w) b(w0)) (cr7) = A2 v :A1; f = A1(a) : w; and A2(a) : w0 2 S
then fnew = A1(a) : (b(w); b(w0); 1 d(w) b(w0)) (cr8) = A v :9R; f = ga(R; a; b) : w; and A(a) : w0 2 S
then fnew = ga(R; a; b) : (b(w); b(w0); 1 b(w) b(w0)) (cr10) = 9R v :A , f = ga(R,a,b) : w, and A(a) : w’ 2 S
then fnew = ga(R; a; b) : (b(w); b(w0); 1 b(w) b(w0)) (cr11) = 9R v :A; f = A(a) : w; and ga(R; a; b) : w0 2 S
then fnew = A(a) : (b(w); b(w0); 1 b(w) b(w0))
It is worth noting that the application of chase rules can be a source of inconsistencies in the ontology. By increasing the belief degree of an opinion (resp. disbelief), we may put it in conflict with its disbelief degree (resp. belief), rendering the opinion invalid. Having an invalid opinion in our KB means that no interpretation will be able to satisfy it.
With the notion of chase in place we can introduce the notion of canonical interpretation. We define can(K) as the interpretation h4can(K); can(K)i, where: – 4can(K)= C – acan(K) = a, for each constant a occurring in chase(K) – Acan(K) : C ! W; such that A(a) : w 2 chase(K) =) Acan(K)(a) = w – P can(K) : C C ! W; P (a1; a2) : w 2 chase(K) =) P can(K)(a; b) = w
We can also define cani(K) = h4can(K); cani(K)i as the interpretation relative to chasei(K) instead of chase(K) .
Lemma 1. Let K = hT ; Ai be a SDL-Litecoreknowledge base, then can(K) is a model of K iff every opinion w that appears in can(K) is valid. tu
( If any of the opinions w that appear in the canonical interpretation is invalid, i.e., b(w) + d(w) > 1, then it is obvious that the canonical interpretation is not a model of K.
) The fact that can(K) satisfies all membership assertions in A follows from the fact that A chase(K). tu Lemma 2. Let K = hT ; Ai be a SDL-Litecore knowledge base, then if can(K) is a model of K, every other model of K is a specialisation of can(K). tu
Let m be a model of K, and m( ) = ! the opinion assigned by m to the assertion 2 K. Let can( ) = !c be the opinion assigned by the canonical model to , with !c !. This means that, according to m, ! is a perfectly valid opinion for . However, since !c is a specialisation of !, we can infer that, while building the chase, there was a semantic constraint applicable to that it is not satisfied by m. Given that there is at least one semantic constraint applicable to that is not covered by m, it is clear that m is not a model of K. We conclude for these reasons that every model of K must be at most as general as can. tu
The implications from lemma 2 are profound and very relevant. Knowing that every model of K is a specialisation of the canonical interpretation, we can focus on answering queries over this canonical interpretation. Any answer that is valid for the canonical interpretation will be valid for any other possible interpretation.
Of course, from a practical point of view, we will never construct the chase nor use directly the canonical model, since it might not be feasible to construct the chase for huge collections of data in a reasonable amount of time. Instead, we will apply the chase rules during the rewriting of the query, in such a way that we simulate the propagation of the beliefs performed during the chase into the final query. Following this approach, we can be sure to obtain a valid answer for our original query, since this will be an answer for the canonical model and, through virtue of lema 2, an answer for any other interpretation of K. 6
It is expected that the capability to handle uncertainty in query answering solutions will be a critical requirement for future applications. Precisely to address this problem we propose a subjective extension of DL-Lite, to combine the efficient query answering properties of DL-Lite with the uncertainty modelling of Subjective Logic. Our main contributions come in the form of the theoretical foundation for the justification of the semantics used in Subjective DL-Lite, and the construction of a canonical model through a chase. We have shown that the theory behind this approach is sound, and could be used to develop a query answering application with support for uncertainty. For our future works we still need to demonstrate that every possible interpretation is a specialisation of the canonical model. Thus, any answer given for the canonical model will be an answer for the rest of the interpretation. Finally, in order to develop our query answering application, we need to define the algorithms that will perform inference over the set of axioms of the ontology and collect the answers to the queries. The initial results are promising, and encourages us to continue in this interesting, though challenging, line of research.