JPH04213765A - 関係データベースシステムの表を結合する方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータベース管理装置の
分野に関するものであり、とくに、関係データベース管
理装置の少なくとも２つの表を結合するためのハイブリ
ッド技術に関するものである。この技術は、表を結合す
るための確立されている２つの技術の積極的な特徴を組
合わせる点でハイブリッドである。

【０００２】

【従来の技術】関係データベース装置においては、デー
タは表化されたフォーマットで記憶される。データベー
スの表は、共通の特性を共用する行のセットで構成され
る。図３のＳｋｉｌｌ−Ｔａｂｌｅ　は、特定の製造技
能を持つ全ての従業員の記録を記憶する表１０である。 この表は隣接する記憶装置においてレコードが順次並べ
られることを意図するが、実際にはレコードはでたらめ
に記憶されることがある。しかし、この明細書における
説明を明確にするため、および以下に述べる本発明の動
作を強調するために、先の形式が図３に示されている。

【０００３】図３において、表の各水平スライス（「行
」）は従業員番号（ｅｍｐｎｏ）　と従業員名（ｅｍｐ
−ｎａｍｅ）と、技能（ｓｋｉｌｌ）との３つのフィー
ルドを含む。したがって、この表の１行目は従業員番号
（ｅｍｐｎｏ）　が５３、姓（ｅｍｐ−ｎａｍｅ）がフ
ィッシャー、技能が「設計」であるような従業員を示す
。通常、上から下へ行が番号（「識別子」）により識別
されるように、この表は順次番号をつけられ、組立てら
れた行によって様式化される。実際に、行識別子（ＲＩ
Ｄ）　は、この表が含まれる記憶装置の「ページ」にお
けるオフセットに対応する。

【０００４】「結合」は関係データベース装置において
最も強力な演算子の１つである。その演算子は質問の形
でデータベース装置へ示された基準に従って既存の表か
ら新しい表をユーザが作成できるようにする。たとえば
、図４において、図３の表１０を含む管理装置が、表１
０に掲げられている従業員を直属の管理者および所属部
署「ｄｅｐｔ」に関係づける表１２も含む。この装置の
ユーザは、「試験」技能を有し、かつ管理者がデービス
である全ての従業員についての質問を行う。その結果得
られた表が参照番号１４で示されている。

【０００５】表が「結合される」と、結果１４の行は従
業員名と、管理者と、技能とを図４に示すように含む。

【０００６】表１０と１２のどのレコードが述部（すな
わち、列の値についての諸条件）を満すかの判定におい
ては、表の内容が構造化された検査を受ける。これにつ
いては、レコードのｅｍｐｎｏ　フィールドがそれらの
フィールドの垂直の並びを列として取扱うようにして検
査される。表１０と１２の各々において、この列は「結
合列」と呼ばれる。したがって、サーチ中に、表１２の
従業員番号が５３である行に出会い、それが管理者述部
を満す時には、表１０において従業員番号５３の行を見
つけるために表１０のｅｍｐｎｏ　列を参照する。同一
の結合列値をを有する行が表１０でひとたび見つけられ
ると、技能条件が表１０中の行に対して適用される。後
者に類似する諸条件を「ローカル」述部と呼ぶ。という
のは、それらの条件が１つの表の列だけを参照するから
である。

【０００７】表１０と１２において、第１に、結合述部
を満し、第２にそれぞれのローカル述部を満す２つの行
が見つかると、希望の結合表フィールドを含んでいる新
しい行がそれら２つのレコードから形成され、結合表１
４に入れられる。

【０００８】２つまたはそれ以上の表を組合わせて１つ
の結合表にする結合法を、１つのやり方、または別のや
り方を実現するために多くの方法が従来技術で知られて
いる。たとえば、本願出願人は下記のデータベース製品
を提供している。各製品は１つまたは複数の結合法をサ
ポートするものである。ＤＢ２　、ＳＱＬ／ＤＳ、ＡＳ
／４００データベースマネージャ、ＯＳ／２拡張編集デ
ータベースマネージャがそれである。

【０００９】上記質問において述べられた１つまたは複
数のそれらの製品のために用いられる構文が下記のよう
にＳＱＬ　で表される。

【００１０】ＳＥＬＥＣＴ　ｅｍｐ　　ｎａｍｅ，　ｍ
ａｎａｇｅｒ，　ｓｋｉｌｌＦＲＯＭ　ｄｅｐｔ　　ｔ
ａｂｌｅ，　ｓｋｉｌｌ　　ｔａｂｌｅＷＨＥＲＥ　ｄ
ｅｐｔ　　　ｔａｂｌｅ．ｅｍｐｎｏ　＝　ｓｋｉｌｌ
　　ｔａｂｌｅ．ｅｍｐｎｏａｎｄ　ｄｅｐｔ　　　ｔ
ａｂｌｅ．ｍａｎａｇｅｒ　＝　”Ｄａｖｉｓ”ａｎｄ
　ｓｋｉｌｌ　　ｔａｂｌｅ．ｓｋｉｌｌ　＝　”ｔｅ
ｓｔ”この質問は、等しいｅｍｐｎｏ　を有する全ての
行に対して表１０と１２を結合する。ｅｍｐｎｏ　フィ
ールドについての条件は「結合述部」と呼ばれる。結合
述部において言及される表１０と１２の列は表の「結合
」列である。述部マネージャ＝「デービス」と技能＝「
試験」は「ローカル述部」と呼ばれる。

【００１１】この例は限定するものであることを意味し
ない。いいかえると、従来のデータベース装置は、各表
ごとに２つ以上の結合述部と２つ以上のローカル述部を
有する質問をサポートする。また、通常のアンド演算子
とオア演算を用いて、またそれらの演算子の組合わせを
用いて複数の述部を組合わせることができる。更に、結
果行を構成するために結合述部を満す行に対して任意の
数のフィールドを検索できる。

