Wojtek Kazana ; Luc Segoufin - First-order queries on classes of structures with bounded expansion

lmcs:4281 - Logical Methods in Computer Science, February 25, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:25)2020
First-order queries on classes of structures with bounded expansionArticle

Authors: Wojtek Kazana ; Luc Segoufin

    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.


    Volume: Volume 16, Issue 1
    Published on: February 25, 2020
    Accepted on: January 7, 2020
    Submitted on: February 14, 2018
    Keywords: Computer Science - Databases

    Consultation statistics

    This page has been seen 1618 times.
    This article's PDF has been downloaded 246 times.