Computing the jth solution of a first-order query
We design algorithms of "optimal" data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R subset of I x O whose instances x is an element of I may admit of several solutions R(x) = {y is an element of O : (x, y) is an element of R}. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution y. R(x); enumerate without repetition each solution y(j) in some specific linear order y(0) < y(1) <... < y(n-1) where R(x) = {y(0),..., y(n-1)}; compute the solution y(j) of rank j in the linear order <. Algorithms of "minimal" data complexity are presented for the following problems: given any first-order formula phi((v) over bar) and any structure S of bounded degree: (1) compute a random element of phi(S) = {(a) over bar : (S, (a) over bar) satisfies phi((v) over bar)}; (2) compute the jth element of phi(S) for some linear order of phi(S); (3) enumerate the elements of phi(S) in lexicographical order. More precisely, we prove that, for any fixed formula phi, the above problem (1) (resp. (2), (3)) can be computed within average constant time (resp. within constant time, with constant delay) after a linear (O(vertical bar S vertical bar)) precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.
first-order queries structures of bounded degree constant time constant delay complexity of enumeration linear time