Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-10-04
2003-04-08
Corrielus, Jean M. (Department: 2772)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06546381
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to querying databases. More specifically, the present invention relates to manners of optimizing queries in single or multiple database systems in which partially or fully replicated data exist.
2. The Relevant Technology
Two scenarios frequently occur in modern database usage. In both scenarios, multiple tables or “relations” within a single database or within different databases may exist and be available to an entity or organization. The tables in these particular instances contain partially or fully replicated information. That is, the information or “data” in the different tables may be equivalent. Additionally, the tables exhibit heterogeneous formatting, or “schemas.” That is, the information within the tables may be organized into different combinations of relations, rows, and columns, possibly with different relation names, row names, and columns. Such tables are referred to herein as being “restructuring views” of each other.
In a first scenario, the tables are naturally occurring. That is, the different tables exist for independent purposes. For instance, separate departments of an organization may individually maintain their own databases or tables within a common database, but may populate the tables or database with information from a common source. Such tables may be available to over a local network. Additionally, different databases that exhibit replicated information and heterogeneous schemas may exist at remote locations within organizations or may be maintained by different organizations and be commonly available over large scale networks such as the Internet.
In a second scenario, the tables are replicated for research purposes. A first table or “base table” is generally a naturally occurring database. The other tables are generally replicated from the first table as subsets of the first table. The replications often take the form of views. A View is a mechanism employed by the SQL language of which most databases are constructed that acts as a filter, showing only a portion of the data in the table to the user. Views, as abbreviated forms of the tables, can be searched more quickly than the full table or set of tables. A view can be created every time it is referenced, or it can be “materialized” and exist in a permanent or semi-permanent form.
Generally, when databases are replicated, as in our second scenario, they maintained through the use of materialized views. One such multiple database system (MDBS) in which materialized views are used for research and complex querying is known as a data warehouse. Various tools for managing such data warehouses exist, one example of which is IBM's DataJoiner® product.
It is a primary objective in designing database systems to expedite query servicing by optimizing the query system. The use of materialized views is one manner in which the art has approached query optimization. It is often the case that certain materialized views can be more efficiently accessed for certain types of queries while others are more efficient for other types of queries. Thus, one technique for speeding up query servicing is to maintain a plurality of materialized views and to selectively direct queries to the appropriate materialized view for which the query can be most rapidly serviced.
A further development in the art of MDBS management is the addition of certain management tools to the SQL language. One such tool is SchemaSQL. SchemaSQL is a proposed extension to the SQL language that promotes efficient manipulation and classification of materialized views. For instance, SchemaSQL provides “view definitions,” which allow one materialized view to be mapped to another.
Conventional management and querying of views presumes that the views exhibit a common schema. Nevertheless, as discussed above, many naturally occurring multiple database systems include databases having heterogeneous schemas. It would be advantageous to employ the replicated tables in query optimization. Additionally, it has been predicted by the inventors that tables with replicated data and heterogeneous schemas could be used to further improve query optimization in data warehousing applications.
Accordingly, a need exists for a query optimization system that is compatible with and which capitalizes on the presence of databases that are restructuring views of each other. Such a query optimization system, to be most advantageous, should be easily implemented with existing technology and noninvasive to the MDBS on which it is intended to operate. Such a query optimization system and its method of use are disclosed herein.
OBJECTS AND BRIEF SUMMARY OF THE INVENTION
The apparatus of the present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available database management systems. Thus, it is an overall objective of the present invention to provide a query optimization system and method for a database management system that capitalizes on the presence of multiple tables that are restructuring views of each other.
To achieve the foregoing object, and in accordance with the invention as embodied and broadly described herein in the preferred embodiment, a query optimization system and method are provided. The query optimization system preferably is implemented with modules for execution by a processor. In one embodiment, the modules comprise a schema mapping module executable on the processor to express a schema mapping between a plurality of database tables with heterogeneous schemas and at least partially replicated information. The modules preferably also include a middleware module adapted to employ a middleware schema for use as a reference in expressing the schema mapping.
The query optimization system is preferably compatible with existing technology that optimizes queries by posing them against materialized views. Additionally, the query optimization system of the present invention may be adapted for use on a multiple database system (MDBS) comprising databases that are restructuring views of each other. That is, the databases preferably contain data that is partially or fully replicated among the databases, but exhibit heterogeneous schemas.
In one embodiment, the middleware module comprises a canonical schema module that constructs a virtual canonical schema. The virtual canonical schema is used to express a schema mapping between different restructuring views. The schema mapping may, in one embodiment, comprise an SQL view definition.
A plurality of operators may also be employed by the schema mapping module in expressing the schema mapping. In one embodiment, each operator represents a particular type of manipulation for transforming base tables into restructuring views and for expressing the transformations. Preferably, the plurality of operators are adapted for noninvasive use with existing databases. For instance, it is preferable that the operators perform operations written in the SchemaSQL language or a similar SQL compatible language or syntax.
In one embodiment, the operators comprise a fold operator, an unfold operator, a split operator, and a unite operator.
The query optimization system may also comprise a schema restructuring module executable on a processor to restructure a database relation into a restructuring view of the database relation in conjunction with the schema mapping module and the middleware module.
A query processing module may also be included and may serve as a query translation module. The query processing module is preferably executable on the processor to communicate with the schema mapping module and translate a received query executable on one of the plurality of heterogeneous database tables to a substantially equivalent query executable on another of the plurality of heterogeneous database tables. In one embodiment, the query processing module comprises a restructuring view to canonical query c
Subramanian Narayana
Venkataraman Shivakumar
Corrielus Jean M.
International Business Machines - Corporation
Kunzler & Associates
LandOfFree
Query optimization system and method 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 system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query optimization system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3104049