Database system and method of organizing an n-dimensional data set

• US 6,510,435 B2
• Filed: 01/10/2002
• Issued: 01/21/2003
• Est. Priority Date: 09/02/1996
• Status: Expired due to Term

• Current Assignee: Rudolf Bayer
• Original Assignee: Rudolf Bayer
• Inventors: Bayer, Rudolf
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US10/041,749
• Publication Number:
  US 20020091704A1
• Time in Patent Office: 376 Days
• Field of Search: 707/100, 707/101, 707/102, 707/103.R
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

The invention concerns a database system and method of organizing a multidimensional data stock. The database system comprises a computing arrangement, a main memory and an in particular peripheral memory arrangement. In order to index and store the data stock present in multidimensional cube on memory pages of the peripheral memory device with a given storage capacity, the multidimensional cube is divided iteratively in all dimensions into sub-cubes until successive sub-cubes can be combined to form regions each containing an amount of data objects which can be stored on one of the memory pages with a given storage capacity. The method according to the invention for organizing, insert, deleting and searching for data objects is designed as a dynamic data structure known as an “FB tree”, which improves access times and is therefore suitable for use in on-line applications.

Claims

1. A database system, comprising:

a computing device,

a main memory for indexing and storing a data set lying in a multidimensional cube, said main memory having memory pages of given storage capacity,

said multidimensional cube being repeatedly divided iteratively into sub-cubes in all dimensions until successive sub-cubes can be collected together to regions which each contains a set of data objects which can be stored on one of the memory pages.

2. A database system in accordance with claim 1, wherein the storing of the data objects of a region is performed on a memory page under allocation of a pointer to the memory page and an address designating the region boundaries.

3. A database system in accordance with claim 2, wherein the storage of the pointer and the address is done in one of a B tree, a B* tree or a prefix B tree.

4. A database system in accordance with claim 3, wherein the storage of the data objects is done on leaf pages of one of the B tree, B* tree or prefix B tree.

5. A database system in accordance with claim 2, wherein the address designating the region boundaries consists of data on the last of the sub-cubes forming the region.

6. A database system in accordance with claim 5, wherein the address comprises data on the number of sub-cubes contained at each division stage in the region.

7. A database system in accordance with claim 5, wherein the address comprises a sequence of numbers allocated to the last sub-cube in each case in the corresponding division stage still fully enclosed by the region.

8. A method for organizing an n-dimensional data set on memory pages of a storage device of given storage capacity, wherein the data set lies in a multidimensional cube, comprising:

a) repeatedly dividing iteratively the multidimensional cube in all dimensions into sub-cubes until successive sub-cubes can be collected together to regions which each contains a set of data objects which can be stored on one of the memory pages of the storage device, and

b) indexing and storing the data set on the memory pages of the storage device.

9. A method in accordance with claim 8, wherein the indexing and storing of the data set on the memory pages comprises:

a) forming a starting region consisting of a total cube;

b) counting the data objects existing in the starting region;

c) storing the data objects of the starting region on a memory page, if the number of data objects of the starting region is not greater than the number of data objects corresponding to the given storage capacity of a memory page;

d) otherwise, selecting a splitting address for the starting region in such a way that by splitting the starting region along the splitting address a first and a second partial region are created in which in each case around half the data objects of the starting region are contained;

e) continuing the method from step b), with the first partial region taking on the role of the starting region;

f) continuing the method from step b), with the second partial region taking on the role of the starting region;

g) repeating steps e) and f) in each case until the partial regions created in step d) each contains a set of data objects which can be stored on one of the memory pages of given storage capacity.

10. A method in accordance with claim 9, wherein the storing in accordance with step c) is performed with parallel storing of an address allocated to the corresponding region and a pointer allocated to the address and referring to the memory page on which the data objects stored in accordance with step c) are contained.

