Abstract query plan

• US 7,461,052 B2
• Filed: 12/06/2004
• Issued: 12/02/2008
• Est. Priority Date: 12/06/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kolz, Daniel P., Dettinger, Richard D.
• Primary Examiner(s): Fleurantin; Jean B.
• Assistant Examiner(s): Jami; Hares
• Application Number:
  US11/005,418
• Publication Number:
  US 20060122993A1
• Time in Patent Office: 1,457 Days
• Field of Search: 707/3, 707 1- 2, 707 4- 6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus, and article of manufacture are provided to process an abstract query of a database abstraction constructed over an underlying physical data storage mechanism. The database may comprise a single data source, or a federated source spanning multiple systems. Embodiments of the invention process an abstract query by generating an intermediate representation of the abstract query. In one embodiment, the intermediate representation comprises an abstract query plan. An abstract query plan includes a combination of elements from the data abstraction model and elements relating to the underlying physical data storage mechanism. Once generated, a back-end component may easily traverse the abstract query plan to generate an SQL statement (or other resolved query) corresponding to the abstract query. Further, once constructed, the abstract query plan provides a platform for many different optimizations that may be selected by a user or by the runtime component inspecting the abstract query plan prior to creating the resolved query.

Claims

1. A method of processing an abstract query, comprising:

receiving, from a requesting entity, an abstract query composed from a plurality of logical fields, wherein each logical field specifies (i) a name used to identify the logical field, (ii) an access method that maps the logical field to a data source in a database;

identifying (i) a set of data sources referenced by the plurality of logical fields in the abstract query and (ii) a set of relationships between the set of data sources;

determining an acyclic graph representation of the set of data sources;

generating an abstract query plan, wherein the abstract query plan comprises;

(a) a plurality of table instances, wherein each table instance includes;

(i) an indication of a data source associated with that table instance;

(ii) each of the logical fields included in the abstract query that depend on data present in the indicated data source; and

(iii) conditions used to limit data selected from the indicated data source; and

(b) a set of join relationships that indicates how the plurality of table instances are related to one another;

performing at least one optimization of the abstract query plan to generate an optimized abstract query plan; and

traversing the optimized abstract query plan to generate a resolved query of the set of data sources.

2. The method of claim 1, wherein the optimization comprises (i) modifying the set of join relationships or (ii) reducing a number of identical table instances included in the abstract query plan.

3. The method of claim 1, further comprising,

providing the resolved query to the a database management system configured to manage the data stored in the database;

receiving a set of query result data; and

returning the set of query result data to the requesting entity.

4. The method of claim 1, wherein the graph representation of the relational database comprises a graph representation wherein each node represents a data source, and each edge represents a relationship between data sources.

5. The method of claim 1, wherein the set of data sources comprise a set of tables in a relational database and wherein the set of relationships between the data sources comprise primary key and foreign key relationships.

6. The method of claim 1, wherein the database comprises a federated database defined using a relational schema constructed from a plurality of individual relational databases.

7. The method of claim 1, wherein acyclic graph representation of the set of data sources comprises a Steiner tree representation, wherein the root node of the Steiner tree corresponds to a model entity identified by the abstract query.

8. The method of claim 1, wherein the access method for each logical field is selected from one of a simple, filtered, or composed access method.

9. The method of claim 1, wherein creating a resolved query of the set of data comprises generating an SQL statement.

10. The method of claim 1, wherein the query building interface comprises a web-based interface accessed using an internet web browser application.