Abstract query plan

• US 20060122993A1
• Filed: 12/06/2004
• Published: 06/08/2006
• Est. Priority Date: 12/06/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kolz, Daniel P., Dettinger, Richard D.
• Granted Patent: US 7,461,052 B2
• Time in Patent Office: Days
• 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 accessing data in a database, 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, and (ii) an access method that maps the logical field to a data source in the database;

generating, from the abstract query, an intermediate representation of the abstract query that indicates (i) which logical fields and access methods are included in the abstract query, (ii) the data sources within the database containing the data, and (iii) the relationships between the data sources in the database; and

generating, from the intermediate representation, a resolved query of the database.

2. The method of claim 1, wherein the database is a relational database, and wherein the data source is a relational table.

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

4. The method of claim 2, wherein generating the intermediate representation of the abstract query comprises, identifying a representation of the database that includes only the relational tables and relationships between tables necessary to generate the intermediate representation.

5. The method of claim 4, wherein the identified representation of the database comprises a Steiner tree representation, wherein the root node of the Steiner tree corresponds to a model entity identified by the abstract query, and wherein the model entity identifies a logical focus of the data being queried by the abstract query.

6. The method of claim 1, wherein the intermediate representation of the abstract query comprises an abstract query plan, wherein the abstract query plan comprises (i) a plurality of table instances, wherein the each table instance includes an indication of a data source, each the logical field included in the abstract query that depend on data present on the indicated data source, and conditions used to limit the data selected from the data source;

and (ii) a set of join relationships that indicate how the plurality of table instances are related to one another relative to the abstract query.

7. The method of claim 6, further comprising, optimizing the abstract query plan by minimizing a number of identical table instances included in the abstract query plan.

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 generating, the resolved query of the database comprises generating an SQL statement.

10. The method of claim 1, wherein the query building interface comprises a web-based interface.

11. The method of claim 1, further comprising, issuing the resolved query against the database to retrieve a set of query result data, and returning the query result data to the requesting entity.

12. A method of providing an abstraction of a relational database, comprising:

defining a data abstraction model, wherein the data abstraction model comprises;

(i) a plurality of logical fields, wherein each logical field identifies a name for the logical field and an access method that maps the logical field to a column of a table in the relational database, (ii) an indication of the relationships between logical fields, and a (iii) a representation of the relational database that identifies the relationships between data sources in the relational database;

providing a query building interface configured to allow a user to compose an abstract query from the plurality of logical fields; and

providing a runtime component configured to process an abstract query to generate an intermediate representation of the abstract query.

13. The method of claim 12, wherein the intermediate representation of the abstract query comprises an abstract query plan, wherein the abstract query plan comprises (i) a plurality of table instances, wherein the each table instance includes an indication of a data source, each of the logical fields included in the abstract query that depend on data present on the indicated data source, and conditions used to limit the data selected from the indicated data source;

and (ii) a set of join relationships that indicate how the plurality of table instances are related to one another relative to the abstract query; and

(iii) a set of join relationships that indicate how the plurality of table instances are related to one another relative to the abstract query.

14. The method of claim 12, further comprising, presenting a user with an indication of the abstract query plan and allowing the user to optimize the intermediate representation by (i) modifying the set of join relationships or (ii) reducing a number of identical table instances included in the abstract query plan.

15. The method of claim 12, wherein presenting the user with an indication of the intermediate representation comprises generating displaying a graphical representation of the interface that illustrates each table instance and set of join relationships between the table instances.

16. The method of claim 13, wherein the runtime component is further configured to generate, from the abstract query plan, a resolved query of the relational database comprising an SQL statement.

17. The method of claim 12, wherein the 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.

18. The method of claim 12, wherein the query building interface comprises a web-based interface.

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

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

21. 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;

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

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

(b) a set of join relationships that indicate 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 data sources.

22. The method of claim 21, 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.

23. The method of claim 21, 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.

24. The method of claim 21, 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.

25. The method of claim 21, 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.

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

27. The method of claim 21, 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.

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

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

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

31. A computer-readable medium containing a plurality of instructions which, when executed on a computer system is configured to perform operations comprising:

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

generating, from the abstract query, an intermediate representation of the abstract query that identifies both data from the abstract query, a corresponding data source within the database containing the data, and the relationships between different data sources in the database; and

generating, from the intermediate representation, a resolved query of the database.

32. The computer-readable medium of claim 31, wherein the database is a relational database.

33. The computer-readable medium of claim 31, wherein the identified representation of the database comprises a Steiner tree representation, wherein the root node of the Steiner tree corresponds to a model entity identified by the abstract query.

34. The computer-readable medium of claim 31, wherein the intermediate representation of the abstract query comprises an abstract query plan, wherein the abstract query plan comprises (i) a plurality of table instances, wherein the each table instance includes:

an indication of a data source, each of the logical fields included in the abstract query that depend on data present on the indicated data source, and

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

(ii) a set of join relationships that indicate how the plurality of table instances are related to one another relative to the abstract query.

35. A computer-readable medium containing a plurality of instructions which, when executed on a computer system is configured to perform operations comprising:

defining a data abstraction model, wherein the data abstraction model comprises;

a plurality of logical fields, wherein each logical field identifies a name for the logical field and an access method that maps the logical field to a data source in a relational database, an indication of the relationships between logical fields, and a graph representation of the relational database that identifies the relationships between data sources in the relational database; and

providing a query building interface configured to allow the composition of an abstract query from the plurality of logical fields;

providing a runtime component configured to process an abstract query to generate a resolved query of the relational database from the abstract query.

36. A system for processing an abstract query, comprising:

a data abstraction model, wherein the data abstraction model includes (i) a plurality of logical fields, wherein each logical field specifies (a) a name used to identify the logical field, and (b) an access method that maps the logical field to data in the database, (ii) a graph representation of an underlying physical data storage mechanism being abstracted by the data abstraction model;

a user interface configured to allow a user to compose an abstract query from the plurality of logical fields;

a runtime component configured to receive and abstract query, and in response, to generate an abstract query plan, wherein the abstract query plan comprises (i) a plurality of table instances, wherein the each table instance includes an indication of a data source, each of the logical fields included in the abstract query that depend on data present on the indicated data source, and conditions used to limit the data selected from the indicated data source; and

(ii) a set of join relationships that indicate how the plurality of table instances are related to one another relative to the abstract query; and

traversing the abstract query plan to generate a resolved query of the set of data based on each table instance and the join relationships indicated between table instances.

37. The system of claim 36, further comprising,

issuing the resolved query to the underlying physical data storage mechanism retrieve a set of query result data;

and

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

38. The system of claim 36, wherein the underlying physical data storage mechanism comprises a set of tables in a relational database.

39. The system of claim 36, wherein the database comprises a federated database defined using a relational schema constructed from a plurality of individual relational databases.

40. The system of claim 36, wherein the 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.

41. The system of claim 36, wherein the user interface is further configured to present a user with an indication of the abstract query plan and allowing the user to optimize the intermediate representation by (i) modifying the set of join relationships or (ii) reducing a number of identical table instances included in the abstract query plan.