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

Luc Segoufin 1, 2 Alexandre Vigny 1
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, 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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01589303
Contributor : Luc Segoufin <>
Submitted on : Tuesday, October 16, 2018 - 9:52:02 AM
Last modification on : Thursday, February 7, 2019 - 4:57:38 PM
Long-term archiving on : Thursday, January 17, 2019 - 12:44:57 PM

Identifiers

  • 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. ⟨hal-01589303⟩

Share

Metrics

Record views

312

Files downloads

57