Effecting constraint magic rewriting on a query with the multise

Details Effecting constraint magic rewriting on a query with the multise Effecting constraint magic rewriting on a query with the multise

1997-05-23

2000-05-09

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 707 4, 707 5, G06F 1730

Patent

active

060616768

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.

REFERENCES:
patent: 5548755 (1996-08-01), Leung et al.
patent: 5687362 (1997-11-01), Bhargava et al.
patent: 5694591 (1997-12-01), Du et al.
patent: 5701454 (1997-12-01), Bhargava et al.
patent: 5713015 (1998-01-01), Goel et al.
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. 1994.

Affiliated with

Also associated with

Rating

Effecting constraint magic rewriting on a query with the multise does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Effecting constraint magic rewriting on a query with the multise, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Effecting constraint magic rewriting on a query with the multise will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1074646