First-order queries on structures of bounded degree are computable with constant delay
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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 \cite{Seese-96} on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that \cite{Seese-96} and comparable results is that it does not rely on the Hanf's model-theoretic technic (see \cite{Hanf-65}) and is completely effective.
18 pages, 1 figure
18 pages, 1 figure