Generally, XML (extensible markup language) has become an important standard for data exchange. The exchange or transmission of large XML streams has become increasingly common, and often the preference is to consume such streams “on the fly”, as opposed to storing them for future use.
One of the core operations of such consumption processes of XML streams is tuple extraction. Generally, tuple extraction lies at the core of XML data integration. One of the most common ways to retrieve information from XML is to “shred” them in relational format. Once shredded, queries can be applied to present an aggregate view for BI (business intelligence). Another important application related to XML streams is for data transformation in schema mapping.
Surprisingly, tuple extraction over streams has not hitherto been widely addressed. Thus, there have been few if any sub-optimal algorithms presented for extracting single tuple types over XML streams. Further, little if any work has been done in the area of extracting multiple tuple types by way of optimal algorithms.