Query optimization with deferred update and autonomous sources

Details Query optimization with deferred update and autonomous sources Query optimization with deferred update and autonomous sources

1998-11-16

2001-09-04

Black, Thomas (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C709S217000

Reexamination Certificate

active

06285997

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to computer-implemented database systems, and, in particular, to query optimization with deferred updates and autonomous sources.
2. Description of Related Art
Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. Relational databases are organized into tables which consist of rows and columns of data. The rows are formally called tuples or records. A database will typically have many tables and each table will typically have multiple tuples and multiple columns. The tables are typically stored on direct access storage devices (DASD), such as magnetic or optical disk drives for semi-permanent storage.
The integration of object technology and database systems has been an active area of research for the past decade. One important aspect of the integration of these two technologies is the provision of efficient, declarative query interfaces for accessing and manipulating object data. Compared to other aspects of object-oriented database (“OODB”) technology, such as integrating persistence into object-oriented languages (e.g., C++ and Smalltalk), queries were given relatively little attention in the early days of OODB research, which is further described in Mike Stonebraker,
Third
-
Generation Data Base System Manifesto
, Computer Standards & Interfaces, Dec. 12, 1991, which is incorporated by reference herein. In Won Kim,
Object
-
Oriented Database Systems: Promise, Reality, and Future
, Proc. 19th International Conference on Very Large Data Bases, Dublin, August 1993, which is incorporated by reference herein, it is pointed out that commercial OODB systems are weak in this regard.
However, a number of proposals for OODB query languages have appeared in the database literature. See Mike Carey, David DeWitt, and Scott Vandenberg,
A Data Model and Query Language for EXODUS
, Proc. ACM-SIGMOD International Conference on Management of Data, Chicago, June 1988; Won Kim,
A Model of Queries For Object
-
Oriented Databases
, Proc. 15th International Conference on Very Large Data Bases, Amsterdam, August 1989; Francois Bancilhon, S. Cluet, and C. Delobel A,
Query Language for the O
2
Object
-
Oriented Database System
, edited by Richard Hull, Ron Morrison, and David Stemple, Proc. 2nd International Workshop on Database Programming Languages, Gleneden Beach, Morgan-Kaufmann Publishers, Inc., June 1989 [hereinafter “Bancilhon et al.”]; Jack Orenstein, Sam Haradhvala, Benson Margulies, and Don Sakahara,
Query Processing in the ObjectStore Database System
, Proc. ACM-SIGMOD International Conference on Management of Data, San Diego, June 1992, [hereinafter “Orenstein et al.”]; S. Dar, N. Gehani, and H. Jagadish,
CQL++: A SQL for a C++ Based Object
-
Oriented DBMS
, Proc. International Conference on Extending Data Base Technology, Advances in Database Technology—EDBT '92, Lecture Notes in Computer Science, Vienna, Springer-Verlag, 1992; Michael Kifer, Won Kim, and Yehoshua Sagiv,
Querying Object
-
Oriented Databases
, Proc. ACM-SIGMOD International Conference on Management of Data, San Diego, June 1992; Tom Atwood, Joshua Duhl, Guy Ferran, Mary Loomis, and Drew Wade,
Object Query Language
, edited by R. G. G. Cattell, Object Database Standards: ODMG—93 Release 1.1 Morgan-Kaufmann Publishers, Inc., 1993, [hereinafter “Atwood et al.”]; José Blakeley, William J. McKenna, and Goetz Graefe, Experiences Building The Open OODB Query Optimizer, Proc. ACM-SIGMOD International Conference on Management of Data, Washington D.C., May 1993; each of which is incorporated by reference herein. While proposals outnumber actual implementations, several of these language designs have indeed been implemented as the query interfaces for significant commercial OODB products, which is discussed in Bancilhon et al. and Orenstein et al.
The commercial OODB systems that are generally considered to have good object query facilities, O2, which is discussed in Bancilhon et al., and ObjectStore, which is discussed in Orenstein et al., each provide their own flavor of object query language. ObjectStore's query language is an extension to the expression syntax of C++. O2's query language is generally more like SQL and has been adapted into a proposed OODB query language standard (i.e., the ODMG-93 proposal) by a consortium of OODB system vendors, which is discussed in Atwood et al., but it differs from SQL in a number of respects, which is discussed further in Won Kim,
Observations on the ODMG
-93
Proposal
, ACM SIGMOD Record, 213(1), March 1994, which is incorporated by reference herein.
Query rewrite transformations have been developed for relational DBMSs. See Hamid Pirahesh, Joseph M. Hellerstein, and Waqar Hasan,
Extensible/Rule Based Query Rewrite Optimization in Starburst
, Proc. ACM-SIGMOD International Conference on Management of Data, San Diego, June 1992; Inderpal Singh Mumich, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan,
Magic is Relevant
, Proc. ACM-SIGMOD International Conference on Management of Data, pages 247-258, Atlantic City, May 1990; Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan,
The Magic of Duplicates and Aggregates
, Proc. 16th International Conference on Very Large Data Bases, Brisbane, August 1990; each of which is incorporated by reference herein.
Many of these transformations also apply for Object Query Systems. However, new query rewrite transformations that apply specifically to Object Query Systems need to be developed, as discussed in Sophie Cluet and Claude Delobel,
A General Framework for the Optimization of Object
-
Oriented Queries
, Proc. ACM-SIGMOD International Conference on Management of Data, San Diego, June 1992, which is incorporated by reference herein. Predicate pushdown, which is a query rewrite transformation, is the notion of taking a query and determining which parts of the query can be migrated through the layers of the schema to the databases where the data resides. The objective is to use the power of the database query function to do data filtering, and, thereby, restrict the amounts of data that have to be transferred from the database servers to clients.
Predicate pushdown can include all of the predicates that define a query's result, in which case the task of restricting the result set is entirely performed by the databases where the data resides. Predicate pushdown can include partial predicates that define a query's results, in which case some of the predicates (e.g., a subset of the conjuncts that define a query's result) are passed down to the databases where the data resides, thereby restricting the results returned by these databases. The remaining predicates that could not be pushed down are then applied in object space by the query evaluator. Finally, if predicate pushdown cannot be applied, the predicates that define a query's results must be applied in object space after having retrieved the complete sets of data referenced in the query.
Semi-join techniques for distributed query processing have been presented in Clement T. Yu and C. C. Chang,
Distributed Query Processing
, ACM Computing Surveys, 16(4):399-433, December 1984, [hereinafter “Yu et al.”], which is incorporated by reference herein. Similarly, to join queries, semi-join queries involve multiple tables and have predicates that establish a relationship among the tables participating in a query. However, only a subset of the tables are referenced in the projection clause of a semi-join query.
The following optimization is presented in Yu et al. Given two remote tables T
1
and T
2
participating in a join, if each table is managed by a different remote DBMS, results corresponding to table T
i
are first retrieved. Results corresponding to a table T
j
, j≠i are then retrieved by sel

Affiliated with

Also associated with

Rating

Query optimization with deferred update and autonomous sources does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Query optimization with deferred update and autonomous sources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query optimization with deferred update and autonomous sources will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2444487