Runtime semantic query optimization for event stream processing

• US 8,065,319 B2
• Filed: 12/05/2007
• Issued: 11/22/2011
• Est. Priority Date: 04/01/2007
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Ding, Luping, Hsiung, Wang-Pin, Chen, Songting, Rundensteiner, Elke A, Tatemura, Junichi
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Kim; Paul
• Application Number:
  US11/950,719
• Publication Number:
  US 20090006320A1
• Time in Patent Office: 1,448 Days
• Field of Search: 707/1, 707/769
• US Class Current: 707/769
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Systems and method are disclosed for applying a query to an event stream by storing one or more event constraints; performing constraint aware complex event processing on the query and the event constraints; and optimizing the query at run time.

Claims

1. A method for applying a query to an event stream, comprising:

storing one or more event constraints specifying a predetermined order or occurrence of events in a stream of events ordered by timestamps, wherein the event constraints represent prior knowledge to discern event patterns that can appear in the event stream from patterns that cannot appear in the event stream;

generating a query with one or more correlation rules representing one or more event patterns to be detected in the event stream;

analyzing the query for query unsatisfiability using the event constraints and predicting whether upcoming events satisfy the constraints in the query;

performing constraint aware complex event processing on the query and the event constraints by determining whether the event stream corresponds to the correlation rules in the query; and

optimizing the query by detecting and terminating an unsatisfiable query as early as possible using the query and the event constraints,

where the event stream can be partitioned into multiple sub-sequences based on a predetermined criteria, each partition of the event stream comprising a trace, and

where for a query Q, event constraints C and a partial trace h_p, Q is said to be runtime unsatisfiable if there does not exist a trace h_e that is consistent with C and contains a match to Q, where h_p is prefix of h_e

where event data becomes available in order of occurrences and the partial trace h_p is the prefix of the trace h_e and wherein the trace comprises sub-sequences of the stream of events (event history) and wherein the query Q is runtime unsatisfiable if there does not exist a remaining trace h_p=h_e−

h_p that contains a match to a remaining query.

3. The method of claim 1, comprising checking for runtime query unsatisfiability (RunSAT) using the query, one or more event constraints, and a partial event history and terminating processing of an unsatisfiable query at run time.

4. The method of claim 1, comprising identifying unsatisfiable partial query matches at runtime.

5. The method of claim 3, wherein the RunSAT considers the event query, the partial event history and the event constraints including workflows.

6. The method of claim 3, comprising improving the RunSAT performance by applying a general pre-processing mechanism to pre-compute query failure conditions.

7. The method of claim 1, comprising pre-processing the query with abductive inference.

8. The method of claim 1, comprising applying common event constraints to allow a constant time RunSAT.

9. The method of claim 1, comprising augmenting event queries with pre-computed failure conditions.

10. The method of claim 1, comprising augmenting the query with Event-Condition-Action rules encoding the pre-computed failure conditions.

11. The method of claim 1, comprising discarding an event instance if a query instance has failed.

12. The method of claim 1, comprising discarding an event instance and rejecting a query instance if the event instance causes a global failure condition.

2. A system to process an event stream, comprising:

a constraint database to store one or more event constraints specifying a predetermined order or occurrence of events in a stream of events ordered by timestamps, wherein the event constraints represent prior knowledge to discern event patterns that can appear in the event stream from patterns that cannot appear in the event stream;

a query with one or more correlation rules representing one or more event patterns to be detected in the event stream;

a constraint processor coupled to the database to perform constraint aware complex event processing on a query and the event constraints, the constraint processor analyzing the query for query unsatisfiability using the event constraints and predicting whether upcoming events satisfy the constraints in the query; and

a query processor coupled to the constraint processor to optimize the query optimizing the query by detecting and terminating an unsatisfiable query as early as possible using the query and the event constraints at run time by determining whether the event stream corresponds to the correlation rules in the query,

where the event stream can be partitioned into multiple sub-sequences based on a predetermined criteria, each partition of the event stream comprising a trace, and

where for a query Q, event constraints C and a partial trace h_p, Q is said to be runtime unsatisfiable if there does not exist a trace h_e that is consistent with C and contains a match to Q, where h_p is prefix of h_e

where event data becomes available in order of occurrences and the partial trace h_p is the prefix of the trace h_e and wherein the trace comprises sub-sequences of the stream of events (event history) and wherein the query is runtime unsatisfiable if there does not exist a remaining trace h_p=h_e−

h_p that contains a match to a remaining query.

13. A system to process an event stream, comprising:

a constraint database to store one or more event constraints specifying a predetermined order or occurrence of events in a stream of events ordered by timestamps, wherein the event constraints represent prior knowledge to discern event patterns that can appear in the event stream from patterns that cannot appear in the event stream;

a query with one or more correlation rules representing one or more event patterns to be detected in the event stream;

a constraint processor coupled to the database to perform constraint aware complex event processing on a query and the event constraints, the constraint processor analyzing the query for query unsatisfiability using the event constraints and predicting whether upcoming events satisfy the constraints in the query; and

a query processor coupled to the constraint processor to optimize the query optimizing the query by detecting and terminating an unsatisfiable query as early as possible using the query and the event constraints at run time by determining whether the event stream corresponds to the correlation rules in the query,

where the event stream can be partitioned into multiple sub-sequences based on a predetermined criteria, each partition of the event stream comprising a trace, and

where for a query Q, event constraints C and a partial trace h_p, Q is said to be runtime unsatisfiable if there does not exist a trace h_e that is consistent with C and contains a match to Q, where h_p is prefix of h_e

where event data becomes available in order of occurrences and the partial trace h_p is the prefix of the trace h_e.

14. The system of claim 13, wherein the constraint processor checks for static query unsatisfiability (SunSAT) and statically eliminates processing of an unsatisfiable query.

15. The system of claim 13, wherein the constraint processor checks for runtime query unsatisfiability (RunSAT) using the query, one or more event constraints, and a partial event history and terminating processing of an unsatisfiable query at run time.

16. The system of claim 13, wherein the constraint processor identifies unsatisfiable partial query matches at runtime.

17. The system of claim 15, wherein the RunSAT check considers the event query, the partial event history and the event constraints including workflows.

18. The system of claim 15, comprising improving the RunSAT check performance by applying a general pre-processing mechanism to pre-compute query failure conditions.

19. The system of claim 13, wherein the constraint processor comprises abductive inference.

20. The system of claim 13, wherein the query processor augments the query with Event-Condition-Action rules for encoding the pre-computed failure conditions.