US5058002A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Page splitting method and apparatus for a database stored in a plurality of memory storage units
Assignee: Mitsubishi Electric Corp
•
Filing: 1988-06-13
•
Granted: 1991-10-15
•
Expires: 2008-06-13
Abstract
Abstract In a data processing system for management of a relational data base stored among a plurality of disc storage units, a method and apparatus for horizontally partitioning a physical page on the basis of tuples includes a master processor, a master disc storage unit coupled to the master processor, a plurality of slave processors controlled by the master processor, and a plurality of slave disc storage units, one coupled to each of the slave processors. The master disc storage unit stores, in the form of a B-tree structure, a clustered index for either an attribute or a relation to be processed in the relational data base. The plurality of slave disc storage units store divisionally a relation in the data base which is partitioned on the basis of a page for a clustered index thereof in such a manner that the plurality of slave processors may execute, in parallel, a plurality of processings on a cluster of tuples, as defined in their range in connection with a given key value of the clustered index.
Inventors
- 👤 Shunichiro Nakamura
- 👤 Harumi Minemura
- 👤 Tatsuo Minohara
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 01:03
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F16/27; G06F16/28; G06F16/284; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
124 words
A method of storing a relation of a data base in pages of memory in a plurality of memory storage units by horizontally partitioning tuples of the relation, comprising the steps of: indexing said pages of memory with a cluster index stored in one of the memory storage units; determining when one of said pages of memory is filled with tuples; allocating at least one new page in at least one of the memory storage units; transferring a portion of the tuples from the memory of the full page to the at least one new page in the at least one memory storage unit; and reorganizing the cluster index to correspond to the at least one new page after the full page is partitioned.
Claim 2
Independent Claim
124 words
A method of storing a relation of a data base in pages of memory in a plurality of memory storage units by horizontally partitioning tuples of the relation, comprising the steps of: indexing said pages of memory with a cluster index stored in one of the memory storage units; determining when one of said pages of memory is filled with tuples; allocating at least one new page in at least one of the memory storage units; transferring a portion of the tuples from the memory of the full page to the at least one new page in the at least one memory storage unit; and reorganizing the cluster index to correspond to the at least one new page after the full page is partitioned.
Claim 3
Dependent Claim
28 words
A method as set forth in claim 1 wherein the portion of tuples transferred from the full page comprises one half of the tuples in the full page.
Claim 4
Dependent Claim
21 words
A method as set forth in claim 1 wherein at least one of the memory storage units comprises a magnetic disk.
Claim 5
Dependent Claim
41 words
A method as set forth in claim 1 wherein the at least one new page is allocated in said at least one memory storage unit currently containing fewer pages of tuples of the relation than others of said memory storage units.
Claim 6
Dependent Claim
195 words
A data processing system for managing data tuples organized into attributes of a relation which are stored in pages of memory, comprising: a master processor; a master memory storage means coupled to the master processor for storing a clustered index for the relation; a plurality of slave processors coupled to and controlled by the master processor; a plurality of slave memory storage means each slave memory storage means associated with and coupled to one of the slave processors for storing pages of data from the relation; means, within the master processor, for partitioning a first page of data stored in a first slave memory storage means into a plurality of pages when the first page becomes filled with data tuples by allocating at least one new page in at least one of the slave memory storage means, and transferring a portion of the tuples from the first page of the first slave memory means to the at least one new page of the at least one slave memory means; and means within the master processor, for reorganizing the clustered index to correspond to the at least one new page after said first page is partitioned.
Claim 7
Dependent Claim
195 words
A data processing system for managing data tuples organized into attributes of a relation which are stored in pages of memory, comprising: a master processor; a master memory storage means coupled to the master processor for storing a clustered index for the relation; a plurality of slave processors coupled to and controlled by the master processor; a plurality of slave memory storage means each slave memory storage means associated with and coupled to one of the slave processors for storing pages of data from the relation; means, within the master processor, for partitioning a first page of data stored in a first slave memory storage means into a plurality of pages when the first page becomes filled with data tuples by allocating at least one new page in at least one of the slave memory storage means, and transferring a portion of the tuples from the first page of the first slave memory means to the at least one new page of the at least one slave memory means; and means within the master processor, for reorganizing the clustered index to correspond to the at least one new page after said first page is partitioned.
Claim 8
Dependent Claim
23 words
A data processing system as set forth in claim 5 wherein the first page is partitioned into a second and a third page.
Claim 9
Dependent Claim
33 words
A data processing system as set forth in claim 6 wherein the first page is partitioned into second and third pages each containing one half of the data tuples from the first page.
Claim 10
Dependent Claim
51 words
A data processing system as set forth in claim 5 further comprising: means, within the master processor, for storing the at least one new page in the at least one slave memory storage means containing fewer pages of data tuples of the relation than others of said slave memory storage means.
Claim 11
Dependent Claim
18 words
A data processing system as set forth in claim 5 wherein the clustered index of a B-tree structure.
Claim 12
Dependent Claim
190 words
A data processing system for managing data tuples organized into attributes of a relation which is stored in pages of memory comprising: a master processor; a master magnetic disk memory unit coupled to the master processor for storing a B-tree clustered index for the relation; a plurality of slave processors coupled to and controlled by the master processor; a plurality of slave magnetic disk memory units; each slave memory unit being coupled to a respective one of the slave processors for storing pages of data tuples of the relation; means, within the master processor, for partitioning a first page of data stored in one of said slave memory units into second and third pages, each containing one half of the data from the first page, when the first page becomes filled with data tuples, the second page being stored in said one slave memory unit and the third page stored in another of said slave memory units containing pages of data tuples of the relation; and means, within the master processor for reorganizing the clustered index to correspond to the second and third pages after said first page is partitioned.
Claim 13
Dependent Claim
190 words
A data processing system for managing data tuples organized into attributes of a relation which is stored in pages of memory comprising: a master processor; a master magnetic disk memory unit coupled to the master processor for storing a B-tree clustered index for the relation; a plurality of slave processors coupled to and controlled by the master processor; a plurality of slave magnetic disk memory units; each slave memory unit being coupled to a respective one of the slave processors for storing pages of data tuples of the relation; means, within the master processor, for partitioning a first page of data stored in one of said slave memory units into second and third pages, each containing one half of the data from the first page, when the first page becomes filled with data tuples, the second page being stored in said one slave memory unit and the third page stored in another of said slave memory units containing pages of data tuples of the relation; and means, within the master processor for reorganizing the clustered index to correspond to the second and third pages after said first page is partitioned.
References Cited (Backward Citations)
US4412285A
Cited
US4445171A
Cited
US4543630A
Cited
US4468728A
Cited
US4432057A
Cited
US4611272A
Cited
US4606002A
Cited
US4677550A
Cited
US4635189A
Cited
US4769772A
Cited
EP0252234A2
Cited
US4774657A
Cited
US4922417A
Cited
US4930071A
Cited
US4930072A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-10-14 | 1995-04-15 | 1995-10-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-10-14 | 1999-04-15 | 1999-10-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-10-14 | 2003-04-15 | 2003-10-15 | $7700.00 | Window Closed / Lapsed |