Abstract
We study the enumeration complexity of the natural extension of acyclic conjunctive queries with disequalities. In this language, a number of NP-complete problems can be expressed. We first improve a previous result of Papadimitriou and Yannakakis by proving that such queries can be computed in time \(c.|\cal M|.|\varphi(\cal M)|\) where \(\cal M\) is the structure, \(\varphi(\cal M)\) is the result set of the query and c is a simple exponential in the size of the formula ϕ. A consequence of our method is that, in the general case, tuples of such queries can be enumerated with a linear delay between two tuples.
We then introduce a large subclass of acyclic formulas called CCQ ≠ and prove that the tuples of a CCQ ≠ query can be enumerated with a linear time precomputation and a constant delay between consecutive solutions. Moreover, under the hypothesis that the multiplication of two n×n boolean matrices cannot be done in time O(n 2), this leads to the following dichotomy for acyclic queries: either such a query is in CCQ ≠ or it cannot be enumerated with linear precomputation and constant delay. Furthermore we prove that testing whether an acyclic formula is in CCQ ≠ can be performed in polynomial time.
Finally, the notion of free-connex treewidth of a structure is defined. We show that for each query of free-connex treewidth bounded by some constant k, enumeration of results can be done with \(O(|{\mathcal M}|^{k+1})\) precomputation steps and constant delay.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bagan, G.: MSO queries on tree decomposable structures are computable with linear delay. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 167–181. Springer, Heidelberg (2006)
Bagan, G., Durand, A., Grandjean, E., Olive, F.: Computing the jth element of a first-order query (submitted 2007)
Berge, C.: Graphs and hypergraphs, 2nd edn. Amsterdam (1973)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1–21 (1993)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theor. Comput. Sci. 239(2), 211–229 (2000)
Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.: Group-theoretic algorithms for matrix multiplication. In: FOCS, pp. 379–388 (2005)
Courcelle, B.: Linear delay enumeration and monadic second-order logic. Discrete Applied Maths (to appear, 2006)
Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(1&2), 49–82 (1993)
Durand, A., Grandjean, E.: First-order queries on structures of bounded degree are computable with constant delay. Transactions on Computational Logic (to appear)
Durand, A., Olive, F.: First-order queries over one unary function. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 334–348. Springer, Heidelberg (2006)
Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716–752 (2002)
Grandjean, E., Schwentick, T.: Machine-independent characterizations and complete problems for deterministic linear time. SIAM J. Comput. 32(1), 196–230 (2002)
Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In: STOC, pp. 657–666 (2001)
Libkin, L.: Elements of finite model theory. Springer, Heidelberg (2004)
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)
Yannakakis, M.: Algorithms for acyclic database schemes, 82–94 (1981)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bagan, G., Durand, A., Grandjean, E. (2007). On Acyclic Conjunctive Queries and Constant Delay Enumeration. In: Duparc, J., Henzinger, T.A. (eds) Computer Science Logic. CSL 2007. Lecture Notes in Computer Science, vol 4646. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74915-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-74915-8_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74914-1
Online ISBN: 978-3-540-74915-8
eBook Packages: Computer ScienceComputer Science (R0)