2005/07/07 by Arnaud Durand, Durand, Arnaud, Étienne Grandjean +2 · 3 citations
Computer Science · #Advanced Database Systems and Queries #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.cs/0507020
18 pages, 1 figure
arxiv created 2005/07/07 · openalex publication_date 2005/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order queries over structures of bounded degree. Query evaluation is considered here as a dynamical process. We prove that any query on bounded degree structures is \constantdelaylin, i.e., can be computed by an algorithm that has two separate parts: it has a precomputation step of linear time in the size of the structure and then, it outputs all tuples one by one with a constant (i.e. depending on the size of the formula only) delay between each. Seen as a global process, this implies that queries on bounded structures can be evaluated in total time O(f(|ϕ|).(|\calS|+|ϕ(\calS)|)) and space O(f(|ϕ|).|\calS|) where \calS is the structure, ϕ is the formula, ϕ(\calS) is the result of the query and f is some function. Among other things, our results generalize a result of \citeSeese-96 on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that \citeSeese-96 and comparable results is that it does not rely on the Hanf's model-theoretic technic (see \citeHanf-65) and is completely effective.