Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2008-04-01
2008-04-01
Hosain, Alam (Department: 2166)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07353219
ABSTRACT:
“Determining Validity Ranges of Query Plans Based on Suboptimality” A method for approximating a validity range for a domain of cardinalities of input to an optimal query plan is provided. Such a validity range is iteratively approximated using a modified Newton-Raphson method to find roots of cost functions for optimal and alternative query plans, respectively. The Newton-Raphson method is combined with a method of incrementing roots of cost functions, known as input cardinalities, such that discontinuous and non-differentiable points in cost functions are avoided. In this manner, input cardinalities remain within a domain for which a valid range can be specified. Additionally, a robustness measure is determined by a sensitivity analysis performed on an approximated validity range. Using a robustness measure provided by a sensitivity analysis and resultant validity range and, query plan sub-optimality detection is simplified, re-optimization is selectively triggered, and robustness information is provided to a system or user performing corrective actions.
REFERENCES:
patent: 5761653 (1998-06-01), Schiefer et al.
patent: 5822747 (1998-10-01), Graefe et al.
patent: 5926820 (1999-07-01), Agrawal et al.
patent: 6092062 (2000-07-01), Lohman et al.
patent: 6272487 (2001-08-01), Beavin et al.
patent: 6363371 (2002-03-01), Chaudhuri et al.
patent: 6510422 (2003-01-01), Galindo-Legaria et al.
patent: 6625593 (2003-09-01), Leung et al.
patent: 2002/0198867 (2002-12-01), Lohman et al.
patent: 2003/0055813 (2003-03-01), Chaudhuri et al.
patent: 2003/0167258 (2003-09-01), Koo et al.
patent: 2003/0187831 (2003-10-01), Bestgen et al.
Zhang et al.; “Dynamic Selection of Optimal Grouping Sequence at Runtime for Grouping Sets, Rollup and Cube Operations in SQL Query Processing;” Jul. 29, 2003.
Bruno et al.; “Exploiting Statistics on Query Expression for Optimization;”ACM SIGMOD 2002; Jun. 4-6, 2002; pp. 263-274.
Chirkova et al.; “A Formal Perspective on the View Selection Problem”Proceedings of the 27thVLDB Conference; 2001.
Rjaibi et al.; “Incremental Cardinality Estimation for a Set of Data Values;” Jul. 15, 2002.
Markl et al.; “Learning Table Access Cardinalities with LEO;”SIGMOD '02; Jun. 3-6, 2002; p. 613.
Sitllger et al.; “LEO—DB2's LEarning Optimizer;”Proceedings of the 27thVLDB Conference; 2001.
Zuzarte, Calisto; “Method of Cardinality Estimation Using Statistical Soft Constraints;” Oct. 18, 2001.
Markl Volker G.
Raman Vijayshankar
Harper Leon J
Hosain Alam
International Business Machines - Corporation
IP Authority, LLC
Nguy Van
LandOfFree
Determining validity ranges of query plans based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determining validity ranges of query plans based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining validity ranges of query plans based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2756968