Methods and system for model matching

• US 6,826,568 B2
• Filed: 12/20/2001
• Issued: 11/30/2004
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Madhavan, Jayant, Bernstein, Philip A.
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/028,912
• Publication Number:
  US 20030120651A1
• Time in Patent Office: 1,076 Days
• Field of Search: 707/1, 707/6, 707/100, 707/101, 707/104.1, 707/102, 704/1, 706/20
• US Class Current: 707/749
• 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 method for generating similarity coefficients between model elements when comparing a first data model having hierarchically organized first model elements and a second data model having hierarchically organized second model elements, comprising:

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;

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;

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

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

2. A method according to 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. A method according to claim 1, wherein said second generating includes 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. A method according to claim 1, whereby in connection with said second generating, said pairs of model elements are initially assigned structural similarity coefficients based on a constant.

5. A method according to claim 1, whereby in connection with said second generating, said pairs of model elements are initially assigned structural similarity coefficients based on data type compatibility.

6. A method according to claim 1, whereby in connection with said second generating, only pairs of leaves are initially assigned structural similarity coefficients.

7. A method according to 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. A method according to 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. A method according to claim 1, wherein said first generating includes first generating a plurality of linguistic similarity coefficients for each pair of model elements and said third generating includes 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. A method according to claim 9, wherein said first generating includes first generating a plurality of linguistic similarity coefficients for each pair based on per type similarities of tokens of the model elements.

11. A method according to claim 10, wherein token types include numbers, special symbols, common words, concepts and content.

12. A method according to claim 9, wherein said first generating includes analysis of at least one of (a) at least one dictionary and (b) at least one thesaurus.

13. A method according to claim 1, wherein said second and third generating are computed in inverse-topological order.

14. A method according to claim 1, wherein the weight of the weighted function is a variable parameter.

15. A method according to claim 1, wherein said second generating is performed for only those pairs of model elements that have a comparable number of leaves within a predetermined factor.

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

17. A method according to claim 1, further including 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. A method according to claim 1, further including 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. A method according to claim 1, further including 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. A method according to claim 1, wherein said first, second and third generating are performed in real-time.

21. A method according to claim 1, wherein further including transforming said first and second models to first and second trees of data paths, respectively.

22. A computer readable medium having stored thereon a plurality of computer-executable instructions for performing the method of claim 1.

23. A modulated data signal carrying computer executable instructions for performing the method of claim 1.

24. A computing device comprising means for performing the method of claim 1.

25. A computer readable medium having stored thereon a plurality of computer-executable modules, the computer executable modules, comprising:

a comparison mechanism for generating similarity coefficients between model elements when comparing a first data model having hierarchically organized first model elements and a second data model having hierarchically organized second model elements, 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.

26. A computer readable medium according to claim 25, 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.

27. A computer readable medium according to claim 25, 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.

28. A computer readable medium according to claim 25, whereby in connection with said means for second generating, said pairs of model elements are initially assigned structural similarity coefficients based a constant.

29. A computer readable medium according to claim 25, 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.

30. A computer readable medium according to claim 25, whereby in connection with said means for second generating, only pairs of leaves are initially assigned structural similarity coefficients.

31. A computer readable medium according to claim 25, 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.

32. A computer readable medium according to claim 25, 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.

33. A computer readable medium according to claim 25, 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.

34. A computer readable medium according to claim 33, 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.

35. A computer readable medium according to claim 34, wherein token types include numbers, special symbols, common words, concepts and content.

36. A computer readable medium according to claim 33, wherein said means for first generating includes analysis of at least one of (a) at least one dictionary and (b) at least one thesaurus.

37. A computer readable medium according to claim 25, wherein said means for second and third generating compute in inverse topological order.

38. A computer readable medium according to claim 25, wherein the weight of the weighted function is a variable parameter.

39. A computer readable medium according to claim 25, 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.

40. A computer readable medium according to claim 25, 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.

41. A computer readable medium according to claim 25, 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.

42. A computer readable medium according to claim 25, 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.

43. A computer readable medium according to claim 25, 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.

44. A computer readable medium according to claim 25, wherein said means for first, second and third generating perform in real-time.

45. A computer readable medium according to claim 25, wherein further including means for transforming said first and second models to first and second trees of data paths, respectively.

46. A modulated data signal carrying computer executable instructions output as a result of the execution of the plurality of computer-executable instructions of the computer readable medium of claim 25.

47. A computing device comprising means for carrying out the plurality of computer-executable instructions of the computer readable medium of claim 25.