Optimization of relational database queries

• US 6,175,836 B1
• Filed: 05/06/1998
• Issued: 01/16/2001
• Est. Priority Date: 10/09/1997
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aldred, Barry Keith
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/073,804
• Time in Patent Office: 986 Days
• Field of Search: 707/102, 707/103, 707/104, 707/2, 711/171
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A data retrieval system stores a plurality of objects having a multi-level hierarchical relationship, each object having a respective parent and a set of children. The system stores one or more base tables, the or each base table comprising a respective set of attributes associated with a sub-set of objects in the system, and generates for the or each base table a respective complementary table, the or each complementary table comprising a set of attributes excluding the attributes of the associated base table. The system further includes an expression optimiser adapted to interpret a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands. The optimser tracks a number of objects associated with the or each operation and any attributes associated with the operation; and re-formulates the expression accordingly.

Claims

1. A data retrieval system in which a plurality of objects having a multi-level hierarchical relationship are stored, each object having a respective parent and a set of children, said system including:

means adapted to store one or more base tables, each base table comprising a respective set of attributes associated with a sub-set of objects in the system;

means adapted to generate for each base table a respective complementary table, the complementary table comprising a set of attributes excluding the attributes of the associated base table and having a null cardinality; and

optimisation means adapted to interpret a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands;

to track a number of objects associated with each operation and any attributes associated with the operation; and

to reformulate the expression accordingly.

2. A data retrieval system as claimed in claim 1 comprising means adapted to extend each base table to include any attributes of any parents of each base table.

3. A data retrieval system as claimed in claim 2 comprising means adapted to generate a universal view, said view comprising a union of one or more products of each extended base table and its corresponding complementary table.

4. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a product or a join operator and a pair of operands, one of said operands being a relation with no attributes, and to re-formulate the expression to delete the operator and the one operand.

5. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression an operator and a pair of operands, one of said operands being of zero cardinality, and to re-formulate the expression to delete the operator and the operand of zero cardinality.

6. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a restrict, said restrict including a plurality of parameters, and to re-formulate the expression to divide said restrict into a plurality of restricts, each including one parameter.

7. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a restrict following a join operation having a pair of join operands, and to re-formulate the expression to apply the restrict to the respective join operands separately.

8. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression consecutive projects, and to re-formulate the expression to retain only the last project.

9. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a universal view operator, and to re-formulate the expression to replace the universal view operator with an expression comprising a product of each base table and its corresponding complementary table and a union of each said product.

10. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a plurality of consecutive restricts each with one or more associated parameters, and to re-formulate the expression to combine said restricts into one restrict having all of said parameters.

11. A data retrieval system as claimed in claim 1, wherein said optimisation means is adapted to identify in an expression a join operator and a pair of join operands, said operands comprising tables having respective sets of attributes, and to re-formulate the expression to:

rename any attributes of one operand synonymous with attributes of said other operand;

replace the join operator with a product operator;

restrict the product operation to objects where any renamed attributes of the said one operand and any previously synonymous attributes of said other operand match; and

project the expression to remove any renamed attributes of the said one operand.

12. A computer program product comprising computer readable program code stored on a computer readable recording medium, the program code including a data retrieval system in which a plurality of objects having a multi-level hierarchical relationship are stored, each object having a respective parent and a set of children, said system including:

means adapted to store one or more base tables, each base table comprising a respective set of attributes associated with a sub-set of objects in the system, means adapted to generate for each base table a respective complementary table, the complementary table comprising a set of attributes excluding the attributes of the associated base table and having a null cardinality, and optimisation means adapted to interpret a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands;

to track a number of objects associated with each operation and any attributes associated with the operation; and

to reformulate the expression accordingly.

13. A method for optimizing access to a data retrieval system, said data retrieval system comprising a plurality of objects having a multi-level hierarchical relationship, each object having a respective parent and a set of children, comprising the steps of:

storing one or more base tables, each base table comprising a respective set of attributes associated with a sub-set of objects in the system;

generating for each base table a respective complementary table, the complementary table comprising a set of attributes excluding the attributes of the associated base table and having a null cardinality;

interpreting a query comprising an expression including one or more operations, each operation having a respective operator and one or more associated operands;

tracking a number of objects associated with each operation and any attributes associated with the operation; and

reformulating the expression accordingly.

14. The method of claim 13, further comprising extending each base table to include any attributes of any parent of each base table.

15. The method of claim 13 further comprising generating a universal view, said view comprising a union of one or more products of each extended base table and its corresponding complementary table.

16. The method of claim 13 further comprising identifying in an expression a product or a join operator and a pair of operands, one of said operands being a relation with no attributes and wherein said reformulating comprises reformulating the expression to delete the operator and the one operand.

17. The method of claim 13 further comprising identifying in an expression an operator and a pair of operands, one of said operands being of zero cardinality, and wherein said reformulating comprises reformulating the expression to delete the operator and the operand of zero cardinality.

18. The method of claim 13 further comprising identifying in an expression a restrict, said restrict including a plurality of parameters, and wherein said reformulating comprises reformulating the expression to divide said restrict into a plurality of restricts, each including one parameter.

19. The method of claim 13 further comprising identifying in an expression a restrict following a join operation having a pair of join operands, wherein said reformulating comprises reformulating the expression to apply the restrict to the respective join operands separately.

20. The method of claim 13 further comprising identifying in an expression consecutive projects and wherein said reformulating comprises reformulating the expression to retain only the last project.

21. The method of claim 13 further comprising identifying in an expression a universal view operator and wherein said reformulating comprises reformulating the expression to replace the universal view operator with an expression comprising a product of each base table and its corresponding complementary table and a union of each said product.

22. The method of claim 13 further comprising identifying in an expression a plurality of consecutive restricts each with one or more associated parameters and wherein said reformulating comprises reformulating the expression to combine said restricts into one restrict having all of said parameters.

23. The method of claim 13 further comprising identifying in an expression a join operator and a pair of join operands, said operands comprising tables having respective sets of attributes and wherein said reformulating comprises the steps of:

renaming any attributes of one operand synonymous with attributes of said other operand;

replacing the join operator with a product operator;

restricting the product operation to objects where any renamed attributes of the one operand and any previously synonymous attributes of said other operand match; and

projecting the expression to remove any renamed attributes of the one operand.