Enumerating answers to first-order queries over databases of low degree

Arnaud Durand 1, 2 Nicole Schweikardt 3 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 : A class of relational databases has low degree if for all delta, all but finitely many databases in the class have degree at most n^delta, where n is the size of the database. Typical examples are databases of bounded degree or of degree bounded by log n. It is known that over a class of databases having low degree, first-order boolean queries can be checked in pseudo-linear time, i.e. in time bounded by n^(1+epsilon), for all epsilon. We generalise this result by considering query evaluation. We show that counting the number of answers to a query can be done in pseudo-linear time and that enumerating the answers to a query can be done with constant delay after a pseudo-linear time preprocessing.
Type de document :
Communication dans un congrès
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, Jun 2014, Snowbird, United States. pp.121--131, 2014, 〈10.1145/2594538.2594539〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01070898
Contributeur : Luc Segoufin <>
Soumis le : jeudi 2 octobre 2014 - 16:16:05
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Lien texte intégral

Identifiants

Collections

Citation

Arnaud Durand, Nicole Schweikardt, Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, Jun 2014, Snowbird, United States. pp.121--131, 2014, 〈10.1145/2594538.2594539〉. 〈hal-01070898〉

Partager

Métriques

Consultations de la notice

148