【００１２】従来の２つの特定の結合手順が知られてい
る。各手順はある条件に対してとくに効率的にする特定
の長さを有し、かつ各手順は他条件に対しては費用を高
くする限界を有する。２つの技術は「ネストされたルー
プ結合」および「分類／マージ結合」と呼ばれる。

【００１３】従来のネストされたループ結合技術を理解
するために図４を参照する。図４（および他の図）にお
いて、ｄｅｐｔ−ｔａｂｌｅ構造１２は「外側」表と呼
ばれ、ｓｋｉｌｌ−ｔａｌｌｅ　構造１０は「内側」表
である。ネストされた結合技術においては、ローカル述
部を満す外側表１２中の各行に対して、内側表における
結合列が一致する行に対して走査される。したがって、
従業員の管理者がデービスであるという述部を満す行を
探すために、外側表の結合列が上から下へ走査される。 デービスが管理者として示されている外側表の各行に対
して、インデックスが存在しないとすると、内側表１０
の結合列が上から下へ走査される。走査中は、外側表の
行の結合列値に一致する結合列値を有する各内側表行が
、それの技能条件が試験に等しいかどうかの試験を受け
る。したがって、ネストされたループ走査においては、
２つのネストされた走査が採用される。最初に、ローカ
ル述部を満す行に対する外側表の走査を行い、次にそれ
らの各行に対して、内側表１０の完全な結合列走査また
は結合列におけるインデックスを介するプローブが行わ
れて一致するレコードを探す。

【００１４】従来技術の分類／マージ結合が図５に示さ
れている。この技術の必須条件は、外側表の結合列と内
側表の結合列を基にしてそれらの表を順序づけすること
である。これにより「ＳＯＲＴ」ルーチンの「ＭＥＲＧ
Ｅ　」フェーズと同様にして結合することが可能にされ
る。それに関連して、分類により各表を順序づけること
ができ、または結合列シーケンス中でアクセスするため
にインデックスを介して表に到達できる。各表における
ローカル述部が図５に示すように分類の前に加えられる
。したがって、従業員番号の大きさの順に管理者＝デー
ビスを分類することにより、表１２から表２０が作成さ
れる。同様に、技能フィールド中に「試験」を有する技
能表レコードを選択し、それらのレコードを従業員番号
により順序づけることにより、技能表１０から分数され
た表２２が得られる。結合列の順序がひとたび表に対し
て課されると、結合列で分類された構造を用いて結合が
非常に効率良く行われる。このようにして、得た表２０
における最初のエントリイに対応する従業員番号で表２
２の結合列を走査することにより走査が開始される。一
致に出会うと、結合表行が一致する行から組立てられ、
結合表１４へ入れられる。これに続いて、表２０内の次
のレコードが得られ、表２２の結合列の走査が最後の走
査が停止された場所からピックアップされる。このよう
にして、分類された表２０と２２の結合列が、表の結合
を行う際に１回だけおのおの走査される。これとは対照
的に、ネストされたループ結合手順は、外側表ローカル
述部を満す外側表行が見つけられるたびに内側表の結合
列を完全に走査することを要する。

【００１５】ネストされた結合技術は内側表の結合列上
におけるインデックスを効率的に使用する。内側表へ送
られた結合列値が順序通りであり、かつ内側表がまとめ
られた時、およびインデックス中の一致する値を見つけ
ることにより内側表において検索された行の数が小さい
時に、ネストされた結合技術は良い。知られているよう
に、表の行が、ほとんど、キー値の順序と同じ物理的順
序で格納される時に、インデックスがまとめられる。

【００１６】

【発明が解決しようとする課題】ネストされたループ結
合の欠点は多数ある。第一に、外側表の各行に対して、
外側表の結合列値がキーとして内側表のインデックスへ
送られる。インデックスキーに一致することが見出され
ると、結合手続きは保留され、データページが装置の記
憶装置に存在しなければ、インデックスキーに対応する
データページを取出すためにＩ／Ｏ　手続きが指名され
る。 Ｉ／Ｏ　プロセスを指名するために結合プロセスを保留
することにより、両者は「同期」させられる。同期Ｉ／
Ｏ　は、内側表におけるまとめられたインデックスアク
セスに対してさえも行われる。その理由は、外側表の結
合列値が順序づけられないことがあるか、外側表結合列
値の間に広い間隙が存在することがあるからである。知
られているように、同期Ｉ／Ｏ　プロセスは、ページ数
を累積して、それらのページ数をまとめてフェッチする
か、ページをプリフェッチする非同期Ｉ／Ｏ　プロセス
よりも長くかかる。ネストされたループ結合の第２の欠
点は、内側表がインデックスの樹を介してアクセスされ
る時に生ずる。 この場合には、内側表の各行の結合列値が、根から始ま
ってインデックスの樹を介してサーチされ、一致するキ
ー値に対する葉ページまで続く。このアクセスモードは
ランダム「インデックスプローブ」と呼ばれている。外
側表の結合列値がはるかに離れていると、インデックス
プローブは効率的である。結合列値が接近していると、
葉ページを通る走査の方がより効率的である。しかし、
この場合には、ネストされたループ結合は、以前の行処
理から得た情報を使用しない。

【００１７】最後に、ネストされたループ結合において
は、外側表中に重複結合列値を有する行を、外側表のロ
ーカル述部を含んでいるフィールドでアクセスがキーさ
れる時のように、ランダムにアクセスできる。したがっ
て、外側表中の重複行は、重複行のうちの第１の重複行
に対するＣＰＵ　処理時間と同じ処理時間を必要とし、
内側表のデータページが記憶装置になければ、そのデー
タページをフェッチすることを要求できる。

【００１８】分類／マージ結合の欠点は、フィルタリン
グのために結合列インデックスを効果的に使用すること
に失敗することである。この技術においては、結合結果
に関与しない行は分類されることもあり、その結果とし
て、後で結合述部により除去される行のアクセスにおい
て不必要なＣＰＵ　時間およびＩ／Ｏ　時間を費やすこ
とになる。

【００１９】ネストされたループ結合と分類／マージ結
合の性能の違いは、１桁またはそれ以上も異なることが
あることを発明者は認めた。含意は、結合法を不正確に
選択するためのコストが非常に高いことである。更に、
不十分または不正確な統計、あるいは表における相関さ
せられた列値のために、今日のデータベース装置は実行
的に大幅に費用がかさむことがある結合法をしばしば選
択する。

【００２０】２つの主な従来の結合法の諸欠点を避ける
と同時に、２つの方法の利点を保持する代りの方法に対
する需要がある。

【００２１】本発明の目的は、ネストされたループ結合
技術と分類／マージ結合技術を強めるために、既存のデ
ータベース構造を用いる結合技術を得ることである。

【００２２】本発明の別の目的は、多数のプロセスを並
列またはパイプライン状に処理できるようにして応答時
間を短くすることである。

【００２３】

【課題を解決するための手段】本発明は、結合列につい
てのインデックスと、外側表および内側表のローカル述
部とを利用し、効率的な重複処理および効果的なインデ
ックス検索でデータページに対する順次アクセスを行う
ハイブリッド結合技術で構成される。本発明のハイブリ
ッド結合技術は、ループ結合法および分類／マージ結合
法の性能を向上させる。このハイブリッド結合技術は広
範囲の用途に対して従来技術のいずれよりも良い。本発
明のハイブリッド結合技術は、データベース装置があい
まいな状況にある時には安全な技術を常に提供する。

【００２４】本発明のハイブリッド結合技術は関係デー
タベース管理装置の２つの表を３段のプロセスで結合す
る。最初に、本発明を実施する任意の装置が、結合述部
がアンド操作により組合わされた時に内側表の１つまた
は複数の結合列に存在することを求め、または内側表の
各結合列についてのインデックスが、全ての結合列につ
いてのインデックスの結果を達成するためにインデック
スのアンド操作またはオア操作を行うことができる場所
に存在することを求めることが主張される。

【００２５】

【作用および発明の効果】正式にいえば、それらの前提
条件は次の通りである。

【００２６】１．結合述部が（Ｐ１　ＡＮＤ　Ｐ２　Ａ
ＮＤ…Ｐｎ）の形式であるならば、インデックスが内側
表の１つまたは複数の結合列に存在することを本発明は
必要とする。ここに、Ｐｉ、ｉ＝１，…，ｎ，　は各表
の１つの列を含む結合述部である。

【００２７】２．結合述部が（Ｐ、ＯＲ　Ｐ２　ＯＲ…
Ｐｎ）　の形式であるならば、内側表の全ての結合列が
（個々にまたはまとめて）十分なインデックスで表わさ
れるように、それらのインデックスを設けることを本発
明は求める。

【００２８】３．第１の条件と第２の条件で与えられて
いるように、結合述部が接続的（ＡＮＤ）　形式と離接
的（ＯＲ）形式を組合わせた複合述部であれば、第１の
条件と第２の条件を対応する条件に対してホールドせね
ばならない。

【００２９】本発明の方法の第１の段階においては、内
側表の結合列についてのインデックスが、外側表の行の
そのような値に一致する結合列値を有する内側表の行に
対して走査される。これは外側表と、結合列についての
内側表のインデックス（これは本質的に順序づけられて
いる）とを１回通ったのに応じて行われる。外側表は結
合列において（外側表の結合列についてのインデックス
を分類、走査、またはまとめられたインデックスにより
ある表を走査することにより）順序づけられる。この段
階が終ると、それらの一致する外側表行へ連結されてい
る選択された内側表ＲＩＤ　を含んでいる一時的な作業
表が発生される。

【００３０】第２の段階においては、一時的な作業表が
、すでに順序づけられていなければ、ＲＩＤ　により順
序づけられ、またはほとんど順序づけられる。

【００３１】最後に、内側表の選択された行をフェッチ
するために内側表の行のＲＩＤ１１　ステートメントが
用いられる。ローカル述部と結合述部がそれらの行へ加
えられ、両者を満す述部がそれらの一致する表の行に組
合わされ、結合表に置くために戻される。

【００３２】本発明の非常に独特の性質は、データをそ
れの物理的（ｐｈｙｓｉｃａｌ）順序でアクセスできる
ことである。これは非常に効率的なＩ／Ｏをサポートす
る。データをそれの物理的な順序でアクセスすることを
サポートする際には、本発明はデータの区画によりタス
クをアクセスするデータの並列実行も可能にする。更に
、方法のコードなる過程をおのおの実行する別々のプロ
セッサで並列タスクを実行することにより、本発明を実
施できる。 １つの過程が結果を次の過程へ供給する（パイプライニ
ング）。

【００３３】

【実施例】本発明を詳しく説明するための準備として、
以下に述べる技術はＳＱＬ　型関係データベース管理装
置、またはそれと同等の装置を含むプログラム式コンピ
ュータ装置で実行可能であることを述べておく。ＳＱＬ
　型装置は本願出願人の製品であるＤＢ２　およびＳＱ
Ｌ／ＤＳデータベース管理装置のような製品で具体化さ
れる。両方の製品はアイビーエム・システム／３７０　
型、または同等の装置で実行できる。とくに、ＤＢ２　
はＭＶＳ／３７０　およびＭＶＳ／ＸＡオペレーティン
グシステムに使用することを意図しており、ＳＱＬ／Ｄ
Ｓデータベース管理装置はＶＭ／ＳＰ　、ＵＭ　ＸＡ　
システム製品、ＶＳＥ／ＳＰおよびＶＳＥ　オペレーテ
ィングシステムに使用することを意図するものである。 ＳＱＬ　型のデータベースマネージャが、本願出願人に
より、ＤＳ／２　ＥＥ　製品およびＡＳ／４００製品に
関連して提供される。また、基礎を成すＳＱＬ　型装置
に対するユーザインターフェイスが、アイビーエム社か
ら入手できるＱＭＦ　設備のようなユーザ質問製品によ
り提供される。その設備は、本願発明により関係データ
ベースへ質問をベースとするユーザインデックスも提供
できる。

