One of the main challenges in knowledge representation and reasoning is still to cope with vague and imprecise information in an adequate manner. This imprecision is found in many knowledge domains, particularly medicine and life sciences. A typical source of imprecision in these domains arises from the level of detail in which the knowledge is described. For example, a disease is usually diagnosed through a series of symptoms that a patient presents, but two individuals, say Ana and Bob, showing the same symptoms might in fact suffer from different maladies. Thus, while these individuals might be equivalent from a symptomatic point of view, they might be classified into different illness classes. One of the many approaches suggested for handling imprecise knowledge is based on rough approximations. Generally speaking, the individuals in a domain are partitioned into equivalence classes, based on their indiscernibility according to the current level of detail. An individual belongs to the upper approximation of a class C (denoted C), if it is indiscernible from some element of C. For instance, Ana and Bob are in the same symptomatic equivalence class. If Bob is diagnosed with, say the Cooties, then Ana potentially has the Cooties, too. In rough terminology, Ana is in the upper approximation of Cooties (Cooties). An analogous lower approximation of a class can be defined, too. Intuitively, C contains the prototypical elements of the class C: if an element x belongs to C, then every element indiscernible from x is guaranteed to belong to C. Rough extensions of Description Logics (DLs) [1] have been proposed as a formalism for handling these upper and lower approximations [5]. An important example is the rough DL ELρ, which extends EL with two new rough constructors. Formally, ELρ concepts are built from concept names A and role names r through the grammar rule C ::= A | > | C u C | ∃r.C | C | C. The semantics of this logic is based on interpretations I = (ΔI , ·I , ρI ) that extend standard interpretations by an equivalence relation ρI over the elements of ΔI . The interpretation function is extended to the classical constructors in the usual way, and to the rough constructors by setting (C)I = {x ∈ ΔI | ∃y ∈ CI .xρI y}, (C)I = {x ∈ ΔI | ∀y ∈ ΔI .xρI y ⇒ y ∈ CI }.
xA r A, C xC
A
C r
[xB] r C, B B
B
[xC] (b)
It has been shown that standard reasoning, such as subsumption or instance
checking is decidable in this logic in polynomial time [
Interestingly, there is a very tight connection between canonical models for EL knowledge bases, and those for ELρ knowledge bases. In EL, the canonical model has a domain element xC for every concept appearing in the KB. This element xC acts as a representative for the concept C, and every concept containing this element is guaranteed to be a subsumer of C. In the case of ELρ, the canonical model can be understood as a more detailed view into the classical canonical model for EL. While each concept C appearing in the KB still produces a representative xC , this representative defines a whole equivalence class, rather than a single domain element. This equivalence class, in turn, provides all the information regarding the upper and lower approximations of the concept C. This intuition is depicted in Figure 1. For example, the interpretation in part (b) of the figure expresses that A v C, through the auxiliary node in the class [xA], and that C v B, through the distinguished auxiliary (diamond shaped) element in the class [xC ]. Notice that this figure does not depict the whole canonical interpretation; some conclusions are missing from it.
Canonical interpretations are helpful for answering conjunctive queries w.r.t.
EL knowledge bases [
[xA]
We exploit the connection between canonical models, and provide a combined approach for conjunctive query answering in ELρ.
Answering Rough Queries in ELρ As mentioned already, the canonical interpretation I of an ELρ KB K provides a compact representation of all models of K from which all the subsumption and instance relationships among the individual and concept names that appear in K can be easily read. While all instance queries can be easily answered from this interpretation, for conjunctive queries the situation is more complex. The issue with answering conjunctive queries over the canonical interpretation arises from the succinctness of this interpretation. Mainly, in this interpretation there is one domain element xC that represents the whole concept C. Thus, two individual names a, b that belong to the concept ∃r.C will have the same r-successor xC in I, although in general these successors need not be the same.
Clearly, since ELρ is an extension of EL, all the rewriting rules for query answering in EL are also required in the rough setting. However, the structure of the canonical model of an ELρ KB is more complex: each symbol gets a representative equivalence class, which is needed to convey the rough approximations of the concepts. Thus, some elements are connected by an equivalence relation, that can be understood as a symmetric, transitive and reflexive role ρ. This special kind of role needs to be treated carefully to avoid erroneous answers to a query. As a simple example, consider the KB K0 containing the assertion ∃r.A(a) and the GCI A v ∃r.A. The canonical interpretation of this KB is depicted in Figure 2. The query φ(x) = ∃y, z.r(x, y) ∧ ρ(y, z) ∧ r(z, y) over this interpretation would return a as an answer, although it is not true that a satisfies this property in all models of K0. It is thus important to adapt the rewriting technique to handle also the equivalence relation that the rough constructors and the role assertions for ρ yield.
We give a computation algorithm following the combined approach for
answering conjunctive queries in the rough DL ELρ. As in case of EL, the approach
consists in computing the canonical interpretation I that simulates all models
of the input KB K, which can be done in polynomial time. This interpretation is
first used as a guideline for rewriting the conjunctive query φ into a first-order
query φb, and then as the finite domain over which φb is answered. As a result,
we obtain an effective method for answering conjunctive queries that can handle
imprecision described as rough approximations of a concept or as indiscernibility
information using ρ in role assertions. The full details can be found in [