301 Pages
English

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

-

Gain access to the library to view online
Learn more

Description

EQComplex Event Processing with XChange :Language Design, Formal Semantics, and IncrementalEvaluation for Querying EventsDissertationzur Erlangung des akademischen Grades desDoktors der Naturwissenschaftenan der Fakult¨at fur¨ Mathematik, Informatik und Statistikder Ludwig-Maximilians-Universit¨at Munc¨ henvonMichael Eckert22. 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 20083Im Gedenken und Liebe/In memory and loveK¨athe Tomin, geb. Strathmann∗ 15.06.1913 † 27.07.200545AbstractThe 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 othersystems) due to legal, contractual, or operational considerations lead to an increasing generationof events. This development is accompanied by a growing demand for managing and processingevents 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-levelknowledge from lower-level events while the events occur, i.e., in a timely, online fashion andpermanently.

Subjects

Informations

Published by
Published 01 January 2008
Reads 26
Language English
Document size 1 MB

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 eine Methode zur Bestimmung der temporalen Relevanz, einer
besonders nutzlichen Form, die auf zeitbezogenen Informationen basiert.¨89
Acknowledgments
Theworkpresentedinthisthesiswouldnotbewhatistodaywithoutthesupportandcontribution
of many people. Foremost, I would like to express my gratitude to my thesis advisor Fran¸cois
Bry for his continuous support and encouragement. The many fruitful discussion with him have
shaped all aspects of this work as well as my life in research and teaching. I am also indebted to
Martin Kersten for taking on the burden of being the external reviewer for this thesis.
It has been a great pleasure to work with all the people in the programming and modeling
languages research group at the University of Munich (LMU). Sacha Berger, Norbert Eisinger,
Tim Furche, Alex Kohn, Jakub Kotowski, Benedikt Linse, Bernhard Lorenz, Hans Jur¨ gen Ohlbach,
Paula-Lavinia P˘atrˆanjan, Edgar-Philipp Stoffel, Klara Weiand, and Christoph Wieser, have been
fellow researchers and together created an excellent work environment. I greatly enjoyed the time
spent talking to you, listening to you, and teaching with you. The administrative and technical
staff of the group, Stefanie Heidmann, Martin Josko, Ellen Lilge, Uta Schwertel, and Ingeborg von
Troschke, have contributed greatly to making things run smoothly in our group. I thank them for
this and for sometimes even managing to make filling out the most confusing and boring forms a
fun experience.
The following students have worked with me on their theses and deserve my thanks: Hendrik
Grallert has worked on the demonstration of an XChange use case, Stephan Leutenmayr has sur-
veyed languages for Web Service composition, Fatih Co¸skun has developed declarative semantics
forthepattern-basedupdatesofXChange,andHai-Lam Bui iscurrentlyworkingonacomparison
of event query languages in practical applications.
The following colleagues have worked with me on joint publications and on the project pro-
posal “Management of Events on the Web (MEOW)” and not been mentioned yet: Bruno Bers-
tel, Philippe Bonnard, Thomas Geyer, Martin Kluge, Peter Knaack, Inna Romanenko, Nikolaus
Seifert, and Sanja Vranes. I thank them as well as the numerous colleagues from the REWERSE
Network of Excellence.
The research in this work has been partly funded by the European Commission and the Swiss
Federal Office for Education and Science within the 6th Framework Programme project REW-
ERSE (number 506779, see http://rewerse.net). Not only has the funding of this project made
many travels to conferences possible; the network of colleagues that has grown in this project
has greatly helped improved this work. I am also indebted to the Studienstiftung des Deutschen
Volkes and the German-American Fulbright Commission for their financial and non-financial sup-
port during my studies prior to the work on this thesis.
Last but not least, I deeply thank my family, especially my parents, for always supporting and
encouraging me.10