Method and apparatus for multidimensional database using binary hyperspatial code

• US 6,161,105 A
• Filed: 10/02/1996
• Issued: 12/12/2000
• Est. Priority Date: 11/21/1994
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Vretanos, Panagiotis A., Varma, Herman P., Keighan, Edric, Galluchon, Michael
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/827,987
• Time in Patent Office: 1,532 Days
• Field of Search: 707/102, 707/104, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An improved database data structure and datatype is disclosed for storing, manipulating and accessing multidimensional spatial data in a database. Binary helical hyperspatial code (HH CODE) is used to represent data of N dimensions. The binary HH CODE data structure maintains the dimensional organization of multidimensional data within the data itself. Spatial data is stored using BH code which is modeled as a N-tree structure derived using recursive decomposition. A high water mark is set as the upper limit for data volume which may be stored in any one partition. As data stored in a partition exceeds the high water mark, the data is decomposed into child partitions such that no partition data stores exceed the high water mark. If the high water mark is exceeded, additional child partitions are automatically created and the parent table is not retained. A data structure is defined which represents the partitioned tables and BH code values. Appropriate attributes are associated with each of the BH code values which may represent non-spatial data such as temperature, salinity, or cosmic ray flux. Methods and apparatus are also provided to apply teachings of binary HH CODE to line segments and topology.

Claims

1. A method for storing dimensional data in a database, comprising the computer-implemented steps of:

receiving dimensional data points;

determining a hyperspatial code for said data points by recursively defining spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another;

generating hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and

generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.

2. The method for storing dimensional data as defined by claim 1, wherein each of said data partitions stored in said data dictionary is a database object.

66. The method as defined by claim 1, wherein each of said respective entries for each of said generated data partitions includes a hyperspatial code value representing an extent of a corresponding generated data partition.

3. A method for storing dimensional data in a database, comprising the computer-implemented steps of:

receiving dimensional data points; and

determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code.

4. The method for storing dimensional data as defined by claim 3, wherein said meta data includes dimension bits to identify a number of dimensions in hyperspatial key.

5. The method for storing dimensional data as defined by claim 3, wherein said meta data includes a type bit to identify the type of a geometric object associated with the hyperspatial key.

6. The method for storing dimensional data as defined by claim 3, wherein said meta data includes a topology bit to identify whether hyperspatial key represents the interior or boundary of topology.

7. The method for storing dimensional data as defined by claim 3, wherein said meta data includes level bits to identify the number of levels of precision which are encoded in hyperspatial key for each dimension identified by said dimension bits.

8. A method for storing dimensional data in a database, comprising the computer-implemented steps of:

receiving dimensional data points;

determining a hyperspatial code for said data points by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another; and

generating a data dictionary, wherein said data dictionary includes a list of all tables stored in said database that are multidimensional.

9. The method for storing dimensional data as defined by claim 8, wherein said database stores a list of said dimensional data, including both spatial and non-spatial.

10. The method for storing dimensional data as defined by claim 8 wherein said data dictionary includes partitioned tables and non-partitioned tables, said non-partitioned tables comprising relational database tables that include at least one column having attributes with spatial hyperspatial code columns.

11. The method for storing dimensional data as defined by claim 10, wherein said partitioned tables comprise multidimensional tables that include at least one spatial column and are partitioned on said at least one of said spatial columns.

12. An apparatus for storing dimensional data points in a database coupled to a computer, comprising:

an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in which a predefined volume of said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another;

an element for partitioning and storing said hyperspatial code in said database, said element for partitioning generates hyperspatial code data partitions based on the number of dimensions of said dimensional data points and said predefined volume; and

an element for generating a data dictionary, said data dictionary including a partition table having respective entries for each of said generated data partitions.

13. The apparatus as defined by claim 12, wherein each of said data partitions stored in said data dictionary is a database object.

67. The apparatus as defined by claim 12, wherein each of said respective entries for each of said generated data partitions includes a hyperspatial code value representing an extent of a corresponding generated data partition.

14. An apparatus for storing dimensional data points in a database coupled to a computer, comprising:

an element coupled to said computer for determining binary hyperspatial codes (BH codes) for said data points, respectively, by recursively defining spatial cells in which said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another, wherein each of said BH codes includes a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code; and

an element for partitioning and storing said BH codes in said database.

15. The apparatus as defined by claim 14, wherein said meta data includes dimension bits to identify a number of dimensions in the hyperspatial key.

16. The apparatus as defined by claim 14, wherein said meta data includes a type bit to identify the type of a geometric object associated with the hyperspatial key.

17. The apparatus as defined by claim 14, wherein said meta data includes a topology bit to identify whether hyperspatial key represents the interior or boundary of topology.

18. The apparatus as defined by claim 14, wherein said meta data includes level bits to identify the number of levels of precision which are encoded in hyperspatial key for each dimension identified by said dimension bits.

