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. Einige erste Entwicklungen für allgemeine Zwecke sind:
- Stanford Stream Data Manager (STREAM) an der Stanford University
- Aurora an der Brandeis University, Brown University und dem MIT
- TelegraphCQ in Berkeley
- PipelineDB (wie TelegraphCQ ein Ableger PostgreSQL)
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
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 aktuelle Zustand ist relevant | Berücksichtigung der Eingangs-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
Während in herkömmlichen (relationale) Datenbanksystemen 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. 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 ( vom 13. Oktober 2007 im Internet Archive)
- QStream
- PIPES, RTM Analyzer
- StreamGlobe
- Odysseus
- PipelineDB
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 (PDF; 685 kB). (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, S. 5–14, Juni 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).