Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-12-04
1999-12-21
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707103, G06F 1730
Patent
active
060062142
ABSTRACT:
The system, method, and program of this invention, referred to herein as nest elimination, performs query rewrite transformations, within a database management system (DBMS), for a certain class of object queries over views that involve derived nested sets. The nest elimination algorithm uses query rewriting to avoid computing these nested sets in certain common cases. For each quantifier in a query (if the quantifier is defined over a nested set that is a part of a view or if the quantifier is implemented by a subquery that projects a NEST aggregate) the following functions are performed: a) resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; b) adding a null testing predicate to the rewritten database query; c) adding quantifiers defined within the nest subquery to the rewritten database query; d) adding predicates from the nest subquery of the view to the rewritten database query; and e) rewriting each expression involving a quantifier over an instance into a path expression. The resulting rewritten query is then further processed by the DBMS such as through a query optimizer, etc. By avoiding nested set computations for a certain class of queries, the rewritten query can result in improved processing performance.
REFERENCES:
patent: 5659725 (1997-08-01), Levy et al.
patent: 5713015 (1998-01-01), Goel et al.
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5774692 (1995-10-01), Boyer et al.
"Performing Group-By before Join," Yan et al., Proceedings o fteh 10th International Conference on Data Engineering, USA, pp. 89-100, IEEE, Feb. 1994.
The Committee for Advanced DBMS Function. "Third-Generation Database System Manifesto", SIGMOD Record, vol. 19, No. 3, Sep. 1990, pp. 31-44.
Kim, W., "Object-Oriented Database Systems: Promises, Reality, and Future", Proceedings of the 19.sup.th International Conference on Very Large Data Bases, Aug. 24-27, 1993, Dublin, Ireland; Agrawal, R. et al., Editors; pp. 676-687.
Carey, M.J. et al., A Data Model and Query Language for EXODUS', Proceedings SIGMOD International Conference on Management of Data, Chicago, Illinois, Jun. 1-3, 1988, ACM Press, SIGMOD Record, vol. 17, No. 3, Sep. 1988, pp. 413-423.
Kim, W., "A Model of Queries for Object-Oriented Databases", Proceedings of the Fifteenth International Conference on Very Large Data Bases, Aug. 22-25, 1989, Amsterdam. The Netherlands; Apers, P.M.G. et al., Editors; pp. 423-432.
Bancilhon, F. et al., "A Query Language for the O.sub.2 Object-Oriented Database System", Proceedings of the 2.sup.nd International Workshop on Database Programming Languages, Gleneden Beach, Oregon, 1989; Hull, R. et al., Editors; 1990 Morgan Kaufmann Publishers, Inc., pp. 122-138.
Orenstein, J. et al., "Query Processing in the ObjectStore Database System", Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, Jun. 2-5, 1992, SIGMOD Record, vol. 21, Issue 2, Jun. 1992; Stonebraker, M., Editor; 1992 ACM, pp. 403-412.
Dar., S. et al., "CQL++:A SQL for the Ode Object-Oriented DBMS", Proceedings of the 3.sup.rd International Conference on Extending Database Technology, Advances in Database Technology--EDBT '92; Lecture Notes in Computer Science; Vienna, Austria, Mar. 1992, Pirotte, A. et al., Editors; 1992 Springer-Verlag Berlin Heidelberg, pp. 201-216.
Kifer, M. et al, "Querying Object-Oriented Databases", Proceeding of the 1992 SIGMOD International Conference on Management of Data, San Diego, California, Jun. 2-5, 1992, SIGMOD Record, vol. 21, Issue 2, Jun., 1992; Stonebraker, M., Editor; ACM Press, pp. 393-402.
Atwood, T. et al., "Object Query Language", The Object Database Standards ODMG-93, Release 1.1; Cattell, R.G.G., Editor, 1993 Morgan Kaufmann Publishers, pp. 65-81.
Blakeley, J.A. et al., "Experiences Building the Open OODB Query Optimizer", Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, SIGMOD '93, Washington, D.C., May 26-28, 1993; Buneman, P. et al., Editors; SIGMOD Record, vol. 22, Issue 2, Jun. 1993, ACM Press, pp. 287-296.
Kim., W., "Observations on the ODMG-93 Proposal for an Object-Oriented Database Language", SIGMOD Record, vol. 23, No. 1, Mar. 1994.
Pirahesh, H. et al, "Extensible/Rule Based Query Rewrite Optimization in Starburst", Proceeding of the 1992 SIGMOD International Conference on Management of Data, San Diego, California, Jun. 2-5, 1992, SIGMOD Record, vol. 21, Issue 2, Jun., 1992; Stonebraker, M., Editor; ACM Press, pp. 39-48.
Murnick, I.S. et al., "Magic is Relevant", Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, May 23-25, 1990, Atlantic City, New Jersey; Garcia-Molina, H. et al., Editors: 1990 ACM, pp. 247-258.
Murnick, I.S. et al, "The Magic of Duplicates and Aggregates" Proceedings of the 16th International Conference on Very Large Databases, Aug. 13-16, 1990, Brisbane, Australia; McLeod, D. et al., Editors; pp. 264-277.
Cluer, S. et al., "A General Framework for the Optimization of Object-Oriented Queries", Proceedings of the 1992 SIGMOD International Conference on Management of Data, San Diego, California, Jun. 2-5, 1992, SIGMOD Record, vol. 21, Issue 2, Jun., 1992; Stonebraker, M., Editor; ACM Press, pp. 383-392.
Object Management Group, "Object Services RFP 4", OMG TC Document 94-4-18, May 11, 1994.
IBM Corporation Itasca, Objectivity, Inc., Ontos, O2, Servio, SunSoft, Inc., Sybase, Inc., and Taligent, Inc.; Joint Submission, "Object Query Service Specification", OMG TC Document 95.1.1, Jan. 4, 1995.
ISO-ANSI, Working Draft, "Information Technology-Database Language SQL", Jim Melton, Editor, International Organization for Standardization and American National Standards Institute, Jul. 1992.
Microsoft Corporation, "ODBC 2.0 Programmer's Reference and SDK Guide. The Microsoft Open Database Standard for Microsoft Windows.TM. and Windows NT.TM., Microsoft Open Database Connectivity.TM. Software Development Kit", 1992, 1993, 1994 Microsoft Press, pp. 3-30 and 41-56.
ISO Working Draft, "Database Language SQL-Part 2:Foundation (SQL/Foundation)", CD9075-2:199.chi.SQL, Sep. 11, 1997, ISO/IECJTC1/SC21N11106 - DBL:???-002, Table of Contents, Section 6.7 <field reference>, and Section 6.8 <monadic function reference>.
Kiernan, J. et al., "Extending SQL-92 for OODB Access: Design and Implementation Experience", Proceedings of the Conference on Object-Oriented Programming Systems '95, Austin, Texas, 1995 ACM, pp. 467-480.
Carey Michael J.
Kiernan Gerald George
Alam Hosain T.
Black Thomas G.
International Business Machines - Corporation
LandOfFree
Database management system, method, and program for providing qu 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 management system, method, and program for providing qu, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database management system, method, and program for providing qu will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-515897