【００３４】本発明のハイブリッド結合技術が処理フロ
ー１，２，３に示されている。それらの処理フローを表
１０と１２の例である結合を参照して説明する。この例
が図１に示されている。それらの表は本発明の技術の３
つの相を示す。３つの表が、基礎を成すＳＱＬ　型装置
をとる疑似コードの態様で提示されている。疑似コード
においては、外側表（表１２）は「Ｔ１」と呼ばれ、内
側表（表１０）はＴ２と呼ばれる。知られているように
、ＳＱＬ　装置は、データベースレコードを順次アクセ
スするために、「カーソル」と呼ばれる構造を採用する
。これに関して、質問のＳＥＬＥＣＴステートメントに
より形成される。ＳＱＬ　プログラミングにおいては、
ＳＥＬＥＣＴステートメントにより宣言されたカーソル
の実行を開始するためにＯＰＥＮステートメントが採用
される。質問のＦＲＯＭ項に指定されているデータベー
ス構造にカーソルが適用される。 ＯＰＥＮステートメントは指定されている構造をアクセ
スし、結合条件とローカル条件を満すレコードのフィー
ルドを得る。従来、全ての指定されている構造が完全に
アクセスされるまで、ＯＰＥＮカーソル処理が再帰的に
進む。 ＯＰＥＮ手順は１組の中間結果を組立てる。カーソル処
理のフェッチ相中にレコードを検索するためにそれらの
中間結果は用いられる。

【００３５】ＳＱＬ　処理におけるＦＥＴＣＨ　ステー
トメントは、中間結果を基にしてレコードを得、ＳＥＬ
ＥＣＴステートメントにおいて指定されているフィール
ドを含む結合表を構成する。

【００３６】最後に、ＣＬＯＳＥ　ステートメントがカ
ーソルおよび関連する任意のプロセスを非活動化する。

【００３７】次に処理フロー１と図１を参照する。カー
ソルが開かれた時に本発明の技術の第１の相が呼び出さ
れる。第１の相の間に中間結果が得られ、外側表（表１
２）の行と、内側表（表１０）の中のそれの一致する行
の行識別子（ＲＩＤ）　を供給するために表がＦＥＴＣ
Ｈ　時刻に用いられる。第１に、分類されたアクセスを
表１２に対して行う走査がステートメント１００におい
て開かれる。 総称的には、「走査」というのは、表のレコードが行ご
とに順次検査されるレコードサーチのプロセスを指す。 ステートメント１０１においては、内側表、図５の表１
０、の結合列で走査が開かれる。

【００３８】処理フロー１ カーソル解放処理 １００　　　　分類されたアクセスを行う走査を解放１
０１　　　　Ｔ２インデックスで操作を解放１０２　　
　　Ｔ１上のＥＯＦ／Ｔ２上のＥＯＦまで実行１０３　
　　　　　　　すべての必要な列を検索し、すべての入
手可能な述部を適用しながら次のＴ１行を得る。 １０４　　　　　　　　Ｉｆ　　新しいキー値が複製で
ない場合、Ｔｈｅｎ １０５　　　　　　　　　　　　Ｔ２よりＲＩＤリスト
をフェッチ、ここでインデックスキー＝結合列値 １０５ａ　　　　　　Ｅｌｓｅ　　前のＲＩＤリストが
見つかればそれを使用 １０６　　　　　　　　Ｉｆ　　ＲＩＤリストが見つか
れば、　　Ｔｈｅｎ １０７　　　　　　　　　　　　中間結果表中に複合行
（Ｔ２　　ＲＩＤ、Ｔ１　　データ）を形成 １０８　　　　Ｅｎｄ １２０　　　　分類から得られたすべてのランをマージ
１２１　　　　Ｉｆ　　ローカル術部（Ｔ２）の列のイ
ンデックスが使用されていれば、　　　　　　　　　　
　　Ｔｈｅｎ１２２　　　　　　　　修飾された行要に
分類されたＲＩＤリストを形成 １２３　　　　　　　　ＲＩＤと中間結果表のそれとを
ＡＮＤ走査 １２５　　　　Ｉｆ　　ＥＯＦ　　（Ｔ１またはＴ２の
いずれかの）、　　Ｔｈｅｎ １２６　　　　　　　　Ｔ１上の走査を終了１２７　　
　　　　　　Ｔ２インデックス上の走査を終了１３０　
　　　Ｔ２上の連続的なプリフェッチ走査を解放１３１
　　　　中間結果表上の連続的なプリフェッチ走査を解
放

【００３９】処理フロー２ フェッチカーソル処理 ２００　　　　（復帰した行／ＥＯＦ）まで実行２０１
　　　　中間結果表中の次の行をフェッチ２０２　　　
　Ｉｆ　　Ｔ２　　ＲＩＤが最後のものと同じであれば
、Ｔｈｅｎ ２０３　　　　　　　　同じ内側表を再使用２０４　　
　　　　　　Ｉｆ　　行がすべての術部を満足していれ
ば、Ｔｈｅｎ ２０５　　　　　　　　　　　　結果行を形成し、ユー
ザに戻す戻った行を表示 ２０６　　　　　　　　Ｅｌｓｅ ２０６ａ　　Ｅｌｓｅ ２０７　　　　　　　　すべての術部を適用しながらＴ
２行をフェッチ（結合術部含む） ２０８　　　　　　　　Ｉｆ　　行がすべての術部を満
足するならば、Ｔｈｅｎ ２０９　　　　　　　　　　　　結果行を形成し、ユー
ザに戻す２１０　　　　　　　　　　　　戻った行を表
示２１１　　　　Ｅｎｄ

