In this section, our discussion is divided into two parts. Two scoring functions are discussed in the first subsection, while the search algorithm is discussed in the second subsection.

Before the main discussion, we introduce several types of cardinality constraints in schema matching, which are the prerequisite of the scoring functions. The cardinality constraint is an important feature of the ER-diagram in the database. The constraints usually state instructions of the form “every person has exactly one mother”, or “every course must have at least one teacher”. They are very useful, because they allow the logical integrity of the database to be maintained. The cardinality constraints in schema matching are similar to the one in the database. Given two sets of attributes, the cardinality constraints state how many attributes in one set should hold correspondences with attributes in the other set. Thus, given a mapping, these constraints play an important role in the behavior of a scoring function. We will analyze the effect of these constraints on the scoring function in detail, in the remainder of this section. In our approach, we consider three types of cardinality constraints: one-to-one mapping, onto mapping, and partial mapping, which are first proposed in [2]. For two input schemas S₁ and S₂ to be matched, the three types of cardinality constraints are described as follows:

1) One-to-one mapping: For each attribute in S1, there exists one and only one corresponding attribute as the counterpart in S2, and vice versa. If the two schemas S1 and S2 are referred to as two sets and the mapping is referred to as a function, we can see that this function is the so-called bijective mapping in discrete mathematics, i.e., it is both surjection and incidence.2) Onto mapping: For each attribute in S1, there exists a unique attribute in S2 as a match. Conversely, each attribute in S2 either has one and only one attribute in S1 as a match, or remains unmatched. Compared to the one-to-one mapping, this mapping actually falls into the class of incidence.3) Partial mapping: Each attribute in S1 either has one and only one attribute in S2 as a match, or remains unmatched, and vice versa. In practice, this case is the most general and difficult one. The reason is that for an attribute in one schema, the existence of its match (counterpart) in another schema is unknown (uncertain); for a schema, the number of its attributes that have matches in another schema is unknown.

These three types of cardinality constraints are very prevalent in practice, as opposed to the case where an attribute in one schema has multiple matches in another schema, so in the proposed approach we do not consider this kind of cardinality constraint.

In essence, a scoring function is a function that takes some parameters of some entity, or some quantitative features of some model or some procedure as input, and then outputs a final numeric value (score), as a measurement of inputs. It is also a mapping from a set of parameters to a final numeric value. It is a computation rule, which embodies some measurements about what is good or bad, between inputs and the final score. The computation rule is the important component of the scoring function, because a set of appropriate rules is the key to obtaining an accurate final score. The problem of how to create an effective scoring function to evaluate the quality of matching has been discussed in [2]. They proposed two scoring functions, and addressed the problem of the monotonicity of scoring functions. They classified their scoring functions into monotonic and non-monotonic. Given the mapping, we exploit their scoring functions as the measurement of similarity of feature matrices in our approach. As in [5], we introduce some formal descriptions about schema matching. Let S₁ and S₂ be two schemas to be matched. Given their respective feature matrices, the matching task is to find the optimal mapping that gives the highest score for a specific scoring function. Consequently, any mapping m should provide three kinds of information for the scoring function. The first is the number of matches (matched attributes) included in m, denoted as k_m; the second is the attributes occurring in m, denoted as ｛a₁, ..., a_i, ..., a_km｝ for S₁ and ｛b1, ..., bj, ..., bkm｝ for S₂; and the third is the actual correspondences between attributes of S₁ and S₂, i.e., m(a_i) = b_j (m(_i) = j). Here, it should be noted that k_m is the number of matches in m, rather than the number of correct matches in m. For two feature matrices, they are required to have the same number of rows and columns for the computation of similarity. Thus, if the number of their rows and columns is not equal, additional rows and columns with values 0 are added to the end of the corresponding matrix. Now, we present the definition of the monotonic scoring function.

DEFINITION 2. Let P₁ and P₂ be the two feature matrices collected from the query logs of schemaS₁ and S₂, respectively, and n be the number of the rows of P₁ and P₂. Let aij be an entry in P₁, which represents the statistics about attribute ai appearing in position j, while bij is an entry in P₂, which represents the statistics about attribute bi appearing in position j. Given a mapping m, the monotonic scoring function is defined as:

