Enumerating with constant delay the answers to a query

Luc Segoufin 1
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We survey recent results about enumerating with constant delay the answers to a query over a database. More precisely, we focus on the case when enumeration can be achieved with a preprocessing running in time linear in the size of the database, followed by an enumeration process outputting the answers one by one with constant time between any consecutive outputs. We survey classes of databases and classes of queries for which this is possible. We also mention related problems such as computing the number of answers or sampling the set of answers.
Type de document :
Communication dans un congrès
ICDT 2013 - 16th International Conference on Database Theory, Mar 2013, Genes, Italy. ACM, ICDT '13 Proceedings of the 16th International Conference on Database Theory, pp.10-20, 2013, 〈10.1145/2448496.2448498〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00907085
Contributeur : Luc Segoufin <>
Soumis le : mercredi 20 novembre 2013 - 17:57:19
Dernière modification le : jeudi 5 juillet 2018 - 13:35:11
Document(s) archivé(s) le : vendredi 21 février 2014 - 04:34:38

Fichier

cdlin-survey.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Luc Segoufin. Enumerating with constant delay the answers to a query. ICDT 2013 - 16th International Conference on Database Theory, Mar 2013, Genes, Italy. ACM, ICDT '13 Proceedings of the 16th International Conference on Database Theory, pp.10-20, 2013, 〈10.1145/2448496.2448498〉. 〈hal-00907085〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

178