more complex patterns for CEP (was: CEP two transitions to the same state)

[Frank Dekervel <ke...@gmail.com>]

Hello,

i did some more analysis wrt the problem i'm facing and the flink CEP api.

In order to complete the problem i'm facing using flink CEP i would need 3
additions to the API (i think). I tried to understand the NFA logic, and i
think 2 of them should be doable without fundamental changes.

First is to add a "negative" pattern (notFollowedBy / notNext):

Reason is the flow below: i have a start and a termination event, and an
optional "failure" event in between. i want all succesful termination
events, so i want to express there should not be a failure event between
the start and the termination event. Note that there is no "success" event
in this case on which i could match.

[image: Inline image 1]

To implement, upon checking whether a transition would be possible, one
would first need to check if it was not already dead-ended by a
notFollowedBy / notNext. This would add a bit of complexity to the logic
(when seeing if a transition is valid for a state, first check if on this
state there was not already a match made to an notFollowedBy/notNext state.
in that case one would reject the match)

Second is to allow the filterfunction to inspect the partial match made, so
one would be able to filter based on the already-matched event. Reason is
the following (hypothetical) example where we would match arrivals of a
trains in a station. We cannot keyBy train (because the "occupied" events
of the station don't have train information), neither can we keyBy station
(as the start of the sequence is outside the station), so we need to add an
additional condition for the second event: the train number must equal the
train number of the first one. And in the third event, the station number
should equal the station number of the second one.

I think this could be accomplished by overloading the where function with a
second filterfunction variant that takes 2 parameters: the event considered
+ the partial match (as a Map<String,T> with T the class of the event)

[image: Inline image 2]

Third one is - i think - more difficult to accomplish, and that's more
complex graphs i asked in my original e-mail (eg two states having 2
transitions ending in the same state).
The problem here is that it allows one to construct cyclic states, and the
PatternStream takes a Map<String,T> as input, which cannot express a state
occuring twice, neither the order (which event was the first and which
event was the second). In the problem i'm trying to solve cyclic states are
not necessary, but i can imagine usecases exist.

[image: Inline image 3]
I think the NFA implementation would already allow such scenario's but the
nfacompiler and the CEP api would need changing.

I wonder if the problem i'm facing is exotic (so a custom CEP would be more
logic) or it is just something that should be implemented in the flink CEP.
I'm relatively new to CEP, so i cannot compare which other
systems/implementations. I'd like to try implementing the changes myself
(at least the first two) after taking some advice here ...

thanks!
greetings,
Frank






On Wed, Sep 14, 2016 at 5:22 PM, Frank Dekervel <ke...@gmail.com> wrote:

> Hello,
>
> I'm trying to model a FSM using the flink CEP patterns. However, there is
> something i can't figure out as all the documentation examples are linear
> (either you go to the single possible next state, either no match).
>
> Suppose that two transitions lead from one state to two different states.
> I guess this is doable by just defining multiple followedBy/next on the
> same state.
>
> But what about two different states that can end up in the same state (in
> the order / delivery example: suppose there are two different delivery
> methods, having a separate starting state but resulting in the same end
> state). It is possible to deduplicate the "delivered" state but this would
> lead to difficult to manage patterns when things get more complex.
>
> Thanks!
> greetings,
> Frank
>
>
>
>

Re: more complex patterns for CEP (was: CEP two transitions to the same state)

[Till Rohrmann <tr...@apache.org>]

Hi Frank,

thanks for sharing your analysis. It indeed pinpoints some of the current
CEP library's shortcomings.

Let me address your points:

1. Lack of not operator

The functionality to express events which must not occur in a pattern is
missing. We've currently a JIRA [1] which addresses exactly this. For the
notFollowedBy operator, we should discard all patterns where we've seen a
matching event for the not state. I think it could be implemented like a
special terminal state where we prune the partial pattern.

For the notNext operator, we could think about keeping the event which has
not matched the notNext state and return it as part of the fully matched
pattern. Alternatively, we could simply forget about it once we've assured
that it does not match.

2. Allow functions to access fields of previous events

This hasn't been implemented yet because it is a quite expensive operation.
Before calling the filter function you always have to reconstruct the
current partial pattern and then give it to the filter function. But I
agree that the user should be allowed to use such a functionality (and then
pay the price for it in terms of efficiency). Giving access to the
partially matched fields via a Map would be a way to solve the problem on
the API level.

