Open Problems in Database Theory

Submitted by Michael Benedikt on Mon, 04/10/2017 - 23:29

ICDT 17 witnessed the first special session on open problems.  The session had a number of goals:

  1.  We want to introduce people to the kinds of problems the community has been looking at, in a way that is different from either a typical research presentation or a keynote.
  2.  We want to give an idea of what are some of the most challenging and significant problems that have been open for more than a few years. Even for many of us who are regular attendees at database theory conferences, the status of these problems may not be familiar.

The idea is to have a repository of problems available both to insiders and outsiders to database theory, and in particular to look for connections to other areas of theory.

In one session we could cover only a small subset of the problem domains. Pablo Barcelo covered problems related to semantic query optimization, focusing on transforming a query into an equivalent acyclic one. Benny Kimmelfeld covered problems related to probabilistic query evaluation, and Paris Koutris discussed problems related to parallel query evaluation. Benny and Paris jointly covered problems related to evaluation of queries on "dirty databases", using the approach of consistent query answering and data repair. Carsten Lutz discussed problems related to ontology-based query access, while Jurek Marcinkowski explained the "BD/FC conjecture", which posits a relationship between two techniques for answering queries in the presence of constraints. Thomas Schwentick closed the session with an overview of problems related to maintaining queries under updates.