Datebase Device, Database Management Method, Data Structure Of Database, Database Management Program, And Computer-Readable Storage Medium Storing Same Program

• US 20080091691A1
• Filed: 10/27/2005
• Published: 04/17/2008
• Est. Priority Date: 10/28/2004
• Status: Abandoned Application

• Current Assignee: University of Fukui
• Original Assignee: Kukui University of
• Inventors: Tsuji, Tatsuo
• Application Number:
  US11/666,121
• Publication Number:
  US 20080091691A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

When a record inserting section inserts a record having a new column value, the record inserting section registers the column value in a CVT such that an extendible array is extended; registers, in a history table, a history value indicating a chronological sequence of array extension; registers, in a coefficient table, coefficients of a linear function for calculating an offset of an element in an subarray; registers an initial value in a record number table; and inserts as a key value a 2-tuple expression of the history value and the offset of the element of the extendible array into RDT. This makes it possible to dynamically add, upon operation, a record having a new column value and to register only an existing record, thereby realizing a relational database allowing for fast record retrieval.

Claims

1. A database device using a relational table, comprising:

a database memory section for storing element location B⁺tree data registering, as key values, location information indicating locations of elements of an extendible array, which elements respectively correspond to records of the relational table,

the location information being information including (i) section location information indicating locations of first elements of sections of the extendible array to which the elements belong, and (ii) in-section offsets indicating the locations of the elements in the sections.

2. The database device as set forth in claim 1, wherein:

each of the sections is a subarray of the extendible array, and

the database memory section stores;

second B⁺tree data, which registers, as key values, 2-tuple expressions of history values and in-subarray offsets of the sections to which the elements, respectively corresponding to the records of the relational table, of the extendible array belong, the second B⁺tree data being the element location B⁺tree data, the history values being the section location information, the in-subarray offsets being the in-section offsets;

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into subscripts of the extendible array;

a history table, which registers chronological sequence of array extension;

a coefficient table, which registers, for each subarray, a coefficient vector made up of a coefficient of a linear function for calculating an in-subarray offset of an element in the subarray;

a record number table, which registers, for each of the subscripts of the extendible array, the number of all records that have a column value corresponding to the subscript.

3. The database device as set forth in claim 2, further comprising:

record retrieving means for retrieving, from the second B⁺tree data in response to a retrieval request, a 2-tuple of a history value and an in-subarray offset corresponding to the retrieval request.

4. The database device as set forth in claim 2, further comprising:

record inserting means for, upon inserting a record having a new column value, (i) registering the column value in the first B⁺tree data such that the extendible array is extended, (ii) registering a history value in the history table and registering a coefficient in the coefficient table, (iii) registering an initial value in the record number table, and (iv) inserting, into the second B⁺tree data as a key value, a 2-tuple expression of the history value and an in-subarray offset of an element of the extendible array.

5. The database device as set forth in claim 2, further comprising:

record deleting means for, upon deleting one record, (i) deleting a 2-tuple of a corresponding history value and a corresponding in-subarray offset from the second B⁺tree data and (ii) decrementing the number of records in the record number table by one.

6. The database device as set forth in claim 3, further comprising:

key value/column value reconverting means for converting the 2-tuple of the history value and the offset retrieved by the record retrieving means into a corresponding subscript of each dimension of the extendible array, and acquiring, in accordance with the subscript thus converted, either a column value or a pointer for a memory area in which the column value is stored, the column value or the pointer being stored in advance in each slot of the history table, the coefficient table, and the record number table of each dimension.

7. The database device as set forth in claim 2,

the database memory section further storing a unique key table registering (i) a unique key, which never has a duplicate column value, and (ii) a 2-tuple expression of a history value and an in-subarray offset of an element of the extendible array,

said database device, further comprising unique key managing means for managing a relation between the unique key and column values other than the unique key in accordance with the unique key table.

8. The database device as set forth in claim 7, further comprising:

a vertical splitting managing means for (i) splitting the relational table into two sets of columns so as to obtain split relational tables, (ii) respectively constructing extendible arrays for the split relational tables, (iii) respectively generating, for the split relational tables, second B⁺tree data which register pairs of history values and offsets, and (iv) generating a unique key table which registers (a) one or more unique key values that the relational table before being split had and (b) the pairs of history values and offsets stored in the second B+tree data corresponding to the split relational tables.

16. The database device as set forth in claim 1, wherein:

the extendible array is a chunked extendible array and each of the sections is a chunk of the chunked extendible array, and

the database memory section stores;

second B⁺tree data, which registers, as key values, 2-tuple expressions of chunk numbers and in-chunk offsets of the chunks to which the elements, respectively corresponding to the records of the relational table, of the chunked extendible array belong, the second B⁺tree data being the element location B⁺tree data, the chunk numbers being the section location information, the in-chunk offsets being the in-section offsets;

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into 2-tuple expressions of (i) subscripts indicating locations of chunk subarray information in the chunked extendible array and (ii) subscripts in the chunks;

a history table, which registers chronological sequence of chunked array extension as the chunk subarray information;

a coefficient table, which registers, for each chunk subarray, a coefficient vector made up of a coefficient of a linear function for calculating a chunk number of a chunk in the chunk subarray;

a column value table, which includes, as column value information, either a column value corresponding to each of the subscripts of the extendible array or a pointer for a memory area in which the column value is stored; and

a record number table, which registers the number of all records that have the column value.

17. The database device as set forth in claim 16, further comprising:

record retrieving means for retrieving, from the second B⁺tree data in response to a retrieval request, a 2-tuple of a chunk number and an in-chunk offset corresponding to the retrieval request.

18. The database device as set forth in claim 16, further comprising:

record inserting means for, upon inserting a record having a new column value, (i) registering the column value in the first B⁺tree data such that the chunked extendible array is extended, (ii) registering a history value in the history table and registering a coefficient in the coefficient table, (iii) registering an initial value in the record number table, and (iv) inserting, into the second B⁺tree data as a key value, a 2-tuple expression of the chunk number and an in-chunk offset of a chunk to which the element of the chunked extendible array belongs.

19. The database device as set forth in claim 16, further comprising:

record deleting means for, upon deleting one record, (i) deleting a 2-tuple of a corresponding chunk number and a corresponding in-chunk offset from the second B⁺tree data and (ii) decrementing the number of records in the record number table by one.

20. The database device as set forth in claim 17, further comprising:

key value/column value reconverting means for converting the 2-tuple of the chunk number and the in-chunk offset retrieved by the record retrieving means into a subscript of each dimension of the chunked extendible array, and acquiring, in accordance with the subscript thus converted, either a column value or a pointer for a memory area in which the column value is stored, the column value or the pointer being stored in advance in the column value table.

21. The database device as set forth in claim 16,

the database memory section further storing a unique key table registering (i) a unique key, which never has a duplicate column value, and (ii) a 2-tuple expression of a chunk number and an in-chunk offset of a chunk, to which an element belongs, of the chunked extendible array,

said database device, further comprising unique key managing means for managing a relation between the unique key and column values other than the unique key in accordance with the unique key table.

22. The database device as set forth in claim 21, further comprising:

a vertical splitting managing means for (i) splitting the relational table into two sets of columns so as to obtain split relational tables, (ii) respectively constructing chunked extendible arrays for the split relational tables, (iii) respectively generating, for the split relational tables, second B⁺tree data which register 2-tuple expressions of chunk numbers and in-chunk offsets, and (iv) generating a unique key table which registers (a) one or more unique key values that the relational table before being split had and (b) the 2-tuple expressions of chunk numbers and in-chunk offsets stored in the second B⁺tree data corresponding to the split relational tables.

27. A database management program for operating the database device as set forth in claim 3, and for causing a computer to function as the respective means.

28. A computer-readable storage medium storing the database management program as set forth in claim 27.

9. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into subscripts of an extendible array;