I think that almost all functionality for this feature is already in place.
We simply would have to check the filter condition whether they require
access to previous events and then compute the partial pattern.

3. Support for recursive patterns

The underlying SharedBuffer implementation should allow recursive event
patterns. Once we have support for branching CEP patterns [2] which allow
to connect different states this should also be possible with some minor
changes.

However, a more interesting way to specify recursive CEP patterns is to use
regular expression syntax (Kleene star, bounded occurrences) to express
recursive parts of a pattern. I think this makes specifying such a pattern
easier and more intuitive for the user. We've also a JIRA issue to track
the process there [3] and Ivan is already working on this.

If you want to get involved in Flink's CEP development, then feel free to
take over any free JIRA issue or create one yourself :-)

[1] https://issues.apache.org/jira/browse/FLINK-3320
[2] https://issues.apache.org/jira/browse/FLINK-4641
[3] https://issues.apache.org/jira/browse/FLINK-3318

Cheers,
Till

On Fri, Sep 16, 2016 at 10:04 PM, Frank Dekervel <ke...@gmail.com> wrote:

> Hello,
>
> i did some more analysis wrt the problem i'm facing and the flink CEP api.
>
> In order to complete the problem i'm facing using flink CEP i would need 3
> additions to the API (i think). I tried to understand the NFA logic, and i
> think 2 of them should be doable without fundamental changes.
>
> First is to add a "negative" pattern (notFollowedBy / notNext):
>
> Reason is the flow below: i have a start and a termination event, and an
> optional "failure" event in between. i want all succesful termination
> events, so i want to express there should not be a failure event between
> the start and the termination event. Note that there is no "success" event
> in this case on which i could match.
>
> [image: Inline image 1]
>
> To implement, upon checking whether a transition would be possible, one
> would first need to check if it was not already dead-ended by a
> notFollowedBy / notNext. This would add a bit of complexity to the logic
> (when seeing if a transition is valid for a state, first check if on this
> state there was not already a match made to an notFollowedBy/notNext state.
> in that case one would reject the match)
>
> Second is to allow the filterfunction to inspect the partial match made,
> so one would be able to filter based on the already-matched event. Reason
> is the following (hypothetical) example where we would match arrivals of a
> trains in a station. We cannot keyBy train (because the "occupied" events
> of the station don't have train information), neither can we keyBy station
> (as the start of the sequence is outside the station), so we need to add an
> additional condition for the second event: the train number must equal the
> train number of the first one. And in the third event, the station number
> should equal the station number of the second one.
>
> I think this could be accomplished by overloading the where function with
> a second filterfunction variant that takes 2 parameters: the event
> considered + the partial match (as a Map<String,T> with T the class of the
> event)
>
> [image: Inline image 2]
>
> Third one is - i think - more difficult to accomplish, and that's more
> complex graphs i asked in my original e-mail (eg two states having 2
> transitions ending in the same state).
> The problem here is that it allows one to construct cyclic states, and the
> PatternStream takes a Map<String,T> as input, which cannot express a state
> occuring twice, neither the order (which event was the first and which
> event was the second). In the problem i'm trying to solve cyclic states are
> not necessary, but i can imagine usecases exist.
>
> [image: Inline image 3]
> I think the NFA implementation would already allow such scenario's but the
> nfacompiler and the CEP api would need changing.
>
> I wonder if the problem i'm facing is exotic (so a custom CEP would be
> more logic) or it is just something that should be implemented in the flink
> CEP. I'm relatively new to CEP, so i cannot compare which other
> systems/implementations. I'd like to try implementing the changes myself
> (at least the first two) after taking some advice here ...
>
> thanks!
> greetings,
> Frank
>
>
>
>
>
>
> On Wed, Sep 14, 2016 at 5:22 PM, Frank Dekervel <ke...@gmail.com> wrote:
>
>> Hello,
>>
>> I'm trying to model a FSM using the flink CEP patterns. However, there is
>> something i can't figure out as all the documentation examples are linear
>> (either you go to the single possible next state, either no match).
>>
>> Suppose that two transitions lead from one state to two different states.
>> I guess this is doable by just defining multiple followedBy/next on the
>> same state.
>>
>> But what about two different states that can end up in the same state (in
>> the order / delivery example: suppose there are two different delivery
>> methods, having a separate starting state but resulting in the same end
>> state). It is possible to deduplicate the "delivered" state but this would
>> lead to difficult to manage patterns when things get more complex.
>>
>> Thanks!
>> greetings,
>> Frank
>>
>>
>>
>>
>

