Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-08-31
2001-05-29
Black, Thomas (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06240406
ABSTRACT:
I. BACKGROUND OF THE INVENTION
The present invention relates generally to database queries and more specifically to aggregate queries.
The design of database query languages has started to benefit from advances in general programming language design. For example, SQL, a common query language, has adopted more referential transparency and compositionality, especially in the versions used for object-relational databases. In addition, a rich and challenging standard language, OQL, has been proposed for object-oriented databases.
As demands for information have become more complex, and as the sizes of databases has increased, queries have become correspondingly complex. Traditional query language compilers directly translate queries written in source language into query execution plans that are then executes against the databases of interest. Doing so often creates plans that consume massive amounts of memory and occupy large amounts of I/O resources. Also, complex queries often require construction of intermediate data structures, which further consumes memory.
The increasing sizes of many databases have made many queries unfeasible without some sort of optimization. Although most compilers for general-purpose programming languages perform some optimizing, they do not generally perform such optimizing for database queries. Moreover, these optimizations are not sound if programs are allowed to diverge or have side-effects. In addition, although some database query language compilers perform optimization, they do not do so for aggregates or conversions, two important functions described in detail below.
II. SUMMARY OF THE INVENTION
To address this deficiency, methods and apparatus consistent with this invention apply certain transformation rules on selected aggregates and conversions to produce a query that is more efficient.
Specifically, a method of optimizing an aggregate query of a database consistent with this invention comprises translating the query into an internal language; identifying in the translated query candidates for optimization; and applying a set of optimization rules to the identified candidates to form a transformed query.
A computer system for optimizing an aggregate query of a database consistent with this invention comprises compiler means for translating the query into an internal language; means for identifying in the translated query candidates for optimization; and means for applying a set of optimization rules to the identified candidates to form a transformed query.
Both the foregoing general description and the following detailed description are exemplary and explanatory only and do not restrict the invention claimed. The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate some systems and methods consistent with the invention and, together with the description, explain the principles of the invention.
REFERENCES:
patent: 5313575 (1994-05-01), Beethe
patent: 5325465 (1994-06-01), Hung et al.
patent: 5412718 (1995-05-01), Narasimhalu et al.
patent: 5428737 (1995-06-01), Li et al.
patent: 5442778 (1995-08-01), Pedersen et al.
patent: 5487132 (1996-01-01), Cheng
patent: 5487141 (1996-01-01), Cain et al.
patent: 5590324 (1996-12-01), Leung et al.
patent: 5701466 (1997-12-01), Yong et al.
patent: 5727158 (1998-03-01), Bouziane et al.
patent: 5749079 (1998-05-01), Yong et al.
patent: 5751962 (1998-05-01), Fanshier et al.
patent: 5761493 (1998-06-01), Blakeley et al.
patent: 5774692 (1998-06-01), Boyer et al.
patent: 5819255 (1998-10-01), Celis et al.
patent: 6006214 (1999-12-01), Carey et al.
patent: 6021405 (2000-02-01), Celis et al.
Dynamic optimization of index scans restricted by booleans by Genneady Antoshenkov, Oracle Corporation, pp. 430-440, Feb. 1996.*
The Microsoft relational engine by G. Graefe, Microsoft Corp. Redmond, WA, pp. 1-2, Mar. 1996.*
Lellahi, K. et al., “A Calculus for Collections and Aggregates,” Université de Paris 13, Institut Galilée, CIS Dept., Univ. of Pennsylvania, pp. 1-19. (Sep. 4-6 1997).
Davidson, S.B., et al., “BioKleisli: A Digital Library for Biomedical Researchers,” Dept. of Computer Information Science & Dept. of Genetics, Univ. of Pennsylvania, Institute of Systems Science, Heng Mui Keng Terrace, Singapore, pp. 1-10, Aug. 12, 1996.
“CBIL bioWidgets for Java,” Univ. of Pennsylvania, bioWidgets, pp. 1-9. (1998).
Wong, Limsoon Dr., “The Kleisli System,” Kent Ridge Digital Laboratories, 21 Hen Mui Keng Terrace, Singapore, pp. 1-4. (Sep. 20, 1998).
Wong, Limsoon Dr., Strategy of the Kleisli Project, Kent Ridge Digital Laboratories, 21 Heng Mui Keng Terrace, Singapore, pp. 1-4. (Aug. 20, 1998).
Fanshier, S. R. et al., “Object-based Systems Management of Computer Networks,” Abstract No. 5751962, www.patents.ibm.com., pp. 1-2. (Dec. 13, 1995).
Beethe, D.C., “Processing Method for An Iconic Programming System,” Abstract No. 5313575, www.patents.ibm.com., pp. 1-3. (May 14, 1993).
Fah, Low Kwee, et al, “KRDL—Press Releases,” Jointly issued by KRDL, NUS, and NTU., pp. 1-3, 1-3. 1-3, KRDL Communications, Jul. 1998.
Wong, L., “The Collection Programming Language,” Kent Ridge Digital Labs, 21 Heng Mui Keng Terrace, Singapore, pp. 1-108, Aug. 21, 1998.
Wong, L., “The Kleisli/CPL Extensible Query Optimizer,” Institute of Systems Science, Heng Mui Keng Terrace, Singapore, pp. 1-258, Apr. 16, 1996.
Wong, L., “The Kleisli Query System,” Institute of Systems Science, Heng Mui Keng Terrace, Singapore, pp. 1-258, Nov. 24, 1997.
Black Thomas
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Mizrahi Diane D.
The Trustees of the University of Pennsylvania
LandOfFree
System and method for optimizing queries with aggregates and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for optimizing queries with aggregates and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for optimizing queries with aggregates and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2435941