Theoretical foundations for efficient enumeration of query results
Final Report Abstract
Die effiziente Auswertung von Anfragen ist eine der zentralen Aufgaben von Datenbanksystemen. Die theoretischen Grundlagen der Anfrageauswertung beruhen auf einem engen Zusammenhang zwischen der Datenbanktheorie und der mathematischen Logik, aus deren Sicht eine relationale Datenbank einer endlichen relationalen Struktur und eine Anfrage einer Logik-Formel entspricht. Im Bereich der Logik in der Informatik und der Datenbanktheorie wurden seit 2007 eine Reihe von Ergebnissen erzielt, die sich mit der effizienten Aufzählung von Anfrageergebnissen beschäftigen. Das Ziel in diesem Szenario ist, bei Eingabe einer Struktur (d.h. Datenbank) und einer Logik-Formel (d.h. Anfrage) nach einer möglichst kurzen Vorverarbeitungsphase die Anfrageergebnisse nach und nach zu erzeugen und dabei Garantien über die maximal benötigte Wartezeit zwischen der Ausgabe zweier Ergebnistupel einzuhalten. Ziel des Projekts war die Erforschung der theoretischen Grundlagen der effizienten Aufzählung von Anfrageergebnissen. Dabei haben wir uns auch der Frage gewidmet, inwieweit Datenbank-Aktualisierungen bei der effizienten Aufzählung der Anfrageergebnisse unterstützt werden können. Die Anfragesprachen, die im Fokus des Projekts standen, sind geeignete Fragmente der Logik erster Stufe oder deren Erweiterung um bestimmte Zählmechanismen. In einigen Szenarien haben wir das Augenmerk jeweils auf geeignete Klassen von Datenbanken eingeschränkt, u.a. Klassen beschränkten Grades oder so genannte nirgends-dichte Klassen (engl.: nowhere dense classes). Wir wollten jeweils die "Grenzen der Machbarkeit" identifizieren, also bei gegebener Klasse von Strukturen möglichst gro#e Logik-Fragmente und bei gegebener Logik möglichst große Strukturklassen finden, für die eine effiziente Aufzählung der Anfrageergebnisse möglich ist. Um untere Schranken nachzuweisen, haben wir u.a. Methoden des noch jungen Gebiets der "feinkörnigen Komplexitätstheorie"genutzt.
Publications
- Answering conjunctive queries under updates. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303–318. ACM, 2017
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt
(See online at https://doi.org/10.1145/3034786.3034789) - First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12. IEEE Computer Society, 2017
Dietrich Kuske and Nicole Schweikardt
(See online at https://doi.org/10.1109/LICS.2017.8005133) - Answering FO+MOD queries under updates on bounded degree databases. ACM Trans. Database Syst., 43(2):7:1–7:32, 2018. ACM TODS 2018 (Special Issue for selected papers from ICDT 2017).
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt
(See online at https://doi.org/10.1145/3232056) - Answering UCQs under updates and in the presence of integrity constraints. In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt
- Enumeration for FO queries over nowhere dense graphs. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 151–163. ACM, 2018
Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny
(See online at https://doi.org/10.1145/3196959.3196971) - First-order query evaluation with cardinality conditions. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 253–266. ACM, 2018
Martin Grohe and Nicole Schweikardt
(See online at https://doi.org/10.1145/3196959.3196970) - Gaifman normal forms for counting extensions of first-order logic. In Ioannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 133:1–133:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018
Dietrich Kuske and Nicole Schweikardt
(See online at https://doi.org/10.4230/LIPIcs.ICALP.2018.133) - Constant delay enumeration with fptpreprocessing for conjunctive queries of bounded submodular width. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 58:1–58:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019
Christoph Berkholz and Nicole Schweikardt
(See online at https://doi.org/10.4230/LIPIcs.MFCS.2019.58) - Local normal forms and their use in algorithmic meta theorems (invited talk). In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, pages 1–3. IEEE, 2019
Nicole Schweikardt
(See online at https://doi.ieeecomputersociety.org/10.1109/LICS.2019.8785748) - Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4–33, 2020
Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt
(See online at https://doi.org/10.1145/3385634.3385636)