19. An apparatus for storing dimensional data points in a database coupled to a computer, comprising:

an element coupled to said computer for determining a hyperspatial code for said dimensional data points by recursively decomposing spatial cells in said dimensional data points reside, said spatial cells being identified by binary quantities representing the location of said spatial cells relative to one another;

an element for partitioning and storing said hyperspatial code in said database; and

an element for generating a data dictionary, wherein said data dictionary includes a multidimension table which contains a list of all tables stored in said database that are multidimensional.

20. The apparatus as defined by claim 19, wherein said database stores a list of said dimensional data, including both spatial and non-spatial.

21. The apparatus as defined by claim 19, wherein said data dictionary includes partitioned tables and non-partitioned tables, said non-partitioned tables comprising relational database tables that include at least one column having attributes with spatial hyperspatial code columns.

22. The apparatus as defined by claim 21, wherein said partitioned tables comprise multidimensional tables that include at least one spatial column and are partitioned on said at least one of said spatial columns.

23. A method for storing a line segment in a database, comprising the computer-implemented steps of:

receiving data points representing a first (x₁,y₁) and a second (x₂, y₂) end point of said line segment; and

determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.

24. The method as defined by claim 23, wherein said hyperspatial code determined for said line segment is a four dimension hyperspatial code.

25. The method as defined by claim 24, wherein:

a first dimension of the four dimension hyperspatial code represents x₁,

a second dimension of the four dimension hyperspatial code represents y₁,

a third dimension of the four dimension hyperspatial code represents x₂ and

a fourth dimension of the four dimension hyperspatial code represents y₂.

26. The method as defined by claim 23, wherein a plurality of line segments are stored in said database, each of said line segments being represented by a hyperspatial code.

27. The method as defined by claim 23, further providing an element for performing the steps of generating hyperspatial code data partitions based upon a predefined number of hyperspatial code entries which may be disposed in any one partition.

28. The method as defined by claim 27, wherein if during said generation of hyperspatial code data partitions said predefined number of hyperspatial code entries is exceeded, additional child data partitions are generated and said original parent data partition is not retained.

29. The method as defined by claim 28, wherein for each of said parent data partitions in which said predefined number of hyperspatial code entries are exceeded, sixteen child data partitions are created.

30. The method as defined by claim 29, wherein of said sixteen data partitions only those partitions in which a hyperspatial code is actually stored are maintained in said database.

31. The method as defined by claim 27, wherein attribute data is associated with said hyperspatial codes representing said dimensional data, said attribute data further being associated with said BH code data partitions.

32. The method as defined by claim 27, further including an element for performing the steps of generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.

33. The method as defined by claim 32, wherein each of said data partitions stored in said data dictionary is a database objects.

34. The method as defined by claim 26, wherein each said hyperspatial code is a binary hyperspatial code (BH code) including a data structure having hyperspatial code data representing a hyperspatial key and meta data representing an attribute of the BH code.

35. The method as defined by claim 34, wherein said meta data includes a type bit to identify the type of said hyperspatial code data as a geometric object.

36. The method as defined by claim 32, wherein said data dictionary includes a list of all tables stored in said database that are multidimensional.

37. The method as defined by claim 32, further including a method for accessing said stored line segments, comprising the steps of:

receiving input from a user defining a region of interest;

identifying which of said data partitions define line segments which are at least partially disposed within said region of interest;

compiling a list of said identified data partitions;

determining if each of said hyperspatial code entries in said identified partitions are disposed within said region of interest, and reporting those hyperspatial code entries which are disposed within said region to said user.

38. The method as defined by claim 37, wherein said step of identifying which of said data partitions define line segments which are at least partially disposed within said region of interest includes the steps of:

defining sixteen potential partition shapes for said stored line segments, said sixteen partition shapes representing said data partitions in said data dictionary; and

examining each of said hyperspatial code entries in said partitions stored in said data dictionary and decoding said hyperspatial code.

39. An apparatus for storing a line segment in a database coupled to a computer, comprising:

an element for receiving data points representing a first (x₁,y₁) and a second (x₂,y₂) end point of said line segment;

an element for determining a single hyperspatial code for said line segment by defining first and second spatial cells in which said first and second end points reside, respectively, said first and second spatial cells being identified by binary quantities representing the location of said first and second spatial cells relative to one another.

40. The apparatus as defined by claim 39, wherein said hyperspatial code determined for said line segment is a four dimension hyperspatial code.

41. The apparatus as defined by claim 40, wherein:

a first dimension of the four dimension hyperspatial code represents x₁,

a second dimension of the four dimension hyperspatial code represents y₁,

a third dimension of the four dimension hyperspatial code represents x₂ and

a fourth dimension of the four dimension hyperspatial code represents y₂.

