On the complexity of database queries (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of database queries (extended abstract)

Full text

Pdf (1.41 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Tucson, Arizona, United States

Pages: 12 - 19

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Christos H. Papadimitriou	Division of Computer Science, U. C. Berkeley, Berkeley, CA
Mihalis Yannakakis	Bell Laboratories, Lucent Technologies, Murray Hill, NJ

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 55, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263661.263664 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
	3	Jonathan F. Buss , Judy Goldsmith, Nondeterminism within P, SIAM Journal on Computing, v.22 n.3, p.560-572, June 1993 [doi>10.1137/0222038]
	4	Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
	5	Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
	6	Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	7	Paris Kanellakis, Constraint programming and database languages: a tutorial, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.46-53, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212447]
	8	Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
	9	Orna Lichtenstein , Amir Pnueli, Checking that finite state concurrent programs satisfy their linear specification, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-107, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318622]
	10	B. Monien, "How to Find Long Paths Efficiently", Ann. Disc. Malh., pp. 239-254, 1985.
	11	Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996 [doi>10.1006/jcss.1996.0058]
	12	N. Robertson, P. D. Seymour, "Graph Minors XIII: The Disjoin~ Paths Problem".
	13	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	14	Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
	15	Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]
	16	M. Yannakakis, "Algorithms for Acyclic Database Schemes", Proc. 7~h Intl. Conf. Very Large Data Bases, pp. 82-94, 1981.
	17	M. Yannakakis, Perspectives on database theory, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.224, October 23-25, 1995

CITED BY 17

	Martin Grohe, The parameterized complexity of database queries, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.82-92, May 2001, Santa Barbara, California, United States
	Markus Frick , Martin Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM (JACM), v.48 n.6, p.1184-1206, November 2001
	Roni Khardon, Learning first order universal Horn expressions, Proceedings of the eleventh annual conference on Computational learning theory, p.154-165, July 24-26, 1998, Madison, Wisconsin, United States
	Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
	Georg Gottlob , Francesco Scarcello , Martha Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence, v.138 n.1-2, p.55-86, June 2002
	Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
	Michael R. Fellows, Parameterized complexity: the main ideas and connections to practical computing, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Jörg Flum , Martin Grohe, Describing parameterized complexity classes, Information and Computation, v.187 n.2, p.291-319, 15 December 2003
	Sergei Vorobyov , Andrie Voronkov, Complexity of nonrecursive logic programs with complex values, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-253, June 01-04, 1998, Seattle, Washington, United States
	Roni Khardon, Learning Function-Free Horn Expressions, Machine Learning, v.37 n.3, p.241-275, Dec. 1999
	Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Francesco Scarcello, Query answering exploiting structural properties, ACM SIGMOD Record, v.34 n.3, September 2005
	Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Journal of Computer and System Sciences, v.73 n.3, p.475-506, May, 2007
	Benny Kimelfeld , Yehoshua Sagiv, Matching twigs in probabilistic XML, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece
	Rebecca J. Cathey , Steven M. Beitzel , Eric C. Jensen , David Grossman , Ophir Frieder, Using a relational database for scalable XML search, The Journal of Supercomputing, v.44 n.2, p.146-178, May 2008