Optimization of queries using relational algebraic theta-semijoi

Details Optimization of queries using relational algebraic theta-semijoi Optimization of queries using relational algebraic theta-semijoi

1997-05-23

2000-02-29

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

06032144&

ABSTRACT:
A collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator is used to generate relational algebraic expressions equivalent to a computer programming language query. These expressions may be employed as a search space which is utilized by, for example, optimizing software or software that determines the equivalency of queries. Cost formulas for the multiset version of the theta-semijoin operator may be used in computing cost estimates for the generated expressions. Based on these computed cost estimates, the least costly implementation of a complex query is determined. Thus, queries are cost-based optimized on both a local and global basis by use of the relational algebraic theta-semijoin operator.

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. Seshadri, H. Pirahesh, T.Y.C. Leung, Proceedings--12th Int'l Conference on Data Engineering sponsored by IEEE Computer Society Technical Committeee on Data Engineering, pp. 450-458.
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 - 5/94, 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.
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 of Database Systems, Text Book, Chap 6, p. 154 [sixth edition], 1995.
Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, U. Dayal, Proceedings of the 13th VLDB Conference, Brighton 1987, pp.197-208.

Affiliated with

Also associated with

Rating

Optimization of queries using relational algebraic theta-semijoi does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization of queries using relational algebraic theta-semijoi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of queries using relational algebraic theta-semijoi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-692216