US6175836B1 — Optimization of relational database queries

Claim 1

Independent Claim 142 words

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.

Claim 2

Dependent Claim 142 words

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.

Claim 3

Dependent Claim 28 words

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.

Claim 4

Dependent Claim 37 words

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.

Claim 5

Dependent Claim 55 words

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.

Claim 6

Dependent Claim 51 words

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.

Claim 7

Dependent Claim 48 words

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.

Claim 8

Dependent Claim 48 words

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.

Claim 9

Dependent Claim 34 words

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.

Claim 10

Dependent Claim 58 words

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.

Claim 11

Dependent Claim 50 words

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.

Claim 12

Dependent Claim 105 words

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.

Claim 13

Dependent Claim 162 words

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.

Claim 14

Dependent Claim 162 words

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.

Claim 15

Independent Claim 137 words

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.

Claim 16

Independent Claim 137 words

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.

Claim 17

Dependent Claim 23 words

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

Claim 18

Dependent Claim 31 words

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.

Claim 19

Dependent Claim 48 words

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.

Claim 20

Dependent Claim 44 words

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.

Claim 21

Dependent Claim 41 words

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.

Claim 22

Dependent Claim 40 words

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.

Claim 23

Dependent Claim 27 words

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.

Claim 24

Dependent Claim 51 words

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.

Claim 25

Dependent Claim 43 words

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.

Claim 26

Dependent Claim 95 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-01-16	2004-07-17	2005-01-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-01-16	2008-07-17	2009-01-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-01-16	2012-07-17	2013-01-16	$7700.00	Window Closed / Lapsed

Optimization of relational database queries

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag