Method for processing a data base - Patent Review 4644471

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

The present invention relates to a method for processing a data base, especially a relational data base.

In a relational data base, data is managed conceptually in the form of tables. If we arrange the physical storage into the style of a table, however, operations such as insertion or deletion of data become more difficult. Therefore, according to the prior art, as shown by a publication entitled "An Introduction to Database System" written by C. J. Date, pp. 171-179, data elements are dividedly stored within unit areas, each called a page, so that each page includes plural data elements, and in each page there are included pointers which point to a location of a data element. This style of storage of data is suited for insertion or deletion of data elements, but is does not suit fast processing by means of hardware, such as a vector data processor, which processes a large amount of data as a group by a pipeline method. That is, it is necessary in general to provide a large number of data elements to be processed to an arithmetic or logic operation unit (ALU) with as small a time pitch as possible, but it is difficult to do so for data stored with the aforementioned page style. The reasons are as follows.

In a pipelined processor, data elements are fetched in advance of execution of an operation on the data elements by successively generating the addresses of the data elements to be fetched within a data storage, in advance of the execution of the operation, so that data elements are successively supplied to an ALU with a small time pitch. For example, in a vector data processor, vector data elements to be processed are stored at storage locations each with a predetermined address difference from its neighboring location. Therefore, it is possible to successively decode addresses of all vector elements with a small time pitch, based upon only the address of the first vector element and the address difference or displacement between elements. According to the prior art relating to page type data, data elements are not spaced with a constant address difference. Therefore, it is difficult to successively generate the addresses of all vector elements with a small time pitch. Therefore, it is difficult to successively provide data elements to a pipelined ALU with a short time period.

SUMMARY OF THE INVENTION

Therefore, it is an object of the present invention to provide a method for performing a piplelined processing on a data base which includes data elements spaced at irregular address increments.

Accordingly, to the present invention, the data elements for a column or 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. The vector data is processed by a program routine which can perform the processing required by a selected command, and which includes vector instructions each designating at least one set of vector data elements to be executed, in such a manner that vector data elements are fetched successively from the data storage device and are supplied successively to a pipelined arithmetic or logical operation unit.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram of a data base managing system;

FIG. 2A is a diagram of a table provided in the system of FIG. 1;

FIG. 2B is a diagram of another table provided in the system of FIG. 1;

FIG. 2C is a diagram of a search command as used in the system of FIG. 1;

FIG. 2D is a diagram of a table obtained as a result of execution of the search command in FIG. 2C;

FIG. 3 is a diagram of a vector instruction format used in the embodiment in FIG. 1;

FIG. 4 is a more detailed schematic block diagram of the data base managing system in FIG. 1;

FIG. 5 is a diagram of the data arrangement for page type data;

FIG. 6 is a diagram which shows how data is stored in the main storage and the subsidiary storage of a system in FIG. 1;

FIG. 7 is a flow chart of steps for obtaining table row addresses in a memory based upon row numbers;

FIG. 8 is a diagram of a processs sequence designating codes used in the data base managing system of FIG. 1;

FIG. 9 is a schematic diagram of an execution part within the data base managing system of FIG. 1;

FIG. 10 is a flow chart of a CONTROL routine (701) of FIG. 9;

FIG. 11 is a diagram of vector type data obtained from page type table data by means of the execution part (109) of FIG. 1;

FIG. 12 is a diagram of various table definition tables used in connection with the BUILD-VECTOR routine (107) of FIG. 9;

FIG. 13 is a diagram of the vector area (111) of FIG. 1 separated into used and non-used areas (111A and 111B);

FIG. 14 is a diagram of various program variables used in the BUILD-VECTOR routine (1-7) of FIG. 9;

FIG. 15 is a flow chart of the BUILD-VECTOR routine (107) of FIG. 9;

FIG. 16 is a diagram of variables and a list vector formed in an intermediate state of the BUILD-VECTOR routine (107) of FIG. 9;

