Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2011-02-01
2011-02-01
Ly, Cheyne D (Department: 2168)
Data processing: database and file management or data structures
Database and file access
Query optimization
C707S719000, C707S797000
Reexamination Certificate
active
07882100
ABSTRACT:
A database system with methodology for generating bushy nested loop join trees is described. In one embodiment, for example, an improved method is described for optimization of a query requesting data from a database, the method comprises steps of: generating a left deep operator tree for returning data requested by the query based on traversing a left deep operator tree search space; transforming the left deep operator tree into a semantically correct structure for returning data requested by the query; and building a query execution plan for returning data requested by the query based on the semantically correct structure.
REFERENCES:
patent: 5121494 (1992-06-01), Dias et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5412804 (1995-05-01), Krishna
patent: 5412806 (1995-05-01), Du et al.
patent: 5446886 (1995-08-01), Li
patent: 5469568 (1995-11-01), Schiefer et al.
patent: 5495605 (1996-02-01), Cadot
patent: 5694591 (1997-12-01), Du et al.
patent: 5758335 (1998-05-01), Gray
patent: 5822750 (1998-10-01), Jou et al.
patent: 6021405 (2000-02-01), Celis et al.
patent: 6421663 (2002-07-01), Chen et al.
patent: 6665663 (2003-12-01), Lindsay et al.
patent: 6757670 (2004-06-01), Inohara et al.
patent: 6807546 (2004-10-01), Young-Lai
patent: 6996557 (2006-02-01), Leung et al.
patent: 7076477 (2006-07-01), Lin et al.
patent: 7139749 (2006-11-01), Bossman et al.
patent: 7171398 (2007-01-01), Bestgen et al.
patent: 7184998 (2007-02-01), Nica
patent: 7523462 (2009-04-01), Nesamoney et al.
patent: 2004/0006561 (2004-01-01), Nica
patent: 2004/0220923 (2004-11-01), Nica
Andrei et al., Proceedings of the 27th VLDB Conference, Roma, Italy, 2001, pp. 1-10.
Leonard D. Shapiro, David Maier, Paul Benninghoff, Keith Billings, Yubo Fan, Kavita Hatwal, Quan Wang, Yu Zhang, Hsiao min Wu, and Bennet Vance. Exploiting upper and lower bounds in top-down query optimization. In Proceedings of Ideas '01, pp. 20-33, 2001.
Kremer et al. A Survey of Query Optimization in Parallel Databases, York University, Nov. 1, 1999, pp. 1-29.
Von, V., Algeraic Query Optimization in Database Systems, Universitate Mannheim, 1999, pp. 1-139.
McKenna, W. J., Efficient Search in Extensible database query optimization: The Volcano Optimizer Generator, University Microfiles International, 1993, pp. 1-152.
Evrendilek et al., Distributed and Parallel Databases, 5, 77-114 (1997).
Scheufele et al., PODS '97 Tucson Arizona, USA, 1997, pp. 238-248.
Wilschut et al., SIGMOND '95, San Jose, CA USA, 1995, pp. 115-126.
Steinebrunn, M. et al, Heuristic and Randomized Optimization for the Join Ordering Problem, VLDB Journal, vol. 6: 191-208, 1997.
Vance, B. et al, Rapid Bushy Join-Order Optimization with Cartesian Products, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 35-46, Jun. 1996.
Cluet, S. et al, On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Proceedings of the Fifth International Conference on Database Theory, pp. 54-67, Jan. 1995.
Galindo-Legaria, C., Uniformly-Distributed Random Generation of Join Orders, Proceedings of the International Conference on Database Theory, pp. 280-293, Jan. 1995.
Galindo-Legaria, C. et al, Fast, Randomized Join-order Selection—Why Use Transformations?, Proceedings of the International Conference on Very Large Data Bases, pp. 85-95, Sep. 1994.
Swami, A. et al, A Polynomial Time Algorithm for Optimizing Join Queries, Proceedings of the IEEE Conference of Data Engineering, pp. 345-354, Apr. 1993.
Ono, K. et al, Measuring the Complexity of Join Enumeration in Query Optimization, Proceedings of the 16th International Conference on Very Large Data Bases, pp. 314-325, Aug. 1990.
Ioannidis, Y.E. et al, Randomized Algorithms for Optimizing Large Join Queries, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 312-321, Apr. 1990.
Swami, A., Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 367-376, May 1989.
Swami, A. et al, Optimization of Large Join Queries, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 8-17, May 1988.
Krishnamurthy, R. et al, Optimization of Non-recursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, pp. 128-137, Aug. 1986.
Ibaraki, T. et al, On the Optimal Nesting Order for Computing N-Relational Joins, ACM Transaction on Database Systems, vol. 9: pp. 482-502, Sep. 1984.
Selinger, P.G. et al, Access Path Selection in a Relational Database Management System, Proceedings of ACM SIGMOD Conference of Management of Data, pp. 23-34, May 1979.
Wong, E. et al, Decomposition—a Strategy for Query Processing, ACM Transaction on Database Systems, 1(3): pp. 223-241, Sep. 1976.
Ly Cheyne D
Riddle G. Mack
Smart John A.
Sybase Inc.
LandOfFree
Database system with methodology for generating bushy nested... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system with methodology for generating bushy nested..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with methodology for generating bushy nested... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2642915