With growing popularity of ontologies as semantics-aware integration solutions, various ontology merging methods have been proposed. Each of them uses their own set of criteria to determine a desirable merge result. In this work, we rst categorize these criteria into generic merge requirements (GMRs). Not all of these requirements can be met simultaneously. We argue that users should be able to select those requirements that are most important to them, but that system support is required to determine a compatible set of requirements based on user inputs. We propose a graph-theory based approach to determining such sets.
An ontology is a formal explicit description of a domain. It contains a set of entities including classes, properties, and instances. Given a set of input ontologies and a set of correspondences between them, an ontology merging process creates a new merged ontology. One aspect that various approaches to ontology merging di er in is the set of criteria they aim to ful ll, i.e., what are the requirements they expect the merged ontology to meet. We have conducted an analysis of the literature and determined which criteria, here called generic merge requirements (GMR), are used by di erent approaches. Our ultimate aim is to provide a exible merging approach, where users can actively choose which requirements are important to them, instead of allowing only a very indirect choice by picking the right merging method, something that is not transparent to the user. Unfortunately, not all GMRs are compatible with each other. For instance, one may want to preserve all classes contained in the original ontology in the merged ontology. On the other hand, one could wish to achieve class acyclicity. Likely, these goals con ict. Thus, once a user has chosen which GMRs they consider important, a system is needed that is able to check whether these are compatible and which other requirements can be met simultaneously.
In this paper, we take the rst step towards this goal: We analyse the literature to compile a list of GMRs, we provide rst insights into their compatibility and we describe a graph-theory based method for determining maximal sets of compatible GMRs.
Completeness . Class preservation . Property preservation . Instance preservation 4. Correspondence preservation 5. Correspondences’ Property
preservation 6. Property’s value preservation 7. Structure preservation
Integrity
Minimality 8. Class redundancy prohibition 9. Property redundancy
prohibition . Instance redundancy
prohibition . Extraneous entity prohibition
Deduction 12. Entailment deduction satisfaction
Constraint . One type restriction 14. Property value’s constraint . Property’s domain and
range oneness Model Properties
Acyclicity . Acyclicity in the class hierarchy . Acyclicity in the property
hierarchy 18. Prohibition of properties being inverses of themselves
Connectivity 19. Unconnected class prohibition . Unconnected property
prohibition
Legend Dimension Aspect GMR
To discover the most commonly used GMRs, we have studied and analyzed three
di erent research areas including (i) ontology merging methods [
We determined six aspects that GMRs can be grouped into:
Completeness refers to knowledge preservation and coverage:
R1. Class preservation: Each class in (all/target) 1 input ontologies should have
a mapped class in the merged ontology [
R2. Property preservation: Each property from the (all/target) input ontologies
is explicitly in or implied by the merged ontology [
R3. Instance preservation: All instances of (all/target) input ontologies should
be preserved in the merged ontology [
R4. Correspondence preservation: If two entities of the input ontologies are
corresponding 2, both should map to the same merged entity in the merged
ontology [
R5. Correspondences' property preservation : If any of the corresponding entities
from the input ontologies has a certain property, the merged entity should
also have this property [
R6. Property's value preservation : Properties' values from the (all/target) input
ontologies should be preserved in the merged ontology [
R7. Structure preservation : If two entities are connected via a certain property
in an input ontology, their mapped entities in the merged ontology should be
connected via the respective mapped property [
Minimality refers to knowledge redundancy and controlling of semantic overlap:
R8. Class redundancy prohibition : A class from the (all/target) input ontologies
should have at most one mapping in the merged ontology [
Deduction refers to the deduction satisfaction with R12 :
R12. Entailment deduction satisfaction : The merged ontology is desirable to be
able to entail all entailments of the (all/target) input ontologies [
Constraint re ects the satisfaction of the ontology constraints:
R13. One type restriction: Two corresponding entities should follow the same data
type [
R14. Property value's constraint : If the (all/target) input ontologies place some
restriction on a property's values (e.g., in terms of cardinality or by
enumerating possible values) this should be preserved without con ict in
the merged ontology [
R15. Property's domain and range oneness : The merge process should not result
in multiple domains or ranges de ned for a single property. This rule is recast
from the ontology modelling issues in [
Acyclicity refers to controlling the chain problem in the merged ontology:
R16. Acyclicity in the class hierarchy : A cycle of is-a relationships implies equality
of all of the classes in the cycle, since is-a is transitive. Therefore, the merge
process should not produce a cycle in the class hierarchy [
R18. Prohibition of properties being inverses of themselves : The merged process
should not cause an inverse recursive de nition on the properties [
Connectivity refers to the hierarchy connectivity satisfaction:
R19. Unconnected class prohibition : The merge process should not make the
classes unconnected [
R20. Unconnected property prohibition : The merge process should not make the
properties unconnected [
Intuitively, not all GMRs are compatible, e.g., completeness and minimality are di cult to achieve simultaneously. In our ongoing work, we are determining the precise relationships. Typically, users will, however, not be interested in all of them anyhow. Depending on the application they want to create an ontology for, some GMRs might be important to them while others are only nice to have. We therefore propose an approach that takes as input a set of user-selected GMRs, namely U and an undirected graph G re ecting the relationship among GMRs. G = (V; E ), where V is the set of vertices representing the GMRs, and E is the set of edges. Two GMRs are connected via an edge i they are compatible.
Given the set U containing the GMRs the user is interested in, we nd the maximum subset of V containing all vertices out of U and no incompatible nodes. This may not always be possible, since the user might have chosen incompatible GMRs already. In this case, we search for a maximum subset of V that preserves as many nodes out of U as possible and contains compatible nodes only.
Precisely, we recast the problem at hand as maximum clique extraction on G.
A clique is a set of fully connected vertices. We thus extract a compatible clique
KC -Clique, where K indicates the number of vertices in the clique, and C denotes
that the clique is compatible. KC -Clique includes compatible GMRs from U and
some additional compatible GMRs related to U 's elements. KC -max-Clique, is a
clique containing at least K vertices that is not a subset of any other cliques. To
compute the KC -max-Clique, we use the CLIQUES algorithm in [
To illustrate our approach with an example, Fig. 2 left shows the graph G, for six GMRs where U = fR2; R8; R11g. Based on this graph, three di erent cliques have been extracted, in which the user-selected compatible GMRs, the incompatible U 's elements, and the additional compatible GMRs related to U are indicated with green, red, and yellow circles, respectively. Two possible represented 3C -Clique are compatible cliques however they are not a maximal clique. The 4C -max-Clique is the best match to the U and indicates the maximal compatible subset on the sketched G. Fig. 2: From left to right: a graph G for six GMRs; two di erent compatible 3C -Clique; a compatible 4C -max-Clique. 4
There is a variety of generic merge requirements (GMR) in the ontology engineering domain. We gathered the most common GMRs 3, and classi ed them into three dimensions. Since not all GMRs can be ful lled at the same time, we propose an approach that allows users to specify the most important GMRs for their speci c task, then determines the maximal compatible subset of GMRs. This result can then be used to select a proper merge method or to parameterize a generic merge method. We are currently working on two aspects of this problem: First, a systematic determination of GMR compatibility and second the development of a generic, parameterizable merge method.
Acknowledgments. S. Babalou is supported by a scholarship from German Academic Exchange Service (DAAD). 3 see also: http://comerger.uni-jena.de/requirement.jsp