Streaming XML patch

• US 20070240034A1
• Filed: 04/10/2006
• Published: 10/11/2007
• Est. Priority Date: 04/10/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Murthy, Ravi, Agarwal, Nipun, Sthanikam, Balasubramanyam
• Granted Patent: US 8,082,493 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

A technique for differencing XML documents is provided. An edit graph is generated for computing the cost of possible edits that may be applied to a first XML document in order to generate a second XML document. A hash value is assigned to nodes included in the axes of the edit graph, where one axis includes nodes in the first XML document and the other axis includes nodes in the second XML document. The hash value may be generated based on a particular node'"'"'s name and attributes, and the hash value of the name and attributes of each child node of the particular node. A technique for patching an XML document is also provided. Events are generated for each node in the input document and for at least one operation specified in the edit script. The edit script is applied to the input document by performing one or more operations specified in the operation events on one or more node events.

Claims

1. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

generating a plurality of node events based on an input document;

generating one or more operation events based on an edit script, wherein the edit script specifies a set of operations to perform on the input document;

applying the edit script to the input document by performing one or more operations, corresponding to one or more operation events, on one or more node events of the plurality of node events; and

generating an output document that reflects the one or more operations.

2. The method of claim 1, wherein the nodes that are identified for one or more operations in the edit script are identified by the edit script using XPath notation.

3. The method of claim 2, wherein the instructions further comprise instructions for maintaining state for correlating an XPath locator referenced in the one or more operation events to one or more nodes identified by the one or more node events by maintaining a stack that stores an XPath of the latest node event.

4. The method of claim 3, wherein:

the one or more operations specify nodes XPath notations that refer to the output document; and

a delta table is maintained that reflects modifications by a subset of the one or more operation events that have occurred thus far.

5. The method of claim 1, wherein the instructions for performing the step of applying the edit script to the input document further comprise instructions for:

generating a current node event based on the first node in the input document;

generating a current operation event based on the first operation of the set of operations;

for each node event in the plurality of node events,

if the node identified by the current operation event is not the node identified by the current node event, then returning the current node event, wherein the current node event becomes the next node event;

else if the node identified by the current node event is deleted by the operation specified by the current operation event, then generating a new operation event from the edit script, wherein the current operation event becomes the new operation event and the current node event is not returned;

else if the operation specified by the current operation event specifies a new node to be inserted, generating and returning a new node event node event that is based on the new node, and generating a new operation event from the edit script, wherein the current operation event becomes the new operation event; and

else if the operation specified by the current operation event is an update of the node specified by the current node event, generating and returning a new node event that reflects the update or rename, and generating a new operation event from the edit script, wherein the current operation event becomes the new operation event.

6. The method of claim 5, wherein the plurality of node events and the one or more operation events are generated by a pull parser.

7. A machine-readable medium carrying one or more sequences of instructions, which when executed by one or more processors, causes the one or more processors to perform a method comprising the steps of:

generating a plurality of node events based on an input document;

generating one or more operation events based on an edit script, wherein the edit script specifies a set of operations to perform on the input document;

applying the edit script to the input document by performing one or more operations, corresponding to one or more operation events, on one or more node events of the plurality of node events; and

generating an output document that reflects the one or more operations.

8. The machine-readable medium of claim 7, wherein the nodes that are identified for one or more operations in the edit script are identified by the edit script using XPath notation.

9. The machine-readable medium of claim 8, wherein the method further comprises maintaining state for correlating an XPath locator referenced in the one or more operation events to one or more nodes identified by the one or more node events by maintaining a stack that stores an XPath of the latest node event.

10. The machine-readable medium of claim 9, wherein:

the one or more operations specify nodes XPath notations that refer to the output document; and

a delta table is maintained that reflects modifications by a subset of the one or more operation events that have occurred thus far.

11. The machine-readable medium of claim 7, wherein the method further comprises:

generating a current node event based on the first node in the input document;

generating a current operation event based on the first operation of the set of operations;

for each node event in the plurality of node events,

if the node identified by the current operation event is not the node identified by the current node event, then returning the current node event, wherein the current node event becomes the next node event;

else if the node identified by the current node event is deleted by the operation specified by the current operation event, then generating a new operation event from the edit script, wherein the current operation event becomes the new operation event and the current node event is not returned;

else if the operation specified by the current operation event specifies a new node to be inserted, generating and returning a new node event node event that is based on the new node, and generating a new operation event from the edit script, wherein the current operation event becomes the new operation event; and

else if the operation specified by the current operation event is an update of the node specified by the current node event, generating and returning a new node event that reflects the update or rename, and generating a new operation event from the edit script, wherein the current operation event becomes the new operation event.

12. The machine-readable medium of claim 11, wherein the plurality of node events and the one or more operation events are generated by a pull parser.