 |
|
|
|
|
|
 Title: |
US5664171:
System and method for query optimization using quantile values of a large unordered data set
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Swami, Arun Narasimha; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1997-09-02
/ 1994-04-14
|
| Application Number: |
US1994000227428
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 15/00;
G06F 17/30;
|
| ECLA Code: |
G06F17/30S4P3T5S; G06F17/30S4P8A;
|
| U.S. Class: |
Current:
707/002;
707/003;
707/004;
715/210;
Original:
395/602;
364/148;
395/601;
395/603;
395/604;
|
| Field of Search: |
395/600
364/574,300
|
| Priority Number: |
| 1994-04-14 |
US1994000227428 |
|
| 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.
|
| Attorney, Agent or Firm: |
Baker, Maxham, Jester & Meador ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Lewis, Cheryl R.
|
| Maintenance Status: |
E3 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 2 known family members
|
First Claim:
Show all 12 claims |
We claim:
1. A data storage system, comprising:
- a computer;
- one or more input devices electrically connected to the computer for generating a user request for data satisfying a predetermined condition;
- a database accessible by the computer for holding a set of data records; and
- a database management system executable by the computer, the database management system including a compiler, the compiler including:
- a query optimizer for generating a query plan in response to quantiles of the set of data records;
- comparator means in the query optimizer for sequentially comparing the data records in the set of data records to a test value of the condition in a single pass over the set of data records;
- means for selectively inserting a data record in a test set having a cardinality less than the cardinality of the set of data records based upon the comparison and the condition; and
- means for accessing the test set to generate a quantile value in response to a data record in the test set, the quantile value representative of a number of data records in the database satisfying the condition.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 20 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
J.I. Munro & M.S. Peterson, "Selection & Sorting with Limited Storage", North-Holland Publishing Company, Mar. 1980.
Raj Jain & Imrich Chlamtac, "The P2 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 P2 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.
(10 pages)
Cited by 4 patents
"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.
(14 pages)
Cited by 3 patents
"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.
(9 pages)
Cited by 3 patents
|
|
 Nominate this for the Gallery...
|
|
