Data Stream Management System

Ein Data Stream Management System (DSMS) ist ein Datenbanksystem zur Verwaltung von kontinuierlichen Datenströmen. Es ist vergleichbar mit einem Datenbankverwaltungssystem (DBMS), welches für Datenbanken eingesetzt wird. Im Gegensatz zu einem DBMS muss ein DSMS zusätzlich zu den Relationen mit Datenströmen umgehen und auf diesen kontinuierliche Anfragen ausführen können. Zur Formulierung von Anfragen können spezielle Anfragesprachen wie beispielsweise die Continuous Query Language (CQL) eingesetzt werden.

Data Stream Management Systeme sind in der Datenbankwelt noch relativ neu. Zurzeit (2004) werden mindestens drei große Systeme für allgemeine Zwecke entwickelt:

• Stanford Stream Data Manager (STREAM) an der Stanford University
• Aurora an der Brandeis University, Brown University und dem MIT
• TelegraphCQ in Berkeley

Daneben gibt es eine wachsende Zahl kleinerer Projekte mit verschiedenen Schwerpunkten. Im Gegensatz zu nicht-strömenden Daten, die fast ausschließlich mit universellen Datenbankverwaltungssystemen verwaltet werden, werden für strömende Daten allerdings noch in der Regel Systeme verwendet, die speziell für den Anwendungsfall entwickelt oder angepasst werden.

Unterschiede zu DBMS

Datenverarbeitung in einem DBMS

Datenverarbeitung in einem DSMS

Während in herkömmlichen Datenbanksystemen bei der Datenauswertung die Datenbasis relativ gleich bleibt und darauf verschiedene Anfragen an das System gestellt werden können, bleiben in einem Data Stream Management System die Anfragen über einen gewissen Zeitraum gleich und es kommen laufend neue Daten hinzu. Diese beiden komplementären Prinzipien sind beispielsweise auch beim Information Retrieval als Ad-hoc-Anfragen (neue Anfragen an gleiche Dokumente) und Routing-Aufgaben (neue Dokumente zu vorgegebenen Anfragen) bekannt (siehe [1]).

Die folgende Tabelle gibt einen Vergleich verschiedener Merkmale eines Database Management Systems (DBMS) und eines Data Stream Management Systems (DSMS):

Database Management System (DBMS)	Data Stream Management System (DSMS)
Persistente Daten (Relationen)	Flüchtige Datenströme
Random Access	Sequentieller Zugriff
Einmalige Anfragen	Kontinuierliche Anfragen
(Theoretisch) unbeschränkter Sekundärspeicher	Beschränkter Hauptspeicher
Nur der aktueller Zustand ist relevant	Berücksichtigung der Eingabe-Reihenfolge
relativ niedrige Update-Rate	möglicherweise extrem hohe Update-Rate
keine oder geringe Zeitanforderungen	Echtzeitanforderungen
Exakte Daten werden angenommen	Veraltete / Ungenaue Daten
Planbare Anfragebearbeitung	Variable Datenankunft und -merkmale

Verarbeitung von Strömen und Relationen

Aufbau eines DSMS

Während in herkömmlichen (relationale) Datenbankenbanksysteme die Daten in Tabellen (Relationen) verwaltet werden, kommen in einem DSMS als grundlegende Datenobjekte Datenströme hinzu. Datenströme können als kontinuierliche Folge von Zeit-Wertepaaren aufgefasst werden. Da Datenströme prinzipiell unendlich sind, müssen sie zur Verarbeitung zwischenzeitlich in Relationen umgewandelt werden. Umgekehrt können Relationen wieder in Datenströme umgewandelt werden (siehe Abbildung). Die Verarbeitung von reinen Relationen kann mit herkömmlichen Methoden stattfinden. Die Umwandlung von Strömen in andere Ströme findet über den Umweg von Relationen statt. Die auf SQL aufbauende Continuous Query Language bietet dazu verschiedene Operatoren an.

Formulierung, Planung und Optimierung von Anfragen

Ebenso wie in herkömmlichen Datenbanksystemen werden Anfragen in einer deklarativen Sprache formuliert und zur Ausführung mit Hilfe eines Anfrageplans optimiert. Da möglichst viele Anfragen gleichzeitig abgearbeitet werden sollen, werden die gespeicherten Anfragen möglichst geschickt kombiniert, so dass Teilanfragen mehrfach verwendet werden können.