【００４０】処理フロー３ カーソル閉鎖処理 Ｉｆ　　Ｔ２上の走査が解放されているとき、Ｔｈｅｎ
それを閉鎖 Ｉｆ　　中間結果表上の走査が解放されているとき、Ｔ
ｈｅｎそれを閉鎖

【００４１】表１０のインデックスについての走査を以
下に詳しく説明する。この走査は表１０の結合列につい
てのインデックスを順次進んで、表１０の結合述部を満
す行のＲＩＤ　を検索する。走査の結果を図１に参照し
て理解できる。インデックスが、たとえば、樹木の形を
有するものとすると、「葉」と呼ばれるそれの最も外側
（最低）の部材が、（ｋｅｙ　ｖａｌｕｅ：ＲＩＤ　ｌ
ｉｓｔ）の形を有するインデックスフォーマットで表１
０の行のＲＩＤ　を含む。走査は表１０の結合列につい
てキーイングするから、キー値は外側表行の結合列の値
であり、パラメータ「ＲＩＤ　ｌｉｓｔ」はそのキー値
を有する表の行を識別するリストである。

【００４２】図１の手続き３５はローカル述部　（管理
者＝「ＤＡＶＩＳ」）　により表１２の行を分類し、対
応するレコードの結合列値によりそれらのレコードを順
序づける。処理の結果が表３８により表されている。

【００４３】処理フロー１のカーソル開放プロセスへ戻
って、ステップ１０２においてＤ０ループが開かれる。 ファイルの終り（ＥＯＦ）　標識に表１２で遭遇する。 この手続きにおいては、外側表、表１２、中の、外側表
に対してローカルである述部を満す、各行に対して、キ
ー値が表１２の行の結合列値に等しいようなセットに対
して表１０のインデックスからＲＩＤ　リストが得られ
る。これの例外は、表１２の行の結合列値が以前に処理
されたものを複製する時である。

【００４４】現在アクセスされている表１２の行の結合
列値が表１０についてのインデックスのインデックスキ
ーに一致すると仮定すると、（外側表の列のサブセット
と内側表のＲＩＤ　で構成された）複合行がステップ１
０６および１０７で構成される。（このサブセットは質
問を実行するために必要とされる全ての列を含む。）複
合列が形成されるにつれて、それをＴ２のＲＩＤ　列で
分類するために送ることができる（ステップ１０７ａ）
。多重プロセス（またはタスク）においては、１つのプ
ロセスが１つの複合行を生じて、それらの行を分類のた
めに送ることができる。分類された全てのランはステッ
プ１２０で組合わされる。複合行は中間結果表１２０を
形成する。その中間結果表は図１に参照番号４５で示さ
れている書式を有する。この表は表１０についてのイン
デックスから検索されたＲＩＤ　値で順序づけられる。

【００４５】ステップ１２１〜１２３においては、表１
０に対してローカルである述部で参照される列に１つま
たは複数のインデックスが存在する場合に、中間結果表
４５のサイズを小さくするための用意が行われる。ステ
ップ１０６と１０７は、ＲＩＤ　リストが２つ以上の値
を含むならば、２つ以上の複合レコードを構成すること
に注目されたい。これがたとえばインデックスセット（
５３：１，１１）　により示されている。このインデッ
クスセットは従業員番号５３を有するレコードに対して
表１２における２行の場所を示すものである。表１０に
対してローカルである述部にインデックスが存在する、
すなわち、技能＝「試験」である、と仮定すると、ロー
カル述部を満すことにより「修飾する」対応するレコー
ドを有するＲＩＤ　の分類されたリストを作成するため
にローカル述部インデックスが採用される。修飾しない
ＲＩＤ　は表にのせられない。それから、分類されたＲ
ＩＤ　リストは中間結果表とともにアンド操作されて、
修飾されたＲＩＤ　を表に入れる。この場合には、ステ
ップ１２３でステップ１２０を行うことができる、すな
わち、分類された全てのランの「組合わせ」が行われる
と同時に「アンド操作」が行われる。ステップ１２５〜
１２７において、手順は表１０と１２で走査を閉じる。

【００４６】最後に、内側表で順次プリフェッチ走査が
開かれる。内側表からの修飾された行がフェッチされ、
かつ外側表の対応する行に組合わされて結合表を形成す
る次の処理フェーズに対してそれらの走査が求められる
。

【００４７】本発明の１つの独特な特性は表データをそ
れの物理的な順序でアクセスする備えがされていること
である。これは効率的なＩ／Ｏ　をサポートする。本発
明は表データをそれの物理的な順序でアクセスするから
、本発明はデータの区画により並列実行の機会も与える
。並列タスクが表デジタルデータをアクセスし、その時
に各並列タスクが、一緒に物理的にまとめられるデータ
のそれの部分に対して各並列タスクが作業すると仮定す
ると、Ｉ／Ｏ　の競合を最少まで減少できる。質問がＩ
／Ｏ　に対するものであると、各並列実行タスクがそれ
ぞれのＩ／Ｏ　装置により表データをアクセスできる。

【００４８】質問がＣＰＵ　に対するものであると、各
並列実行タスクをそれの個々のプロセッサに対して実行
してＣＰＵ　の能力をフルに利用することが望ましい。 本発明は表データをそれの物理的順序でアクセスするか
ら、各並列タスクは、たとえばプリフェッチ機能によっ
て、それ自身のＩ／Ｏ　を大量に実行できる。これはＩ
／Ｏ　の効率を高めるばかりでなく、種々の並列タスク
の間での起り得るＩ／Ｏ　競合を減少する。

【００４９】更に、データの区画により並列関係を利用
するために、表とインデックスのアクセスのより多くの
類似を下記のように行うことができる。それと同時に、
外側表のアクセス中に、トーナメントの樹を利用するこ
とにより、分類されているランを形成できる。分解され
たランは一時的な表に書込むことができる。次に、分類
されたランを含んでいる一時的な表を組合わせのために
アクセスでき、結合列についてのインデックスが同時に
アクセスされる。組合わされたランからの行はインデッ
クスからのＲＩＤ　に組合わされる。それと同時に、行
とＲＩＤ　の組合わせを、ＲＩＤ　により分類するトー
ナメントの樹へ導入することにより形成されたランは、
一時的な表へ書込むことができるランを形成する。最後
に、それらの一時的な表をアクセスおよび組合わせるこ
とができ、内側表は同時にアクセスされる。

