Peer To Patent

Home > Archived Applications > 20090125495 > Prior Art > Detail

Pre-Grant Publication Number: 20090125495

Optimized streaming evaluation of xml queries

Please help the USPTO examine the application by evaluating the relevance of the publicly submitted prior art to the patent application. Peer To Patent forwards the Top 10 most relevant prior art submissions and their annotations to the USPTO.

Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.

Prior Art Detail

Annotations(0)

#546Ef*cient Evaluation of XQuery over Streaming Data

Applies to Claims 1,19

Submitted by: Diane WillisLast updated: almost 4 years ago

0 thumbs up 0 thumbs down

Summary / Description

Summary / Description	Abstract With the growing popularity of XML and emergence of streaming data model, processing queries over streaming XML has become an important topic. This paper presents a new framework and a set of techniques for processing XQuery over streaming data.

Basic Information

Type of Prior Art	Online Publication

URL	http://portal.acm.org/citation....

Author/Creator	Xiaogang Li, Gagan Agrawal

Title	Efcient Evaluation of XQuery over Streaming Data

Publication Date	2005

Publisher	portal.acm.org

Directions to Document Location	Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005

Additional Information

Notes / To Do

Notes	Prior art investigation by Kristoffer Rose, IBM, and submitted by Diane Willis.

Excerpt

Excerpt

With the growing popularity of XML and emergence of streaming data model, processing queries over streaming XML has become an important topic. This paper presents a new framework and a set of techniques for processing XQuery over streaming data. As compared to the existing work on supporting XPath/XQuery over data streams, we make the following three contributions:1. We propose a series of optimizations which transform XQuery queries so that they can be correctly executed with a single pass on the dataset.2. We present a methodology for determining when an XQuery query, possibly after the transformations we introduce, can be correctly executed with only a single pass on the dataset.3. We describe a code generation approach which can handle XQuery queries with user-defined aggregates, including recursive functions. We aggressively use static analysis and generate executable code, i.e., do not require a query plan to be interpreted at runtime.We have evaluated our implementation using several XMark benchmarks and three other XQuery queries driven by real applications. Our experimental results show that as compared to Qizx/Open, Saxon, and Galax, our system: 1) is at least 25% faster on XMark queries with small datasets, 2) is significantly faster on XMark queries with larger datasets, 3) at least one order of magnitude faster on the queries driven by real applications, as unlike other systems, we can transform them to execute with a single pass, and 4) executes queries efficiently on large datasets when other systems often have memory overflows.

Relevance

Claims

A computer-implemented method for evaluating XPath expressions, comprising the steps of:(1) sending criteria from an XPath evaluation component to an XML event-streaming component;wherein the criteria is based at least upon a next unmatched step in an XPath expression;

(2) streaming an XML event from the XML event-streaming component to the XPath evaluation component;wherein the XML event-streaming component determines the XML event based on the criteria;

(3) matching the XML event to said next unmatched step in the XPath expression;

(4) repeating steps 1-3 with respect to a new next unmatched step in the XPath expression, until it is determined that there are no remaining unmatched steps in the XPath expression; and

(5) outputting an XPath result based at least upon the XML event streamed in the last iteration of step 2.

Relevance

See the Excerpt.

Claim Chart

Some

A method for evaluating an XPath expression comprising the computer-implemented steps of:compiling a state machine based on an XPath expression, the state machine comprising states and transitions that reflect the steps of the XPath expression;

evaluating the XPath expression using the state machine, wherein the step of evaluating comprises:receiving one or more XML events from an XML event-streaming component;

maintaining state information based on the content and ordering of the one or more XML events, wherein the state information indicates a current state in the state machine;

based at least upon transitions from the current state to subsequent states, determining criteria, wherein the criteria describes characteristics of any XML event that will transition the state machine to at least one of the subsequent states;

requesting, from the XML event-streaming component, a next XML event that meets the criteria;

in response to said requesting, receiving an XML event from the XML streaming component that meets the criteria; and

generating an XPath result based on the evaluation.

Relevance

See the Excerpt.

Claim Chart

Some

0 days left