Patent ID: 7953742

Claim:
A method, comprising: in a first phase, creating a pending update list (PUL) including all update operations to be performed on nodes in a fragment of an Extensible Markup Language (XML) document using a computer processor; in a second phase, sorting said PUL using the computer processor, wherein said sorting comprises assigning numbers to operations on a node allowing said operations to be processed in a particular order, and wherein said PUL is sorted on a first key that is a node-id and on a second key that is an update primitive, and wherein node-ids in said sorted PUL are not in document order but in semi-document order in response to said allowing of said operations to be processed in said particular order, said semi-document order being established by said node-ids conveying information regarding a hierarchical relationship between said nodes; and in a third phase, applying said sorted PUL to each said node in said XML fragment during a single traversal of said XML fragment using the computer processor, and wherein said third phase is processed during said single traversal of said XML fragment rather than in multiple traversals, by accessing the node-ids stored in the sorted PUL in semi-document order.