Re: more complex patterns for CEP - Negation (was: CEP two transitions to the same state)

[Till Rohrmann <tr...@apache.org>]

Hi LF,

this feature (not occurrence of an event) can definitely be implemented and
the community is currently working on it. I think that both scenarios
you're describing a legit use cases and Flink's implementation of the not
operator should cover both.

I hope that this feature can be used soon. For a more detailed answer of
Frank's email see [1].

[1]
http://apache-flink-user-mailing-list-archive.2336050.n4.nabble.com/more-complex-patterns-for-CEP-was-CEP-two-transitions-to-the-same-state-td9046.html

Cheers,
Till

On Sun, Sep 18, 2016 at 7:37 AM, <lg...@yahoo.com> wrote:

> Hi,
>
>
>
> We are also looking for negation (absence of an event) functionality in
> Flink CEP. Something like notFollowedBy/notNext that detects the following
> patterns will be great additions to Flink CEP (other CEP frameworks support
> negation):
> 1. Occurrence of an event (that matches specific criteria) followed by
> absence of an event (that matches specific criteria) followed by another
> event (that matches specific different criteria)
> 2. Occurrence of an event (that matches specific criteria) followed by
> absence of an event (that matches specific criteria) for a specific period
>
> Could this be implemented?
>
> Thank you.
>
>
> - LF
>
>
> ------------------------------
> *From:* Frank Dekervel <ke...@gmail.com>
> *To:* user@flink.apache.org
> *Sent:* Friday, September 16, 2016 1:04 PM
> *Subject:* more complex patterns for CEP (was: CEP two transitions to the
> same state)
>
> Hello,
>
> i did some more analysis wrt the problem i'm facing and the flink CEP api.
>
> In order to complete the problem i'm facing using flink CEP i would need 3
> additions to the API (i think). I tried to understand the NFA logic, and i
> think 2 of them should be doable without fundamental changes.
>
> First is to add a "negative" pattern (notFollowedBy / notNext):
>
> Reason is the flow below: i have a start and a termination event, and an
> optional "failure" event in between. i want all succesful termination
> events, so i want to express there should not be a failure event between
> the start and the termination event. Note that there is no "success" event
> in this case on which i could match.
>
> [image: Inline image 1]
>
> To implement, upon checking whether a transition would be possible, one
> would first need to check if it was not already dead-ended by a
> notFollowedBy / notNext. This would add a bit of complexity to the logic
> (when seeing if a transition is valid for a state, first check if on this
> state there was not already a match made to an notFollowedBy/notNext state.
> in that case one would reject the match)
>
> Second is to allow the filterfunction to inspect the partial match made,
> so one would be able to filter based on the already-matched event. Reason
> is the following (hypothetical) example where we would match arrivals of a
> trains in a station. We cannot keyBy train (because the "occupied" events
> of the station don't have train information), neither can we keyBy station
> (as the start of the sequence is outside the station), so we need to add an
> additional condition for the second event: the train number must equal the
> train number of the first one. And in the third event, the station number
> should equal the station number of the second one.
>
> I think this could be accomplished by overloading the where function with
> a second filterfunction variant that takes 2 parameters: the event
> considered + the partial match (as a Map<String,T> with T the class of the
> event)
>
> [image: Inline image 2]
>
> Third one is - i think - more difficult to accomplish, and that's more
> complex graphs i asked in my original e-mail (eg two states having 2
> transitions ending in the same state).
> The problem here is that it allows one to construct cyclic states, and the
> PatternStream takes a Map<String,T> as input, which cannot express a state
> occuring twice, neither the order (which event was the first and which
> event was the second). In the problem i'm trying to solve cyclic states are
> not necessary, but i can imagine usecases exist.
>
> [image: Inline image 3]
> I think the NFA implementation would already allow such scenario's but the
> nfacompiler and the CEP api would need changing.
>
> I wonder if the problem i'm facing is exotic (so a custom CEP would be
> more logic) or it is just something that should be implemented in the flink
> CEP. I'm relatively new to CEP, so i cannot compare which other
> systems/implementations. I'd like to try implementing the changes myself
> (at least the first two) after taking some advice here ...
>
> thanks!
> greetings,
> Frank
>
>
>
>
>
>
> On Wed, Sep 14, 2016 at 5:22 PM, Frank Dekervel <ke...@gmail.com> wrote:
>
> Hello,
>
> I'm trying to model a FSM using the flink CEP patterns. However, there is
> something i can't figure out as all the documentation examples are linear
> (either you go to the single possible next state, either no match).
>
> Suppose that two transitions lead from one state to two different states.
> I guess this is doable by just defining multiple followedBy/next on the
> same state.
>
> But what about two different states that can end up in the same state (in
> the order / delivery example: suppose there are two different delivery
> methods, having a separate starting state but resulting in the same end
> state). It is possible to deduplicate the "delivered" state but this would
> lead to difficult to manage patterns when things get more complex.
>
> Thanks!
> greetings,
> Frank
>
>
>
>
>
>
>
>
>

