CN-122019635-A - Complex event processing method based on extended regular tree mode

CN122019635ACN 122019635 ACN122019635 ACN 122019635ACN-122019635-A

Abstract

The application discloses a complex event processing method based on an extended regular tree mode, which relates to the technical field of complex event processing, and provides an ERTP (equal cost performance) as a description mode of a unified query mode, wherein the method comprises the steps of simultaneously expressing structure, time sequence and attribute constraint in a single mode, performing structure matching on a tree mode part, storing partial matching results into an instance set, recursively enumerating and checking a conditional expression when a root node list is updated, outputting a return node corresponding event, and performing incremental time sequence matching based on a symbol storage automaton (SMA) on the regular mode part.

Inventors

LI YIHANG
SU HANG
GAO HONGYU

Assignees

北京工业大学

Dates

Publication Date: 20260512
Application Date: 20260128

Claims (10)

1. A complex event processing method based on an extended regular tree pattern, comprising: Constructing an expanded normal tree pattern ERTP for uniformly describing structural constraints, time sequence constraints and cross-event attribute relation constraints in the same query pattern, wherein the ERTP comprises a node group, a normal formula group, a structural relation shaft group, a normal assignment shaft group, a conditional expression group and return requirements; based on the ERTP, matching is carried out from event streams which arrive according to the structure preface order and can judge the structure relation of any two events, and the events needing to be returned in the matching result are output; the matching process includes a structure matching process for tree pattern portions, an automaton-based timing matching process for normal pattern portions, and writing both partial matching results to a shared instance set, and performing enumeration and condition checking to determine output results when the instance set is updated.
2. The method of claim 1, wherein the nodes in ERTP form a tree pattern through a structural relation axis, each node has at most one parent node, the nodes with child nodes are not regular nodes, and at least the nodes with structural relation to another node or are regular nodes are bound to be called as nodes on the tree pattern.
3. The method for processing complex events based on the extended regular tree mode according to claim 1, wherein the automaton used in the timing matching process includes, in addition to a state set, a start state, and a stop state set: The predicate associated with the conditional expression for examining events selected by multiple nodes at the time of state transition, and a return requirement for indicating which events need to be output.
4. The method for complex event processing based on extended regular tree patterns as set forth in claim 1, wherein the set of instances comprises a plurality of lists, each list corresponding to a node on the tree pattern in ERTP for storing an event or sequence of events that partially matches the result; an event in the list is associated with a set of pairs of pointers, including a start pointer and an end pointer, that define a range of descendant events corresponding to a child node or associated normal.
5. The method for complex event processing based on extended regular tree mode as claimed in claim 4, wherein each event is additionally associated with in the list of corresponding regular nodes: a set of automaton running instances for maintaining a plurality of timing matching attempts in the sequence of event sub-events; a candidate list for storing candidate results which are not completely matched successfully; and the result list is used for storing the matched result.
6. The method for complex event processing based on extended regular tree mode as set forth in claim 1, wherein each event in the list of the set of instances is appended with a sibling pointer indicating a location of a next sibling event in the same list.
7. The complex event processing method based on the extended regular tree mode as claimed in claim 1, comprising the steps of: s1, initializing, namely establishing a corresponding empty list for nodes on a tree mode in ERTP to form an instance set, and constructing a corresponding automaton for each normal mode; S2, structure matching processing, namely screening corresponding nodes according to the types of the arrival events, initializing pointer pairs, checking structural relation satisfaction after all offspring of the event are processed, and writing the event meeting the conditions into an instance set corresponding list; S3, performing incremental matching based on automata on the normal expression associated with the normal node, updating a multi-event cache of the running instance, determining state migration according to the predicate transfer check condition, and maintaining a candidate list and a result list according to the state migration; And S4, performing result enumeration, namely performing recursion enumeration from the newly added event when the root node corresponding list is updated, checking by combining the environment update and the conditional expression, and collecting and outputting all return node corresponding events passing the checking.
8. The complex event processing method based on the extended regular tree mode as claimed in claim 7, wherein the structure matching processing adopts a matching stack mechanism, popping a stack when all event offspring are processed, and checking whether parent-child/ancestor precedence relation is satisfied according to a pointer pair update range.
9. The method for complex event processing based on extended regular tree patterns as set forth in claim 7, wherein in the timing matching process, when events are read in for each running instance: Updating the multi-event cache; checking event attributes in the current cache according to the transfer predicates to determine whether to execute state transfer; And if the transition is successful and the event needs to be output, adding the candidate list, and if the ending state is reached, merging the candidate list into a result list and emptying the candidate list.
10. The method for processing complex events based on the extended regular tree mode as set forth in claim 7, wherein the result enumeration process comprises updating a current environment and checking a conditional expression of node binding, recursively invoking enumeration on descendants, requiring at least one descendant check pass for each child node of a denormal node, requiring a descendant check pass for events in at least one result list for a regular node, and collecting return node corresponding events on all pass paths as output.

