Simplification of SQL queries using generalized inference propag

Details Simplification of SQL queries using generalized inference propag Simplification of SQL queries using generalized inference propag

1995-01-17

1997-12-23

Black, Thomas G.

G06F 1730

Patent

active

057014540

ABSTRACT:
A method and apparatus for query simplification by applying generalization inference propagation and transitive closure in SQL queries having intersection operations combined with inner and outer join operations further combined with selection and/or projection operations. First a strong set of predicates is calculated, typically a selection or join predicate which is null-intolerant. Second the strong set of attributes is used to select and replace a full, left, or right outer join operation found as the operand of an intersection operation in the query. A less expensive outer or inner join replaces the selected join and the process is repeated until no further simplification if possible. Inferences are propagated from one operand to the other of an intersection operation. Selection operators are applied through transitive closure to reduce the size of intermediate results. The transformations are applied to the query to produces a set of operations that perform more efficiently than that of the original query while providing the same results.

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.
APERS, "Optimization Algorithms for Distributed Queries", IEEE Transactions on Software Engineering, vol. SE9, No. 1, Jan. 1983, pp. 57-68.
Lohman et al., "Research Report--Query Processing in R*", IBM Research Laboratory, San Jose, CA (US) IBM Research Division, Apr. 1984, pp. 1-33.
Lafortune et al., "A State Transition Model for Distributed Query Processing", University of California, ACM transactions on Database Systems, vol. 11, No. 3, Sep. 1986 (294-322).
Kim, Won, IBM Research "On Optimizing an SQL-Like Nested Query", ACM Transactions on Database Systems, vol. 7, No. 3, Sep. 1982, pp. 443-469.
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., "Relational Database Management" Relational Database Writings 1989-1991, Part II, pp. 133-154.
Selinger et al, "Access Path Selection in a Relational Database Management System", IBM Research Division, San Jose, CA (US), ACM, 1979, pp. 23-34.
Dayal et al., "An Extended Relational Algebra with Control Over Duplicate Elimination", Computer Corporation of America, Cambridge, MA, (US), ACM 1982, pp. 117-123.
Galindo-Legaria, C., and Rosenthan, 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 Optimization of Outerjoin Queries", Ph.D. dissertation, Center for Research in Computing Technology, Harvard University, Cambridge, MA, 1992.
Alon Levy, Inderpal Mumick, Yehoshua Sagiv, "Query Optimization by Predicate Move-Around," Proceedings of the 20th VLDB Conference, Santiago, Chile, Sep., 1994.
Paulley, G.N. and Per-Ake Larson, "Exploiting Uniqueness in Query Optimization", CASCON, pp. 804-822, vol. II, Oct. 1993.
Pirahest, H., Hellerstein, J.M. and Hasan, W. "Extensible/Rule Based Query Rewrite Optimization in Starburst", ACM SIGMOD, pp. 39-48, San Diego, CA, Jun. 1992.
Date, C.J. "The Outer Join", Proceedings of the Second International Conference on Databases, Cambridge, England, Sep. 1983, pp. 76-106.
Dayal, Umeshwar, "Processing Queries with Quantifiers: A Horticultural Approach", Proc. 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.
Rosenthal, A. and Galindo-Legaria, C., "Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins", ACM SIGMOD, pp. 291-299, 1990.

Affiliated with

Also associated with

Rating

Simplification of SQL queries using generalized inference propag does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Simplification of SQL queries using generalized inference propag, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplification of SQL queries using generalized inference propag will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1807909