Boots – shoes – and leggings
Patent
1995-02-17
1996-08-20
Kulik, Paul V.
Boots, shoes, and leggings
364DIG1, 3642821, 3642834, G06F 1730
Patent
active
055487556
ABSTRACT:
A system for optimizing SQL queries in a relational database management system using magic decorrelation. After representing an assembly of multiple SQL queries in computer memory using data structures configured in the query box representation ("QBR") format, queries amenable to decorrelation are identified, and FEED and ABSORB stages are applied to rewrite the QBR in decorrelated form. The FEED stage generates a set of correlation values that the subquery can use to decorrelate. The ABSORB stage decorrelates the subquery using the correlation values prepared by the FEED stage, resulting in the correlation bindings being absorbed into the subquery. The invention thereby takes full advantage of set-at-a-time, rather than tuple-at-a-time, processing.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 5043872 (1991-08-01), Cheng et al.
patent: 5067166 (1991-11-01), Ito
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5367675 (1994-11-01), Cheng et al.
P. Selinger et al., "Access Path Selection in a Relational Database Management System", Proc. of the 1979 Assoc. of Comp. Mach.(ACM) SIGMOD Intl Conf. on Management of Data, 1979, pp. 1-59.
Kim, "On Optimizing an SQL-Like Nested Query", ACM Transactions on Database Systems, Sep. 7, 1982, pp. 443-469.
A. Chen et al., "Properties of Optimal Semi-join Programs for Distributed Query Processing", Proc. of the IEEE Comp. Soc., 7th Intl. Comp. Sofware and Appls. Conf., Chicago, Ill. Nov. 1983, pp. 476-483.
Jiawei Han et al., "Efficient Evaluation of Multiple Linear Recursions, IEEE Transactions on Software Engineering,"vol. 17 No. 12, Dec. 1991, pp. 1241-1252.
Mumick et al., "Implementation of Magic-sets in a Relational Database System", Proc. of the 1994 ACM Sigmod, International Conference on Management of Data, Minneapolis, MN, 1994, pp. 103-114.
Dayal, "Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates and Quantifiers", Proceedings of the Eighteenth International Conference on Very Large Databases (VLDB), pp. 197-208, 1987.
Ganski et al., "Optimization of Nested SQL Queries Revisited", Proceedings of ACM SIGMOD '87, International Conference on Management of Data, San Francisco, CA, 1987 pp. 23-33.
Y. Ioannidis et al., "Query Optimization by Simulated Annealing", Proc. of the 1987 ACM-SIGMOD Conf. on Management of Data, San Francisco, CA, May 1987, pp. 9-22.
S. Chi et al., "Recursive Query Answering with Non-Horn Clauses", Proc. of the 9th Intl. Conf. on Automated Deduction, Argonne, ILL, May 1988, pp. 294-313.
G. M. Lohman, "Grammar-like Functional Rules for Representing Query Optimization Alternatives", IBM Almaden Research Center, San Jose, CA 95120, Jun. 1988, pp. 18-27.
S. Pramanik et al., "Optimizing Join Queries in Distributed Databases", IEEE Trans. on Software Engr., vol. 14, No. 9, pp. 1319-1326, Sep. 1988.
E. Omiecinski, "Heuristics for Join Processing Using Nonclustered Indexes", IEEE Trans. on Software Engineering, vol. 15, No. 1, Jan. 1989, pp. 18-25.
A. Swami, "Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques", Proc. of 1989 ACM-SIGMOD Intl Conf. of Management of Data, Portland, Oregon, Jun. 1989, pp. 367-376.
D. Cornell et al., "Integrated Site Assignment for Relations and Join Operations in Distributed Transaction Processing", IBM Technical Disclosure Bulletin, vol. 32, No. 4A, Sep. 1989, pp. 306-314.
L. Haas, et al., "Extensible Query Processing in Starburst", Proc. of the 1989 ACM Sigmod, International Conf. on the Management of Data, Portland, OR, 1989, pp. 377-388.
Mumick et al. "Magic is Relevant", Proceedings of ADM SIGMOD '90, International Conference on Management of Data, Atlantic City, NJ, 1990, pp. 1-23.
Haas et al., "STARBURST Mid-flight: As the Dust Clears," IEEE Transactions on Knowledge and Data Engineering, Mar. 1990, pp. 143-160.
Y. Ioannidis et al., "Randomized Algorithms Large Join Queries", Proc. of the 1990 ACM-SIGMOD Intl Conf. on Management of Data, Atlantic City, NJ, May 1990, pp. 312-321.
D. Cornell et al., "Integrated Buffer Management and Query Optimization Strategy for Relational Databases", IBM Technical Disclosure Bulletin, vol. 32, No. 12, May 1990, pp. 253-257.
M. Chen et al., "Using Join Operations as Reducers in Distributed Query Processing", Proc. 2nd Intl. Sym. on Databases in Parallel and Distributed Systems, Dublin, Ireland, Jul. 1990, (Abstract only).
K. Ono et al., "Measuring the Complexity of Join Enumeration in Query Optimization", Proceedings of the 16th VLDB Conference, Brisbane, Australia, Aug. 1990, pp. 314-325.
Beeri et al., "On the Power of Magic", Proc. of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Diego, CA, 1987, pp. 269-283.
S. Lee et al., "Semantic Query Reformulation in Deductive Databases", IEEE Proc. of the 7th Intl Conf. on Data Engr., Koby, Japan, Apr. 1991, pp. 232-239.
Muralikrishna, "Improved Unnesting Algorithms for Join Aggregate SQL Queries", Proceedings of the Eighteenth International Conference on Very large Databases VLDB, pp. 91-102, 1992.
A. Shibamiya et al., "DB2 Cost Formula", IBM Technical Disclosure Bulletin, vol. 34, No. 12, May 1992, pp. 389-394.
H. Pirahesh et al., "Extensible/Rule Based Query Rewrite Optimization in Starburst", Proc. of 1992 ACM SIGMOD, Jun. 1992, pp. 39-48.
R. Kabler et al., "Performance Evaluation of Algorithms for Transitive Closure", Information Systems, vol. 17, No. 5, Sep. 1992, pp. 415-441.
W. Hong et al., "Optimization of Parallel Query Execution Plans in XPRS", Distributed and Parallel Databases, vol. 1, No. 1, pp. 9-32, Jan. 1993.
Raab, TPC Benchmark .TM.D (Decision Support) Working Draft 9.0, 1995 (Transaction Processing Performance Council), pp. 1-124.
Leung Ting Y.
Pirahesh Mir H.
Seshadri Praveen
International Business Machines - Corporation
Kulik Paul V.
LandOfFree
System for optimizing correlated SQL queries in a relational dat 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 for optimizing correlated SQL queries in a relational dat, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for optimizing correlated SQL queries in a relational dat will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2337839