System and method for querying xml streams

Abstract

A system and method for querying a stream of XML data in a single pass using standard XQuery expressions. The system comprises: an expression parser that receives a query and generates a parse tree; a SAX events API that receives the stream of XML data and generates a stream of SAX events; an evaluator that receives the parse tree and stream of SAX events and buffers fragments from the stream of SAX events that meet an evaluation criteria; and a tuple constructor that joins fragments to form a set of tuple results that satisfies the query for the stream of XML data.

1 . A system for querying a stream of mark-up language data, the system including at least one computer comprising:
 an expression parser that receives a query and generates a parse tree;   a system that receives the stream of mark-up language data and generates a stream of events;   an evaluator that receives the parse tree and stream of events, and buffers fragments from the stream of events that meet an evaluation criteria; and   a tuple constructor that joins fragments to form a set of tuple results that satisfies the query for the stream of mark-up language data.   
   
   
       2 . The system of  claim 1 , wherein the parse tree includes:
 a set of nodes corresponding to node tests in the query; and   edges corresponding to relationships between node tests in the query.   
   
   
       3 . The system of  claim 2 , wherein at least one of the nodes comprises an output node corresponding to a bound-out variable from the query. 
   
   
       4 . The system of  claim 2 , wherein at least one of the nodes comprises a set of predicate parse trees. 
   
   
       5 . The system of  claim 2 , wherein the evaluator includes a work array for storing evaluation data for the stream of events, wherein the evaluation data tracks matches between nodes and events. 
   
   
       6 . The system of  claim 5 , wherein the evaluator includes a set of output buffers to store fragments that meet the evaluation criteria. 
   
   
       7 . The system of  claim 5 , wherein the evaluator includes:
 a set of predicate buffers to store the content of nodes participating in predicate expressions; and   a predicate evaluation system for evaluating predicate expressions.   
   
   
       8 . The system of  claim 1 , wherein the tuple constructor provides a buffer queue for each variable specified in the query, and identifies correct tuples by processing a cross-product of the buffer queues. 
   
   
       9 . The system of  claim 1 , the at least one computer further comprising a buffer management system, wherein the buffer management system identifies conditions when buffers can be deleted. 
   
   
       10 . A program product stored on a tangible recordable medium for querying a stream of mark-up language data, wherein the program product comprises:
 parsing means for receiving a query and generating a parse tree;   means for receiving the stream of mark-up language data and generating a stream of events;   evaluating means for receiving the parse tree and stream of events, and for buffering fragments from the stream of events that meet an evaluation criteria; and   construction means for joining fragments to form a set of tuple results that satisfies the query for the stream of mark-up language data.   
   
   
       11 . The program product of  claim 10 , wherein the parse tree includes:
 a set of nodes corresponding to node tests in the query; and   edges corresponding to relationships between node tests in the query.   
   
   
       12 . The program product of  claim 11 , wherein at least one of the nodes comprises an output node corresponding to a bound-out variable from the query. 
   
   
       13 . The program product of  claim 11 , wherein at least one of the nodes comprises a set of predicate parse trees. 
   
   
       14 . The program product of  claim 11 , wherein the evaluating means includes a work array for storing evaluation data for the stream of events, wherein the evaluation data tracks matches between nodes and events 
   
   
       15 . The program product of  claim 14 , wherein the evaluating means includes a set of output buffers to store fragments that meet the evaluation criteria. 
   
   
       16 . The program product of  claim 14 , wherein the evaluating means includes:
 a set of predicate buffers to store the content of nodes participating in predicate expressions; and   predicate evaluation means for evaluating predicate expressions.   
   
   
       17 . The program product of  claim 10 , wherein the construction means provides a buffer queue for each bound-out variable specified in the query, and identifies correct tuples by processing a cross-product of the buffer queues. 
   
   
       18 . The program product of  claim 10 , further comprising buffer management means for identifying conditions when buffers can be deleted.