Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-07-28
2008-05-20
Leroux, Etienne (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
07376639
ABSTRACT:
A method for consistent selectivity estimation based on the principle of maximum entropy (ME) is provided. The method efficiently exploits all available information and avoids the bias problem. In the absence of detailed knowledge, the ME approach reduces to standard uniformity and independence assumptions. The disclosed method, based on the principle of ME, is used to improve the optimizer's cardinality estimates by orders of magnitude, resulting in better plan quality and significantly reduced query execution times.
REFERENCES:
patent: 5469568 (1995-11-01), Schiefer et al.
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5864841 (1999-01-01), Agrawal et al.
patent: 6477523 (2002-11-01), Chiang
patent: 6738755 (2004-05-01), Freytag et al.
patent: 6763359 (2004-07-01), Lohman et al.
patent: 6961685 (2005-11-01), Sy
patent: 2004/0267713 (2004-12-01), Chaudhuri et al.
patent: 2005/0004907 (2005-01-01), Bruno et al.
“Conditional Selectivity for Statistics on query expressions”, Nicolar Bruno, copyright 2004 ACM.
Getoor et al., “Selectivity Estimation Using Probabilistic Models,” ACM Sigmod 2001, May 21-24, Santa Barbara, CA, pp. 461-472.
Deshpande et al., “Independence is Good: Dependencey-Based Histogram Synopses for High-Dimensional Data,” ACM Sigmod 2001, May 21-24, Santa Barbara, CA, pp. 199-210.
Wang et al., “Estimating the Selectivity of XML Path Expression with Predicates by Histograms,” The 5thInternational Conf. on Web-Age Information Management (WAIM), Jul. 15-17, 2004, Dalian, China, pp. 410-418.
Chaudhuri et al., “Selectivity Estimation for String Predicates: Overcoming the Underestimation Problem,” Proceedings of the 20thInternational Conf. on Data Engineering (ICDE '04), Mar. 30.-Apr. 2, 2004, Boston, MA, 13pgs.
Chung et al., “An Efficient Selectivity Estimation Method for Spatial Query Optimization with Topological Relationships,” Journal of Chongqing University of Posts and Telecommunications (Natural Science), V16, N5, Oct. 2004, pp. 113-120.
Kutsch Marcel
Markl Volker Gerhard
Megiddo Nimrod
Tran Tam Minh Dai
IP Authority, LLC
Leroux Etienne
Nguy Van
Nguyen Cindy
Soundararajan Ramraj
LandOfFree
Selectivity estimation for conjunctive predicates in the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selectivity estimation for conjunctive predicates in the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selectivity estimation for conjunctive predicates in the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3982890