Grundlagen der Verarbeitung von großen Datenmengen und Datenströmen
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
- “Approximation Schemes for First-Order Definable Optimisation Problems”. In: 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings. 2006, S. 411–420
Anuj Dawar, Martin Grohe, Stephan Kreutzer und Nicole Schweikardt
(See online at https://dx.doi.org/10.1109/LICS.2006.13) - “Machine models and lower bounds for query processing”. In: Proc. 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’07). 2007, S. 41–52
Nicole Schweikardt
(See online at https://dx.doi.org/10.1145/1265530.1265537) - “Model Theory Makes Formulas Large”. In: Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings. 2007, S. 913– 924
Anuj Dawar, Martin Grohe, Stephan Kreutzer und Nicole Schweikardt
(See online at https://dx.doi.org/10.1007/978-3-540-73420-8_78) - “Tight lower bounds for query processing on streaming and external memory data”. In: Theor. Comput. Sci. 380.1-2 (2007)
Martin Grohe, Christoph Koch und Nicole Schweikardt
(See online at https://dx.doi.org/10.1016/j.tcs.2007.02.062) - “Logic and Data Exchange: Which Solutions Are “Good” Solutions?” In: Logic and the Foundations of Game and Decision Theory - LOFT 8, 8th International Conference, Amsterdam, The Netherlands, July 3-5, 2008, Revised Selected Papers. 2008, S. 61–85
André Hernich und Nicole Schweikardt
(See online at https://dx.doi.org/10.1007/978-3-642-15164-4_4) - “Database Query Processing Using Finite Cursor Machines”. In: Theory Comput. Syst. 44 (2009), S. 533–560
Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz und Jan Van den Bussche
(See online at https://dx.doi.org/10.1007/s00224-008-9137-7) - “Database Theory: Query Languages”. In: Algorithms and Theory of Computation Handbook. Hrsg. von Mikhail J. Atallah und Marina Blanton. 2nd edition. Bd. 2: Special Topics and Techniques. CRC Press, Nov. 2009. Kap. 19
Nicole Schweikardt, Thomas Schwentick und Luc Segoufin
- “Lower Bounds for Multi-Pass Processing of Multiple Data Streams”. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings. 2009, S. 51–61
Nicole Schweikardt
(See online at https://dx.doi.org/10.4230/LIPIcs.STACS.2009.1857) - “Lower bounds for processing data with few random accesses to external memory”. In: J. ACM 56.3 (2009)
Martin Grohe, André Hernich und Nicole Schweikardt
(See online at https://dx.doi.org/10.1145/1516512.1516514) - “Machine models for query processing”. In: SIGMOD Record 38.2 (2009), S. 18–28
Nicole Schweikardt
(See online at https://doi.acm.org/10.1145/1815918.1815922) - “One-Pass Algorithm”. In: Encyclopedia of Database Systems. 2009, S. 1948–1949
Nicole Schweikardt
(See online at https://dx.doi.org/10.1007/978-0-387-39940-9_253) - Data Exchange, Integration, and Streams. Bd. 5. Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 2013. isbn: 978-3-939897-61-3
Phokion G. Kolaitis, Maurizio Lenzerini und Nicole Schweikardt, Hrsg.
- “Closed world data exchange”. In: ACM Trans. Database Syst. 36.2 (2011), S. 14
André Hernich, Leonid Libkin und Nicole Schweikardt
(See online at https://doi.acm.org/10.1145/1966385.1966392) - “Locality from Circuit Lower Bounds”. In: SIAM J. Comput. 41.6 (2012), S. 1481–1523
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt und Luc Segoufin
(See online at https://doi.org/10.1137/110856873) - “Regular tree languages, cardinality predicates, and addition-invariant FO”. In: 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. 2012, S. 489–500
Frederik Harwath und Nicole Schweikardt
(See online at https://dx.doi.org/10.4230/LIPIcs.STACS.2012.489) - “Expressiveness and static analysis of extended conjunctive regular path queries”. In: J. Comput. Syst. Sci. 79.6 (2013), S. 892–909
Dominik D. Freydenberger und Nicole Schweikardt
(See online at https://dx.doi.org/10.1016/j.jcss.2013.01.008) - Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014
Nicole Schweikardt, Vassilis Christophides und Vincent Leroy, Hrsg.
- “Enumerating Answers to Firstorder Queries over Databases of Low Degree”. In: Proc. 33rd ACM SIGMOD-SIGACT- SIGART Symposium on Principles of Database Systems (PODS’14). 2014, S. 121–131
Arnaud Durand, Nicole Schweikardt und Luc Segoufin
(See online at https://dx.doi.org/10.1145/2594538.2594539) - “Monadic Datalog Containment on Trees”. In: Proc. 8th Alberto Mendelzon Workshop on Foundations of Data Management. 2014
André Frochaux, Martin Grohe und Nicole Schweikardt
- “Distributed Streaming with Finite Memory”. In: Proc. 18th International Conference on Database Theory (ICDT’15). 2015, S. 324–341
Frank Neven, Nicole Schweikardt, Frédéric Servais und Tony Tan
(See online at https://dx.doi.org/10.4230/LIPIcs.ICDT.2015.324)
