Markov logic combines first-order logic and undirected probabilistic graphical models [11]. A Markov logic network (MLN) is a set of first-order formulae with weights. Intuitively, the more evidence there is that a formula is true the higher the weight of this formula. It has been proposed as a possible approach to several problems occurring in the context of the semantic web [2]. We have shown that Markov logic provides a suitable framework for ontology matching as it captures both hard logical axioms and soft uncertain statements about potential correspondences between entities. The probabilistic-logical framework we propose for ontology matching essentially adapts the syntax and semantics of Markov logic. However, we always type predicates and we require a strict distinction between hard and soft formulae as well as hidden and observable predicates. Given a set of constants (the classes and object properties of the ontologies) and formulae (the axioms holding between the objects and classes), a Markov logic network defines a probability distribution over possible alignments. We refer the reader to [9,8] for an in-depth discussion of the approach and some computational challenges. For generating the Marcov logic networks we used the approach described in [12].

Given two ontologies O 1 and O 2 and an initial apriori similarity measure σ we apply the following formalization. First, we introduce observable predicates O to model the structure of O 1 and O 2 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 rules 1 :

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 m c and m p , 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)) if C and D are concepts (mp(p, r), σ(P, R))

if P and R are properties

Notice that the distinction between m c and m p 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 [1]. Within the ML framework, we can include a set of hard cardinality constraints, restricting the alignment to be functional and one-to-one. In the following we write x, y, z to refer to variables ranging over the appropriately typed constants and omit the universal quantifiers.

Analogously, the same formulae can be included with hidden predicates m p , restricting the property alignment to be one-to-one and functional.

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

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 [7]. As a reciprocal idea, the general notion of stability was introduced, expressing that an alignment should not introduce new structural knowledge [5].

The soft formula below, for instance, decreases the probability of alignments that map concepts X to Y and

Here, w 1 and w 2 are negative real-valued weights, rendering alignments that satisfy the formulae possible but less likely.

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.

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 [10].

In cases with two different T-Boxes the T-Box matching approach is applied as a preprocessing step, merge the two aligned T-Boxes and then use our instance matching algorithm. CODI offers complete conflict elimination meaning that the resulting alignment is always coherent for OWL DL ontologies. This component is based on the work of Meilicke et al. [6]. CODI enforces the instance alignment to be consistent. To this end, we need to introduce observable predicates O to model conflicts, that is, a positive assertion of one instance in one ontology and a negative assertion of the same instance in the other ontology. This is done for both property and concept assertions.

Analogous to the concept and property alignment before, we introduce the hidden predicate m i representing instance correspondences. Let C be a concept and P be a property of T-Box T . Further, let A ∈ A 1 and B ∈ A 2 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:

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 [10]. The following formulae are added to the set of soft formulae F s :

if A, B, C, and D are instances

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 [4] for our experiments. It is possible to apply different aggregation functions like average or maximum and to include specific properties of an ontology like URIs, labels, and comments. In all OAEI test cases Algorithm 1 was used for computing the a-priori similarity σ(entity 1 , entity 2 ). 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.

CODI can be downloaded from http://codi-matcher.googlecode.com.

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

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. 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.

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 F 1 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 F 1 score. For the last task, where a partial reference alignment was given, we could gain almost 5 % on the F 1 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 .

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. 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.

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.

We encorage the organizers to use semantic precision and recall measures as described in [3].

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.