Cartesian product detection

• US 20060047638A1
• Filed: 09/02/2004
• Published: 03/02/2006
• Est. Priority Date: 09/02/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kolz, Daniel P., Dettinger, Richard D., Tenner, Jeffrey W., Stevens, Richard J.
• Application Number:
  US10/932,709
• Publication Number:
  US 20060047638A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A method, system and article of manufacture for query processing and, more particularly, for determining that Cartesian Products will occur in query results without executing corresponding queries. One embodiment provides a method for detecting Cartesian Products in query results. The method comprises identifying, from a query against one or more databases, joins between different tables of the one or more databases. Without executing the query against the one or more databases, it is determined on the basis of cardinalities of the identified joins whether a Cartesian Product will occur in a query result corresponding to the query.

Claims

1. A method for detecting Cartesian Products in query results, comprising:

identifying, from a query against one or more databases, joins between different tables of the one or more databases; and

determining on the basis of cardinalities of the identified joins whether a Cartesian Product will occur in a query result corresponding to the query, without executing the query against the one or more databases.

2. The method of claim 1, wherein the determining comprises:

detecting a condition in the cardinalities of the identified joins that will result in occurrence of the Cartesian Product.

3. The method of claim 1, further comprising:

determining the cardinalities of the identified joins by analyzing the different tables of the one or more databases.

4. The method of claim 1, further comprising:

determining the cardinalities of the identified joins from relationship definitions included with a data abstraction model abstractly describing the data in the one or more databases.

5. The method of claim 1, further comprising:

constructing a join graph representing the identified joins and the cardinalities of the identified joins.

6. The method of claim 5, further comprising:

identifying, from the join graph, joins having cardinalities defining one of (i) one-to-many and (ii) many-to-many relationships between corresponding tables; and

wherein it is determined that the Cartesian Product will occur if the join graph includes two or more joins having cardinalities defining the one of (i) one-to-many and (ii) many-to-many relationships.

7. The method of claim 5, wherein the join graph comprises two or more branches connected to a star point, each branch including one or more identified joins, the method further comprising:

for each branch of the join graph;

traversing the branch to identify the included joins; and

determining the cardinalities of each included join to identify joins having cardinalities defining one of (i) one-to-many and (ii) many-to-many relationships between corresponding tables; and

wherein it is determined that the Cartesian Product will occur if the join graph includes two or more branches including joins having cardinalities defining the one of (i) one-to-many and (ii) many-to-many relationships.

8. The method of claim 1, further comprising:

notifying a user if it is determined that the Cartesian Product will occur in the query result.

9. The method of claim 1, further comprising:

associating the query with a warning flag to indicate that it is determined that the Cartesian Product will occur in the query result.

10. The method of claim 1, wherein the query is composed using logical fields defined by a data abstraction model abstractly describing the data in the database.

11. The method of claim 10, wherein each logical field is mapped to one or more physical entities of data of an underlying data representation being used in the one or more databases.

12. The method of claim 1, wherein the query is a SQL query.

13. A method for detecting Cartesian Products in query results, comprising:

constructing, for a query, a join graph representing joins between a plurality of tables of one or more databases;

traversing the join graph from one table to another table for each of the plurality of tables; and

determining, on the basis of the traversing and without executing the query, whether a predetermined type of condition exists in the join graph which is capable of contributing to a resulting Cartesian Product in a query result corresponding to the query.

14. The method of claim 13, wherein the predetermined type of condition comprises a N-to-many join in the join graph.

15. The method of claim 13, wherein determining the predetermined type of condition capable of contributing to the resulting Cartesian Product comprises determining the cardinalities of the joins.

16. The method of claim 13, further comprising determining, on the basis of the predetermined type of condition in the join graph that wherein determining the predetermined type of condition capable of contributing to the resulting Cartesian Product comprises identifying at least two N-to-many joins in the join graph.

17. The method of claim 13, further comprising:

determining that the Cartesian Product will result in the query result on the basis of the predetermined type of condition existing in the join graph; and

notifying a user of the Cartesian Product without executing the query.

18. A computer-readable medium containing a program which, when executed by a processor, performs a process for detecting Cartesian Products in query results, the process comprising:

identifying, from a query against one or more databases, joins between different tables of the one or more databases; and

determining on the basis of cardinalities of the identified joins whether a Cartesian Product will occur in a query result corresponding to the query, without executing the query against the one or more databases.

19. The computer-readable medium of claim 18, wherein the determining comprises:

detecting a condition in the cardinalities of the identified joins that will result in occurrence of the Cartesian Product.

20. The computer-readable medium of claim 18, wherein the process further comprises:

determining the cardinalities of the identified joins by analyzing the different tables of the one or more databases.

21. The computer-readable medium of claim 18, wherein the process further comprises:

determining the cardinalities of the identified joins from relationship definitions included with a data abstraction model abstractly describing the data in the one or more databases.

22. The computer-readable medium of claim 18, wherein the process further comprises:

constructing a join graph representing the identified joins and the cardinalities of the identified joins.

23. The computer-readable medium of claim 22, wherein the process further comprises:

identifying, from the join graph, joins having cardinalities defining one of (i) one-to-many and (ii) many-to-many relationships between corresponding tables; and

wherein it is determined that the Cartesian Product will occur if the join graph includes two or more joins having cardinalities defining the one of (i) one-to-many and (ii) many-to-many relationships.

24. The computer-readable medium of claim 22, wherein the join graph comprises two or more branches connected to a star point, each branch including one or more identified joins, the process further comprising:

for each branch of the join graph;

traversing the branch to identify the included joins; and

determining the cardinalities of each included join to identify joins having cardinalities defining one of (i) one-to-many and (ii) many-to-many relationships between corresponding tables; and

wherein it is determined that the Cartesian Product will occur if the join graph includes two or more branches including joins having cardinalities defining the one of (i) one-to-many and (ii) many-to-many relationships.

25. The computer-readable medium of claim 18, wherein the process further comprises:

notifying a user it is determined that the Cartesian Product will occur in the query result.

26. The computer-readable medium of claim 18, wherein the process further comprises:

associating the query with a warning flag to indicate that it is determined that the Cartesian Product will occur in the query result.

27. The computer-readable medium of claim 18, wherein the query is composed using logical fields defined by a data abstraction model abstractly describing the data in the database.

28. The computer-readable medium of claim 27, wherein each logical field is mapped to one or more physical entities of data of an underlying data representation being used in the one or more databases.

29. The computer-readable medium of claim 18, wherein the query is a SQL query.

30. A computer system comprising:

one or more databases; and

a query manager configured for;

identifying, from a query against the one or more databases, joins between different tables of the one or more databases; and

determining on the basis of cardinalities of the identified joins whether a Cartesian Product will occur in a query result corresponding to the query, without executing the query against the one or more databases.