2026-08-10T16:18:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7060 2024-03-06T10:39:26Z ddc:004 open_access

Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion Segoufin, Luc Vigny, Alexandre enumeration first-order queries local bounded expansion. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luc Segoufin and Alexandre Vigny 2017 Is Part Of LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2017.20 urn:nbn:de:0030-drops-70602 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode