A major challenge in knowledge representation is to manage the access to knowledge: users should not be presented with knowledge that is irrelevant to their topic of interest, or have no right to access. Two general strategies exist for providing access restrictions: (1) the ontology engineers describe the conditions that allow access to speci c fragments of the ontology, or (2) fragments are automatically identi ed through their logical properties. The former is prone to miss logical connections between axioms, while the latter can fail to capture relevant knowledge that has no logical connection with the topic of interest. We de ne the Context-Oriented Decomposition (COD) of an ontology as a technique that combines the bene ts of both approaches: it allows authors to identify relevant fragments, while guaranteeing the strong semantic properties of the logic-based Atomic Decomposition.
Description Logics (DLs) [
In general, ontologies can be very large and contain a high level of detail of
di erent topics within the same general domain. For example, the large-scale
ontology Snomed CT [
One strategy for tacking these issues is to decompose the ontology into
meaningful fragments that can be provided to or hidden from users, depending on their
interests and access rights. Current approaches for decomposing an ontology
can be divided in two main categories: manual author-de ned decompositions
like [
In this paper we present a new approach to ontology partitioning, called context-oriented (atomic) decomposition (COD ), that combines the bene ts of both kinds of approaches, while minimizing their drawbacks: it allows authors to identify fragments of an ontology that may be provided to users under some conditions; and it is based on a well-de ned ontology partitioning, namely the atomic decomposition, that can be e ciently computed and guarantees the fragments obtained to satisfy strong logical properties. 2
We assume familiarity with Description Logics (DLs) [
In general, we call module any subset M of an ontology O such that there
exists a signature Oe for which M is a logical module in O. This notion
of module is based upon the well-known notion in logics of deductive
Conservative Extensions (dCEs), rst discussed for DLs in [
Some (not necessarily minimal) modules satisfy two additional properties:
(1) a module M is depleting if O n M entails only tautologies over the signature
; and (2) M is self-contained if it is a module in O for the signature [ Mf.
Intuitively, depleting modules encapsulate the knowledge of O about , and
no information about is disclosed if the remainder O n M is published; and
self-containment guarantees that all the terms in Mf have the same status w.r.t.
entailments, so that all the terms in Mf are as much constrained in M as they are
in O. Modules satisfying these two properties also satisfy uniqueness : for each
ontology O, a depleting and self-contained module for a signature is uniquely
determined, under some mild conditions on the language used that are always
satis ed by DL ontologies [
The hardness results for minimal modules transfer to the computation of
minimal self-contained and depleting modules. To identify feasible module
extraction algorithms, one line of research in module extraction has been to restrict
the expressivity of the DL to regain decidability; this approach has led to the
identi cation of a polynomial algorithm to extract modules from DL-Lite
ontologies using QBF solvers [
A di erent approach, aiming to allow module extraction from ontologies as
expressive as SROIQ, consists of identifying conditions under which computing
a module is cheap, and the resulting modules are \not too large"; i.e., do not
contain too many super uous axioms. A prominent approach in this direction
exploits the notion of syntactic locality [
Let 2 f>; ?g, and let 0 denote the formula obtained by replacing with the
concept all the terms in that are not in . A syntactic check for -locality
can be performed by testing whether 0 matches one of the syntactical patterns
that guarantee that is a tautology, that can be found in [
Proposition 1 ([
The extraction of a module can be thus performed as follows: (1) de ne M as the set consisting of all the axioms in O that are non -local w.r.t. ; (2) enlarge with Mf; (3) repeat steps (1) and (2) until a xpoint is reached. By Proposition 1, the set M obtained is a depleting module. Moreover, the enlargement of by Mf guarantees that M is also self-contained. The resulting module is called the -module of in O, and is denoted by -mod( ; O).
Due to the coverage property, the extraction of the ?-module for a signature from the >-module for in O is still a module for in O. The converse is also true; that is, the >-module for in the ?-module for in O is still a module for in O. Hence, by iteratively nesting ?- and >-extraction until a xpoint is reached one can get rid of more axioms that are not needed to preserve the entailments of O over . It can be shown that the xpoint does not depend on which notion is applied rst. This uniquely determined new notion of module is called the >? -module of in O, and is denoted by >? -mod( ; O).
Roughly speaking, a >-module for in O gives a view \from above" to
the knowledge about : it contains all the named sub-concepts of any concept
name in ; dually, a ?-module for in O gives a view \from below" since it
contains all the named super-concepts of any concept name in ; a >? -module,
instead, is a subset of both the corresponding >- and ?-modules, containing all
the axioms needed to entail that two concepts in are one a sub-concept of
the other, but not necessarily all their sub- or super-concepts. The results in
this paper can be easily extended to all notions of self-contained and depleting
modules, but for simplicity we restrict our attention to LBMs. For a deeper
discussion on LBMs, see [
OWL [
We can restrict our attention to the building blocks of modules, as de ned
in [
For each atom a, there is a unique smallest module Ga that contains a. Such a module is called genuine. Notably, the set G of the genuine modules of O forms a base of the set F of all the modules of O. In particular, every module of O can be decomposed in a unique way as the union of one or more genuine modules. Moreover, G induces a partial order relation over the set A which is de ned as follows: we say that an atom a depends on another, distinct atom b, and write a b, i for every genuine module G 2 G such that a G, we have that b G. The partially ordered set (A; ) is called the Atomic Decomposition (AD) 3 http://www.co-ode.org/downloads/protege-x 4 http://owlapi.sourceforge.net/ 35 10 21 of O, and its well-foundedness derives from the depletion and self-containment properties of modules. ADs are usually represented by their Hasse diagrams as the one shown in Figure 1. Each genuine module Ga can be found by identifying the corresponding atom a and by taking the union of atoms obtained by chasing the dependence relation .
Example 2. The Common Anatomy Reference Ontology (CARO) is a simple
ontology, available in the ontology repository BioPortal,5 that, in the words of
its developers, aims at \facilitating interoperability between existing ontologies
for di erent species, and at providing a template for building new anatomy
ontologies" [
Figure 1 depicts the ?-AD of CARO, which re ects the hierarchical structure of the ontology. As it can be seen, CARO decomposes into 50 di erent ?-atoms. 46 of these atoms contain only one axiom, and the remaining atoms (a3; a7; a19; and a37 in the gure) contain 2 axioms each. Looking at the graph, we can identify the di erent genuine modules. For instance, a20 de nes the genuine module G20 = a20 [ a38. The atom a39 contains only epithelium v portion of tissue. Three atoms depend on a39: a12 = fatypical epithelium v epitheliumg; a13 = fmultilaminar epithelium v epitheliumg; and a16 = funilateral epithelium v epitheliumg: Although a31 contains the axiom epithelial cell v cell, no logical dependence among a31 and a39 is shown since the ontology does not describe any logical relationship between an epithelial cell and the epithelium. 3
Modules are widely used for ontology reuse as they provide a powerful tool to
identify a part of an ontology preserving the meaning of a signature of interest.
For other tasks, though, the user must understand how the module M relates
to the rest of the ontology. In the following, we describe two such tasks, and
discuss the limitations of using purely logical modules for them.
5 http://bioportal.bioontology.org/
Knowledge Completion (KC). An ontology is an explicit, formal
representation that accounts for the ontological commitment of a particular
conceptualization of the knowledge about a domain [
Access Control (AC). As discussed in Section 2, the signature of a module M
is usually larger than the seed signature , as the reasons for an entailment over
to hold can arise from axioms where no term in is mentioned. Since users are
capable of reasoning, they can then derive logical consequences over the signature
Mf. Thus, the knowledge engineer must ensure that users can only access those
modules that do not implicitly encode any sensitive information, whose access
should be denied. This task is in general infeasible given the exponential number
of possible modules. Restricting the inspection only to genuine modules can still
be impractical since their number is usually close to the number of axioms of
the ontology [
Technically, both KC and AC can be carried out with the help of contexts, and more precisely, modules that preserve the knowledge from a context. De nition 3. Let O be an ontology, L a nite set of labels and lab : O ! 2L a function that maps every axiom to a set of labels. A context is a nite subset C = fC1; : : : ; C g L. Every context C de nes the subontology
RC := f 2 O j lab( ) \ C 6= ;g: This set RC is called the rheme of the context C.6 Intuitively, the set C expresses the conditions under which the ontology RC is accessible to a user. Every user will be associated also to a set of labels from L. If she has at least one label from C, then she can access the whole rheme RC .
If there is no ambiguity regarding the context C, or specifying it is irrelevant in the discussion, we will usually drop the symbol C and write R. In some cases, we may deal with sets of contexts C1; : : : ; C ; to ease the notation, we will then write Ri to denote the rheme of the context Ci, for i 2 f1; : : : ; g. De nition 4. Let O be an ontology, a notion of module, and C a context. The contextual -module for C in O is the set -mod(C; O) = -mod(RfC ; O) [ RC . The signature of this set, C , is called the contextual signature of C. 6 The term rheme is borrowed from linguistics; it refers to \what is said about a theme", in contrast to the theme itself, which may be seen as the title for the rheme.
;
against RfC [ MgC is negative) or ( 2 RC) then
If the ontology O is clear, we will use the notation MC. If, instead, we have a set of contexts C1; : : : ; C , then we denote the corresponding contextual signatures by 1; : : : ; . As the name suggests, a contextual module is also a module. Proposition 5. The contextual -module for a context C in an ontology O is a self-contained and depleting logical module in O for the signature RfC. Proof. By de nition, -mod(RfC; O) is a module for RfC. Then, the result follows by monotonicity of DLs since the contextual module MC is a superset of -mod(RfC; O), and hence since RfC is contained in the signature of the module, it is also a module for RfC with the same properties as -mod(RfC; O). tu Notice that in general MC 6= -mod(RfC; O): in principle the rheme RC could contain tautologies, like OWL declarations, which have no logical in uence on the represented knowledge, but can be helpful for simplifying the work of the reasoners. Since tautologies are logically unnecessary for preserving entailments over RfC, minimal modules over this signature will not include any of them.7 Tautologies, though, can be of interest for users, for example if they are annotated with useful information. For this reason, it is crucial to leave at the discretion of the ontology engineer the choice of including them in rhemes or not.
Contextual modules can be computed by making use of Algorithm 1, which we prove to compute in nite time the contextual module MC for a context C. Proposition 6. Let O be an ontology, a notion of module, and C a context. Algorithm 1 computes the contextual -module for the context C. Proof. Termination follows from the niteness of the ontology: the repeat loop on lines 2-7 terminates when no more axioms can be added to the set MC, and this eventually happens since there is a nite number of axioms in O. Lines 5 and 6 ensure that the output MC of the algorithm contains -mod(RfC; O) [ RC. We need only to prove that the converse inclusion holds.
Suppose that there is some axiom 2 MC n ( -mod(RfC; O) [ RC). W.l.o.g., assume to be -local against the signature of -mod(RfC; O), but not -local 7 In syntactic approximations of modules, like e.g., syntactic locality, some tautologies can still appear since syntactic checks may fail to identify them as irrelevant. against the signature of -mod(RfC; O) [ RC. Notice that the signature of the second term RC equals (thus, it is contained in) the seed signature of the rst term -mod(RfC; O). Thus, the set of all the axioms that are non -local against the signature of -mod(RfC; O) [ RC is already in -mod(RfC; O). tu Computing a contextual module requires a polynomial number of locality checks in the number n of axiom of an ontology O. Since we focus only on the syntactic notions which can be performed in polynomial time on n, it is clear that the whole extraction is overall polynomial in n.
We now take a closer look at the notion of context and its properties. From De nition 3, an axiom can belong to as many contexts as the number ` of possible labels, which could, in principle, be arbitrarily large. On the other hand, ontologies are always nite by de nition. Let n be the cardinality of the ontology. If ` > 2n, then some contexts have the same content; that is, there exists two di erent contexts C1 = fC11; : : : ; Cr1g and C2 = fC12; : : : ; Cs2g such that R1 = R2. In other words, we have two syntactically di erent contexts sharing the same rheme. Since we cannot di erentiate among them, we can equivalently de ne a new context C := C1 [ C2. It is a simple consequence of De nition 3 and the equivalence of R1 and R2 that the rheme for C is R = R1 = R2.
From what we just discussed, it is clear that the number of contexts can be bounded by 2n. Such method leads to a potentially exponential number of different contexts, and hence of contextual modules. In this case, it is hard to check that all of them keep the promise of either completing knowledge or restricting the access to sensitive knowledge. However, ontology engineers can focus their attention to a much smaller sample of contextual modules; there is a base, linear in n, of contextual modules, called genuine, such that every contextual module is the union of a suitable selection of genuine contextual modules. Attentive readers may have noticed that we are reusing the term \genuine" as in the context of ADs. This choice is not due to chance; it is rather a way to emphasize the similarities between the two notions. We formalize and analyse this next. De nition 7. Let O be an ontology, and C the set of all the contexts over O. For each axiom 2 O, de ne the rheme of as RC = f 2 O j lab( ) lab( )g if lab( ) is non-empty, or f g otherwise. A genuine contextual module is a contextual module GC := mod(RfC ; O) for some 2 O.
For each two axioms ; , the condition lab( ) lab( ) means that whoever can access can also access . In particular, GC is the smallest contextual module containing .
Theorem 8 Let O be an ontology. The set of the genuine contextual modules GC = fGC j 2 Og is a base for the set of all the contextual modules in O. Proof. We prove that every contextual module MC coincides with the union of all the modules GC for 2 MC. The inclusion MC S 2MC GC is trivial since every RC contains at least . The converse inclusion also holds since MC contains, for each 2 MC, the rheme RC by construction. tu Since there are at most as many genuine contextual modules as axioms, we have that GC is a linear (in jOj) base of the set of all contextual modules of O. As for ADs, the genuine contextual modules are those contextual modules that never split as the union of two or more contextual modules, which are incomparable by . We want to nd the building blocks of contextual modules. De nition 9. A contextual atom is a maximal subset of axioms aC O such that, for each genuine contextual module GC 2 GC , either aC GC , or aC \GC = ;. Contextual atoms are pairwise disjoint by construction; as for modules, contextual modules are then a nite union of contextual atoms. Since contextual modules are also modules, atoms cannot split across two contextual modules. Similarly, contextual atoms do not split across two contextual modules by construction. Thus, the set AC of all the contextual atoms of O is a coarsening of the set A of all the atoms of O. Moreover, the preservation of logical interrelations between the terms of a contextual atom requires that this atom is always provided to users as a whole. Thus, rhemes can be, ultimately, rede ned to coincide with contextual atoms. Rhemes then contain axioms that are logically or contextually interrelated; that is, RC includes axioms that belong to a same topic according to the knowledge engineer.
De nition 10. Let O be an ontology, C = fC1; : : : ; C g a set of contexts with rhemes R1C ; : : : ; RC , and AC the set of all the corresponding contextual atoms. A partial order relation is induced as follows: for each pair of distinct contextual atoms aC ; bC , we say that aC bC i , if a contextual module GC contains aC , then GC contains also bC . The pair (AC ; ) is called the Context-Oriented Decomposition (COD) of O.
The COD of an ontology can be represented by a dependency graph of contextual atoms. From this graph, ontology engineers may want to identify the fragments of the ontology that are of interest for the needs of its users, and provide them with suitable contexts to access the corresponding subontology. Thus, the issue of identifying the right subontology for each user can be reduced to the de nition of contexts in such a way that the corresponding COD re ects the knowledge engineer modelling of the domain.
We discuss a feasible methodology to generate a suitable set of contexts C and the corresponding fragments of the ontology O from which users are assigned the right to access to the relevant part of O. Rather than de ning all the modules directly, the knowledge engineer may proceed in the following way. First, she can identify relevant but small rhemes RiC . Second, the COD (AC ; ) is computed, and rhemes are rede ned to coincide with contextual atoms. Finally, she de nes suitable labels for each contextual atoms that will form the set of contexts. 4
In this section, we discuss the two applications, Knowledge Completion and Access Control, introduced before, and show how COD can be of help for practical use of ontologies.
Fig. 2. ?-COD of the CARO ontology COD for KC. An analysis of the ?-AD of the CARO ontology reveals how hard it can be to identify which fragment captures everything that an ontology says about a certain topic. The most emblematic example in CARO can be observed already in Example 2: even by chasing sub- and super-concepts, incoming or outgoing role-links to the concept epithelium, a user not familiar with CARO cannot nd the portion of the ontology dealing with epithelial cells. To reveal that these terms are related in the ontological commitment of the CARO ontology, we have grouped the 8 atoms a39; a12; a13; a16; a35; a10 and a21 in rheme R4, and named the context C4 as Epithelium.
In general, two axioms dealing with the same topic may still belong to di erent atoms even when the ontology is supposedly well-modelled. Ideally, we might want that two contextual atoms are distinct only when they deal with di erent topics. To obtain this situation, we can adopt the strategy just described, and merge into a broader contextual atoms all those atoms that deal with the same topic according to the domain experts' knowledge.
In Figure 2 we show the ?-COD of CARO where the atoms are grouped according to the principle just discussed. In speci c: rheme R1, that deals with Immaterial anatomical entity, consists of the atom a26 plus all the atoms that depend on it; R2, dealing with Sexual traits, contains the atoms a8; a17; a22 plus all those that depend on any of these; R3= a25 [ a2, and deals with Acellular anatomical objects; R5= a23 [ a7 [ a19, and deals with Neuron projection; R6, dealing with Compound organ, consists of the atom a32 plus all those that depend on it; R7= a49 [ a24 [ a46, and deals with Anatomic group; nally, R8=a20 [ a15 deals with Portion of substance.
From the ?-COD of CARO, the knowledge engineer will provide the axioms in R4, a4; a40; a5 and a38 to those interested in getting the fragment of CARO that deals with Epithelium.
COD for AC. To exploit the use of COD for AC, the main idea is that users are assigned a set of genuine contextual signatures, which specify the logical symbols over which the user can query the ontology. The coverage properties of logical modules guarantees that reasoning over these modules yields the exact same answers as reasoning over the whole ontology, provided that they refer only to symbols in the genuine contextual signature. Thus, the knowledge engineer can verify that the user cannot derive a consequence, simply by comparing the signature of the consequence with the contextual signatures assigned to the user: if the former is contained in any of the latter, then (and only then) the user can derive the consequence.
Notice that, by de nition, users are not assigned one module, but a set of them. This means that each user can derive the consequences of the union of all the contexts that she can access. For each of these contexts, it is guaranteed that all the consequences of the ontology that refer to its signature are obtained. However, we might want to restrict the access a speci c piece of knowledge, but not to completely obstruct access to its signature. In this case, we can exploit the fact that the union of two modules is not, in general, a module. For example, suppose that we are trying to hide a consequence C v D from a user. To achieve this, it is not necessary to completely prevent the user from accessing none of the concept names C or D. In fact, she can be assigned two signatures 1 and 2 such that C 2 1 and D 2 2, as long as fC; Dg is not contained in any of them. In this way, the user can still derive meaningful consequences concerning each of the concepts C and D, while the subsumption C v D remains hidden.
To fully specify an AC scenario, the knowledge engineer needs only to identify which genuine contextual modules do not cover the signature of the piece of knowledge that some users cannot access. Users are then assigned only contextual signatures that do not contain the signature of any consequence that they are not allowed to see, or which are irrelevant for their intended use. 5
We have proposed a new approach for decomposing ontologies, capable of dealing with contexts de ned by a user or knowledge engineer. This context-oriented decomposition is based on the notions of atomic decompositions, and preserves several of its important properties. Most notably, the COD can be e ciently computed and provides a compact representation of all genuine modules that preserve the given contexts. Intuitively, one can think of contexts as a manner of combining axioms that do not necessarily share logical properties into a single entity. This combination can be motivated by the presence of axioms with disparate signatures, but referring to a common theme.
As working examples, we showed how COD can be used to complete knowledge and to restrict access to some consequences of the ontology in a structured manner. Using COD, a knowledge engineer can easily de ne contexts that can be assigned to di erent users, guaranteeing access to all relevant knowledge, while hiding all unauthorized consequences from them.
Although we have focused our discussion on locality-based modules, and in particular on the three notions of >-, ?-, and >? -modules, it should be noted that our approach is general and can be applied to any desired notion of module. Obviously, the choice of a di erent notion of module can a ect the e ciency of the method; in particular, if modules are hard to compute, then the decomposition will necessarily be also hard to nd.
As future work we plan to further study the logical and computational properties of COD and its applicability to other context-dependent reasoning problems. We are also in the process of developing a tool for computing these decompositions. This tool will allow us to evaluate the practical feasibility of our approach for solving di erent reasoning tasks.