Scalable algorithms for mapping-based xml transformation

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.

1 .- 16 . (canceled) 
   
   
       17 . A computer-implemented method for use with an extensible markup language (XML) document, comprising:
 receiving an input stream of source data from one or more data bases, said stream selected from one of an XML data and a relational database data;   inputting a high-level mapping specification for a schema mapping, said mapping represented as a set of tuple-generating dependency (tgd) entities, wherein said tgd expresses a pattern of a source data and a target data;   performing a tuple extraction phase by taking all possible instantiations of the input stream source data provided that an associated target data pattern is satisfied, said extraction employing an instruction set based on types of data sources and semantics of said extraction, wherein nested concepts in said input stream source data are unnested to form flat tuples;   performing a fragment generation phase, wherein each of said flat tuples is transformed into a fragment based on an associated logical mapping represented by a template determined by a tgd;   performing a data merging phase to create a target document from coherent and non-redundant target instances, wherein fragments are merged into said target document by merging fragments identified with a same key value and eliminating duplicate fragments that have comparable tags values, wherein said merging comprising:
 creating a chain of hash tables for each of said tuples wherein each hash table is associated with a key value and said key value is associated with a document content attribute; 
 flushing the chain of hash tables to remove duplicate tables 
 dynamically switching between a main memory-based and a sort-based algorithm based on the available memory used by said hash tables, wherein said hash tables are written to a disk file as a file-run, said file-run an ordered serialization of said hash tables from a root hash table and associated child hash tables; 
 merging said file-runs when said incoming fragment are processed as file-runs; and 
   outputting said merged file-runs as said target document to a database, said database being identical with or distinct from said XML or rationale database providing said input stream.   
   
   
       18 . A system for scalable extensible markup language (XML) transformation based on schema mappings, the system executing processes for:
 performing a streaming operation for tuple extraction on a streamed XML input comprising:   matching a set-path expression against an XML document provided by the streamed XML input using a blocking process;   assembling records corresponding to set-elements in a set-path expression, wherein a parent record comes after one of the parent record's child elements and the set element has a start-record and an end-record;   storing the parent record's child elements in a buffer until the parent record arrives; and   performing a set-path expression matching concurrently with arrival of new records wherein if all extraction elements of the set-element have arrived, sending the start-record to set-path expression matching before the end-record arrives; and   generating, based on the schema mappings, a target XML document from the streamed XML input.   
   
   
       19 . A computer program product, for use with extensible markup language (XML) data having a size, the computer program product comprising a computer readable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:
 execute a main memory-based set of instructions for merging XML fragments from the XML data, wherein the main memory-based set of instructions comprises:   instructions for hash-based merging;   instructions for writing hash tables generated by the hash-based merging instructions to disk when the hash tables fill the main memory allocated to the hash tables; and   freeing up the hash tables in main memory for subsequent XML fragments from the XML data;   execute a disk-based set of instructions for merging XML fragments from the XML data wherein the disk-based set of instructions comprises:   outputting one file run from a group of linked hash tables in response to the hash tables using up all the available main memory, wherein outputting a file run comprises:   starting serialization from a root hash table of the group of linked hash tables;   sorting keys by key value in a predetermined order; and   outputting the keys in the sorted order wherein after each key is output, recursively serializing the child hash tables of the key; and   merging, in a single sequential scan, multiple file runs output from the hash tables, wherein merging multiple file runs comprises:   comparing the current keys of all the file runs;   in response to the current keys of all the file runs not being equal, outputting the content for the foremost key and updating the current key for the file run with the foremost key;   in response to the current keys of all the file runs being equal, outputting the current key and recursively merging the smaller file runs nested inside the current keys; and   dynamically switching 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.