Dynamic database structuring method and apparatus, and database clustering method and apparatus

• US 5,940,832 A
• Filed: 02/27/1995
• Issued: 08/17/1999
• Est. Priority Date: 03/10/1994
• Status: Expired due to Fees

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Fujitsu Limited
• Inventors: Hamada, Takeo, Azuma, Mitsuhiro, Iseda, Kohei, Chujo, Takafumi
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/394,798
• Time in Patent Office: 1,632 Days
• Field of Search: 395/600, 707/200, 707/205, 707/100, 707/101, 707/5, 707/6, 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A dynamic database structuring method includes the steps of (a) clustering transition probabilities among transactions by on-line, (b) forming a hyper graph representing the transition probabilities of the transactions clustered in the step (a) using weighting, (c) partitioning the hyper graph to obtain clustering information related to objects or records to be stored in a storage, and (d) reorganizing a database by rearranging data in the storage by on-line using the clustering information obtained in the step (c), thereby restructuring the database dynamically.

Claims

1. A dynamic database structuring method comprising the steps of:

(a) clustering transition probabilities among transactions according to statistical information of previously occurring on-line, transactions;

(b) forming a hyper graph representing the transition probabilities of the transactions clustered in said step (a) using weighting;

(c) partitioning said hyper graph to obtain clustering information including an optimum arrangement for objects or records to be stored in a database; and

(d) reorganizing the database by rearranging the object or records stored according to the clustering information obtained in said step (c), thereby restructuring the database dynamically.

2. The dynamic database structuring method as claimed in claim 1, which further comprises the steps of:

(e) successively updating the partitioning of said hyper graph based on correlation information that is indicative of correlation among the transactions and is obtained by forming said hyper graph.

3. The dynamic database structuring method as claimed in claim 2, wherein said database is selected from a group consisting of an object oriented database and a relational database.

4. The dynamic database structuring method as claimed in claim 1, wherein said database is selected from a group consisting of an object oriented database and a relational database.

5. The dynamic database structuring method as claimed in claim 1, wherein the clustering transition probabilities step includes storing transitions of transactions in a predetermined format.

6. The dynamic database structuring method as claimed in claim 5, wherein the clustering transition probabilities step further includes storing an additional transition for every new transaction started.

7. The dynamic database structuring method as claimed in claim 1, wherein the hyper graph is formed by calculating the transition probabilities among the transactions from statistical information clustered on line.

9. The database clustering method as claimed in claim 5, wherein said database is selected from a group consisting of an object oriented database and a relational database.

8. A database clustering method comprising the steps of:

(a) clustering transition probabilities among transactions according to statistical information of previously occurring on-line, transactions;

(b) forming a hyper graph representing the transition probabilities of the transactions clustered in said step (a) using weighting;

(c) partitioning said hyper graph to obtain clustering information including an optimum arrangement for objects or records to be stored in a database; and

(d) successively updating the partitioning of said hyper graph based on correlation information that is indicative of correlation among the transactions and is obtained by forming said hyper graph; and

(e) reorganizing the database by rearranging the objects or records stored according to the clustering information obtained in said step (c), thereby restructuring the database dynamically and automatically clustering the database.

10. A dynamic database structuring apparatus comprising:

storage means for storing a database;

a database management system, coupled to said storage means, managing the database;

clustering means, coupled to said database management system, for clustering transition probabilities among transactions according to statistical information of previously occurring on-line transactions; and

database reorganizing means, coupled to said database management system, comprising;

means for forming a hyper graph representing the transition probabilities of the transactions clustered in said clustering means using weighting,

means for partitioning said hyper graph to obtain clustering information including an optimum arrangement for objects or records to be stored in said storage means, and

means for reorganizing the database by rearranging the objects or records in said storage means according to the clustering information obtained in said partitioning means, thereby restructuring the database dynamically.

11. The dynamic database structuring apparatus as claimed in claim 10, wherein said database reorganizing means further comprises means for successively updating the partitioning of said hyper graph based on correlation information that is indicative of correlation among the transactions and is obtained by forming said hyper graph.

12. The dynamic database structuring apparatus as claimed in claim 11, wherein said database is selected from a group consisting of an object oriented database and a relational database.

13. The dynamic database structuring apparatus as claimed in claim 10, wherein said database is selected from a group consisting of an object oriented database and a relational database.

14. The dynamic database structuring apparatus as claimed in claim 10, wherein the clustering means includes second storage means for storing transactions of transactions in a predetermined format.

15. The dynamic database structuring apparatus as claimed in claim 10, wherein the clustering means stores an additional transition for every new transaction started.

16. The dynamic database structuring apparatus as claimed in claim 10, wherein the hyper graph forming means calculates transition probabilities among the transactions from statistical information clustered on line.

17. A database clustering apparatus adapted to cluster a database stored in a storage means, comprising:

a database management system managing the database;

clustering means, coupled to said database management system, for clustering transition probabilities among transactions according to statistical information of previously occurring on-line transactions; and

database reorganizing means, coupled to said database management system, comprising;

means for forming a hyper graph representing the transition probabilities of the transactions clustered in said clustering means using weighting,

means for partitioning said hyper graph to obtain clustering information including an optimum arrangement for objects or records to be stored in storage means.

means for successively updating the partitioning of said hyper graph based on correlation information that is indicative of correlation among the transactions and is obtained by forming said hyper graph, and

means for reorganizing the database by rearranging the objects or records in the storage means according to the clustering information obtained in said partitioning means, thereby restructuring the database dynamically and automatically clustering the database.

18. The database clustering apparatus as claimed in claim 17, wherein said database is selected from a group consisting of an object oriented database and a relational database.