JPH01253027A - Data base address calculating device - Google Patents

Abstract

PURPOSE:To calculate the storage address of corresponding fixed-length data at a high speed by minimizing the number of times of calculations of an entry position and an address by using difference information on line numbers at the time of accessing based upon the line numbers which are inputted in increasing order. CONSTITUTION:A data base which stores and controls fixed-length data in two-dimensional representation stores and controls the data in column units of each table by using a complete balanced tree and respective rows are identified by using line numbers determined by input order. In this case, when the access based upon the line numbers which are inputted in increasing order is attained, the difference information on the line numbers is used to minimize the number of times of calculations of the entry position and address. Consequently, the storage address of corresponding fixed-length data is calculated at a high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION (1) Technical field to which the invention pertains The present invention relates to a database (relational database) that stores and manages data in a two-dimensional table format.

Data is stored and managed in each column (attribute) unit of each table (relation) using a fully balanced tree, and each row (tuple) is input in ascending order using a method that uses the row number determined by the input order. The present invention relates to a database address calculation device that enables high-speed calculation of a storage address for corresponding fixed-length data when accessing using a fixed-length data row number.

(2) Conventional storage management methods for databases that store and manage technical data in a two-dimensional table format are generally divided into row-by-row storage and column-by-column storage.
access by column number or column identifier) is inefficient.
Train position storage is inefficient for row direction access (access by row number or row identifier). Also, traditional column-based storage.

Since a row identifier is added to each row, storage space usage efficiency is also poor.

This column-by-column storage is slow when accessing in the row direction.

In order to solve the problem of poor storage space utilization efficiency, a ``relational arithmetic processing method using associative memory'' was proposed.
This is a column-based storage method using a perfectly balanced tree that was announced at the Information Processing Society of Japan's 1986 National Conference, 3G-1. In this storage method, data is stored and managed column by column using a fully balanced tree, each row is identified using a row number determined by the input order, and row-direction access is performed using address calculation that calculates the address of the value corresponding to one row number. The structure is such that this is done through a mechanism. For details of the address calculation mechanism in this storage method, see
Database storage device” (Patent application 1986-266706)
No. 1, filing date: November 11, 1988). It connects in series the circuits that perform address calculations at each stage in the tree search of a perfectly balanced tree, operates them in a pipeline, and has a built-in short-circuit route for address calculation based on identity comparison with the previous tree search. ing. In other words, in the process of calculating the entry position of each stage from the root address and line number, if the entry position is the same as the previous one, the previous address is used as is without address calculation.

The process then proceeds to the entry position calculation for the next stage. However, this short-circuit route is only used to reduce the number of address calculations; calculation of entry positions must be performed at all stages every time an access is made.

(3) Purpose of the Invention An object of the present invention is to store and manage data in each column of each table using a fully balanced tree in a database that stores and manages data in a two-dimensional table format.

The identification of each line is based on the method of using line numbers determined by the input order, and when accessing by line numbers input in ascending order
To provide a database address calculation device capable of calculating a storage address of corresponding fixed-length data at high speed by minimizing the number of calculations between an entry position and an address using difference information of line numbers. There is a particular thing.

(4) Structure of the Invention (4-1) Features of the Invention and Differences from the Prior Art First, the storage method will be explained. FIG. 1 is an explanatory diagram for explaining a table, and FIG. 2 shows the table shown in FIG. 1 stored column by column in a perfectly balanced tree, focusing on the first column. Further, FIG. 3 shows the case when accessing the perfectly balanced tree shown in FIG. 2 in the 9-row direction.

"Database storage device" (Patent application No. 61-26670)
FIG. 4 shows an embodiment of the address calculation mechanism presented in No. 6) of the present invention.

Both FIG. 3 and FIG. 4 are examples in which the nest level at the end of perfect equilibrium is equal to or less than 3. Now, the number of values stored in the lowest block (leaf) of the tree is N, and the number of pointers stored in other blocks is M.

Let n be the row number in question, and let r be the entry position in the block of stage i that is passed through to reach the value corresponding to n.
When (i) is assumed, the relational expression used in FIG. 3 is shown below.

