Database Theory
From International Center for Computational Logic
Database Theory
Database theory deals with a broad range of topics related to data management and data management systems. Its theoretical foundations stem from logic, most notably relational algebra, and first-order logic. It focuses, among other subjects, on the computational complexity and the expressive power of query languages. Traditionally, database theory has studied the relational model - where databases and queries can be viewed as relational structures and query evaluation boils down to finding an appropriate homomorphism between two structures. However, in recent years, one can see a steady rise of other models. The most notable example is the graph model, where structures are restricted to binary signatures and queries are lifted to regular expressions.
Professors and Research Group Leaders
Scientific Staff
Former Members
Journal Articles
David Carral, Lukas Gerlach, Lucas Larroque, Michaël Thomazo
Restricted Chase Termination: You Want More than Fairness
Proc. ACM Manag. Data, 3(2 (PODS)), to appear
Details Download
Philipp Hanisch, Markus Krötzsch
Chase Termination Beyond Polynomial Time
Proc. ACM Manag. Data, 2(2):93, May 2024
Details Download
Bartosz Bednarczyk, Sebastian Rudolph
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC
Journal of Artificial Intelligence Research, 78:385–458, November 2023
Details Download
Proceedings Articles
Lukas Gerlach, David Carral
Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination (Technical Report)
In Pierre Marquis,Tran Cao Son,Gabriele Kern-Isberner, eds., Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023), volume 20 of Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 301–310, September 2023. International Joint Conferences on Artificial Intelligence Organization
Details Download
Lukas Gerlach, David Carral
General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase (Extended Abstract)
In Oliver Kutz, Carsten Lutz, Ana Ozaki, eds., Proceedings of the 36th International Workshop on Description Logics (DL 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning (KR 2023 and NMR 2023), volume 3515 of CEUR Workshop Proceedings, October 2023. CEUR-WS.org
Details Download
Lukas Gerlach, David Carral
General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase (Extended Technical Report)
In Brian Williams, Yiling Chen, Jennifer Neville, eds., Proceedings of the 37th AAAI Conference on Artificial Intelligence, volume 37 of Proceedings of the AAAI Conference on Artificial Intelligence, 6372-6379, June 2023. AAAI Press
Details Download
Ali Elhalawati, Markus Krötzsch, Stephan Mennicke
An Existential Rule Framework for Computing Why-Provenance On-Demand for Datalog
In Guido Governatori, Anni-Yasmin Turhan, eds., Proceedings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR 2022), volume 13752 of LNCS, 146--163, 2022. Springer
Details Download
Larry González, Alex Ivliev, Markus Krötzsch, Stephan Mennicke
Efficient Dependency Analysis for Rule-Based Ontologies
In Ulrike Sattler, Aidan Hogan, Maria Keet, Valentina Presutti, João Paulo A. Almeida, Hideaki Takeda, Pierre Monnin, Giuseppe Pirrò, Claudia d’Amato, eds., Proc. 21st International Semantic Web Conference (ISWC 2022), volume 13489 of LNCS, 267-283, October 2022. Springer
Details Download
Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values
In Dan Olteanu, Nils Vortmeier, eds., Proceedings of the 25th International Conference on Database Theory (ICDT 2022), volume 220 of LIPIcs, 13:1--13:20, March 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values (extended abstract)
In Mario Alviano, Andreas Pieris, eds., Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry, volume 3203 of CEUR Workshop Proceedings, 97--103, September 2022. CEUR-WS.org
Details Download
Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral, Sebastian Rudolph
A Journey to the Frontiers of Query Rewritability
In Leonid Libkin, Pablo Barceló, eds., Proceedings of the 41st Symposium on Principles of Database Systems (PODS'22), 359-367, June 2022. ACM
Details Download
Manuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian Rudolph
On Logics and Homomorphism Closure
Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), 1-13, 2021. IEEE
Details Download
Emanuel Kieroński, Sebastian Rudolph
Finite Model Theory of the Triguarded Fragment and Related Logics
In IEEE, eds., Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), 1-13, 2021
Details Download
Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1719--1725, July 2020. International Joint Conferences on Artificial Intelligence
Details Download
Talks and Miscellaneous
Lukas Gerlach
Chase Termination - Analytical Hierarchy, Disjunctions, Sufficient Conditions
Talk at Description Logics Seminar, April 2025
Details
