Computing the jth solution of a first-order query

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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 147-164 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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 (x) = {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 (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}, \dots, 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 $ϕ (\bar{v})$ and any structure $S$ of bounded degree: $(1)$ compute a random element of $ϕ (S) = {\bar{a} : (S, \bar{a}) ⊧ ϕ (\bar{v})}$ ; $(2)$ compute the $j$ th element of $ϕ (S)$ for some linear order of $ϕ (S)$ ; $(3)$ enumerate the elements of $ϕ (S)$ in lexicographical order. More precisely, we prove that, for any fixed formula $ϕ$ , 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 (| S |))$ precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

Publié le : 2008-01-01

MR 2382549 | Zbl 1149.68028

DOI : https://doi.org/10.1051/ita:2007046
Classification: 68Q15, 68Q19

@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},
     volume = {42},
     year = {2008},
     pages = {147-164},
     doi = {10.1051/ita:2007046},
     mrnumber = {2382549},
     zbl = {1149.68028},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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, Tome 42 (2008) pp. 147-164. doi : 10.1051/ita:2007046. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_147_0/

Bibliographie

[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 2334422 | Zbl pre05528206

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

[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 2350797

[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 2334433 | Zbl pre05528217

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

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

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

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

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

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

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

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

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

[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 1436931 | Zbl 0862.68056

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