q (1) =N q (+) -q (+-1) *M (+=2...,k) p(k)=n-1 r (k) = [p (k> /q (k) ]p
(i-1) =p (i)-q (i) *r (i)
r (i-1) = [p(i 1) /q (i
1) ] (i=2....,k) r (0) -p (1) -q (1) *r (1
) In Fig. 3, the logic circuits forming each stage are as follows.

Gaussian symbol calculation circuit 3. Simple arithmetic operations (a-bIC)
Circuit 4. Word access circuit 5. Comparison circuit 6 etc.
This is common to each stage. The base address l is the address of the root block of the fully balanced tree pointed to from the attribute table (FIG. 2). The comparison circuit 6 compares the previous entry position r゛(i) and the current entry position r(i
), it is possible to form a short-circuit route for address calculation.

Now, 1. When a database is configured using the storage method handled by the present invention, the derived relations created by applying relational algebraic operations and set operations include the root address of the basic relation,
All you need to do is keep a row number column that corresponds to the value to be stored.

Often in ascending order. selection,
projection, aggregation
gate function).

division, set difference
erence), intersection
etc. is applied to the basic relation, a derived relation can be constructed using the row numbers of the necessary data every 9 columns. For example, for the ration shown in Figure 1,
Select under the condition (value of column l) <'H' (sele
ction) When the operation is performed, the sequence l of the 1 derived relation
has 1 row number column + 2.5, 6, 10, 12, 15.17
゜...) is maintained. Also, when these operations are applied to a 1-derived relation, the row number of the basic relation that the 2-derived relation has as a value is used instead of the row number of the 5-derived relation.

Represents the value of a new derived relation. Binary operations can also be applied to combinations of basic relations and derived relations. In the union (un 1on), all you have to do is add the non-duplicate data of one relation to the other relation, so if you divide the row number column into two depending on the basic relation you are referring to, then
Each can be done in ascending order. In the case of a join, the row number columns composed of relations that include key attributes are all in ascending order, but those composed from the other are not in ascending order.However, if you group the relations by key attribute, Since each group can be arranged in ascending order, it can be treated as ascending order data by dividing one column.

The conventional technology did not pay attention to the ascending order of the nine rows and number columns, so the entry position in each row was recalculated every time it was accessed.

Taking advantage of the fact that the row numbers are arranged in ascending order, the entry position on perfect equilibrium water is calculated from the difference information.

The current entry position is calculated by dividing the sum of the number of difference lines calculated in the previous stage and the previous entry position in that stage by the number of values (or pointers) that can be stored in each block, starting from the bottom block. can be calculated. Therefore, the greater the number of values stored in the bottom block, the less likely it is that the entry position in the upper block will be recalculated, so the number of calculations can be reduced.

(4-2) Example Hereinafter, the present invention will be explained in more detail using FIG. 4 and FIGS. 5 to 8.

First, in column-wise storage using a fully balanced end.

The relational expression between the line number difference and the value entry position is shown. The meaning of N, M, n, r (i) is the third in the following letters.
In addition, the previous line numbers are nl and n
Let r'(i) be the entry position in the block of stage i through which the value corresponding to 1 is reached. At this time, (r(i)l is determined by the following recurrence formula.

d(0)=n-n' d(1)= [(r'(0) 10d(0)] /N
]r (0)= (r'(0)+d (0))−
N*d (1)d (i + 1) = [(r'(
i) 10d (i) ) /M]r (1)” (
r'H)+d (i)'j -M*d(i+1)(
+ -1, . . . , k) In FIG. 4, as in FIG. 3, each stage has almost the same configuration reflecting the form of the recurrence formula. Namely.

The logic circuits constituting each stage perform four simple arithmetic operations ((a+b
)-cod) Circuit 7. Gaussian symbol calculation circuit 8. Word access circuit 5. The comparator circuit 6 and the like are common to each stage. The line number n is in the line number data 10 shown at the right end of the bottom row.
When input, the number of difference rows calculated by the difference calculation (n-n'') circuit 9 is held in do. If the difference is O, the same value as the previous value is outputted through the comparison circuit 6 at the bottom stage. If it is not 0, dl and rO are recalculated in the first stage. At this time.

ro used in circuits 7 and 8 is the previous entry position r
'0, and the value calculated by the two circuits 7 becomes the current rO. The base address l is the same as in FIG. 3, and a gate is opened according to the value of the nest level of the perfectly balanced tree. Also, in FIG. 1, 1 nit indicates that it is set at the time of initial setting.

Using Figures 5 to 8, =2. n=4. Assuming that the value of attribute l corresponding to one row number (5, 7, 18, ...) is requested for the table in Figure 1, which shows the operation by a concrete example when M = 4, the main In Fig. 5, where the operation route is indicated by a thick line, first, the 5 base address 'A21' is set as the initial setting.
is sent, and a value with 1 nit added is set. the result.

A2. shown in FIG. AI, AO, VA t respectively “
A21'', 'All°, 'AO1', and 'T' are entered. That is, in the word access circuit 5 to which °A21' is input, <, A21+4*
Operation W is performed on O, in other words, W(A21
+, 10), that is, W(A21) is applied.
If the processing result of (A21) is "All", the corresponding "A 11 ' is led to the next stage. Similarly.

The processing result of W(A11+4*O) is "AOIo", and the processing result of W(A114*1) is "■". Figure 6 shows the state after accessing 2nd line number 5. As a result of the access, the entry The location is rO and “1. Address is AO
and val is recalculated.

The value "A' is obtained. In other words, the word access circuit 5 to which °All" is input performs the operation (A11+4*1
) is applied, and the processing result of this = Pig W (All) is “A”.
02'', and the corresponding "All" is led to the next stage. In the same way, W (A11+4*1) is calculated. Figure 7 shows the state after accessing 9th row number 7, and shows the result of the access. .

Only rO and val are recalculated to obtain the value 'J'. That is, in the word access circuit 5 to which "A02°" is input, the operation (A11+4*1) is performed. FIG. 8 shows the state after accessing row number 18. , as a result of the access, all three stages are recalculated and the value "N" is obtained.

(5) As described in detail, according to the present invention, in a database that stores and manages fixed-length data in a 22-dimensional table format, data is stored in each column of each table using a fully balanced tree. Under the method of using line numbers determined by the input order to identify each line, when accessing by line numbers input in ascending order, the difference information of one line number is used to calculate the entry position and the number of address calculations. By minimizing the storage address of the corresponding fixed-length data, it is possible to calculate the storage address at high speed. When the number of values to be stored is 1/10 of 100.000, the number N of values to be stored in the bottom block is 512.000. If the number M of pointers stored in other blocks is 64, the number of calculations for the lowest entry position r(0) is at most 100.0.
00, but "(1)" in the second row from the bottom is at most 195
4. r (2) in the third row from the bottom may be at most 31. In other words, the larger N and M are, the smaller the rate of recalculation of entry positions in rows closer to the root becomes, and the access efficiency improves.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing an example of a relation for an embodiment of the apparatus, FIG. 2 is a diagram showing an example of storage using the storage method of the present invention focusing on the first attribute of the relation shown in FIG. 1, and FIG. The figure shows an example of conventional technology. FIG. 4 is a diagram showing an embodiment of the present invention, and FIGS. 5 to 8 are operation examples in which the embodiment of FIG. 4 is operated for the storage example of FIG. 2. 1... Base address, 2... (line number - 1) data, 3... Gaussian symbol calculation circuit, 4... Simple arithmetic operation (a-b*c) circuit, 5... Word access circuit. 6...Comparison circuit, 7...Four arithmetic operations ((a+b
)-c*d) circuit, 8...Gaussian symbol calculation circuit, 9.
... Difference calculation (n-n') circuit, 10... Row number data. Patent applicant Nippon Telegraph and Telephone Corporation

Claims (1)

[Claims] In a database that stores and manages fixed-length data in a two-dimensional table format, data is stored in a perfectly balanced tree for each column of each table.
Under this method, each row is stored and managed using a row number determined by the input order, and when accessing by row number, addresses are calculated for each stage in a traverse of a fully balanced tree. For each stage, calculate the entry position in the block using the calculation result of the previous stage, and calculate the address where the value of that stage is stored using the address obtained in the previous stage and the entry position obtained in that stage. It has a configuration in which the calculations are divided into two calculations and connected in series, and using the difference information of the row numbers between the previous and current calculations, the calculation of the corresponding fixed length data is performed for the ascending order input of the row number column. A database address calculation device that enables high-speed calculation of storage addresses.