Several tools and techniques have been proposed recently for extracting modules from ontologies. Being focused on some particular application scenario, modularization tools generally rely on their own definitions and intuitions about modularity. In this paper, it is proposed that these different techniques be expressed under a common framework. As most of the existing approaches rely on the traversal of the graph underlying the ontology to harvest relevant entities and axioms, the framework chosen is based on graph transformation. An abstract model for representing ontologies as attributed graphs is described, along with the reformulation of existing module extraction techniques as graph transformation rules. The ultimate goal of this work is to build a parametric modularization tool, enabling application developers to easily compare, apply and combine different approaches for module extraction, or even create entirely new techniques.
Recently, the idea of modularization has gained important attention from the
Semantic Web community, as tools and methods for developing and managing
large ontologies are more and more required. This notion of modularization, or
modularity, comes from software engineering where it relates to the design of
software made of well defined components that can be managed and reused
independently. However, as the definition for a good software module is already
vague [
While they are presented and implemented in different ways, resulting in
different modules, techniques for ontology module extraction are generally based
on similar principles: they rely on the traversal of the graph structure underlying
the ontology to gather entities and axioms considered as relevant for the module.
Each technique relies on its own assumptions, its own rules, about which relations
should be traversed and which entities and axioms should be included. Based
on this observation, it is believed that a graph transformation model [
The proposed framework is based on the structural representation of
ontologies in the form of graphs. Another interesting outcome of this work is that it
provides a basis for studying the limitations of the considered structural
(syntactic) techniques in taking into account the underlying semantics of ontologies.
In particular, we expect difficulties in the integration of approaches relying on
reasoning (like [
In this paper, we provide the initial step towards such a framework. Section 2 presents a brief overview of ontology module extraction. Section 3 investigates a model for representing ontologies as graphs and extraction operations as transformation rules. The intention is to show the feasibility and the interest of such an approach by reformulating several existing module extraction techniques as graph transformation rules. This is done in Section 4. This leads to a discussion in Section 5 on the implementation of a tool for parametric modularization based on the framework presented in this paper. Finally, Section 6 presents the conclusions and future work. 2
This paper only considers techniques for extracting one ontology module from an
existing ontology, what we call ontology module extraction techniques.
Descriptions of other types of modularization techniques, including ontology partitioning
and query based view extraction can be found in [
An ontology is defined as a set of axioms (subclass, equivalence, disjointness relations, etc.) The vocabulary of an ontology O, also called its signature Sig(O), is the set of entity names that are employed in the axioms of O.
The task of module extraction consists in reducing an ontology O to the
sub-part, the module, that covers a particular sub-vocabulary. It has been called
segmentation in [
Several tools implementing more-or-less sophisticated techniques have been
recently proposed, generally focusing on a particular use-case for modularization.
For instance, in [
All these techniques are detailed in Section 4, where they are reformulated within our common, general framework. 3
A Graph Transformation Model for Modularization
The techniques briefly mentioned in the previous section are intended to be used
in different application scenarios. As such, they rely on different intuitions about
ontology modularity and, therefore, generally give different results [
We chose to rely on directed, attributed graphs, as it is a powerful enough
model to represent ontologies written in RDF-S, OWL, or DAML+OIL. The
underlying RDF graph3 model of these formalisms does not contain the features
required by the framework presented. In addition, attributed graphs are the
model implemented in the AGG library4 for graph transformation, therefore
providing an adequate basis for implementation. Below, we employ a simplified
definition for attributed graphs. Details about attributed graphs, their definition
and transformation, can be found for example in [
Attributed graphs. An attributed graph G is a pair (NG, EG), where NG is a set of attributed nodes and EG is a set of attributed edges. An attributed node n = hTn, AVni has a type Tn and a set of attribute values AVn. An attributed edge e = hTe, AVe, Oe, Dei has a type Te, a set of attribute values AVe, an origin node Oe and a destination node De. An attribute value is a pair (a, v) associating a value v to an attribute a.
Ontologies as attributed graphs. Ontology representation languages are mostly based on the RDF model, that is itself based on graphs. In that sense, representing ontologies as attributed graphs is quite straightforward. We consider four types of nodes: Class, P roperty, Individual and Literals. Edge types correspond to properties used to relate different entities. For example, subClassOf is a type of edge that can be used to link nodes of the type Class.
In the case of a named entity (i.e. the entity is associated to an identifier, a URI), this name is used as a value for the attribute name in the corresponding node. For example, if an ontology contains a class C, it would be represented as a node of the type Class, with the attribute value name=C.
In the case of OWL or DAML+OIL, classes (and to some extent properties) can be represented as expressions, using language constructs and other classes or properties. The employed construct is represented in the class node as a value for an attribute named const and special edges are employed to link the corresponding node to the nodes of other entities used in its definition. For example, we use op1 and op2 for the operands of a union (AtB) or an intersection (A u B), as well as p and someV aluesF rom for an existential restriction (∃p.C). A simple example. Following the principles described above, Figure 1 shows the representation as an attributed graph of the expression P ersonW ithDogAndCat ≡ P erson u ∃hasP et.Dog u ∃hasP et.Cat5 3.2
Most of the module extraction techniques are based, explicitly or implicitly, on the idea of traversing the graph underlying the source ontology to collect entities or axioms to be included in the module. The main difference between 3 http://www.w3.org/TR/rdf-mt/ 4 http://tfs.cs.tu-berlin.de/agg/index.html 5 in the description logic syntax. Taken from http://owl.man.ac.uk/tutorial/ twopets.rdf
N1:Class (name=P ersonW ithDogAndCat)
≡ op1 N2:Class (const=u)
N3:Class (name=P erson) op2 N4:Class (const=u)
op1 op2 N6:Class (const=∃) someV aluesF rom p
p N5:Class (const=∃)
someV aluesF rom
N7:Class (name=Dog) N9:Class (name=Cat)
N8:P roperty (name=hasP et) these techniques is the rules they apply to decide wether or not an element has to be included in the module. Therefore, based on the attributed graph model for ontologies, we believe that module extraction techniques can be formulated as graph transformation rules.
Graph transformation rules on attributed graphs. An attributed graph transformation rule R = hLHSR, RHSR, M apRi is composed of an attributed graph LHSR representing the left hand side of the rule (the premise), of an attributed graph RHSR representing the right hand side of the rule (the transformation), and of a set of mappings between LHSR and RHSR. Mappings are either pairs of nodes (n1, n2) or pairs of edges (e1, e2), indicating a correspondence between these two elements in two different graphs. For the sake of simplicity, we consider nodes having the same label and edges of the same type between corresponding pairs of nodes to be implicitly mapped.
of module extraction is to decide which entities and axioms (relations) have to be included in the extracted module. To represent included elements, a particular boolean attribute is used, inc, that can be applied to both nodes and edges. The premiss of a modularization rule generally contains one or more elements having inc=true. The right hand side of such a rule generally contains additional elements marked as included (inc=true).6
Module extraction techniques take as an input a sub-vocabulary of the ontology. This sub-vocabulary represents the starting point for the application of the transformation rules. The first step of the process is therefore to mark the nodes corresponding to the elements of this sub-vocabulary as included. Then, 6 To simplify the notation, we will consider the presence of the inc attribute as representing inc=true. In case there is no indication about inc, it implicitly means inc=f alse. the transformation rules corresponding to the modularization technique are applied (in random order7) until no transformation is applicable. Applying a rule corresponds to matching the left hand side of the rule into a subgraph of the graph representing the source ontology (i.e. finding an isomorphic subgraph) and replacing this subgraph by the one in the right hand side of the rule, taking into account the mappings. Existing graph transformation engines (such as AGG) implement this process and can be used for this purpose.
A very simple modularization technique consists in extracting a sub-tree of the class hierarchy of the ontology, specifying (as the input sub-vocabulary) the root class of this sub-tree. The following transformation rule implements this technique:
Once the input root class is marked as included, the rule is applied recursively until the leaves of the hierarchy are reached, and marked as included. Therefore, at the end of the transformation process, all the entities (nodes) and axioms (edges) representing the considered subtree of the ontology class hierarchy are included in the module. 4
Implementing Modularization Techniques as Graph Transformation Rules Our goal is to provide a common framework for module extraction techniques in which a common mechanism, graph transformation, would be used and parametrized by specialized transformation rules. In order to show the feasibility and the relevance of such an approach, we detail hereafter the reformulation of several techniques (from very simple ones, to more sophisticated) in our graph transformation model for ontologies. Note that, in addition to providing the basis for a tool for parametric, customisable module extraction, this also gives the opportunity to better understand the intuitions, or assumptions, on which the considered techniques rely, and to compare them on a common basis. 4.1
The technique described in [
It takes one or several classes of the ontology as an input, and applies the basic idea that anything that participates (even indirectly) to the description (and so the definition) of an included class has to be included. Therefore the (simplified) reformulation of this technique in our graph transformation framework is straightforward:
A node or an edge marked with the type ∗ can be matched with a node or an
edge of any possible type in the graph model. Note that, according to this rule,
all the super-classes of included classes are included, as well as any definition
associated to included classes or properties. Individuals are not included.
The technique described in [
N1:∗
It is worth noticing that, using this technique, all the sub-classes of the input classes, as well as any entity using this class or other included entities in its definition, will be included.
The above rule is very simple and shows that this module extraction
technique can be easily represented using graph transformation rules. However, it
does not completely translate the corresponding technique, as [
This can easily be handled using the notion of negative application
condition [
In the case of the last technique, adding another boolean attribute input for identifying the input class8, the Negative Application Condition N AC of the rule would be:
NAC N2:Class (inc, input)
disjointW ith
The N AC in that case acts as the expression of an exception to the rule. 4.3
For Knowledge Selection
[
Concerning the use of inferences during the modularization process, instead of taking as a source graph the representation of the elements declared in the ontology, we use the translation of the inferred elements. In particular, in that case, a subClassOf edge in the source graph no longer means that one class is directly declared to be a sub-class of the other, but also that it can be inferred, for example because of the transitivity of the sub-class relation. It is worth mentioning that an incomplete reasoning mechanism could be implemented as part of the graph transformation model, where inference rules on the ontology language would be translated as graph transformation rules. For example, the inferences linked to the fact that the subClassOf relation is transitive can be 8 This attribute can also be specified for other techniques, even if not used. represented by a rule generating new subClassOf relations in the graph, on the basis of existing ones. However, this would represent only a partial solution since this implementation of ontological reasoning would be very incomplete and inefficient compared to existing, tableau based reasoners.
Using the inferred graph, the first rule of the technique is the same as the one of the Galen segmentation service, except that it excludes named classes, which are treated separately.
N2:∗
∗
As explained above, concerning named classes, only the most specific common super-classes of included classes are included in this technique. The most specific super-class C of two classes A and B is a super-class of both A and B such that there is not any other super-class of A and B that is a sub-class of C. This can easily be represented by a combination of the (positive) premiss of the rule and of a negative application condition:
v
NAC
v
v
Note that these two rules make use of the fact that the implicit, indirect
sub-class relations are made explicit. Comparing the rules, and considering that
the ones corresponding to the technique in [
Starting from one class of the considered ontology, Prompt traverses the
relations of this class recursively to include related entities. In that sense, the
principle is similar to the one applied in [
Whilst this first particularity of Prompt, its interactivity, affects only the overall system; the second one introduces a certain level of sophistication in the transformation rules required to implement it. In order to identify selected properties to be traversed, an attribute selected is associated to the node they correspond to. Another attribute is used to represent the maximum recursion level for each of the selected properties. Two rules are considered: one for the first step of the traversal, and one for the following steps.
As we can see, this corresponds to a specialization of the Galen segmentation
service rule, introducing a limitation. Indeed, the Prompt rule applied with all
the properties selected and a level of recursion infinite would give the same result
as Galen. Otherwise, the result would be smaller.
[
This technique clearly shows the limit of our framework based on graph transformation. Indeed, since the first method relies on the use of a reasoner to dynamically realise complex inferences for testing semantic locality, it could not be implemented as graph transformation rules. The second method is based on the syntactic inspection of the axioms of the ontology, looking in particular at the structure of the entities linked by these axioms. Therefore, it should be possible to design a set of transformation rules implementing the test of syntactic locality, and so, the extraction of a module based on this notion. However, the number of rules that are required is too numerous to make this approach really practical. 5
In the previous section, a number of module extraction techniques were reformulated using a common mechanism, graph transformation, parametrized by a specific set of transformation rules. This has shown that the approach is feasible for most of the existing techniques.
The ultimate goal of this work is to build a tool in which the user could select the appropriate technique for his application, and even reuse, combine or create rules from different approaches to build a customised modularization technique. Figure 2 gives an overview of the architecture of such a tool. The components to implement would be the ontology-to-graph and graph-to-ontology converters, in accordance with the model described in Section 3. As already mentioned, we can rely on existing tools and libraries of graph transformation engines. The ontology-to-graph and graph-to-ontology converters will be able to take an ontology file as input or interface with a triple store, such as Jena9.
The techniques described in the previous section provide an initial pool of
rules that can be reused and combined. It could, for example, be possible to
add the recursion level of Prompt [
Also, a natural progression for such a tool would be to allow the user to interactively build modules. It is unlikely that any one module extraction technique would extract a module that meets the requirements of the user and their 9 http://jena.sourceforge.net/ particular application. Thus, in the same way as Prompt allows, once an initial module is created, to refine it by choosing a new starting point. It would be interesting to build a module interactively, and iteratively, letting the user choose a different sub-vocabulary and a different set of transformation rules at each step. In this way, by controlling how the elements of the original ontology are to be included in the extracted modules, the user could build modules that match the requirements of their application. In this paper, we have shown that, even if they are based on different assumptions and implementations, most of the ontology module extraction techniques rely on the same principles and can be reformulated in a common framework based on graph transformation. By reformulating existing techniques as graph transformation rules, the feasibility of such a framework has been shown. The interests of this work are multiple. First, having modularization techniques gathered together in the same format facilitates their comparison and evaluation. It is simpler for the user to understand them, match them to his requirements, and apply them. Second, this leads to the development of a parametric modularization tool, in which the parameters are the rules to apply for module extraction. The reformulated techniques provide an initial pool of rules to chose from and to combine to build the adequate technique in a given application scenario. In addition, this tool would give the possibility to easily (visually, graphically) build entirely new modularization techniques by editing, modifying and creating new module extraction rules, enabling application developers to obtain specialised modularization techniques, without having to re-implement a new tool or modify an existing one.
The obvious next step of this work is the implementation of such a tool, requiring the consideration of a number of different aspects, as described in Section 5. Moreover, in order to facilitate the exploitation of this tool, and the manipulation of modularization techniques as graph transformation rules, this parametric modularization tool should be integrated within an ontology development environment, such as Prot´eg´e.
Whilst reformulating the existing techniques into the graph transformation
framework presented in this paper, it became clear that some elements and
features are not easily represented in graph transformation rules. In particular,
when trying to reformulate [
Another interesting direction for future work would be to consider the
reformulation of the partioning techniques, such as [
A full comparison between the set of rules needed for each reformulated technique will be completed. This will, hopefully, provide a solid theoretical comparison that would allow the user to better select which approach best fits their needs.
Also, there is the need to consider scalability issues. With the framework presented in this paper it is assumed that the whole ontology will be transformed into a graph, which does not make sense in the cases where modularization is used as a way to improve the performance of ontology tools, by considering only a part of the original ontology. One possible solution to this scalability problem would be to build the graph on the fly, as transformation rules are applied, rather than building the whole graph in the beginning and then doing the extraction.