Publikationsserver der Universitätsbibliothek Marburg

Titel: Continuous Queries over Data Streams - Semantics and Implementation
Autor: Krämer, Jürgen
Weitere Beteiligte: Seeger, Bernhard (Prof. Dr.)
Erscheinungsjahr: 2007
URI: https://archiv.ub.uni-marburg.de/diss/z2007/0671
DOI: https://doi.org/10.17192/z2007.0671
URN: urn:nbn:de:hebis:04-z2007-06717
DDC: 004 Informatik
Titel(trans.): Kontinuierliche Anfragen über Datenströmen - Semantik und Implementierung

Dokument

Schlagwörter:
Implementation, Data streams, Optimierung, Continuous queries, Semantics, Datenstrom, Datenstrommanagementsystem, Implementierung, Semantik, Query processing, Abfrageverarbeitung

Summary:
Recent technological advances have pushed the emergence of a new class of data-intensive applications that require continuous processing over sequences of transient data, called data streams, in near real-time. Examples of such applications range from online monitoring and analysis of sensor data for traffic management and factory automation to financial applications tracking stock ticker data. Traditional database systems are deemed inadequate to support high-volume, low-latency stream processing because queries are expected to run continuously and return new answers as new data arrives, without the need to store data persistently. The goal of this thesis is to develop a solid and powerful foundation for processing continuous queries over data streams. Resource requirements are kept in bounds by restricting the evaluation of continuous queries to sliding windows over the potentially unbounded data streams. This technique has the advantage that it emphasizes new data, which in the majority of real-world applications is considered more important than older data. Although the presence of continuous queries dictates rethinking the fundamental architecture of database systems, this thesis pursues an approach that adapts the well-established database technology to the data stream computation model, with the aim to facilitate the development and maintenance of stream-oriented applications. Based on a declarative query language inheriting the basic syntax from the prevalent SQL standard, users are able to express and modify complex application logic in an easy and comprehensible manner, without requiring the use of custom code. The underlying semantics assigns an exact meaning to a continuous query at any point in time and is defined by temporal extensions of the relational algebra. By carrying over the well-known algebraic equivalences from relational databases to stream processing, this thesis prepares the ground for powerful query optimizations. A unique time-interval based stream algebra implemented with efficient online algorithms allows for processing data in a push-based fashion. A performance analysis, along with experimental studies, confirms the superiority of the time-interval approach over comparative approaches for the predominant set of continuous queries. Based upon this stream algebra, this thesis addresses architectural issues of an adaptive and scalable runtime environment that can cope with varying query workload and fluctuating data stream characteristics arising from the highly dynamic and long-running nature of streaming applications. In order to control the resource allocation of continuous queries, novel adaptation techniques are investigated, trading off answer quality for lower resource requirements. Moreover, a general migration strategy is developed that enables the query processing engine to re-optimize continuous queries at runtime. Overall, this thesis outlines the salient features and operational functionality of the stream processing infrastructure PIPES (Public Infrastructure for Processing and Exploring Streams), which has already been applied successfully in a variety of stream-oriented applications.

Zusammenfassung:
Der rapide technologische Fortschritt der vergangenen Jahre hat die Entwicklung einer neuen Klasse von Anwendungen begünstigt, die sich dadurch auszeichnen, dass enorme Datenmengen in Form von Datenströmen bereitgestellt und kontinuierlich verarbeitet werden müssen, um zeitnah wichtige Informationen und Kennzahlen zu ermitteln. Beispiele für Anwendungen finden sich in den unterschiedlichsten Bereichen, die sich von der Überwachung und Auswertung von Sensordaten im Verkehrsmanagement oder der Fabrikautomation bis hin zur Trenderkennung in Börsenkursen erstrecken. Konventionelle Datenbanksysteme sind für die erforderliche kontinuierliche Anfrageverarbeitung, bei der die eintreffenden Daten möglichst direkt und ohne vollständige Zwischenspeicherung verarbeitet werden müssen, nicht ausgelegt. Das Ziel dieser Arbeit besteht darin, eine solide Grundlage zur adäquaten Verarbeitung kontinuierlicher Anfragen auf Datenströmen bereitzustellen. Um die Ressourcenanforderungen bei der Verarbeitung zu begrenzen, beziehen sich kontinuierliche Anfragen auf gleitende Fenster über den potentiell unbeschränkt großen Datenströmen. Dieses Vorgehen bietet den Vorteil, dass sich die Ergebnisse einer Anfrage stets auf die aktuellen Daten beziehen, die üblicherweise für die Anwendungen von höherer Relevanz sind. Damit Anwender einen einfachen Zugang zu den neu entwickelten Verfahren finden können, orientiert sich diese Arbeit an bewährter Datenbanktechnologie und adaptiert diese auf das Datenstrommodell. Eine deklarative, eng an den weit verbreiteten SQL-Standard angelehnte Anfragesprache erlaubt es Anwendern, komplexe Applikationslogik auf einfache Weise auszudrücken. Die zu Grunde liegende, aussagekräftige Anfragesemantik basiert auf temporalen Erweiterungen der relationalen Algebra. Darauf aufbauend ist es gelungen, die aus Datenbanken bekannten algebraischen Äquivalenzen auf kontinuierliche Anfragen über Datenströmen zu übertragen, wodurch eine hervorragende Grundlage zur Anfrageoptimierung geschaffen wurde. Für die datengetriebene Verarbeitung sorgt eine bislang einzigartige zeitintervallbasierte Datenstromalgebra umgesetzt durch effiziente Online-Algorithmen. Mittels einer Performanzanalyse gestützt durch experimentelle Studien wird belegt, dass der Zeitintervall-Ansatz für einen Großteil der Anfragen konkurrierenden Ansätzen deutlich überlegen ist. Darüber hinaus widmet sich die Arbeit architekturellen Gesichtspunkten einer adaptiven und skalierbaren Laufzeitumgebung, die in der Lage ist, sich einer variierenden Anfragelast sowie sich über die Zeit ändernden Datenstromcharakteristika anzupassen. Insbesondere werden neue Verfahren vorgestellt, um die Ressourcenallokation von Anfragen zu steuern und Anfragen zur Laufzeit zu optimieren. Die im Rahmen dieser Arbeit entwickelte Funktionalität bildet den Kern der Softwareinfrastruktur PIPES (Public Infrastructure for Processing and Exploring Streams), die sich bereits in diversen Anwendungsgebieten als ein mächtiges und nützliches Werkzeug zur Verarbeitung von Datenströmen bewährt hat.


* Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten