Method for processing multi-dimensional data

• US 5,864,857 A
• Filed: 03/27/1997
• Issued: 01/26/1999
• Est. Priority Date: 03/29/1996
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Yoneda, Shigeru, Kimura, Tomoko, Ozu, Ikuyo, Kiyasu, Kiyotaka, Ohata, Hideo, Masuishi, Tetsuya
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/835,026
• Time in Patent Office: 670 Days
• Field of Search: 707/1, 707/100, 707/503, 707/504, 707/509
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

In a multi-dimensional data management method in a database management system, a collection of members constituting each dimension is grouped and page indexes constituted by entries corresponding to combinations of member groups of each dimension are assigned to a memory unit. A set of member groups corresponding to input data is determined from a set of members of dimensions specifying the input data and an entry of page index corresponding to the set of member groups is obtained. When a page number is not registered in said obtained entry, a page is assigned in the memory unit and the page number of the page is registered in the entry. The input data and identification information of the data are paired to be stored in the page having the page number registered in the entry.

Claims

1. A method of storing multi-dimensional data in a database management system in which data identified by a combination of members of a plurality of dimensions are stored in a memory unit and a query relating to said data is processed, comprising:

a step of grouping a collection of members constituting each dimension to determine a collection of member groups;

a step of assigning to said memory unit a memory area of a page index constituted by entries corresponding to each combination relating to said plurality of dimensions, of said member groups determined in said grouping step;

a step of inputting data to be stored in said memory unit;

a step of determining a set of member groups corresponding to said data inputted in said inputting step, from a set of members of dimensions specifying said data on the basis of said grouping of said grouping step;

a step of obtaining an entry corresponding to said set of member groups determined in said set determining step, from said page index having said memory area assigned in said assigning step;

a step of allotting a memory area of a page to said memory unit when a page number is not registered in said entry of said page index obtained in said obtaining step and registering said page number of said page in said entry of said page index; and

a step of pairing said data inputted in said inputting step and identification information of said data to store said paired data and identification information in said page having said page number registered in said page index entry obtained in said obtaining step.

2. A multi-dimensional data storing method according to claim 1, wherein

said grouping step comprises assigning a series of numerical coordinates to said members constituting each dimension and dividing said coordinates by sections to thereby group said members and assign a series of numerical coordinates to said member groups;

and

said assigning step comprises arranging each entry of said page index in order of a nest with respect to a set of numerical coordinates of said member group corresponding to said entry;

said grouping step comprising determining block coordinates which are the set of numerical coordinates of the corresponding member group from said set of members of dimensions specifying said input data;

said obtaining step comprising calculating a distance from the head of said page index on the basis of said block coordinates determined in said set determining step to thereby determine a memory location of said entry and obtain said entry.

3. A multi-dimensional data storing method according to claim 2, wherein said grouping step further comprises determining cell coordinates which are a set of numerical coordinates of members from said set of members of dimensions specifying said input data;

and

said pairing step further comprises coding said cell coordinates of said input data into numerical value to thereby determine said identification information of said data.

4. A multi-dimensional data storing method according to claim 2, wherein

said grouping step further comprises assigning to said members constituting each dimension, relative coordinates obtained by subtracting a minimum value of numerical coordinates of members belonging to the same group as said member from numerical coordinates of said member;

and

said grouping step further comprises determining relative cell coordinates which are a set of relative coordinates of members from said set of members of dimensions specifying said input data;

said pairing step further comprising coding said relative cell information of said input data into numerical value to thereby determine said identification information of said data.

5. A multi-dimensional data storing method according to claim 2, wherein

said grouping step further comprises assigning to said members constituting each dimension, relative coordinates obtained by subtracting a minimum value of numerical coordinates of members belonging to the same group as said member from numerical coordinates of said member;

and

said grouping step further comprises determining relative cell coordinates which are a set of relative coordinates of members from said set of members of dimensions specifying said input data;

