Techniques for matching a certain class of regular expression-based patterns in data streams

• US 8,498,956 B2
• Filed: 08/26/2009
• Issued: 07/30/2013
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Srinivasan, Anand, Komuravelli, Rakesh, Jain, Namit, Mishra, Shailendra
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US12/548,209
• Publication Number:
  US 20100057663A1
• Time in Patent Office: 1,434 Days
• Field of Search: 706/52, 706/45
• US Class Current: 706/52
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing

Abstract

Techniques for detecting patterns in data streams. A pattern to be detected may be specified using a regular expression. Events received in data streams are then processed during runtime to detect occurrences of the pattern specified by the regular expression in the data stream. If the pattern to be matched belongs to a certain predetermined class of patterns, then a pattern matching technique that is customized for that class of patterns is used during the runtime events processing.

Claims

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

a memory storing a plurality of instructions;

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

receive predicate information, the predicate information specifying a predicate associated with each symbol in a set of one or more symbols, and the predicate information expressing an inequality relationship between (1) a value from the data stream and (2) a specified value;

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

maintain a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event; and

determine if the pattern is matched due to the received event based upon the set of one or more bindings.

2. The system of claim 1 wherein the processor is configured to:

determine, for each symbol in the set of symbols, that the predicate for the symbol is independent of another symbol in the set of symbols;

determine, for each symbol in the regular expression,

if a quantifier is associated with the symbol, then whether the quantifier is only one of a quantifier indicating zero or more occurrences of the symbol, a quantifier indicating one or more occurrences of the symbol, or a quantifier indicating zero or more occurrences of the symbol.

3. The system of claim 1 wherein the processor is configured to:

determine that an alternation operator, a grouping operator, or an aggregation operator over the same symbol is not specified in the regular expression; and

determine whether the symbols in the regular expression are linked only using a concatenation operator.

4. The system of claim 1 wherein the processor is configured to:

determine a first set of one or more bindings after processing a first received event, each binding in the first set of bindings indicating a degree to which the pattern is matched as a result of receiving the first event, the first set of bindings determined based upon a second set of one or more bindings maintained after receipt of a second event received before the first event, each binding in the second set of bindings indicating a degree to which the pattern is matched as a result of receiving the second event.

5. The system of claim 1 wherein the processor is configured to:

for each event received in the data stream,

determine if a symbol from the set of symbols is matched by the received event, wherein a symbol in the set of symbols is matched if the predicate associated with the symbol is satisfied due to the received event, and

determine the set of one or more bindings maintained after processing the received event based upon the matched symbols.

6. The system of claim 1 wherein the processor is configured to:

construct an automaton for the pattern;

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;

determine one or more states of the automaton and associated bindings based upon the one or more symbols and based upon a set of prior states and associated bindings stored prior to receiving the received event; and

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

7. The system of claim 6 wherein the second set of bindings comprises at most one binding for each state in the one or more states.

8. The system of claim 6 wherein a first state in the one or more states has multiple associated bindings, wherein the processor is configured to:

use a set of preconfigured rules to delete at least one or more bindings associated with the first state such that only one binding is maintained for the first state.

9. The system of claim 1 wherein the processor is configured to, when the pattern is matched due to a received event, output a set of events from the data stream that caused the pattern to be matched.

10. A computer-readable non-transitory 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, and the predicate information expressing an inequality relationship between (1) a value from the data stream and (2) a specified value;

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 maintain a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event; and

instructions that cause the processor to determine if the pattern is matched due to the received event based upon the set of one or more bindings.

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

instructions that cause the processor to determine, for each symbol in the set of symbols, that the predicate for the symbol is independent of another symbol in the set of symbols;

instructions that cause the processor to determine, for each symbol in the regular expression, if a quantifier is associated with the symbol, then whether the quantifier is only one of a quantifier indicating zero or more occurrences of the symbol, a quantifier indicating one or more occurrences of the symbol, or a quantifier indicating zero or more occurrences of the symbol.

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

instructions that cause the processor to determine that an alternation operator, a grouping operator, or an aggregation operator over the same symbol is not specified in the regular expression; and

instructions that cause the processor to determine whether the symbols in the regular expression are linked only using a concatenation operator.

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

instructions that cause the processor to determine a first set of one or more bindings after processing a first received event, each binding in the first set of bindings indicating a degree to which the pattern is matched as a result of receiving the first event, the first set of bindings determined based upon a second set of one or more bindings maintained after receipt of a second event received before the first event, each binding in the second set of bindings indicating a degree to which the pattern is matched as a result of receiving the second event.

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

instructions that cause the processor to construct an automaton based upon the regular expression; and

instructions that cause the processor to determine the set of bindings maintained after each received event using the automaton.

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

for each event received in the data stream,

instructions that cause the processor to determine if a symbol from the set of symbols is matched by the received event, wherein a symbol in the set of symbols is matched if the predicate associated with the symbol is satisfied due to the received event, and

instructions that cause the processor to determine the set of one or more bindings maintained after processing the received event based upon the matched symbols.

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

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

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;

determine one or more states of the automaton and associated bindings based upon the one or more symbols and based upon a set of prior states and associated bindings stored prior to receiving the received event; and

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

17. The computer-readable storage medium of claim 16 wherein the second set of bindings comprises at most one binding for each state in the one or more states.

18. The computer-readable storage medium of claim 16 wherein a first state in the one or more states has multiple associated bindings, the method further comprising:

using a set of preconfigured rules to delete at least one binding associated with the first state.

19. The computer-readable storage medium of claim 10 wherein the plurality of instructions further comprises, when the pattern is matched due to a received event, instructions that cause the processor to output a set of events from the data stream that caused the pattern to be matched.

20. 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, and the predicate information expressing an inequality relationship between (1) a value from the data stream and (2) a specified value;

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

maintaining, at the processing system, a set of one or more bindings after processing each event received in the data stream, each binding in the set of bindings indicating a degree to which the pattern is matched as a result of the received event;

determining, at the processing system, if the pattern is matched due to the received event based upon the set of one or more bindings; and

outputting a set of events from the data stream that cause the pattern to be matched;

wherein determining if the pattern is matched comprises;

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,

determining one or more states of an automaton constructed for the pattern and associated bindings based upon the one or more symbols and based upon a set of prior states and associated bindings stored prior to receiving the received event, and

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