First-order queries on classes of structures with bounded expansion

Wojciech Kazana 1 Luc Segoufin 2
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
2 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded expansion, first-order sentences could be evaluated in time linear in the size of the database. We give a different proof of this result. Moreover, we show that answers to first-order queries can be enumerated with constant delay after a linear time preprocessing. We also show that counting the number of answers to a query can be done in time linear in the size of the database.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01706665
Contributor : Luc Segoufin <>
Submitted on : Monday, February 12, 2018 - 3:16:55 PM
Last modification on : Friday, April 19, 2019 - 4:54:52 PM
Long-term archiving on : Monday, May 7, 2018 - 3:28:20 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01706665, version 1

Citation

Wojciech Kazana, Luc Segoufin. First-order queries on classes of structures with bounded expansion. 2018. ⟨hal-01706665⟩

Share

Metrics

Record views

167

Files downloads

105