Re: more complex patterns for CEP - Negation (was: CEP two transitions to the same state)

[lg...@yahoo.com]

Hi,


We are also looking for negation (absence of an event) functionality in Flink CEP. Something like notFollowedBy/notNext that detects the following patterns will be great additions to Flink CEP (other CEP frameworks support negation):1. Occurrence of an event (that matches specific criteria) followed by absence of an event (that matches specific criteria) followed by another event (that matches specific different criteria)2. Occurrence of an event (that matches specific criteria) followed by absence of an event (that matches specific criteria) for a specific period

Could this be implemented?
Thank you.

- LF
 
      From: Frank Dekervel <ke...@gmail.com>
 To: user@flink.apache.org 
 Sent: Friday, September 16, 2016 1:04 PM
 Subject: more complex patterns for CEP (was: CEP two transitions to the same state)
  
Hello,
i did some more analysis wrt the problem i'm facing and the flink CEP api.
In order to complete the problem i'm facing using flink CEP i would need 3 additions to the API (i think). I tried to understand the NFA logic, and i think 2 of them should be doable without fundamental changes.
First is to add a "negative" pattern (notFollowedBy / notNext):
Reason is the flow below: i have a start and a termination event, and an optional "failure" event in between. i want all succesful termination events, so i want to express there should not be a failure event between the start and the termination event. Note that there is no "success" event in this case on which i could match.


To implement, upon checking whether a transition would be possible, one would first need to check if it was not already dead-ended by a notFollowedBy / notNext. This would add a bit of complexity to the logic (when seeing if a transition is valid for a state, first check if on this state there was not already a match made to an notFollowedBy/notNext state. in that case one would reject the match)
Second is to allow the filterfunction to inspect the partial match made, so one would be able to filter based on the already-matched event. Reason is the following (hypothetical) example where we would match arrivals of a trains in a station. We cannot keyBy train (because the "occupied" events of the station don't have train information), neither can we keyBy station (as the start of the sequence is outside the station), so we need to add an additional condition for the second event: the train number must equal the train number of the first one. And in the third event, the station number should equal the station number of the second one.
I think this could be accomplished by overloading the where function with a second filterfunction variant that takes 2 parameters: the event considered + the partial match (as a Map<String,T> with T the class of the event)


Third one is - i think - more difficult to accomplish, and that's more complex graphs i asked in my original e-mail (eg two states having 2 transitions ending in the same state). The problem here is that it allows one to construct cyclic states, and the PatternStream takes a Map<String,T> as input, which cannot express a state occuring twice, neither the order (which event was the first and which event was the second). In the problem i'm trying to solve cyclic states are not necessary, but i can imagine usecases exist.

I think the NFA implementation would already allow such scenario's but the nfacompiler and the CEP api would need changing.
I wonder if the problem i'm facing is exotic (so a custom CEP would be more logic) or it is just something that should be implemented in the flink CEP. I'm relatively new to CEP, so i cannot compare which other systems/implementations. I'd like to try implementing the changes myself (at least the first two) after taking some advice here ...
thanks!greetings,Frank





On Wed, Sep 14, 2016 at 5:22 PM, Frank Dekervel <ke...@gmail.com> wrote:

Hello,
I'm trying to model a FSM using the flink CEP patterns. However, there is something i can't figure out as all the documentation examples are linear (either you go to the single possible next state, either no match).
Suppose that two transitions lead from one state to two different states. I guess this is doable by just defining multiple followedBy/next on the same state.
But what about two different states that can end up in the same state (in the order / delivery example: suppose there are two different delivery methods, having a separate starting state but resulting in the same end state). It is possible to deduplicate the "delivered" state but this would lead to difficult to manage patterns when things get more complex.
Thanks!greetings,Frank