License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2017.20
URN: urn:nbn:de:0030-drops-70602
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7060/
Go to the corresponding LIPIcs Volume Portal

Segoufin, Luc ; Vigny, Alexandre

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

pdf-format:
LIPIcs-ICDT-2017-20.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{segoufin_et_al:LIPIcs:2017:7060,
  author =	{Luc Segoufin and Alexandre Vigny},
  title =	{{Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Michael Benedikt and Giorgio Orsi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7060},
  URN =		{urn:nbn:de:0030-drops-70602},
  doi =		{10.4230/LIPIcs.ICDT.2017.20},
  annote =	{Keywords: enumeration, first-order queries, local bounded expansion.}
}

Keywords: enumeration, first-order queries, local bounded expansion.
Collection: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 17.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI