The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jul. 16, 2002
Filed:
Jun. 14, 1999
Method and system for determining the lowest cost permutation for joining relational database tables
Joseph Sinnott, Jr., Palo Alto, CA (US);
International Business Machines Corporation, Armonk, NY (US);
Abstract
A method and system for calculating the lowest cost join permutation for queries which involve multiple database tables is disclosed. A method and system comprises building all initial table composites and determining the cost of building each member of the set of composites one table at a time. The method and system includes comparing the cost of building each member of the composites to a threshold value and skipping any member of the set of composites that has a value greater than the threshold value. The method and system includes calculating the cost of building all possible members of the next successively larger set of composites which can be built from members which do not exceed the threshold value and saving the lowest cost means for building each member of the next successively larger composites. The method and system includes determining if a final composite has been built and stepping to the next composites if the final composite has not been built. Finally, the method and system includes repeating the above until the final composite has been built. The costs of building a given composite are compared to a threshold. The threshold is determined by choosing a minimum cost composite from all the composites which have N tables in them. The costs of adding each missing table, one at a time, to this composite are calculated until the full N-table composite has been “built”. The minimum cost of building the N-table composite is the threshold. The threshold value is recalculated each time the successively larger set of composite tables has been built. If any new calculation results in a lower threshold value, the newer value replaces the current threshold value.