Die Komponenten eines Plans sind Operatoren, Warteschlangen und Zustände. Die Operatoren entsprechen den aus herkömmlichen Datenbanken bekannten Operatoren wie beispielsweise die Filterung, Sortierung, Join, mathematische Operatoren etc. sowie die Ein- und Ausgabe von Datenströmen. Die einzelnen Operatoren eines Planes sind durch Warteschlangen verbunden, in die Datenobjekte sequentiell hineingeschrieben und in der gleichen Reihenfolge vom nächsten Operator ausgelesen werden. Als Zwischenergebnisse gibt es Zustände wie beispielsweise der Inhalt eines festgelegten Fensters.

Beispiel

Ein Nachrichtenportal möchte auf seiner Seite aktuelle Nachrichten zu den zurzeit am meisten besprochenen Themen sowie die Nachrichtenmenge eines Tages anzeigen. In einem Datenstrom kommen Nachrichten und in einem anderen Datenstrom als „Zeitgeist“ die aktuell wichtigen Themen an. Jede Nachricht ist einem Thema zugeordnet werden. Konkret sollen die Nachrichtentitel der letzten Stunde zu den 10 letzten Themen sowie die Anzahl aller dazu passenden Nachrichten innerhalb der letzten 24 Stunden angezeigt werden. In CQL formuliert sind dies zwei Anfragen:

Q1: SELECT Titel FROM Nachrichten N [Range 1 HOUR], Zeitgeist Z [RANGE 10] WHERE N.Thema = Z.Thema

Q2: SELECT COUNT(*) FROM Nachrichten N [RANGE 1 DAY], Zeitgeist Z [RANGE 10] WHERE N.Thema = Z.Thema

Das DSMS erstellt nun aus diesen Anfragen einen möglichst effizienten Plan, der beispielsweise wie in nebenstehender Abbildung angegeben aussehen könnte. Von den Nachrichten werden zunächst die Titel und Themen projiziert und kommen in eine Warteschlange. Die Themen kommen zunächst in eine Warteschlange und von dort in ein Fenster der Länge 10. Nachrichten und Fenster werden durch einen JOIN-Operator verknüpft und gelangen in ein Fenster das alle Nachrichten eines Tages enthält. Aus diesem Fenster wird über den COUNT-Operator das Ergebnis der Anfrage Q2 ermittelt. Für die Anfrage Q1 schließt sich an das größere Fenster ein kleineres Fenster mit dem Umfang einer Stunde an.

Weblinks

• STREAM, Stream Team HomePage
• AURORA, StreamBase Systems, Inc.
• TelegraphCQ
• NigaraST (Archivversion vom 13. Oktober 2007)
• QStream
• PIPES, RTM Analyzer
• StreamGlobe
• Odysseus

Literatur

• Brian Babcock, Shivnath Babu, Mayur Data, Rajeev Motwani, Jennifer Widom. Models and Issues in Data Stream Systems. In: Proceedings of 21st ACM Symposium on Principles of Database Systems (PODS 2002)
• Don Carney, Ugur Centintemel, Mitch Cherniack, et.al.: Monitoring Streams - A New Class of Data Management Applications. (VLDB 2002)
• Rajeev Motwani, Jennifer Widom, Arvind Arasu, Brian Babcock, Shivnath Babu, Mayur Datar, Gurmeet Manku, Chris Olston, Justin Rosenstein und Rohit Varma: Query Processing, Resource Management, and Approximation in a Data Stream Management System. Stanford, 2002 (CIDR 2003)
• Golab L., Ozsu M.T. Issues in data stream management, ACM SIGMOD Record Volume 32, Issue 2, pp.5-14, June 2003.
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Bernhard Seeger: Anfrageverarbeitung auf Datenströmen. Datenbank-Spektrum 11: 5-13, (2004).
• Jürgen Krämer: Continuous Queries over Data Streams - Semantics and Implementation. Dissertation, Philipps-Universität Marburg, (2007).
• Jürgen Krämer, Bernhard Seeger: Semantics and implementation of continuous sliding window queries over data streams. (ACM TODS 2009).