System and method for querying XML streams

• US 20040205082A1
• Filed: 04/14/2003
• Published: 10/14/2004
• Est. Priority Date: 04/14/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Josifovsld, Vanja, Fontoura, Marcus F.
• Granted Patent: US 7,392,239 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. A system for querying a stream of mark-up language data, 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;

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, 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 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 system of claim 10, further comprising buffer management means for identifying conditions when buffers can be deleted.

19. A method of querying a stream of mark-up language data, comprising:

receiving a query and generating a parse tree;

receiving the stream of mark-up language data and generating a stream of events;

evaluating the parse tree and stream of events, and buffering fragments from the stream of events that meet an evaluation criteria; and

joining fragments to form a set of tuple results that satisfies the query for the stream of mark-up language data.

20. The method of claim 19, 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.

21. The method of claim 20, wherein at least one of the nodes comprises an output node corresponding to a bound-out variable from the query.

22. The method of claim 20, wherein at least one of the nodes comprises a set of predicate parse trees.

23. The method of claim 20, wherein the evaluating step includes the step of generating a work array for storing evaluation data for the stream of events, wherein the evaluation data tracks matches between nodes and events.

24. The method of claim 23, wherein the evaluating step includes the step of generating a set of output buffers to store fragments that meet the evaluation criteria.

25. The method of claim 23, wherein the evaluating step includes:

generating a set of predicate buffers to store the content of nodes participating in predicate expressions; and

evaluating predicate expressions.

26. The method of claim 19, wherein the step of joining fragments includes the steps of:

providing a buffer queue for each bound-out variable specified in the query; and

identifying correct tuples by processing a cross-product of the buffer queues.

27. The method of claim 19, comprising the further steps of:

identifying buffers that can be deleted; and

deleting identified buffers.

28. The method of claim 19, wherein the mark-up language data comprises XML.