Given the mapping m, this scoring function employs the Euclidean distance metric to measure the similarity between two feature matrices. Let d_m(P₁, P₂) be the Euclidean distance above, i.e., the square root item. We can see that d_m(P₁, P₂) increases monotonically with the increase of the number of matches in m; that is, this function is monotonic in k_m. For example, let m₁ = (a₁, b₁), m₂ = (a₁a₂, b₁b₂) be two mappings. If n is set to 2, then d_m1(P₁, P₂) is (a₁ – b1)₂, and d_m2(P₁, P₂) is (a₁ − b₁)² + (a₂ − b₂)². As a result, d_m2 is equal to or greater than d_m1, because of (a₂ − b₂)² ≥ 0; that is, the score decreases monotonically with the increase of km. Given two schemas to be matched, if the correct k_m is unknown, the matching algorithm using this function will just return the mapping with only one match as , because the score of any mapping with more than one match will be smaller than the one with only one match. As a result, this function can be used to achieve the one-to-one mapping and the onto mapping problems where the km is known, and as the input of search algorithms, rather than the partial mapping problem. The variable ub takes the value that is the upper bound to the value of d_m(P₁, P₂); and this guarantees that the value of the function is positive. In the following, we will discuss the non-monotonic scoring function.

DEFINITION 3. Let P₁ and P₂ be the two feature matrices with n rows. Let aij be an entry in P₁, which represents the statistics about attribute ai appearing in position j, while b_ij is an entry in P₂, which represents the statistics about attribute b_i appearing in position j. Given a mapping m, the non-monotonic scoring function is defined as:

This is a non-monotonic scoring function; that is, there is no monotonic relation between the score and the number k_m of matches in the mapping. Now, we will analyze the principle of this scoring function. The item multiplied by α in the equation above is the normal distance [2]. Suppose that, if the statistics values about the position of attributes are uniformly distributed, and two of them are randomly chosen from the matrices, the expected value of normal distance is β (around 1/3). As a result, if the control parameter α is set to 1/β (around 3), the expected score of this function becomes 0 with the assumption above. In other words, in such cases, the match of two randomly chosen attributes will not contribute to the final score. In contrast, if the match is correct (the two attributes map correctly), it will positively contribute to the final score. It can be seen that for a mapping m, the more correct matches m includes, the higher score m that is rewarded. Thus, the optimal mapping is expected to be rewarded with the highest score among other mappings. Based on the analysis above, we can see that this function is non-monotonic in k_m. For a search algorithm using the scoring function, the with the highest score is close to the ideal solution with much higher possibility. Consequently, the corresponding search algorithm can apply to all three kinds of mappings. We compare the two scoring functions over these mappings in our experiments. Actually, the value 1/α represents the average of the normal distance, or the approximate demarcation point between the normal distance of the correct matches, and the normal distance of the wrong matches. The control α can be computed via the quantile, or the experiments. Further, the behavior of the scoring function can be controlled, by changing the parameter α (see [2] for more details).

Given the feature matrices and the scoring functions, our task now is to find the optimal attribute mapping, namely the mapping with the highest score. In this section, we first introduce how to refer to the problem of searching the optimal mapping as a combinatorial optimization problem, then present the details of the search algorithm.

Given two schemas S₁ and S₂ to be matched, the first schema S₁ has n₁ attributes ｛a₁, ..., a_i, ..., an₁｝, while S₂ has n₂ attributes ｛b₁, ..., b_j, ..., bn₂｝. Consider the first cardinality constraint one-to-one mapping, where n₁ = n₂. If the attributes of S₁ are regarded as a fixed sequence a₁a₂ ...an₁ and the correspondence is fixed m(a_i) = b_i, any instance of the permutation of all attributes of S₂ corresponds to a possible mapping. For example, if n₁ = n₂ = 2, then the permutation b₁b₂ and b₂b₁ correspond to two possible mappings ｛(a₁, b₁), (a₂, b2)｝ and ｛(a₁, b₂), (a₂, b₁)｝, where each mapping includes two matches. As a result, we can see that our task of finding the can be transformed into a combinatorial optimization problem, where the score of each permutation is the score of its corresponding mapping. However, for the other two cardinality constraints of onto mapping and partial mapping, the numbers of the attributes of the two schemas are typically not equal. To perform the problem transformation above, we need to make the two schemas own the same number of attributes n. For this purpose, the ‘dummy’ attributes [5] are added to S₁ and S₂. The problem of how many attributes should be added depends on the scoring function. If the monotonic function is used, then n₂ − attributes will be added to S₁, while n₁ − attributes will be added to S₂, so each schema has n₁ + n₂ − = n attributes. Here, for onto mapping, is also known, and takes the value min(n₁, n₂); but for partial mapping, it is the estimate of the number of the correct matches between S₁ and S₂, and should be given to the algorithm. Now, we describe how to decide the number of attributes that are added. For S₂, there exist n₂ − attributes ｛b_q...b_r｝ that have no matching attributes in S₁, so n₂ − ‘dummy’ attributes are added to S₁ as the matching attributes for ｛b_q...b_r｝. The reason for S₁ is the same as S₂; thus we will no longer give unnecessary details. For the non-monotonic function, the is not required, so it is considered to be zero. Thus, n₂ ‘dummy’ attribute will be added to S₁, while n₁ ‘dummy’ attributes will be added to S₂. We can see that in addition to making the two schemas have the same number of attributes, another purpose of the ‘dummy’ attributes is to make each attribute have a counterpart in the other schema. In addition, the ‘dummy’ attribute enables the feature marices to have the same number of rows with value 0. So, we only need to add some columns into the feature matrices to make them have the same size. Here, it should be noted that, when the search algorithm computes the score of a mapping, the matches that involve the ‘dummy’ attributes are ignored.

