Effecting constraint magic rewriting on a query with the multiset version of the relational algebric theta-semijoin operator

Patent 6061676 Issued on May 9, 2000. Estimated Expiration Date:

May 23, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

System for optimizing correlated SQL queries in a relational database using magic decorrelation
Patent #: 5548755
Issued on: 08/20/1996
Inventor: Leung, et al.

Enumerating projections in SQL queries containing outer and full outer joins in the presence of inner joins
Patent #: 5687362
Issued on: 11/11/1997
Inventor: Bhargava, et al.

Reducing query response time using tree balancing
Patent #: 5694591
Issued on: 12/02/1997
Inventor: Du, et al.

Simplification of SQL queries using generalized inference propagation and generalized transitive closure
Patent #: 5701454
Issued on: 12/23/1997
Inventor: Bhargava, et al.

Reordering of complex SQL queries involving GROUPBYs, joins, outer joins and full outer joins Patent #: 5713015
Issued on: 01/27/1998
Inventor: Goel, et al.

Inventors

Application

No. 862906 filed on 05/23/1997

US Classes:

707/3, Query processing (i.e., searching)707/2, Access augmentation or optimizing707/4, Query formulation, input preparation, or translation707/5Query augmenting and refining (e.g., inexact access)

Examiners

Primary: Amsbury, Wayne
Assistant: Channavajjala, Srirama

Attorney, Agent or Firm

Monteleone; Geraldine

International Class

G06F 017/30

Abstract

An equivalence rule having the multiset version of the relational algebraic theta-semijoin operator is used in effectuating Constraint Magic rewriting on a computer programming language query having non-equality, as well as equality, predicates. In particular, the rule effectuates Constraint Magic rewriting for a single join. When applied repeatedly on a sequence of joins, Constraint Magic rewriting is effectuated for a single block query. The rule may be used to generate relational algebraic expressions to optimize or determine the equivalency of queries. Cost estimates for alternative ways of evaluating a complex query can be efficiently computed. Based on these computed cost estimates, the least costly implementation of a complex query is determined.

Other References

Implementation of Magic-sets in a Relational Database System, I.S. Mumick and H.Pirahesh, SIGMOD Record, vol. 23, Issue 2, Jun. 1994, pp. 103-114
Query Optimization by Predicate Move-Around, A. Y. Levy, I.S. Mumick, Y. Sagiv, Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994, pp. 96-107
Magic is Relevant, I.S. Mumick, S.J. Finkelstein, H.Pirahesh, R.Ramakrishnan, SIGMOD Record, vol. 19, Issue 2, Jun. 1990, pp. 247-258
Complex Query Decorrelation, P. Seshardri, H. Pirahesh, T.Y.C. Leung, Proceedings -12th Int'l Conference on Data Engineering sponsored by IEEE Computer Society Technical Committee on Data Engineering, vol. SE-11, No. 4, Apr. 1985, pp. 324-345
Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries, S. Ceri and G. Gottlob, IEEE Transactions on Software Engineering, vol. SE-11, No. 4, Apr. 1985, pp. 324-345
Compiling Query Constraints, P.J. Stuckey and S. Sudarshan, SIGMOD/PODS 94--May 1994, Minneapolis, MN, USA, 1994 ACM 0-89791-639-5/94/0005, pp. 56-67
Query Porcessing in a System for Distributed Databases (SDD-1), P.A. Bernstein, N. Goodman, E. Wong, C.L. Reeve and J.B. Rothnie, Jr., ACM Transactions on Database Systems, vol. 6, No. 4, Dec. 1981, pp. 602-625
Space/Time Trade-offs in Hash Coding with Allowable Errors, B.H. Bloom, Communications of the ACM, vol. 13, No. 7, Jul. 1970, pp. 422-426
Optimization of Nonrecursive Queries, R. Krishnamurthy, H. Boral, C. Zaniolo, Proceedings of the 12th Int'l Conf. on Very Large Data Bases, Kyoto, Aug. 1986, pp. 128-137
Inderpal Singh Mumick et al., Magic is Relevant, SIGMOD Record, vol. 19, Issue 2, and 247-258, Jun. 1990
Stefano Ceri et al. Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries, IEEE 1985, 324-345, Apr. 4, 1985
Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates and Quantifiers, Proceedings of the 13th VLDB Conference, Brighton 1987, 197-208, Sep. 4, 1987
C J Date, An Introduction to Database Systems, Text Book, Chap 6, p. 154 [sixth edition, 1995
Inderpal Singh Mumick et al., Implementation of Magic-sets in a Relational Database System, SIGMOD RECORD, vol. 23, Issue 2, 103-114, Jun. 199