XML sub-document versioning method in XML databases using record storages

• US 7,529,726 B2
• Filed: 08/22/2005
• Issued: 05/05/2009
• Est. Priority Date: 08/22/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Teng, James Zu-Chia, Zhang, Guogen, Zou, Qinghua
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Gortayo; Dangelino N
• Application Number:
  US11/161,908
• Publication Number:
  US 20070043686A1
• Time in Patent Office: 1,352 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/100, 707/102, 707/104, 707/200, 707/203
• 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 for versioning records of XML sub-documents in a database implemented in computer storage, said method comprising:

representing node identifiers and version numbers in two-dimensional space along with record boundaries, a horizontal axis in said two-dimensional space representing said node identifiers in document order and a vertical axis in said two-dimensional space representing said version numbers;

adding virtual record boundaries to said record boundaries and dividing said dimensional space into a series of rectangles being any of a close rectangle if respective upper corners are known or an open rectangle if respective upper corners are not known, said virtual record boundaries added to support multiple versions of said sub-documents;

building a search tree index comprising index points corresponding to a bottom corner point of each of said open or closed rectangles, each of said index points comprising a tripe of node identifier, version number and record identifier; and

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, in said computer storage, 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 versions number corresponding said first index point with the versions 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 point'"'"' 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 point'"'"' 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 point'"'"' node identifier is greater than said first index point'"'"' node identifier, returning −

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

2. The method according to claim 1, wherein said search tree is a B+ tree.

3. The method according to claim 1, wherein said bottom corner points are right corner points of said rectangles.

4. The method according to claim 1, wherein a ratio of a number of fresh index points to a number of all index points is determined as a freshness of index and old versions of records are removed if a freshness value is less than a defined threshold value.

5. The method 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. The method 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.

7. The method according to claim 6, wherein said intersecting points are identified, said indentifying 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.

8. The method 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.