second B⁺tree data, which registers, as key values, 2-tuple expressions of history values and in-subarray offsets of elements, respectively corresponding to records of the relational table, of the extendible array;

a history table, which registers chronological sequence of array extension;

a coefficient table, which registers, for each subarray, a coefficient vector made up of a coefficient of a linear function for calculating an in-subarray offset of an element in the subarray; and

a record number table, which registers, for each of the subscripts of the extendible array, the number of all records that have a column value corresponding to the subscript,

said method, comprising the step of retrieving, from the second B⁺tree data in response to a retrieval request, a 2-tuple of a history value and an in-subarray offset corresponding to the retrieval request.

10. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into subscripts of an extendible array;

second B⁺tree data, which registers, as key values, 2-tuple expressions of history values and in-subarray offsets of elements, respectively corresponding to records of the relational table, of the extendible array;

a history table, which registers chronological sequence of array extension;

a coefficient table, which registers, for each subarray, a coefficient vector made up of a coefficient of a linear function for calculating an in-subarray offset of an element in the subarray; and

a record number table, which registers, for each of the subscripts of the extendible array, the number of all records that have a column value corresponding to the subscript,

said method, comprising the step of, upon inserting a record having a new column value, (i) registering the column value in the first B⁺tree data such that the extendible array is extended, (ii) registering a history value in the history table and registering a coefficient in the coefficient table, (iii) registering an initial value in the record number table, and (iv) inserting, into the second B⁺tree data as a key value, a 2-tuple expression of the history value and an in-subarray offset of an element of the extendible array.

11. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into subscripts of an extendible array;

second B⁺tree data, which registers, as key values, 2-tuple expressions of history values and in-subarray offsets of elements, respectively corresponding to records of the relational table, of the extendible array;

a history table, which registers chronological sequence of array extension;

a coefficient table, which registers, for each subarray, a coefficient vector made up of a coefficient of a linear function for calculating an in-subarray offset of an element in the subarray; and

a record number table, which registers, for each of the subscripts of the extendible array, the number of all records that have a column value corresponding to the subscripts,

said method, comprising the step of, upon deleting one record, (i) deleting a 2-tuple of a corresponding history value and a corresponding in-subarray offset from the second B⁺tree data and (ii) decrementing the number of records in the record number table by one.

12. A data structure for a database using a relational table, comprising:

first B+tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into subscripts of an extendible array;

second B+tree data, which registers, as key values, 2-tuple expressions of history values and in-subarray offsets of elements, respectively corresponding to records of the relational table, of the extendible array;

a history table, which registers chronological sequence of array extension;

a coefficient table, which registers, for each subarray, a coefficient vector made up of a coefficient of a linear function for calculating an in-subarray offset of an element in the subarray; and

a record number table, which registers, for each of the subscripts of the extendible array, the number of all records that have a column value corresponding to the subscript.

13. The data structure as set forth in claim 12, wherein:

the second B⁺tree data is provided for each dimension of the extendible array so as to manage, for each dimension, the 2-tuple expressions of the history values and the in-subarray offsets, which 2-tuple expressions serve as the key values.

14. The data structure as set forth in claim 12,

said data structure being used in an object-oriented database using a complex object,

wherein:

the complex object is an object having, as an object ID, a reference attribute for other instance objects,

attributes of a class are allocated to columns of the relational table, respectively, and

when a column is the object ID type attribute for making reference to other instance objects, the column has a column value that is an object ID of a record of the relational table to be referred and that is rendered such that a set type column corresponding to a set type attribute of the class is able to be handled separately from other simple type columns.

15. A data structure of a document data, using the data structure as set forth in claim 14, wherein:

the document data includes a tag element, which is allocated to a column of the relational table, and

when the tag element includes more than one tag element, the column has a column value that is an object ID of a record of the relational table to be referred, and meta information of a node in a tree graph expression of the document is allocated to the column of the relational table.

23. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into 2-tuple expressions of (i) subscripts indicating locations of chunk subarray information in the chunked extendible array and (ii) subscripts in the chunks;

