Wojciech Kazana ; Luc Segoufin - First-order query evaluation on structures of bounded degree

lmcs:903 - Logical Methods in Computer Science, June 29, 2011, Volume 7, Issue 2 - https://doi.org/10.2168/LMCS-7(2:20)2011
First-order query evaluation on structures of bounded degreeArticle

Authors: Wojciech Kazana ; Luc Segoufin

    We consider the enumeration problem of first-order queries over structures of bounded degree. It was shown that this problem is in the Constant-Delaylin class. An enumeration problem belongs to Constant-Delaylin if for an input of size n it can be solved by: - an O(n) precomputation phase building an index structure, - followed by a phase enumerating the answers with no repetition and a constant delay between two consecutive outputs. In this article we give a different proof of this result based on Gaifman's locality theorem for first-order logic. Moreover, the constants we obtain yield a total evaluation time that is triply exponential in the size of the input formula, matching the complexity of the best known evaluation algorithms.


    Volume: Volume 7, Issue 2
    Published on: June 29, 2011
    Imported on: November 19, 2010
    Keywords: Computer Science - Logic in Computer Science,F.4.1, F.1.3
    Funding:
      Source : OpenAIRE Graph
    • Foundations of XML - Safe Processing of Dynamic Data over the Internet; Funder: European Commission; Code: 233599
    • Foundations of Web Data Management; Funder: European Commission; Code: 226513

    18 Documents citing this article

    Consultation statistics

    This page has been seen 1471 times.
    This article's PDF has been downloaded 362 times.