JPS63286931A - Index generating method - Google Patents

Abstract

PURPOSE:To shorten time consumed for the generation processing of an index by performing the OR operation of the index value of a record for the index of a relation to be operated after shifting it by proper number of bits, and obtaining the index concerning the operated result at the tie of the operation. CONSTITUTION:It is assumed that a query to retrieve all taples whose age attribute is 17 and sex distinction attribute is female is issued. For generating a query mask, an age and a sex distinction-binary value conversion procedure is applied to the age (e.g., 17) and the sex distinction (e.g., female), and the binary values 1001 and 10 are obtained. Besides, a person's name attribute is assumed to be 0000 if it is not designated, and these three binary values are shifted by one bit, and the OR operation is executed. Regarding all positions, in which the bits of the query mask 13 obtained by such a way are set, the index records 8, 10, in which all the bits are set at the same bit positions are selected out of the index records 7-12 and the taples 2, 5 are extracted. The extracted contents are checked and the taple 2, the age attribute which is 17 and the sex distinction attribute which is female is extracted and the retrieval is finished.

Description

Detailed Description of the Invention (Industrial Field of Application) The present invention provides a method for performing an operation (for example, a cartesian product operation or a join operation) related to the combination of tuples between relations having superposition codes as indexes. This invention relates to an index creation method that uses an index to obtain an index for a relation that is an execution result.

(Prior Art) Conventionally, in relational database systems, in order to achieve high-speed searches of relation tuples, there have been two methods: preparing an index such as a B"tree for each key attribute of each relation, and a hashing method. A method of preparing a function and a hash table is used.B+t
In a search using an index such as ree, the index for the attribute specified in the search request is traced, and eventually a tuple that satisfies the request is obtained. On the other hand, a search using a hash function and a ladder table is a method in which the ladder table is searched based on the result of applying a hash function to the attribute value specified in the search request to obtain candidate tuples that satisfy the request. It is. When a direct product operation is executed between two relations that has a search means using an index such as B"tree or a hash function and a ladder table, and a search means is also required for the relation that is the execution result. examines the tuples resulting from the execution and creates an index record for the key attribute, or calculates the hash value for all tuples in the result relation to create an index or ladder table. was.

(Problem to be solved by the invention) However, in the above method, it is necessary to create all new indexes and ladder tables for the key attributes of the relation that is the result of the Cartesian product operation, and the relation to which the operation is applied must be created. Pre-existing indexes and ladder tables are not used at all.

A relay system used in practical use has hundreds to tens of thousands of tuples, and it would take an enormous amount of time to create all new indexes, ladder tables, and tables for each key attribute of a single relation. becomes.

If an attempt was made to create all new indexes for the relations that result from the Cartesian product operation, the system would be forced to create the indexes and ladder tables, which had the disadvantage of significantly slowing down the processing speed of the system as a whole. .

The present invention has been made in order to eliminate such drawbacks of the prior art, and it is possible to use an index for a resultant relation when performing a direct product operation, etc. between relations that have an index that can quickly search for tuples of relations. The purpose of the present invention is to provide an index creation method that reduces the time consumed in index creation processing.

(Means for Solving the Problems) The present invention is directed to a method of creating an index for a resultant relation obtained by performing an operation on two indexed relations, and aims to solve the problems of the prior art. , a conversion means for converting an attribute value into a binary value of a predetermined length according to the type of attribute of the operand relation; An OR operation means is provided for performing an OR operation on a bit-by-bit basis by shifting the most significant bit or the least significant bit of a decimal value by a certain number of bits, and the binary value obtained by the OR operation means is used as an index value, and its value. and a pointer that specifies the record that generated it, and configure it as an index record for that record,
This is a dispute in which the index value of the index record of the operand relation is shifted by an appropriate number of bits during the operation, and an OR operation is performed to obtain an index for the result of the operation.

(Function) The present invention can provide an index to a relation and search its tuples at high speed, and can also apply operations when performing a direct product operation, etc. between relations having such an index, and Using an index, it is possible to easily obtain an index for a relation that is the result of an operation.