second B⁺tree data, which registers, as key values, 2-tuple expressions of chunk numbers and in-chunk offsets of chunks to which elements, respectively corresponding to records of the relational table, of the chunked extendible array belong;

a history table, which registers chronological sequence of chunked array extension as chunk subarray information;

a coefficient table, which registers, for each chunked subarray, a coefficient vector made up of a coefficient of a linear function for calculating a chunk number of a chunk in the chunked subarray;

a column value table, which includes, as column value information, either a column value corresponding to each of the subscripts of the chunked extendible array or a pointer for a memory area in which the column value is stored; and

a record number table, which registers the number of all records that have the column value,

said method, comprising the step of retrieving, from the second B⁺tree data in response to a retrieval request, a 2-tuple of a chunk number and an in-chunk offset corresponding to the retrieval request.

24. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into 2-tuple expressions of (i) subscripts indicating locations of chunk subarray information in the chunked extendible array and (ii) subscripts in the chunks;

second B⁺tree data, which registers, as key values, 2-tuple expressions of chunk numbers and in-chunk offsets of chunks to which elements, respectively corresponding to records of the relational table, of the chunked extendible array belong;

a history table, which registers chronological sequence of chunked array extension as chunk subarray information;

a coefficient table, which registers, for each chunked subarray, a coefficient vector made up of a coefficient of a linear function for calculating a chunk number of a chunk in the chunked subarray;

a column value table, which includes, as column value information, either a column value corresponding to each of the subscripts of the chunked extendible array or a pointer for a memory area in which the column value is stored; and

a record number table, which registers the number of all records that have the column value,

said method, comprising the step of, upon inserting a record having a new column value, (i) registering the column value in the first B⁺tree data such that the chunked extendible array is extended, (ii) registering a history value in the history table and registering a coefficient in the coefficient table, (iii) registering an initial value in the record number table, and (iv) inserting, into the second B⁺tree data as a key value, a 2-tuple expression of the chunk number and an in-chunk offset of a chunk to which an element of the chunked extendible array belongs.

25. A database management method for a database device using a relational table,

the database device including a database memory section,

the database memory section storing:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into 2-tuple expressions of (i) subscripts indicating locations of chunk subarray information in the chunked extendible array and (ii) subscripts in the chunks;

second B⁺tree data, which registers, as key values, 2-tuple expressions of chunk numbers and in-chunk offsets of chunks to which elements, respectively corresponding to records of the relational table, of the chunked extendible array belong;

a history table, which registers chronological sequence of chunked array extension as chunk subarray information;

a coefficient table, which registers, for each chunked subarray, a coefficient vector made up of a coefficient of a linear function for calculating a chunk number of a chunk in the chunked subarray;

a column value table, which includes, as column value information, either a column value corresponding to each of the subscripts of the chunked extendible array or a pointer for a memory area in which the column value is stored; and

a record number table, which registers the number of all records that have the column value,

said method, comprising the step of, upon deleting one record, (i) deleting a 2-tuple of a corresponding chunk number and a corresponding in-chunk offset from the second B⁺tree data and (ii) decrementing the number of records in the record number table by one.

26. A data structure for a database using a relational table, comprising:

first B⁺tree data, which are so provided as to respectively correspond to column values of the relational table, and which convert the column values into 2-tuple expressions of (i) subscripts indicating locations of chunk subarray information in the chunked extendible array and (ii) subscripts in the chunks;

second B⁺tree data, which registers, as key values, 2-tuple expressions of chunk numbers and in-chunk offsets of chunks to which elements, respectively corresponding to records of the relational table, of the chunked extendible array belong;

a history table, which registers chronological sequence of chunked array extension as chunk subarray information;

a coefficient table, which registers, for each chunked subarray, a coefficient vector made up of a coefficient of a linear function for calculating a chunk number of a chunk in the chunked subarray;

a column value table, which includes, as column value information, either a column value corresponding to each of the subscripts of the chunked extendible array or a pointer for a memory area in which the column value is stored; and

a record number table, which registers the number of all records that have the column value.