FIG. 17 is a diagram of vectors obtained as a final result of execution of the BUILD-VECTOR routine (107) of FIG. 9;

FIG. 18 is a diagram of vectors obtained after execution of a SORT-VECTOR routine (705) of FIG. 9;

FIG. 19 is a diagram of data after execution of the JOIN-VECTOR-BY-NESTED-LOOP routine (706) of FIG. 9;

FIG. 20 is a diagram of various variables used in the JOIN-VECTOR-BY-NESTED-LOOP routine (706) of FIG. 9.;

FIGS. 21A to 21C in combination comprise a flow chart of the JOIN-VECTOR-BY-NESTED-LOOP routine (706) in FIG. 9.

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 sequence, 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 112, 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 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 order to faciltate the understanding of the purpose and operation of the described embodiment of the present invention, an example of a search command and the process required thereby will be explained prior to description of the detailed operation.

A commodity table 201 shown in FIG. 2A includes the names of commodites and the names of the salesmen in charge of the respective commodities in pairs. A telephone number table 202 shown in FIG. 2B includes names of employees and their EXT telephone numbers in pairs. The search command shown in FIG. 2C includes three parts. The first part 205 including a key word "SELECT" indicates which columns of the tables of FIGS. 2A and 2B should be selected. The second part 206 including a key word "FROM" indicates from which tables data should be extracted. The last part 207 including a key word "WHERE" indicates what conditions must be satisfied by rows of the tables from which data is to be extracted. Therefore, in the present example, the search command 204 indicates that all possible combinations of the salesman and employee columns of the commodity and telephone tables, respectively, should be searched to find the name of the salesman included in the saleman column of the commodity table 201 which coincides with the name of the employee included in the employee column of the telephone number table 202, and a resultant table is to be provided which compirses three columns relating to commodity, salesman, and EXT with the rows of data from the two tables relating to the searched combinations which satisfy the condition. The result 203 of the search is shown in FIG. 2D. For example, the first row (E) of the salesman column of the commodity table 201 coincides with the fourth row (E) of the employee column of the telephone number table 202. Therefore, the commodity X3 belonging to the commodity column in the first row of the commodity table 201, and the EXT telephone number 331 belonging to the telephone number column in the third row of the telephone number table 202 are listed in the first row of the result table 203 as shown in FIG. 2A, along with the coindicent saleman's name E. The data relating to salesman B, G and C are similarly listed. Thus, it is the formation of the table 203 which is ultimately called for by the command 204, and this data toble 203 is to be formed from data stored in page format in the data buffer area 110 or the subsidiary storage 112.

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. 12, 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.

When the vector data is to be generated for storage in vector area 111, a list comprising the addresses of the vector elements on the respective data pages is first generated for each column of table data, such as 201 in FIG. 2A. Each list vector includes as its vector elements the addresses for respective data elements within the main storage 101 (FIG. 1) each belonging to a respective column of a table, such as table 201 in FIG. 2A. The vector data is then fetched from the main storage 101 (FIG. 1) based upon the list vector in a pipelined manner. At the same time, the vector data designating data is generated. This process of list vector formation will be described in more detail later.

FIG. 17 shows four data vectors 903, 904, 1503 and 1504 thus generate for the table data shown in FIGS. 2A and 2B.

In the preferred embodiment, a sort operation is done on the vectors 1503 and 1504 (Flg. 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 includes 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)

Before going into a detailed explanation of the processing of the system shown in FIG. 1, a brief explanation of the format of a vector instruction will be provided as well as explanation of the details of the data processor 113.

Referring to FIG. 3, the first 8 bit part 1608 of the instruction 1601 indicates the kind of instruction and, in this example, "A4" is a hexadecimal representation showing that this instruction 1601 is a vector instruction. The next two fields 1609 and 1610 designate two general registers R.sub.1 (1603) and R.sub.2 (1605) within the data processor 113 respectively including indication of the vector length and an operand descriptor address. The next field is a base field (B) 1611 which designates a general register 1602 storing a base value. The least significant 8 bits of the base value and the displacement part (D) 1612 of the instruction 1601 indicates what kind of vector instruction the instruction 1601 is.

A vector can be designated by the first element address and its increment value, as exemplified by the vector descriptor 1607. The operand descriptor 1606 holds three addresses for three operand vector descriptors and a control vector address. The address of the operand descriptor 1606 is designated by the address included in the general register R.sub.2 (1605) whose address is designated by the R.sub.2 field (1610) of the instruction.

FIG. 4 shows a more detailed diagram of the data base managing system of FIG. 1. The system in FIG. 4 is realized by a M-280H with an integrated array processor, manufactured by Hitachi Ltd., Japan. An instruction read out of the main storage 101 and held by the instruction register 1701 is decoded by the decoder 1702 based upon the first 8 bit field 1608 of the instruction 1601. If the decoded instruction is a scalar instruction, a scalar ALU 1708 is activated, while if the decoded instruction is a vector instruction, such as a VEA instruction, which will be explained later on in connection with FIG. 15, a set up circuit 1703 is activated. The set up circuit 1703 reads out one of the general registers 1704 designated as a base register by the instruction in the instruction register 1701, and the kind of instruction is detected based upon the sum of the content of the general register designated as the base register by the instruction and the displacement field (A) of the instruction, to indicate the detected kind of vector instruction to the vector ALU 1709, which is comprised of a pipelined ALU. The set-up circuit 1703 reads the vector length from a general register designated by the R.sub.1 field 1609 of the instruction 1601 to send the vector length to the vector ALU 1709. The set-up circuit 1703 reads out an operand descriptor address from a general register designated by the R.sub.2 field 1610 of the instruction 1601, reads out an operand descriptor 1606 based upon the read out operand descriptor address, and, based upon the contents of the read out operand descriptor, reads out vector descriptors. The first element address and an increment included in each vector descriptor are sent to an address generator 1705. Thus, set-up of various data is finished, and the set-up circuit 1703 starts the vector ALU 1709. The address generator 1705 successively generates addresses for operand addresses to access the main storage 101 thereby. The operand vector elements accessed by the address generator 1705 are sent to the vector ALU 1709 successivly and the resultant vector elements are successively sent from the vector ALU 1709 for example to the main storage 101. The operation by the vector ALU 1709 is continued until all elements designated by the vector length have been operated on. As the operation by the vector ALU 1709 and access to the main storage 101 are repeated by a pitch of one machine cycle, the total operation finishes very quickly.

The result of an operation by the vector ALU 1709 may be provided to one of the general registers as scalar data, or to the address generator 1705 as a list vector depending upon the vector instruction. The usage of a list vector by the address generator is necessitated for a VMSX instruction, which will be explained later on in more detail. In an operation of this instruction, a list vector, for example, comprising addresses A.sub.1 to A.sub.4 as shown by a vector 1401 in FIG. 16, is read out as a result of accesses by the address generator to the main storage 101. The read out list vector elements are successively sent to the vector ALU 1709, which passes the read out elements to the addresses generator 1705, which stores the elements within a storage device (not shown). After all list vector elements are read out of the main storage 101, the address generator 1705 provides the read out list vector elements to the main storage 101 as access addresses therefor. In reference to the addresses, the vector elements, for example, X3, X2, X1 and X4 shown in FIG. 11 are successively read out from the main storage 101, and passed through the vector ALU 1709 to the main storage 101 to be stored therein at a storage location designated by the second operand of the VMSX instruction. Therefore, the address generator 1705 accesses the main storage 101 at different locations for different vectors in parallel, so that, for example, a vector is read out from the main storage 101 while another vector is being written into the main storage 101 in parallel to the reading operation.

(Data storage form)

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 beneficial 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.

As is clear from the structure of the data page, a storage location of a row within the subsidiary storage 112 (FIG. 1) can be designated by a data page number i and a slot number j. Therefore, the combination 301 of the data page number i and the slot number j is called a row number.

According to this form of storage of data, it is possible to change only the slot pointer without chaning the row number, when a location of a slot within a data page or the length of a slot is changed. Therefore, this storage form is advantageous for deletion or insertion of a new row of data or for storage of data with a variable length.

(Data buffer area 110 and data buffer directory 401)

When a data page 302 in a subsidiary storage 112 is to be processed by the relational data base managing program 103, the data in the data page 302 is transferred to a data buffer area 110 within a main storage 101 before the processing.

The data buffer area 110 is divided into data buffer units as shown in FIG. 6. Each data buffer unit has its own number, has the same size as the data page 302, and stores a copy of the necessary data page 302. In connection with the data buffer area 110, there is provided a director area 114 within the main storage 101. The directory area 114 includes a data buffer directory 401 which indicates which data buffer is stored in which one of the data buffer units. For example, when data within the i-th data page is stored in a k-th data buffer unit, a pair consisting of the data page number i and the data buffer unit number k is stored in the data buffer directory 401.

(Row number transformation)

A transformation from a row number comprising a page number i and a slot number j to a corresponding storage address of the data for that row within the main storage is carried out in accordance with the sequence of steps in FIG. 7.

At first access is made to the data buffer directory 401 to find whether or not any of the data buffer units hold data read out from the i-th data page (step 502). If a k-th data buffer unit is found to be holding the data, the number k is obtained from the data buffer directory 401. If not, the data in the i-th data page is read out to an empty one of the data buffer units, a pair consisting of the number i of the data page and the number, say k, of the empty data buffer units is written into the data buffer directory 401 (step 503), and then the step 504 if performed. When there is no empty data buffer unit available for the operation of the step 503, a pair consisting of a data buffer number of an appropriately selected data buffer unit and a corresponding data page number is deleted from the data buffer directory 401, and then the step 503 is performed. The selection of the appropriate data buffer unit can be done, e.g., according to the well-known least-recently-used algorithm. Next, an address, say x, of the j-th slot within the k-th data buffer unit is obtained, based upon the data buffer number k, and the j-th slot pointer which indicates the address x (step 505).

The directory area 114, includes a plurality of row number tables 1004 and 1006 (FIG. 12) in correspondence to a respective one of the data tables such as the commodity table 201 (FIG. 2A) and telephone number table 202 (FIG. 2B) to be processed by the program 103 (FIG. 1). The table 404 in FIG. 6 shows one of those row number tables as an example. Therefore, we pick up sequentially row numbers listed in a selected one of the row number tables and sequentially transform each picked up row number into a corresponding address within the main storage, then we can access the data for the row within a selected one of the data tables 201 (FIG. 2A) and 202 (FIG. 2B). In this way, we can access any row within a data table referred to by 201 or 202 to be processed by the program 103 and therefore, any row within any data table to be processed by the program 103.

(Generation of process sequence designating codes)

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.

(Execution of the process sequence designating code)

The execution part 109 of the program 103 includes, as shown in FIG. 9, a CONTROL routine 701, a START-PROCESS routine 702, END-PROCESS routine 703, BUILD-VECTOR routine 704, SORT-VECTOR routine 705, JOIN-VECTOR-BY-NESTED-LOOP routine 706, and so on. Each routine corresonds to a respective one of the key words included in the process sequence designating code 107 generated by the analysis part 105 of the program 103.

The execution part 103 has a program variable area 1201 which stores program variables used by the routines mentined above.

(1) Control routine (701).

This routine first checks whether or not there is any next process designating sentence within the process sequence designating code 107 given by the analysis part 105 (step 802). If there is any, it takes the next process designating sentence out of the process sequence designating code 107 (step 803), calls for a corresponding one of the process routines 702 to 706, to provide a parameter included in the process designating sentence to the corresponding process routine, and to start it (step 804). These steps 802 to 804 are repeated until there is no next process designating sentence.

(2) START-PROCESS routine (702).

