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 whose instances may admit of several solutions . One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution ; enumerate without repetition each solution in some specific linear order where ; compute the solution of rank in the linear order . Algorithms of “minimal” data complexity are presented for the following problems: given any first-order formula and any structure of bounded degree: compute a random element of ; compute the th element of for some linear order of ; enumerate the elements of in lexicographical order. More precisely, we prove that, for any fixed formula , the above problem (resp. , ) can be computed within average constant time (resp. within constant time, with constant delay) after a linear precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.
Mots clés : complexity of enumeration, first-order queries, structures of bounded degree, linear time, constant time, constant delay
@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}, mrnumber = {2382549}, zbl = {1149.68028}, 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 SP - 147 EP - 164 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/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 http://www.numdam.org/articles/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, Tome 42 (2008) no. 1, pp. 147-164. doi : 10.1051/ita:2007046. http://www.numdam.org/articles/10.1051/ita:2007046/
[1] 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] 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.
, and ,[3] Linear delay enumeration and monadic second-order logic. Discrete Appl. Math. (2007) (to appear).
,[4] First-order queries on structures of bounded degree are computable with constant delay. ACM T. Comput. Logic (2007) 1-18. | MR
and ,[5] 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
and ,[6] Query evaluation via tree decompositions. J. ACM 49 (2002) 716-752. | MR
, and ,[7] Deciding first-order properties of locally tree decomposable structures. J. ACM 48 (2001) 1184-1206. | MR
and ,[8] The complexity of acyclic conjunctive queries. J. ACM 48 (2001) 431-498. | MR
, and ,[9] Décidabilité et complexité des théories logiques. Collection Didactique INRIA 8 (1991) 7-97. | MR
,[10] Machine-independent characterizations and complete problems for deterministic linear time. SIAM J. Comput. 32 (2002) 196-230. | MR | Zbl
and ,[11] Elements of finite model theory. EATCS Series, Springer (2004). | MR | Zbl
,[12] A normal form for first-order logic over doubly-linked data structures. Int. J. Found. Comput. Sci. (2006) (to appear). | MR
,[13] Randomized algorithms. Cambridge University Press (1995). | MR | Zbl
and ,[14] On the complexity of database queries. J. Comput. Syst. Sci. 58 (1999) 407-427. | MR | Zbl
and ,[15] On the complexity of bounded-variable queries. Proc. Principles of Databases Systems (PODS'95), ACM Press (1995) 266-276.
,[16] Linear time computable problems and first-order descriptions. Math. Structures Comput. Sci. 6 (1996) 505-526. | MR | Zbl
,[17] Algorithms for acyclic database schemes. Proc. Very Large Data Bases Conference (VLDB'81) (1981) 82-94.
,Cité par Sources :