On the propagation of errors in the size of join results

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the propagation of errors in the size of join results

Full text

Pdf (936 KB)

Source

International Conference on Management of Data archive
Proceedings of the 1991 ACM SIGMOD international conference on Management of data table of contents

Denver, Colorado, United States

Pages: 268 - 277

Year of Publication: 1991

ISBN:0-89791-425-2

Also published in ...

Authors

Yannis E. Ioannidis	Computer Sciences Department, University of Wisconsin, Madison, WI
Stavros Christodoulakis	Electronic and Computer Eng. Department, Technical University of Crete, 73100 Chania, Crete, Greece

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): 13, Downloads (12 Months): 68, Citation Count: 71

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

	Chr84	S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
	Chr89	S. Christodoulakis. On the estimation and use of selectivities in database performance evaluation. Research Report CS-89-24, Dept. of Computer Science, University of Waterloo, June 1989.
	IC91	Y.E. Ioannidis and S. Christodoulakis. On the propagation of errros in the size of join results. Technical Report 1018, Computer Science Dept., University of Wisconsin, Madison, March 1991.
	Kaz64	N.D. Kazarinoff. Analylic Inequalilies. Holt, Rinehart and Winston, New York, NY, 1964.
	MCS88	Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
	ML86a	Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
	ML86b	Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
	MO79	A. W. Marshall and I. Oikin. Ineq~talities: Theory of Majorization and Its Applications. Academic Press, New York, NY, 1979.
	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]
	Sel89	P.G. Selinger, June 1989. Personal communication.
	Zip49	G.K. Zipf. Human Behavior and the Princzple of Leasl Effort. Addison-Wesley, Reading, MA, 1949.

CITED BY 71

	Luc Bouganim , Olga Kapitskaia , Patrick Valduriez, Memory-adaptive scheduling for large query execution, Proceedings of the seventh international conference on Information and knowledge management, p.105-115, November 02-07, 1998, Bethesda, Maryland, United States
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	Yannis E. Ioannidis , Stavros Christodoulakis, Optimal histograms for limiting worst-case error propagation in the size of join results, ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993
	Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, ACM SIGMOD Record, v.24 n.2, p.233-244, May 1995
	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast incremental maintenance of approximate histograms, ACM Transactions on Database Systems (TODS), v.27 n.3, p.261-298, September 2002
	Fotis Barlos , Ophir Frieder, On the development of a site selection optimizer for distributed and parallel database systems, Proceedings of the second international conference on Information and knowledge management, p.684-693, November 01-05, 1993, Washington, D.C., United States
	William Perrizo , Venkata Nagarjuna Rao Goli, Domain vector hashing for earth system data querying, Proceedings of the 1995 ACM symposium on Applied computing, p.71-75, February 26-28, 1995, Nashville, Tennessee, United States
	Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, ACM SIGMOD Record, v.27 n.2, p.106-117, June 1998
	Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, ACM SIGMOD Record, v.23 n.2, p.150-160, June 1994
	Nikos Mamoulis , Dimitris Papadias, Multiway spatial joins, ACM Transactions on Database Systems (TODS), v.26 n.4, p.424-475, December 2001
	Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996
	H. V. Jagadish , Hui Jin , Beng Chin Ooi , Kian-Lee Tan, Global optimization of histograms, ACM SIGMOD Record, v.30 n.2, p.223-234, June 2001
	Joseph M. Hellerstein, Optimization techniques for queries with expensive methods, ACM Transactions on Database Systems (TODS), v.23 n.2, p.113-157, June 1998
	Martin Staudt , René Soiron , Christoph Quix , Matthias Jarke, Query optimization for repository-based applications, Proceedings of the 1999 ACM symposium on Applied computing, p.197-203, February 28-March 02, 1999, San Antonio, Texas, United States
	Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States
	Kamil Saraç , Ömer Eğecioǧlu , Amr El Abbadi, Iterated DFT based techniques for join size estimation, Proceedings of the seventh international conference on Information and knowledge management, p.348-355, November 02-07, 1998, Bethesda, Maryland, United States
	Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, ACM SIGMOD Record, v.23 n.2, p.161-172, June 1994
	Kyu Young Whang , Sang Wook Kim , Gio Wiederhold, Dynamic maintenance of data distribution for selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.1, p.29-51, January 1994
	Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998
	Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	V. Markl , N. Megiddo , M. Kutsch , T. M. Tran , P. Haas , U. Srivastava, Consistently estimating the selectivity of conjuncts of predicates, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Elisa Bertino , Paola Foscoli, On Modeling Cost Functions for Object-Oriented Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.500-508, May 1997
	Paolo Ciaccia , Dario Maio, Domains and Active Domains: What This Distinction Implies for the Estimation of Projection Sizes in Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.641-655, August 1995
	Roberto J. Bayardo, Jr. , Daniel P. Miranker, Processing queries for first-few answers, Proceedings of the fifth international conference on Information and knowledge management, p.45-52, November 12-16, 1996, Rockville, Maryland, United States
	Pauray S. M. Tsai , Arbee L. P. Chen, Optimizing Queries with Foreign Functions in a Distributed Environment, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.809-824, July 2002
	M. -S. Chen , P. S. Yu, A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.152-165, February 1994
	E. N. Hanson , S. Bodagala , U. Chadaga, Trigger Condition Testing and View Maintenance Using Optimized Discrimination Networks, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.261-280, March 2002
	Raghav Kaushik , Jeffrey F. Naughton , Raghu Ramakrishnan , Venkatesan T. Chakravarthy, Synopses for query optimization: A space-complexity perspective, ACM Transactions on Database Systems (TODS), v.30 n.4, p.1102-1127, December 2005
	A. H. H. Ngu , B. Harangsri , J. Shepherd, Query Size Estimation for Joins Using Systematic Sampling, Distributed and Parallel Databases, v.15 n.3, p.237-275, May 2004
	Surajit Chaudhuri , Vivek Narasayya , Ravishankar Ramamurthy, Estimating progress of execution for SQL queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	V. Markl , G. M. Lohman , V. Raman, LEO: An autonomic query optimizer for DB2, IBM Systems Journal, v.42 n.1, p.98-106, January 2003
	Alin Dobra, Histograms revisited: when are histograms the best approximation method for aggregates over joins?, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Anastasios Gounaris , Norman W. Paton , Alvaro A. A. Fernandes , Rizos Sakellariou, Self-monitoring query execution for adaptive query processing, Data & Knowledge Engineering, v.51 n.3, p.325-348, December 2004
	B. John Oommen , Jing Chen, A new histogram method for sparse attributes: the averaged rectangular attribute cardinality map, Proceedings of the 1st international symposium on Information and communication technologies, September 24-26, 2003, Dublin, Ireland
	Mariano P. Consens , Denilson Barbosa , Adrian Teisanu , Laurent Mignet, Goals and benchmarks for autonomic configuration recommenders, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Surajit Chaudhuri , Raghav Kaushik , Ravishankar Ramamurthy, When can we trust progress estimators for SQL queries?, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Brian Babcock , Surajit Chaudhuri, Towards a robust query optimizer: a principled and practical approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	B. John Oommen , Luis G. Rueda, A formal analysis of why heuristic functions work, Artificial Intelligence, v.164 n.1-2, p.1-22, May 2005
	Raghav Kaushik , Raghu Ramakrishnan , Venkatesan T. Chakaravarthy, Synopses for query optimization: a space-complexity perspective, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Nikos Mamoulis , Dimitris Papadias , Dinos Arkoumanis, Complex Spatial Query Processing, Geoinformatica, v.8 n.4, p.311-346, December 2004
	Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Soumen Chakrabarti , Kriti Puniyani , Sujatha Das, Optimizing scoring functions and indexes for proximity search in type-annotated corpora, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
	Anna Pagh , Rasmus Pagh, Scalable computation of acyclic joins, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Dennis Fuchs , Zhen He , Byung Suk Lee, Compressed histograms with arbitrary bucket layouts for selectivity estimation, Information Sciences: an International Journal, v.177 n.3, p.680-702, February, 2007
	Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
	Belgin Ozakar , Franck Morvan , Abdelkader Hameurlain, Mobile join operators for restricted sources, Mobile Information Systems, v.1 n.3, p.167-184, August 2005
	Peter A. Boncz , Martin L. Kersten, MIL primitives for querying a fragmented world, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.101-119, October 1999
	Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
	Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996
	Laura M. Haas , Michael J. Carey , Miron Livny , Amit Shukla, Sing the truth about ad hoc join costs, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.241-256, August 1997
	Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007
	V. Markl , P. J. Haas , M. Kutsch , N. Megiddo , U. Srivastava , T. M. Tran, Consistent selectivity estimation via maximum entropy, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.1, p.55-76, January 2007
	Michael Stillger , Guy M. Lohman , Volker Markl , Mokhtar Kandil, LEO - DB2's LEarning Optimizer, Proceedings of the 27th International Conference on Very Large Data Bases, p.19-28, September 11-14, 2001
	Christos Faloutsos , H. V. Jagadish, On B-Tree Indices for Skewed Distributions, Proceedings of the 18th International Conference on Very Large Data Bases, p.363-374, August 23-27, 1992
	Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
	Viswanath Poosala , Yannis E. Ioannidis, Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing, Proceedings of the 22th International Conference on Very Large Data Bases, p.448-459, September 03-06, 1996
	Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
	Arnd Christian König , Gerhard Weikum, Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.423-434, September 07-10, 1999
	Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
	CORPORATE Univ. of Wisconsin, Database research at Wisconsin, ACM SIGMOD Record, v.22 n.1, p.74-81, March 1993
	Lionel Brunie , Harald Kosch, Control strategies for complex relational query processing in shared nothing systems, ACM SIGMOD Record, v.25 n.3, p.34-39, Sept. 1996
	Hongjun Lu , Rudy Setiono, Effective Query Size Estimation Using Neural Networks, Applied Intelligence, v.16 n.3, p.173-183, May-June 2002
	Joseph M. Hellerstein , Michael Stonebraker , James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, v.1 n.2, p.141-259, February 2007
	Feng Yan , Wen-Chi Hou , Zhewei Jiang , Cheng Luo , Qiang Zhu, Selectivity estimation of range queries based on data density approximation via cosine series, Data & Knowledge Engineering, v.63 n.3, p.855-878, December, 2007
	Harish D. , Pooja N. Darera , Jayant R. Haritsa, Identifying robust plans through plan diagram reduction, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Peter Mork , Ken Smith , Barbara Blaustein , Chris Wolf , Keri Sarver, Facilitating discovery on the private web using dataset digests, Proceedings of the 10th International Conference on Information Integration and Web-based Applications & Services, November 24-26, 2008, Linz, Austria
	Riham Abdel Kader , Peter Boncz , Stefan Manegold , Maurice van Keulen, ROX: run-time optimization of XQueries, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.521-542, April 2009
	Surajit Chaudhuri, Query optimizers: time to rethink the contract?, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA