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

1997-08-28

1999-01-26

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 1, 707 3, 707 4, G06F 1730

Patent

active

058648410

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), Hefferman et al.
"Mining Association Rules Between sets of items in large databases", R. Agrawal et al., ACM-089791-592, May 993, pp. 207-216.
"Equidepth Partitioning of a Data Set Based on Finding its Medians", A.P. Gurajada et al., IEEE TH0 355, Sep. 1991, pp. 32-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.
"Selection and Sorting With Limited Storage", J.I. Munro et al., Theoretical Computer Science 12, North-Holland Publishing Company, 1980, pp. 35-323.
David J. DeWitt, Jeffrey F. Naughton, and Donovan A. Schneider, "Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting", IEEE, p. 280-291, Jan. 1991.
M. Pawlak and U. Stradtmuller, "On Nonparametric Curve Estimation With Compressed Data", IEEE, p. 253, Jan. 1995.

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-1458584