Bandeau_logo_GDR_IFM_V_5.png
 
18-21 mars 2024 | Grenoble  (France)
Alpes.jpg
Efficient enumeration of query answers via circuits
Antoine Amarilli  1  
1 : Télécom Paris
Télécom Paris, Télécom-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.



  • Poster
Personnes connectées : 1 Vie privée
Chargement...