11. A method in accordance with claim 10, wherein the storing of the address and the pointer is done in one of a B tree, B* tree or prefix B tree, with regions being defined in each case by successive addresses, the data objects of which regions are stored in each case on a memory page of given storage capacity.

12. A method for insertion of data objects into an n-dimensional data set with n>

1 divided into regions and stored on memory pages of given storage capacity of a storage device, comprising;

a) determining a region of the n-dimensional data set associated with the data object to be inserted from the coordinates of the data object in the n-dimensional space;

b) locating the memory page on which this region is stored;

c) determining the number of the data objects stored on this memory page;

d) storing the data object on this memory page if the number of data objects stored is smaller than the number corresponding to the given storage capacity of the memory page;

e) otherwise, selecting a splitting address for the region stored on this memory page in such a way that by splitting the region along the splitting address, a first and a second partial region are generated in which in each case less than roughly half of the number of data objects corresponding to the given storage capacity is contained;

f) inserting the data object in that partial region in which the coordinates of the data object lie;

g) storing the first and second partial regions on one memory page in each case.

13. A method in accordance with claim 12, wherein the locating of the memory page in accordance with step b) is performed by means of addresses and pointers stored in one of a B tree, a B* tree or a prefix B tree and allocated to the memory pages.

14. A method in accordance with claim 13, wherein the storage of the first and second partial regions in accordance with g) is performed while replacing the pointer and address of the region from step b) by the addresses and pointers allocated in each case to the first and second partial regions.

15. A method in accordance with claim 14, wherein the storage of the address and the pointer is done in one of a B tree, B* tree or prefix B tree, with regions being defined by successive addresses in each case, the data objects of which regions are stored in each case on a memory page of given storage capacity.

16. A method for deletion of data objects in an n-dimensional data set divided into regions and stored on memory pages of given storage capacity of a memory device, comprising:

a) determining a region of the n-dimensional data set associated with the data object to be deleted from the coordinates of the data object in the n-dimensional space;

b) locating the memory page on which this region is stored;

c) deleting the data object on this memory page;

d) determining the number of data objects stored on this memory page;

e) merging the region with one of its two neighboring regions if the number of stored data objects is smaller than around half of the number corresponding to the given storage capacity of the memory page;

f) determining the number of the data objects in the region newly created by the merger;

g) storing the region on one memory page if the number of data objects existing in the region is not greater than the number corresponding to the given storage capacity of the memory page;

h) otherwise, selecting a splitting address for the region in such a way that by splitting along the splitting address, a first partial region and a second partial region are generated which each contain roughly half of the data objects determined in accordance with step f) and storage of the partial regions on one memory page in each case.

17. A method in accordance with claim 16, wherein the location of the memory page in accordance with step b) is performed by means of addresses and pointers stored in one of a B tree, B* tree or prefix B tree and allocated to the memory pages.

18. A method for performing a data query on the basis of a given n-dimensional query area in an n-dimensional data set divided into regions compiled from sub-cubes and stored on memory pages of given storage capacity of a memory device, comprising:

a) determining the coordinates of the lowest and highest point of intersection of the query area with the n-dimensional data set;

b) determining that region in which lies the lowest point of intersection and location of that memory page on which this region is stored;

c) determining all data objects stored on this memory page which form an intersection set with the query area and output of the data objects determined;

d) determining the last sub-cube in the succession of the region determined in step b), which sub-cube intersects the query area;

e) ending the data query if the highest point of intersection lies in this sub-cube;

f) otherwise, determining the next sub-cube of the same plane and the same next higher cube which intersects the query area;

g) determining the coordinates of the lowest point of intersection of the query area with the sub-cube determined and continuation of the method at step b) if a sub-cube was determined in step f);

h) otherwise, determining the next sub-cube of the plane of the next higher cube from step f) which intersects the query area and performance of step f) with the sub-cubes of the cube determined;

i) continuing the method with step f) if in step h) no sub-cube of the plane of the next higher cube from step f) is determined, with the next higher cube taking over the role of the sub-cube.