Scalable algorithms for mapping-based XML transformation
AssigneeInternational Business Machines Corporation
InventorsWook-Shin Han, Ching-Tien Ho, Haifeng Jiang, Lucian Popa
Life of this patent
Estimating the term…
Abstract
A computer-implemented method for use with an extensible markup language (XML) document includes inputting a high-level mapping specification for a schema mapping; and generating a target XML document based on the mapping. The method may perform schema mapping-based XML transformation as a three-phase process comprising tuple extraction, XML-fragment generation, and data merging. The tuple extraction phase may be adapted to handle streamed XML data (as well as stored/indexed XML data). The data merging phase may use a hybrid method that can dynamically switch between main memory-based and disk-based algorithms based on the size of the XML data to be merged.
Claims15
A computer-implemented method for use with an extensible markup language (XML) document, comprising:
- inputting a high-level mapping specification for a schema mapping;
- performing, by the execution of a computer processor, a tuple extraction phase on stored XML data wherein the tuple extraction includes unnesting nested concepts to form flat tuples;
- creating XML fragments from the flat tuples;
- removing duplicate ones of the XML fragments;
- creating keys for the XML fragments;
- performing a data merging phase on the stored XML data, wherein the data merging includes:
- using a hybrid algorithmic method that dynamically switches between main memory-based and disk-based algorithms based on the size of the XML data to be merged;
- creating a plurality of chains of hash tables, wherein one of the plurality of chains of hash tables is created for each of the flat tuples;
- ordering a plurality of keys for each of the hash tables;
- sorting the hash tables by sorting the plurality of keys for each of the hash tables;
- merging the sorted hash tables;
- merging those of the XML fragments that share a single one of the keys;
- and
- generating a target XML document based on the mapping.
A system comprising a computer processor for scalable extensible markup language (XML) transformation based on schema mappings,
- wherein the computer processor is configured to perform a streaming operation using a computer processor for tuple extraction on a streamed XML input,
- wherein the tuple extraction includes unnesting nested concepts to form flat tuples, and
- wherein the computer processor is configured to:
- create XML fragments from the flat tuples;
- remove duplicate ones of the XML fragments;
- create keys for the XML fragments;
- use a hybrid algorithmic method that dynamically switches between main memory-based and disk-based algorithms based on a size of the XML fragments;
- create a plurality of chains of hash tables, wherein one of the plurality of chains of hash tables is created for each of the flat tuples;
- order a plurality of keys for each of the hash tables;
- sort the hash tables by sorting the plurality of keys for each of the hash tables;
- and
- merge the sorted hash tables;
- merge those of the XML fragments that share a single one of the keys;
- and
- generate, based on the schema mappings, a target XML document from the streamed XML input.
A computer program product, for use with extensible markup language (XML) data having a size, the computer program product comprising a non-transitory computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:
- extract flat tuples from the XML data by unnesting nested concepts to form flat tuples;
- create XML fragments from the flat tuples;
- remove duplicate ones of the XML fragments;
- create keys for the XML fragments;
- create a plurality of chains of hash tables, wherein one of the plurality of chains of hash tables is created for each of the flat tuples;
- order a plurality of keys for each of the hash tables;
- sort the hash tables by sorting the plurality of keys for each of the hash tables:
- merge the sorted hash tables
- execute a main memory-based set of instructions configured to merge the XML fragments from the XML data;
- execute a disk-based set of instructions configured to merge the XML fragments from the XML data;
- and
- dynamically switch between the main memory-based set of instructions and the disk-based set of instructions based on the size of the XML data to be merged.
Dependencies are inferred from the claim text.