said allotting step comprising allotting a memory area of pages of a first or second kind to said memory unit when said page number is not registered in said page index entry;

said pairing step comprising, when said page having said page number registered in said page index entry is a page of the first kind, pairing said input data and said identification information of said data to store said paired input data and identification information in said page and when said page is a page of the second kind, storing said input data in said page and arranging memory locations of said data in said page in order of a nest with respect to the relative cell coordinates of said data.

6. A multi-dimensional data storing method according to claim 5, wherein

said grouping step further comprises determining cell coordinates which are a set of numerical coordinates of members from said set of members of dimensions specifying said input data;

and

said pairing step further comprises coding said cell coordinates of said input data into numerical value to thereby determine said identification information of said data.

7. A multi-dimensional data storing method according to claim 5, wherein

said grouping step further comprises assigning to said members constituting each dimension, relative coordinates obtained by subtracting a minimum value of numerical coordinates of members belonging to the same group as said member from numerical coordinates of said member;

and

said grouping step further comprises determining relative cell coordinates which are a set of relative coordinates of members from said set of members of dimensions specifying said input data;

said pairing step further comprising coding said relative cell coordinates of said input data into numerical value to thereby determine said identification information of said data.

8. A method of retrieving multi-dimensional data in a database management system in which data identified by a combination of members of a plurality of dimensions are stored in a memory unit and a query relating to said data is processed, comprising:

a step of assigning a series of numerical coordinates to members constituting each dimension and dividing said coordinates by sections to group said members and assign a series of numerical coordinates to member groups obtained by said grouping;

a step of allotting to said memory unit, memory areas for page indexes constituted by entries corresponding to combinations relative to said plurality of dimensions, of said member groups determined in said numerical coordinate assigning step and in which said entries are arranged in order of a nest with respect to a set of numerical coordinates of said corresponding member group;

a step of inputting data to be stored in said memory unit;

a step of determining block coordinates which are a set of numerical coordinates of a member group corresponding to said data inputted in said data inputting step, from a set of members of dimensions specifying said data;

a step of calculating a distance from the head of said page indexes on the basis of said block coordinates determined in said block coordinate determining step to thereby determine a memory location of said page index entry corresponding to said block coordinates and obtain said entry;

a step of assigning a memory area of a page to said memory unit to register a page number of said page in said entry when the page number is not registered in said page index entry obtained in said calculating step;

a step of pairing said data inputted in said data inputting step and identification information of said data to store said paired data and identification information in the page having the page number registered in said page index entry obtained in said calculating step;

a step of inputting a retrieval condition represented by a combination of members of dimensions;

a step of determining block coordinates corresponding to said retrieval condition inputted in said retrieval condition inputting step from combinations of members of dimensions specifying retrieval data;

a step of making calculation of a distance from the head of said page index on the basis of said block coordinates determined in said corresponding block coordinate determining step to thereby determine a memory location of said page index entry corresponding to said block coordinates and obtain said entry; and

a step of obtaining from said memory unit the page having the page number registered in said page index entry obtained in said calculation making step and obtaining data having identification information corresponding to the retrieval data from said page.

9. A method of storing multi-dimensional data in a database management system including a plurality of processing nodes each having a CPU and a memory unit and interconnected through a communication network and in which data identified by a combination of members of a plurality of dimensions are stored in said memory units of said plurality of processing nodes and a query relating to said data is processed, comprising:

a step of assigning a series of numerical coordinates to members constituting each dimension and dividing said coordinates by sections to thereby group said members and assign a series of numerical coordinates to the obtained member groups;

a step of allotting to said memory units of said plurality of processing nodes, memory areas for page indexes constituted by entries corresponding to combinations relative to said plurality of dimensions, of said member groups determined in said numerical coordinate assigning step and in which said entries are arranged in order of a nest with respect to a set of numerical coordinates of said corresponding member group;

a step of inputting data to be stored in said memory units of said plurality of processing nodes;