【００５０】ＣＰＵ　を並列に利用することにより応答
時間を一層短縮するために、先に概略的に述べたステッ
プを、多数のプロセスまたはタスクを用いることにより
、並列に実行できる。あるステップを実行するプロセス
は、それのステップの結果が発生されるにつれて、それ
らの結果を、次のステップを実行するプロセスへ送る。 このようにして、ステップはパイプラインを形成する。

【００５１】次に、本発明の処理の第２の段階を理解す
るために処理フロー２と図１を参照する。ＦＥＴＣＨ　
が発せられると第２の段階が呼出される。このフェーズ
中に、中間結果４５がアクセスされ、対応する内側表行
が検索され、ユーザへ戻される。

【００５２】処理フロー２のＦＥＴＣＨ　処理が繰返し
行われ、ループはステップ２００で開かれ、ステップ２
１１で閉じられる。ループにおいては、中間結果表４５
の行を順次プリフェッチし、内側表１０の対応する行を
順次アクセスするために、ステップ１３１における中間
結果表の走査と、ステップ１３０における順序プリフェ
ッチ走査とが用いられる。したがって、ステップ２０１
において、表４５の次の行がフェッチされる。フェッチ
される行のＲＩＤ　が以前にフェッチされた行のＲＩＤ
　と同じであるとすると、同じ内側表の行が再び用いら
れる。さもないと、対応する内側表の行が順次プリフェ
ッチされる内側表行のセットから検索され、全ての述部
がそれに対して評価される。行が述部を満したとすると
、質問のＳＥＬＥＣＴステートメントにより指定された
ようにして作成される。結果行が作成されて、中間結果
表の全てのエントリイがアクセスされるまでこのように
して戻される。処理フロー３のＣＬＯＳＥ　処理がまだ
開かれている任意の走査を閉じ、本発明に従って処理を
終る。

【００５３】動作の例 図１の例は先に説明され、処理フロー１〜３で具体化さ
れる本発明を示す。本発明の１つの主な前提条件は、結
合列についての良くまとめられたインデックスで結合述
部または表スペースについて分類または索引することに
より、外側表を順序づけることである。図１において、
外側表１２を実効的に走査して、それローカル述部の試
験をまず行うことにより、これが満される。示されてい
る値「デービス」に一致する管理者列を有する表１２の
全ての列が、表３８に示されているように従業員番号に
より順序づけられる。参照番号３５の手続きにより外側
表を順序づけることに本発明は限定されものでないこと
が断言される。知られているように、外側表の１つまた
は複数の結合列にインデックスが存在するものとすると
、順序はインデックス中に暗に含まれる。

【００５４】本発明は、内側表の結合列について索引づ
けすることによる内側表の順序づけを前提とするもので
もある。また、索引づけは順序づけを意味し、ＲＩＤ　
が順序づけられるならば、表の行の順序アクセスをサポ
ートする。

【００５５】したがって、結合列により順序づけおよび
分類された外側表１２の行を用いて、本発明は、インデ
ックスキー値として、５３である最初のレコードへ従業
員番号をとる。このキー値は表１０のインデックスを走
査するために用いられる。これらに関して、表１０のイ
ンデックスについての走査はセット（１：９）　でスタ
ートし、そこからセット（５３：１，１１）　まで走査
する。リスト１，１１がセットからフェッチされ、２つ
の複合行が作成されて表４５に置かれる。表に置かれる
行は順序づけられるから、最初の行はＲＩＤ値１により
示される行であり、第２の行はＲＩＤ　値１１によ

【００５６】り示される行である。プロセスは構造３８
中の次の外側表行へ戻り、キー値を１００へ変える。キ
ー値はインデックス走査へ送られる。そのインデックス
走査はキー値セットから順次動き、そこで停止を続け、
セット（１００：３）　へ動く。複合行が構成され、表
４５の行１と１１の間に順次置かれ、外側表走査は行２
０７へ動く。表３８のＥＯＦ　またはインデックスのＥ
ＯＦ　に遭遇するまで、この手順は続く。

【００５７】中間結果表中の行が形成されるにつれて、
内側表のＲＩＤ　で分類するためにその行を送ることが
できる。分類された全てのランの組合わせを図１の表４
５における結果について行うことができる。フェッチス
テップを行うために内側表行を検索するために必要なＩ
／Ｏ　処理を、表４５中のＲＩＤ　のリストをバッファ
マネージャへ送り、それから、検索された内側表の行を
、Ｉ／Ｏ　の終了後に、１つずつアクセスすることによ
り、１つの非同期ステップで行うことができる。検索さ
れた内側表の行は中間結果表４５の順序でとられる。こ
の場合には、表における初めの２つのエントリイがロー
カル述部「試験」を加えることに失敗する。その理由は
、技能表の初めの行が「設計」を示し、第２の行が「符
号」を示すからである。しかし、内側表１０の行３に対
応する表４５における第３のエントリイはローカル述部
に適合する。したがって、ＦＥＴＣＨ　は結果行ウェス
ト／デービス／試験を作成し、それをユーザへ戻す。同
様に、結果表５０における第２のエントリイと第３のエ
ントリイは、ローカル述部を満す内側表の行に対応する
。表１２のローカル述部は外側表のレコードへすでに加
えられているから、結果レコードのマネージャフィール
ドが全てエントリイ「デービス」を含む。

