System and method for query optimization using quantile values o

Details System and method for query optimization using quantile values o System and method for query optimization using quantile values o

1994-04-14

1997-09-02

Black, Thomas G.

Boots, shoes, and leggings

364148, 395601, 395603, 395604, G06F 1730, G06F 1500

Patent

active

056641710

ABSTRACT:
A database management system determines, in a single pass over an unordered database, the quantile information. The system sequentially compares each tuple in the data set to a test value, and then selectively inserts the tuple in a test set having a cardinality less than the cardinality of the data set based upon the comparison. The system next uses the quantile information to estimate the number of tuples in the database which satisfy a user-defined predicate to generate an efficient query plan.

REFERENCES:
patent: 4379948 (1983-04-01), Ney et al.
patent: 4530076 (1985-07-01), Dwyer
patent: 4817158 (1989-03-01), Picheny
patent: 4829427 (1989-05-01), Green
patent: 5018088 (1991-05-01), Higbie
patent: 5091967 (1992-02-01), Ohsawa
patent: 5105469 (1992-04-01), MacDonald et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5379419 (1995-01-01), Heffernan et al.
J.I. Munro & M.S. Peterson, "Selection & Sorting with Limited Storage", North-Holland Publishing Company, Mar. 1980.
Raj Jain & Imrich Chlamtac, "The P.sup.2 Algorithm for Dynamic Calculation of Quantiles & Histograms Without Storing Observation", vol. 28, Oct. 1985.
"Mining Association Rules Between Sets of Items in Large Databases", R. Agrawal et al., ACM-089791-592, May 1993, pp. 207-216.
"Equidepth Partitioning of a Data Set Based on Finding Its Medians", A.P. Gurajada et al., IEEE THO355, Aug. 1991, pp. 92-101.
"The P.sup.2 Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations", R. Jain et al., Communications of the ACM, vol. 28, No. 10, Oct. 1985, pp. 1076-1085.
"Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries", M. Muralikrishna, ACM 0-89791-268, Mar. 1988, pp. 28-36.
"Accurate Estimation of the Number of Tuples Satisfying a Condition", G. Piatetsky-Shapiro, ACM 0-89791-198, Aug. 1984, pp. 256-276.
"Quantile Estimation from Grouped Data: the Cell Midpoint", B.W. Schmeiser et al., Comm. Statist.-Simula. Computa., B6(3), 1977, pp. 221-234.
"The Generation of Order Statistics in Digital Computer Simulation: A Survey", B.W. Schmeiser, pp. 137-140, no date.
"Selection and Sorting with Limited Storage", J.I. Munro et al., Theoretical Computer Science 12, North-Holland Publishing Company, 1980, pp. 315-323.

Affiliated with

Also associated with

Rating

System and method for query optimization using quantile values o does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for query optimization using quantile values o, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for query optimization using quantile values o will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-316344