MULTI-DIMENSIONAL HISTOGRAM METHOD USING MINIMAL DATA-SKEW COVER IN SPACE-PARTITIONING TREE AND RECORDING MEDIUM STORING PROGRAM FOR EXECUTING THE SAME

• US 20110145244A1
• Filed: 01/28/2010
• Published: 06/16/2011
• Est. Priority Date: 12/15/2009
• Status: Abandoned Application

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Kim, Jae Ho, Son, Jin Hyun, Kim, Myoung Ho, Roh, Yohan J.
• Application Number:
  US12/695,500
• Publication Number:
  US 20110145244A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

The present disclosure relates to a multi-dimensional histogram method using a minimal data-skew cover in a space-partitioning tree, which is used to estimate the selectivity of queries, that is, the sizes of query results, and a recording medium storing a program for executing the multi-dimensional histogram method. In the multi-dimensional histogram method, a Database (DB) system receives information required to generate a histogram from an outside of the DB system, and then constructs a space-partitioning tree based on the information required to generate a histogram. The DB system constructs a multi-dimensional histogram based on a minimal data-skew cover in the space-partitioning tree. When the DB system receives a query from the outside, the DB system calculates the estimate of the selectivity for the query by using the multi-dimensional histogram. Further, the present disclosure includes a recording medium storing a program for executing the multi-dimensional histogram method.

Claims

1. A multi-dimensional histogram method using a minimal data-skew cover in a space-partitioning tree to estimate selectivity of queries, comprising:

(a) a database (DB) system receiving information required to generate a histogram from an outside of the DB system, and then constructing a space-partitioning tree based on the information required to generate a histogram;

(b) the DB system constructing a multi-dimensional histogram based on a minimal data-skew cover in the space-partitioning tree; and

(c) the DB system receiving a query from the outside, and then estimating selectivity of the quay by using the multi-dimensional histogram.

2. The multi-dimensional histogram method according to claim 1, wherein the information required to generate the histogram comprises one or more of an entire data space, a data set, a maximum number of buckets, and an index structure.

3. The multi-dimensional histogram method according to claim 2, wherein (a) comprises:

(a-1) the DB system receiving the entire data space, the data set and the maximum number of buckets as the information required to generate a histogram from the outside, and then partitioning the entire data space into one or more areas;

(a-2) the DB system computing the Minimum Bounding Regions (MBRs) of data objects in the partitioned areas, and constructing a space-partitioning tree, based on the computed MBRs; and

(a-3) calculating data skew values of respective nodes included in the space-partitioning tree.

4. The multi-dimensional histogram method according to claim 3, wherein (a-1) is performed to partition the entire data space into one or more areas by using one of a binary space partitioning method and a complete quadtree partitioning method.

5. The multi-dimensional histogram method according to claim 2, wherein (a) comprises:

(a′

-1) the DB system receiving the index structure, the data set, and the maximum number of buckets as the information required to generate a histogram from the outside, and then using the index structure as a space-partitioning tree; and

(a′

-2) calculating data skew values of respective nodes included in the space-partitioning tree.

6. The multi-dimensional histogram method according to claim 5, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.

7. The multi-dimensional histogram method according to claim 6, wherein the buckets of the multi-dimensional histogram are formed in shapes of hyperrectangles.

8. The multi-dimensional histogram method according to claim 6, wherein (c) is performed such that, for a data region I specified by a given range query, an estimate of the selectivity for the query is computed using the following equation:

19. The multi-dimensional histogram method according to claim 4, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.

20. The multi-dimensional histogram method according to claim 3, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.

9. A recording medium storing a program for executing a multi-dimensional histogram method using a minimal data-skew cover in a space-partitioning tree to estimate selectivity of queries, the multi-dimensional histogram method comprising:

(a) a database (DB) system receiving information required to generate a histogram from an outside of the DB system, and then constructing a space-partitioning tree based on the information required to generate a histogram;

(b) the DB system constructing a multi-dimensional histogram based on a minimal data-skew cover in the space-partitioning tree; and

(c) the DB system receiving a query from the outside, and then estimating selectivity of the query by using the multi-dimensional histogram.

10. The recording medium according to claim 9, wherein the information required to generate the histogram comprises one or more of an entire data space, a data set, a maximum number of buckets, and an index structure.

11. The recording medium according to claim 10, wherein (a) comprises:

(a-1) the DB system receiving the entire data space, the data set and the maximum number of buckets as the information required to generate a histogram from the outside, and then partitioning the entire data space into one or more areas;

(a-2) the DB system computing the Minimum Bounding Regions (MBRs) of data objects in the partitioned areas, and constructing a space-partitioning tree, based on the computed MBRs; and

(a-3) calculating the data skew values of respective nodes included in the space-partitioning tree.

12. The recording medium according to claim 11, wherein (a-1) is performed to partition the entire data space into one or more areas by using one of a binary space partitioning method and a complete quadtree partitioning method.

13. The recording medium according to claim 10, wherein (a) comprises:

(a′

-1) the DB system receiving the index structure, the data set, and the maximum number of buckets as the information required to generate a histogram from the outside, and then using the index structure as a space-partitioning tree; and

(a′

-2) calculating the data skew values of respective nodes included in the space-partitioning tree.

14. The recording medium according to claim 13, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of the data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.

15. The recording medium according to claim 14, wherein the buckets of the multi-dimensional histogram are formed in shapes of hyperrectangles.

16. The recording medium according to claim 14, wherein (c) is performed such that, for a data region I specified by a given range query, an estimate of the selectivity for the query is computed using the following equation:

17. The recording medium according to claim 12, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of the data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.

18. The recording medium according to claim 11, wherein (b) comprises:

(b-1) the DB system searching the space-partitioning tree for covers of the space-partitioning tree;

(b-2) the DB system determining a minimal data-skew cover with respect to a given cover in the space-partitioning tree, depending on whether a number of nodes included in the given cover in the space-partitioning tree is less than or equal to the externally received maximum number of buckets and whether a sum of the data skew values of the respective nodes included in the given cover in the space-partitioning tree is a minimal value; and

(b-3) the DB system constructing a multi-dimensional histogram by organizing the nodes included in the minimal data-skew cover into histogram buckets.