A Method for Semantic Optimization of Complex Event Processing
Olga Poppe · 2011
Semantic optimization of database queries, i.e. the use of metadata for query optimization, is well investigated and has led to signi cant performance gains. This report shows that semantic optimization of database systems is applicable to complex event processing (CEP) and has even greater potential in this eld. However, in CEP in contrast to database systems, the validity of data and metadata, and the evaluation of queries are dependent from particular time intervals or application states. Many event-based applications have numerous involved work ow determined constraints. For these reasons, a new kind of CEP metadata, called Instantiating Hierarchical Timed Automata (IHTA), is formally de ned in this report. IHTA formalize application states very naturally. They capture complex causal, temporal, cardinality, and data dependencies between events and states. They are modular and represent an arbitrary number of concurrent processes. To keep IHTA readable, only the work ow determined part of application semantics is captured by them. The rest of the application speci c knowledge is expressed by constraints in the Event Stream Constraint Language (ESCL) developed in this work. ESCL constraints are short but expressive rst-order logic formulas capturing causal, temporal, cardinality, data, and spatial dependencies between events and states. ESCL has strong formal foundations. Its declarative semantics is de ned very similarly to the Tarski model theory. The operational semantics of ESCL is the algorithm semantically rewriting CEP queries with respect to ESCL constraints which is the adaption of the respective algorithm for database systems [31] to CEP. (IHTA will be transformed into ESCL constraints to be used for semantic query optimization by the same algorithm. This transformation is still subject for future work.) To reduce the number of constraints which must be speci ed by the user in ESCL directly, ESCL cardinality constraints are propagated from base events (states) to the derived events (states) with respect to the queries deriving them. Propagation of other