Computing the jth solution of a first-order query
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 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×O$ whose instances $x\in I$ may admit of several solutions $R\left(x\right)=\left\{y\in O:\left(x,y\right)\in R\right\}$. 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)=\left\{{y}_{0},\cdots ,{y}_{n-1}\right\}$; 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)=\left\{\overline{a}:\left(S,\overline{a}\right)\vDash \varphi \left(\overline{v}\right)\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\left(|S|\right)\right)$ precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

DOI: 10.1051/ita:2007046
Classification: 68Q15,  68Q19
Keywords: complexity of enumeration, first-order queries, structures of bounded degree, linear time, constant time, constant delay
Bagan, Guillaume ; Durand, Arnaud ; Grandjean, Etienne ; Olive, Frédéric 1

1 LIF, Université Aix-Marseille 1, CNRS, 39 rue Joliot Curie, 13453 Marseille Cedex 13, France;
@article{ITA_2008__42_1_147_0,
author = {Bagan, Guillaume and Durand, Arnaud and Grandjean, Etienne and Olive, Fr\'ed\'eric},
title = {Computing the jth solution of a first-order query},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {147--164},
publisher = {EDP-Sciences},
volume = {42},
number = {1},
year = {2008},
doi = {10.1051/ita:2007046},
zbl = {1149.68028},
mrnumber = {2382549},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007046/}
}
TY  - JOUR
AU  - Bagan, Guillaume
AU  - Durand, Arnaud
AU  - Grandjean, Etienne
AU  - Olive, Frédéric
TI  - Computing the jth solution of a first-order query
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 147
EP  - 164
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007046/
UR  - https://zbmath.org/?q=an%3A1149.68028
UR  - https://www.ams.org/mathscinet-getitem?mr=2382549
UR  - https://doi.org/10.1051/ita:2007046
DO  - 10.1051/ita:2007046
LA  - en
ID  - ITA_2008__42_1_147_0
ER  - 
%0 Journal Article
%A Bagan, Guillaume
%A Durand, Arnaud
%A Grandjean, Etienne
%A Olive, Frédéric
%T Computing the jth solution of a first-order query
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 147-164
%V 42
%N 1
%I EDP-Sciences
%U https://doi.org/10.1051/ita:2007046
%R 10.1051/ita:2007046
%G en
%F ITA_2008__42_1_147_0
Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne; Olive, Frédéric. Computing the jth solution of a first-order query. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 1, pp. 147-164. doi : 10.1051/ita:2007046. http://www.numdam.org/articles/10.1051/ita:2007046/

[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. | MR | Zbl

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

[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). | MR | Zbl

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

[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. | MR | Zbl

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

Cited by Sources: