Complex event processing with Xchange_1hnE_1hnQ [Elektronische Ressource] : language design, formal semantics, and incremental evaluation for querying events / von Michael Eckert

Michael Eckert

Sujets

• Informatik

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 26
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

EQComplex Event Processing with XChange :
Language Design, Formal Semantics, and Incremental
Evaluation for Querying Events
Dissertation
zur Erlangung des akademischen Grades des
Doktors der Naturwissenschaften
an der Fakult¨at fur¨ Mathematik, Informatik und Statistik
der Ludwig-Maximilians-Universit¨at Munc¨ hen
von
Michael Eckert
22. Oktober 2008Erstgutachter: Prof. Dr. Franc¸ois Bry
(Ludwig-Maximilians-Universtat¨ Mun¨ chen)
Zweitgutachter: Prof. Dr. Martin L. Kersten
(Centrum Wiskunde & Informatica, Amsterdam)
Tag der mund¨ lichen Pruf¨ ung: 09. Dezember 20083
Im Gedenken und Liebe/
In memory and love
K¨athe Tomin, geb. Strathmann
∗ 15.06.1913 † 27.07.200545
Abstract
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
withdatabaseorWebdata,sinceeventqueriesarestandingqueriesthatareevaluatedpermanently
over time against incoming streams of event data. In order to express complex events that are of
interesttoaparticularapplicationoruserinaconvenient, concise, cost-effectiveandmaintainable
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
forincremental query evaluation. Its centraltopic is the developmentofthe high-level event query
EQlanguage XChange .
EQIn contrast to previous data stream and event query languages, XChange ’s language design
recognizes the four querying dimensions of data extractions, event composition, temporal rela-
tionships, and, for non-monotonic queries involving negation or aggregation, event accumulation.
EQXChange 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.
EQA recurrent theme in the formal foundations of XChange 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.
EQDeclarative semantics for XChange are given as a (Tarski-style) model theory with accompa-
nying 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.
Materializationpointsaccountforstoringandmaintaininginformationaboutthosereceivedevents
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
isrelevantisaprerequisiteforperforminggarbagecollectionduringeventqueryevaluationandalso
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.67
Zusammenfassung
Die Einfuhrung von ereignisgesteuerten Architekturen, die Automatisierung von Geschafts-¨ ¨
prozessen, kostengunstige Sensortechnik und die rechtlich, vertraglich oder betrieblich bedingte¨
¨Uberwachung von Informationssystemen erzeugen mehr und mehr Ereignisse. Diese Entwicklung
wird begleitet von einer zunehmenden Notwendigkeit, Ereignisse systematisch und automatisch
zu verwalten und zu verarbeiten. Complex Event Processing (CEP) hat zur Aufgabe hoheres,¨
wertvollen Wissen aus Ereignissen abzuleiten wahrend diese passieren, also kontinuierlich und¨
zeitnah.
Zentral in CEP sind Anfragen, die Strome von einfachen“ Ereignissen uberwachen, um so-¨ ¨
”
genannte komplexe Ereignisse (engl.: complex events) zu erkennen. Komplexe Ereignisse sind Er-
eignisse oder Situationen, die sich durch das gemeinsame, zeitlich verteilte Auftreten (oder Nicht-
Auftreten) von mehreren Ereignissen außern¨ und nicht erkannt werden konn¨ en, indem man nur
einzelne Ereignisse betrachtet. Anfragetechniken fur¨ Ereignisse unterscheiden sich grundlegend
von traditionellen Anfrage- und Schlußtechniken fur¨ Datenbanken oder Web-Daten, denn Ereig-
nisanfragen sind stehende Anfragen, die mit Zeit fortw¨ahrend gegen einen ankommenden Strom
von Ereignisdaten ausgewertet werden. Zur bequemen, kostengun¨ stigen und leicht wartbaren Be-
schreibung von komplexen Ereignissen, die fur¨ eine bestimmte Anwendung oder einen bestimmten
Benutzer von Interesse sind, bedarf es spezieller Ereignisanfragesprachen.
Die vorliegende Arbeit besch¨aftigt sich mit praktischen und theoretischen Fragestellungen zu
Anfragen nach komplexen Ereignissen. Das abgedeckte Themenspektrum reicht von Sprachde-
sign ub¨ er deklarative Semantik bis zu operationaler Semantik fur¨ eine inkrementelle Anfrage-
auswertung. Der rote Faden der Arbeit ist die Entwicklung der hoheren¨ Ereignisanfragesprache
EQXChange .
Im Gegensatz zu vorherigen Datenstrom- und Ereignisanfragesprachen tragt das Sprachdesign¨
EQvonXChange denvierAnfragedimensionenRechnung:ExtraktionvonDaten,Kompositionvon
Ereignissen, zeitliche Zusammenhange und, fur nicht-monotone Anfragen mit Negation oder Ag-¨ ¨
EQgregation, Akkumulation von Ereignissen. XChange kann mit komplex strukturierten Daten in
Ereignissen umgehen, wie sie haufig in Ereignissen, die in XML-Formaten uber das Web kom-¨ ¨
muniziert werden, zu finden sind. Als Abstraktions- und Schlußmechanismus werden deduktive
Regeln unterstutzt. Um eine vollstandige Abdeckung der vier Anfragedimensionen zu erreichen,¨ ¨
EQbaut XChange auf einer Trennung dieser Dimensionen auf, was die Sprache leicht benutzbar
und ausdrucksstark macht.
EQEin Leitmotiv in den formalen Grundlagen von XChange ist, daß trotz der grundlegenden
Unterschiede zwischen traditionellen Datenbankanfragen und Ereignisanfragen viele bekannte Er-
gebnisse aus der Forschung ub¨ er Datenbanken und Logikprogrammierung —mit einigen wichtigen
EQ¨Anderungen— auf Ereignisanfragen anwendbar sind. Die deklarative Semantik von XChange
wirdals(Tarski-)ModelltheoriemitbegleitenderFixpunkttheorieangegeben.DieserAnsatzeignet
sich besonders zur Behandlung von (1) Daten in Ereignissen und (2) deduktive Regeln, die neue
Ereignisse aus existierenden ableiten. Diese beiden Aspekte wurden in vorherigen Arbeiten zur
Semantik von Ereignisanfragesprachen oft vernachlass¨ igt.
ZurAuswertungvonEreignisanfragenfuh¨ rtdieseArbeiteineoperationaleSemantikein,dieauf
einer erweiterten und spezialisierten Form von relationaler Algebra sowie auf Anfragepl¨anen mit
ausgezeichneten Punkten fur¨ Materialisierung aufbaut. Die Materialisierungspunkte dienen dazu,
Informationen ub¨ er Ereignisse, die relevant fur¨ zukun¨ ftige Antworten sein k¨onnen, zu speichern.
Ferner sind sie zweckdienlich fur¨ eine inkrementelle Auswertung, die eine wiederholte Berech-
nung bestimmter Zwischenergebnisse vermeidet. Die effiziente Aktualisierung der Zustande von¨
Materialisierungspunkten basiert auf der Differenzierung“ von Algebraausdrucke, d.h., darauf¨
” ¨neue Ausdrucke abzuleiten, die nur die notigen Anderungen berechnen. Eine Speicherbereinigung¨ ¨
wahrend der Anfrageauswertung setzt voraus zu wissen, wie lange ein Ereignis relevant ist. Die-¨
ses Wissen ist auch von zentraler Bedeutung, um kostenbasierte Anfrageoptimierer zu entwickeln.
Dazu fuhrt diese Arbeit einen Begriff der Relevanz von Ereignissen (bezuglich einem gegebenen¨ ¨
Anfrageplan) ein und entwickelt e