Theoretische Grundlagen der effizienten Anfrageauswertung über dynamischen Datensätzen

• Antragstellerin: Professorin Dr. Nicole Schweikardt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 431183758

Die effiziente Anfragebearbeitung, d.h. das Berechnen der Antwort auf eine Datenbankanfrage, ist ein Kernproblem der Datenbanktheorie, zu dem im Laufe der Zeit immer wieder neue Resultate erzielt und neue Forschungsrichtungen eingeschlagen wurden, z.B. effiziente Algorithmen zur Aggregatberechnung, zum Aufzählen von Ergebnistupeln und zum Berechnen von Provenance-Informationen. Während im Datenbanksystembereich Datenbanken zumeist als dynamische Objekte betrachtet werden, die sich mit der Zeit ändern, hat sich die Erforschung der theoretischen Grundlagen weitgehend auf statische Datenbanken fokussiert. Für den Fall, dass sich die Datenbank auch nur leicht ändert, liefern die theoretischen Laufzeitgarantien oft keine bessere Strategie, als das Anfrageergebnis nach erfolgter Datenbank-Aktualisierung komplett neu zu berechnen und dabei alle vorher bereits gesammelten Informationen zu verlieren. Dies steht in starkem Kontrast zu realen Datenbanksystemen, die Indexstrukturen vorhalten, um die Anfragebearbeitung zu beschleunigen. In der Datenbanktheorie hat die systematische Untersuchung der Berechnungskomplexität der Anfragebearbeitung auf dynamischen Datensätzen erst kürzlich begonnen. Einige Forschungsarbeiten, darunter Arbeiten der Kooperationspartner dieses Projekts, haben das Problem für kleine Aktualisierungsoperationen in relativ einfachen Kontexten untersucht, z.B. bzgl. konjunktiven Anfragen und Anfragen an Baum-ähnliche Daten.In diesem Projekt werden wir systematisch untersuchen, in welchem Maße die komplette Neuberechnung durch Nutzung von effizient aktualisierbaren Datenstukturen vermieden werden kann. Wir sind am Nachweis von Laufzeit-Garantien für Algorithmen zur dynamischen Anfragebearbeitung interessiert und wir wollen prinzipielle untere Schranken beweisen, d.h. Mindestanforderungen an die Ressourcen, die von jedem Algorithmus benötigt werden, der das Problem löst. Wir werden diese Fragen für verschiedene Arten von Anfragen betrachten, u.a. Boolesche Anfragen, Aggregatanfragen und Anfragen, die das Aufzählen aller Ergebnistupel erfordern.Das generelle Ziel von EQUUS ist, die Untersuchung dynamischer Aspekte der Anfragebearbeitung als eine Standard-Fragestellung der Datenbanktheorie zu etablieren, die für jede Anfragesprache untersucht wird. EQUUS ist in 3 Hauptaufgaben gegliedert, die verschiedene Aspekte des Themas untersuchen - Aufgabe 1: Anfragen an Graph-Datenbanken, Aufgabe 2: Komplexe Änderungsoperationen, Aufgabe 3: Untere Schranken. Hinzu kommt eine administrative Aufgabe 4, die Organisatorischem und der Publikmachung der Resultate gewidmet ist.EQUUS ist ein Deutsch-Französisches Projekt mit deutschen Projektpartnern an der HU Berlin und der Univ. Bayreuth und französichen Projektpartnern in Paris (Inria Paris; Télécom ParisTech; IMJ, Université Paris-Diderot) und der Region Hauts-de-France (CRIL, Lens; CRIStAL, Lille); es wird gemeinsam von Stefan Mengel (CNRS, Frankreich) and Nicole Schweikardt (HU Berlin) koordiniert.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Frankreich
• Mitverantwortliche: Professor Dr. Christoph Berkholz; Professor Dr. Wim Martens; Dr. Matthias Niewerth
• Kooperationspartner: Professor Dr. Antoine Amarilli; Dr. Pierre Bourhis; Professor Dr. Arnaud Durand; Dr. Stefan Mengel; Dr. Luc Segoufin