Patent ID: 8862636

Claim:
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.