Complex Event Processing with XChangeEQ

The emergence of event-driven architectures, automation of business
processes, drastic cost-reductions in sensor technology, and a
growing need to monitor IT systems (as well as other systems) due
to legal, contractual, or operational considerations lead to an
increasing generation of events. This development is accompanied by
a growing demand for managing and processing events in an automated
and systematic way. Complex Event Processing (CEP) encompasses the
(automatable) tasks involved in making sense of all events in a
system by deriving higher-level knowledge from lower-level events
while the events occur, i.e., in a timely, online fashion and
permanently. At the core of CEP are queries which monitor streams
of "simple" events for so-called complex events, that is, events or
situations that manifest themselves in certain combinations of
several events occurring (or not occurring) over time and that
cannot be detected from looking only at single events. Querying
events is fundamentally different from traditional querying and
reasoning with database or Web data, since event queries are
standing queries that are evaluated permanently over time against
incoming streams of event data. In order to express complex events
that are of interest to a particular application or user in a
convenient, concise, cost-effective and maintainable manner,
special purpose Event Query Languages (EQLs) are needed. This
thesis investigates practical and theoretical issues related to
querying complex events, covering the spectrum from language design
over declarative semantics to operational semantics for incremental
query evaluation. Its central topic is the development of the
high-level event query language XChangeEQ. In contrast to previous
data stream and event query languages, XChangeEQ's language design
recognizes the four querying dimensions of data extractions, event
composition, temporal relationships, and, for non-monotonic queries
involving negation or aggregation, event accumulation. XChangeEQ
deals with complex structured data in event messages, thus
addressing the need to query events communicated in XML formats
over the Web. It supports deductive rules as an abstraction and
reasoning mechanism for events. To achieve a full coverage of the
four querying dimensions, it builds upon a separation of concerns
of the four querying dimensions, which makes it easy-to-use and
highly expressive. A recurrent theme in the formal foundations of
XChangeEQ is that, despite the fundamental differences between
traditional database queries and event queries, many well-known
results from databases and logic programming are, with some
importance changes, applicable to event queries. Declarative
semantics for XChangeEQ are given as a (Tarski-style) model theory
with accompanying fixpoint theory. This approach accounts well for
(1) data in events and (2) deductive rules defining new events from
existing ones, two aspects often neglected in previous work of
semantics of EQLs. For the evaluation of event queries, this work
introduces operational semantics based on an extended and tailored
form of relational algebra and query plans with materialization
points. Materialization points account for storing and maintaining
information about those received events that are relevant for,
i.e., can contribute to, future query answers, as well as for an
incremental evaluation that avoids recomputing certain intermediate
results. Efficient state maintenance in incremental evaluation is
approached by "differentiating" algebra expressions, i.e., by
deriving expressions for computing only the changes to
materialization points. Knowing how long an event is relevant is a
prerequisite for performing garbage collection during event query
evaluation and also of central importance for developing cost-based
query planners. To this end, this thesis introduces a notion of
relevance of events (to a given query plan) and develops methods
for determining temporal relevance, a particularly useful form
based on time-related information.