title: Join Queries over Data Streams and Their Optimization using Dynamic Metadata
title: Verbundoperationen über Datenströmen und deren Optimierung unter Verwendung dynamischer Metadaten
Creators: name: Cammert, Michael
Publisher: name: Philipps-Universität Marburg
Year: 2015
Subjects: Datenstrom
Optimization
Metadaten
Join
Informatik
Join-Operation
Optimierung
Datenstrommanagementsystem
Data Stream Management System
Data Stream
Metadata

description: Due to technological progress
      there has been an enormous increase of the number of
      continuous data streams from which valuable information has
      to be derived as fast as possible. Therefore, data stream
      management systems have emerged as a new technology to
      process continuous queries over data streams. In contrast to
      databases they primarily operate in memory and are optimized
      for processing continuous queries over data streams. During
      the development of this new kind of systems taking over the
      concept of using relational operator graphs from database
      theory has proven to be of value if executing them data
      driven instead of demand driven. Assigning validity intervals
      to the elements of the data streams solves the problem of
      processing potentially unbounded data streams while using
      bounded resources. The capabilities of such systems
      considerably depend on the availability of efficient and well
      defined techniques for combining information from different
      data streams. The objective of this thesis therefore is to
      transfer the proven concept of the relational join to the
      data driven data stream processing using validity intervals.
      For this purpose the semantic of the join operation for data
      streams is derived from the one of the extended relational
      algebra using the concept of snapshot-reducibility. Several
      join algorithms are presented and proven to comply with this
      semantic. The consequent usage of parameterization of the
      techniques with respect to the data structures used for
      storing the status allows supporting a large variety of
      different join predicates. Well known techniques of join
      processing using nested loops, hashing or indexing are
      adapted for data stream processing. Additionally, the
      Temporal Progressive-Merge-Join is introduced as an algorithm
      which allows to derive the join by using value based sorting
      of the data stream elements. Additionally, several
      optimizations are proposed, including the generalization of
      all presented algorithms for more than two input streams. To
      enable the automated choice and parameterization of the
      concrete implementations with respect to a forecast of their
      resource usage the techniques are embedded in a detailed cost
      model. Often, several kinds of metadata concerning the data
      streams to process are not available at registration time of
      the continuous queries and additionally may change during
      their long-lasting execution time. Therefore, it is important
      to be able to gather detailed information regarding the data
      streams and the system state at any time and to be able to
      adapt the processing strategy accordingly if necessary. A
      main part of the thesis therefore deals with the question how
      to provide dynamic metadata within a data stream management
      system. For that purpose a user-friendly framework is
      presented which allows to efficiently obtain consistent
      dynamic metadata. This process is investigated in several
      experiments and also used to evaluate the presented join
      techniques. Additionally, an approach allowing to restructure
      continuous queries at runtime is presented and it is shown
      that this approach is applicable for join processing.
description: Technischer Fortschritt und
      Vernetzung haben zu einem enormen Zuwachs an kontinuierlich
      anfallenden Datenströmen geführt, aus denen immer schneller
      wertvolle Informationen abgeleitet werden sollen. Zur
      Verarbeitung von kontinuierlichen Anfragen über Datenströme
      etablieren sich daher Datenstrommanagementsysteme, die
      hauptsächlich im Hauptspeicher operieren und im Gegensatz zu
      Datenbanksystemen auf die Verarbeitung kontinuierlicher
      Anfragen über Datenströmen zugeschnitten sind. Bei der
      Implementierung dieser neuen Systeme hat sich die Übernahme
      des Konzeptes der relationalen Operatorgraphen aus der Welt
      der Datenbanken bewährt, wobei diese allerdings statt
      bedarfsgesteuert nun kontinuierlich und datengetrieben
      ausgewertet werden. Durch Zuweisen von Gültigkeitsintervallen
      zu den Datenstromelementen kann dabei das Problem gelöst
      werden, mit endlichen Ressourcen potentiell unbegrenzte
      Datenströme zu verarbeiten. Die Mächtigkeit solcher Systeme
      hängt wesentlich von der Verfügbarkeit effizienter
      wohldefinierter Techniken zur Verknüpfung von Informationen
      aus verschiedenen Datenströmen ab. Ziel dieser Arbeit ist es
      daher, das für Datenbanken bewährte Konzept des relationalen
      Verbundes auf die datengetriebene Datenstromverarbeitung mit
      Gültigkeitsintervallen zu übertragen. Dazu wird die Semantik
      der Verbundoperation für Datenströme mittels der
      Schnappschuss-Reduzierung formal auf die des Verbundes in der
      erweiterten relationalen Algebra zurückgeführt. Es werden
      mehrere Verbundalgorithmen vorgestellt und gezeigt, dass
      diese die gewünschte Semantik haben. Durch eine konsequente
      Parametrisierung der Verfahren bezüglich der Datenstrukturen
      zur Statusverwaltung werden verschiedenste Typen von
      Verbundprädikaten effizient unterstützt. Bewährte Techniken
      der Verbundberechnung mittels verschachtelter Schleifen,
      Hashing und Indexierung werden dabei für die
      Datenstromverarbeitung adaptiert. Mit dem temporalen
      Progressive-Merge-Join wird zudem ein Verfahren vorgestellt,
      dass den Verbund über Datenströmen mittels einer
      wertbasierten Sortierung berechnet. Zudem werden für die
      Verfahren verschiedenste Optimierungen vorgeschlagen,
      darunter für alle Verfahren die Verallgemeinerung auf mehr
      als zwei Datenströme. Zur Ermöglichung der automatischen
      Auswahl und Parametrisierung der Implementierungen anhand
      ihres prognostizierten Ressourcenverbrauchs werden diese in
      ein detailliertes Kostenmodell eingebettet. Da bestimmte
      Metadaten bezüglich der zu verarbeitenden Datenströmen bei
      der Registrierung kontinuierlicher Anfragen oftmals nicht
      vorliegen und sich zudem während der langen Laufzeit der
      Anfragen ändern können, ist es wichtig, jederzeit
      detaillierte Informationen bezüglich der Datenströme und des
      Systemverhaltens erheben und gegebenenfalls durch Anpassungen
      an der Verarbeitungsstrategie darauf reagieren können. Ein
      wesentlicher Teil der Arbeit ist daher der Fragestellung
      gewidmet, wie in einem Datenstrommanagementsystem dynamische
      Metadaten erhoben werden können. Dazu wird ein
      benutzerfreundliches Rahmenwerk vorgestellt, das es
      ermöglicht, dynamische Metadaten konsistent und effizient zu
      erheben. In Experimenten wird die dynamische
      Metadatenerhebung untersucht und auch für die Evaluation der
      vorgestellten Verbundoperationen eingesetzt. Zudem wird eine
      Technik vorgestellt, mit der kontinuierliche Anfragen zur
      Laufzeit restrukturiert werden können, und deren
      Anwendbarkeit für die Verbundoptimierung aufgezeigt.