Database system and method for operating a database system6381596Abstract The invention relates to a database system comprising a computing unit, a main memory and a, in particular a peripheral memory storing at least one multi-dimensional stock of data in the form of a UB tree, further the invention relates to methods to run a database of this kind to read data and to implement join operations and further relational algebra operations, and sub-dividing the UB tree into a predetermined number of sub-spaces and consecutively processing the sub-spaces to read and ready the stock of data. Advantageously a cache storage buffers the regions (jump regions) of the UB tree cutting the sub-space being processed until the jump region(s) has (have) been completely processed in the subsequent sub-spaces. Claims What is claimed is: Description The invention relates to a database system comprising a computer unit, an operational memory and a separate peripheral memory, storing at least one multi-dimensional stock of data in the form of a UB tree, further to a method for operating a database system of this kind to read data and to carry out join operations and further relational-algebra operations.
ABC BAC CAB
ACB BCA CBA
AB BA CA
AC BC CB
A B C
namely a total of 15 different sorting orders. For a multi-dimensional UB tree of dimension d, there will be in general d!+d*(d-1)* . . . *2+ . . . +d*(d-1) . . . *i+ . . . +d*(d-1)+d feasible sorting orders [for d=3 there will be 3!+3*2+2=15]. To carry out the method of the invention, hereafter called "UB cache method", the stock of data F is subdivided in one dimension into a predetermined number n of sub-spaces. If, in the three-dimensional illustrative embodiment shown in FIGS. 1a-1c, data reading or processing is to be carried out in a sorting sequence relating to the attribute C, then the stock of data F will be sub-divided into n sub-spaces in the dimension of the attribute C (see FIG. 1a). If however the stock of data shall be read or processed relative to the attribute B, then a sub-division into n sub-spaces will be carried out in the dimension of the attribute B (FIG. 1b). FIG. 1c shows the corresponding case for a sub-division into n sub-spaces of the stock of data F in the dimension of the attribute A. The stock of data shall be sub-divided by preferably equidistant hyper planes, one segment of the stock of data between two consecutive hyper planes forming one data sub-space (=multi-dimensional slab). In the two-dimensional case (FIG. 2), the data sub-spaces are rows and columns. In the example of the stock of data shown in FIG. 1a, subdivision is implemented by consecutive hyper planes of the form C=j/n*c in slabs of width 1/n, the so-called C slabs. The ith slab then contains precisely those data which satisfy the following relation for the C attribute (i-1)*c/n<=C<i*c/n where the attribute C may assume values between 0 and a given number c. If the data in the above space shall be assorted with respect to the attribute A, the procedure is as follows: for j:=1 to n do sort the data in the jth slab and output these data in sorting sequence. This row by row processing works because in the sorting order of the attribute A all data in the first slab precede all data in the 2.sup.nd slab and in general all data in the jth slab precede the data in the (j+1)th slab. During such consecutive processing, the slabs are processed in rows. Illustratively FIG. 1a shows in shaded manner the first slab relating to attribute C, while FIG. 1b correspondingly shows the third slab relating to attribute B and FIG. 1c the second slab relating to attribute A. The number n of slabs satisfies the condition n=2.sup.k, where k .gtoreq.0, and where k is a measure of the subdivision of the data space. Following k-fold subdivision of a data space of edge length 1, sub-cubes of side length 1/n will result. FIG. 2 shows a UB tree for a two-dimensional stock of data with regions 01, 023, 101, 12, 131, 201, 221, 301, 32, 331 and 4 (ad infinitum) where, for the sake of simplicity the region is denoted by the upper limit of its address. Following k=3 sub-division, this stock of data has been subdivided into minimal, i.e. sub-squares of edge length 1/n with n=8. In general a sub-cube is so overlapped by the regions of the UB tree that there will be a first region cutting the cube though it may not be wholly contained in it. Such a region is called a jump region because it is penetrating the sub-cubes from the outside. Then the sub-cube is filled by further regions as far as the last region which need not be wholly contained in the sub-cube and jumps out of it. This last region also is a jump region. Independently of the plane of subdivision, there may be at most two jump regions per sub-cube on a given plane of subdivision of the k-fold sub-divided stock of data. To carry out the method of the invention, the illustrative embodiment of a two-dimensional stock of data shown in FIG. 2 is sub-divided into n=2.sup.3 =8 rows (horizontal, two-dimensional slabs). When reading or processing the data objects contained in the stock of data, the data contained in row 1 are read first by region. If a region is not wholly contained in row 1, then a jump region is involved which together with at least another row forms cut sets. Those data objects of the jump region which are outside the row being processed are buffered according to the invention until the jump region has been completely processed in the ensuing rows. Accordingly the particular row j is considered being the query box FZ(j) to read the data and those regions which cut FZ(j) are entered from the peripheral memory into a buffer illustratively part of the main memory and are internally sorted in said buffer. The FZ(j) data can be immediately processed further, while the data from jump regions outside FZ(j) will be buffered for later processing. In the example of FIG. 2, the following jump regions exist for each row,
row 1:01 023 101 12
row 2: 023 101
row 3: 023 101 131 201
row 4: 201
row 5:221 301 32
row 6:221 (301)
row 7: 301 331 infinite
row 8: no longer any jump function,
where each region is denoted by the higher of its two addresses. This example shows the jump regions per row and the particular contents of the buffer (hereafter UB buffer). At the same time, one may conclude that it is pessimistic to estimate that, of the possible jump regions, there are two jump regions per sub-cube. In the shown embodiment up to 16 jump regions might arise per row (n=2.sup.3 =8 sub-cubes each with up to 2 jump regions), actually however only 4 jump regions occurring per row. Accordingly the row 1 of FIG. 2 is cut by the regions 01, 023, 101 and 12. Each of these regions therefore constitutes a jump region relative to row 1 and at least the portion of the data objects of each region not in row 1 will be buffered. Row 2 also is cut by the regions 01, 023, 101 and 12. However, the two regions 01 and 12 only jumping into the row 2, without jumping out of it again, they will be fully processed together with their data objects buffered in the UB buffer within the framework of row 2, and accordingly the two regions 023 and 101 remain in the UB buffer as being regions to be buffered therein further, which jump out of the row 2 and form further cut sets with the rows 3 and 4. Row 6 is didactic, meeting only the jump region 221 (region 32 is completely processed within the scope of row 6), while the bracketed region 301 remains in the UB buffer for later processing within the scope of row 7. If the two-dimensional stock of data shown in FIG. 2 shall not be read in the sorting sequence of the vertical attribute not further specified, but instead shall be read in the sorting sequence of the horizontal attribute, there takes place sub-division not into rows, but into columns, and the regions are not read by rows but by columns. In the general d-dimensional case, the rows or columns are replaced by slabs separated from each other by hyper planes. Accordingly the UB cache method of the invention serves to process a given data space slab-by-slab, to buffer the projecting jump regions and to optimally control data transports. Essentially the method of the invention is composed of two components, namely the so-called UB buffer and the so-called UB control. Advantageously the UB buffer is part of the main memory and is used to buffer jump regions or parts of jump regions for later processing. The UB control is used to optimally control data transports between the peripheral memory and the UB buffer and it implements the actual data processing (for instance internal sorting or join operation) of the data in the buffer. Accordingly the UB buffer is needed for two tasks: 1. Input of all regions cutting a slab zone, 2. Buffering those portions of the input jump regions not in the slab instantaneously processed and which must therefore be "undone" until the slab in which they are located shall be processed. Accordingly the tasks for the UB control are the following: 1. Determining optimal slab partitioning for F, 2. Controlling the data transports from the peripheral memory into the UB buffer, 3. Internal sorting in the UB buffer of the data in the input regions. For this purpose standard sorting procedures for internal sorting are used, for instance Heapsort or Quicksort, 4. Output, in the desired sorting sequence, of the data within the instantaneous slab zone, 5. Managing those portions of the jump regions which shall be needed for subsequent slab processing. The following applies to an algorithm of high programming level for the general case of the method of the invention to read and ready data in an arbitrary sorting sequence: Let a given multi-dimensional stock of data F be sub-divided k-fold, that is, there are n=2.sup.k slabs from 1 to n and per slab there are also n sub-cubes and therefore at most 2n jump regions. The ith slab of the stock of data F being denoted FS(i). UB buffer:=empty
for i: = 1 to n do
begin co process ith slab oc
for all regions r in the UB buffer do
begin if r cuts FS(i) then
begin process data in r (in particular: sort
them internally in the UB buffer);
if r is completely processed
then erase r from UB buffer
end
end;
for all regions r cutting FS(i) but were not
yet in the UB buffer do
begin read r from hard disk;
co here FS(i) is considered as if it were a Query Box for
the
UB
tree oc
process data from the intersection of r with FS(i);
if r is a jump region
then store r in UB buffer
end;
co now all data from FS(i) are in the UB buffer ready and
in sorting sequence oc
process data in FS(i) in sorting sequence for instance
printing them, displaying them on the monitor, or in the event
of relations process further using relational algebra
end
co after the last slab has been processed, the UB buffer must be
empty
because no jump region can jump beyond the last slab in F oc.
If F is sub-divided into slabs of width 1/n, the required size of the UB buffer for processing F into sorting sequence in the two-dimensional case is given by: B(F, n)=.vertline.F.vertline./n+2*n.vertline.P.vertline. .vertline.F.vertline./n is needed for the slab itself, 2*n*.vertline.P.vertline. for the jump regions, where .vertline.F.vertline. is the magnitude of F and .vertline.P.vertline. is the magnitude of one page of data in bytes. This buffer size is minimal when the derivation with respect to n becomes zero, that is for B'(F,n)=-1*.vertline.F.vertline./n.sup.2 +2*.vertline.P.vertline.=0, with the optimal size n.sub.opt for n being n.sub.opt =root of (.vertline.F.vertline./[2*.vertline.P.vertline.]). Approximately k is selected next so that n=2.sup.k is as close as possible to n.sub.opt and thereby becomes a nearly optimal size for the UB buffer. The following mathematical illustration concerns the required memory sizes: .vertline.F.vertline.=10.sup.9 bytes, .vertline.P.vertline.=10.sup.3 bytes n.sub.opt =root of (10.sup.9 /[2*10.sup.3 ])=707 Selecting k=10 and hence n=1024, B(F, 1024)=3 Mb Selecting k=9 and hence n=512, B(F, 512)=3 Mb. The precise optimum thus would be B(F, 707)=10.sup.9 /707+2*707*10.sup.3 =2.82 Mb, This example also shows that B(F, n) has a very flat minimum and is fairly insensitive to the precise selection. In the general d-dimensional case, the size of the UB buffer required for processing F in the sorting sequence is given by B(F,n,d)=.vertline.F.vertline./n+2*n.sup.d-1*.vertline.P.vertline., .vertline.F.vertline./n being required for the sub-space itself (the slab), and 2n.sup.d-1*.vertline.P.vertline. for the jump regions. This buffer size will be minimum when the derivation with respect to n becomes zero, namely when B'(F, n, d)=-1*.vertline.F.vertline./n.sup.2 +2*(d-1)*n.sup.d-2.vertline.P.vertline.=0 with the optimal magnitude n.sub.opt for n being given by n.sub.opt =dth root (.vertline.F.vertline./[2*(d-1)*.vertline.P.vertline.]). Accordingly the UB cache of the invention is especially advantageous to implement a join operation. For efficient implementation, most relational algebra operations require that at least one, or also both operands (relations) be present in sorting order as defined by specific attributes. As already discussed above, the relations must therefore be sorted very frequently in conventional databases. Multiple to-and-for data transport between the computer main memory and the hard disk is involved. In the invention however using the UB cache method, stocks of data organized as a UB tree can be read and processed in such manner as if they were sorted on the hard disk. Accordingly the UB cache method avoids the heretofore required sorting procedures. As a result, the above mentioned data transports--for sorting purposes--between the main memory and the hard disk can be avoided and the relational algebra operations can be carried out at significantly higher speeds. Therefore the UB cache method allows substantially accelerating relational operator implementation in all relational databases. Some relational algebra operations are used similarly also in other database systems, for instance in object-oriented database systems. These operations as well can be correspondingly accelerated using the UB cache method of the invention. As regards the state of the art, for instance in a join operation between two relations R and S, the following processing stages are conventionally used: 1. read R relation from hard disk 2. pre-sort R in portions 3. enter R by portions on hard disk 4. again read R by portions from hard disk 5. sort R using a so-called mixing procedure 6. enter R on the hard disk 7. if S has not yet been sorted according to the join attribute, the steps 1 through 6 now must be appropriately also be carried out for S; the steps 1 through 7 are preparatory for the actual join operation, 8. read S by portions in sorting sequence from the hard disk 9. read R by portions in sorting sequence from the hard disk and join to the pertinent tuples from S (join operation proper) 10. enter the join result on the hard disk. Steps 4, 5, 6 are carried out at least once, and several times in many sorting procedures. Therefore R will be read at least a total of three times from the hard disk (in steps 1, 4, 6) and will be entered three times on the hard disk (steps 3, 6, 10 because the join result contains data from R and S). Just as R, S also will be read three times from the hard disk and will be entered on it three times. The just described join procedure is also known in the literature as "sort-merge-join". When the relation R is appropriately organized as a UB tree, R can only be read using the UB cache method in such manner as if R had been sorted on the hard disk. The same conditions apply appropriately to S. As a result the steps 1 through 7 are eliminated from the above join method. As a result the total join method is accelerated by a factor of at least 3. Because in most relational algebra operations (besides the join operation, which however is the most important one) the participating relations must be read in sorted form (and therefore, in the heretofore conventional procedures must first be sorted) such sorting procedures are eliminated using the UB cache method jointly with the UB tree and the operations can be speeded up substantially. The function of a join algorithm of the invention with the UB cache method is elucidated below in relation to FIG. 3. 1. the UB control optimizes the buffer size and automatically determines n.sub.opt ; in the example, it is assumed that n.sub.opt =n=8, 2. next a relation R organized as a UB tree is sub-divided into portions of size 1/n where n=2.sup.k, and in this example therefore k=3; in the two-dimensional case these portions are rows; these rows are numbered 1 through n, 3. after the space has been sub-divided k-fold, there will be n sub-cubes in one row, in this instance 8 squares, 4. as regards the join operation, next an S row is fed in entirety into the UB buffer (corresponding to step 8 in the previously described sort-merge-join); if S is organized as a B tree or is suitably sorted, exactly one row can be fed from the peripheral memory into the UB buffer; (if S is organized as a UB tree, the zone of rows will be fed in sorted manner, the projecting portions of the jump regions being stored in the UB buffer for subsequent uses), 5. next the relation R is processed row by row in order for instance to join the tuples in this row with the matching tuples from the corresponding S row (corresponding to step 9 in the above described sort-merge-join); for that purpose those regions of the hard disk are being read which cover the n sub-cubes of a row; because the regions of a UB tree precisely correspond to one side of a hard disk, regions always are moved (read) from the hard disk into the main memory; two cases now arise: those regions fully contained in the row can be immediately processed and be joined to their partners of the corresponding S row, that is, they need not be buffered, those regions which project beyond the row into rows (jump regions) to be processed later contain two kinds of data: those within the row being processed (intra-row data) and those outside this row (extra-row data); the intra-row data can be processed at once and be joined to their partners of the corresponding S row, while the extra-row data are buffered and stored in the UB buffer until subsequently processing the row in which they are located. It is important in this respect to know the number of jump regions maximally possible in order to estimate the memory needs for buffering R jump regions or at least their row-extra data in the UB buffer. It is assumed for simplicity that the jump regions all are buffered. By splitting into row-intra and row-extra data, the memory required by R in the UB buffer may be further reduced by about half because in reality only the R extra-row data need be buffered. The size of the UB buffer for the join method then follows: Case 1: let S be appropriately sorted and let B be organized as a UB tree: to sort a full S row: .vertline.S.vertline./n bytes to store the jump regions of the R row: 2*n*.vertline.P.vertline. bytes total requirement: B1 (S,n)=.vertline.S.vertline.n+2*n*.vertline.P.vertline. bytes. The optimum is given by B1'(2,n)=-.vertline.S.vertline./n.sup.2 +2*.vertline.P.vertline.=0 and accordingly n.sub.opt =root(.vertline.S.vertline./[2*.vertline.P.vertline.]). Case 2: Neither relation R or S is appropriately sorted, but they are organized as UB trees, to store the full S row and store this row's jump regions: .vertline.S.vertline./n+2*n.vertline.P.vertline. bytes to store jump regions of R row: 2*n*.vertline.P.vertline. bytes total requirement: B2(S, n)=.vertline.S.vertline./n+4*n*.vertline.P.vertline. bytes. Optimum exists at B2'(S,n)=-.vertline.S.vertline./n.sup.2 +4.vertline.P.vertline.=0, whence n.sub.opt =root (.vertline.S.vertline./[4*.vertline.P.vertline.]). The concept of the invention reflected in the claims also includes using the database system of the invention and the UB cache method of the invention in further operations of relational algebra, for instance projections, merging quantities etc.
|
Same subclass Same class Consider this |
||||||||||