42. The apparatus as defined by claim 39, wherein a plurality of line segments are stored in said database, each of said line segments being represented by a hyperspatial code.

43. The apparatus as defined by claim 39, further providing an element for generating hyperspatial code data partitions based upon a predefined number of hyperspatial code entries which may be disposed in any one partition.

44. The apparatus as defined by claim 43, wherein if during said generation of hyperspatial code data partitions said predefined number of hyperspatial code entries is exceeded, additional child data partitions are generated and said original parent data partition is not retained.

45. The apparatus as defined by claim 44, wherein for each of said parent data partitions in which said predefined number of hyperspatial code entries are exceeded, sixteen child data partitions are treated.

46. The apparatus as defined by claim 45, wherein of said sixteen data partitions only those partitions in which hyperspatial code is actually stored are maintained in said database.

47. The apparatus as defined by claim 43, wherein attribute data is associated with said hyperspatial codes representing said dimensional data, said attribute data further being associated with said hyperspatial code data partitions.

48. The apparatus as defined by claim 43, further including an element for generating a data dictionary, said data dictionary including a table having respective entries for each of said generated data partitions.

49. The apparatus as defined by claim 48, wherein each of said data partitions stored in said data dictionary is a database object.

50. The apparatus as defined by claim 42, wherein each said hyperspatial code is a binary hyperspatial code (BH code) including a data structure having BH code data representing a hyperspatial key and meta data representing an attribute of the BH code.

51. The apparatus as defined by claim 50, wherein said meta data includes a type bit to identify the type of hyperspatial key as a geometric object.

52. The apparatus as defined by claim 48, wherein said data dictionary includes a list of all tables stored in a corresponding relational database which are multidimensional.

53. The apparatus as defined by claim 43, further including an apparatus for accessing said stored line segments, comprising:

an element for receiving input from a user to define a region of interest;

an element for identifying which of said data partitions define line segments which are at least partially disposed within said region of interest;

an element for compiling a list of said identified data partitions;

an element for determining if each of said hyperspatial code entries in said identified partitions are disposed within said region of interest, and reporting those hyperspatial code entries which are disposed within said region to said user.

54. A method for storing a topologic representation of a first object in a database, comprising the computer-implemented steps of:

defining an interior I₁ and a boundary B₁ for said first object;

recursively decomposing said first object into first object tile regions defined by BH codes; and

wherein said BH codes identify whether each of said first tile regions forms part of said interior I₁ or said boundary B₁.

55. The method as defined by claim 54, further comprising the step of creating an object partitioned table for said first object containing said BH codes.

56. The method as defined by claim 55, further including the steps of:

providing a second object;

defining an interior I₂, and a boundary B₂ for said second object;

recursively decomposing said second object into second object tile regions defined by BH codes;

wherein each of said BH codes for said second object identifies whether each of said second object tile regions forms part of said interior I₂ or said boundary B₂.

57. The method as defined by claim 56, further comprising the step of creating an object partitioned table for said second object containing said BH codes for said second object.

58. The method as defined by claim 57, further including the step of applying an intersection methodology to said BH codes in said first and second object partitioned tables to determine the relationship of said first and second objects to one another.

59. The method as defined by claim 58, wherein said intersection methodology comprises an Egenhofer Four Point Intersection methodology.

68. The method as defined by claim 56, wherein each of BH codes includes a data structure having code data and meta data, said meta data including a topology bit to identify whether said BH code data represents the interior or boundary of topology.

60. An apparatus for storing a topologic representation of a first object in a database, comprising:

an element for defining an interior I₁ and a boundary B₁ for said first object; and

an element for recursively decomposing said first object into first object tile regions defined by binary hyperspatial codes (BH code);

wherein each of said BH codes identifies whether each of said first tile regions forms part of said interior I₁ or said boundary B₁.

61. The apparatus as defined by claim 60 further including an element for creating an object partitioned table for said first object containing said BH codes.

62. The apparatus as defined by claim 61 further including:

a second object;

an element for defining an interior I₂ and a boundary B₂ for said second object; and

an element for recursively decomposing said second object into second object tile regions defined by BH codes;

wherein each of said BH codes identifies whether each of said second tile regions forms part of said interior I₂ or said boundary B₂.

63. The apparatus as defined by claim 62, further including an element for creating an object partitioned table for said second object containing said BH codes for said second object.

64. The apparatus as defined by claim 63, further including an element for applying an intersection methodology to said BH codes in said first and second object partitioned tables to determine the relationship of said first and second objects to one another.

65. The apparatus as defined by claim 64, wherein said intersection methodology comprises an Egenhofer Four Point Intersection methodology.

69. The apparatus as defined by claim 62, wherein each of BH codes includes a data structure having code data and meta data, said meta data including a topology bit to identify whether said BH code data represents the interior or boundary of topology.