NESTED COMPLEX SEQUENCE PATTERN QUERIES OVER EVENT STREAMS

• US 20130066855A1
• Filed: 03/27/2012
• Published: 03/14/2013
• Est. Priority Date: 09/12/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Wang, Song, Mehta, Abhay, Rundensteiner, Elke Angelika, Gupta, Chetan Kumar, Liu, Mo, Ray, Medhabi
• Granted Patent: US 9,298,773 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method of evaluating nested complex sequence pattern queries includes obtaining events from an event stream and evaluating the events within a first window using an outer query to produce outer partial results. The method also includes determining a more stringent window constraint, the more stringent window constraint comprising a subset of the window constraint corresponding to events that produces the outer partial results and passing the more stringent window constraint to an inner query nested within the outer query. A complex event processing system is also provided.

Claims

1. A method of evaluating nested complex sequence pattern queries comprising:

obtaining events from an event stream;

evaluating the events within a first window using an outer query to produce outer partial results;

determining a more stringent window constraint, the more stringent window constraint comprising a subset of the window constraint corresponding to events that produces the outer partial results; and

passing the more stringent window constraint to an inner query nested within the outer query.

2. The method of claim 1, further comprising:

evaluating events within the more stringent window constraint using the inner query to produce qualified result sequences; and

passing the qualified result sequences back up to the outer query.

3. The method of claim 2, further comprising joining the outer partial results with the qualified result sequences to produce an outer result.

4. The method of claim 1, further comprising:

allocating events into stacks; and

applying iterative execution until a root operator produces a final result.

5. The method of claim 1, further comprising, when the outer query consumes the next event, repeating:

evaluating the events within the window constraint;

determining the more stringent window constraint; and

passing the more stringent window constraint to an inner query nested within the outer query.

6. The method of claim 1, further comprising passing correlated predicates between nested inner and outer queries.

7. The method of claim 1, further comprising filtering outer partial results if the inner query comprises a negative query that produces a result set that is not empty.

8. The method of claim 1, further comprising if a negation is bounded by an adjacent sub-query, then using a delayed constraint during evaluation of the adjacent sub-query.

9. A complex event processing system comprising:

an event stream;

a computational device;

a complex event processing engine for receiving event from the event stream, in which the complex event processing engine is hosted by the computational device;

nested complex sequence pattern query executed by the complex event processing engine, the nested complex sequence pattern query comprising;

an outer query;

an inner child sub-query nested within the outer query, in which the outer query is evaluated prior to evaluation of the inner child sub-query; and

a window constraint derived from the outer query, the window constraint being passed down to the inner child sub-query, the inner child sub-query being evaluated within the window constraint.

10. The system of claim 9, in which window constraints are generated for each partial result of the outer query and each of the window constraints is passed down a respective inner child sub-query for evaluation, the inner child sub-query computing results based on events within the event stream constrained by the window constraints to produce qualified result sequences.

11. The system of claim 10, in which the qualified result sequences are passed up to the outer query.

12. The system of claim 11, further comprising local results generated by the outer query, in which the outer query joins the qualified result sequences with the local results.

13. The system of claim 9, further comprising a root operator, in which evaluation of the outer query and inner child query are performed iteratively and passed upward to the root operator until a final result sequence is produced by the root operator.

14. The system of claim 9, in which the inner child sub-query comprises a negative event instance bounded by positive event instances in the outer query, in which the positive event instances are first evaluated and define the window constraint;

the window constraint is passed to the inner child sub-query, the inner child sub-query for evaluating event instances in the window constraint and passing the subset of events that meet the negative criteria back up to the outer query.

15. A complex event processing system comprising:

an event stream;

a computational device;

a complex event processing engine for receiving event from the event stream, in which the complex event processing engine is hosted by the computational device by executing computer readable instructions by a processor in the computational device;

nested complex sequence pattern query executed by the complex event processing engine, the nested complex sequence pattern query comprising;

an outer query;

an inner child sub-query nested within the outer query, in which the outer query is evaluated prior to evaluation of the inner child sub-query;

a window constraint derived from the outer query, the window constraint being passed down to the inner child sub-query, the inner child sub-query being evaluated within the window constraint, in which window constraints are generated for each partial result of the outer query and each of the window constraints is passed down a respective inner child sub-query for evaluation, the inner child sub-query computing results based on events within the event stream constrained by the window constraints to produce qualified result sequences that are passed up to the outer query; and

local results generated by the outer query, in which the outer query joins the qualified result sequences with the local results;

a root operator, in which evaluation of the outer query and inner child query are performed iteratively and passed upward to the root operator until a final result sequence is produced by the root operator;

a contextual delay constraint for passing up intermediate results when evaluating event instances in the window constraint with the inner child sub-query;

local predicates for filtering events before being stored in a stack; and

an attribute value passed from the outer query to the inner child query to correlate the outer query with the inner child query, the events within the window constraint being evaluated against the attribute value by the inner child query to determine which events are relevant to the outer query;

in which partial outer results from the outer query are joined with the inner query results of the inner child query.