Next, we will discuss the search algorithm. We can see that while regarding the attributes of S₁ as a fixed sequence, the number of the permutations of all attributes of S₂ is n!. The space of all the permutations is very large, and an exhaustive search is not feasible. Thus, we exploit the simulated annealing (SA) algorithm [6], which is the classical solution to the combinatorial optimization problem, to find the optimal permutation corresponding to , denoted by . SA algorithm is a random search technique based on the physical annealing process, which can gradually approach global optimization, by continuously breaking off from local optimization. SA is a generic probabilistic metaheuristic for the global optimization problem in a large search space. It is fit for a search space that is discrete. For certain problems, SA may be more efficient than an exhaustive search, if the globally optimal solution is not necessary for users. The inspiration of SA is from annealing in metallurgy, which is a technique involving the heating and controlled cooling of a material, to increase the size of its crystals, and to reduce their defects. The energy function of SA represents the energy of the solids that are heated. In our context, the scoring functions are used as the energy function of SA. It should be noted that we aim at the solution with the highest score, rather than the usual lowest energy. The SA algorithm involves six key components: the generator of new solutions, the Metropolis criterion, the initial temperature, the length of Markov chain, the temperature-fall period, and the stopping criteria. We now briefly explain each of these components in our context.

The purpose of the first component is to explore the solutions in the search space. The generator should uniformly explore the space, which benefits the discovery of global optimization. There are many methods that can be used as the solution generator, for example, the methods from the genetic algorithm. The implementation of our generator is shown in Algorithm 1. The main idea of the algorithm is to use some ordering and exchanging rules based on two random numbers, to generate the new solutions. Given a current solution b₁b₂…b_n, two numbers q and r are randomly generated. If q > r, the elements from b_q to b_r are re-arranged in reverse order, while the order of other elements remains unchanged. If q > r, the elements from b₁ to b_r and from b_q to b_n are conversely rearranged, respectively. If q = r, the elements from b₁ to b_q are conversely re-arranged. Here, other methods can also be used, for example the cross and mutation leveraged from the genetic algorithm.

The Metropolis criterion represents the acceptance criterion of the new solutions. We use an example to explain this criterion. Let p₁ be the current solution, p₂ be the new solution, and f(x) be the scoring function, i.e., f_e(x) or f_n(x). The Metropolis criterion means that if f(p₂) > f(p₁), use p₂ as the current solution instead of p₁; else if exp > rn , also accept p₂; else preserve p₁ and abandon p₂, where rn is a random number in the range (0,1), and T is the current temperature. When the score of the new solution is greater than the current solution (f(p₂) > f(p₁)), then we accept the new solution, and make a small forward step towards global optimization. When the score of the new solution is less than the current solution, the algorithm will accept the new solution with some probabilities. This step can guarantee that the algorithm can break from the local optimization with some probabilities, and approach the global optimization gradually. SA algorithm makes use of this criterion, to make a decision about whether or not to accept the new solutions.

