Supporting efficient partial update of hierarchically structured documents based on record storage

• US 20120078942A1
• Filed: 09/27/2010
• Published: 03/29/2012
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Cai, Mengchu, Chen, Yu, Katayama, Eric Naoto
• Granted Patent: US 8,495,085 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/835 Query processing

Abstract

Methods and apparatus, including computer program products, implementing and using techniques for performing a partial update of a hierarchically structured document referencing one or more records stored in a database. An expression specifying one or more updates to be applied to the document is received. The document is searched to find update target position(s). Based on the received expression, a pending update list is built. When an update target position is found, a row of a document column in a base table is updated with the new version number for the document. New database records for insertion into the new document version are generated from the pending update list. Old database records to be replaced are identified. A database table for the document is updated to mark the old database records as obsolete and to add new database records to be referenced in the new version of the document.

Claims

1. A computer-implemented method for performing a partial update of a hierarchically structured document referencing one or more records stored in a database, the method comprising:

receiving an expression by a computer processor, wherein the expression specifies one or more updates to be applied to the document;

searching the document by the computer processor to find one or more update target positions;

building, based on the received expression, a pending update list that contains requested updates which have not yet been applied to the document;

in response to finding an update target position in the document, updating a row of a document column in a base table of the database with the new version number for the document;

generating, based on the pending update list, new database records to be inserted into the new version of the document and identifying old database records to be replaced in the new version of the document; and

updating a database table for the document to mark the old database records as obsolete and to add new database records to be referenced in the new version of the document.

2. The method of claim 1, wherein the hierarchically structured document is an Extended Markup Language Document and the update expression is an expression written in the XQuery programming language.

3. The method of claim 2, wherein each base table row includes:

a document identifier column uniquely identifying an Extended Markup Language document, and one or more Extended Markup Language columns storing information pertaining to the Extended Markup Language data for the Extended Markup Language document, wherein each Extended Markup Language column has a corresponding internal Extended Markup Language table storing the Extended Markup Language data.

4. The method of claim 3, wherein the one or more Extended Markup Language columns include an Extended Markup Language indicator column, the Extended Markup Language indicator column containing update timestamps indicating the latest time of update to the document identified by the document identifier column.

5. The method of claim 3, wherein the internal Extended Markup Language table includes:

a start timestamp and an end timestamp for the Extended Markup Language data, and a document identifier, wherein the start and end timestamps indicate a validity time period for the Extended Markup Language record.

6. The method of claim 3, wherein updating a database table includes:

storing an update timestamp in the base table row referencing the document identifier;

storing in each changed Extended Markup Language record a start timestamp indicating a starting time of a validity period for the changed Extended Markup Language record; and

storing in each changed Extended Markup Language record an end timestamp indicating an ending time of a validity period for the changed Extended Markup Language record.

7. The method of claim 1, wherein generating new database records and identifying old database records includes:

dividing the pending update list in accordance with record boundaries; and

determining whether to apply single-record update or subtree reconstruction.

8. The method of claim 1, wherein searching the document and updating the database table are performed as a streaming process.

9. The method of claim 7, further comprising applying a single record update, the single record update including:

adjusting one or more nodes of an Extended Markup Language tree representing the Extended Markup Language document, the one or more nodes being located around an update target node in the Extended Markup Language tree.

10. The method of claim 9, further comprising:

preserving a physical storage order of child nodes in response to inserting or replacing one or more of attribute and namespaces for a record.

11. The method of claim 9, wherein adjusting the one or more nodes includes:

determining whether there are any adjacent text nodes in the Extended Markup Language tree; and

in response to determining that there are adjacent text nodes, merging at least two of the adjacent text nodes.

12. The method of claim 9, wherein adjusting the one or more nodes includes:

adjusting the update target node and a parent node of the update target node in accordance with the received expression.

13. The method of claim 12, wherein the received expression represents a deletion and wherein the deletion is effected by skipping the update target node in the new records.

14. The method of claim 12, wherein the received expression represents an insertion or replacement and wherein the insertion or replacement is effected by adding new source nodes specified by the received expression into the Extended Markup Language tree.

15. The method of claim 7, further comprising applying a subtree reconstruction, the subtree reconstruction including:

selecting a record specified by the received expression, the record specifying a starting node in an Extended Markup Language tree representing the Extended Markup Language document; and

constructing one or more subtrees under the selected starting node, while also preserving context information that connects newly constructed records with pre-existing records in the Extended Markup Language document.

16. The method of claim 15, wherein constructing one or more subtrees includes:

using a first traversal process to scan and construct the original document;

in response to identifying the update target is identified, using a second traversal process on the source data to continue construction of the document; and

in response to determining that the source data is fully constructed, switching back to the first traversal process to traverse data located after the target position in the original document, until the whole subtree has been traversed.

17. The method of claim 15, further comprising:

examining the pending update list pertaining to the subtree; and

if there are no pending updates in the pending update list that affect a lower level subtree with child records, avoiding reconstruction of the lower level subtree.

18. The method of claim 15, wherein updating the database table further includes:

collecting pending updates and performing a batch update on the impacted records at the time when the next pending update target is on a different Extended Markup Language subtree having a disjoint record hierarchy.

19. A computer program product for performing a partial update of a hierarchically structured document referencing one or more records stored in a database, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to receive an expression that specifies one or more updates to be applied to the document;

computer readable program code configured to search the document to find one or more update target positions;

computer readable program code configured to build, based on the received expression, a pending update list that contains requested updates which have not yet been applied to the document;

computer readable program code configured to update a row of a document column in a base table of the database with the new version number for the document, in response to finding an update target position in the document;

computer readable program code configured to generate, based on the pending update list, new database records to be inserted into the new version of the document and identify old database records to be replaced in the new version of the document; and

computer readable program code configured to update a database table for the document to mark the old database records as obsolete and to add new database records to be referenced in the new version of the document.

20. A system for performing a partial update of a hierarchically structured document referencing one or more records stored in a database, the system comprising:

a database, the database storing a plurality of database records that are referenced by a hierarchically structured document;

a processor; and

a memory, the memory storing instructions that when executed by the processor cause the processor to;

receive an expression that specifies one or more updates to be applied to the document;

search the document to find one or more update target positions;

build, based on the received expression, a pending update list that contains requested updates which have not yet been applied to the document;

in response to finding an update target position in the document, update a row of a document column in a base table of the database with the new version number for the document;

generate, based on the pending update list, new database records to be inserted into the new version of the document and identify old database records to be replaced in the new version of the document; and

update a database table for the document to mark the old database records as obsolete and to add new database records to be referenced in the new version of the document.