JPH0658643B2 - How to create an index - Google Patents
How to create an indexInfo
- Publication number
- JPH0658643B2 JPH0658643B2 JP62121364A JP12136487A JPH0658643B2 JP H0658643 B2 JPH0658643 B2 JP H0658643B2 JP 62121364 A JP62121364 A JP 62121364A JP 12136487 A JP12136487 A JP 12136487A JP H0658643 B2 JPH0658643 B2 JP H0658643B2
- Authority
- JP
- Japan
- Prior art keywords
- index
- relation
- value
- attribute
- record
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
- 238000000034 method Methods 0.000 claims description 27
- 238000006243 chemical reaction Methods 0.000 description 11
- 239000008280 blood Substances 0.000 description 4
- 210000004369 blood Anatomy 0.000 description 4
- 101100489867 Mus musculus Got2 gene Proteins 0.000 description 1
- 230000008878 coupling Effects 0.000 description 1
- 238000010168 coupling process Methods 0.000 description 1
- 238000005859 coupling reaction Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】 （産業上の利用分野） 本発明は、重ね合せ符号を索引に持つリレーションの間
でタプルの結合に係わる演算（例えば直積演算または結
合演算）を実行する際に、その索引を利用して実行結果
であるリレーションに対して索引を得る索引の作成方法
に関するものである。DETAILED DESCRIPTION OF THE INVENTION (Industrial field of application) The present invention relates to the execution of an operation (for example, a direct product operation or a join operation) relating to a join of tuples between relations having a superposition code as an index. The present invention relates to a method of creating an index that uses an index to obtain an index for a relation that is an execution result.
（従来の技術） 従来、リレーショナル・データベース・システムにおい
ては、リレーションのタプルの高速な検索を実現するた
めに、各リレーションのキー属性ごとにB+tree等の索引
を用意しておく方法と、ハシュ関数およびハシュ・テー
ブルを用意しておく方法とが用いられる。B+tree等の索
引を用いた検索では、検索要求で指定された属性につい
ての索引をなぞっていきやがて要求を満足するタプルを
得る。一方、ハシュ関数およびハシュ・テーブルを用い
た検索は、検索要求で指定された属性値にハシュ関数を
施した結果をもとにハシュ・テーブルを検索し要求を満
足するタプルの候補を得るという手法である。B+tree等
の索引またはハシュ関数およびハシュ・テーブルを用い
た検索手段を有する２つのリレーションの間で直積演算
を実行し、その実行結果であるリレーションに対しても
検索手段が必要となる場合には、実行結果のタプルを吟
味して、キーとなる属性についての索引レコードを作成
するか、もしくはハシュ値を計算するという処理を結果
リレーションの全タプルについて実行し、索引やハシュ
・テーブルを作成していた。(Prior Art) Conventionally, in a relational database system, in order to realize a high-speed search of relation tuples, a method of preparing an index such as B + tree for each key attribute of each relation, and hashing A function and a method of preparing a hash table are used. In a search using an index such as B + tree, the index for the attribute specified in the search request is traced until a tuple satisfying the request is obtained. On the other hand, the search using the hash function and hash table is a method of searching the hash table based on the result of applying the hash function to the attribute value specified in the search request and obtaining tuple candidates that satisfy the request. Is. When a direct product operation is executed between two relations that have a search means using an index such as B + tree or a hash function and a hash table, and a search means is also needed for the relation that is the execution result. Examines the tuples of the execution results and creates index records for key attributes, or calculates hash values for all tuples of the result relation, creating indexes and hash tables. Was there.
（発明が解決しようとする問題点） しかし以上の方法では、直積演算の結果となるリレーシ
ョンのキー属性についての索引やハシュ・テーブルは全
て新たに作成する必要があり、演算を適用されるリレー
ションが予め有していた索引やハシュ・テーブルは全く
利用されていない。実用に供されるリレーションでは数
百〜数万件のタプルを有しており、１リレーションの各
キー属性についての索引やハシュ・テーブルを全て新た
に作成するとなると膨大な時間を費やすこととなる。(Problems to be solved by the invention) However, in the above method, it is necessary to newly create all indexes and hash tables for the key attributes of the relation resulting from the direct product operation, and the relation to which the operation is applied is No pre-owned index or hash table is used. A relation used for practical use has hundreds to tens of thousands of tuples, and it would take an enormous amount of time to newly create an index and a hash table for each key attribute of one relation.
このように直積演算の結果となるリレーションに対し全
て新たに索引を作ろうとすると、システムはその索引や
ハシュ・テーブルの作成にかかりきりとなり、システム
全体としての処理速度が著しく低下する欠点があった。In this way, if an index is newly created for all relations resulting from the direct product operation, the system will have to complete the creation of the index and hash table, and the processing speed of the system as a whole will decrease significantly. .
本発明はこのような従来技術の欠点を解消するためにな
されたものであって、リレーションのタプルを高速に検
索できる索引を有するリレーションの間で直積演算等を
実行する際に結果リレーションに対する索引を作成する
処理に消費される時間を短縮する索引の作成方法を提供
することを目的とする。The present invention has been made in order to solve the above-mentioned drawbacks of the prior art. When performing a direct product operation or the like between relations having an index capable of searching tuples of relations at high speed, the index for the result relation is set. An object of the present invention is to provide a method of creating an index that reduces the time consumed for the creating process.
（問題点を解決するための手段） 本発明は、２つの索引付リレーションに演算を施して得
られた結果リレーションについての索引を作成する方法
を対象とし、前記従来技術の問題点を解決するため、被
演算リレーションＡおよびＢの各属性の種類に応じて属
性値を予め指定された長さの２進値に変換し、ファイル
の各レコードについて前記変換したレコード中の各属性
値について得た２進値の最上位ビットもしくは最下位ビ
ットについて一定のビット数Ｍだけずらしてビットごと
にオア演算し、該オア演算により得た２進値を索引値と
したものと、その値を生成したレコードを指定するポイ
ンタとを対としたものをそのレコードについての索引用
レコードとして構成し、結果リレーションＣのレコード
の並びをリレーションＡのあとにリレーションＢが続く
ものとした時には、リレーションＡのあとにＢの索引値
を、Ｍ×ＮＡ（前記リレーションＡのレコードの属性
数）ビットずらしてオア演算を行って演算結果リレーシ
ョンＣについての索引値を得、結果リレーションＣのレ
コードの並びをリレーションＢのあとにリレーションＡ
が続くものとした時には、リレーションＢのあとにＡの
索引値を、Ｍ×ＮＢ（前記リレーションＢのレコードの
属性数）ビットずらしてオア演算を行って演算結果リレ
ーションＣについての索引値を得るようにしたものであ
る。(Means for Solving Problems) The present invention is directed to a method of creating an index for a result relation obtained by performing an operation on two indexed relations, and solves the above-mentioned problems of the prior art. , The attribute value is converted into a binary value having a predetermined length according to the type of each attribute of the operated relations A and B, and obtained for each attribute value in the converted record for each record of the file 2 The most significant bit or the least significant bit of the binary value is shifted by a certain number M of bits, and the OR operation is performed for each bit. The binary value obtained by the OR operation is used as an index value, and the record that generated the value is A pair with a specified pointer is configured as an index record for that record, and the sequence of records of the result relation C is relayed after relation A. When the section B is to be continued, the index value of B after the relation A is shifted by M × NA (the number of attributes of the record of the relation A) bits to perform an OR operation, and the index value for the relation C is calculated. Get, Result The sequence of records of relation C is relation A after relation B.
When A is continued, the index value of A is shifted by M × NB (the number of attributes of the record of the relation B) bits after the relation B, and the OR operation is performed to obtain the index value for the calculation result relation C. It is the one.
（作用） 本発明はリレーションに対して索引を与え、そのタプル
を高速に検索できると共に、このような索引を有するリ
レーションの間での直積演算等を実行する際に演算を適
用したリレーションの索引を用いて演算の実行結果とな
るリレーションについての索引を容易に得るものであ
る。(Operation) According to the present invention, an index is given to a relation, a tuple of the relation can be searched at high speed, and a relation index to which an operation is applied when a direct product operation or the like between the relations having such an index is executed is performed. By using this, an index can be easily obtained for the relation that is the execution result of the operation.
索引を作成するために、属性の種類に応じて属性値を予
め指定された長さの２進値に変換する手続きを用意して
おく。索引を作成するには、先ずリレーションの中のタ
プルの各キー属性について２進数変換手続きを属性の種
類に応じて適応し２進値を得る。次にオア演算により、
１つのタプルの全てのキー属性について得た２進値を、
そのタプルの属性の順番と対応づけて一定のビットずつ
ずらしてビットごとにオア演算した結果得た２進値（以
下、重ね合せ符号と呼ぶ）を索引値とする。In order to create an index, a procedure for converting an attribute value into a binary value having a length designated in advance according to the type of attribute is prepared. To create an index, first, a binary conversion procedure is applied to each key attribute of the tuple in the relation according to the type of the attribute to obtain a binary value. Next, by OR operation,
The binary values obtained for all the key attributes of one tuple,
A binary value (hereinafter referred to as a superposition code) obtained as a result of performing an OR operation for each bit by shifting a certain bit in association with the order of the attribute of the tuple is used as an index value.
そして索引値とその値を生成したタプルを指定するポイ
ンタとを対としてそのタプルについての索引レコードと
する。リレーションのすべてのタプルに対して用意した
索引レコードの集りがそのリレーションに対する索引と
なる。Then, the index value and the pointer designating the tuple that generated the value are paired to form an index record for the tuple. The set of index records prepared for all tuples of a relation is the index for that relation.
この索引を用いて、１つ以上の属性値についてＡＮＤの
条件で指定してその値を持つタプルをすべて検索するに
は、索引を作成する際に用いた変換手続きと同一の手続
きを用いて指定された属性の値を２進値に変換し、指定
されていない属性についてはすべてのビットがリセット
されている２進値を作成し、索引での２進値のオア演算
と対応させて、対応する属性の順番を同一とし、同一の
ビット数だけずらして２進値のビットごとにオア演算を
とり、この結果において、セットされているビット位置
と同じビット位置がセットされている索引レコードに対
応するタプルはすべて抽出すると条件を満足するタプル
はすべてここに含まれており、このタプルを吟味するこ
とで条件を満たすタプルだけを検索できる。To use this index to search for all tuples with one or more attribute values specified by AND conditions, specify the same conversion procedure used to create the index. Converts the value of the specified attribute to a binary value, creates a binary value in which all bits are reset for the unspecified attribute, and corresponds it to the OR operation of the binary value in the index. The attribute order to be set is the same, the OR operation is performed for each bit of the binary value by shifting by the same number of bits, and in this result, it corresponds to the index record in which the same bit position as the set bit position is set. All tuples that satisfy the condition are included here when extracted, and by examining this tuple, only tuples satisfying the condition can be searched.
この索引を持つ２つのリレーションの間で直積演算を行
い、その結果に対して索引を与えるために、演算におい
てタプルの組み合せを作成する際に、対応する索引レコ
ード値どうしでの組み合せも作成し、直積演算の結果か
ら上記の手順によって索引値を作成した場合と同一な２
進値が作成できるように索引値の組み合せを各々を少し
ずらしてオア演算を行うことにより得た２進値を対応す
るタプルについての索引値とし、その索引値と対応する
タプルへのポインタを対として索引レコードが作成でき
る。Carry out a Cartesian product operation between two relations with this index, and when giving a combination of tuples in the operation to give an index to the result, also create a combination between corresponding index record values, 2 which is the same as when the index value is created from the result of the Cartesian product by the above procedure
A binary value obtained by performing an OR operation by slightly shifting each combination of index values so that a binary value can be created is used as an index value for the corresponding tuple, and a pointer to the tuple corresponding to the index value is paired. You can create an index record as.
（実施例） 以下、本発明の一実施例を図面を参照して詳細に説明す
る。(Example) Hereinafter, one example 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 "human life" attribute, an "age" attribute, and a "sex" attribute, and has six tuples 1, 2, 3, 4, 5, and 6.
In the "human life-binary value conversion procedure", the "person name" attribute and in the "age-binary value conversion procedure" both the "age" attribute is set to a 4-bit binary value. Then, the "gender" attribute is converted into a binary value having a 2-bit length. The "person name" attribute of tuple 1 is converted to a binary value "0100" by the person name-binary value conversion procedure, and the "age" attribute is converted to a binary value "0010" by the age-binary value conversion procedure. The "gender" attribute is a binary value "0" by the gender-binary value conversion procedure.
"01010" is converted into 1 "and the result of OR operation by shifting these three binary values by 1 bit becomes the index value of the index record 7 for tuple 1. Similarly, the" person name "attribute of tuple 2 is 2". It is converted to a binary value "1100", the "age" attribute is converted to a binary value "1001", the "sex" attribute is converted to a binary value "10", and an OR operation is performed on these three binary values. As a result, "11101" becomes the index value of the index record 8 for tuple 2. Furthermore, the binary value "101
10 "is the index value of index record 9 for tuple 3, 2
The index record 1 for tuple 4 with the decimal value "10011"
The index value of 0 is the index value of the index record 11 for the tuple 5, and the binary value "01110" is the index value of the index record 12 for the tuple 6. 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. The tuple can be accessed from the index record.
第２図は本発明による索引を用いた検索を第１図に基づ
いて実行した例を示す。人物リレーションのうちで「年
齢」属性が‘１７’でありかつ「性別」属性が‘女性’
であるタプルをすべて検索するキュエリが出されたもの
とする。キュエリマスクを生成するために「年齢」属性
に対しては年齢−２進値変換手続きを適用し２進値“１
００１”を得、「性別」属性に対しては性別−２進値変
換手続きを適用し２進値“１０”を得、「人名」属性は
指定されていないため２進値“００００”とし、これら
の２進値を索引を作成した際と同じ順番で配置し同じビ
ット数だけずらしてオア演算を行う。このようにして得
られたキュエリマスク１３において、ビットがセットさ
れている位置すべてについて、索引レコード７〜１２中
から同一のビット位置についてすべてのビットがセット
されている索引レコード８、１１を選び出し、その索引
レコードが指すタプル２、５を抽出する。抽出したタプ
ル２、５の内容を調べ、「年齢」属性が‘１７’で「性
別」属性が‘女性’であるタプル２を取り出すことで検
索は終了する。FIG. 2 shows an example in which the search using the index according to the present invention is executed based on FIG. Among the person relations, the "age" attribute is "17" and the "gender" attribute is "female"
It is assumed that a query is issued to search all tuples that are. The age-binary conversion procedure is applied to the "age" attribute to generate the query mask and the binary value "1" is applied.
001 "is obtained, and the" sex "attribute is subjected to the gender-binary conversion procedure to obtain a binary value" 10 ". 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 and shifted by the same number of bits to perform the OR operation. In the query mask 13 thus obtained, index records 8 and 11 in which all the bits are set for the same bit position are selected from the index records 7 to 12 for all the positions in which the bits are set. The tuples 2 and 5 pointed to by the index record are extracted. The contents of the extracted tuples 2 and 5 are examined, and the tuple 2 having the “age” attribute of “17” and the “gender” attribute of “female” is taken out to complete the search.
第３図に本発明による直積演算の実行結果についての索
引の作成例を示す。リレーション「人物１」とリレーシ
ョン「人物２」との間で直積演算を実行した結果として
リレーション「人物３」が作成される。リレーション
「人物１」は「人名」属性および「性別」属性および
「血液型」属性とから構成されており、このリレーショ
ンに対しては重ね合せ符号を用いた索引として「インデ
クス１」が与えられている。「インデクス１」の各索引
値は対応するタプルの各属性値についてハシュを施して
得た２進値を最上位ビットについて１ビットずつずらし
てオア演算をとったものである。リレーション「人物
２」は「人名」属性および「年齢」属性とから構成され
ており、このリレーションに対しては重ね合せ符号を用
いた索引として「インデクス２」が与えられている。
「インデクス２」の各索引値は対応するタプルの各属性
値についてハシュを施して得た２進値を最上位ビットに
ついて１ビットずつずらしてオア演算をとったものであ
る。リレーション「人物３」は「人物１」と「人物２」
の直積演算の結果であるから、２つの「人名」属性およ
び「年齢」属性および「性別」属性および「血液型」属
性とから構成されており、このリレーションに対しての
索引「インデクス３」は先の「インデクス１」および
「インデクス２」の内容を利用して作成されたものであ
る。「人物１」と「人物２」との間で直積演算を実行す
ると「人物１」のタプルｔ１，ｔ２と「人物２」のタプ
ルｔ３〜ｔ５を結合させたタプルｔ６〜ｔ１１を作る。
この際、ｔ２とｔ３を結合させた結果としてｔ９を得た
ものとする。ここで、ｔ２に対応する索引レコードｉ２
の索引値は、各属性値にハシュを施した結果得た２進値
“０１”、“１００００”、“０１００１”について、
左端を先頭として１ビットずつずらしてオア演算した結
果得た２進値“０１０１１０”である。さらに、ｔ３に
対応する索引レコードｉ３の索引値は、各属性値にハシ
ュを施した結果得た２進値“０１００１”、“０００１
１”について、左端を先頭として１ビットずつずらして
オア演算した結果得た２進値“０１００１１”である。FIG. 3 shows an example of creating an index for the execution result of the direct product operation according to the present invention. The relation "person 3" is created as a result of performing the direct product calculation between the relation "person 1" and the relation "person 2". The relation "person 1" is composed of a "person name" attribute, a "gender" attribute, and a "blood type" attribute. For this relation, "index 1" is given as an index using a superposition code. There is. Each index value of "index 1" is obtained by performing an OR operation by shifting the binary value obtained by hashing each attribute value of the corresponding tuple by one bit with respect to the most significant bit. The relation "person 2" is composed of a "person name" attribute and an "age" attribute, and "index 2" is given to this relation as an index using a superposition code.
Each index value of "index 2" is obtained by performing an OR operation by shifting the binary value obtained by hashing each attribute value of the corresponding tuple by one bit with respect to the most significant bit. Relation "person 3" is "person 1" and "person 2"
Since it is the result of the Cartesian product operation, it is composed of two "person name" attributes, "age" attributes, "gender" attributes, and "blood group" attributes, and the index "index 3" for this relation is It is created by using the contents of the above-mentioned "index 1" and "index 2". When a direct product calculation is performed between "person 1" and "person 2", tuples t6 to t11 are created by combining tuples t1 and t2 of "person 1" and tuples t3 to t5 of "person 2".
At this time, t9 is obtained as a result of combining t2 and t3. Here, the index record i2 corresponding to t2
The index values of are the binary values “01”, “10000”, and “01001” obtained as a result of hashing each attribute value,
It is a binary value “010110” obtained as a result of an OR operation with the left end as the head and shifting by one bit. Further, the index value of the index record i3 corresponding to t3 is the binary value “01001”, “0001” obtained as a result of hashing each attribute value.
1 "is a binary value" 010011 "obtained as a result of performing an OR operation by shifting the left end by 1 bit by 1 bit.
タプルを結合させる際に各タプルを指す索引レコードの
索引値を取り出し、最上位ビットについて適切なビット
数だけずらしてオア演算を行う。これにより結合後のタ
プルから索引値を生成した場合と等価な索引値を生成で
きる。つまり、ｔ２の索引レコードｉ２の索引値“０１
０１１０”とｔ３の索引レコードｉ３の索引値“０１０
０１１”について、ｉ２の索引値をｉ３の索引値よりも
左にもってきたならば各々の左端のビットを先頭として
３ビットずらして、オア演算した結果の索引レコードｉ
９の値は“０１０１１００１１”であり、ｔ９に変換手
続きを施して生成した索引値ｉ９’と同一の値となる。When combining tuples, the index value of the index record pointing to each tuple is extracted, and the OR operation is performed by shifting the most significant bit by an appropriate number of bits. As a result, it is possible to generate an index value that is equivalent to the case where the index value is generated from the tuples after combining. That is, the index value “01” of the index record i2 at t2
0110 ”and the index value“ 010 of the index record i3 of t3
For 011 ", if the index value of i2 comes to the left of the index value of i3, the leftmost bit of each is shifted by 3 bits and the index record i of the result of the OR operation is calculated.
The value of 9 is “010111001”, which is the same value as the index value i9 ′ generated by performing the conversion procedure on t9.
第４図に本発明による結合演算の実行結果についての索
引の作成例を示す。リレーション「人物１」は「人名」
属性および「性別」属性および「血液型」属性とから構
成されており、このリレーションに対しては重ね合せ符
号を用いた索引として「インデクス１」が与えられてい
る。「インデクス１」の各索引値は対応するタプルの各
属性値についてハシュを施して得た２進値を最上位ビッ
トについて１ビットずつずらしてオア演算をとったもの
である。リレーション「人物２」は「人名」属性および
「年齢」属性とから構成されており、このリレーション
に対しては重ね合せ符号を用いた索引として「インデク
ス２」が与えられている。「インデクス２」の各索引値
は対応するタプルの各属性値についてハシュを施して得
た２進値を最上位ビットについて１ビットずつずらして
オア演算をとったものである。リレーション「人物１」
とリレーション「人物２」との間で「人名」属性が等し
いことを条件として結合演算を実行すると結果としてリ
レーション「人物３」が作成される。リレーション「人
物３」は「人物１」と「人物２」の結合演算の結果であ
るから、２つの「人名」属性および「年齢」属性および
「性別」属性および「血液型」属性とから構成されてお
り、このリレーションに対しての索引「インデクス３」
は先の「インデクス１」および「インデクス２」の内容
を利用して作成されたものである。「人物１」と「人物
２」との間で結合演算を実行することにより「人物１」
のタプルｔ１，ｔ２と「人物２」のタプルｔ３〜ｔ５を
結合させたタプルｔ６、ｔ７を作る。この際、ｔ２とｔ
３を結合させた結果としてｔ６を得たものとする。ここ
で、ｔ２に対応する索引レコードｉ２の索引値“０１０
１１０”は各属性値にハシュを施して得た２進値“０
１”、“１００００”、“０１００１”について、左端
を先頭として１ビットずつずらしてオア演算した結果で
ある。さらに、ｔ３に対応する索引レコードｉ３の索引
値“０１００１１”は各属性値にハシュを施して得た２
進値“０１００１”、“０００１１”について、左端を
先頭として１ビットずつずらしてオア演算した結果であ
る。タプルを結合させる際に各タプルを指す索引レコー
ドの索引値を取り出し、最上位ビットについて適切なビ
ット数だけずらしてオア演算を行う。これにより結合後
のタプルから索引値を生成した場合と等価な索引値を生
成できる。つまり、ｔ２の索引レコードｉ２の索引値
“０１０１１０”とｔ３の索引レコードｉ３の索引値
“０１００１１”について、ｉ２の索引値をｉ３の索引
値よりも左にもってきたならば各々の左端のビットを先
頭として３ビットずらして、オア演算した結果の索引レ
コードｉ６の値は“０１０１１００１１”であり、ｔ６
に変換手続きを施して生成した索引値ｉ６’と同一の値
となる。FIG. 4 shows an example of creating an index for the execution result of the join operation according to the present invention. Relation "person 1" is "person's name"
It is composed of an attribute, a "sex" attribute, and a "blood group" 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 performing an OR operation by shifting the binary value obtained by hashing each attribute value of the corresponding tuple by one bit with respect to the most significant bit. The relation "person 2" is composed of a "person name" attribute and an "age" attribute, and "index 2" is given to this relation as an index using a superposition code. Each index value of "index 2" is obtained by performing an OR operation by shifting the binary value obtained by hashing each attribute value of the corresponding tuple by one bit with respect to the most significant bit. Relation "Person 1"
When the join operation is executed under the condition that the "person name" attributes are equal between the relation "person 2", the relation "person 3" is created as a result. Since the relation “person 3” is the result of the combination operation of “person 1” and “person 2”, it is composed of two “person name” attributes, “age” attributes, “gender” attributes, and “blood group” attributes. And the index "index 3" for this relation
Is created using the contents of the above-mentioned "index 1" and "index 2". By executing a join operation between "person 1" and "person 2", "person 1"
The tuples t1 and t2 are combined with the tuples t3 to t5 of the "person 2" to create tuples t6 and t7. At this time, t2 and t
It is assumed that t6 is obtained as a result of coupling 3 together. Here, the index value “010 of the index record i2 corresponding to t2
110 "is a binary value" 0 "obtained by applying a hash to each attribute value.
This is the result of performing an OR operation by shifting the left end by 1 bit for 1 ”,“ 10000 ”, and“ 01001. ”Furthermore, the index value“ 010011 ”of the index record i3 corresponding to t3 has a hash for each attribute value. Got 2
It is the result of OR operation for the binary values "01001" and "00011" by shifting by 1 bit with the left end as the head. When combining tuples, the index value of the index record pointing to each tuple is extracted, and the OR operation is performed by shifting the most significant bit by an appropriate number of bits. As a result, it is possible to generate an index value that is equivalent to the case where the index value is generated from the tuples after combining. That is, for the index value "010110" of the index record i2 at t2 and the index value "010011" of the index record i3 at t3, if the index value of i2 is located to the left of the index value of i3, the leftmost bit of each is set. The value of the index record i6, which is the result of the OR operation after shifting by 3 bits as the head, is "010111001", and t6
It becomes the same value as the index value i6 'generated by applying the conversion procedure to.
（発明の効果） 以上、詳細に説明したように本発明によれば、多数のタ
プルを有するリレーションにおいて、複数個の属性につ
いてＡＮＤをとったものを条件として検索を実行する際
に、条件を満足するすべてのタプルを高速に検索するこ
とが可能となる。更に、重ね合せ符号を用いた索引を有
するリレーションの間で直積演算または結合演算を実行
した結果に対して、演算の実行に伴って演算を適用した
リレーションの索引を利用して、重ね合せ符号を用いた
索引を作成することができる。従って、他の索引を有す
るリレーション間で演算を実行した結果に対して索引を
与えるために、実行結果の内容を吟味して索引を作成す
る方式に比べ、本発明による方式では既存の索引にきわ
めて簡単な演算を施して作成するために索引の作成時間
が遥かに短時間ですむ。(Effects of the Invention) As described in detail above, according to the present invention, in a relation having a large number of tuples, a condition is satisfied when a search is executed by ANDing a plurality of attributes. It is possible to search all the tuples to be performed at high speed. Furthermore, for the result of performing a direct product operation or a join operation between relations that have an index using a superposition code, the superposition code is obtained by using the index of the relation to which the operation is applied as the operation is executed. The used index can be created. Therefore, in order to give an index to the result of executing an operation between relations having other indexes, the method according to the present invention is much more effective than an existing index in comparison with the method of creating an index by examining the contents of the execution result. The index creation time is much shorter because it is created by a simple operation.
第１図は本発明による索引の作成方法の説明図、第２図
は本発明による索引を用いた検索の説明図、第３図は直
積演算の実行結果についての索引の作成例を示す図、第
４図は結合演算の実行結果についての索引の作成例を示
す図である。 １〜６，ｔ１〜ｔ１１……タプル ７〜１２，ｉ１〜ｉ１１……索引レコード １３……キュエリマスクFIG. 1 is an explanatory view of an index creating method according to the present invention, FIG. 2 is an explanatory view of a search using the index according to the present invention, and FIG. 3 is a view showing an example of creating an index for an execution result of a direct product operation, FIG. 4 is a diagram showing an example of creating an index for the execution result of the join operation. 1-6, t1-t11 ... tuple 7-12, i1-i11 ... index record 13 ... query mask
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 ＩＥＥＥ ＣＯＭＰＵＴＥＲ 20〔３〕 （1987−３）Ｐ．25−32 「情報処理学会 第34回（昭和62年前 期）全国大会講演論文集」Ｐ．1489−1490 ─────────────────────────────────────────────────── ─── Continued Front Page (56) References IEEE COMPUTER 20 [3] (1987-3) P. 25-32 “Proceedings of the 34th National Conference of the Information Processing Society of Japan (the first half of 1987)” p. 1489-1490
Claims (1)
し、ＡもしくはＢのいずれともスキーマの異なる結果リ
レーションＣを得る場合に、該Ｃについての索引を作成
する方法において、 被演算リレーションＡおよびＢの各属性の種類に応じて
属性値を予め指定された長さの２進値に変換し、 ファイルの各レコードについて前記変換したレコード中
の各属性値について得た２進値の最上位ビットもしくは
最下位ビットについて一定のビット数Ｍ（Ｍ：正の整
数）だけずらしてビットごとにオア演算し、 該オア演算により得た２進値を索引値としたものと、そ
の値を生成したレコードを指定するポインタとを対とし
たものをそのレコードについての索引用レコードとして
構成し、 結果リレーションＣのレコードの並びをリレーションＡ
のあとにリレーションＢが続くものとした時には、リレ
ーションＡのあとにＢの索引値を、Ｍ×ＮＡ（前記リレ
ーションＡのレコードの属性数）ビットずらしてオア演
算を行って演算結果リレーションＣについての索引値を
得、 結果リレーションＣのレコードの並びをリレーションＢ
のあとにリレーションＡが続くものとした時には、リレ
ーションＢのあとにＡの索引値を、Ｍ×ＮＢ（前記リレ
ーションＢのレコードの属性数）ビットずらしてオア演
算を行って演算結果リレーションＣについての索引値を
得ることを特徴とする索引の作成方法。1. A method for creating an index for an indexed relation A and B when an operation is performed on the relation A and B and a result relation C having a schema different from that of either A or B is obtained. The attribute value is converted into a binary value having a predetermined length according to the type of each attribute, and the most significant bit of the binary value obtained for each attribute value in the converted record of each record of the file, or The least significant bit is shifted by a fixed number of bits M (M: positive integer), and an OR operation is performed for each bit. A binary value obtained by the OR operation is used as an index value and a record that generated that value. A pair with a specified pointer is configured as an index record for that record, and the sequence of records of the result relation C is related to relation A.
When the relation B is followed by the relation A, the index value of the relation A is shifted by M × NA (the number of attributes of the record of the relation A) bits and the OR operation is performed to calculate the relation C. The index value is obtained, and the sequence of records of the result relation C is related to relation B.
When the relation A is followed by, the index value of A after the relation B is shifted by M × NB (the number of attributes of the record of the relation B) bits to perform an OR operation, and the operation result relation C A method of creating an index characterized by obtaining an index value.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62121364A JPH0658643B2 (en) | 1987-05-20 | 1987-05-20 | How to create an index |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62121364A JPH0658643B2 (en) | 1987-05-20 | 1987-05-20 | How to create an index |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63286931A JPS63286931A (en) | 1988-11-24 |
| JPH0658643B2 true JPH0658643B2 (en) | 1994-08-03 |
Family
ID=14809417
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62121364A Expired - Lifetime JPH0658643B2 (en) | 1987-05-20 | 1987-05-20 | How to create an index |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0658643B2 (en) |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7340481B1 (en) | 2000-01-21 | 2008-03-04 | International Business Machines Corp. | Method and system for adding user-provided content to a content object stored in a data repository |
| US7356766B1 (en) | 2000-01-21 | 2008-04-08 | International Business Machines Corp. | Method and system for adding content to a content object stored in a data repository |
| US8589777B1 (en) | 2000-01-21 | 2013-11-19 | International Business Machines Corporation | Method and system for calculating cost of a compilation of content |
| US7089239B1 (en) | 2000-01-21 | 2006-08-08 | International Business Machines Corporation | Method and system for preventing mutually exclusive content entities stored in a data repository to be included in the same compilation of content |
| US7401097B1 (en) | 2000-01-21 | 2008-07-15 | International Business Machines Corporation | System and method for creating compilations of content |
| US7043488B1 (en) | 2000-01-21 | 2006-05-09 | International Business Machines Corporation | Method and system for storing hierarchical content objects in a data repository |
| US6986102B1 (en) | 2000-01-21 | 2006-01-10 | International Business Machines Corporation | Method and configurable model for storing hierarchical data in a non-hierarchical data repository |
| US6449627B1 (en) | 2000-01-21 | 2002-09-10 | International Business Machines Corp. | Volume management method and system for a compilation of content |
| US6611840B1 (en) | 2000-01-21 | 2003-08-26 | International Business Machines Corporation | Method and system for removing content entity object in a hierarchically structured content object stored in a database |
| US6839701B1 (en) | 2000-01-21 | 2005-01-04 | International Business Machines | Hitmask for querying hierarchically related content entities |
| US7346844B1 (en) | 2000-01-21 | 2008-03-18 | International Business Machines, Corporation | Method and system for moving content in a content object stored in a data repository |
| US7076494B1 (en) | 2000-01-21 | 2006-07-11 | International Business Machines Corporation | Providing a functional layer for facilitating creation and manipulation of compilations of content |
| US10496624B2 (en) | 2013-01-11 | 2019-12-03 | Nec Corporation | Index key generating device, index key generating method, and search method |
-
1987
- 1987-05-20 JP JP62121364A patent/JPH0658643B2/en not_active Expired - Lifetime
Non-Patent Citations (2)
| Title |
|---|
| 「情報処理学会第３４回（昭和６２年前期）全国大会講演論文集」Ｐ．１４８９−１４９０ |
| ＩＥＥＥＣＯＭＰＵＴＥＲ２０〔３〕（１９８７−３）Ｐ．２５−３２ |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63286931A (en) | 1988-11-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0658643B2 (en) | How to create an index | |
| US6507846B1 (en) | Indexing databases for efficient relational querying | |
| JPH04213765A (en) | How to join tables in relational database systems | |
| CN115080599B (en) | Database query SQL field blood relationship generation method | |
| CN113094449A (en) | Large-scale knowledge map storage scheme based on distributed key value library | |
| JP2007534035A (en) | DML statement for densifying data in a relational database system | |
| CN117235037B (en) | A data lineage relationship tracing method based on data entities | |
| CN112487015A (en) | Distributed RDF system based on incremental repartitioning and query optimization method thereof | |
| Demurjian et al. | The multi-lingual database system | |
| CA2253744C (en) | Indexing databases for efficient relational querying | |
| JPH02132559A (en) | Natural connection arithmetic processing system | |
| Kyu et al. | Graph-based indexing method for searching in RDF data | |
| Touzi et al. | New architecture of fuzzy database management systems. | |
| Dittrich et al. | On producing join results early | |
| Ribeiro et al. | Bridging database applications and declarative similarity matching | |
| JPH08235033A (en) | Joint arithmetic system for object-oriented data base management system | |
| Gillenson | Physical design equivalencies in database conversion | |
| US5819277A (en) | Method for generating SQL commands to create an integrated global schema | |
| Xingjian | A database design method for finite element analysis | |
| JP3066836B2 (en) | High-speed access method in knowledge base system | |
| Yahyaoui et al. | Efficient of bitmap join indexes for optimising star join queries in relational data warehouses | |
| KR101460950B1 (en) | The Method and device of NoSQL Query based on denormalized table notation | |
| JPH02190970A (en) | Index structure and search processing method using the structure | |
| US20250139166A1 (en) | Database management system based on prefractal graphs | |
| Burdick et al. | Fault-Tolerant Query Execution over Distributed Bitmap Indices |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |