Source: http://www.google.com/patents/US4785400?dq=5708422
Timestamp: 2017-11-17 22:32:21
Document Index: 125971039

Matched Legal Cases: ['art 104', 'art 105', 'art 109', 'art 104', 'art 104', 'art 109', 'art 109', 'art 104', 'art 105', 'art 105', 'arts 603']

Patent US4785400 - Method for processing a data base - Google Patents
The data elements for a column of a table are fetched from irregular address locations in memory and stored as vector data with a regular address increment. Vector designating data is also generated which includes at least the first element address of the stored vector data and the increment of the vector....http://www.google.com/patents/US4785400?utm_source=gb-gplus-sharePatent US4785400 - Method for processing a data base
Publication number US4785400 A
Application number US 07/015,694
Also published as US4644471
Publication number 015694, 07015694, US 4785400 A, US 4785400A, US-A-4785400, US4785400 A, US4785400A
Inventors Keiji Kojima, Shunichi Torii
Method for processing a data base
US 4785400 A
1. A method for processing a data base, which comprises a plurality of groups of data elements, each group of data elements being stored at storage locations within a data storage device whose addresses are not uniformly separated, the method comprising the steps, performed by a computer, of:
fetching one group of data elements to be processed among said plurality of groups of data elements, in response to a command requiring processing of the one group of data elements, and storing the one group of data elements into said storage device so that the one group of data elements is stored as elements of vector data at locations with uniformly separated addresses within said storage device;
storing vector designating data required for accessing vector data; and
accessing elements of vector data based upon the vector designating data and processing accessed elements of vector data.
2. A method according to claim 1, wherein the vector designating data includes an address of starting element of a vector.
3. A method according to claim 1, wherein the data base is a relational data base which includes a plurality of table data each comprised of a plurality of columns and rows, wherein a group of data elements belonging to respective rows of a column of a table are stored at storage locations within the data stroage device whose addresses are not uniformly separated.
4. A method according to claim 1, wherein the fetching step includes the steps of:
determining addresses of respective data elements of one group of data elements and storing determined addresses in the data storage device as elements of vector data at locations with uniformly separated addresses within said data storage device; and
fetching one group of data elements based upon vector data comprised of said determined addresses and storing the one group of data elements into said data storage device as vector data for the one group of data elements.
5. A method according to claim 4, wherein the address determining and storing step includes the step of:
accessing group defining data stored within said data storage device and prepared for the one group of data elements so that group specifying data assigned to the one group of data elements and a plurality of data elements specifying data assigned to respective data elements within the one group are read out from the group defining data; and
determining addresses of respective data elements of the one group based upon the group specifying data and the plurality of data elements specifying data.
6. A method according to claim 5, wherein the data base is a relational data base which includes a plurality of table data each comprised of a plurality of columns and rows, wherein a group of data elements belonging to respective rows of a column of a table are stored at storage locations within the data storage device whose addresses are not uniformly separated.
7. A method according to claim 4, wherein the data base is a relational data base which includes a plurality of table data each comprised of a plurality of columns and rows, wherein a group of data elements belonging to respective rows of a column of table are stored at strogae locations within the data stroage device whose addresses are not uniformly separated.
8. A method according to claim 1, wherein said fetching and storing step includes the steps of:
accessing group defining data stored within said data storage device and prepared for the one group of data elements so that group specifying data assigned to the one group of data elements and a plurality of data element specifying data assigned to respective data elements within the one group are read out from the group defining data;
determining addresses of respective data elements of the one group of data elements based upon the group specifying data and the plurality of data elements specifying data;
fetching respective data elements of the one group of data elements based upon the determined addresses and storing fetched data elements into said data storage device as vector data.
9. A method according to claim 8, wherein the data base is a relational data base which includes a plurality of table data each comprised of a plurality of columns and rows, wherein a group of data elements belonging to respective rows of a column of a table are stored at storage locations within the data storage device whose addresses are not uniformly separated.
10. A method for processing a data base which comprises a plurality of groups of data elements, each group of data elements being stored at storage locations with nonuniformly spaced addresses within a data storage device, the method comprising the steps, executed by a computer, of:
determining addresses of respective data elements of the one group of data elements and storing the determined addresses into the data storage device as elements of vector data at locations with uniformly separated addresses within said data storage device;
storing vector data designating data required for accessing vector data; and
fetching vector data based upon the vector data designating data and processing fetched vector data.
11. A method according to claim 10, wherein the vector designating data includes an address of a starting element of a vector.
12. A method according to claim 10, wherein the data base is a relational data base which includes a plurality of table data each comprised of a plurality of columns and rows, wherein a group of data elements belonging to respective rows of a column of a table are stored at storage locations within the data storage device whose addresses are not uniformly separated.
This is a division of application Ser. No. 684,789, filed Dec. 21, 1984 now U.S. Pat. No. 4,644,471.
FIG. 2 is a diagram of a table provided in the system of FIG. 1;
FIG. 8 is a diagram of a process sequence designating codes used in the data base managing system of FIG. 1;
DETAILED EXPLANATION OF A PREFERRED EMBODIMENT (Outline of an operaton of the system)
FIG. 1 shows a shematic diagram of a relational data base managing system according to the present invention. In a main storage 101, a search command is issued from an application program 102 and is examined by an interface part 104 of a relational data base managing program 103, which identifies the command as a search command. An analysis part 105 of the program 103 then analyzes the search command to determine the most suitable process sequence for that search command, generates codes which designate the determined process seauence, and stores the process sequence designating codes 107 into a control block 106. An execution part 109 of the program 103 refers to the codes stored in the control block 106 and processes the search command received by the interface part 104 according to the process sequence designated by the codes, to provide results of the processing to the application program 102 by way of the interface part 104.
During the processing, data required for the processing, but not yet loaded, is loaded into a data buffer area 110 in the main storage 101 from a data page area 141 in a subsidiary storage 102, in such a manner that data elements are separately loaded by units of the data elements contained within a unit area called a data page and having a fixed area size. The data pages are randomly distributed in the main storage 101, and therefore, one of the processes employed according to the present invention is to arrange the data elements stored in a page form to provide the data in a vector structure. Data of a vector structure designates a group of data elements which are spaced from a neighboring element with a constant address interval in the main storage 101. Each data element is referred to a as a vector element, and a group of vector elements is referred to as vector data. If this vectorizing process is designated by the process sequence designating codes 107, the execution part 109 operates to gather the vector data elements, to store the resultant vector data elements into vector area 111, and to store vector designating data concerning the generated vector data into a vector designating data area 108 of the control block 106. The vector designating data in the area 108 comprises an address of the first vector element of the vector data, an increment value designating an address difference or displacement between two neighboring vector elements and the vector length designating the number of the vector elements included in the vector data.
If the process sequence designating codes further indicates processing of the vector data, the execution part 109 sends the vector designating data in the area 108 to vector instructions included in a vector processing routine provided within the execution part. These vector instructions are executed by a data processor 113 in a pipelined manner. The data processor 113 also performs scalar instructions included in the relational data base managing program 103. The data processor 113 will be explained in more detail later in connection with FIG. 4. (An example of a process for the search command.)
In the embodiment described below, the table data to be processed, such as the commodity table 201 (FIG. 2A) is stored in units of a data page, for example, as shown by 302 in FIG. 5, and these data pages are stored in the subsidiary storage 112 with some data pages being duplicated in the data buffer areas 110. Each data page includes plural slots 304 each of which contains a respective row of data in a particular table, such as the commodity table 201 (FIG. @A). Also, the directing area 114 of main memory 110, as seen in FIG. 1, includes a table definition table, such as 1003 or 1005 in FIG. 12, and row number tables, such as 1004 or 1006 in FIG. 12. The table definition table includes various data elements required to define the data within the table to be processed. The row number table includes the data page address (page number and slot pointer number) for a table to be processed. Based upon a table definition table, such as 1003 or 1005 in FIG. 12, and a corresponding row number table, such as 1004 or 1006 in FIG. 2, the data pages for a particular table are accessed to generate vector data which includes data elements such as X1 to X4 belonging to one of the columns of the table to be processed, such as the commodity column in the commodity table 201 (FIG. 2A) and this vector data is stored in vector area 111. Also generated is vector data designating data, which is stored in the area 108 of control block 106 and includes the starting address of the vector in vector area 111, vector length, and other identifying data for the vector. The vector designating data is supplied to a vector data processing program so that the vector data in the vector area 111 can be accessed by the programs.
In the preferred embodiment, a sort operation is done on the vectors 1503 and 1504 (FIG. 17) to genrate the vector data 1801 and 1802 (FIG. 18) which are obtained after arrangement of the vector data 1503 and 1504 in alphabetical order according to employee designation. Thereafter, a join operation is performed by a program which includcs vector instructions in order to find the vector data 1902 (FIG. 19) which corresponds to the EXT column of the search result table 203 in FIG. 2D. As the vector data such as 903, 904, 1801 or 1802 shown in FIG. 18 is processed by the last mentioned program, the resultant vector data 1902 is obtained very quickly by means of pipleined processing by the data processor 113. (Instruction format and details of the data processor)
The operation explained in conection with table data shown in FIGS. 2A to 2D strongly depends upon how the tables are actually stored, i.e., how easy it is to access the data in the tables. As was explained previously, it is benefcial to store data belonging to a table separately in units of a data page, from the standpoint of easiness of insertion or deletion of data elements. The same storage form is employed in this embodiment. The details of a data storage form will be given hereinafter with reference to FIG. 5. A data page area 114 in the subsidiary storage is divided into a plurality of data pages. A data page 302 includes plural data storage areas 304 referred to as a slot. Each slot 304 includes all entries belonging to one row of a table. For example, in the case of a slot for the first row of the table 202 of FIG. 2B, data "A, 316" is stored in the slot. Each slot has its own slot number. Each data page 302 includes slot pointers 303 each indicating a starting address of a respective one of the slots 304 within the same data page 302. The slot pointers are stored at an area starting from the start address of the data page and according to the order of the corresponding slot numbers.
A search command, for example, as shown in FIG. 2C, is transferred from an application program 102 by way of the interface part 104 of the managing program. The analysis part 105 responds to this search command by determining a process sequence which is judged to be the best according to a selected standard, and provides the process sequence designating code, as shown in FIG. 8. The method of determining the best process sequence by the analysis part 105 is known, for example, in literature by P.G. Selinger et al, "Access Path Selection in a Rational Database Management System" (Prox. ACM SIGMOD Conf. 1979). The code comprises plural process designating sentences. In FIG. 8, each line forms one process designating sentence. Each process designating sentence includes a key word 601, 602, 606, 610, 613 or 618 each designating the kind of process to be performed, and parameter designating parts 603 to 605, 607 to 609, 611 to 612, 614 to 617 or 619 to 621, relating to a respective process.
Program variables used in the BUILD-VECTOR routine 704 will be explained hereinafter in connection with FIG. 4. The variables comprise VDTA (1202), VDTB (1203), i (1208) and 1 (1209), all provided in the program variable area 1201. VDTA (1202) includes VDTA.1 (1204) and VDTA.2 (1205). VDTB (1203) also includes two entries VDTB.1 (1206) and VDTB.2 (1207). VDTA (1202) and VDTB (1203) are variables used in order to describe vectors generated by the BUILD-VECTOR routine. i and j are program variables used in order to count a loop number.
At first, a value VTOP (1101) which designates a start address of the non-used region 111B (FIG. 13) is set in the variable VDTA.1 (1204), and a row number "4" in a row number entry of the commodity table definition table 1003 is set in the variable VDTA.2 (1205) (step 1302). An initial value of "1" is set in the variables i (1208) and 1 (1209) (step 1303). In a loop of steps from 1304 to 1306, addresses A1 to A4 in the main storage 101 are obtained sequentially for all rows in a table selected by the first parameter 6, in this example, T#1 related to a key word "BUILD-VECTOR", and each obtained address ai(i=1˜4) is stored in a location starting from an address designated by VTOP (1101) (step (1305). By changing VTOP by four each time when one of the four addresses A1 to A4 is obtained (step 1306), a vector can be stored in the vector area 111 which comprises four vector elements of thus obtained addresses A1 to A4. The amount "4" of each increase of VTOP (1101) is predetermined by the bit length of the addresses A1 to A4. The data "4" provided to VDTA.2 (1205) also represents the same length. The method of obtaining the addreses as shown by step 1305 was already explained in connection with FIG. 7.
According to a loop comprising steps 1307 to 1313, a vector designating data and a vector for each column within the table 201 (FIG. 2A) is formed on a vector area 111. In case of a process designating sentence starting from the key word "BUILD-VECTOR" 602 shown in FIG. 8, the vector designating data 901 and 902 and vectors 903 and 904 respectively comprising the first and second column entries are generated. The same processing is repeated by the same number as the column number in the entry 1007 of the table definition table 1001, ("2" in case of the commodity table definition table 1003). The program variable 1 (1209) designates a loop number, that is, what column is being processed. If 1 is smaller than a column number stored in the entry 1007 of the table definition table 1001 ("2" in case of the commodity table definition table 1003) (step 1307), the steps 1308 to 1313 are performed in order to generate a vector for the 1-th column. That is, at first, in VDTB.1 (1206) is stored a VTOP (1101) which represents the start address of the non-used area 111B of the vector area 111 (step 1308). As a new vector for a new column is stored at locations starting from the top of the non-used area 111, VDTB.1 (1206) designates the first element address of the new vector to be generated. In VDTB.2 (1207) is stored the 1-th column element length stored in the entry 1010 to the table definition table 100 ("4" in case of any column of the commodity table definition table 1003) (step 1308). As the vector for a column is arranged on a continuous area on the vector area 111, the address distance between two neighboring vector elements, that is, the increment value, is equal to the vector element length. Therefore, VDTB.2 (1207) now holds an increment value for a vector to be generated from now on, as a result of the setting of the vector element length into VDTB.2 (1207). Thus, the step 1308 finishes. Next, vector designating data is generated (step 1309). That is, necessary information is taken out of the table designating table (e.g., table 1003 case of the commodity table) designateed by the first parameter (e.g., T#1 (603) in FIG. 6) in a process designated sentence including the key word BUILD-VECTOR, and is written into a vector designating data area located at a location designateed by the (1+1)-th paramter (e.g., V#1 (604) or V#2 (605) in FIG. 6) within the same process designating sentence. As was explained before, the first element address of a vector for a column element is equal to VTOP (1101), VTOP (1101 is written into the first element address area 906). To the element type entry 907, the element length entry 908, and the element number entry 909 are transferred the 1-th column type 1009, the 1th column length 1010 and the row number 1011 all provided from the table designating table 1003 or 1004 (step 1309). In cases of the first and second columns of the commodity table 201 (FIG. 2A), the vector data designating data 901, 902 shown in FIG. 9 are generated. The next step 1310 is a step of execution of a vector instruction. VMSX is a name of a vector instruction, and VDTA (1202) and VDTB (1203) each designate a vector which becomes an operand of this VMSX instruction. An operand vector can be designated by its first element address and its increment. As is clear from the explanation in connection with the steps 1304 to 1306, VDTA.1 (1204) and VDTA. 2 (1205) respectively designates the first element address and the increment value of the list increment value of the list vector generated by these steps and shown by 1401 in FIG. 16, and includes elements A1 to A4 which designates locations of slots 304a to 304d within the commodity table 201 (FIG. 2A). VDTB.1 (1206) and VDTB.2 (1207) designates the first element address and the increment value of a vector which should be formed as was explained before. The operation of the VMSX instruction is to read out column elements whose addresses are respectively designated by the elements A1 to A4 of the list vector designated by the VDTA 1202 and store the read out elements as the vector elements designated by VDTB (1203) (step 1310).
It is to be noted that in the low chart of FIG. 5 the format shown in FIG. 3 was simplified. The first 8 bits of the instruction 1601 was expressed by a mnemonic expression such as "VMSX" or "VEA" . The number R1 of a general register which stores the vector length (i.e., vector element number) was replaced by the vector length itself. The number R2 of a general register which stores an operand descriptor address was replaced by the descriptor, e.g., VDTA or VDTB. Furthermore, the base (B) or dislacement (D) fields have been omitted. The same simplified representation of an instruction format will be adapted even hereinafter.
The next process designating sentence includes a key word SORT-VECTOR 610. The routine 705 for this key word arranges the vector elements of a vector designated by vector designating data designated by the first paramter 611 of the sentence, according to the ascending order of the values of the vector elements. The vector elements designateed by the vector designating data designated by the second parameter 612 are arranged according to the same arrangements of the vector elements designated by the first parameter 611. These arrangments can be performed by a known algorighm called a merge-sort method which is explained, for example, in "The Art of Computer Programming", Vol. 3, "Sorting and Searching" by Knuth, D. E. This sort can be done by plural scalar instructions without using any vector instruction. FIG. 18 shows a vector 1801 which was obtained after this SORT-VECTOR routine 705 is performed on the vector 1503 shown in FIG. 17. In this example, the vector 1503 is arranged in alphabetical order, as alredy mentioned. FIG. 18 also shows a vector 1802, which has been obtained as a result of the alphabetical arrangement of the vector 1503 to frrm the vector 1801.
FIG. 21C shows a flow chart for a program portion for a process of searchng an element coinciding with a key and within the vector 1801. The key is sequentially changed so as to be concident with a respective element of the vector 904 described by the descriptor VDID. In FIG. 21C is employed an algorithm which vectorizes a binary search method for plural keys. A binary search for a single key is explained, e.g., in Knuth, D. E.: "The Art of Computer Programming", Vol. 3 "Sorting and Searching". A binary seach method for a single key applies a comparison between the key and the central element selected among plural elements sorted according to the ascending order, and repeats the comparison after restricting the seach area to a half area of the original containing smaller elements, if the key is smaller than the selected central element. In FIG. 21C, the processing is vectorized by treating the search key as a vector and information (such as a lower limit, a center and an upper limit) which designates the search area for each key also as a vector.
Hereinafter, a vectorized binary search will be explained by referring to FIG. 21C. VDTL, VDTC and VDTU identify vectors which respectivly designate lower limits, centers and upper limits. At the beginning, the search area is all elements of the vector 1801, and, therefore the first element address of the vector 1801 is written in all element locations of the vector described by VDTL as an operation of a vector instruction "VM", and the last element address is written in all element locations of the vector designated by VDTU as an operation of the same vector instruction (steps 2201, 2202). Next, the loop count k (1907) is initizilzeed to 1 (step 2203). According to the binary search, the search field becomes half of the previus one by every one operation, and the search will be finished by repeating the loop operation by log 2M times (step 2204), wherein the initial total element number for the search of a vector 1801 is M (2023). While the search is not finished, an addition is performed, in response to a VEA instruction, of a respective element of the vector for the search lower limits described by VDTL and a corresponding element of the vector for the search upper limits described by VDTU, and the results of the addition are stored in corresonding vector element locations of a vector described by VDTC (step 2205).
US6526407 Aug 12, 1998 Feb 25, 2003 International Business Machines Corporation Method for supporting multiple file-systems in file input/output operations
WO1995011487A1 * Oct 24, 1994 Apr 27, 1995 Fdc, Inc. Database using table rotation and bimapped queries
International Classification G06F1/00, G06F12/00, G06F7/22, G06F9/38, G06F17/30, G06F17/16, G06F12/02
Cooperative Classification Y10S707/99933, G06F17/30595