Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-10-10
2006-10-10
Coby, Frantz (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
07120623
ABSTRACT:
Methods of optimizing access to a relation queried through a number of predicates. The methods identify one or more candidate predicates of the selection condition that can be used to factorize the selection condition. A gain from using one or more of the candidate predicates to factorize the selection condition is computed. One or more of the candidate predicates that result in a positive gain are factored from the selection condition to produce a rewritten selection condition. The candidate predicates can be predicates that appear exactly in the selection condition more than once and/or merged predicates that may be predicates in the selection condition that overlap.
REFERENCES:
patent: 6629095 (2003-09-01), Wagstaff et al.
patent: 6665664 (2003-12-01), Paulley et al.
patent: 6804669 (2004-10-01), Aggarwal
R.K. Brayton. Factoring Logic Functions. IBM Journal of Research and Development, vol. 31, No. 2, pp. 187-198, Mar. 1987.
R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli and A. Wang. MIS: A Multiple-Level Logic Optimization System. IEEE Transactions on CAD, vol. CAD-6, No. 6, Nov. 1987, pp. 1062-1081.
Sophie Cluet and Claude Delobel. A General Framework for the Optimization of Object-Oriented Queries. Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, CA, pp. 383-392, 1992.
Surajit Chaudhuri and Luis Gravano. Optimizing Queries Over Multimedia Repositories. Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, pp. 91-102, 1996.
Surajit Chaudhuri and Kyuseok Shim. Optimization of Queries with User-Defined Predicates. In VLDB '96, Proceedings of 22ndInternational Conference on Very Large Data Bases, Sep. 3-6, 1996, Mumbai (Bombay), India, pp. 87-98, 1996.
Umeshwar Dayal. Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates, and Quantifiers. Proceedings of 13thInternational Conference on Very Large Data Bases, Brighton, England, pp. 197-208, 1987.
Joseph M. Hellerstein and Michael Stonebraker. Predicate Migration: Optimizing Queries with Expensive Predicates. In SIGMOD Conference, pp. 267-276, 1993.
Alfons Kemper, Guido Moerkotte and Michael Steinbrunn. Optimizing Boolean Expressions in Object-Bases. In Proceedings of the VLDB Conference, pp. 79-90, Vancouver, Canada, Aug. 1992.
M.C. Golumbic and A. Mintz. Factoring Logic Functions Using Graph Partitioning. In Proc. IEEE/ACM International Conference on Computer-Aided Design, (ICCAD-99), San Jose, CA pp. 195-198, 1999.
M. Muralikrishna and David J. DeWitt. Optimization of Multiple-Relation Multiple-Disjunct Queries. In Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Austin, TX pp. 263-275, 1988.
C. Mohan, D. Haderle, Y. Wang and J. Cheng. Single Table Access Using Multiple Indexes: Optimization, Execution and Concurrency Control Techniques. In Proceedings International Conference on Extending Database Technology, pp. 29-43, 1990.
R. Brayton, G. Hachtel and A.L. Sangiovanni-Vincentelli. Multilevel Logic Synthesis. Proceedings of the IEEE, vol. 78, No. 2, pp. 264-300, Feb. 1990.
Lewis T. Reinwald and Richard M. Soland. Conversion of Limited-Entry Decision Tables to Optimal Computer Programs: Minimum Average Processing Time. JACM, vol. 13, No. 3, pp. 339-358, Jul. 1966.
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie and Thomas G. Price. Access Path Selection in a Relational Database Management System. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, pp. 23-34, 1979.
Guido Moerkotte, Wolfgang Scheufele. Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections. In Proceedings of the 6thInternational Conference on Extending Database Technology (EDBT), Valencia, Spain, pp. 201-215, 1998.
Chaudhuri Surajit
Ganesan Prasana
Coby Frantz
Microsoft Corporation
Nguyen Cam-Linh
LandOfFree
Optimizing multi-predicate selections on a relation using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimizing multi-predicate selections on a relation using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing multi-predicate selections on a relation using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3691258