May 19 – 24 , 2019, Dagstuhl Seminar 19211

Enumeration in Data Management


Endre Boros (Rutgers University – Piscataway, US)
Benny Kimelfeld (Technion – Haifa, IL)
Reinhard Pichler (TU Wien, AT)
Nicole Schweikardt (HU Berlin, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 9, Issue 5 Dagstuhl Report
Aims & Scope
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]


In recent years, various concepts of enumeration have arisen in the fields of Databases, Computational Logic, and Algorithms, motivated by applications of data analysis and query evaluation. Common to all concepts is the desire to compute a stream of items with as small as possible waiting time between consecutive items, referred to as the "delay." Alongside each concept, there evolved algorithmic techniques for developing solvers, and proof techniques for establishing complexity bounds. In addition to the traditional guarantees of "polynomial delay" and "incremental polynomial," researchers have been pursuing stronger guarantees such as "constant delay" in the context of logical query evaluation, "dynamic complexity" of incremental maintenance, and "factorized databases." The growing interest and rapid evolution of the associated research brings up opportunities of significantly accelerating the computation of big results, by devising and adopting general-purpose methodologies.

In Dagstuhl Seminar 19211 on “Enumeration in Data Management,” key researchers from relevant communities have gathered to gain a better understanding the recent developments, lay out the important open problems, and join forces towards solutions thereof. These communities include researchers who explore enumeration problems in the fields of databases, logic, algorithms and computational complexity. We have had invited tutorials by
  • Luc Segoufin on Constant-delay enumeration
  • Takeaki Uno on Enumeration algorithms
  • Yann Strozecki on Enumeration complexity – defining tractability
  • Markus Kröll on Enumeration complexity – a complexity theory for hard enumeration problems
  • Endre Boros on Monotone generation problems.

We also had presentations by most of the other participants. Moreover, the participants have prepared in advance a list of open problems in a document that we shared and jointly maintained. We have discussed the open problems during designated times of the seminar.

The organizers are highly satisfied with the seminar. We have got a very high acceptance rate for our invitations. In fact, there were further researchers whom we would have liked to invite after the first invitation round but, unfortunately, no room was left. The participants were exceptionally involved and engaged. Some considerable progress has been made on the open problems prepared in advance, as will be reported in future publications that will acknowledge the seminar. The seminar has also initiated joint efforts to disseminate toolkits for data-centric enumeration problems, including algorithmic techniques, proof techniques, and important indicator problems. To this end, we have had sessions of working groups for the different types of toolkit components. In particular, we have initiated a Wikipedia page on enumeration algorithms:

This page will evolve to contain a thorough picture of the principles and techniques of enumeration problems.

Summary text license
  Creative Commons BY 3.0 Unported license
  Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt


  • Data Bases / Information Retrieval
  • Data Structures / Algorithms / Complexity
  • Verification / Logic


  • Enumeration
  • Polynomial delay
  • Constant delay
  • Dynamic complexity
  • Databases
  • Query evaluation


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.