Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2005-09-27
2010-10-12
Breene, John E (Department: 2162)
Data processing: database and file management or data structures
Database and file access
Query optimization
C707S718000, C707S719000
Reexamination Certificate
active
07814091
ABSTRACT:
Various techniques are described for processing database commands that include MINUS and/or INTERSECT operators. The queries containing the MINUS and/or INTERSECT operators are transformed to create a plurality of transformed queries. Each of the transformed queries produces the same result as the original query, but does not include the MINUS and/or INTERSECT operator. To achieve the same result set as the original query, the transformed queries employ equijoins, antijoins, and/or semijoins, and duplicate elimination operations. Costs are estimated for each of the various transformed queries. Based on the cost estimates, one of the transformed queries is selected as the query that is to be executed to perform the operations specified in the original query.
REFERENCES:
patent: 5412804 (1995-05-01), Krishna
patent: 5437032 (1995-07-01), Wolf et al.
patent: 5495605 (1996-02-01), Cadot
patent: 5548755 (1996-08-01), Leung et al.
patent: 5588150 (1996-12-01), Lin et al.
patent: 5590319 (1996-12-01), Cohen et al.
patent: 5590324 (1996-12-01), Leung et al.
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5797136 (1998-08-01), Boyer et al.
patent: 5822748 (1998-10-01), Cohen et al.
patent: 5832477 (1998-11-01), Bhargava et al.
patent: 5905981 (1999-05-01), Lawler
patent: 5924088 (1999-07-01), Jakobsson et al.
patent: 5963932 (1999-10-01), Jakobsson et al.
patent: 5963959 (1999-10-01), Sun et al.
patent: 5974408 (1999-10-01), Cohen et al.
patent: 6026394 (2000-02-01), Tsuchida et al.
patent: 6032143 (2000-02-01), Leung et al.
patent: 6061676 (2000-05-01), Srivastava et al.
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6298342 (2001-10-01), Graefe et al.
patent: 6339768 (2002-01-01), Leung et al.
patent: 6370524 (2002-04-01), Witkowski
patent: 6510422 (2003-01-01), Galindo-Legaria et al.
patent: 6529896 (2003-03-01), Leung et al.
patent: 6529901 (2003-03-01), Chaudhuri et al.
patent: 6535874 (2003-03-01), Purcell
patent: 6622138 (2003-09-01), Bellamkonda et al.
patent: 6694306 (2004-02-01), Nishizawa et al.
patent: 6792420 (2004-09-01), Stephen Chen et al.
patent: 6801905 (2004-10-01), Andrei
patent: 6934699 (2005-08-01), Haas et al.
patent: 7031956 (2006-04-01), Lee et al.
patent: 7089225 (2006-08-01), Li et al.
patent: 7111020 (2006-09-01), Gupta et al.
patent: 7146360 (2006-12-01), Allen et al.
patent: 7158994 (2007-01-01), Smith et al.
patent: 7167852 (2007-01-01), Ahmed et al.
patent: 7246108 (2007-07-01), Ahmed
patent: 7440935 (2008-10-01), Day et al.
patent: 2001/0047372 (2001-11-01), Gorelik et al.
patent: 2003/0055814 (2003-03-01), Chen et al.
patent: 2003/0120825 (2003-06-01), Avvari et al.
patent: 2004/0148278 (2004-07-01), Milo et al.
patent: 2004/0167904 (2004-08-01), Wen et al.
patent: 2004/0220911 (2004-11-01), Zuzarte et al.
patent: 2004/0220923 (2004-11-01), Nica
patent: 2004/0267760 (2004-12-01), Brundage et al.
patent: 2005/0033730 (2005-02-01), Chaudhuri et al.
patent: 2005/0055382 (2005-03-01), Ferrat et al.
patent: 2005/0076018 (2005-04-01), Neidecker-Lutz
patent: 2005/0149584 (2005-07-01), Bourbonnais et al.
patent: 2005/0187917 (2005-08-01), Lawande et al.
patent: 2005/0198013 (2005-09-01), Cunningham et al.
patent: 2005/0210010 (2005-09-01), Larson et al.
patent: 2005/0234965 (2005-10-01), Rozenshtein et al.
patent: 2005/0283471 (2005-12-01), Ahmed
patent: 2005/0289125 (2005-12-01), Liu et al.
patent: 2006/0167865 (2006-07-01), Andrei
patent: 2007/0027880 (2007-02-01), Dettinger et al.
patent: 2007/0073643 (2007-03-01), Ghosh et al.
Kemp et al. “Improving Federated Database Queries Using Declarative Rewrite Rules for Quantified Subqueries”, Journal of Intelligent Information Systems, Dec. 2001. vol. 17,Iss.2-3;p. 281. Download: http://proquest.umi.com/pqdlink?Ver=1&Exp=04-11-2015&FMT=7&DID=352547461&RQT=309&cfc=1.
Mistry et al, “Materialized View Selection and Maintenance Using Multi-Query Optimization,” IIT-Bombay Bell Labs Univ. of Massachusetts-Amherst (Jun. 2001).
Chaudhuri, Surajit et al., “Including Group-By in Query Optimization,” Proceedings of the 20thVLDB Conference—1994, pp. 354-366.
Galindo-Legaria, Cesar et al., “Outerjoin Simplification and Reordering for Query Optimization,” ACM Transactions on Database Systems, vol. 22, No. 1, Mar. 1997, pp. 43-74.
Erickson, Gail et al., “Improving Performance with SQL Server 2000 Indexed Views,” Microsoft TechNet, Sep. 2000, located on the internet at http://www.microsoft.com/technet/prodtechnol/sql/2000/maintain/indexvw.mspx?pf=true, retrieved on Nov. 11, 2006, 14 pages.
Mishra, Priti et al., “Join Processing in Relational Databases,” ACM Computing Surveys, vol. 24, No. 1, Mar. 1992, pp. 63-113.
Muralikrishna, M. “Improved Unnesting Algorithms for Join Aggregate SQL Queries,”, Proceedings of the 18thVLDB Conference—1992, pp. 91-102.
Seshadri, Preveen, “Cost-Based Optimization for Magic: Algebra and Implementation,” SIGMOND '96, 1996 ACM 0-89791-794-4, pp. 435-446.
Deutsch, Alin et al., “Minimization and Group-By Detection for Nested XQueries”, University of California, San Diego, 2003, 15 pages.
Dehaan, David, “A Rewriting Algorithm for Multi-Block Aggregation Queries and Views using Prerequisites and Compensations”, University of Waterloo, Canada, Technical Report CS-2004-25, May 3, 2004, 39 pages.
Chaudhuri, Surajit, “An Overview of Query Optimization in Relational Systems”, Microsoft Research, 1998, 10 pages.
Muralikrishna, M., “Improved Unnesting Algorithms for Join Aggregate SQL Queries”, VLDB Conference, Canada, 1992, 12 pages.
Hayu, John, “Analytic SQL Features in Oracle9i”, An Oracle Technical White Paper, Dec. 2001, 32 pages.
Oracle, “Optimizer Modes, Plans Stability, and Hints”, Oracle8i Tuning Release 8.1.5 A67775-01, Oracle Website, 1999, 54 pages.
Ahmed, Rafi et al., “Cost-based Query Transformation in Oracle,” VLDB 2006, Seoul, Korea, Copyright 2006 VLSB Endowment, ACM 1-59593-385, pp. 1026-1036.
George Lumpkin, Hakan Jakobsson, “Query Optimization in Oracle9i,” Oracle Corporation, Oracle White Paper, Feb. 2002, pp. 1-30.
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan, “Extensible/Rule Base Query Rewrite Optimization in Starburst,” IBM Almaden Research Center, pp. 1-10.
Umeshwar Dayal, “Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nest Subqueries, Aggregates and Quantifiers,” Proceedings of the 13thVLDB Conference, Brighton 1987, pp. 197-208.
P. Griffiths Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T.G. Price, “Access Path Selection in a Relational Database Management System,” Proceedings of the 1979 ACM SIGMOD International Conference on the Management of Data, 1979, pp. 23-34.
Chen, et al., “View Merging in the Context of View Selection Changing,” Database Engineering and Applications Symposium 2002, Proceedings, Jul. 2002, 10 pages.
Priti, Patil et al., “Holistic Schema Mappings for XML-on-RDBMS,” Database systems for advanced applications, vol. 3882, Lecture notes in Computer Science, Springer-Verlag, Jan. 1, 2006, 16 pages.
Hammerschmidt, B C et al., “Autonomous Index Optimization in XML Databases,” 21stInternational Conference on Data Engineering, XP010924124, IEEE, Apr. 5, 2005, 10 pages.
European Patent Office, “International Search Report,” PCT/US2008/052932, dated Jun. 13, 2008, 13 pages.
Claims, PCT/US2008/052932, 4 pages.
Oracle, “Oracle® Enterprise Manager,” Part A96673-02, Oct. 2002, Chapters 1-4, 439 pages.
Oracle, “Oracle® Enterprise Manager,” Part A96673-02, Oct. 2002, Chapters 5-Appendix H, 394 pages.
Fitzgerald et al., “Special Edition Using Crystal Reports IO,” Que, Chapters 23, 24, 27, 35, Appendix A, Jul. 14, 2004, 170 pages.
Rankins et al., “Microsoft SQL Server 2000 Unleashed,” Second Edition, Sams, Cha
Ahmed Rafi
Baer Hermann
Ghosh Bhaskar
Breene John E
Hickman Brian D.
Hickman Palermo & Truong & Becker LLP
Jami Hares
Oracle International Corporation
LandOfFree
Multi-tiered query processing techniques for minus and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-tiered query processing techniques for minus and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-tiered query processing techniques for minus and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4226816