Description

Complex event processing method based on extended regular tree mode Technical Field The application relates to the technical field of complex event processing, in particular to a complex event processing method based on an extended regular tree mode. Background Complex event processing (Complex Event Processing, CEP) is a class of techniques for identifying combinations of events in a continuously input event stream that satisfy a preset pattern, and outputting matching results. CEP can be applied to the scene of monitoring, alarming and analyzing real-time data. With the development of data sources and business requirements, input data is often semi-structured. For such data, the query pattern typically requires the simultaneous expression of multiple types of constraints, including structural constraints between events (e.g., hierarchical constraints such as parent-child, ancestor-ancestor, etc.), timing constraints (e.g., sequential constraints such as sequencing, repetition, selection, etc.), and attribute-based relational constraints (e.g., comparisons between event attributes, equivalence or threshold determinations, etc.). Some existing CEP solutions represent and execute event timing modes based on models such as automata, perform incremental matching on input events through state transitions, and filter event attributes in combination with predicate conditions. This type of scheme is common when dealing with sequence-based timing constraints. However, when the query pattern further includes constraints on the hierarchy between events (e.g., the tree structure relationship and the sequence relationship need to be satisfied simultaneously), the pattern representation and execution often requires the introduction of additional data structures or staged processing mechanisms to satisfy both the requirements of structure matching and sequence matching. In this case, more intermediate results may be generated in the matching process, thereby increasing the storage and calculation overhead. In addition, in a query scene containing structural constraint, time sequence constraint and cross-event attribute relation constraint at the same time, partial schemes are insufficient in terms of organization mode of relation constraint and unified execution flow. Therefore, how to uniformly describe structure constraint, time sequence constraint and cross-event attribute relation constraint in the same query mode and reduce intermediate results and processing overhead in the stream processing process is still one of the technical problems to be solved in the field. Disclosure of Invention The application provides a complex event processing method based on an extended regular tree mode, which allows a user to describe a query containing structural constraint, time sequence constraint and cross-event attribute relation constraint in the same query mode through ERTP without describing the query in stages, can comprehensively consider various constraints in the query mode to screen events and organize partial results, reduces useless intermediate result generation to a certain extent, improves query efficiency, and can effectively solve the problems in the background technology. In order to achieve the above purpose, the application provides a complex event processing method based on an extended normal tree mode, wherein the ERTP comprises a node group, a normal formula group, a structural relation axis group, a normal formula assignment axis group, a conditional expression group and a return requirement. The method comprises the steps of selecting a node group, wherein the node group is an identifier and used for indicating selection of one type of event, the normal expression group is formed by combining the node groups through sequence, selection, cline closure and other operators and used for describing time sequence constraint among the node selection events, the structural relation shaft group comprises a father-son shaft (PC) and an ancestor-offspring shaft (AD) and used for indicating father-son relation or ancestor-offspring relation among the node selection events, the normal expression assignment shaft group is used for indicating that each event in an event sequence matched by a normal expression is a sub-event of an event selected by another node, the conditional expression group is an expression referencing a plurality of nodes or constants and used for describing relation constraint crossing the event attribute, and the return requirement is used for indicating which events corresponding to the nodes need to be returned as output. Further, the nodes in the ERTP form a tree mode through a structural relation shaft, each node has at most one father node, the nodes with child nodes are not regular nodes, and the nodes which are at least in a binding structural relation with another node or are regular nodes are called as nodes on the tree mode. Based on the ERTP, the application provides a query method for m