Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-05-14
1998-11-03
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
G06F 1730
Patent
active
058324771
ABSTRACT:
A method and apparatus for reordering complex SQL queries containing joins, outer and full outer joins. The method and apparatus first translates the query into a hypergraph representation. Required sets, conflict sets and preserved sets are then generated for the query hypergraph. Using the required sets, a plurality of plans are enumerated, wherein the plans represent associative re-orderings of relations in the query. SQL operators are selectively assigned to each of the enumerated plans using the conflict sets and/or preserved sets, so that the results from the plans are identical to the original query. A novel Modified General Outer Join (MGOJ) operator may be assigned to the root of a sub-tree, wherein the MGOJ operator is a compensation operator. The operator assignment is performed recursively for the root of each sub-tree in the plan. One of the enumerated plans (generally the most optimal) is then selected for execution.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 5091852 (1992-02-01), Tsunchida et al.
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5412804 (1995-05-01), Krishna
patent: 5423035 (1995-06-01), DePrez
patent: 5551031 (1996-08-01), Cheng et al.
patent: 5557791 (1996-09-01), Cheng et al.
patent: 5680603 (1997-10-01), Bhargava et al.
Apers, P.M.G., Hevner, A.R. and Yao, S.B., "Optimization Algorithms for Distributed Queries," IEEE Trans. Softw. Eng., ,pp.57-68, Jan. 1983.
Dayal, Umeshwar, "Processing Queries with Quantifiers: A Horticultural Approach", ACM PODS, pp. 125-136, 1983.
Dayal, UMeshwar, "Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers", VLDB, pp. 197-208, 1987.
Galindo-Legaria, C.A., Rosenthal, A., "How to Extend a Conventional Optimizer to Handle One and Two-Sided Outerjoin", IEEE Proceedings of Data Engineering, pp. 402-409, 1992.
Galindo-Legaria, C.A., "Algebraic Optimzation of Outerjoin Queries", Ph.D. dissertation, Center for Research in Computing Technology, Harvard University, Cambridge, MA, 1992.
Lafortune, S. and Wong, E., "A State Transition Model for Distributed Query Processing", ACM Transactions on Database Systems, vol. 11, No. 3, pp. 294-322, Sept. 1986.
Lohman, G.M., Mohan, C., Haas, L.M., Lindsay, B.G., Selinger, P.G., Wilms, P.F. and Daniels, D., "Query Processing in R*", Res. Rep. RJ 4272, IBM Research Laboratory, San Jose, Ca., Apr. 1984.
Paulley, G.N. and Per-Ake Larson, "Exploiting Uniquences in Query Optimazation", CASCON, pp.804-822, vol. II, Oct. 1993.
Pirahesh, H., Hellerstein, J.M. and Hasan, W. "Extensible/Rule Based Query Rewrite Optimization", ACM SIGMOD, pp.39-48, CA, Jun. 1992.
Rosenthal, A. and Galindo-Legaria, C., "Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins", ACM SIGMOND, pp. 291-299, 1990.
Selinger, P.G., Anstrahan, M.M., Chamberlin, D.D., Lorie, R.A. and Price, T.G., "Access Path Selection in a Relational Database Management System", ACM SIGMOND, pp. 23-34, 1979.
Kim, Won, IBM Research On Optimizing an SQL-Like Nested Query, ACM Transactions On Database Systems, vol. 7, No. 3, Sep. 1982.
Ganski et al., "Optimization of Nested SQL Queries Revisited", ACM, 1987, pp.23-33.
Haas, et al., "Extensible Query Processing in Starburst", IBM Almaden Research Center, San Jose, CA(US), ACM 1989, pp. 377-388.
Date, C.J. & Darwen, Hugh., "The Role of Functional Dependence in Query Decompositio n", Relational Database Writings 1989-1991, Part II, pp. 133-154.
Levy et al., "Query Optimization by Predicate Move-Around", Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994, pp. 96-107.
Ceri, Stephano and Pelagatti, G., "Distributed Databases--Principles and Systems," McGraw-Hill Computer Science Series, New York, 1984, pp. 93-1972.
Date, C. J., "The Outer Join", Proceedings of the Second International Conference on Databases, Cambridge, England, Sep. 1983, pp. 76-106.
Lee, B.S. and Wiederhold G. "Outer Joins and Filters for Instantiating Objects from Relational Databases Through Views", IEEE Transactions on Knowledge and Data Engineering, vol. 6, No. 1, Feb. 1994, pp. 108-119.
Bhargava Gautam
Goel Piyush
Iyer Balakrishna Ragmavendra
Black Thomas G.
Choules Jack M.
International Business Machines - Corporation
LandOfFree
Method and apparatus for reordering complex SQL queries containi does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reordering complex SQL queries containi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reordering complex SQL queries containi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-703959