【００５８】内側表インデックス走査内側表結合列へキ
ーされている内側表インデックスを効率的に走査する方
法が図２と処理フロー４に示されている。インデックス
走査は、処理フロー４の技術を用いることにより、特定
のより低い（より高い）キー値を持つ先行する（後続す
る）ページにある一が現在保持されているならば、特定
のより高い（より低い）キー値を持つ葉ページへの高速
前進（または後退）運動をサポートする。

【００５９】処理フロー４を理解するために、内側表結
合列へキーされているインデックスの樹の一部を示す図
２を参照する。この樹の構造は根の節１００を有する。 この根の節はそれの各子に対するポインタセットを維持
する。ポインタセットは（ＣＰ：ＭＸ）　で構成される
。その（ＣＰ：ＭＸ）　においては、ＣＰは節のそれぞ
れの子を指す子ポインタであり、ＭＸはその子にわたっ
て索引される最大値である。親の節１００の下側に子の
節１１０、１２０、１３０の最初のレベルがある。各節
が親の節を差す親ポインタＰＰをおのおの維持するとい
うことを付加して、子の節は親の節すなわち根の節１０
０と同一に構成される。 図２の樹は親の節１１０、１２０、１３０の全ての子を
示すわけではないから、その樹は不完全である。しかし
、親の節１１０から出る樹の一部である「副樹」が節１
５０と１６０により示されている。節１５０と１６０は
インデックス樹のより低いレベルを表す。樹の葉は構造
１７０と１８０により示されている。各構造は（ｋｅｙ
　ｖａｌｕｅ：ｌｉｓｔ）の形式の組合わされたデータ
セットで構成される。図１に示す例においては、それら
のセットはｅｍｐｎｏ　とＲＩＤ　のリストで構成され
ているものである。各葉は親ポインタＰＰと、順次次の
葉へのポインタも含む。したがって、葉１７０は葉１８
０へのポインタを有し、等々である。デジタルデータ構
造２００がインデックス走査により維持され、フィール
ドＰＡＬ−ＰＡＧＥ、ＣＵＲ−ＰＯＳ　、ＮＥＷ−ＫＥ
Ｙ　を含む。ＮＥＷ−ＫＥＹ　フィールドは、処理フロ
ー１のステップ１００で開始された外側表走査から送ら
れた現在のキー値を含む。構造２００は、処理フロー１
のステートメント１０１において開かれている内側表イ
ンデックスを走査することにより維持される。ＣＵＲ−
ＰＯＳ　フィールドは図２の樹におけるインデックス葉
におけるインデックス走査の現在の位置である。ＰＡＲ
−ＰＡＧＥフィールドは現在の位置の親ページへのＰＰ
ポインタを含む。

【００６０】動作時には、処理フロー４に示されている
走査は、外側表から最近に受けたＮＥＷ−ＫＥＹ　値を
、走査が現在位置させられている葉に含まれているイン
デックス値の範囲と比較する。新しいキーが葉に属する
ものとすると、キー値に取付けられているリストが探さ
れ、一時的バッファに置かれる。走査が現在位置させら
れているページに新しいキーがないとすると、走査は樹
を上昇し、葉の親ポインタに従って親節に達する。親節
においては、親節から離れた副樹中の他の子のいずれか
により表されている範囲にあるかどうかを判定するため
に、新しいキー値が親節の子ポインタフィールドと比較
される。親節の他の子のうちの１つの子の範囲に新しい
キーがあるものとすると、走査は示されている葉まで子
ポインタに従い、ＲＩＤ　リストを検索する。さもない
と、新しいキー値が含まれている副樹を探すまで、走査
は非葉節の親ポインタに従って上昇する。ＲＩＤ　リス
トの累積されたセット２１０を、Ｉ／Ｏ　処理のために
、ここで説明している本発明の全体の実行の適切な点に
、非同期的に送ることができる。

【００６１】処理フロー４ 略号 ｐａｒ−ｐａｇｅ　　−　　ｐｏｉｎｔｅｒ　　ｔｏ　
　ｐａｒｅｎｔ　　ｐａｇｅ ｃｕｒ−ｐｏｓ　　　　−　　ｃｕｒｒｅｎｔ　　ｐｏ
ｓｉｔｉｏｎ　　ｉｎ　　ｉｎｄｅｘｌｅａｆ　　ｐａ
ｇｅｎｅｗ−ｋｅｙ　　　　−　　ｔｈｅ　　ｎｅｘｔ
　　ｋｅｙ　　ｔｏ　　ｂｅ　　ｌｏｏｋｅｄｕｐ Ｉｆ　　　　ｎｅｗ−ｋｅｙが（ｃｕｒ−ｐｏｓ）ペー
ジに属するときＴｈｅｎ　　それを索引 Ｅｌｓｅ　　次のｐａｒ−ｐａｇｅ　　ポインタ（およ
び必要に応じ、再帰的に）により、新しいキーが属する
副樹を特定するために親ページへ移動（ｃｕｒ−ｐｏｓ
）新しいキーが属する副樹の根に達したとき樹を上り始
め、新しいキーが属する葉に達する。

【００６２】以上説明した本発明は、多重処理または多
重タスク処理ＣＰＵ　、主記憶装置、およびたとえば磁
気テープの態様の補助記憶装置のような従来の部品を有
するプログラム式コンピュータの態様で実施することが
好ましい。本発明は、たとえば処理フロー１〜４に示さ
れている本発明の諸機能を含んでいるデータベース管理
プログラム（「データベースマネージャ｝）の目的コー
ド表現を有する磁気テープを介してその装置に埋め込ま
れる。そのプログラムは、ＰＬ−１のようなプログラミ
ング言語で書かれたコンピュータプログラムの態様の高
レベル媒介手段を介して、磁気テープのような磁気記憶
装置へ最初に書き込まれる。

【図面の簡単な説明】

【図１】本発明のハイブリッド結合技術を示す説明図。

【図２】親ポインタにより構成されたインデックス樹を
示す説明図。

【図３】関係データベース管理装置に記憶されている表
を示す説明図。

