Memory efficient XML shredding with partial commit
View Patent ↗A method and system that allows efficient shredding of large instances of hierarchical data structures into relational data structures. Large instances of hierarchical data structures, which are able to be larger than the random access storage of a computer used to shred them into relational data structures, are incrementally shredded into a temporary storage. When the amount of data shredded into the temporary storage reaches or exceeds a predetermined commit count, the data in the temporary storage is transferred to a relational data structure maintained by a relational database manager. A Document Type Description annotation is provided to allow the end user to specify execution order for SQL commands and to specify commit count values.
1. A method for translating data in a hierarchical data structure to a relational data structure, the method comprising the steps of:
defining at least one shredding tree that each translate a hierarchical data structure into a relational data structure, each of the at least one shredding tree defining a hierarchical data structure comprising at least one cursor node and at least one data node, wherein
each of the at least one cursor node defines, in conjunction with parent cursor nodes, a column within the relational data structure, and
each of the at least one data node being an immediate child of a respective parent cursor node within the at least one cursor nodes, each of the at least one data node comprising a respective data element to be inserted at the column defined by the respective parent cursor node;
reading at least one data element from a subset of the at least one data node of a first part of a hierarchical data structure instance using a tree traversal algorithm defined by the at least one shredding tree;
storing the at least one data element in a first storage according to the relational data structure defined by a current shredding tree comprising the at least one data node containing the at least one data element;
maintaining a set of tree commit counter, each tree commit counter being associated with a respective shredding tree within the at least one shredding tree;
maintaining a global commit counter;
decrementing, in response to the storing, a current tree commit counter within the set of tree commit counters, the current tree commit counter being associated with the current shredding tree;
decrementing, in response to the storing, the global commit counter,
determining, in response to the storing, that the first storage stores a quantity of data that is greater than a threshold and that at least one of a tree commit counter within the set of tree commit counters and the global commit counter has been decremented to zero; and
in response to the determining, transferring data stored in the first storage into a relational data structure according to the mapping.
2. The method of claim 1 , wherein each of the at least one shredding tree is associated with a single structured query language command to modify data within the relational data structure, and wherein the transferring step includes the sub-step of executing the at least one structure query language command according to the mapping.
3. The method of claim 1 , wherein the hierarchical data structure has a size that is larger than a capacity of the first storage.
4. The method of claim 1 , wherein the shredding tree is defined by one of an annotated XML schema an annotated document type definition document, the one of the annotated XML schema and annotated document type definition document defining a hierarchical data structure definition with annotations, wherein the annotations comprise a first set of annotations for at least one leaf node of the hierarchical data structure definition that define a respective binding between a data element of the respective at least one leaf node and a column of the hierarchical data structure.
5. The method of claim 1 , further comprising:
completely traversing all node of the current shredding tree; and
decrementing, in response to completely traversing the current shredding tree, the global commit counter by a value remaining in the current tree commit counter.
6. The method of claim 4 , wherein the first set of annotations are associated with a first shredding tree within the at least one shredding tree, wherein the first binding defines a variable, and wherein the first annotated document type definition document further comprises at least a second set of annotations that define a respective relationship between the respective binding and a respective separate relational data structure defined by a separate shredding tree within the at least one shredding tree.