|
|
|
Query processing (i.e., searching) |
Table format data presenting method, inserting method, deleting method, and updating method6973467
Abstract
A method to perform the insertion, deletion and updating of data in table-format data quickly and appropriately. A CPU 12 accepts a record number as a subscript, generates a subscript conversion array for giving an offset value corresponding to the range of the subscript in question, identifies the insertion position which indicates the position of the field value to be inserted, and, in the subscript conversion array, gives an offset value that defines the range of the corresponding subscript and also identifies the end of the array, and in the subscript conversion array, gives an offset value that increments the corresponding range of subscripts and also decrements the accepted subscript, and places the field value to be inserted at the stipulated end position, such that an offset value according to the range of subscripts within the subscript conversion array is given as the subscript.
Claims
1. A method of inserting table-format data where field values are inserted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said method of inserting table-format data comprises the steps of:
generating a subscript conversion array constituted such that the subscript conversion array accepts a storage position number specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said subscript,
identifying an insertion position that indicates the position of the field value to be inserted,
in said subscript conversion array, regarding said insertion position, giving an offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said array,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said insertion position, giving an offset value that shifts the corresponding range of subscripts upward and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said array,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
2. A method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said method of deleting table-format data comprises the steps of:
generating a subscript conversion array constituted such that the subscript conversion array accepts a storage position number array specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said accepted subscript,
identifying a deletion position that indicates the position of the field value to be deleted, and
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward and also increments the accepted subscript,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
3. A method of updating table-format data where field values are updated at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said method of updating table-format data comprises the steps of:
generating a subscript conversion array constituted such that subscript conversion array accepts a storage position number specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said accepted subscript,
(1) assuming the position of the field value to be updated to be the deletion position,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward and also increments the accepted subscript, and
(2) assuming the position of the field value to be updated to be the insertion position,
in said subscript conversion array, regarding said insertion position, giving an offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said array,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said insertion position, giving an offset value that shifts the corresponding range of subscripts upward and also decrements the accepted subscript, and
placing said field value to be updated at the stipulated position after the end of said array, and
said (1) and (2) or (2) and (1) are executed sequentially,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
4. A data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array.
5. The data structure according to claim 4 characterized in that each of said subscript conversion arrays comprises: a start position array consisting of start positions that indicate the minimum value of the subscripts contained within each of the stipulated ranges, and optionally an end position array consisting of end positions that indicate the maximum value of the subscripts contained in said stipulated range, and an offset array consisting of the corresponding offset values.
6. The data structure according to claim 4 characterized in that said value conversion array comprises: a start position array consisting of start positions that indicate the minimum value of the subscripts contained within each of the stipulated ranges, and optionally an end position array consisting of end positions that indicate the maximum value of the values contained in said stipulated range, and an offset array consisting of the corresponding offset values.
7. A method of inserting table-format data where field values are inserted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
said method of inserting table-format data comprises the steps of:
(1) regarding said value list,
identifying an insertion position that indicates the position of the field value to be inserted,
in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array,
in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
identifying an insertion position that indicates the position of the pointer value corresponding to the record number to be inserted,
in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list,
in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position.
8. The method of inserting table-format data according to claim 7 characterized in that:
the table comprises m record numbers and n field values,
when the insertion position for field values within said value list is i (0<=i<=n-1), a field value is placed at the end n of the first actual array, and the record number insertion position is j (0<=j<=m-1), a pointer value is placed at the end m of the second actual array,
(1) in the second subscript conversion array of said value list,
0 is given as the third offset value in the case that the value is in the range of (i-1) or less,
(n-1) is given as the third offset value in the case that the value is i, and
-1 is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array,
0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less,
(m-j) is given as the first offset value in the case that the subscript is j, and
(-1) is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and m or less,
(3) in the value conversion array of said pointer array,
0 is given as the second offset value in the case that the value is in the range of (i-1),
1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and
(i-n) is given as the second offset value in the case that the value is n.
9. The method of inserting table-format data according to claim 7 characterized in that:
the table comprises m record numbers and n field values,
when the insertion position for field values within said value list is i (0<=i<=n-1), a field value is placed at a stipulated position z (z>=n) after the end of the first actual array, and the record number insertion position is j (0<=j<=m-1), a pointer value is placed at a stipulated position x (x>=m) after the end of the second actual array,
(1) in the second subscript conversion array of said value list,
0 is given as the third offset value in the case that the value is in the range of (i-1) or less,
(z-1) is given as the third offset value in the case that the value is i, and
(-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array,
0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less,
(x-j) is given as the first offset value in the case that the subscript is j, and
(-1) is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and m or less, and also
(3) in the value conversion array of said pointer array,
0 is given as the second offset value in the case that the value is in the range of (i-1),
1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and
(i-y) is given as the second offset value in the case that the value is y (where y is the pointer value stored at the position x of the second actual array).
10. A transaction processing method characterized in that, when the insertion, deletion and/or updating of data in table-format data is performed by means of a method according to claim 7, and either a rollback or commit is performed, said subscript conversion array and value conversion array are discarded.
11. A transaction processing method characterized in that, when the insertion, deletion and/or updating of data in table-format data is performed by means of a method according to claim 7, and a rollback is performed, said subscript conversion array and value conversion array are discarded.
12. A method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
said method of deleting table-format data comprises the steps of:
regarding said pointer array,
identifying a deletion position that indicates the position of the pointer value to be deleted,
in said first subscript conversion array, regarding said insertion position, defining the corresponding subscript,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
13. The method of deleting table-format data according to claim 12 characterized in that:
the table comprises m record numbers and n field values,
when the record number deletion position is j (0<=j<=m-1),
in the first subscript conversion array of said pointer array,
0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, and
1 is given as the offset value in the case that the subscript is in the range of j or greater and (m-2) or less.
14. A method of updating table-format data where field values are updated at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
said method of updating table-format data comprises the steps of:
(A) (1) regarding said value list,
assuming the position of the field value to be updated to be the insertion position, identifying an insertion position that indicates the position of the field value to be inserted,
in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array,
in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
assuming the pointer value to be updated to be the pointer value to be inserted, identifying an insertion position that indicates the position of the pointer value to be inserted,
in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript,
placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list,
in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position,
(B) regarding said pointer array,
identifying the position of the pointer value to be updated as the deletion position, in consideration of said insertion position,
in said first subscript conversion array, regarding said deletion position, defining the corresponding subscript,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript, and
either of said (A) and (B) or said (B) and (A) are executed sequentially.
15. The method of updating table-format data according to claim 14 characterized in that:
the table comprises m record numbers and n field values,
when the updating position for field values within said value list is i (0<=i<=n-1), a field value is placed at the end n of the first actual array, and the record number updating position is j (0<=j<=m-1), a pointer value is placed at the end m of the second actual array,
(1) in the second subscript conversion array of said value list,
0 is given as the third offset value in the case that the value is in the range of (i-1) or less,
(n-1) is given as the third offset value in the case that the value is i, and
(-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array,
0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less,
(m-j) is given as the first offset value in the case that the subscript is j, and
0 is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and (m+1) or less,
(3) in the value conversion array of said pointer array,
0 is given as the second offset value in the case that the value is in the range of (i-1),
1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and
(i-n) is given as the second offset value in the case that the value is n.
16. The method of updating table-format data according to claim 14 characterized in that:
the table comprises m record numbers and n field values,
when the insertion position for field values within said value list is i (0<=i<=n-1), a field value is placed at a stipulated position z (z>=n) after the end of the first actual array, and the record number insertion position is j(0<=j<=m-1), a pointer value is placed at a stipulated position x (x>=m) after the end of the second actual array,
(1) in the second subscript conversion array of said value list,
0 is given as the third offset value in the case that the value is in the range of (i-1) or less,
(z-1) is given as the third offset value in the case that the value is i, and
(-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array,
0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less,
(x-j) is given as the first offset value in the case that the subscript is j, and
0 is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and (m+1) or less, and also
(3) in the value conversion array of said pointer array,
0 is given as the second offset value in the case that the value is in the range of (i-1),
1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and
(i-y) is given as the second offset value in the case that the value is y (where y is the pointer value stored at the position x of the second actual array).
17. A method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
said method of deleting table-format data comprises the steps of:
regarding said record number, providing a fourth actual array in which the record numbers themselves are placed, and a third subscript conversion array given stipulated offset values according to the range of subscripts for identifying said record number,
identifying a deletion position that indicates the position of said record number to be deleted,
in said third subscript conversion array, defining a corresponding subscript regarding said deletion,
in said third subscript conversion array, regarding those records having a value greater than the subscript corresponding to said deletion position, giving a fourth offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
18. A method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said method of deleting table-format data comprises the steps of:
regarding said record number, providing an array in which the record numbers themselves are placed, and a subscript conversion array given stipulated offset values according to the range of subscripts for identifying said record number,
identifying a deletion position that indicates the position of said record number to be deleted,
in said subscript conversion array, defining a corresponding subscript regarding said deletion, and
in said subscript conversion array, regarding those records having a value greater than the subscript corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
19. A parallel processing method where a plurality of processes are performed simultaneously on table-format data having a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
among the aforementioned processes, those that involve the insertion, deletion and/or updating of data are constituted such that, in said pointer array, they go through a first subscript conversion array, second actual array and value conversion array, and also, in said value list, they go through a second subscript conversion array and a first actual array, and
on the other hand, among the aforementioned processes, those that do not involve the insertion, deletion and/or updating of data are constituted such that, in said pointer array, they go through a second subscript conversion array, and also, in said value list, they go through a first actual array.
20. The parallel processing method according to claim 19 characterized in that said processes that involve the insertion, deletion and/or updating of data utilize a method of inserting table-format data where field values are inserted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array, wherein
said method of inserting table-format data comprises the steps of:
(1) regarding said value list,
identifying an insertion position that indicates the position of the field value to be inserted,
in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array,
in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
identifying an insertion position that indicates the position of the pointer value corresponding to the record number to be inserted,
in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list,
in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position.
21. A record locking method for table-format data having a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
an information block containing an array for controlling locking is provided, and field values corresponding to each of said record numbers that indicate the type of locking are placed within the array of said information block.
22. A computer-readable recording medium recorded with a data insertion program for table-format data where field values are inserted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein
said data insertion program for table-format data comprises the steps of:
generating a subscript conversion array constituted such that the subscript conversion array accepts a storage position number specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said subscript,
identifying an insertion position that indicates the position of the field value to be inserted,
in said subscript conversion array, regarding said insertion position, giving an offset value that defines the range of the corresponding subscript and also identifies the end of said array,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said insertion position, giving an offset value that shifts the corresponding range of subscripts upward and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said array,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
23. A computer-readable recording medium recorded with a data deletion program for table-format data where field values are deleted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein
said data deletion program for table-format data comprises the steps of:
generating a subscript conversion array constituted such that the subscript conversion array accepts a storage position number specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said accepted subscript,
identifying a deletion position that indicates the position of the field value to be deleted, and
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward and also increments the accepted subscript,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
24. A computer-readable recording medium recorded with a data updating program for table-format data where field values are updated at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein
said data updating program for table-format data comprises the steps of:
generating a subscript conversion array constituted such that the subscript conversion array accepts a storage position number specifying the position of the array of records as a subscript and gives an offset value corresponding to the range of said accepted subscript,
(1) assuming the position of the field value to be updated to be the deletion position,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward and also increments the accepted subscript, and
(2) assuming the position of the field value to be updated to be the insertion position,
in said subscript conversion array, regarding said insertion position, giving an offset value that defines the range of the corresponding subscript and also identifies the end of said array,
in said subscript conversion array, regarding those records having a storage position number greater than the storage position number corresponding to said insertion position, giving an offset value that shifts the corresponding range of subscripts upward and also decrements the accepted subscript, and
placing said field value to be updated at the stipulated position after the end of said array, and
said (1) and (2) or (2) and (1) are executed sequentially,
such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
25. A computer-readable recording medium recorded with a data insertion program for table-format data where field values are inserted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array,
wherein
said data insertion program for table-format data comprises the steps of:
(1) regarding said value list,
identifying an insertion position that indicates the position of the field value to be inserted,
in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array,
in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
identifying an insertion position that indicates the position of the pointer value corresponding to the record number to be inserted,
in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list,
in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position.
26. A computer-readable recording medium recorded with a data deletion program for table-format data where field values are deleted at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array
wherein
said data deletion program for table-format data comprises the steps of:
regarding said pointer array,
identifying a deletion position that indicates the position of the pointer value to be deleted,
in said first subscript conversion array, regarding said insertion position, defining the corresponding subscript,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
27. A computer-readable recording medium recorded with a data updating program for table-format data where field values are updated at arbitrary positions in table-format data represented by a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein the array of records is stored in a computer readable medium of a computer system, wherein
said data structure for table-format data comprises:
said table-format data constituted in a manner such that said table-format data is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order,
a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array, wherein
said data updating program for table-format data comprises the steps of:
(A) (1) regarding said value list,
assuming the position of the field value to be updated to be the insertion position, identifying an insertion position that indicates the position of the field value to be inserted,
in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array,
in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and
placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
assuming the pointer value to be updated to be the pointer value to be inserted, identifying an insertion position that indicates the position of the pointer value to be inserted,
in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript,
placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list,
in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position,
(B) regarding said pointer array,
identifying the position of the pointer value to be updated as the deletion position, in consideration of said insertion position,
in said first subscript conversion array, regarding said deletion position, defining the corresponding subscript,
in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript, and
either of said (A) and (B) or said (B) and (A) are executed sequentially.
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a data processing method and data processing apparatus for processing large amounts of data using a computer or other information processing apparatus, and particularly to the updating, deleting, inserting and transaction processing of table-format data that constitutes a database.
2. Description of the Prior Art
Databases are used for various applications, but the use of a relational database (RDB) which is able to eliminate logical contradictions has become the mainstream in medium-to large-scale systems. For example, an RDB may be used in an airline seat reservation system or the like. In this case, a key field may be specified to perform a quick search for targets (often a single target), or to confirm, cancel or change reservations.
However, in recent years, there has been a conspicuous trend for databases to be used not only for applications involving the simple management of individual data records as described above (mission-critical work), but also analysis (information-based work). For example, the owner of the aforementioned database may try to create cross tabulations in order to analyze how the seat vacancy rate varies depending on the time zone, route, season or the like.
However, with a conventional RDB, local memory is used to commit a transaction and confirm its content, so despite being suited to mission-critical work based mainly on transaction processing, it is not suited to the analysis of large-scale data (information-based work) from a structural standpoint. For example, if one wishes to perform a sort on an arbitrary field, theoretically this will take time on the order of n*log(n) (with n records), so processing efficiency is reduced the larger the scale of data. (In actual products, the drop in processing performance proceeds more rapidly than according to theory.) Moreover, this limitation (time=n*log(n)) appears not only in sorting but also in all general operations such as the extraction of partial sets (=searching).
Naturally, various methods of avoiding this limitation and increasing speed have been proposed. A good example of this is the bitmap index. A bitmap index is a bitmap wherein information as to whether or not each record satisfies a condition is represented by a single bit. For example, in the case of a "sex" field, a "male" bitmap and a "female" bitmap would be created. At this time, if one wishes to extract (search for) only the records of "females," it is possible to obtain that partial set (the set of records of females) quickly. However, it is not possible to create bitmaps for each value at all times. For example, in the case of a field (e.g. an ID number) that has one billion different values in a database of one billion records, it would be necessary to create one billion bitmaps, each of a size of one billion bits (approximately 125 MB). One can see that a bitmap index is only realistic for fields (e.g. sex) that have an extremely small number of variations. In addition, this method clearly cannot be applied instantly to partial sets, and it cannot be used in cases in which records are frequently inserted or deleted. Other techniques of increasing speed similarly have some kind of limitation. Because of such limitations in the applicable scope of these various technologies for increasing speed, operations that may appear to the user to be completely identical may be completed instantaneously or may take hours, so a serious problem of extreme discontinuity in processing time (difficulty of prediction) occurs.
For example, when times were measured with a currently commercially available RDB using a table having 10 million records in the entire set, it has been reported that hitting all records (=10 million records) took only 1 second, but hitting only 737 records required 61 seconds. Well then, how much processing time do you think it would take to hit 9 million records? It need not be said that the number of hits cannot be known prior to executing the search, so even if a function were known for the correspondence between the number of hits and the time required for a search, the time required cannot be predicted accurately. After all, even the theoretical basis is weak for assuming that the time required to extract 5 million records that satisfy the condition of being males (search time) is the same as the time required to extract 5 million records that satisfy the condition of being females (search time).
Such instability in performance is fatal particularly for real-time control systems. For example, large-scale, complex electrical power supply control systems wherein a plurality of power plants are connected to an extremely large number of electrical power customers via a power line network, or control systems for large-scale chemical plants are two of a large number of examples of systems that manage and use large amounts of data but cannot use databases.
Naturally, it is clear that even if their performance is stable, they are not usable if they are too slow, but what we would like to emphasize here is database systems can become horribly complex as a result of introducing various methods of increasing speed that are applicable only under special limited conditions, or they entail major problems such as the aforementioned extreme discontinuity in processing times.
Now, the aforementioned methods of statistical usage of databases have come into general use as described above, and at the same time, it is a known fact that the amounts of data processed are rapidly becoming larger and larger. In this situation, the data warehouse (DWH) and multidimensional database (MDB) have appeared in order to overcome the aforementioned problems.
The DWH may be thought of as an RDB from which transaction processing functions and the like have been removed and that is tuned to specialize in search and tabulation functions. Accordingly, the fundamental limitation of a processing time of n*log(n) remains as is, so the performance has not been adequately improved and the problem of discontinuity has also not been solved. Moreover, the unavoidable combination of an existing RDB for mission-critical work and DWH for information-based work results in a large increase in facilities investment and also gives rise to new problems including increased complexity of information management and added operating costs.
On the other hand, an MDB may be thought of as a system wherein foundation cross tabulations are prepared in advance based on a combination of specified fields (called dimensions), and the cross tabulations requested by the user are synthesized from the foundation cross tabulations. MDBs can synthesize cross tabulations with satisfactory response, but they also have many problems. For example, it is not possible to return to the original records (unless special manipulation is performed, because it is not possible to return to the original data from tabulations); it also cannot handle data such as stock prices that are updated over time (because the cross tabulations must be prepared in advance); and cross tabulations cannot be prepared on fields (dimensions) other than those specified in advance, among other problems. Naturally, the same problems as with a DWH of increased facilities investment and added complexity of information management also occur.
Looking at reality, the DWH and MDB are rarely introduced except for in fields where performance is emphasized regardless of cost, such as the aforementioned control systems and scientific and technical computations, financial engineering and the like. This is evidence that their functions and performance cannot stand up to actual use in the aforementioned fields.
In order to solve these problems, the present inventors have already invented a method of searching for, tabulating, sorting and joining table-format data (the linear filter method) at roughly 100-1000 times the speed as in the prior art, and have applied for a patent thereupon (Japanese Patent Application No. 10-227278) The linear filter method has many superior properties including high, stable processing performance, unity of processing, compactness and divisibility of data, an O(n) architecture, along with direct connectivity of sorts and suitability to pipeline and parallel processing.
Thus, the present invention has as its object to provide a method of inserting, deleting and updating data in table-format data using the aforementioned linear filter method, particularly wherein the insertion, deletion and updating of data is performed quickly and appropriately.
In addition, as is generally understood, actual update operations require the appropriate application of exclusive control whereby simultaneous access to the same data by multiple processes is controlled, and transaction processing wherein multiple processes are committed (or rolled back) as a single significant processing block.
To this end, the present invention has as an additional object to provide a method of inserting, deleting and updating table-format data wherein the aforementioned transaction processing is performed appropriately.
SUMMARY OF THE INVENTION
The object of the present invention is achieved by providing a method of inserting table-format data where field values are inserted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein said method of inserting table-format data is characterized in comprising the steps of: generating a subscript conversion array constituted such that it accepts a record number as a subscript and gives an offset value corresponding to the range of said subscript, identifying an insertion position that indicates the position of the field value to be inserted, in said subscript conversion array, regarding said insertion position, giving an offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said array, in said subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving an offset value that shifts the corresponding range of subscripts upward and also decrements the accepted subscript, and placing said field value to be inserted at the end of said array, such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
By means of the present invention, the subscript conversion array is used to give the stipulated offset to the subscripts and identify the field values of the array. Accordingly, in the case of insertion, by means of the subscript conversion array, the subscript corresponding to the newly inserted position can identify a new field value placed at a stipulated position after the end of the array. Accordingly, data is actually inserted into the array, so there is no need to move other data and thus field values can be logically inserted into the array. In addition, it is thereby possible to perform parallel processing and transaction processing as described later.
A further object of the present invention is achieved by providing a method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by an array of records containing a field and the field values contained therein, wherein said method of deleting table-format data is characterized in comprising the steps of: generating a subscript conversion array constituted such that it accepts a record number as a subscript and gives an offset value corresponding to the range of said accepted subscript, identifying a deletion position that indicates the position of the field value to be deleted, and in said subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving an offset value that shifts the corresponding range of subscripts downward and also increments the accepted subscript, such that an offset value according to the range of subscripts within the subscript conversion array is given as said subscript and the field value with the array is identified by means of the subscript given by said offset value.
In the present invention also, the subscript conversion array is used to make the field values corresponding to the position to be deleted not be pointed to by subscripts. Thus, the process of logical data deletion is achieved without deleting actual data and without moving data.
In addition, the method of deleting table-format data may be performed by executing the aforementioned method of updating and method of deleting sequentially or in reverse order.
In addition, in a different embodiment of the present invention, a value conversion method for table-format data that converts the values of field values in table-format data represented by an array of records containing a field and the field values contained therein is characterized in comprising the steps of: generating a value conversion array constituted such that it gives an offset value corresponding to the range of said field value, and being constituted such that it accepts a record number as a subscript and gives an offset value corresponding to the range of said field value to the field value corresponding to said subscript within said array.
A further object of the present invention is achieved by providing a data structure for table-format data constituted such that the field values corresponding to an arbitrary record number are identified in table-format data represented by an array of records containing a field and the field values contained therein, wherein said data structure for table-format data is characterized in that: said table-format data is constituted in a manner such that it is divided into one or more information blocks consisting of: a value list containing a first actual array in which the field values are stored in the order of a field value number corresponding to the field value belonging to a specified field, and a pointer array containing a second actual array in which pointer values for pointing to said field value numbers are stored in a unique record number order, a second subscript conversion array constituted such that an input, output of the pointer array is given as the subscript in said value list, and a third offset corresponding to the range of said subscript is given is formed and field value within the first actual array is identified by means of the output of the pointer array given by an offset via said second subscription conversion array.
By means of the present invention, for example, a certain process may form a data stream via the subscript conversion array and value conversion array, while another process may form a data stream that uses only the actual array. In this manner, if necessary, by setting either the passage or non-passage of said conversion array, parallel processing and transaction processing can be achieved appropriately.
For example, each of said subscript conversion arrays may comprise: a start position array consisting of start positions that indicate the minimum value of the subscripts contained within each of the stipulated ranges, and/or an end position array consisting of end positions that indicate the maximum value of the subscripts contained in said stipulated range, and an offset array consisting of the corresponding offset values. In addition, said value conversion array may comprise: a start position array consisting of start positions that indicate the minimum value of the subscripts contained within each of the stipulated ranges, and/or an end position array consisting of end positions that indicate the maximum value of the values contained in said stipulated range, and an offset array consisting of the corresponding offset values.
A still further object of the present invention is achieved by providing a method of inserting table-format data where field values are inserted at arbitrary positions in table-format data represented by the data structure defined above, wherein said method of inserting table-format data is characterized in comprising the steps of:
(1) regarding said value list:
identifying an insertion position that indicates the position of the field value to be inserted, in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array, in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array,
identifying an insertion position that indicates the position of the pointer value corresponding to the record number to be inserted, in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array, in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array,
in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list, in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position.
In a preferred embodiment of the aforementioned method of inserting table-format data: the table comprises m record numbers and n field values, and when the insertion position for field values within said value list is i (0<=i<=n-1: hereinafter "<=" means the left side is equal to or less than the right side, while ">=" means the left side is equal to or greater than the right side), a field value is placed at the end n of the first actual array, the record number insertion position is j (0<=j<=m-1), and a pointer value is placed at the end m of the second actual array,
(1) in the second subscript conversion array of said value list: 0 is given as the third offset value in the case that the value is in the range of (i-1) or less, (n-1) is given as the third offset value in the case that the value is i, and (-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array: 0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, (m-j) is given as the first offset value in the case that the subscript is j, and (-1) is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and m or less,
(3) in the value conversion array of said pointer array: 0 is given as the second offset value in the case that the value is in the range of (i-1), 1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and (i-n) is given as the second offset value in the case that the value is n.
Alternately, the table comprises m record numbers and n field values, and when the insertion position for field values within said value list is i (0<=i<=n-1), a field value is placed at a stipulated position z (z>=n) after the end of the first actual array, and the record number insertion position is j (0<=j<=m-1), a pointer value is placed at a stipulated position x (x>=m) after the end of the second actual array,
(1) in the second subscript conversion array of said value list:
0 is given as the third offset value in the case that the value is in the range of (i-1) or less, (z-1) is given as the third offset value in the case that the value is i, and (-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array: 0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, (x-j) is given as the first offset value in the case that the subscript is j, and (-1) is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and m or less, and also
(3) in the value conversion array of said pointer array: 0 is given as the second offset value in the case that the value is in the range of (i-1), 1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and (i-y) is given as the second offset value in the case that the value is y (where y is the pointer value stored at the position x of the second actual array).
In addition, another object of the present invention is achieved by a method of deleting table-format data where field values are deleted at arbitrary positions in table-format data represented by the data structure defined above, wherein said method of deleting table-format data is characterized in comprising the steps of: regarding said pointer array, identifying a deletion position that indicates the position of the pointer value to be deleted,
in said first subscript conversion array, regarding said insertion position, defining the corresponding subscript, in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
In a preferred embodiment of the aforementioned method of deleting table-format data: the table comprises m record numbers and n field values, and when the record number deletion position is j (0<=j<=m-1), in the first subscript conversion array of said pointer array: 0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, and 1 is given as the offset value in the case that the subscript is in the range of j or greater and (m-2) or less.
A still further object of the present invention is achieved by providing a method of updating table-format data where field values are updated at arbitrary positions in table-format data represented by the data structure defined above, wherein said method of updating table-format data is characterized in comprising the steps of:
(A) (1) regarding said value list:
assuming the position of the field value to be updated to be the insertion position, identifying an insertion position that indicates the position of the field value to be inserted, in said second subscript conversion array, regarding said insertion position, giving a third offset value that defines the range of the corresponding subscript and also identifies a stipulated position after the end of said first array, in said second subscript conversion array, regarding those records having a value greater than the subscript corresponding to said insertion position, giving a third offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, and placing said field value to be inserted at the stipulated position after the end of said first actual array,
(2) regarding said pointer array, assuming the pointer value to be updated to be the pointer value to be inserted, identifying an insertion position that indicates the position of the pointer value to be inserted, in said first subscript conversion array, regarding said insertion position, giving a first offset value that defines the corresponding subscript and also identifies a stipulated position after the end of said first actual array, in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said insertion position, giving a first offset value that shifts the corresponding range of subscripts upward so that the values that define said range become larger and also decrements the accepted subscript, placing a new pointer value greater than the existing pointer values at the stipulated position after the end of said second actual array, and
(3) regarding said pointer array, in said value conversion array, giving a second offset value that increments those records that have a value greater than the pointer value corresponding to the insertion position in said value list, in said value conversion array, giving a second offset value such that said new pointer value identifies a position corresponding to said insertion position,
(B) regarding said pointer array, identifying the position of the pointer value to be updated as the deletion position, in consideration of said insertion position, in said first subscript conversion array, regarding said deletion position, defining the corresponding subscript, in said first subscript conversion array, regarding those records having a record number greater than the record number corresponding to said deletion position, giving a first offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript, and
either of said (A) and (B) or said (B) and (A) are executed sequentially. In a preferred embodiment of the aforementioned method of updating table-format data: the table comprises m record numbers and n field values, and when the updating position for field values within said value list is i (0<=i<=n-1), a field value is placed at the end n of the first actual array, and the record number updating position is j (0<=j<=m-1), a pointer value is placed at the end m of the second actual array,
(1) in the second subscript conversion array of said value list: 0 is given as the third offset value in the case that the value is in the range of (i-1) or less, (n-1) is given as the third offset value in the case that the value is i, and (-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array: 0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, (m-j) is given as the first offset value in the case that the subscript is j, and 0 is given as the first offset value in the case that the subscript is in the range of (m+1) or greater and (m+1) or less,
(3) in the value conversion array of said pointer array: 0 is given as the second offset value in the case that the value is in the range of (i-1), 1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and (i-n) is given as the second offset value in the case that the value is n.
Alternately, the table comprises m record numbers and n field values, and when the insertion position for field values within said value list is i (0<=i<=n-1), a field value is placed at a stipulated position z (z>=n) after the end of the first actual array, and the record number insertion position is j (0<=j<=m-1), a pointer value is placed at a stipulated position x (x>=m) after the end of the second actual array,
(1) in the second subscript conversion array of said value list: 0 is given as the third offset value in the case that the value is in the range of (i-1) or less, (z-1) is given as the third offset value in the case that the value is i, and (-1) is given as the third offset value in the case that the value is in the range of (i+1) or greater and n or less,
(2) in the first subscript conversion array of said pointer array: 0 is given as the first offset value in the case that the subscript is in the range of (j-1) or less, (x-j) is given as the first offset value in the case that the subscript is j, and 0 is given as the first offset value in the case that the subscript is in the range of (j+1) or greater and (m+1) or less, and also
(3) in the value conversion array of said pointer array: 0 is given as the second offset value in the case that the value is in the range of (i-1), 1 is given as the second offset value in the case that the value is in the range of i or greater and (n-1) or less, and (i-y) is given as the second offset value in the case that the value is y (where y is the pointer value stored at the position x of the second actual array).
Alternately, the method of deleting table-format data defined above may comprise the steps of: regarding said record number, providing a fourth actual array in which the record numbers themselves are placed, and a third subscript conversion array given stipulated offset values according to the range of subscripts for identifying said record number, identifying a deletion position that indicates the position of said record number to be deleted, in said third subscript conversion array, defining a corresponding subscript regarding said deletion, in said third subscript conversion array, regarding those records having a value greater than the subscript corresponding to said deletion position, giving a fourth offset value that shifts the corresponding range of subscripts downward so that the values that define said range become smaller and also increments the accepted subscript.
This involves forming an information block containing a fourth actual array in which the record numbers themselves are placed, and a subscript conversion array for specifying the record number, and thus more substantial deletion of data is achieved.
In addition, another object of the present invention is achieved by a transaction processing method characterized in that, when the insertion, deletion and/or updating of data in table-format data is performed by means of the above method, and either a rollback or commit is performed, said subscript conversion array and value conversion array are discarded. In this case, said subscript conversion array and value conversion array may be discarded only when a rollback is performed.
In addition, another object of the present invention is achieved by a parallel processing method where a plurality of processes are performed simultaneously on table-format data having the data structure defined above, wherein among the aforementioned processes, those that involve the insertion, deletion and/or updating of data are constituted such that, in said pointer array, they go through a first subscript conversion array, second actual array and value conversion array, and also, in said value list, they go through a second subscript conversion array and a first actual array, and on the other hand, among the aforementioned processes, those that do not involve the insertion, deletion and/or updating of data are constituted such that, in said pointer array, they go through a second subscript conversion array, and also, in said value list, they go through a first actual array.
These processes that involve the insertion, deletion and/or updating of data may utilize one of the aforementioned methods of inserting, deleting or updating table-format data.
Alternately, in still another embodiment of the present invention, a record locking method for table-format data having the aforementioned data structure is such wherein an information block containing an array for controlling locking is provided, and field values corresponding to each of said record numbers that indicate the type of locking are placed within the array of said information block.
In addition, an object of the present invention is also achieved by a computer-readable recording medium recorded with a program for implementing one of the various methods described above.
BRIEF EXPLANATION OF THE DRAWINGS
This and other objects of the present invention will be made clear in reference to the appended drawings and embodiments. Here:
FIG. 1 is a block diagram showing the hardware configuration of a computer system that is able to implement the retrieval, tabulation and search methods according to an embodiment of the present invention.
FIG. 2 is a diagram illustrating an information block used in an embodiment of the present invention.
FIGS. 3A-3D are diagrams illustrating an example of table-format data, and an example of an information block based on this table-format data.
FIG. 4 is a diagram illustrating another example of table-format data, and an example of an information block based on this table-format data.
FIG. 5 is a flowchart showing the method of searching on a single field.
FIG. 6 is a flowchart used to describe the process of creating an information block based on table-format data.
FIGS. 7A and 7B, respectively, are diagrams showing an example of original data used for creating an information block.
FIGS. 8A and 8B are diagrams showing an example of inserting elements into an array and an example of updating the elements of an array, respectively.
FIGS. 9A through 9D are diagrams used to describe the subscripts, arrays and values from arrays, and an overview of subscript conversion and value conversion according to the present invention, respectively.
FIGS. 10A through 10C are diagrams used to describe the logical input/output relationships related to insertion of elements and the insertion of elements into an array according to Embodiment 1.
FIG. 11 is a flowchart illustrating the process of specifying an element within an array from the subscript according to Embodiment 1.
FIG. 12 is a diagram used to explain the insertion of a certain element to a specified position.
FIG. 13 is a flowchart illustrating the process of generating a subscript conversion array for inserting elements in this embodiment.
FIG. 14 is a diagram illustrating one example of the subscript conversion array generated by means of the process of FIG. 13.
FIGS. 15A through 15C are diagrams used to describe the logical input/output relationships related to deletion of elements and the deletion of elements from an array according to Embodiment 1.
FIGS. 16A and 16B are diagrams used to explain the deletion of a certain element at a specified position in Embodiment 1.
FIG. 17 is a flowchart illustrating the process of generating a subscript conversion array for deleting elements in this embodiment.
FIGS. 18A and 18B are diagrams illustrating how the numerical values within the conversion array change according to the process of FIG. 17.
FIG. 19 is a diagram used to describe the state in the case that insertion and deletion are performed sequentially in Embodiment 1.
FIG. 20 is a diagram used to describe the state in the case that insertion and deletion are performed sequentially in Embodiment 1.
FIGS. 21A through 21C are diagrams used to describe the structure of the conversion array according to Embodiment 2 of the present invention.
FIG. 22 is a diagram used to describe the actual array and difference array according to Embodiment 3 of the present invention.
FIGS. 23A and 23B are diagrams used to describe an overview of a value conversion array according to Embodiment 4 of the present invention.
FIG. 24 is a flowchart illustrating the process of value conversion according to Embodiment 4 of the present invention.
FIG. 25 is a flowchart illustrating the process of generating a value conversion table according to Embodiment 4 of the present invention.
FIGS. 26A and 26B are diagrams used to describe the state in the case that the conversion of values within the actual array is executed in Embodiment 4 of the present invention.
FIG. 27 is a diagram illustrating one example of a data structure that combines a subscript conversion array and value conversion array according to the present invention.
FIGS. 28A through 28D are diagrams illustrating the structure of various information blocks in Embodiment 5 of the present invention.
FIGS. 29A and 29B are diagrams used to describe the process of deleting a specific record in Embodiment 5 of the present invention.
FIGS. 30A and 30B are diagrams used to describe the process of deleting a specific record in Embodiment 5 of the present invention.
FIGS. 31A and 31B are diagrams used to describe the process of deleting a specific record in Embodiment 5 of the present invention.
FIG. 32 is a diagram used to describe the process of deleting a specific record in Embodiment 5 of the present invention.
FIGS. 33A and 33B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIG. 34 is a diagram used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 35A and 35B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 36A and 36B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 37A and 37B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 38A and 38B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 39A and 39B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIGS. 40A and 40B are diagrams used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIG. 41 is a diagram used to describe the process of inserting a specific record into a specific position in Embodiment 5 of the present invention.
FIG. 42 is a diagram used to describe the process of deleting a specific record in Embodiment 6 of the present invention.
FIG. 43 is a flowchart illustrating transaction processing utilizing the present invention.
FIG. 44 is a diagram used to describe the parallel processing of a plurality of processes utilizing the present invention.
FIG. 45 is a diagram used to describe exclusive control utilizing the present invention.
FIGS. 46A and 46B are flowcharts used to describe the data insertion process for table-format data in the form of information blocks in the present invention.
FIG. 47 is a diagram used to describe the data insertion process for table-format data in the form of information blocks in the present invention.
FIG. 48 is a diagram used to describe the data deletion process for table-format data in the form of information blocks in the present invention.
FIG. 49 is a diagram used to describe another practical example of a subscript conversion array according to the present invention.
FIG. 50 is a diagram used to describe a further practical example of a value conversion array according to the present invention.
FIG. 51 is a diagram used to describe a further practical example of a subscript conversion array and value conversion array according to the present invention.
FIG. 52 is a diagram used to describe another example of the data insertion process in table-format data in the form of information blocks according to the present invention.
FIG. 53 is a diagram used to describe the data updating process in table-format data in the form of information blocks according to the present invention.
FIG. 54 is a diagram used to describe another example of the data updating process in table-format data in the form of information blocks according to the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Here follows a description of the embodiments of the present invention made with reference to the appended drawings. FIG. 1 is a block diagram showing the hardware configuration of a computer system that is able to implement the method of inserting, deleting and updating of the data of a certain field of table-format data according to an embodiment of the present invention. As shown in FIG. 1, this computer system 10 has the same configuration as that of an ordinary computer, consisting of a CPU 12 which controls the entire system and its individual components by executing a program, random access memory (RAM) 14 which stores working data and the like, read only memory (ROM) 16 which stores programs and the like, hard disk or other fixed storage device 18, CD-ROM drive 20 for accessing a CD-ROM 19, interface (I/F) 22 provided for the CD-ROM drive 20 and external terminals connected to an external network (not shown), a keyboard, mouse or other input device 24 and a CRT display device 26. The CPU 12, RAM 14, ROM 16, external storage medium 18, interface 22, input device 24 and CRT display device 26 are connected to each other via a bus 28.
According to the embodiment, the program for inserting data in a certain field of table-format data, program for deleting data in a certain field, program for updating the data in a certain field, program for implementing transaction processing, program that controls parallel processing and program for implementing exclusive control may be contained on the CD-ROM 19 and read by the CD-ROM drive 20, or stored in advance in ROM 16. In addition, once read from the CD-ROM 19, the program may also be stored in a specific area of the external storage medium 18. Alternately, the aforementioned programs may also be supplied from outside via the network (not shown), external terminals or interface 22. Note that in this Specification, the insertion of data is defined to refer to both inserting data between adjacent records and adding new records to the end of the records.
In addition, in this embodiment, in order to implement the insertion, deletion and updating of data, along with transaction processing, parallel processing and exclusive control appropriately and quickly, as described later, it is necessary to generate an information block of a stipulated data format. This information block generation program may be similarly contained on CD-ROM 19, stored in ROM 16, or stored on the external storage medium 18. Alternately, these programs may also naturally be supplied from outside via the network (not shown). In addition, in this embodiment, the data (information blocks) generated by the aforementioned information block generating program that generates the information blocks are stored in RAM 14 or in a specific area of the external storage medium 18.
Next, we shall briefly describe the handling of table-format data prerequisite to the present invention, namely the form in which table-format data is managed. In order to achieve high-speed searching, tabulating and sorting of table-format data, and in order to join a plurality of tables of table-format data in the desired manner, the present inventors thought of the construction of table-format data that has a specific data format (Japanese Patent Application No. 10-227278) and a method of joining table-format data which has said specific data format (Japanese Patent Application No. 11-151156). In the present invention also, fundamentally, table-format data is constructed based on the techniques disclosed in this applications as a stipulated set of information blocks and searching, tabulating and sorting are performed using them.
FIG. 2 is a diagram illustrating an information block used in an embodiment of the present invention. As shown in FIG. 2. an information block 100 contains a value list 110 and an array of pointers to the value list 120. The value list 110 is a table containing, for each of the fields of table-format data, field values 111 corresponding to field value numbers in the order of the field value numbers which are assigned (integrally assigned) based on the field values belonging to that field. The array of pointers to the value list 120 is an array containing the field value number of a column (namely a field) in the table-format data, or namely pointers to the value list 110 in the table-format data record number order.
By combining the aforementioned array of pointers to the value list 120 and value list 110, given a certain record number, it is possible to get the field value number stored corresponding to that record number from the array of pointers to the value list 120 for a certain field, and then get the field value stored corresponding to that field value number within the value list 110, and thus obtain the field value from the record number. Accordingly, it is possible to refer to all data (field values) using the record number (row) and field (column) in the same manner as a conventional data table.
For example, consider the table-format data shown in FIG. 3A. In this example, various field values are given to the fields of Customer ID, Customer name and Telephone number. In this embodiment, such table-format data is stored as information blocks of the format indicated in FIGS. 3B through 3D. For example, in FIG. 3B, pointer array 120-1 is associated with value list 110-1 which contains the field values indicating the Customer ID. To wit, the pointer value of the pointer array for the first record (record number "0") is 0, and the corresponding field value of "1" indicating the Customer ID is obtained. In FIG. 3C, pointer array 120-2 is associated with value list 110-2 which contains the field values indicating the Customer name. For example, the pointer value of the pointer array for the first record (record number "0") is 5, and the corresponding field value of "Smith" indicating the Customer name is obtained. In FIG. 3D also, one can see that pointer array 120-3 is similarly associated with value list 110-3 which contains the field values indicating the Telephone number. In addition, one can also see that the field values are applied in sequential order (ascending order in this example) in each value list.
Moreover, in this embodiment, the value control table of information block 100 contains the value list 110 along with a category number flag array used for searches and tabulation, a start position array that indicates the starting address of the memory space to store pointers corresponding to the field values, and the count array. The various flags of the category number flag array and the counts of the count array are each associated to a field value. The flag values of the category number flag array are normally "0" but are set to "1" corresponding to field values to be found at the time of searching and tabulation. In addition, the count corresponds to the number of records that have that field value. Note that the start position corresponds to the one found by adding the count corresponding to the point value smaller than the corresponding pointer value, and need not necessarily be provided.
FIG. 4A is a diagram illustrating another example of table-format data, while FIGS. 4B and 4C are diagrams illustrating information blocks regarding "sex" and "age." As shown in FIG. 4B, the value control table 210-1 of the information block regarding sex 200-1 contains the field values corresponding to the various pointer values ("Male" and "Female") of pointer array 220 and category numbers, start positions and counts corresponding to the various field values. For example, the number of records in which the pointer value is "0" (namely, the field value in the value list is "Male") is 632564, and on the other hand, the number of records in which the pointer value is "1" (namely, the field value in the value list is "Female") is 367436. In addition, the start positions corresponding to the various field values indicate the starting address in the array of pointers to records 230-1 (to be described later). One can see that the same goes for FIG. 4C.
Here follows a description of one example of a search using an information block having such a data structure and the process of generating the information block. FIG. 5 is a flowchart showing the method of searching on a single field. This process is implemented by the CPU 12 (see FIG. 1) executing a stipulated search program. In this example, we shall search for records in which the value of the "age" field is 16 or 19. First, among the information blocks regarding table-format data, the information block regarding "age" 200-2 shown in FIG. 4C is specified (Step 501).
Next, in the value list 210-2 of the information block thus specified (hereinafter referred to as the "specified information block"), "1" is set as the category number of rows in which the field value matches the aforementioned search conditions (16 or 19) (Step 502). In the case of this example, "1" is set as the category number of rows corresponding to a field value number of "0" or a field value of "3." Next, the start position and count corresponding to rows in which the category number is set to "1" are obtained (Step 503). This information is called the pointer fetch information. In the array of pointers to records, based on the pointer fetch information obtained in Step 503, record numbers that indicate pointers to records that match the search conditions are obtained (Step 504). In this example, one can see that the record pointers corresponding to the field value number of "0" are stored in a region of the array of pointers to records from the start position of "0," or namely the beginning, to a position sufficient to contain 45898 pointers. On the other hand, the record pointers corresponding to the field value number of "3" are stored in a region of the array of pointers to records from the 2383137th pointer to a position sufficient to contain 189653 pointers. Finally, in order for it to be used in subsequent processing, an array of fetched record numbers is created as a result set and this is saved (Step 505).
In addition, tabulation and sorting can also be implemented by utilizing the category number, start position and count.
Here follows a description of the process of generating the information blocks used for the aforementioned search processes and the like. FIG. 6 is a flowchart used to describe the process of creating an information block based on table-format data. First, the system 10 gets table-format original data and categorizes this by field (Step 601). This original data may be that as shown in FIG. 7A or that as shown in FIG. 7B. These original data may be supplied from outside or may be stored in the external storage medium 18. A processing block 610 consisting of Step 602 through Step 604, to be described later, generates an information block regarding a single field. Accordingly, when generating information blocks regarding a plurality of fields, the processing corresponding to processing block 610 is executed the same number of times as the number of fields. Here follows a description of the generation of the information block regarding "sex" as an example.
First a region is allocated in RAM 14 for the information block regarding the "sex" field (Step 602). Next, a value control table is generated in this allocated region. To be more specific, the value control table is initialized. Next, within the original data, all data regarding "sex" is operated upon from the start to end to find how many instances of which field names are present. In this example, the field names "Female" and "Male" were found 367436 and 632564 times, respectively. Thus the field values of "Female" and "Male" are set in the value list and the appropriate numbers were also set in the Count column. Thereafter, the field values are sorted according to the appropriate standard. At the time of sorting, the counts are also reordered as the field numbers are reordered. Next, the values of the Start position column are determined. These are found by taking the sum of the Counts in the positions higher than that row in the sort. In addition, the value of the Start position column is assigned to the value of the corresponding Category number column. This value is used in the next step. After the value control table is generated in this manner, the array of pointers to records is generated. The size of the region for this pointer array corresponds to the overall total of the counts.
In this manner, it is possible to create an information block for the appropriate field. By performing this generation of information blocks in advance, the information blocks thus generated are used to perform the processes of searching, tabulation and sorting.
Next, we shall describe the process of inserting, deleting or updating elements in an information block of the aforementioned form.
For example, consider the case of inserting one element in a position second from the start of an array of a size of 1 million records (record numbers 0-999,999). For example, there is the case of inserting one new element between record numbers "0" and "1" among the array corresponding to the record numbers 0-999,999 (see FIG. 8A). In this case, a new value (e.g. "10") is inserted in the new record number "1" and the remaining values (namely, a total of 999,999 values) must each be moved one down. In addition, in the case of deleting a specific element also, it is necessary to move a huge number of elements. Alternately, in the case of rewriting elements in the aforementioned array that have a specific value, for example, incrementing those that have a value of I or greater (see FIG. 8B), it is necessary to scan the entire array so processing takes a huge amount of time.
In passing, the aforementioned array has an advantage in that a subscript indicates the position within the array, so it is possible to extract the value stored in the corresponding position (namely, reference the value stored from the subscript). To wit, if the various elements (stored values) are stored in address order in memory, then the address can be calculated immediately from the subscript and obtain the expanded value of the corresponding address. To this end, a technique that minimizes the load required for insertion and deletion of elements (stored values) while still maintaining this advantage is desirable.
According to the present invention, as shown in FIG. 9A, in a system wherein a subscript is given to an array to fetch the corresponding value (stored value), as shown in FIGS. 9B through 9D, by providing a subscript converter that converts the "subscript" given to the array and/or a value converter that converts the value fetched from the array, and also dividing the array itself into an actual array and difference array, it is possible to perform the insertion, deletion and updating of elements without changing the positions of elements (stored values) contained within the array, and without changing the values themselves.
[Insertion of Elements by Means of a Subscript Conversion Array]
First, we shall describe a subscript conversion array for the insertion of elements, etc. which is used in Embodiment 1 of the present invention. Considering the information block shown in FIGS. 2-4, subscripts may include the record number for specifying elements of the array of pointers to the value list (pointer values), or pointer values within the pointer array for specifying field values of the value list. In addition, the arrays may include arrays of pointers to value lists, value lists, and arrays of pointers to record numbers or the like.
For example, as shown in FIG. 10A, consider the case of inserting the element "Y0" between the 0th row (subscript "0") and the 1st row (subscript "1"). In this case, after the insertion of the element "Y0," the subscripts and the elements within the array (stored values) have the logical relationship shown in FIG. 10B.
In order to maintain the logical relationship shown in FIG. 10B while minimize the load arising from insertion, consider the subscript conversion array shown in FIG. 10C. In FIG. 10C, the subscript conversion array consists of a starting position array, ending position array and offset array. Among the elements (values) contained within these arrays, those at the same position (e.g., the 0th row, 1st row, etc.) are associated to each other. The range of subscripts to be associated is defined by the elements within the starting position array and the corresponding elements within the ending position array. To wit, the elements within the starting position array indicate the minimum values of the subscripts to be associated, while the elements within the ending position array indicate the maximum values of the subscripts to be associated. On the other hand, the corresponding elements within the offset array indicate the offset values for obtaining the converted subscript which is added to or subtracted from the subscript to specify the real actual array. Note that in this Specification, a set of corresponding elements within the starting position array, ending position array and offset array (namely, a set of elements positioned on the same rows) is called a "structure array" depending on the case, and the elements within the various arrays are called "structure members."
Here follows a description of the meaning of this subscript conversion array. As described above, the structure members within the structure array determine the range of subscripts and the offset values of subscripts included within this range. Thus, for a certain subscript, by identifying a structure array to be associated to that subscript and adding an offset value, it is possible to obtain converted subscripts, and these can be used to identify the position of arrays (actual arrays) and look up elements (stored values) within the array.
For example, in FIG. 10C, one can see that the subscript "0" is associated with the structure array of row 0 (the first row). In this structure array, the member value (offset value) within the offset array is "0" so the converted subscript is "0+0"=0. Accordingly, one can see that the element within the actual array corresponding to the original subscript of "0" is stored at the position "0." In addition, the subscript "1" is associated with the structure array of row 1 (the second row), and the member value (offset value) within the offset array is "n-1" so the converted subscript is "1+(n-1)=n." Accordingly, one can see that the element within the actual array corresponding to the original subscript of "0" is stored at the position "0." For the subscripts "2" through "n" also, it is clear that the position at which the corresponding element is stored can be identified in the same manner.
More specifically, we shall describe the aforementioned procedure with reference to the flowchart of FIG. 11. First, a number that indicates the position of the subscript (the storage position number) is initialized (Step 1101), and next, the elements of the starting array and ending array are looked up and the range containing the subscript is identified from among the ranges which are demarcated by values of the starting position array and ending position array (Step 1102). To wit, this step identifies the structure array to which the subscript is associated. For example, in the example of FIG. 10C, one can see that the subscript "0" is contained within the range identified by the element "0" within the starting array and the element "0" within the ending array. Also, one sees that the subscript "1" is contained within the range identified by the element "1" within the starting array and the element "1" within the ending array.
Next, based on this range, the corresponding offset value is fetched (Step 1103), and the value found by adding the offset value to the subscript is obtained (Step 1104). This value to which the offset is added becomes the converted subscript, so this value is used to identify an element within the actual array (Step 1105). With regard to subscript "1" for example, this subscript is contained within the range corresponding to row 1 (the second row), so the offset value of row 1 which is "n-1" is added to the subscript "1." Accordingly, the converted subscript becomes "n" so it is possible to obtain "Y0" as the corresponding element (stored value) within the actual array. Also, with regard to subscript "2," this subscript is contained within the range corresponding to row 2 (the third row), so the offset value of row 2 which is "-1" is added to the subscript "2."Accordingly, the converted subscript becomes "1" so it is possible to obtain "X1" as the corresponding element (stored value) within the actual array.
By repeating the process of Steps 1102 through 1105 for the required subscripts (see Steps 1106 and 1107), it is possible to maintain the logical relationship shown in FIG. 10B while obtaining the elements (stored values) within the actual array. Accordingly, with the present invention, at the time of insertion of elements (stored values) within an array, by generating a conversion array as described above, it is possible to achieve the insertion of elements without moving the elements themselves within the arrays, and arrange the elements to be inserted at a stipulated position in the actual array (e.g., a position corresponding to the maximum value of the address) without causing excessive loads.
[Generation of a Subscript Conversion Array for Insertion of Elements]
Next, we shall describe the procedure for creating the aforementioned subscript conversion array according to Embodiment 1. For example, as shown in FIG. 12, consider an array of 5 elements (symbol 1201), and consider the case of inserting a new element (stored value) "Y0" between row 0 (the first row) and row 1 (the second row) (see symbol 1202). FIG. 13 is a flowchart used to describe the process of generating a conversion array for inserting new elements (stored values) in the array. This process is executed by the CPU 12 in FIG. 1. First, an initialized subscript conversion array is generated (Step 1300). More specifically, the number of elements in the array is examined and the start position and end position are determined. For example, in the example shown in FIG. 12, the number of elements is "5" so in the initial subscript conversion array the start position is "0" and the end position is "4." In addition, in this example, the elements in the array are referenced directly from the substrate, so the initial offset value is "0" (see symbol 1401 of FIG. 14). Note that in the case in which a substrate conversion array had been generated in advance, namely the case in which one or more insertions had already been performed, or in the case in which an initial subscript conversion array is generated at the time of generation of the information block, Step 1300 is omitted.
Next, the position of the element to be inserted is identified (Step 1301), and area is allocated for the insertion position and the subscript conversion array regarding elements before the insertion position and elements after the insertion position. In the example of symbol 1401 of FIG. 14, the various arrays contained within the initial subscript conversion array contain only one element each, but in the processing of Step 1301, area is allocated for an array having three elements (an element for before the insertion position, an element for the insertion position, and an element for after the insertion position) (Step 1302). Note that if an array having a plurality of elements is already provided, an area is allocated for an array in which the number of elements can be increased by 2.
Thereafter, regarding elements before the insertion position, the values of the elements of each array are determined (Step 1303). More specifically, the element value corresponding to the start position array and the element value corresponding to the offset array are not changed, but the "value corresponding to the insertion position-1" is given as the element value of the end position array. In addition, regarding the insertion position also, the values of corresponding elements in each array are determined (Steps 1305 and 1304). In this case, the "value corresponding to the insertion position" is given as the element values of the start position array and end position array, and the "value corresponding to the position of the end of the actual array" is given as the element value of the offset array. Note that as described later, if the element to be inserted is to be set at a different position, the value corresponding to the position where the element to be inserted may be given as the offset value.
In addition, regarding elements after the insertion position also, the element values of the various arrays are determined by the following technique. To wit, "value corresponding to the insertion position+1" is given as the element value corresponding to the start position array (Step 1306), and the initial "value corresponding to the end position+1" is given as the element value corresponding to the end position array (Step 1307). Next, the element value corresponding to the offset array is set in "its initial value (original value)-1" (Step 1308).
For example, in the case in which there are a subscript and array as indicated by symbol 1201 of FIG. 12, and the initial subscript conversion array indicated by symbol 1401 of FIG. 14 is generated, one can understand that the subscript conversion array indicated by symbol 1411 is generated by the process of the aforementioned Step 1301 and Step 1307.
After such a subscript conversion array is generated, the CPU 12 stores the element to be inserted at a stipulated position after the end of the actual array set in Step 1304. Thereby, an element can be effectively (logically) inserted at the desired position in the actual array without moving the elements (stored values) of the actual array.
[Deletion of Elements by Means of a Subscript Conversion Array]
Next, we shall describe the method of deleting elements using the aforementioned subscript conversion array. For example, as shown in FIG. 15A, consider the case of deleting the elements of row 1 (the second row) of the array. In this case, after the deletion, the subscripts and the elements within the array (stored values) have the logical relationship shown in FIG. 15B. In the same manner as during insertion, in order to maintain the logical relationship shown in FIG. 15B while minimize the load arising from deletion, consider the subscript conversion array shown in FIG. 15C. In FIG. 15C also, in the same manner as in FIG. 10C, the subscript conversion array defines the range of subscripts and offset values so that the converted subscript may be found. More specifically, for each subscript, one can see that the elements (stored values) within the actual array are identified by performing the process of FIG. 11. For example, one can see that the subscript "1" is associated with the structure array of row 1 (the second row), and the member value (offset value) within the offset array related to this structure array is "1" so the converted subscript is "1+1=2." Accordingly, one can see that the corresponding element is stored at the position corresponding to "2" in the actual array.
[Generation of a Subscript Conversion Array for Deletion of Elements]
For example, as shown in FIG. 16A, consider an array of 5 elements (symbol 1601), and among these consider the case of deleting the element (stored value) X0 in row 1 (the second row) (see symbol 1602). Note that in this example, the actual array is assumed to be the same as array 1601.
FIG. 17 is a flowchart used to describe the process of generating a conversion array for deleting elements (stored values) from the array, while FIG. 18A is a diagram that shows how the values within the conversion array change with processing.
The process of FIG. 17 is also executed by the CPU 12 in FIG. 1. First, if no subscript conversion array has been generated, an initialized subscript conversion array is generated (Step 1700). For example, in the example shown in FIG. 16A, the start position array, end position array and offset array are generated such that the number of elements is "5" so the value indicating the start position is "0," the value indicating the end position is "4," and the offset value is "0" (see symbol 1801 of FIG. 18A).
Next, the position of the element to be deleted is identified (Step 1701), and area is allocated for the subscript conversion array regarding elements before the deletion position (Step 1702). In the example shown in FIG. 18A, as shown by symbol 1802, area is obtained such that the various arrays of the subscript conversion array store elements for before the insertion position, the insertion position, and after the insertion position. In the new area, regarding elements before the deletion position, the "value indicating the deletion position-1" is set as the element of the end position array (Step 1703), while the "value indicating the deletion position+1" is set as the element of the start position array (Step 1704). In this manner, regarding the structure array within the conversion array containing the deletion position, the start position array, end position array and offset array are created as indicated by symbol 1802. Note that the structure array regarding the deletion position is not ultimately used, so while the deletion position itself must be calculated, there is no need to store elements within the array as shown in FIG. 18A.
Next, for the various arrays, regarding the element after the deletion position, the following operation is performed. First, the element of the start position array is set to the "original value-1" (Step 1705) and also the element of the end position array is set to the "original value-1" (Step 1706). In addition, the element of the offset array is set to the "original value+1" (Step 1707). For example, in the example of FIG. 18A, the element "2" within the start position array positioned after the deletion position is decremented, becoming "1" (see symbol 1804), the element "4" within the end position array is decremented, becoming "3" and the element "0" within the offset array is incremented, becoming "1." In this manner, it is possible to obtain a subscript conversion array for deleting elements within the array. Note that the actual array (the array that actually contains the elements identified by subscripts) is not changed even at the time of deletion of elements. To wit, the virtual (logical) deletion of elements within the array is performed only by the subscript conversion array. In addition, the deletion of elements within an array can be achieved by the process of FIG. 17 for the other example shown in FIG. 16B. In this example, the element "Y0" is inserted into row 3 (the fourth row) of the array, and accordingly the actual array takes a form in which the element "Y0" is added to the end (see symbol 1610 of |
