Query Decomposition for Distributed Complex Event Processing

Complex Event Processing (CEP) Systeme evaluieren Abfragen über hochfrequenten Ereignisströmen, um relevante Muster darin zu erkennen. In Szenarien mit verteilten Ereignisquellen, etwa in Sensornetzwerken oder IoT-Anwendungen, gewinnt CEP zunehmend an Bedeutung. Bestehende Ansätze nutzen das Optimierungspotenzial in solchen Netzwerken nur begrenzt aus. Diese Dissertation stellt Techniken zur Optimierung verteilter Mustererkennung vor, die darauf abzielen, die Netzwerkkosten, also die Anzahl der im Netzwerk ausgetauschten Nachrichten, zu minimieren. Dazu nutzen wir sowohl die Semantik der Abfragesprache als auch Netzwerkeigenschaften aus. Insbesondere führen wir eine Dekompositionstechnik von Mustern ein, mit der korrekte Teilmuster spezifiziert und für die verteilte Erkennung genutzt werden können. Darauf aufbauend führen wir Modelle für die verteilte Mustererkennung in Netzwerken ein: MuSE- und INEv-Graphen. Während MuSE-Graphen eine vollständige Netzwerktopologie voraussetzen, erlauben INEv-Graphen beliebige Netzwerktopologien und spezifizieren die effizienten Weiterleitung von Ereignissen. Zusätzlich untersuchen wir die Ereignisübertragung. Während Ereignisse üblicherweise sofort nach ihrer Generierung versandt werden, können Kommunikationskosten reduziert werden, indem die Übertragung erst durch eine Anfrage geschieht. Hierzu führen wir PrePP-Pläne ein, die die Anfrage-basierte Übertragung von Ereignissen mit Prädikat-basierter Filterung modellieren. Schließlich übertragen wir unsere Dekompositionstechniken auf die parallele Mustererkennung. Dabei analysieren wir Durchsatzengpässe bei Rechenknoten und entwickeln ein Kostenmodell zur Musterdetektion in Clusterumgebungen. Die resultierenden DecoPa-Pläne ermöglichen eine durchsatzoptimierte, parallele Mustererkennung. Für alle Modelle definieren wir formale Eigenschaften, beweisen Korrektheit und geben Konstruktionsalgorithmen an. Experimente zeigen die Überlegenheit unserer Ansätze gegenüber bestehenden Verfahren.