Method in a computing system for comparing XMI-based XML documents for identical contents

• US 6,502,112 B1
• Filed: 08/27/1999
• Issued: 12/31/2002
• Est. Priority Date: 08/27/1999
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Baisley, Donald Edward
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Bieneman, Charles A.
• Application Number:
  US09/384,690
• Time in Patent Office: 1,222 Days
• Field of Search: 707/511, 707/513, 707/514, 707/516, 707/203, 717/37, 717/104, 717/105, 717/114, 717/143, 717/144
• US Class Current: 715/210
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method is provided by a computer system processing XMI-based XML documents. The method compares two such XMI-based XML documents for identical content. The method begins with the step of parsing each of the documents to create for each a semantic graph of the document'"'"'s objects. Next, a list of names of properties for each of the objects having significant order is read. For each of the objects, and then for each object'"'"'s property not listed as having significant order, values of said properties are sorted. Finally, the objects of the semantic graphs are compared.

Claims

1. In a computer system for processing XMI-based XML documents, a method for comparing two such documents for identical content, said method comprising the steps of:

a. parsing each of said documents to create for each a semantic graph of the document'"'"'s objects;

b. reading a list of names of properties of said objects having significant order;

c. for each of said objects, and then for each object'"'"'s property not listed as having significant order, sorting values of said property; and

,

d. comparing objects of said semantic graphs.

2. The method as in claim 1 wherein said step of sorting values of said property further includes the step of assigning a unique qualified name to each object in each of said semantic graphs.

3. The method as in claim 2 wherein said step of assigning a unique qualified name is based on the sorted position of each object in the composition structure of each of said semantic graphs.

4. The method as in claim 1 wherein said step of comparing objects in said two semantic graphs further includes returning the result of said step of comparing.

5. The method as in claim 1 wherein said step of sorting values of said property not having significant order, further includes the step of sorting said values of said property based on their data value where said value is in fact a data value.

6. The method as in claim 1 wherein said step of sorting values of said property not having significant order further includes the step of sorting said values based on referenced objects where said values are references to objects.

7. The method as in claim 6 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on type of said referenced objects.

8. The method as in claim 6 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on number of properties of said referenced objects.

9. The method as in claim 6 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on the property name/value pairs of properties with data values.

10. The method as in claim 6 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on the composition depth of said referenced objects.

11. The method as in claim 6 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on the composite owner of said referenced objects, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

12. The method as in claim 6 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on referenced objects of properties specified as having significant order, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

13. The method as in claim 6 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on referenced objects of properties not specified as having significant order, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

14. The method as in claim 1 wherein said step of comparing objects of said semantic graphs further comprises the step of determining whether or not said objects are of the same type.

15. The method as in claim 1 wherein said step of comparing objects of said semantic graphs further comprises the step of determining whether or not said objects have the same number of properties.

16. The method as in claim 1 wherein said step of comparing objects of said semantic graphs further comprises comparing each property of the first one of said objects with corresponding property of the second one of said objects.

17. The method as in claim 16 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes comparing property names.

18. The method as in claim 16 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes comparing types of property values.

19. The method as in claim 16 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are data values, comparing said data values.

20. The method as in claim 16 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are references to objects, comparing unique qualified names of said referenced objects.

21. The method as in claim 16 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are composite references to objects, comparing said referenced objects thereby repeating step d of claim 1 recursively.

22. The method as in claim 1 wherein said step of comparing objects of said semantic graphs further comprises the step of, where any of said objects compare as unequal, returning an indication that said documents are unequal;

and where all of said objects compare as equal, returning an indication that said documents are equal.

23. The method as in claim 1 wherein said step of parsing further comprises capturing the following for each object in each one of said semantic graphs:

a. type name of said object;

b. a list of property values in the order occurring in said document, and for each property further capturing the property name, property value as either a reference to an object within the same document or a data value; and

, whether the property is a composite; and

,

c. composite owner, if any, of said object.

24. A storage medium encoded with machine-readable computer program code for comparing two XMI-based XML documents, wherein, when the computer program code is executed by a computer, the computer performs the steps of:

a. parsing each of said documents to create for each a semantic graph of the document'"'"'s objects;

b. reading a list of names of properties of said objects having significant order;

c. for each of said objects, and then for each object'"'"'s property not listed as having significant order, sorting values of said property; and

,

d. comparing objects of said semantic graphs.

25. The storage medium as in claim 24 wherein said step of sorting values of said property further includes the step of assigning a unique qualified name to each object in each of said semantic graphs.

26. The storage medium as in claim 25 wherein said step of assigning a unique qualified name is based on the sorted position of each object in the composition structure of each of said semantic graphs.

27. The storage medium as in claim 24 herein said step of comparing objects in said two semantic graphs further includes returning the result of said step of comparing.

28. The storage medium as in claim 24 wherein said step of sorting values of said property not having significant order, further includes the step of sorting said values of said property based on their data value where said value is in fact a data value.

29. The storage medium as in claim 24 wherein said step of sorting values of said property not having significant order further includes the step of sorting said values based on referenced objects where said values are references to objects.

30. The storage medium as in claim 29 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on type of said referenced objects.

31. The storage medium as in claim 29 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on number of properties of said referenced objects.

32. The storage medium as in claim 29 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on the property name/value pairs of properties with data values.

33. The storage medium as in claim 29 wherein said step of sorting values of said property where said values are references to objects further includes sorting based on the composition depth of said referenced objects.

34. The storage medium as in claim 29 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on the composite owner of said referenced objects, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

35. The storage medium as in claim 29 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on referenced objects of properties specified as having significant order, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

36. The storage medium as in claim 29 wherein said step of sorting values of said property, where said values are references to objects, further includes sorting based on referenced objects of properties not specified as having significant order, thereby further sorting said values based on referenced objects, recursively for objects referenced by referenced objects.

37. The storage medium as in claim 24 wherein said step of comparing objects of said semantic graphs further comprises the step of determining whether or not said objects are of the same type.

38. The storage medium as in claim 24 wherein said step of comparing objects of said semantic graphs further comprises the step of determining whether or not said objects have the same number of properties.

39. The storage medium as in claim 38 wherein said step of comparing objects of said semantic graphs further comprises comparing each property of the first one of said objects with corresponding property of the second one of said objects.

40. The storage medium as in claim 38 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes comparing property names.

41. The storage medium as in claim 38 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes comparing types of property values.

42. The storage medium as in claim 38 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are data values, comparing said data values.

43. The storage medium as in claim 38 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are references to objects, comparing unique qualified names of said referenced objects.

44. The storage medium as in claim 38 wherein said step of comparing each property of the first one of said objects with corresponding property of the second one of said objects further includes, where property values are composite references to objects, comparing said referenced objects thereby repeating step d of claim 25 recursively.

45. The storage medium as in claim 24 wherein said step of comparing objects of said semantic graphs further comprises the step of, where any of said objects compare as unequal, returning an indication that said documents are unequal;

and where all of said objects compare as equal, returning an indication that said documents are equal.

46. The storage medium as in claim 24 wherein said step of parsing further comprises capturing the following for each object in each one of said semantic graphs:

a. type name of said object;

b. a list of property values in the order occurring in said document, and for each property further capturing the property name, property value as either a reference to an object within the same document or a data value; and

, whether the property is a composite; and

,

c. composite owner, if any, of said object.