【図４】ネストされたループ法により２つの表を結合す
る従来の技術を示す説明図。

【図５】分類／マージ法により２つの表を結合する従来
の技術を示す説明図。

【符号の説明】

１０　　表 １２　　表 ３５　　手続き ３８　　処理結果表 ４５　　中間処理結果表 ５０　　結果表

Claims (9)

【特許請求の範囲】
1. 【請求項１】第２の表の結合列上にインデックスを含む
   関係データベース管理装置の第１の表と前記第２の表を
   結合する方法において、 （ａ）第１の表の行をローカル述部と比較する過程と、
   （ｂ）ローカル述部を満す第１の表の行を結合述部によ
   り順次置く過程と、 （ｃ）結合述部を満す結合列部分を有する第２の表の行
   の識別子をインデックスから検索する過程と、（ｄ）過
   程（ｃ）のレコード識別名に一致する行を第２の表から
   検索する過程と、 （ｅ）過程（ｄ）の第１の表の行を過程（ｂ）の第２の
   表の行に組合わせて複合行を発生する過程と、とを備え
   る、関係データベース管理装置の第１の表と第２の表を
   結合する方法。
2. 【請求項２】請求項１記載の方法において、過程（ｅ）
   は、（ｅ１）過程（ｄ）の行をローカル述部と比較する
   過程と、 （ｅ２）過程（ｂ）の第１の表の行を、ローカル述部を
   満す過程（ｄ）の行だけに組合わせる過程と、とを含む
   方法。
3. 【請求項３】請求項１記載の方法において、過程（ｃ）
   は、 （ｃ１）インデックスから検索された識別子をそれのそ
   れぞれの一致する第２の表の行のフィールドに組合わせ
   て、中間行を発生する過程と、 （ｃ２）中間行を識別子によりある順序に置く過程と、
   とを含む方法。
4. 【請求項４】第２の表の結合列上においてインデックス
   を含み、事前取出し機能を提供する関係データベース管
   理装置の第１の表と第２の表を結合する方法において、
   （ａ）第１のローカル述部を満す第１の行を結合列の順
   序に置く過程と、 （ｂ）過程（ａ）の行の結合列値に一致する結合列値を
   有する第２の表の行を選択する過程と、（ｃ）過程（ｂ
   ）において選択された第２の表の行の識別子をインデッ
   クスから得る過程と、 （ｄ）過程（ｃ）で得た識別子をそれのそれぞれの一致
   する第１の表の行の指定された列に組合わせて中間行を
   生ずる過程と、 （ｅ）識別子が順序通りでないとすると、中間行を識別
   子により順次置く過程と、 （ｆ）過程（ｅ）の識別子に一致する第２の表の行を、
   プリフェッチ機能を用いて検索する過程と、（ｇ）第２
   のローカル述部を満す行に対して、検索された第２の表
   の行を、過程（ｄ）のそれらのそれぞれの一致する第１
   の表の列に組合わせる過程と、とを備える、関係データ
   ベース管理装置の第１の表と第２の表を結合する方法。
5. 【請求項５】（ａ）インデックスの樹における各子に子
   の両親に対するポインタを維持する過程と、（ｂ）各樹
   の節の子に対するポインタと、子を介して到達した副樹
   の葉に含まれている最高のキー値とをおのおの含むデー
   タ構造のセットを各樹の節に維持する過程と、 （ｃ）キー値のセットのうちの最低のキー値を含む葉を
   探し、その値を記録する過程と、 （ｄ）キー値のセットの次に高いキー値が葉にならない
   とすると、葉から、次に高いキー値を含んでいる副樹の
   根に対するポインタを含んでいる木の節まで親ポインタ
   に従う過程と、 （ｅ）過程（ｄ）の節から、次に高いキーを含んでいる
   葉まで子ポインタに従い、値を記録する過程と、（ｆ）
   キー値のセット中の全ての値が記録されるまで、過程（
   ｄ）と（ｅ）を再帰的に行う過程と、を備える、キー値
   を含んでいる葉を探すためにインデックス樹の葉を効率
   的に走査する方法。
6. 【請求項６】データベースを維持するデータベースマネ
   ージャを有する計算機システムにおいて、結合述部とロ
   ーカル述部をデータベースマネージャへ供給するために
   データベースマネージャへ接続される質問手段と、結合
   述部を満す第１の表の行をデータベースから選択し、選
   択された行を順序づけるデータベースマネージャ中の第
   １の手段と、結合述部を満すデータベース中の第２の表
   の識別子を得るためにデータベースマネージャ中の第２
   の手段と、識別子に一致する第２の表の識別された行を
   データベースから検索するためのデータベースマネージ
   ャ中の第３の手段と、選択された行を識別された行に組
   合わせて複合行を形成する組合わせ手段と、を備える、
   データベースの表を結合するための改良。
7. 【請求項７】請求項６記載の改良において、識別された
   行をローカル述部と比較するためのデータベースマネー
   ジャ中の第４の手段を更に含み、組合わせ手段は選択さ
   れた行を、ローカル述部を満す識別された行へ結合する
   ためのものである改良。
8. 【請求項８】データベースを維持するためのデータベー
   ス管理手段と、結合述部を満す前記データベース中の第
   １のファイルの選択された行を選択し、かつ前記選択さ
   れた行を順序づける第１の手段と、結合述部を満す前記
   データベース中の第２のファイルの行の識別子を得る第
   ２の手段と、識別子に一致する第２のファイルの識別さ
   れた行をデータベースから検索するＩ／Ｏ　手段と、選
   択された行を識別された行に結合して複合行を形成する
   組合わせ手段と、を備えるコンピュータ記憶装置におけ
   るデータベースマネージャ。
9. 【請求項９】請求項８記載のデータベースマネージャに
   おいて、識別された行をローカル述部と比較する第３の
   手段を更に含み、組合わせ手段は選択された行を、ロー
   カル述部を満す識別された行に結合するためのものであ
   るデータベースマネージャ。