This routine is stared by the CONTROL routine 701, when the CONTROL routine 701 takes a key word "START PROCESS" 601 shown in FIG. 8 out of the process sequence designating code 107. This routne 702 initializes the vector designating data area 108 and the vector area 111.

(3) BUILD-VECTOR ROUTINE (704).

In case of the process sequence designating code 107 shown in FIG. 6, this routine 704 is started by the CONTROL routine 701, when the operation of the START-PROCESS routine ends and the next key word "BUILD-VECTOR" is read out by the CONTROL routine 701. This routine 704 changes data stored with a form shown in FIG. 5 to a vector structure. That is, all entries of all rows of a table designated by the first parameter 603 are fetched from the data page area 141, and stored in the vector area 111 separately for each column and with a vector structure. The second and third parameters 604 and 605 in FIG. 8 each indicate a start address of a first and second storage area within the vector designating data area 108 wherein vector designating data regarding the first and second vector respectively comprising the data elements belonging to the first and the second columns of the selected table to be processed by the program 103 are to be stored. If we presume that the table selected by the first parameter 603 to be processed by the program 103 is the table 201 in FIG. 2A, then the operation will be more easily understood by referring to FIG. 11, wherein it is assumed that the first and second rows of the table 201 (FIG. 2A) are stored in the first and second slots 304a, 304b in a data page 302a within a data page area 141 but the third and fourth rows are stored within the first and second slots 304c, 304d in another data page 302b. The reference numbers 303a 303b in FIG. 11 are the slot pointers. At first, we will explain data which are obtained as a result of the execution of the BUILD-VECTOR routine 703. A vector 903 and a vector 904 comprise the data elements included respectively in the first and second columns of the table 201 of FIG. 2A. These two vectors 903, 904 show data of a vector structure produced as a result of the execution of the BUILD-VECTOR routine 704. The vector designating data 901 or 902 held in the vector designating area 108 and includes the first element address 906, an element type 907, an element length 908, and an element number 909. The two reference numerals 901 and 902 respectively represent vector designating data for the vectors 903 and 904. These two data 901 and 902 shows two vector designating data which are produced as a result of the execution of the BUILD-VECTOR routine 704. The start address of the vector designating data 901 or 902 is designated by the second or third parameter 604 or 605 of the second sentence.

The first entries of the two vector designating data 901 and 902, respectively, designate the first element address of the vectors 903 and 904. The second entries "CHAR" of the two data 901 and 902 represent that the elements of the vectors 903 and 904 are both of a character type. The third entries "4" of the two data 901 and 902 show that the element lengths of the two vector data 903 and 904 are both 4 bytes. The fourth entries "4" of the two data 901 and 902 show that the element numbers of the two vector data 903 and 904 are both of a character type. The third entries "4" of the two data 901 and 902 show that the element lengths of the two vector data 903 and 904 are both 4 bytes. The fourth entries "4" of the two data 901 and 902 show that the element numbers of the two vector data 903 and 904 are both 4.

Before giving a detailed explanation of the BUILD-VECTOR routine 704, includng the generation of the vector designating data 901 or 902, an explanation will be given regarding data required for the operation of this routine 704.

FIG. 12 shows a table included in the directory area 114. A reference numeral 1003 or 1005 shows an example of a table definition table for the commodity table 201 (FIG. 2A) or the telephone number table 202 (FIG. 2B). A reference number 1004 or 1006 represents a related row number table. Each table definition table includes a number of columns 1007, plural groups of entries such as shown by 1008 to 1010, a number of rows 1011 and a start address of a related row number table 1002. Each group of entries includes a column name 1008, a column element type 1009 (i.e., a character type or a numeral type), and a column element length 1010 in bytes.

The row number table 1004 or 1006 includes a list of all row numbers belonging to a corresponding table.

A start address of a table definition table 1003 or 1005 is indicated by the first parameter of a process designating sentence including a key word "BUILD-VECTOR". In case of the designating sentence shown in FIG. 10, the first parameter T#1 designates the start address of the commodity table definition of table 1003.

