Dagstuhl-Seminar — Representation, Provenance, and Explanations in Database Theory and Logic

The goal of database theory is to formalize the theoretical underpinnings of databases and then analyze them with mathematical tools. One central question in the area is query evaluation, that is the computational problem of computing the answer to a query in a database. Of particular importance in this area is understanding the complexity of query evaluation, i.e., which resources, in particular, how much time and space, are necessary and sufficient to compute the answers to a given query. This Dagstuhl Seminar will focus on three key aspects of query evaluation: representation, provenance, and explanations. One common theme of these three directions is the use of circuits, which have a long history in complexity theory. In recent years, the theory of query processing has witnessed the use of different types of circuits, sometimes over Boolean inputs and operations, but also over more general structures, which often can be formalized as different semirings. We hope to see use of circuits in different representations of inputs for expressing and computing provenance, as well as for computing explanations using scores such as Shapley values. We hope to strengthen our understandings of these topics within database theory and logic.