The problem of linking entities in heterogeneous and decentralized data repositories is the driving force behind the data and knowledge integration effort. In this paper, we describe our probabilistic-logical alignment system CODI (Combinatorial Optimization for Data Integration). The system provides a declarative framework for the alignment of individuals, concepts, and properties of two heterogeneous ontologies. CODI leverages both logical schema information and lexical similarity measures with a well-defined semantics for A-Box and T-Box matching. The alignments are computed by solving corresponding combinatorial optimization problems.
1.1
CODI (Combinatorial Optimization for Data Integration) leverages terminological
structure for ontology matching. The current implementation produces mappings between
concepts, properties, and individuals including mappings between object and data type
properties. The system combines lexical similarity measures with schema information
to reduce or completely avoid incoherence and inconsistency during the alignment
process. The system is based on the syntax and semantics of Markov logic [
Markov logic combines first-order logic and undirected probabilistic graphical
models [
T-Box Matching Formalization Given two ontologies O1 and O2 and an initial apriori similarity measure σ we apply the following formalization. First, we introduce observable predicates O to model the structure of O1 and O2 with respect to both concepts and properties. For the sake of simplicity we use uppercase letters D, E, R to refer to individual concepts and properties in the ontologies and lowercase letters d, e, r to refer to the corresponding constants in C. In particular, we add ground atoms of observable predicates to F h for i ∈ {1, 2} according to the following rules1: Oi |= D ⊑
E 7→ subi(d, e) Oi |= D ⊑ ¬
E 7→ disi(d, e) Oi |= ∃R.⊤ ⊑
Oi |= ∃R.⊤ ⊒ Oi |= ∃R.⊤ ⊑ ¬
D 7→ subid(r, d) D 7→ supid(r, d) D 7→ disid(r, d) The ground atoms of observable predicates are added to the set of hard constraints F h, forcing them to hold in computed alignments. The hidden predicates mc and mp, on the other hand, model the sought-after concept and property correspondences, respectively. Given the state of the observable predicates, we are interested in determining the state of the hidden predicates that maximize the a-posteriori probability of the corresponding possible world. The ground atoms of these hidden predicates are assigned the weights specified by the a-priori similarity σ. The higher this value for a correspondence the more likely the correspondence is correct a-priori. Hence, the following ground formulae are added to F s: (mc(c, d), σ(C, D)) (mp(p, r), σ(P, R)) if C and D are concepts if P and R are properties Notice that the distinction between mc and mp is required since we use typed predicates and distinguish between the concept and property type.
Cardinality Constraints A method often applied in real-world scenarios is the
selection of a functional one-to-one alignment [
mc(x, y) ∧ mc(x, z) ⇒ y = z mc(x, y) ∧ mc(z, y) ⇒ x = z Analogously, the same formulae can be included with hidden predicates mp, restricting the property alignment to be one-to-one and functional. 1 Due to space considerations the list is incomplete. For instance, predicates modeling range restrictions are not included.
Coherence Constraints Incoherence occurs when axioms in ontologies lead to logical contradictions. Clearly, it is desirable to avoid incoherence during the alignment process. All existing approaches to alignment repair remove correspondences after the computation of the alignment. Within the ML framework we can incorporate incoherence reducing constraints during the alignment process for the first time. This is accomplished by adding formulae of the following type to F h.
dis1(x, x′ ) ∧ sub2(x, x′ ) ⇒ ¬(mc(x, y) ∧ mc(x′ , y′ ))
dis1d(x, x′ ) ∧ sub2d(y, y′ ) ⇒ ¬(mp(x, y) ∧ mc(x′ , y′ ))
Stability Constraints Several approaches to schema and ontology matching
propagate alignment evidence derived from structural relationships between concepts and
properties. These methods leverage the fact that existing evidence for the equivalence
of concepts C and D also makes it more likely that, for example, child concepts of C
and child concepts of D are equivalent. One such approach to evidence propagation is
similarity flooding [
The presented list of cardinality, coherence, and stability constraints could be extended by additional soft and hard formulae. Other constraints could, for example, model known correct correspondences or generalize the one-to-one alignment to mto-n alignments.
A-Box Matching The current instance matching configuration of CODI leverages
terminological structure and combines it with lexical similarity measures. The approach
is presented in more detail in [
Analogous to the concept and property alignment before, we introduce the hidden predicate mi representing instance correspondences. Let C be a concept and P be a property of T-Box T . Further, let A ∈ A1 and B ∈ A2 be individuals in the respective A-Boxes. Then, using a reasoner, ground atoms are added to the set of hard constraints F h according to the following rules:
T ∪ A1 |= C(A) ∧ T ∪ A2 |= ¬C(B)
T ∪ A1 |= ¬C(A) ∧ T ∪ A2 |= C(B)
T ∪ A1 |= P (A, A′ ) ∧ T ∪ A2 |= ¬P (B, B′ )
T ∪ A1 |= ¬P (A, A′ ) ∧ T ∪ A2 |= P (B, B′ )
7→ ¬mi(a, b)
7→ ¬mi(a, b)
7→ ¬mi(a, b) ∨ ¬mi(a′ , b′ )
7→ ¬mi(a, b) ∨ ¬mi(a′ , b′ )
In addition to these formulae we included cardinality constraints analogous to those
used in the concept and property matching of Section 1.2. In the instance matching
formulation, the a-priori similarity σc and σp measures the normalized overlap of concept
and property assertions, respectively. For more details on these measures, we refer the
reader to [
The strength of the system is its modularity allowing the incorporation of different
similarity measures. The system can be optimized in two major ways: (a) Inclusion of novel
formulae enforcing the logical consistency and (b) the inclusion of additional similarity
measures. There is room for improvement since we used a very simple lexical
similarity measure based on the Levenshtein distance [
In all OAEI test cases Algorithm 1 was used for computing the a-priori similarity σ(entity1, entity2). In the case of concept and property alignments, the a-priori similarity is computed by taking the maximal similarity between the URIs, labels and OBO to OWL constructs. In case of instance matching the algorithm goes through all data properties and takes the average of the similarity scores. 1.4
CODI can be downloaded from http://codi-matcher.googlecode.com. 1.5
The alignments for the tracks Benchmark and Conference has been made with the SEALS platform. For Anatomy, IIMB, and Restaurant the alignments can be found at http://code.google.com/p/codi-matcher/downloads/list 2
In the following section, we present the results of the CODI system for the individual OAEI tracks. Due to space considerations, we do not explain the different benchmarks in more detail.
Algorithm 1 σ(entity1, entity2) Benchmark Track While our system’s strength is its modularity and adaptability to different ontologies we used the exact same setting for all ontology matching tracks. Hence, the performance on the benchmark track is rather poor. This is primarily due to the high threshold of 0.85 for the Levenshtein similarity measure that we applied in each of the ontology matching tracks. The results are shown in Table 1. Conference Track On the real-world conference dataset CODI achieves very good results since it employs logical reasoning to avoid incoherences. The execution time is between 2 and 4 minutes per test case2. Table 2 summarizes the overall results. Anatomy Track The results on the anatomy track are also convincing. The results shown in Table 3 are en par with the 2009 results of state-of-the-art matching applications. The F1 scores are between 0.79 and 0.73 for all subtasks, even for the two tasks Focus on Precision and Focus on Recall. Thus, our algorithm achieves satisfiable precision and recall values without sacrifices on the F1 score. For the last task, where a partial reference alignment was given, we could gain almost 5 % on the F1 score. This is because incorporating a partial reference alignment in our system is straight-forward. The reference alignment becomes a direct part of the optimization problem, enforcing good correspondences while ruling out contradicting ones. However, since our algorithm uses logical reasoning and has to solve an NP-hard optimization problem, the execution times are quite high3. 2 All experiments are executed on a Desktop PC with 2 GB RAM and a Intel Core2 Duo 2.4
GHz processor. 3 This forces us to submit the solutions without the seals platform because of a timeout after 45 minutes.
IIMB Track The instance matching benchmark IIMB consists of 80 transformations divided in four transformation categories containing 20 transformations each. We applied the full A-Box matching functionality described above with a threshold on the a-priori similarity of 0.1. The average execution time on the IIMB small (large) dataset is 2.6 (35.1) minutes. Table 4 summarizes the different results of the CODI system. The values without brackets are the results for the small IIMB dataset and the values in brackets for the large one.
Transformations Precision Recall F1 score PR Track For this track consisting of small files about persons and restaurants, we used a simple one to one alignment only based on lexical similarity scores since no significant structural information is available. Thus, the runtime was with less than 5 seconds per test case very short. The results of the CODI system are depicted in Table 5.
CODI is a very young system and does not yet provide a user interface. Hence, improvements in usability by designing a suitable user interface will be one of the next steps. In case of the quality of the alignments, more sophisticated lexical similarity measures will be tested and integrated. We are also working on novel algorithms solving the optimization problems more efficiently. 3.2
The SEALS evaluation campaign is very beneficial since it is the first time that the matchers must have a standardized interface which could possibly be used by everyone. 3.3
We encorage the organizers to use semantic precision and recall measures as described
in [
CODI performs concept, property, and instance alignments. It combines logical and structural information with a-priori similarity measures in a well-defined way by using the syntax and semantics of Markov logic. The system therefore not only aligns the entities with the highest lexical similarity but also enforces the coherence and consistency of the resulting alignment.
The overall results of the young system are very promising. Especially when considering the fact that there are many optimization possibilities with respect to the lexical similarity measures that have not yet been investigated. The strength of the CODI system is the combination of lexical and structural information and the declarative nature that allows easy experimentation. We will continue the development of the CODI system and hope that our approach inspires other researchers to leverage terminological structure for ontology matching.