Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion

Luc Segoufin 1, 2 Alexandre Vigny 1
1 VALDA - Value from Data
Inria de Paris
2 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 consider the evaluation of first-order queries over classes of databases with local bounded expansion. This class was introduced by Nesetril and Ossona de Mendez and generalizes many well known classes of databases, such as bounded degree, bounded tree width or bounded expansion. It is known that over classes of databases with local bounded expansion, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all epsilon there exists an algorithm working in time O(n^{1+epsilon)). Here, we investigate other scenarios, where queries are not sentences. We show that first-order queries can be enumerated with constant delay after a pseudo-linear preprocessing over any class of databases having locally bounded expansion. We also show that, in this context, counting the number of solutions can be done in pseudo-linear time.
Type de document :
Communication dans un congrès
ICDT, Mar 2017, Venise, Italy. ICDT, 2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01589303
Contributeur : Luc Segoufin <>
Soumis le : lundi 18 septembre 2017 - 14:20:41
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Identifiants

  • HAL Id : hal-01589303, version 1

Citation

Luc Segoufin, Alexandre Vigny. Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion. ICDT, Mar 2017, Venise, Italy. ICDT, 2017. 〈hal-01589303〉

Partager

Métriques

Consultations de la notice

135