Computing the jth solution of a first-order query

Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne; Olive, Frédéric

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 147-164

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 I\times O$ whose instances $x\in I$ may admit of several solutions $R\left(x\right)=\{y\in O:(x,y)\in R\}$. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution $y\in R\left(x\right)$; enumerate without repetition each solution $y_j$ in some specific linear order $y_0<y_1<...<y_{n-1}$ where $R\left(x\right)=\{y_0,\cdots ,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 $\varphi \left(\overline{v}\right)$ and any structure $S$ of bounded degree: $\left(1\right)$ compute a random element of $\varphi \left(S\right)=\{\overline{a}:(S,\overline{a})\vDash \varphi \left(\overline{v}\right)\}$; $\left(2\right)$ compute the $j$th element of $\varphi \left(S\right)$ for some linear order of $\varphi \left(S\right)$; $\left(3\right)$ enumerate the elements of $\varphi \left(S\right)$ in lexicographical order. More precisely, we prove that, for any fixed formula $\varphi$, the above problem $\left(1\right)$ (resp. $\left(2\right)$, $\left(3\right)$) can be computed within average constant time (resp. within constant time, with constant delay) after a linear $\left(O\right(\left|S\right|\left)\right)$ precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

Classification : 68Q15, 68Q19
Keywords: complexity of enumeration, first-order queries, structures of bounded degree, linear time, constant time, constant delay

[1] G. Bagan, Mso queries on tree decomposable structures are computable with linear delay, in Proc. 15th Annual Conference of the EACSL (CSL'06). Lect. Notes Comput. Sci. 4207 (2006) 167-181. | MR

[2] G. Bagan, A. Durand and E. Grandjean, On acyclic conjunctive queries and constant delay enumeration, in Proc. 16th Annual Conference of the EACSL (CSL'07). Lect. Notes Comput. Sci. (2007) 208-222.

[3] B. Courcelle, Linear delay enumeration and monadic second-order logic. Discrete Appl. Math. (2007) (to appear).

[4] A. Durand and E. Grandjean, First-order queries on structures of bounded degree are computable with constant delay. ACM T. Comput. Logic (2007) 1-18. | MR

[5] A. Durand and F. Olive, First-order queries over one unary function, in Proc. 15th Annual Conference of the EACSL (CSL'06). Lect. Notes Comput. Sci. 4207 (2006) 334-348. | MR

[6] J. Flum, M. Frick and M. Grohe, Query evaluation via tree decompositions. J. ACM 49 (2002) 716-752. | MR

[7] M. Frick and M. Grohe, Deciding first-order properties of locally tree decomposable structures. J. ACM 48 (2001) 1184-1206. | MR

[8] G. Gottlob, N. Leone and F. Scarcello, The complexity of acyclic conjunctive queries. J. ACM 48 (2001) 431-498. | MR

[9] S. Grigorieff, Décidabilité et complexité des théories logiques. Collection Didactique INRIA 8 (1991) 7-97. | MR

[10] E. Grandjean and T. Schwentick, Machine-independent characterizations and complete problems for deterministic linear time. SIAM J. Comput. 32 (2002) 196-230. | Zbl | MR

[11] L. Libkin, Elements of finite model theory. EATCS Series, Springer (2004). | Zbl | MR

[12] S. Lindell, A normal form for first-order logic over doubly-linked data structures. Int. J. Found. Comput. Sci. (2006) (to appear). | MR

[13] R. Motwani and P. Raghavan, Randomized algorithms. Cambridge University Press (1995). | Zbl | MR

[14] C. Papadimitriou and M. Yannakakis, On the complexity of database queries. J. Comput. Syst. Sci. 58 (1999) 407-427. | Zbl | MR

[15] M.Y. Vardi, On the complexity of bounded-variable queries. Proc. Principles of Databases Systems (PODS'95), ACM Press (1995) 266-276.

[16] D. Seese, Linear time computable problems and first-order descriptions. Math. Structures Comput. Sci. 6 (1996) 505-526. | Zbl | MR

[17] M. Yannakakis, Algorithms for acyclic database schemes. Proc. Very Large Data Bases Conference (VLDB'81) (1981) 82-94.