Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin - Enumerating Answers to First-Order Queries over Databases of Low Degree

lmcs:6858 - Logical Methods in Computer Science, May 10, 2022, Volume 18, Issue 2 - https://doi.org/10.46298/lmcs-18(2:7)2022
Enumerating Answers to First-Order Queries over Databases of Low DegreeArticle

Authors: Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin

    A class of relational databases has low degree if for all δ>0, all but finitely many databases in the class have degree at most nδ, where n is the size of the database. Typical examples are databases of bounded degree or of degree bounded by logn. It is known that over a class of databases having low degree, first-order boolean queries can be checked in pseudo-linear time, i.e.\ for all ϵ>0 in time bounded by n1+ϵ. We generalize this result by considering query evaluation. We show that counting the number of answers to a query can be done in pseudo-linear time and that after a pseudo-linear time preprocessing we can test in constant time whether a given tuple is a solution to a query or enumerate the answers to a query with constant delay.


    Volume: Volume 18, Issue 2
    Published on: May 10, 2022
    Accepted on: March 3, 2022
    Submitted on: October 26, 2020
    Keywords: Computer Science - Databases,Computer Science - Logic in Computer Science

    11 Documents citing this article

    Consultation statistics

    This page has been seen 2448 times.
    This article's PDF has been downloaded 773 times.