27 mai 2024
Antoine Amarilli (LTCI, Telecom-Paris)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.