Optimization of real conjunctive queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimization of real conjunctive queries

Full text

Pdf (901 KB)

Source

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

Washington, D.C., United States

Pages: 59 - 70

Year of Publication: 1993

ISBN:0-89791-593-3

Authors

Surajit Chaudhuri
Moshe Y. Vardi	IBM Almaden Research Center, San Jose, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 59, Citation Count: 35

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/153850.153856 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.

	ASU79A	Aho A. V., Sagiv Y, Ullman J. D., "Equivalence of Relational Expressions," SIAM Journal of Computing 8:2, pp. 218- 246.
	ASU79B	A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
	CM77	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]
	D87	C J Date, A guide to the SQL standard, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	DGK82	Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
	DBS90	Pratul Dublish , Joachim Biskup, Optimization of a subclass of conjunctive queries (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.455-469, November 1990, Paris, France
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	IR92	Ioannidis Y. E., Ramakrishnan R., "Generalized Containment of Conjunctive Queries," Computer Science Technical Report, University of Wisconsin-Madison, 1992.
	JK84	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
	K86	Aviel Klausner, Multirelations in relational databases (duplicates, acyclic databases, functional dependencies, tableaux), 1986
	K88	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]
	MPR90	Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
	NPS91	M. Negri , G. Pelagatti , L. Sbattella, Formal semantics of SQL queries, ACM Transactions on Database Systems (TODS), v.16 n.3, p.513-534, Sept. 1991 [doi>10.1145/111197.111212]
	S*79	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	St77	Stockmeyer L.J., "The polynomial-time hierarchy", Theoretical Computer Sci= ence, Vol 3, 1977, pp. 1-22.
	SY81	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	U89	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

CITED BY 35

	Vitaliy L. Khizder , Grant E. Weddell, Reasoning about Uniqueness Constraints in Object Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1295-1306, September 2003
	Oscar H. Ibarra , Jianwen Su, On the containment and equivalence of database queries with linear constraints (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.32-43, May 11-15, 1997, Tucson, Arizona, United States
	Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States
	Val Tannen, Tutorial: languages for collection types, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.150-154, May 24-27, 1994, Minneapolis, Minnesota, United States
	Werner Nutt , Yehoshus Sagiv , Sara Shurin, Deciding equivalences among aggregate queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-223, June 01-04, 1998, Seattle, Washington, United States
	Yannis E. Ioannidis , Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Transactions on Database Systems (TODS), v.20 n.3, p.288-324, Sept. 1995
	Reée J. Miller, Using schematically heterogeneous structures, ACM SIGMOD Record, v.27 n.2, p.189-200, June 1998
	Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Alon Y. Levy, Logic-based techniques in data integration, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
	Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States
	Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Sara Cohen , Yehoshua Sagiv , Werner Nutt, Equivalences among aggregate queries with negation, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.328-360, April 2005
	Sara Cohen, Containment of aggregate queries, ACM SIGMOD Record, v.34 n.1, March 2005
	Murali Mani , Song Wang , Dan Dougherty , Elke A. Rundensteiner, Join minimization in XML-to-SQL translation: an algebraic approach, ACM SIGMOD Record, v.35 n.1, p.20-25, March 2006
	Sara Cohen , Werner Nutt , Yehoshua Sagiv, Rewriting queries with arbitrary aggregation functions using views, ACM Transactions on Database Systems (TODS), v.31 n.2, p.672-715, June 2006
	Gang Gou , Maxim Kormilitsin , Rada Chirkova, Query evaluation using overlapping views: completeness and efficiency, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	T. S. Jayram , Phokion G. Kolaitis , Erik Vee, The containment problem for <bi>Real</bi> conjunctive queries with inequalities, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Sara Cohen, Equivalence of queries combining set and bag-set semantics, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Nicola Onose , Alin Deutsch , Yannis Papakonstantinou , Emiran Curtmola, Rewriting nested XML queries using nested views, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Sara Cohen , Werner Nutt , Yehoshua Sagiv, Deciding equivalences among conjunctive aggregate queries, Journal of the ACM (JACM), v.54 n.2, p.5-es, April 2007
	Deepavali Bhagwat , Laura Chiticariu , Wang-Chiew Tan , Gaurav Vijayvargiya, An annotation management system for relational databases, Proceedings of the Thirtieth international conference on Very large data bases, p.900-911, August 31-September 03, 2004, Toronto, Canada
	Xin Dong , Alon Y. Halevy , Igor Tatarinov, Containment of nested XML queries, Proceedings of the Thirtieth international conference on Very large data bases, p.132-143, August 31-September 03, 2004, Toronto, Canada
	Rajasekar Krishnamurthy , Raghav Kaushik , Jeffrey F. Naughton, Efficient XML-to-SQL query translation: where to add the intelligence?, Proceedings of the Thirtieth international conference on Very large data bases, p.144-155, August 31-September 03, 2004, Toronto, Canada
	Aris Tsois , Timos Sellis, The generalized pre-grouping transformation: aggregate-query optimization in the presence of dependencies, Proceedings of the 29th international conference on Very large data bases, p.644-655, September 09-12, 2003, Berlin, Germany
	Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001
	Sara Cohen , Werner Nutt , Yehoshua Sagiv, Equivalences among aggregate queries with negation, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 2001, Santa Barbara, California, United States
	Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Dongfeng Chen , Rada Chirkova , Fereidoon Sadri, Query optimization using restructured views: Theory and experiments, Information Systems, v.34 n.3, p.353-370, May, 2009
	Rada Chirkova , Michael R. Genesereth, Equivalence of SQL queries in presence of embedded dependencies, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Todd J. Green , Zachary G. Ives , Val Tannen, Reconcilable differences, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Todd J. Green, Containment of conjunctive queries on annotated relations, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Sara Cohen, Equivalence of queries that are sensitive to multiplicities, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.3, p.765-785, June 2009
	David DeHaan, Equivalence of nested queries with mixed semantics, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA