DETECTION OF NON-OCCURRENCES OF EVENTS USING PATTERN MATCHING

• US 20100057737A1
• Filed: 08/26/2009
• Published: 03/04/2010
• Est. Priority Date: 08/29/2008
• Status: Abandoned Application

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mishra, Shailendra, Komuravelli, Rakesh, Srinivasan, Anand
• Application Number:
  US12/548,281
• Publication Number:
  US 20100057737A1
• 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 non-occurrence of an event within a time period following the occurrence of another event. In one embodiment, language extensions are provided to a language that enable queries to be formulated for detecting non-occurrences using that language.

Claims

1. A computer-readable storage medium storing a plurality of instructions for controlling a processor to process a data stream of events, the plurality of instructions comprising:

instructions that cause the processor to receive a query for detecting non-occurrence of a first event within a time period following occurrence of a second event, the query specifying a pattern;

instructions that cause the processor to generate a modified pattern by adding a first symbol to the pattern;

instructions that cause the processor to generate an automaton for the query based upon the modified pattern; and

instructions that cause the processor to detect an instance in the data stream of non-occurrence of the first event within the time period following occurrence of the second event using the automaton.

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

instructions that cause the processor to determine whether the query is for detecting non-occurrence of the first event; and

instructions that cause the processor to, generate the modified pattern only upon determining that the query is for detecting non-occurrence of the first event.

3. The computer-readable storage medium of claim 1 wherein the plurality of instructions comprises instructions that cause the processor to determine the time period from the query.

4. The computer-readable storage medium of claim 1 wherein the plurality of instructions that cause the processor to detect the one or more instances comprises:

instructions that cause the processor to, associate a target time with a binding, wherein the target time is based upon the time of the first element in the binding and the time period;

instructions that cause the processor to receive an input; and

instructions that cause the processor to compare a time associated with the input with the target time.

5. The computer-readable storage medium of claim 4 wherein the input is a heartbeat.

6. The computer-readable storage medium of claim 4 wherein the input is another event received in the data stream.

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

instructions that cause the processor to, upon determining that the time associated with the input equals or exceeds the target time, cause the automaton to move to a final state.

8. A system for processing a data stream of 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 a query for detecting non-occurrence of a first event within a time period following occurrence of a second event, the query specifying a pattern;

generate a modified pattern by adding a first symbol to the pattern;

generate an automaton for the query based upon the modified pattern; and

detect an instance in the data stream of non-occurrence of the first event within the time period following occurrence of the second event using the automaton.

9. The system of claim 8 wherein the processor is configured to:

determine whether the query is for detecting non-occurrence of the first event; and

generate the modified pattern only upon determining that the query is for detecting non-occurrence of the first event.

10. The system of claim 8 wherein the processor is configured to determine the time period from the query.

11. The system of claim 8 wherein the processor is configured to:

associate a target time with a binding, wherein the target time is based upon the time of the first element in the binding and the time period;

receive an input; and

compare a time associated with the input with the target time.

12. The system of claim 11 wherein the input is a heartbeat.

13. The system of claim 11 wherein the input is another event received in the data stream.

14. The system of claim 11 wherein the processor is configured to, upon determining that the time associated with the input equals or exceeds the target time, cause the automaton to move to a final state.

15. A computer-implemented method of processing a data stream of events, the method comprising:

receive, by a processing system, a query for detecting non-occurrence of a first event within a time period following occurrence of a second event, the query specifying a pattern;

generating, by the processing system, a modified pattern by adding a first symbol to the pattern string;

generating, by the processing system, an automaton for the query based upon the modified pattern; and

detecting, by the processing system, an instance an instance in the data stream of non-occurrence of the first event within the time period following occurrence of the second event using the automaton.

16. The method of claim 15 further comprising:

determining, by the processing system, whether the query is for detecting non-occurrence of the first event; and

generating, by the processing system, a modified pattern by adding a first symbol to the pattern only upon determining that the query is for detecting non-occurrence of the first event.

17. The method of claim 15 further comprising determining, by the processing system, the time period from the query.

18. The method of claim 15 wherein detecting the one or more instances comprises:

associating a target time with a binding, wherein the target time is based upon the time of the first element in the binding and the time period;

receiving an input; and

comparing a time associated with the input with the target time.

19. The method of claim 18 wherein the input is a heartbeat or another event received in the data stream.

20. The method of claim 18 further comprising, upon determining that the time associated with the input equals or exceeds the target time, causing the automaton to move to a final state.