Database Theory

From International Center for Computational Logic
Toggle side column

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.

Proceedings Articles

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
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
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