Methods and systems for model matching

• US 7,444,330 B2
• Filed: 10/26/2004
• Issued: 10/28/2008
• Est. Priority Date: 12/20/2001
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bernstein, Philip A., Madhavan, Jayant
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/973,495
• Publication Number:
  US 20050060332A1
• Time in Patent Office: 1,463 Days
• Field of Search: 707/1, 707/6, 707/100, 707/101, 707/102, 707/104.1, 704/1, 706/20
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Systems and methods for automatically and generically matching models are provided, such as may be provided in a matching application or matching component, or provided in a general purpose system for managing models. The methods are generic since the methods apply to hierarchical data sets outside of any particular data model or application. Similarity coefficients are calculated for, and mappings are discovered between, schema elements based on their names, data types, constraints, and schema structure, using a broad set of techniques. Some of these techniques include the integrated use of linguistic and structural matching, context dependent matching of shared types, and a bias toward subtree, or leaf, structure where much of the schema content resides.

Claims

1. A system for generating similarity coefficients between model elements, comprising:

a first data model having hierarchically organized first model elements;

a second data model having hierarchically organized second model elements;

a comparison mechanism for generating similarity coefficients between model elements when comparing the first data model and the second data model, said mechanism comprising;

means for first generating a plurality of inherent similarity coefficients for each pair of model elements, with each pair comprising a model element of said first model elements and a model element of said second model elements;

means for second generating a plurality of structural similarity coefficients for each pair of model elements based on a similarity of subtree elements rooted by the element pair, whereby each pair of model elements is assigned an initial structural similarity coefficient;

means for third generating a plurality of weighted similarity coefficients for each pair of model elements as a weighted function of said plurality of inherent similarity coefficients and said plurality of structural similarity coefficients; and

means for altering the similarity of said subtree elements rooted by the element pair for each pair of model elements, if a function based on said weighted similarity coefficient of said element pair meets a predetermined condition.

2. The system of claim 1, wherein said similarity of subtree elements includes similarity of pairs of subtree elements, with each pair of subtree elements comprising a model element of said first model elements and a model element of said second model elements.

3. The system of claim 1, wherein said means for second generating includes means for second generating a plurality of structural similarity coefficients for each pair of model elements based on a similarity of leaves rooted by the element pair.

4. The system of claim 1, whereby in connection with said means for second generating, said pairs of model elements are initially assigned structural similarity coefficients based a constant.

5. The system of claim 1, whereby in connection with said means for second generating, said pairs of model elements are initially assigned structural similarity coefficients based on data type compatibility.

6. The system of claim 1, whereby in connection with said means for second generating, only pairs of leaves are initially assigned structural similarity coefficients.

7. The system of claim 1, wherein for each pair of model elements, the similarity for said subtree elements rooted by the element pair is increased by a predetermined amount if said weighted similarity coefficient of said element pair exceeds a predefined, variable threshold.

8. The system of claim 1, wherein for each pair of model elements, the similarity for said subtree elements rooted by the element pair is decreased by a predetermined amount if said weighted similarity coefficient of said element pair is less than a predefined, variable threshold.

9. The system of claim 1, wherein said means for first generating includes means for first generating a plurality of linguistic similarity coefficients for each pair of model elements and said means for third generating includes means for third generating a plurality of weighted similarity coefficients for each pair of model elements as a weighted function of said plurality of linguistic similarity coefficients and said plurality of structural similarity coefficients.

10. The system of claim 9, wherein said means for first generating includes means for first generating a plurality of linguistic similarity coefficients for each pair based on per type similarities of tokens of the model elements.

11. The system of claim 10, wherein token types include numbers, special symbols, common words, concepts and content.

12. The system of claim 9, wherein said means for first generating includes analysis of at least one of (a) at least one dictionary and (b) at least one thesaurus.

13. The system of claim 1, wherein said means for second and third generating compute in inverse topological order.

14. The system of claim 1, wherein the weight of the weighted function is a variable parameter.

15. The system of claim 1, wherein said means for second generating performs for only those pairs of model elements that have a comparable number of leaves within a predetermined factor.

16. The system of claim 1, further including means for fourth performing the generating of the means for third generating again, if the similarity of subtree elements has been altered according to said means for altering.

17. The system of claim 1, further including means for post-processing at least one of the plurality of inherent similarity coefficients, the plurality of structural similarity coefficients and the weighted similarity coefficients to construct a mapping between the first and second models.

18. The system of claim 1, further including means for receiving data from a user about matching the first and second models that is used in connection with initializing the initial structural similarity coefficients.

19. The system of claim 1, further including means for transforming said first and second data models into a generic object model format upon which said first, second and third generating operate irrespective of the input format of the first and second data models before such transformation.

20. The system of claim 1, wherein said means for first, second and third generating perform in real-time.

21. The system of claim 1, wherein further including means for transforming said first and second models to first and second trees of data paths, respectively.