a step of determining block coordinates which are a set of numerical coordinates of a member group corresponding to said data inputted in said data inputting step, from combinations of members of dimensions specifying said data;

a step of determining a processing node for storing said data inputted by said data inputting step on the basis of said block coordinates determined by said block coordinate determining step so that data positioned in adjacent different diagonal planes of block coordinate space are assigned to different processing nodes;

a step of, in regard to said processing unit determined in said processing node determining step, calculating a distance from the head of said page indexes of said processing node determined in said processing node determining step on the basis of said block coordinates determined in said block coordinate determining step to thereby determine a memory location of a page index entry corresponding to said block coordinates and obtain said entry;

a step of, in regard to said processing unit determined in said processing node determining step, assigning a memory area of a page to said memory unit of said processing node determined in said processing node determining step and registering a page number of said page in said page index entry obtained in said calculating step when the page number is not registered in said page index entry; and

a step of, in regard to said processing unit determined in said processing unit determining step, pairing said data inputted in said data inputting step and identification information of said data to store said paired data and identification information in said page having said page number registered in said page index entry obtained in said calculating step.

10. A method of retrieving multi-dimensional data in a database management system including a plurality of processing nodes each having a CPU and a memory unit and interconnected through a communication network and in which data identified by a combination of members of a plurality of dimensions are stored in said memory units of said plurality of processing nodes and a query relating to said data is processed, comprising:

a step of assigning a series of numerical coordinates to members constituting each dimension and dividing said coordinates by sections to thereby group said members and assign a series of numerical coordinates to the obtained member groups;

a step of allotting to said memory units of said plurality of processing nodes, memory areas for page indexes constituted by entries corresponding to combinations relative to said plurality of dimensions, of said member groups determined in said numerical coordinate assigning step and in which said entries are arranged in order of a nest with respect to a set of numerical coordinates of said corresponding member group;

a step of inputting data to be stored in said memory units of said plurality of processing nodes;

a step of determining block coordinates which are a set of numerical coordinates of a member group corresponding to said data inputted in said data inputting step, from combinations of members of dimensions specifying said data;

a step of determining a processing node for storing said data inputted by said data inputting step on the basis of said block coordinates determined by said block coordinate determining step so that data positioned in adjacent different diagonal planes of block coordinate space are assigned to different processing nodes;

a step of, in regard to said processing unit determined in said processing node determining step, calculating a distance from the head of said page indexes of said processing node determined in said processing node determining step on the basis of said block coordinates determined in said block coordinate determining step to thereby determine a memory location of a page index entry corresponding to said block coordinates and obtain said entry;

a step of, in regard to said processing unit determined in said processing node determining step, assigning a memory area of a page to said memory unit of said processing node determined in said processing node determining step and registering a page number of said page in said page index entry obtained in said calculating step when the page number is not registered in said page index entry; and

a step of, in regard to said processing unit determined in said processing unit determining step, pairing said data inputted in said data inputting step and identification information of said data to store said paired data and identification information in said page having said page number registered in said page index entry obtained in said calculating step;

a step of inputting a retrieval condition represented by a combination of members of dimensions;

a step of deciding block coordinates corresponding to said retrieval condition inputted in said retrieval condition inputting step from combinations of members of dimensions specifying retrieval data;

a step of determining a processing node for storing said retrieval data having said block coordinates determined in said block coordinate deciding step in accordance with an assignment method to said processing node of the memory data determined in said processing node determining step;

a step of, in regard to said processing node determined in said processing node determining step, making calculation of a distance from the head of said page index on the basis of said block coordinates determined in said block coordinate determining step to thereby determine a memory location of said page index entry corresponding to said block coordinates and obtain said entry; and

a step of, in regard to said processing node determined by said processing node determining step, obtaining from said memory unit of said processing unit the page having the page number registered in said page index entry obtained in said calculation making step and obtaining data having identification information corresponding to the retrieval data from said page.