TECHNIQUES FOR PERFORMING REGULAR EXPRESSION-BASED PATTERN MATCHING IN DATA STREAMS

• US 20100057736A1
• Filed: 08/26/2009
• Published: 03/04/2010
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mishra, Shailendra, Komuravelli, Rakesh, Jain, Namit, Srinivasan, Anand
• Granted Patent: US 8,589,436 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing

Abstract

Techniques for detecting patterns in one or more data streams. A pattern to be detected may be specified using a regular expression. Events received in a data stream are processed during runtime to detect occurrences of the specified pattern in the data stream.

Claims

1. A method of detecting a pattern in a data stream comprising events, the method comprising:

receiving, at a processing system, predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols;

receiving, at the processing system, a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols;

constructing an automaton for the pattern; and

upon receiving an event in the data stream;

determining, based upon the received event, one or more states of the automaton and associated bindings, wherein at least one state in the one or more states has multiple associated bindings, and

determining if the pattern is matched due to the received event based upon the one or more states and associated bindings.

2. The method of claim 1 further comprising:

upon receiving an event in the data stream, determining one or more symbols from the set of symbols that are matched due to the received event, wherein a symbol is matched if the predicate associated with the symbol is satisfied due to the received event; and

wherein determining the one or more states upon receiving an event in the data stream comprises determining the one or more states based upon the one or more symbols and set of states and associated bindings stored prior to receiving the input event.

3. The method of claim 1 wherein the predicate information specifies a predicate that is associated with a first symbol in the set of symbols and is dependent upon a second symbol included in the set of symbols.

4. The method of claim 1 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

5. The method of claim 1 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

6. The method of claim 1 wherein at least one symbol in the regular expression has an associated lazy quantifier.

7. A computer-readable storage medium storing a plurality of instructions for controlling a processor to detect a pattern in a data stream comprising events, the plurality of instructions comprising:

instructions that cause the processor to receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols;

instructions that cause the processor to receive a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols;

instructions that cause the processor to construct an automaton for the pattern; and

instructions that cause the processor to, upon receiving an event in the data stream,

determine, based upon the received event, one or more states of the automaton and associated bindings, wherein at least one state in the one or more states has multiple associated bindings, and

determine if the pattern is matched due to the received event based upon the one or more states and associated bindings.

8. The computer-readable storage medium of claim 7 wherein the plurality of instructions further comprises:

instructions that cause the processor to, upon receiving an event in the data stream, determine one or more symbols from the set of symbols that are matched due to the received event, wherein a symbol is matched if the predicate associated with the symbol is satisfied due to the received event; and

wherein the instructions that cause the processor to determine the one or more states upon receiving an event in the data stream comprise instructions that cause the processor to determine the one or more states based upon the one or more symbols and set of states and associated bindings stored prior to receiving the input event.

9. The computer-readable storage medium of claim 7 wherein the predicate information specifies a predicate that is associated with a first symbol in the set of symbols and is dependent upon a second symbol included in the set of symbols.

10. The computer-readable storage medium of claim 7 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

11. The computer-readable storage medium of claim 7 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

12. The computer-readable storage medium of claim 7 wherein at least one symbol in the regular expression has an associated lazy quantifier.

13. A system for detecting a pattern in a data stream comprising events, the system comprising:

a memory storing a plurality of instructions; and

a processor coupled to the memory, the processor configured to execute the plurality of instructions to;

receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols;

receive a regular expression specifying a pattern, the regular expression comprising one or more symbols from the set of symbols;

construct an automaton for the pattern; and

upon receiving an event in the data stream,

determine, based upon the received event, one or more states of the automaton and associated bindings, wherein at least one state in the one or more states has multiple associated bindings, and

determine if the pattern is matched due to the received event based upon the one or more states and associated bindings.

14. The system of claim 13 wherein the processor is configured to:

upon receiving an event in the data stream, determine one or more symbols from the set of symbols that are matched due to the received event, wherein a symbol is matched if the predicate associated with the symbol is satisfied due to the received event; and

upon receiving an event in the data stream, determine the one or more states based upon the one or more symbols and set of states and associated bindings stored prior to receiving the input event.

15. The system of claim 13 wherein the predicate information specifies a predicate that is associated with a first symbol in the set of symbols and is dependent upon a second symbol included in the set of symbols.

16. The system of claim 13 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

17. The system of claim 13 wherein the regular expression comprises at least one of an alternation operator, a grouping operator, or an aggregation operator.

18. The system of claim 13 wherein at least one symbol in the regular expression has an associated lazy quantifier.