This talk is about *query evaluation*, where we want to efficiently
compute the answers to a query on a database. Since the number of results can be
very large, we want to design an efficient *enumeration algorithm*: such an
algorithm first preprocesses the data and then efficiently enumerates all
answers, with a small delay between any two consecutive answers. This talk will
review results on enumerating query results in multiple settings: from
conjunctive queries on relational databases to monadic second-order queries over
trees. One common theme to such algorithms is the use of circuit classes from
knowledge compilation to serve as a compressed representations of the answers to
enumerate. We will also present extensions, e.g., how to enumerate results in a
specific order, or how to maintain enumeration structures under updates to the
underlying data.
- Poster