To create an index, attribute values are p
Prepare a procedure to convert the data into a binary value of the specified length. This procedure is performed by the conversion means. To create an index, first, the conversion procedure by the conversion means is applied to each key attribute of the tuples in the relation according to the type of attribute to obtain a binary value. Next, using the OR operation means, the binary values obtained for all key attributes of one tuple are shifted by a certain bit in correspondence with the order of the attributes of that tuple, and the OR operation is performed for each bit. value (hereinafter,
(referred to as a superposition code) is used as an index value. Then, the index value and the pointer specifying the tuple that generated the value are paired to form an index record for that tuple. A collection of index records prepared for all tuples of a relation becomes the index for that relation.

To use this index to search for all tuples that have one or more attribute values by specifying an AND condition, use the same conversion procedure that was used to create the index. Converts the value of the specified attribute to a binary value, creates a binary value with all bits reset for unspecified attributes, and corresponds to the OR operation of the binary value in the index , with the corresponding attributes in the same order and shifted by the same number of bits, OR operation is performed on each bit of the binary value, and in this result, the index record that is set at the same bit position as the set bit position is When all the tuples corresponding to are extracted, all the tuples that satisfy the condition are included here, and by examining these tuples, it is possible to search for only the tuples that satisfy the condition.

In order to perform a Cartesian product operation between two relations with this index and provide an index to the result, when creating a combination of tuples in the operation, a combination of corresponding index record values is also created, 2, which is the same as when creating an index value using the above procedure from the result of the Cartesian product operation.
By slightly shifting the combination of index values and performing an OR operation so that a binary value can be created, the binary value obtained by 11# is used as the index value for the corresponding tuple, and the index value and the pointer to the corresponding tuple are You can create index records as pairs.

(Actual/Ih Example) Hereinafter, one embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 1 shows an example of a procedure for creating a relation index according to the present invention. The person relation is composed of a "person name" attribute, an "age" attribute, and a "gender" attribute, and has six tuples 1°2.3, 4, and 5.6.

``Person name - binary value conversion procedure'' converts the ``person name'' attribute into a 4-bit binary value, and ``Age - binary value conversion procedure'' converts the ``age'' attribute into a 4-bit binary value. ” converts the “gender” attribute into a 2-bit binary value. The "person name" attribute of tuple 1 is a binary value "
0100”, the “age” attribute is converted to the binary value “001O” by the age-binary value conversion procedure, and the “gender” attribute is converted to the binary value “01” by the gender-binary value conversion procedure.
After shifting these three binary values by 1 bit and performing an OR operation, "01010" becomes the index value of index record 7 for tuple 1. Similarly, the "person name" attribute of tuple 2 is converted to the binary value "1100", the "age" attribute is converted to the binary value "1001", the "gender" attribute is converted to the binary value "10", As a result of performing an OR operation on these three binary values, "11101" becomes the index value of index record 8 for tuple 2. Furthermore, the binary value “10110” is the index value of index record 9 for tuple 3, and the binary value “1”
0011" is the index value of index record lO for tuple 4, the binary value "Of 101" is the index value of index record 11 for tuple 5, and the binary value "01110" is the index value of index record 11 for tuple 6.
This becomes the index value of index record 12 for . Also, index record 7 points to tuple 1, index record 8 points to tuple 2, index record 9 points to tuple 3, index record 10 points to tuple 4, index record 11 points to tuple 5, and index record 12 points to tuple 6. , and the tuple can be accessed from the index record.

FIG. 2 shows an example in which a search using the index according to the present invention is executed based on FIG. In the person relation, the “age” attribute is “17” and the “gender” attribute is °female’
Suppose that a query is issued that searches for all tuples with . To generate the Query mask, the age-to-binary value conversion procedure is applied to the “age” attribute, and the binary value “1” is
001" is obtained, and the gender-binary value conversion procedure is applied to the "gender" attribute to obtain the binary value "lO". Since the "person name" attribute is not specified, the binary value is "0000". These binary values are arranged in the same order as when the index was created, shifted by the same number of bits, and an OR operation is performed. In the query mask 13 obtained in this way, index records 8.11 in which all bits are set in the same bit position are selected from index records 7 to 12 for all positions in which bits are set, and Extract tuple 2.5 pointed to by the index record. Examining the contents of the extracted tuple 2.5, we find that the "age" attribute is °17' and the "gender" attribute is "female."

The search ends by retrieving tuple 2, which is .

FIG. 3 shows an example of creating an index for the execution results of the Cartesian product operation according to the present invention. A relation "Person 3" is created as a result of performing a direct product operation between the relation "Person 1" and the relation "Person 2". The relation “Person 1” has the “Person name” attribute, “Gender” attribute, and “
"Blood type" attribute, and "Index 1" is given to this relation as an index using a superposition code. Each index value of "Index 1" is obtained by hashing each attribute value of the corresponding tuple, shifting the binary value by one bit, and performing an OR operation on the most significant bit. The relation "Person 2" is composed of the "Person Name" attribute and the "Age" attribute, and "Index 2" is given to this relation as an index using a superimposition code. Each index value of "Index 2" is obtained by performing an OR operation on a binary value obtained by hashing the external attribute value of the corresponding tuple by shifting the -L-most bit by one bit. Since the relation "Person 3" is the result of the direct product operation of "Person 1" and "Person 2", it is composed of two "Person name" attributes, "Age" attributes, "Gender" attributes, and "Blood type" attributes. and the index for this relation is '
``Index 3'' is created using the contents of ``Index 1'' and ``Index 2''. When performing a direct product operation between "Person 1" and "Person 2", the tuple tl of "Person 1", t2 and tuple t3 of "Person 2"
Create tuples t6 to tll that combine t5. On this occasion,
Assume that t9 is obtained as a result of combining t2 and t3. Here, the index value of the index record 12 corresponding to t2 is the binary value "01" obtained as a result of hashing each attribute value.
, "toooo", and "01001", the binary value "010110" is obtained as a result of performing an OR operation by shifting one bit at a time starting from the left end. Furthermore, the index value of index record i3 corresponding to t3 is obtained by performing an OR operation on the binary values “01001” and 00011″ obtained as a result of hashing each attribute value, by shifting the left end by 1 bit. The binary value is "010011".

When tuples are combined, the index value of the index record pointing to each tuple is taken out, the most significant bit is shifted by an appropriate number of bits, and an OR operation is performed.

This makes it possible to generate an index value that is equivalent to the case where the index value is generated from the tuples after the combination. In other words, for the index value "010110" of index record 12 of t2 and the index value "otootl" of index record i3 of t3, if the index value of 12 is brought to the left of the index value of 13, the leftmost bit of each The value of index record 19 as a result of the OR operation by shifting 3 bits at the beginning is "010110011".
”, and the index value 1 generated by applying the conversion procedure to t9
The value is the same as 9°.

FIG. 4 shows 23 examples of index creation for the execution results of join operations according to the present invention. The relation [Person 1] is composed of the attributes ``Person Name'', ``Gender'', and ``Blood Type'', and ``Index 1'' is given to this relation as an index using a superposition code. There is. Each index value of "Index 1" is obtained by hashing each attribute value of the corresponding tuple, shifting the binary value by one bit, and performing an OR operation on the most significant bit. The relation "Person 2" is composed of the "Person Name" attribute and the "Age" attribute, and "Index 2" is given to this relation as an index using a superimposition code. Each index value of "Index 2" is a binary value obtained by hashing each attribute value of the corresponding tuple, shifting the most significant bit by one bit, and performing an OR operation. When a join operation is performed between the relation "Person 1" and the relation "Person 2" on the condition that the "person name" attribute is the same, the relation "Person 3" is created as a result. Since the relation "Person 3" is the result of the join operation of "Person 1" and "Person 2", it is composed of two "Person name" attributes, "Age" attributes, "Gender" attributes, and "Blood type" attributes. The index "Index 3" for this relation is created using the contents of the previous "Index 1" and "Index 2". “Person 1” and “
By performing a join operation between "Person 2", the tuple t1゜tl of "Person 1" and the tuples t3 to t of "Person 2" are created.
Create tuples t6 and tl that combine 5. At this time, tl
Assume that t6 is obtained as a result of combining and t3.

Here, the index value “o” of the index record 12 corresponding to tl
totto” is a binary value obtained by hashing each attribute value.
This is the result of performing an OR operation on ``01'', ``10000'', and ``01001'' by shifting them one bit at a time, starting from the left end. Furthermore, the index value "010011" of index record i3 corresponding to t3 is obtained by performing an OR operation on the binary values "01001" and "00011" obtained by hashing each attribute value, by shifting the left end by 1 bit. This is the result. When tuples are combined, the index value of finger 1 - index record [. By kneading, it is possible to generate an index value that is equivalent to the case where the index value is generated from the tuples after the combination. In other words, for the index value "010110" of index record 12 of tl and the index value "010011" of index record i3 of t3, if the index value of 12 is brought to the left of the index value of i3, the leftmost bit of each The value of index record i6 as a result of the OR operation with a shift of 3 bits at the beginning is "010110011", and t
This value is the same as the index value i6' generated by applying the conversion procedure to 6.

(Effects of the Invention) As described above in detail, according to the present invention, in a relation having a large number of tuples, when performing a search using an AND of multiple attributes as a condition, the condition is satisfied. This makes it possible to quickly search all tuples for which Furthermore, to the result of performing a direct product operation or a join operation between relations that have indexes using superposition codes, we can apply operations as the operation is performed or use the index of the ration to obtain superposition codes. It is possible to create an index using . Therefore, compared to a method in which an index is created by carefully examining the contents of the execution result in order to provide an index for the result of executing an operation between relations that have other indexes, the method according to the present invention is more effective than the existing method. Since the index is created by performing very simple calculations, the time required to create the index is much shorter.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram of a method for creating an index according to the present invention, FIG. 2 is an explanatory diagram of a search using an index according to the present invention, and FIG. 3 is a diagram illustrating an example of creating an index for the execution result of a Cartesian product operation. FIG. 4 is a diagram showing an example of creating an index for the execution result of a join operation. 1-6. t1-t11-...Tuples 7-12. ill~ill...index record 13-...
cueri mask

Claims (1)

[Claims] In a method of creating an index for a resultant relation obtained by performing an operation on two indexed relations, the attribute value is set to a predetermined length according to the type of attribute of the operated relation. a conversion means for converting each record of the file into a binary value; An OR operation means for performing an OR operation is provided, and a binary value obtained by the OR operation means is used as an index value, and a pair of a pointer specifying the record that generated that value is used as an index value for that record. An index creation method characterized by configuring the index as a record, shifting the index value of the index record of the operand relation by an appropriate number of bits during operation, and performing an OR operation to obtain an index for the operation result.