Computer method, apparatus and programmed medium for more efficient database management using histograms with a bounded error selectivity estimation

Claim 2

A computer based method for determining a number of regions, said number being a factor of a minimum number of regions, a database data distribution can be partitioned into to create an approximation of said database which is within said factor of a maximum error measure, said method comprising the steps of: storing said maximum error measure; finding an upper limit number, said upper limit number being at most said factor of a maximum number of regions said database can be partitioned into to create an approximation within at most said factor of said stored maximum error measure; determining whether said upper limit number is also said minimum number of regions said database can be partitioned into to create an approximation of said database which is within said factor of said stored maximum error measure; and using said factor of said minimum number of regions to approximate said database for searchable inquiries.

Claim 3

The method according to claim 1, wherein said determining step further comprises: setting a first number value based on said upper limit number, said set first number value being less than said upper limit number; calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value; and determining whether said b is said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 4

The method according to claim 2, wherein if said b is not said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure, said method further comprises: determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions; replacing said upper limit number by said b number if said calculated error measure does exceed said stored maximum error measure; replacing said set first number value with said b number if said calculated error measure does not exceed said stored maximum error measure; and repeating said calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value step, said determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions step, said replacing said upper limit number step and said replacing said set first number value step until a minimum value for said b number of regions is found, said minimum value b being said factor of said minimum number of regions which said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 5

The method according to claim 3, further comprising the step of: storing said minimum value for said b.

Claim 6

The method according to claim 4, further comprising the step of: outputting an indication of said factor of said minimum number of partitions said database can be partitioned into within said factor of said stored maximum error measure.

Claim 7

The method according to claim 5, wherein said factor is 3.

Claim 8

The method according to claim 1, wherein said maximum error measure is entered by a user.

Claim 9

The method according to claim 1, wherein said step of finding an upper limit number is performed by a binary search method.

Claim 10

The method according to claim 2, wherein said set first number value is equal to one half of said upper limit number.

Claim 11

The method according to claim 2, wherein said b is an average of said upper limit number and said set first number value.

Claim 12

The method according to claim 1, wherein said using step further comprises: constructing an approximation of said database using a histogram technique with said factor of said minimum number of regions.

Claim 13

A computer readable storage medium containing a computer readable code for operating a computer to perform a method for determining a number of regions, said number being a factor of a minimum number of regions, a database data distribution can be partitioned into to create an approximation of said database which is within said factor of a maximum error measure, said method comprising the steps of: storing said maximum error measure; finding an upper limit number, said upper limit number being at most said factor of a maximum number of regions said database can be partitioned into to create an approximation within at most said factor of said stored maximum error measure; determining whether said upper limit number is also said minimum number of regions said database can be partitioned into to create an approximation of said database which is within said factor of said stored maximum error measure; and using said factor of said minimum number of regions to approximate said database for searchable inquiries.

Claim 14

A computer readable storage medium containing a computer readable code for operating a computer to perform a method for determining a number of regions, said number being a factor of a minimum number of regions, a database data distribution can be partitioned into to create an approximation of said database which is within said factor of a maximum error measure, said method comprising the steps of: storing said maximum error measure; finding an upper limit number, said upper limit number being at most said factor of a maximum number of regions said database can be partitioned into to create an approximation within at most said factor of said stored maximum error measure; determining whether said upper limit number is also said minimum number of regions said database can be partitioned into to create an approximation of said database which is within said factor of said stored maximum error measure; and using said factor of said minimum number of regions to approximate said database for searchable inquiries.

Claim 15

The computer readable storage medium according to claim 12, wherein said determining step further comprises: setting a first number value based on said upper limit number, said set first number value being less than said upper limit number; calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value; and determining whether said b is said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 16

The computer readable storage medium according to claim 13, wherein if said b is not said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure, said method further comprises: determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions; replacing said upper limit number by said b number if said calculated error measure does exceed said stored maximum error measure; replacing said set first number value with said b number if said calculated error measure does not exceed said stored maximum error measure; and repeating said calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value step, said determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions step, said replacing said upper limit number step and said replacing said set first number value step until a minimum value for said b number of regions is found, said minimum value b being said factor of said minimum number of regions which said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 17

The computer readable storage medium according to claim 14, further comprising the step of: storing said minimum value for said b.

Claim 18

The computer readable storage medium according to claim 15, further comprising the step of: outputting an indication of said factor of said minimum number of partitions said database can be partitioned into within said factor of said stored maximum error measure.

Claim 19

The computer readable storage medium according to claim 16, wherein said factor is 3.

Claim 20

The computer readable storage medium according to claim 12, wherein said maximum error measure is entered by a user.

Claim 21

The computer readable storage medium according to claim 12, wherein said step of finding an upper limit number is performed by a binary search method.

Claim 22

The computer readable storage medium according to claim 13, wherein said set first number value is equal to one half of said upper limit number.

Claim 23

The computer readable storage medium according to claim 13, wherein said b is an average of said upper limit number and said set first number value.

Claim 24

The computer readable storage medium according to claim 12, wherein said using step further comprises: constructing an approximation of said database using a histogram technique with said factor of said minimum number of regions.

Claim 27

The system comprising a programmed computer and a stored database according to claim 23, wherein said determining step further comprises: setting a first number value based on said upper limit number, said set first number value being less than said upper limit number; calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value; and determining whether said b is said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 28

The system comprising a programmed computer and a stored database according to claim 24, wherein if said b is not said minimum number of regions said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure, said method further comprises: determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions; replacing said upper limit number by said b number if said calculated error measure does exceed said stored maximum error measure; replacing said set first number value with said b number if said calculated error measure does not exceed said stored maximum error measure; and repeating said calculating an error measure of approximation when said database is approximated by partitioning said database into b number of regions, said b being between said upper limit number and said set first number value step, said determining whether said calculated error measure exceeds said stored maximum error measure when said database is partitioned into said b number of regions step, said replacing said upper limit number step and said replacing said set first number value step until a minimum value for said b number of regions is found, said minimum value b being said factor of said minimum number of regions which said database can be partitioned into to create an approximation of said database within said factor of said stored maximum error measure.

Claim 29

The system comprising a programmed computer and a stored database according to claim 25, further comprising the step of: storing said minimum value for said b.

Claim 30

The system comprising a programmed computer and a stored database according to claim 26, further comprising the step of: outputting an indication of said factor of said minimum number of partitions said database can be partitioned into within said factor of said stored maximum error measure.

Claim 31

The system comprising a programmed computer and a stored database according to claim 27, wherein said factor is 3.

Claim 32

The system comprising a programmed computer and a stored database according to claim 23, wherein said maximum error measure is entered by a user.

Claim 33

The system comprising a programmed computer and a stored database according to claim 23, wherein said step of finding an upper limit is performed by a binary search method.

Claim 34

The system comprising a programmed computer and a stored database according to claim 24, wherein said set first number value is equal to one half of said upper limit number.

Claim 35

The system comprising a programmed computer and a stored database according to claim 24, wherein said b is an average of said upper limit and said set first number value.

Claim 36

The system comprising a programmed computer and a stored database according to claim 23, wherein said using step further comprises: constructing an approximation of said database using a histogram technique with said factor of said minimum number of regions.