Servicenavigation

Project Details

Back

Projekt Print View

Grundlagen der Verarbeitung von großen Datenmengen und Datenströmen

Subject Area Security and Dependability, Operating-, Communication- and Distributed Systems
Term from 2005 to 2014
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 5448445
 
Final Report Year 2016

Final Report Abstract

Die effiziente Verarbeitung extrem großer Datenmengen wird — nicht zuletzt weil Sekundär-und Tertiär-Speicherplatz in den letzten Jahren zu sehr preiswerten Ressourcen geworden sind — zu einer immer wichtigeren Herausforderung für die Informatik. Solch große Datenmengen treten in vielen Anwendungsbereichen auf, etwa als Sammlung wissenschaftlicher Ergebnisse (z.B. Medizindatenbanken wie Medline und Swiss-Prot), in Form von Sensordaten oder als Börsenticker. Häufig liegen die Daten dabei nicht in einer klassischen, effizient bearbeitbaren Datenbank, sondern nur in semistrukturierter Form vor, z.B. als XML-Dokument. Solche semistrukturierten Daten können auf natürliche Weise durch Bäume repräsentiert werden. Wegen der großen Datenmenge kann in der Regel nicht die Baumrepräsentation der gesamten Daten im Hauptspeicher eines Rechners vorgehalten werden, sondern nur ein gewisser Ausschnitt. In vielen Anwendungen sind die Daten sogar nur nach und nach, als Datenstrom zugänglich, etwa beim Börsenticker, der mit der Zeit immer wieder neue Informationen sendet. Zur effizienten Verarbeitung solcher Daten sind daher neue, über die aus der klassischen Datenbankverarbeitung bekannten hinausgehende Techniken erforderlich. Ziel dieses Projekts war die Erforschung der theoretischen Grundlagen der Verarbeitung solch großer, semistrukturierter Datenmengen hinsichtlich Anfrageoptimierung, Eigenschaften von Anfragesprachen und prinzipieller Grenzen der Datenstromverarbeitung. Besonders berücksichtigt wurden dabei Szenarien, bei denen es nicht möglich ist, eine für die effiziente Bearbeitung geeignete Repräsentation der gesamten Daten im Hauptspeicher vorzuhalten. Wichtige Maße für die Komplexität von Anfragen sind daher die Größe des Speicherplatzes sowie der durch Speicherzugriffe verursachte Aufwand, der zur Bearbeitung einer Anfrage nötig ist. Im Rahmen des Projekts habe ich in einer Reihe von Arbeiten gemeinsam mit Koautoren verschiedene Maschinenmodelle entwickelt, die den durch Zugriffe auf externe Speichermedien verursachten Aufwand klassifizieren, darunter das Modell der Read/Write Streams und das Modell der Finite Cursor Machines. Dabei haben wir neue Techniken zum Nachweis unterer Schranken entwickelt, die mächtig genug sind, um die durch diese Berechnungsmodelle definierten deterministischen, randomisierten und nichtdeterministischen Komplexitaätsklassen voneinander zu trennen. In weiteren Arbeiten haben wir uns mit dem Austausch relationaler Daten beschäftigt und die theoretischen Grundlagen des Datenaustauschs im Rahmen der Closed World Assumption gelegt. Eine Reihe weiterer Arbeiten ist der Ausdurcksstärke und der statischen Analyse von Anfragen gewidmet, die sich an semistrukturierte Daten oder an Graphdatenbanken richten. Die beiden jüngsten im Rahmen des Projekts entstandenen Arbeiten beschäftigen sich mit der strombasierten Aufzählung von Ergebnistupeln einer Anfrage sowie mit der strombasierten Auswertung von Anfragen in verteilten Rechenmodellen.

Publications

 
 

Additional Information

© 2024 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung