Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View
  Buy Now:   Buy PDF- 8pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
Title: US5864841: System and method for query optimization using quantile values of a large unordered data set
[ Derwent Title ]

Country: US United States of America

View Images High
Resolution

 Low
 Resolution

 
8 pages

 
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: 1999-01-26 / 1997-08-28

Application Number: US1997000920049
IPC Code: Advanced: G06F 17/30;
Core: more...
IPC-7: G06F 17/30;

ECLA Code: G06F17/30S4P3T5S; G06F17/30S4P8A;

U.S. Class: Current: 707/002; 707/001; 707/003; 707/004;
Original: 707/002; 707/001; 707/003; 707/004;

Field of Search: 707/002,4,1,3

Priority Number:
1997-08-28  US1997000920049
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: Gry Cary Ware & Freidenrich ;

Primary / Asst. Examiners: Amsbury, Wayne; Lewis, Cheryl
Maintenance Status: E2 Expired  Check current status

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

       
Related Applications:
Application Number Filed Patent Pub. Date  Title
US1994000227428 1994-04-14    1997-09-02  System and method for query optimization using quantile values of a large unordered data set


       
Parent Case:     This application is a continuation of application Ser. No. 08/227,428, filed on Apr. 14, 1994, U.S. Pat. No. 5,664,171.

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 executed 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 records in the data set to a test value of the condition in a single pass over the data set;
    • means for selectively inserting a record in a test set having a cardinality less than the cardinality of the data set based upon the comparison and the condition; and
    • means for accessing the test set to generate a quantile value representative of a number of records in the database satisfying the condition.


Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 14 U.S. patent(s) that reference this one

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (14)   |   Backward references (9)   |   Citation Link

Buy
PDF		 Patent  Pub.Date  Inventor Assignee   Title
Buy PDF- 12pp US4379948  1983-04 Ney et al.  U.S. Philips Corporation Method of and arrangement for deriving characteristic values from a sound signal
Buy PDF- 8pp US4530076  1985-07 Dwyer  The United States of America as represented by the Secretary of the Navy Frequency domain non-linear signal processing apparatus and method for discrimination against non-Gaussian interference
Buy PDF- 12pp US4817158  1989-03 Picheny  International Business Machines Corporation Normalization of speech signals
Buy PDF- 27pp US4829427  1989-05 Green  Data General Corporation Database query code generation and optimization based on the cost of alternate access methods
Buy PDF- 22pp US5018088  1991-05 Higbie  The Johns Hopkins University Adaptive locally-optimum detection signal processor and processing methods
Buy PDF- 29pp US5091967  1992-02 Ohsawa  Dainippon Screen Mfg. Co., Ltd. Method of extracting contour of a subject image from an original
Buy PDF- 12pp US5105469  1992-04 MacDonald et al.  Crosfield Electronics Limited Control data array generation apparatus and method
Buy PDF- 16pp US5345585  1994-09 Iyer et al.  International Business Machines Corporation Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations
Buy PDF- 54pp US5379419  1995-01 Hefferman et al.  Digital Equipment Corporation Methods and apparatus for accesssing non-relational data files using relational queries
       
Foreign References: None

Other Abstract Info: DERABS G97-448261 DERG99-131657 DERABS G99-131657

Other References:
  • "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 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.
  • "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.


    • Inquire Regarding Licensing

    Powered by Verity
    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help