XML SUB-DOCUMENT VERSIONING METHOD IN XML DATABASES USING RECORD STORAGES

• US 20070043686A1
• Filed: 08/22/2005
• Published: 02/22/2007
• Est. Priority Date: 08/22/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: TENG, JAMES, ZHANG, GUOGEN, ZOU, QINGHUA
• Granted Patent: US 7,529,726 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A new sub-document versioning method for record storages of XML documents which uses virtual cutting points to ensure that a search tree is able to support multiple versions of sub-documents and provide efficient mechanisms for XML updating. Record boundaries and virtual cut points divide the two-dimensional space, the horizontal axis representing node identifiers in document order and vertical axis representing version numbers, into rectangles. The bottom corner of the rectangle is used to represent the rectangles and the corresponding information of the corner is added to the search tree index.

Claims

1. A computer-based method of versioning records of XML sub-documents in a database, said method comprising:

representing node identifiers and version numbers in two -dimensional space along with record boundaries;

adding virtual record boundaries to said record boundaries and dividing said dimensional space into a series of rectangles, said virtual record boundaries added to support multiple versions of said sub-documents; and

building a search tree index comprising index points corresponding to a bottom corner point of each of said rectangles, each of said index points comprising a triple of node identifier, version number and record identifier.

2. A method of versioning records of XML sub-documents, according to claim 1, wherein said search tree is a B+ tree.

3. A method of versioning records of XML sub-documents, according to claim 1, wherein said bottom corner points are right corner points of said rectangles.

4. A method of versioning records of XML sub-documents, according to claim 1, wherein ratio of the number of said fresh index points to all index points is the freshness of index and old versions of records are removed if said freshness value is smaller than a defined threshold.

5. A method of versioning records of XML sub-documents, according to claim 4, wherein the process of removing old versions is delayed until no XML readers are reading said old versions of the records.

6. A method of versioning records of XML sub-documents, according to claim 1, wherein a record identifier for a given node identifier at a version number is identified, said identification process comprising the following steps:

searching said search tree index with a key comprising said node identifier and version number;

storing a first index point based on the result of said searching;

if said first index point is null, returning −

1, indicating no record stores said node identifier, else

if said first index point is not null, comparing the version number corresponding said first index point with the version number corresponding to said key;

if the version number corresponding said first index point is less than or equal to the version number corresponding to said key, returning said first index points'"'"' record identifier, else

if the version number corresponding said first index point is not less than or equal to the version number corresponding to said key, searching said search tree index with a key comprising said first index points'"'"' node identifier and the version number corresponding to said key;

storing a second index point based on the result of said searching; and

if said second index points'"'"' node identifier is greater than said first index points'"'"' node identifier, returning −

1, indicating a non-existent version, else returning said second index points'"'"' record identifier.

7. A method of versioning records of XML sub-documents, according to claim 1, wherein said records are updated, said updating process comprising the following steps:

identifying each new record, identifying all intersecting records with all versions by searching said search tree index and identifying intersecting points, said intersecting points being virtual index points;

creating index points for said new record boundaries; and

creating index points for said virtual index points.

8. A method of versioning records of XML sub-documents, according to claim 7, wherein said intersecting points are identified, said identifying process comprising the following steps:

sorting items in a list by node identifiers in ascending order;

finding a start index point by searching said search tree index with a first node identifier; and

determining an end index point stored in the same record as said start index point in a prior version, wherein all intersecting points are buffered from said start index point to said end index point, said intersecting points being virtual index points.

9. A method of versioning records of XML sub-documents, according to claim 1, wherein old versions of records are removed explicitly or by a background process if freshness is below a given threshold, said removal process comprising the following steps:

identifying stale and virtual index points by searching said search tree index;

removing stale index points and corresponding records; and

removing virtual index points.

10. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents in a database, said medium comprising:

computer readable program code representing node identifiers and version numbers in two-dimensional space along with record boundaries;

computer readable program code adding virtual record boundaries to said record boundaries and dividing said dimensional space into a series of rectangles, said virtual record boundaries added to support multiple versions of said sub-documents; and

computer readable program code building a search tree index comprising index points corresponding to a bottom corner points of each of said rectangles, each of said index points comprising a triple of node identifier,

version number and record identifier.

11. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents, according to claim 10, wherein a record identifier for a given node identifier at a version number is identified, said medium further implementing an identification process comprising the following steps:

computer readable program code searching said search tree index with a key comprising said node identifier and version number;

computer readable program code storing a first index point based on the result of said searching;

computer readable program code deciding if said first index point is null, returning −

1, indicating no record stores said node identifier, else computer readable program code deciding if said first index point is not null, comparing the version number corresponding said first index point with the version number corresponding to said key;

computer readable program code deciding if the version number corresponding said first index point is less than or equal to the version number corresponding to said key, returning said first index points'"'"' record identifier, else

computer readable program code deciding if the version number corresponding said first index point is not less than or equal to the version number corresponding to said key, searching said search tree index with a key comprising said first index points'"'"' node identifier and the version number corresponding to said key;

computer readable program code storing a second index point based on the result of said searching; and

computer readable program code deciding if said second index points'"'"' node identifier is greater than said first index points'"'"' node identifier, returning −

1, indicating a non-existent version, else returning said second index points'"'"' record identifier.

12. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents, according claim 10, wherein said records are updated, said medium further implementing an updating process comprising the following steps:

computer readable program code identifying each new record, identifying all intersecting records with all versions by searching said search tree index and identifying intersecting points, said intersecting points being virtual index points;

computer readable program code creating index points for said new record boundaries; and

computer readable program code creating index points for said virtual index points.

13. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents, according to claim 12, wherein said intersecting points are identified, said medium further implementing an identifying process comprising the following steps:

computer readable program code sorting items in a list by node identifiers in ascending order;

computer readable program code finding a start index point by searching said search tree index with a first node identifier; and

computer readable program code determining an end index point stored in the same record as said start index point in a prior version, wherein all intersecting points are buffered from said start index point to said end index point, said intersecting points being virtual index points.

14. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents, according to claim 10, wherein old versions of records are removed explicitly or by a background process if freshness is below a given threshold, said medium further implementing a removal process comprising the following steps:

computer readable program code identifying stale and virtual index points by searching said search tree index;

computer readable program code removing stale index points and corresponding records; and

computer readable program code removing virtual index points.

15. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML sub-documents, according to claim 10, wherein said search tree is a B+ tree.

16. An article of manufacture comprising computer readable program code implementing a method of versioning records of XML documents, according to claim 10, wherein said bottom corner points are right corner points of said rectangles.

17. An XML updater updating XML sub-documents working in conjunction with a database storing XML documents as a set of records, each of said records associated with an identifier and a version number, each of said records being represented by at least one of nodes identified in an ordered tree, each of said nodes being assigned node identifiers, said system comprising:

an XML reader reading a version of said records based on an XML query;

an XML updater creating new records, said creating based on;

identifying each said new record, identifying all intersecting records with all versions by searching a search tree index and identifying intersecting points, said intersecting points being virtual index points;

creating index points for said new record boundaries; and

creating index points for said virtual index points; and

wherein said new records reflect updates in said XML document.

18. An XML sub-document versioning system, according to claim 17, wherein said search tree is a B+ tree.