Selected publications at LSV

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 ε there exists an algorithm working in time O(n1+ε)). 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.

@inproceedings{SV-icdt17,
   address = {Venice, Italy},
   author = {Segoufin, Luc and Vigny, Alexandre},
   booktitle = {{P}roceedings of the 18th {I}nternational {C}onference on {D}atabase {T}heory ({ICDT}'17)},
   DOI = {10.4230/LIPIcs.ICDT.2017.20},
   editor = {Benedikt, Michael and Orsi, Georgio},
   month = mar,
   pages = {20:1--20:16},
   publisher = {Leibniz-Zentrum f{\"u}r Informatik},
   series = {Leibniz International Proceedings in Informatics},
   title = {Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion},
   url = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7060},
   volume = {68},
   year = {2017},
}

About LSV

Select by Year