A VTOP entry 11+1 (FIG. 13) provided at the start address of the vector area 111 represents the start address of the non-used area 111B of the vector area 111. A new vector data is stored from the starting area of the non-used area 111B, and not in the used-area 111A.

Program variables used in the BUILD-VECTOR routine 704 will be explained hereinafter in connection with FIG. 14. 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.

Hereinafter, a detailed explanation of the operation of the BUILD-VECTOR routine 704 will be given, by referring to FIG. 15.

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.about.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.

FIG. 16 shows an example of data obtained after the steps 1304 to 1306 have been applied to a process designating sentence starting from the key word "BUILD-VECTOR" 602 shown in FIG. 8. It can be seen that a vector 1401 is comprised of elements of addresses A1 to A4 respectively pointing to row entries for the commodity table 201 (FIG. 2A). Hereinafter, a vector, like a vector 1401, which is comprised of elements which are address pointers to some other data is called a list vector. In VDTA.1 (1204) in the program variable area 1201 is stored the start element address of the vector 1401. VTOP (1101) designates a start address of the non-used area 111B, which is adjacent to a storage location of the element A4.

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 in 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 1-th 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 Al 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).

As the initial value of the list vector elements A1 to A4 designates the addresses of the elements belonging to the first column of the commodity table 201 (FIG. 2A), the vector 903 (FIG. 11) is generated as a result of the first execution of the VMSX instruction.

The execution of this VMSX instruction by the system in FIG. 4 was explained before in connection therewith. As a result of the operation of the VMSX instruction, the vector area 111 is used by the size of the 1-th column vector, and, therefore, the VTOP, which represents the top address of the non-used area, is changed by the size, that is, the product of the vector element length 909 and the vector element number 908 (step 1311). Before the generation of the (1+1)-th column element length to each element of the list vector designated by VDTA (1202), because at this moment each element of the list vector element designates the address of the 1-th column element of the 1-th slot. The next vector instruction VEA is an instruction which requests this addition. That is, the 1-th column element length is added to the j-th element of a list vector designated by the VDTA 1202 and the resultant sum is stored as the j-th element of the list vector, and this operation is repeated for elements corresponding to j=1 to j=the 1-th column element number (909) (step 1315). As a result of the operation of the VEA instruction 1315, each element of the list vector designated by the VDTA 1202 designates the (1+1)-th column element address for a corresponding row position. After 1 is increased by 1 (step 1209), the steps 1307 to 1313 are repeated, until all vectors for all columns are formed (step 1307). Thus, the process for the BUILD-VECTOR routine finishes and the CONTROL routine 701 again is informed of the end of the BUILD-VECTOR routine. The next process designating sentence is read out, and as it includes the same key word "BUILD-VECTOR" in the example of FIG. 8, the same procedure as above is performed or the telephone number table 202 in FIG. 2B. FIG. 17 shows vectors 903, 904, 1503, 1504 and vector designating data 901, 902, 1501, 1502 thus obtained for the commodity table 201 and the telephone number table 202 shown in FIGS. 2A and 2B.

It is to be noted that in the flow chart of FIG. 15, 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 R.sub.1 of a general register which stores the vector length (i.e., vector element number) was replaced by the vector length itself. The number R.sub.2 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.

In order to allow the results of the BUILD-VECTOR routine to be used by other instructions, shown in FIG. 3, it is necessary to make the results available for the subsequent instructions. For that purpose, the followng procedures are required. The vector length for a respective column should be transferred to a corresponding one of the general registers from the element length field 908 (FIG. 11) of a corresponding vector designating data 905, (FIG. 11) so that an instruction can use the data by designating the register by its R.sub.1 field 1609. Similarly, vector descriptor 1607 already explained should be formed based on the first element address field 906 (FIG. 11) and the element length 908 (FIG. 11). The operand address descriptor 1606 should be prepared beforehand and its start address should be stored in the general register R.sub.2, and as the first entry, the start address of the descriptor 1607 should be stored as the first operand vector descriptor address. Similarly, the se