Deciding equivalences among aggregate queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deciding equivalences among aggregate queries

Full text

Pdf (1.37 MB)

Source

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

Seattle, Washington, United States

Pages: 214 - 223

Year of Publication: 1998

ISBN:0-89791-996-3

Authors

Werner Nutt	Institute of Computer Science, The Hebrew University, Jerusalem 91904, Israel and German Research Center for Artificial Intelligence GmbH, Stuhlsatzenhausweg 3, 66123 Saarbrücken, Germany
Yehoshus Sagiv	Institute for Computer Science, The Hebrew University, Jerusalem 91904, Israel
Sara Shurin	Institute for Computer Science, The Hebrew University, Jerusalem 91904, Israel

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	ASU79	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]
	CKPS95	Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
	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]
	CV93	Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
	DJLS96	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
	GHQ95	Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
	IR95	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 [doi>10.1145/211414.211419]
	JK83	D.S. Johnson and A. Klug. Optimizing conjunctive queries that contain untyped variables. SIAM Journal on Computing, 12(4):616-640, 1983.
	LMSS93	Alon Levy , Inderpal Singh Mumick , Yehoshua Sagiv , Oded Shmueli, Equivalence, query-reachability and satisfiability in Datalog extensions, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-122, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153860]
	LS95	Alon Y. Levy , Yehoshua Sagiv, Semantic query optimization in Datalog programs (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.163-173, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220207]
	RSSS98	Kenneth A. Ross , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Foundations of aggregation constraints, Theoretical Computer Science, v.193 n.1-2, p.149-179, Feb. 28, 1998 [doi>10.1016/S0304-3975(97)00011-X]
	SS92	Yehoshua Sagiv , Yatin Saraiya, Minimizing restricted-fanout queries, Discrete Applied Mathematics, v.40 n.2, p.245-264, Dec. 10, 1992 [doi>10.1016/0166-218X(92)90032-6]
	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]
	vdM92	R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]

CITED BY 23

	Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, ACM SIGMOD Record, v.30 n.2, p.331-342, June 2001
	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
	J. Albrecht , W. Hümmer , W. Lehner , L. Schlesinger, Query optimization by using derivability in a data warehouse environment, Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, p.49-56, November 06-11, 2000, McLean, Virginia, United States
	Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, ACM SIGMOD Record, v.29 n.2, p.105-116, June 2000
	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
	Leonardo Tininini, Querying multidimensional data, Multidimensional databases: problems and solutions, Idea Group Publishing, Hershey, PA, 2003
	Franz Baader , Ulrike Sattler, Description logics with aggregates and concrete domains, Information Systems, v.28 n.8, p.979-1004, December 2003
	José Luis Ambite , Craig A. Knoblock , Ion Muslea , Andrew G. Philpot, Compiling Source Descriptions for Efficient and Flexible Information Integration, Journal of Intelligent Information Systems, v.16 n.2, p.149-187, March/April 2001
	Ernest Teniente , Toni Urpí, Checking query containment with the CQC method, Data & Knowledge Engineering, v.53 n.2, p.163-223, May 2005
	Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001
	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
	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
	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
	Roberto Esposito , Rosa Meo , Marco Botta, Answering constraint-based mining queries on itemsets using previous materialized results, Journal of Intelligent Information Systems, v.26 n.1, p.95-111, January 2006
	Rada Chirkova , Fereidoon Sadri, Query optimization using restructured views, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, 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
	Rona Machlin, Index-based multidimensional array queries: safety and equivalence, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	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
	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, Containment of conjunctive queries on annotated relations, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia