Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-04-06
2009-12-22
Jalil, Neveen Abel (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07636707
ABSTRACT:
Selectivity estimates are produced that meet a desired confidence threshold. To determine the confidence level of a given selectivity estimate for a query expression, the query expression is evaluated on a sample tuples. A probability density function is derived based on the number of tuples in the sample that satisfy the query expression. The cumulative distribution for the probability density function is solved for the given threshold to determine a selectivity estimate at the given confidence value.
REFERENCES:
patent: 5893090 (1999-04-01), Friedman et al.
patent: 6272487 (2001-08-01), Beavin et al.
patent: 6466894 (2002-10-01), Takeuchi et al.
patent: 6477534 (2002-11-01), Acharya et al.
patent: 6738755 (2004-05-01), Freytag et al.
patent: 6778976 (2004-08-01), Haas et al.
patent: 7139749 (2006-11-01), Bossman et al.
patent: 7356526 (2008-04-01), Gao et al.
patent: 7519529 (2009-04-01), Horvitz
patent: 2004/0205052 (2004-10-01), Gloor et al.
patent: 2005/0210023 (2005-09-01), Barrera et al.
Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy, Join Synopses for Approximate Query Answering, SIGMOD '99 Philadelphia PA Copyright ACM 1999, pp. 275-286.
Gennady Antoshenkov, Query Processing in DEC Rdb: Major Issues and Future Challenges, Database Systems Group, Digital Equipment Corporation USA, pp. 41-50.
Daniel Barbara, William Dumouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstin, Yannis Ioannidis, H.V. Jagadish, Theodore Johnson, Raymond Ng, Viswanath Poosala, Kenneth A. Ross, and Kenneth C. Sevcik, The New Jersey Data Reduction Report, Bulletin of the Technical Committee on Data Engineering Dec. 1997 vol. 20 No. 4 IEEE Computer Society.
Surajit Chaudhuri and Vivek Narasayya, Automating Statistics Management for Query Optimizers, IEEE Transactions on Knowledge and Data Engineering, vol. 13, No. 1 Jan./Feb. 2001, pp. 7-20.
Chungmin Melvin Chen and Nick Roussopouloas, Adaptive Selectivity Estimation Using Query Feedback, SIGMOD 94- 5/94 Minneapolis, Minnesota, USA © 1994 ACM, pp. 161-172.
Francis Chu, Joseph Halpern, and Johannes Gehrke, Least Expected Cost Query Optimization: What Can We Expect?, ACM PODS Jun. 3-6, 2002, Madison, Wisconsin, USA © 2002 ACM, pp. 293-302.
Francis Chu, Joseph Y. Halpern, and Praveen Seshadri, Least Expected Cost Query Optimization: An Exercise in Utility, PODS '99 Philadelphia PA Copyright ACM 1999, pp. 138-147.
G.W. Cran, K. J. Martin, and G.E. Thomas, Applied Statistics, Journal of the Royal Statistical Society (Series C) vol. 26, No. 1, 1977, pp. 111-114.
Amol Deshpande, Minos Garofalakism and Rajeev Rastogi, Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data, ACM SIGMOD May 21-24, 2001, Santa Barbara, California, USA Copyright 2001 ACM.
Donko Donjerkovic and Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25thVLDB Conference, Edinburgh, Scotland, 1999, pp. 411-422.
C. Faloutsos and I. Kamel, Relaxing the Uniformity and Independence Assumptions Using the Concept of Fractal Dimensions, Journal of Computer and System Sciences, vol. 55. No. 2, Oct. 1997, Copyright © 1997 by Academic Press, pp. 229-240.
Lise Getoor, Learning Statistical Models From Relational Data, Dec. 2001, Copyright 2002 by Geloor, Lise Carol.
Lise Getoor, Ben Taskar, and Daphne Koller, Selectivity Estimation using Probabilistic Models, ACM SIGMOD May 21-24, 2001, Santa Barbara, California, USA Copyright 2001 ACM.
Peter J. Haas, Jeffrey F Naughton, S. Seshardri, and Arun N. Swami, Selectivity and Cost estimation for Joins Based on Random Sampling, Journal of Computer and System Sciences, vol. 52, No. 3, Jun. 1996, Copyright © 1996 by Academic Press, Inc.
Peter J. Haas and Arun N. Swami, Sequential Sampling Procedures for Query Size Estimation, 1992 ACM SIGMOD—6/92/CA, USA © 1992 AMC, pp. 341-350.
Yannis Ioannidis, The History of Histograms (abridged), Proceedings of the 29thVLDB Conference, Berlin, Germany, 2003.
Yannis E. Ioannidis and Stavros Christodoulakis, On the Propagation of Errors in the Size of Join Results, © 1991 ACM, pp. 268-277.
H.V. Hagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Ken Sevcik, and Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24thVLDB Conference New York, USA, 1998, pp. 275-286.
Ju-Hung Lee, Deok-Hwan Kim, and Chin-Wan Chung, Multi-dimensional Selectivity Estimation Using Compressed Histogram Information, SIGMOND '99 Philadelphia PA, Copyright ACM 1999, pp. 205-214.
Richard J. Lipton, Jeffrey F. Naughton, and Donovan A. Schneider, Practical Selectivity Estimation through Adaptive Sampling, © 1990 ACM, pp. 1-11.
Michael V. Mannino, Paicheng Chu, and Thomas Sager, Statistical Profile Estimation in Database Systems, ACM Computing Surveys, vol. 20, No. 3 Sep. 1988, © 1988 ACM, pp. 191-221.
Yossi Matias, Jeffrey Scott Vitter, and Min Wang, Wavelet-Bases Histograms for Selectivity Estimation, S1GMON '98 Seattle, WA, USA © 1998 ACM, pp. 448-459.
M. Muralikrishna and David J. Dewitt, Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries, © 1988 ACM, pp. 28-36.
Frank Olken, Random Sampling from Databases, Copyright 1993 by The Regents of the University of California.
Viswanath Poosala and Yannis E. Ioannidis, Selectivity Without the Attribute Value Independence Assumption, Proceedings of the 23rdVLDB Conference Athens, Greece, 1997, pp. 486-495.
Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, and Eugene J. Shekita, Improved Histograms for Selectivity Estimation of Range Predicates, SIGMOD '96 6/96 Montreal, Canada © 1996 ACM, pp. 294-305.
Kamil Saraç, Ömer E{hacek over (g)}ecio{hacek over (g)}lu, and Amr El Abbadi, Iterated DFT Based Techniques for Join Size Estimation, CIKM 98 Bethesda, MD USA, Copyright ACM 1998, pp. 348-355.
Kevin D. Seppi, J. Wesley Barnes, and Carl N. Morris, A Bayesian Approach to Database Query Optimization, ORSA Journal on Computing vol. 5, No. 4 1993, pp. 410-419.
Babcock Brian Frederick
Chaudhuri Surajit
Abel Jalil Neveen
Lee & Hayes PLLC
Microsoft Corporation
Pulliam Christyann R
LandOfFree
Query selectivity estimation with confidence interval does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Query selectivity estimation with confidence interval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query selectivity estimation with confidence interval will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4147281