The initial temperature T₀ of SA is central to obtaining the global optimization, and the higher T₀ is, the closer the solutions approach the real solution. However, a much higher T₀ will lead to a large number of loops, which will result in a unacceptable running time, namely a very slow convergence speed. Kirkpatrick and Vecchi [6] proposed that T₀ should enable the acceptance rate of new solutions to approach the value 1 at the beginning. This means that the acceptance possibility of Metropolis criterion is close to 1 at the beginning, i.e., exp . To obtain more accurate solution and relatively less running time, this possibility is typically set to 0.95 in practice. To use this method to compute T₀ in our context, we need to compute Δ>f>. Here, the statistical method is used to compute the score dif>f_>e>>rence. We randomly choose k pairs of solutions (k > 1000), then compute the score dif>f_>e>>rence of each pair, and finally, take the expectation of these dif>f_>e>>rences as the value of Δ>f>.

The last three components of SA are relatively simple. The length of the Markov chain refers to the number of iterations traversing the new solutions under a certain temperature. Intuitively, the longer the length is, the more accurate the solution is. However, the length is topically associated with the problem size, and overly long chains would not help find global optimization [6]. Thus, the length of Markov chain in our approach is set to 10n. For the temperature-fall period, we make use of the classical method, i.e., T_k+1 = βT_k, to control the attenuation of the temperature, where β = 0.95, and T_k is the current temperature. In theory, we can obtain a more accurate solution using a higher β. However, a higher β will lead to an unacceptable running time. During the running of the algorithm, if consecutive r Markov chains have no improvement on the current optimization, the search process will terminate; this is the stopping criterion. Now, based on these components, the details of the search algorithm are shown in Algorithm 2.

The algorithm begins with a random solution (line 1), because the initial solution has very little effect on its performance. Then, it randomly explores the new solutions (line 5), and employs the Metropolis criterion, to decide whether to update the current solution (lines 6–11). Actually, the internal loop corresponds to a Markov chain (lines 4–13), where line 13 is the length of the Markov chain.

Thus, each iteration of the external loop will generate a Markov chain. If the length exceeds 10n, the spread of the chain is over (line 13), and the temperature falls for the next chain (line 14). If after r iterations of the external loop the current solution remains unchanged, the algorithm will terminate, and return the current solution as .

In this section, we test the time cost, and evaluate the quality of the matching results of our proposed approach, in synthetic schema matching scenarios. First, we present how to generate the synthetic data set used in the experiments. Then, we show the experimental results evaluating the performance of our matching algorithm, in the case of the three cardinality constraints (one-to-one, onto, and partial). We also study the effect of varying the control parameter of the non-monotonic function on the performance of our approach. Finally, we test the time cost of the proposed algorithm. Our algorithm is implemented using C++ language, and the experiments are carried on a PC compatible machine, with Intel Core Duo processor (2.33 GHz).

We generate the experimental data set based on two online bookstores developed by different persons. The schema of the first bookstore includes 31 attributes, while the second includes 35 attributes, and there exist 27 matching attributes (matches) of each schema. We suppose that a fictitious user continuously accesses each bookstore, until the produced log includes 8000 queries. These SQL statements include two kinds of queries: random queries with any keywords, according to the query interface of the bookstore; and fixed queries, generated based on the navigation or classification functions of the bookstore. The first kind of queries mainly makes use of schema attributes as query criteria to find books. The attributes used include ‘bookName’, ‘author’, ‘publisher’, and ‘pubtime’, where the rest of the attributes are not considered, because of their lower frequency of use. The first kinds of queries are also divided into four parts, each of which has a different attribute as a query criterion. We assign different percentages to the queries with different attributes, according to their use frequency. That is, we generate 40% queries using the attribute ‘bookName’, 30% query using ‘author’, 20% queries using ‘publisher’, and 10% queries using ‘pubtime’. We simulate the actual case by this method. Based on the query logs, the two feature matrices of the bookstores can be obtained as the experimental data. In the experiments, the F-Measure metrics are used as the measurement of the performance of the algorithm.

We evaluate the accuracy against the correct mappings determined by manual inspection of the source and target schemas. We run our algorithm with randomly chosen subsets of the experimental data in each experiment for many times, then get the average of the experimental results. We first present the results of one-to-one mapping in Fig. 3. We use the notation ‘mon’ and ‘non’ as shorthand for the monotonic function and the non-monotonic function, respectively. The control parameter α for the non-monotonic function is set to 0.3.

As can be seen in Fig. 3(a), the match results gradually deteriorate, as the number of the matching attributes (matches) increases, and the worst result for the ‘non’ function is nearly 60%. The changing trends of the two curves are almost the same, namely decreasing with the increase of the number of matches. It is obvious that the accuracy will decrease with the increase of matches, because the increase of the number of matching attributes will result in the increase of the space of the candidate matches. The results with ‘mon’ are better than the one with ‘non’. This is because the correct k_m is known for the one-to-one mapping. We can also see that the overall quality of the results over the n-matrix is higher, than the one over the p-matrix. The reason is that the information collected in the n-matrix is more than the information in the p-matrix, and this behavior conforms to our theoretical analysis in the section above.

The experimental results corresponding to the onto cardinality constraint are shown in Fig. 4. Here, the size of the target schema is kept constant at 16 attributes,while the matching attribute number of the source schema is increased from 4 to 14. As can be seen in both data sets, the results with ‘non’ outperform the results with ‘mon’. The accuracy with ‘non’ reaches 80% in Fig. 4(a), while it was 59% in Fig. 4(b). It can be seen that the ‘non’ scoring function shows its advantage, compared to the ‘mon’ scoring function, when the real k_m is unknown. The overall quality over the n-matrix is better than over the p-matrix. The changing trends of curves here are different from the one in Fig. 3. The accuracy in the onto mapping case gradually improves, as the number of matching attributes increases; then the accuracy begins to decline, when the number exceeds some value; this is just contrary to the one-to-one mapping. The reason is that the matching with the onto constraint requires extra effort, in contrast to the one-to-one case, i.e., the onto mapping first needs to choose a subset of the 16 attributes as the matching attributes that will participate in the following matching process, then the onto mapping based on the chosen attribute subset is turned into the one-to-one mapping. At the beginning, the space of the attribute subsets is very large, because of the lesser attributes of the source schema. Thus, the accuracy is low, and the lowest is around 30%. With the increase of the attributes of the source schema, the accuracy gradually rises.

Fig. 5 illustrates the results of the matching with the partial mapping cardinality constraint. In this experiment, we fix the size of both source and target schema at 14, and vary the number of the matching attributes from 4 to 12. To enable the experiment with the ‘mon’ in the partial mapping case, we give the number of the correct matches to the algorithm with the ‘mon’ function. When the number of matching attributes is less than 5, the accuracy is very low, under 15%. Thus, the results when the attribute number is under 4 are not shown in Fig. 4. Here, the trend of curves in Fig. 5 is similar to the above experiment, but the best performance is less than 70%. The reason is that the matching process with partial cardinality is similar to the one with onto cardinality, namely the algorithm needs to choose a subset of the attributes from the attribute universe. Thus, the accuracy is very low, when the matching attributes involved in the matching process are less. That is, the search space is very large, when the matching attribute number is few. It can be seen that the matching with the partial cardinality constraint is the most difficult matching. Conversely, the results with the ‘non’ function are better, than the one with the ‘mon’ function.

Now, we test the effect of varying the control parameter α on the match results. We fix the size of both source and target schema at 14 attributes, and fix the number of the correct matches at 9 and 12, respectively, denoted by n = 12 and n = 9. The experimental results are shown in Fig. 6. We can see that the accuracy first increases, as α increases from 0.1 to 0.3; then achieves the highest value as α ∈ (0.3, 0.5); and finally drops, with the increase of α. When α is under 0.3, most of the true matches are punished with negative score. Conversely, lots of false matches are rewarded with positive score. Thus, at the beginning, the accuracy is low. With α approaching the value ‘0.3’, the accuracy gradually reaches the greatest value, of around 70%. Then, the accuracy gradually declines, because of the punishment of most of the matches. The accuracy with n = 9 is higher than the one with n = 12, and the results over the n-matrix are better than those over the pmatrix, which is consistent with the above experiments.

Finally, we test the time cost of our algorithm with one-to-one cardinality constraint, and α is also set to 0.3. In this experiment, we set the number of the correct matches to 9 and 14, respectively, denoted by n = 9 and n = 14, and set the temperature-fall coefficient β = 0.9 and β = 0.95. The y-coordinate represents time cost, while the x-coordinate represents the length of Markov chain. The results are shown in Fig. 7. The time with n =14 increases, as the length of the Markov chain increases; and the longest running time reaches nearly two minutes. Obviously, the time cost increases, because of the iterations caused by the increase of the length of Markov chain. However, the time cost with n = 9 remains unchanged, after a length beyond 60. The reason for this behavior is that the size of the search space for n = 9 is less than the number of all iterations of the algorithm, so the algorithm will accomplish the search process ahead of time, and ignore the following iterations caused by the increase of length. It can also be seen that the time cost for β = 0.9 in Fig. 7(a) is less than the cost for β = 0.95 in Fig. 7(b). The reason is that the number of iterations increases for β = 0.95.