Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
JPH077422B2 - コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム - Google Patents
[go: Go Back, main page]

JPH077422B2 - コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム - Google Patents

コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム

Info

Publication number
JPH077422B2
JPH077422B2 JP4178884A JP17888492A JPH077422B2 JP H077422 B2 JPH077422 B2 JP H077422B2 JP 4178884 A JP4178884 A JP 4178884A JP 17888492 A JP17888492 A JP 17888492A JP H077422 B2 JPH077422 B2 JP H077422B2
Authority
JP
Japan
Prior art keywords
tuple
tuples
join
responsibility
columns
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
Application number
JP4178884A
Other languages
English (en)
Other versions
JPH05197763A (ja
Inventor
ジョセフィーヌ・ミゥ−クング・チェング
チャンドラセカラン・モハン
ミル・ハミド・ピラェシュ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH05197763A publication Critical patent/JPH05197763A/ja
Publication of JPH077422B2 publication Critical patent/JPH077422B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G06F16/24553—Query execution of query operations
    • G06F16/24558—Binary matching operations
    • G06F16/2456—Join operations
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99932—Access augmentation or optimizing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はコンピュータ処理するリ
レーショナル・データベースの情報検索の用に供するコ
ンピュータ・システム及びその遂行方法に関する。
【０００２】
【従来の技術】コンピュータ処理するリレーショナル・
データベースはデータの行(row) 及びコラム(column)か
ら成るテーブルに組織される。本明細書において、行は
以下タプル(tuple) と呼称する。データベースは典型的
に多くのテーブルを有し、各テーブルは典型的に複数の
タプル及び複数のコラムを持つ。テーブルは典型的に磁
気又は光学ディスク駆動機構のようなランダム・アクセ
ス記憶装置(DASD)に記憶される。データは多種多様な方
法によりこの形式のデータベースから検索することがで
きる。
【０００３】例えば、コンピュータ・プログラムは人間
の介入なしにデータベースから情報を抽出することがで
き、又使用者はデータベース・システムに対するフロン
トエンドとして作用する照会システム・プログラムと対
話することができる。“テーブルのアクセス処理”はテ
ーブルから情報を読出す手段に対する技術として使用さ
れる。テーブルは通常DASDに記憶されるから、テーブル
のアクセス処理はテーブルの全部又は一部をDASDからコ
ンピュータ・システムの RAMに転送することを要求す
る。情報が複数のテーブルから要求される場合、テーブ
ルはデータベース・ソフトウェア又はファームウェアに
よって結合又はジョインされるかもしれない。
【０００４】そのようなジョイン又は結合（Join) に基
づく有意義な方法を使用することにより全テーブルに亘
り追加の情報を得ることができるようになる。その簡単
な例として、例えば、従業員情報のテーブルが例えば
“７６”のような従業員の課番号で作表されるが、課番
号“７６”の定義は他のテーブル、例えば各課番号に対
応して課の完全名称が作表してある課テーブルを照会す
る必要がある。
【０００５】この第２のテーブルにおいて、課“７６”
に対する行は、又課の名称“情報システム課”を有する
コラムを含む。従って、これら課の名称を含む全従業員
のリストを有する報告書の作成を希望する使用者は、従
業員テーブルの課番号コラムと課テーブルの課名称コラ
ムとの間のジョイン・リレーション（結合関係）を明確
にして、従業員の課を番号の形式ではなく名称の形式で
印刷できるようにすることを希望するかもしれない。そ
のジョインを指定し、実行する方法は相当な努力を要す
る事項である。すなわち、データベース・テーブルは非
常に大きく、テーブルの処理はコンピュータ資源の点か
ら高価であるため、テーブルをジョインする方法は“効
率が良い”ということが特に重要なことである。
【０００６】カーサという言語はテーブルのタプルに対
しポインタを位置付けする機構のための方式に使用され
る。“テーブルにカーサを開く”ことは選択規準を満足
する（存在する場合）テーブルの第１行にカーサを位置
付けすることを意味する。如何なる時点においても、同
一テーブルで開く多くのカーサがあるかもしれず、その
各々は異なる（又は同一の）タプルに位置付けされるか
もしれない。
【０００７】アウタ（外部）ジョイン(Outer Join)オペ
レーションは主なリレーショナル又は関係(relational)
データベース・システムに導入され、出現している SQL
２規準の一部として既に提案されている（ISO-ANSI作業
用草稿：データベース言語SQL２及び SQL３； X3H2/90/
398； ISO/IEC JTC1/SC21/WG3, 1990年）。しかしなが
ら、この種のオペレーションに対する効率の良い遂行方
法については有意義な研究がなされていなかった。本発
明は適用範囲が広い汎用方法と、ほとんどの共通な事例
に対して作業しうる特殊化した、又は専用化した特殊方
法と称する効率の良い方法とを説明する。これらの方法
における１つの重要な特性は、アウタ・ジョイン・オペ
レーションを支援するため、数々の現存する効率の良い
ジョイン方法を拡張することができるということであ
る。
【０００８】概念的に、上記のSQL SELECTオペレーショ
ンは、FROM（フロム）節で指定されたテーブルのデカル
ト積(cartesian product) を形成して WHERE（ウェア）
節で指定した述部を満足するタプルを選択する。この選
択の結果、入力テーブルのあるタプルは出力に現われな
いかもしれない。すなわち、オペレーションは入力タプ
ルのあるものを失うかもしれない。そこで、アウタ・ジ
ョインと称するSQL SELECTオペレーションの変形が定義
され、それは入力タプルのいずれをも失うことはない
（１．ISO-ANSI作業用草稿：データベース言語 SQL２及
び SQL３，上記；２．シー・データによるリレーショナ
ル(relational)データベース；選択された著作；アディ
ソン−ウェスレイ・パブリッシング・カンパニイ，1986
年を参照）。
【０００９】アウタ・ジョイン・オペレーションの数々
の副類別も定義された。それらはフル・アウタ・ジョイ
ン(full outer join) ，左アウタ・ジョイン(left oute
r join），右アウタ・ジョイン(right outer join)、及
びフル・ナチュラル・アウタ・ジョイン(full natural
outer join）と称する。フル・ナチュラル・アウタ・ジ
ョインを除き、残るジョインは２つのテーブルがFROM節
で指定された場合においてのみ良く定義される。その２
つのテーブルは左テーブル及び右テーブルと呼ばれる。
両テーブル（それぞれ左テーブル及び右テーブル）のタ
プルが保存されている場合、そのオペレーションはフル
（それぞれ左及び右）・アウタ・ジョインと呼ばれる。
【００１０】今、２つのテーブル T1(C11,…,C1n) 及び
T2(C21,…,C2m) を有するものと想定する。フル・ナチ
ュラル・アウタ・ジョインは、ジョインの述部の形式 C
11＝C21＝…∧ C12＝C22 …∧…を有するナチュラル・
ジョインと同等物である。これらのコラムは、値(VALU
E) 関数が独立変数を最初の非空白(non-NULL)に戻す場
合、VALUE(C1h, C2h, …）の形でのみ出力に現われる。
フル・ナチュラル・アウタ・ジョインがそのオペランド
として許可するテーブルの数は幾つでもよい。
【００１１】下記の例においては、ISO-ANSI作業用草
稿：データベース言語 SQL２及び SQL３（上記）で提案
されたものに対して構文終結又はクローズを使用する。 FROM T1 FULL JOIN T2 ON ＜述部＞
【００１２】＜述部＞は SQLステートメントの WHERE節
（副照会述部を含む条件付き表現のアンド(AND),オア(O
R)、及びノット(NOT) の混合）と同一様式を有する。T1
及びT2を含む与えられたアウタ・ジョイン・オペレーシ
ョンに対し、そのオペレーションの前にT1及びT2に対し
て供給される他の述部及びオペレーションの結果に対し
て与えられる述部もあるかもしれない。これら述部の供
給はSQL SELECTオペレーションを使用して行われ、遂行
方法に関する限りアウタ・ジョイン・オペレーションの
一部ではない。後述するよう、本明細書においては、ア
ウタ・ジョイン・オペレーションに対する特殊方法につ
いて説明する。
【００１３】上記の例として、２つのテーブルcs及びls
（今年の販売及び去年の販売）を有するものと想定す
る。これらテーブルの各々は下記のコラムを有する。 pno ／* 製品番号（個有のキー） *／ ptype ／* 製品の型式 *／ sales ／* 販売量 *／ profit ／* 収益金額 *／
【００１４】下記の照会（照会１）の公式化を希望する
ものとする。今年の販売で利益がなく、去年の販売量が
今年の販売量より少いか等しい場合、同一型式の製品に
対する今年の販売情報及び去年の販売情報のすべてを与
える。次に、同一の照会を述べる別の方法によると、今
年の販売情報のすべてを与え、利益がなかった場合、去
年の販売情報のすべてを与えて去年の販売量が今年の販
売量より少いか等しいかをみる。この例は、後に２の方
法の説明の際再び参照する。このため、右(RIGHT) アウ
タ・ジョイン構文の使用を選択する。
【００１５】照会１： SELECT* FROM ls RIGHT JOIN cs ON（ ls.ptype＝cs.ptype AND ls.sa1es≦cs.sales AND cs.profit ≦０)
【００１６】csテーブルのタプルすべては保存されるこ
とに留意する。同様に、lsテーブルのタプルのすべての
保存を希望することができる。そのため、フル・アウタ
・ジョインを指定しなければならない。上記の照会にお
いて、１以上多くの述部は変動を生じさせるよう省略さ
れるかもしれない。これら変動のすべては合理的な意味
を有する。照会１の変形は下記の如くである。
【００１７】照会２： SELECT* FROM ls RIGHT JOIN cs ON （ ls.pno＝cs.pno AND ls.sa1es≦cs.sales AND cs.profit ≦０)
【００１８】この例において、個有なキーの列、 pnoが
ジョイン・コラムとして使用される。前述のように、ア
ウタ・ジョインのON節の＜述部＞は SQLステートメント
の WHERE節（副照会述部を含む条件付き説明の AND, O
R、及びNOT の混合）と同一の形式を有する。後に説明
する本発明による汎用方法はこの汎用性に従ってON節を
処理するが、本発明による特殊方法は更に効率が良く、
簡単に一群の特別な事例を処理することができる。
【００１９】従って、本発明の一部を従来技術と対比し
てみると、 例えば、ON節の述部が等式のみである場
合、本発明による特殊方法を選択した方が良い。その目
的に対し、汎用方法におけるような損失がなく、ON節の
述部に対する形式を規定することができる。次に、本発
明はこの形式に基づき、述部の類別と呼ばれる一組の特
別な事例を同定する。次に、これら類別のどれが本発明
の特殊方法によってより効率的に処理することができる
かを識別する。
【００２０】今、２つのテーブル T1(C11,…,C1n) 及び
T2(C21,…,C2m) を持つものと想定する。これは汎用方
法の場合のような損失はなく、T1はジョインのアウタ又
は外部(outer) であり、T2はジョインのイナー又は内部
(inner) であると仮定する。又、ON節は下記の形式を有
するものと仮定する。
【００２１】
【数１】
【００２２】これら述部のすべてはアウタ・ジョイン・
オペレーションの一部であり、それらはアウタ・ジョイ
ン・オペレーションの前又は後で供給されなければなら
ない述部ではない。アウタ・ジョイン述部は、その述部
の形式が局所の述部のように見えても、イナー及びアウ
タ・テーブルから１対のタプルに供給されなければなら
ない。P2に対するものを除く残りのものはジョイン又は
T1の局所述部である。
【００２３】
【外１】 は＝，＞，≧，＜，≦であってよい。を含む述部は
特別述部と呼ばれる。
【００２４】本発明方法においては、これら特別な方法
の述部を使用する。Ωはブーリン演算子∧又はｖであっ
てよい。 Fs はスカラ関数（詳細には、後に見られるよ
うに、それらはほとんど単一の値に戻らなければならな
い）である。それら関数の評価はアウタ・テーブルのカ
ーサの流れに依存してはならない。例えば、スカラ関数
はイナー・タプルのコラムの任意な説明であることがで
きる。独立変数V1, …,Vh は、定数，ホスト変数、及び
相関コラム規準を含むこのアウタ・ジョイン・オペレー
ションに対して向けられる結合手段であることができ
る。
【００２５】F関数は、又副照会を含むことができる。
又、これら副照会に対する評価はアウタ・テーブルのカ
ーサの流れに依存してはならない。 V1,…,Vh はスカラ
副照会の結果であってよい。スカラ副照会が１より多く
の値に戻ると、これは誤りとなる。スカラ副照会が値無
しに戻ると、それは副照会が空白(NULL)の値に戻るもの
と思われる。後に、これら特別な場合をいかに取扱うか
について説明する。
【００２６】
【外２】
【００２７】P12は両テーブルのコラムを含むいかなる
述部であってもよい。例えば、 （C15)2 ＋ C23＝５ 又は C11＋C21 IN(SELECT…FROM… WHERE…）
【００２８】P1及びP2はT1及びT2の局所述部である。照
会１及び２の利益に対する述部はP2述部の例である。残
余はT1に対する一組のジョイン又は局所述部である。次
に、述部の異なる類別について定義する。
【００２９】
【外３】 ・類別１：特別等式述部の連言肢： ・Ωすべては∧であり、は等式である。
【００３０】下記の２つの条件が保持されると、 P12の
存在は許される。その第１は、C11,…,C1kがテーブルT1
の個有なキーを形成すること。第２は、上のコラムが汎
用数量子副照会(ALL副照会）である Fijのみで、それら
と関連を持たないことである。
【００３１】この場合、個有なキーの一部でないコラム
の特別等式述部は、又 P12の一部であると考えられるこ
とに留意を要する。上記照会２の例は、 pnoがアウタ・
リレーションの個有なキーであるから、この類別に入
る。又、照会１は述部ls.sales≦cs.salesを除去する
と、この類別に入る。これはアウタ・ジョイン述部の最
も共通な形式であり、本発明方法もこの場合に適合す
る。そして、与えられたコラムに対し、複数の特別等式
述部が許されることに留意する。
【００３２】
【外４】
【００３３】・類別３：上記のものはない。 ・この類別は下記の汎用方法において取扱われるので、
これ以上は説明しない。
【００３４】最初、背影情報として、すべての類別又は
範畴のものを処理する汎用方法と呼ばれる簡単な方法を
説明する。この説明を通し、ジョインは対方式で行われ
るものと仮定する。次の説明は順次的汎用方法である。
LOCP1 及び LOCP2はそれぞれテーブルT1及びT2における
非アウタ・ジョインの局所述部であると仮定する。アウ
タ・ジョイン・オペレーションに対する入力は局所述部
の供給後のT1及びT2である。ここで、照会の仕様は、述
部LOCP1 をテーブルT1に供給し、述部LOCP2 をテーブル
T2に供給し、述部OUTJP を使用した結果についてアウタ
・ジョインを行うものであると仮定する。フル・ナチュ
ラル・アウタ・ジョインに対しては２つより多くのテー
ブルを持つことができる。
【００３５】以下の記述で使用される TIDはタプルの識
別子である。それは、典型的に２つの部分“スロット番
号（アレイに対する索引）に連結された頁ID”から成
る。特定頁の底部におけるアレイの特定スロットをアク
セスすることにより、その頁のタプルの実際の位置に対
してポインタを得ることができる。 TIDリストは索引を
アクセスすることによって得られる TIDのリストであ
る。索引の記入項目は下記の形式のものである。 ＜キーの値，TID ＞
【００３６】オペレーションの結果が出力であるという
場合、これは単に後の使用のため、コンピュータのある
型式のメモリー(RAM, DASD, テープ等）にその結果を記
憶するか、又は使用者に表示するかのいずれかであるこ
とを意味する。
【００３７】汎用順次方法 照会を遂行する；その結果を出力する（次段にパイプ結
合されるかもしれない）；この遂行を通して、個別的TI
D を有する１リスト(TID list）を形成するか、又は後
で重複を除去する；
【００３８】各保存テーブルに対し、｛リストを分類し
重複を除去する(TIDが個別のものでない場合）；関連す
る原始テーブルを走査する（例えば、T1）；｛各タプル
に対し｛そのTID が TID listにあり、LOCP1 が真値で
ある場合｛他のテーブルのコラムに対する空白(NULL)の
値と共にタプルを出力する；｝｝｝｝
【００３９】この方法の第２部分は保存を行うことであ
る。この部分はテーブルと分類された TIDリストとの組
合せジョインに非常に類似している。この方法は、更
に、第１段階中にテーブルを走査することができる場
合、最適化することができる。T1の TIDリストにおい
て、述部LOCP1 を満足する TIDすべてを記憶し、それら
に出力の部分であること（すなわち、 JOINPジョイン述
部を満足した）の印を付ける。第２段階を通し、このリ
ストを走査して印が付けられていない TIDを得る必要が
あり、それらに関するタプルを保存する。
【００４０】上述のように、この方法の利点は既に説明
したように、述部の全類別を処理することができること
である。しかし、この方法は下記のような欠点を有す
る。
【００４１】１．１つの主な欠点は、この方法の第２部
分に入力テーブルの再アクセスを付加することである。
これは入力テーブルに対して記憶を要求するということ
に留意するべきである。それ故、入力テーブルをパイプ
ライン方式とすることができない。パイプライン処理は
多くの場合、大変効率が良い方式である。
【００４２】２．第２の欠点は出力が順序付けを保存し
ないということである。テーブルT1及びT2はアウタ・ジ
ョインされ、汎用方法の第１段階において組合せジョイ
ンが行われたものと想定すると、T1の順序は出力におい
て保存されるが、この方法の第２段階において、その出
力に対しより多くのタプルが加えられ、その結果、その
順序付けを失うことになる。
【００４３】後に詳細に説明するように、本発明により
特殊化した方法（特殊方法）はこの欠点を持たず、ほと
んどの場合を処理することができる汎用方法より更に効
率が良い方法である。左アウタ・ジョインはネストされ
たループ，組合せ走査，ハッシュ・ジョイン，ハイブリ
ッド・ジョイン等のような一クラスの現存するジョイン
方法に対する拡張によって容易に処理することができ
る。すべてこれらの方法は一度（ある段階において）ア
ウタ(outer) タプルを走査してイナー(inner) タプルを
見出する。与えられた走査位置において、イナー・タプ
ルがアウタ・タプルに適合しなかった場合、アウタ・タ
プルはイナーのコラムに対する空白(NULL)の値を持つ出
力である。
【００４４】更に、従来技術において、イナー・タプル
を保存することを要求するフル・アウタ・ジョインの処
理はより複雑である。フル・アウタ・ジョインにおい
て、アウタ・タプルの保存は左アウタ・ジョインと同一
方法により行うことができる。イナー・タプルの保存は
より多くの作業を必要とする。右アウタ・ジョインに対
しても同様である。右アウタ・ジョインを左アウタ・ジ
ョインに語義的に変換することはできるが、大変高価に
なるかもしれないので、それを行うことは欲しないかも
しれない。
【００４５】左アウタ・ジョインの照会さえ、コスト削
減のため右アウタ・ジョインとして遂行しなければなら
ないかもしれない。左アウタ・ジョインが好ましい場合
としては、例えば、保存されなければならないテーブル
が良いアクセス路を有し、他のテーブルが大きく、良い
アクセス路を持たないときであり、故に１回のみそれを
走査することを希望する。このテーブルはイナー（内
部）であれば、アウタ（外部）の各タプルに対してそれ
を走査しなければならず、非常に成果が悪くなる。
【００４６】上記のように、フル・アウタ・ジョインは
左アウタ・ジョインと右アウタ・ジョインとの組合せで
ある。本発明は、アウタ・ジョイン・オペレーションの
アウタ・テーブルのタプルを保存するための簡単且つ効
率良い方法を提供する。以下、イナー・テーブルのタプ
ルの保存方法について記述する。
【００４７】“リレーショナル・データベースのアウタ
・ジョイン・オペレーション・システム”ＪＰ５９−１
２５４６１と称する公開された日本特許出願はアウタ・
ジョインに対する基本方法の改良について記述してい
る。この基本方法は４段階でフル・アウタ・ジョインを
実行する。すなわち、１．一時テーブルにイナー・ジョ
インする；２．一時テーブルに左アウタ・ジョインす
る；３．一時テーブルに右アウタ・ジョインする；４．
一時テーブルから検索する。その出願による改良は一時
テーブルの使用を除去することである。本願発明は以下
に記述するように、完全にそれとは異なる。
【００４８】シー・デートの（リレーショナル・データ
ベース；選択された著作，上記）、エー・パイロットの
（リレーショナル・モデルの正規な定義，ACM SIGMOD R
ecord,１３（１），１９８２年）、及びISO-ANSI草稿に
おける (ISO-ANSI作業用草稿：データベース言語 SQL２
及び SQL３，上記）はアウタ・ジョインに対する構文及
び語義を定義する。エー・ロセンタル及びディー・レイ
ナー（アウタ・ジョイン処理に対する照会処理の代数骨
格の拡張，超大規模データベースの第１０回国際会議議
事録，シンガポール，１９８４年８月）はアウタ・ジョ
インに対する遂行の問題について発言している。これら
論文は左テーブルを保存する必要がある場合を取扱い、
それは先に説明した簡単な拡張と同一である。
【００４９】
【発明が解決しようとする課題】以上説明した従来技術
における汎用方法は処理効率が悪く、更に、出力に順序
付けを保存しないので非常に成果が悪くなるという欠点
を有する。又、上記の論文においても、イナー・テーブ
ルに保存することを許しておらず、この発明の特徴であ
るフル・アウタ・ジョインに対する方法を提供するもの
でもない。この論文は、これらの場合、更に処理の追加
が必要であることに言及しているが、その説明はなされ
ていない。
【００５０】その上、アウタ・ジョインの並列遂行に対
する方法に関する報告はまだ文献に見出すことはできな
い。従って、本発明の目的は、効率良いジョイン方法を
拡張処理することにより、ほとんどの特殊事例に対して
特に効率良くデータベースのジョインを遂行する方法を
提供することである。本発明の他の目的は、アウタ・ジ
ョイン・オペレーションにおけるアウタ・テーブルのタ
プルを保存するため、簡単且つ効率よい方法を提供する
ことである。
【００５１】
【課題を解決するための手段】本発明は下記のように構
成して上記のような従来技術の課題を解決した。すなわ
ち、本発明はすべての場合を効率良く処理するジョイン
の汎用方法を提供すると共に、最少の拡張処理により、
公知の効率良い一クラスのジョイン方法（例えば、ネス
トされたループ，組合せジョイン，ハイブリッド・ジョ
イン、及びハッシュ・ジョイン）に拡張するよう使用す
ることができるジョインの特殊方法を提供して上記の問
題を除去した。すなわち、本発明は、イナー・テーブル
のすべてのタプルがそれぞれ唯一の責任領域に属するよ
う、指定した組のコラムを使用してイナー・テーブルに
複数の責任領域を決定する。アウタ・テーブルのタプル
が順次処理されるとき、各責任領域はその順次中１回の
み処理される。各責任領域の処理は、定義された責任領
域にあるイナー・テーブルのすべてのタプルの出力を含
む。
【００５２】責任領域は、イナー・テーブルの各タプル
は唯一の責任領域に属するというように定義したので、
責任領域の処理は、イナー・テーブルの各タプルが１回
のみ保存されることを保証することになる。次に記述す
るアウタ・ジョインの実行方法は、ジョイン・コラムに
おける索引を介してジョインされ又はアクセスされるコ
ラムに分類されているアウタ・テーブルT1に対する現行
及び次のカーサ位置の機能である責任領域を使用する。
【００５３】本方法はイナー・テーブルT2を分類せずに
作業することにより、顕著な良い効率を達成しうるとい
う利益を得ることができる。各タプルに対してジョイン
されるコラムに対する値は一組のコラム値として引用さ
れる。T1（アウタ・テーブル）の各タプルは処理され、
各個有な組のコラム値はT2（イナー・テーブル）の責任
領域に割当てられる。そこで、T1の各タプルの処理はそ
の責任領域にあるT2の全タプルのジョイン出力の保存を
含む。
【００５４】この好ましい実施例においては、処理の初
期設定段階において、T1の最低のコラムの組の値、すな
わちT1の最初のタプルの値より小さいコラムの組の値を
有するT2のタプルのすべてをジョイン出力に保存する。
他の実施例においては、T1の最初のタプルに対して定義
した領域が初期設定で取扱われる領域を含む。
【００５５】最後のタプル以外のT1のタプルに対する責
任領域は、T1の次のタプルに対するコラムの組の値より
小さく、現行タプルに対するコラムの組の値より大きい
か等しいコラムの組の値を持つタプルとして定義され
る。T1の最後のタプルはT2に未だ保存されなかったT2の
タプルのすべて、すなわち最後のタプルに見出されたコ
ラムの組の値より大きいか等しいすべてのタプルを保存
しなければならない。
【００５６】T1がコラムの組の値に対し重複する値を持
つ場合、重複の最後のタプルのみが非空白(non-NULL)責
任領域を有する。すなわち、最後の１つのみが共同する
T2タプルを保存する。重複タプルの残りのタプルは空白
(NULL)責任領域を有し、如何なるT2タプルをも保存しな
い。これらの領域に対しては、レギュラ・ジョインのみ
を実行する。これはT2タプルの重複保存を防止する。T2
のアクセスは責任領域を定義する述部に基づくため、イ
ナー・テーブルは分類する必要がない。この方法を使用
して、T2の各タプルはジョイン出力に現われる。
【００５７】アウタ・ジョイン方法の並列遂行における
拡張方法はタスクに対しテーブルの区画を割当て、可能
性のある重複を除去するものである。後に、副照会に対
する方法の拡張も説明する。
【００５８】
【実施例】以下、添付図面を参照して本発明の好ましい
実施例を詳細に説明する。図１はイナー・テーブル１６
の１組のタプルに対し、アウタ・テーブル１７のタプル
をマッピングする概念を示す図である。実際の適用業務
においては、イナー・テーブルは図のように分類されて
いないが、この図においては、説明を容易にするため、
イナー・テーブルは分類されたものとして示してある。
アウタ・テーブルは、適当な分類順にアクセスすること
がその要求のすべてであるから、実際に分類する必要は
ない。アウタ・テーブルを正しい順序でアクセス可能に
する索引の使用により、実際にはアウタ・テーブルを分
類する必要性を無用にする。
【００５９】イナー・テーブルのマップされた一組のタ
プルはアウタ・テーブルの対応するタプルに対する責任
領域にあるといわれる。図１では、アウタ・テーブルの
単一コラムの値が使用されるが、同一方法で複数コラム
の値が働くという最も簡単な場合を示す。アウタ・テー
ブルのタプルはコラムの値V11 をイナー・テーブルの責
任領域１３にマップする。責任領域はタプルを含まない
か、又は大きな数を含むことができる。
【００６０】アウタ・テーブルのコラムの値が図１のV
13 に示すように、重複している場合は、最後の重複を
除くすべてに対する責任領域は空白である。方法１１の
初期設定工程は、アウタ・テーブルの適用可能な最低の
コラムの値（すなわち図１のV11 ）より小さい値を有す
るイナー・テーブルに対し全部記録するため、責任領域
１２が割当てられる。
【００６１】値V1n で示すアウタ・テーブルの最後のタ
プルは、その適用可能なコラムの値（すなわち、V1n ）
より大きいか又は等しい値を有するイナー・テーブルの
全タプルを含む責任領域１５が割当てられる。各責任領
域は前の領域が終了した場所から開始し、次のものが開
始する場所に延びる。それによってすべてのイナー・テ
ーブルを取扱範囲とし、イナー・テーブルの全タプルが
唯一の責任領域のみに所属することを保証する。
【００６２】図２は責任領域を構成するタプルは実際に
は、連続的に配置されないということを示す。かくし
て、初期化する責任領域はタプル２２及び２４から成
る。値V11 を有するタプルはタプル２１及び２５にマッ
プし、V12 は２３にマップし、V1n は２６にマップす
る。イナー・テーブルのすべてのタプルはアウタ・テー
ブルのタプルに対してマップされなければならないが、
図２においては、図を簡単にするため、他のマッピング
は省略してある。イナー・テーブルに対するマッピング
はタプルの適当なコラムの内容によって行われるが、イ
ナー・テーブルの実際の位置は重要ではない。
【００６３】類別１に対する方法 T1はC11,…,C1k（最高位から最低位順に）に順序付けさ
れるものと仮定する。この順序付けは上昇順序であると
仮定する。この順序が如何なるコラムにおいても下降順
序であると、それらコラムの値の補数が発生するかもし
れない（例えば、０１は１０となる）ので、それらを上
昇順序で見ることにする。イナー・テーブルは如何なる
順序でもアクセスすることができ、これは最適化手段に
よって決定してもよい。
【００６４】故に、この方法はネストされたループ，組
合せ走査，ハイブリッド・ジョイン、及びハッシュ・ジ
ョイン（後に説明する）のような方法をジョインするた
めの拡張方法(extension) として使用する。この方法は
ジョイン・コラムpno がアウタの個有なキーであるか
ら、上例の照会２の処理に対応し、故に P12が許され
る。不等式ジョイン述部は P12の一部であると想定さ
れ、s1はアウタ・テーブル(T 1)の走査の名称であり、s
1j はアウタ・テーブルのタプルｊの走査位置であると
仮定する。
【００６５】この方法の説明のため、変数ｘを定義す
る。この変数はT1の各タプルに対する１つの値を持つか
もしれない。この値は、C11,…,C1kの値を連結する関数
X を使用して計算される。又、この変数は、関数 F
1j（…) を使用してC11,…,C1kに対するT2のタプルのコ
ラムを最初マッピングし、次にそれらを連結することに
よって計算されるT2の各タプルに対する１つの値を有す
る。T1の与えられたコラムに対する複数の F1j（…) が
ある場合（すなわち、T1の与えられたコラムに対する複
数の等式の述部がある）、それらの１つを特別述部の一
部として選択する。
【００６６】この方法の並列版において、その FijがT2
の異なるタプルに対して大層異なるものと思われる値に
戻る場合、等式の述部を選択することを希望するであろ
う。これは異なる責任領域（後に定義する）に対して割
当てられるタプルの数の配分をより良く行うことができ
る。並列の場合、各責任領域は１つのタスクによって処
理される。従って、タスク間保存と関連するロードのよ
り良い平衡を得ることができる。
【００６７】T1はC11,…,C1kの順に順序付けされるの
で、一次元空間で順序付けされたT1タプルのｘ値すべて
を持つことができる。この一次元空間を“責任領域”と
称する領域に分割する。責任領域ｊは、カーサ位置ｓj
に対応するｘの値≧とカーサ位置ｓj+1 に対応するｘの
値＜とのすべての値を含む。ｘ値がこれら２つのカーサ
位置に対して同一の場合、責任領域は空白(NULL)であ
り、如何なるタプルも保存しない。基本的に、この方法
において、カーサ位置ｓj はその責任領域にマップする
T2のタプル全部を保存する責任がある。
【００６８】この方法は保持するために下記の条件を必
要とする。 （１）各イナー・タプルに対し正確に１つの責任領域が
ある。 （２）イナー・タプルがその責任領域と共同するアウタ
・タプルに適合しない場合、それはアウタの如何なるタ
プルとも適合しない。これは、イナー・タプルを保存す
るべきか、又はその責任領域のアウタ・タプルが与えら
れないか否かの決定を可能にする。イナー・タプルが適
合を有するか（保存されてはならない）、それが全く適
合を持たないか、又はそれが保存されるかどうか等につ
いて記憶する必要はない。これは、より簡単且つ効率良
い方法を導くものである。
【００６９】空白(NULL)の値は関数 Fijのいずれかによ
って戻されるかもしれない。空白の値は、それらが他の
値と同様に取扱われるので、特別な取扱いは要求されな
い。関数 Fijが汎用副照会であると（すべての場合）、
それは値無し(no value)に戻ることが可能である。責任
領域の割当に対し値無しを空白に変換することができる
（明らかに、まだ普通同様、述部の評価を行う。すなわ
ち、空き汎用副照会述部は真値(TRUE)に戻る）。
【００７０】特殊方法１ − 順次版 ／* 下記において、ｓはT1のカーサである *／ T1のｓを開く； ｊ＝０； ｓj ＝タプルなし； while(eof(ｓj ) ではない） ｛ｓj+1 ＝ fetch next；／* ファイルの終了であれば
＝ eof *／ ／* X(ｓo ) ＝−∞及びX(ｓeof ) ＝∞と仮定する *／ if (X(ｓj ）＝X(ｓj+1 )) ｛領域＝’＝X(ｓj ）’；／* 空白領域 *／｝ else ｛領域＝’≧X(ｓj ）∧＜X(ｓj+1 ) ’; ｝ T2のタプルのｘが領域にある場合、T2をアクセスする；
【００７１】戻された各タプルに対し ｛if（空白領域) ｛レギュラ・ジョインと同一ジョイン
を行う；｝ else ｛ジョイン述部を供給する；if（適合した）｛結果を出
力する；｝ else／* タプルを保存する *／ ｛T1に対する空白の値と共にT2のタプルを出力する；｝ ｝｝ j＝ｊ＋１；｝
【００７２】各責任領域は現行及び次のカーサ位置の関
数であることがわかる。アウタがコラムC11,…,C1kに対
する重複する値を持つ場合、重複する最後のタプルのみ
が非空白(non-NULL)責任領域を持つ。すなわち、最後の
１つのみが共同するイナー・タプルを保存する。残りの
タプルは空白(NULL)の責任領域を形成し、如何なるイナ
ー・タプルも保存しない。すなわち、これらの領域に対
しては、ジェネラル・ジョインのみが行われる。これは
イナー・タプルの重複保存を防止することである。イナ
ーのアクセスは責任領域を定義する述部に基づく。これ
はON部で指定されたものより弱い述部であることに留意
する。
【００７３】図３はこの方法の簡単な適用業務を示す。
表Ａは製品数のコラムで分類又は類別されたアウタ・テ
ーブルを示し、表Ｂは分類されないイナー・テーブルを
示す。アウタ・テーブルには５つのタプルがあるので、
ｊは０から５までとなる。各テーブルは製品数のコラム
を有する。ｊ＝０において、初期の責任領域は“≧−∞
及び＜１０”に設定される。マイナス無限大の語はデー
タベースに現れることができる最小数より小さい数を意
味することに使用される。かくして、等価の式はすべて
１０より小さい値である。値１０は製品数１０を有する
ワイヤに対するアウタ・テーブルのタプルであるｊ＝１
を走査することによって発見することができる。
【００７４】保存工程において、イナー・テーブルのタ
プル６は、その製品数の値が１０より小さい２であるか
ら、この最初の責任領域によって保存される。ループを
通る次の通路はｊ＝１に対するものである。この方法
は、ｊ＝１及びｊ＝２におけるアウタ・タプルは同一の
製品数のコラム値を持つ（すなわち、１０）ということ
を確認する。故に、空白の責任領域は、中継タプルが１
０に等しい製品数を持つので、中継タプルであるイナー
・テーブルのタプル２とワイヤ・タプルとのジョイン
（結合）を出力するものと定義される。
【００７５】ｊ＝２における磁石タプルは責任領域“≧
１０及び＜３０”が割当てられる。故に、それは製品数
１０を有するからイナー・テーブルのタプル２が保存さ
れる。ｊ＝３及び４の処理は簡単である。ｊ＝５に対す
る走査において、テーブルの終端が発見され、刃タプル
は、それ故、以前保存されなかったタプルすべてを保存
しなければならないことを知らされる。かくして、最終
の責任領域は製品数５０５，２０５、及び９００を有す
るタプル１，５、及び７を保存する“≧２０５及び＜
∞”に設定される。イナー・テーブルの各タプルは唯一
の責任領域が与えられた。
【００７６】次に、この方法の正確性の立証の概要を説
明する。それには、（１）イナー・タプルが１つの責任
領域のみを有すること、（２）その領域のアウタ・タプ
ルに適合がなかった場合、如何なるアウタ・タプルとも
適合がないことを示さなければならない。 X関数が一次
元空白間の正確な１つの点にT2のタプルをマップし、責
任領域がこの空白間に重複せず、又それらは全空白間を
カバーするが故に、第１の条件は保持される。先に述べ
たように、コラムに複数の特別等式述部、すなわち複数
の関数 Fij（…）を持つ場合、責任領域確認のため、こ
れら関数の１つのみを選択する。
【００７７】そのための理由は、T2の与えられたタプル
を正確に１つの責任領域にマップすることである。第２
の条件を保有することを示すため、C11,…,C1kはテーブ
ルT1の個有なキーを形成するものと仮定する。故に、ア
ウタ・タプルのｘの値はすべて個別なものである。従っ
て、空白(NULL)の責任領域はない（アウタに重複がな
い）。適合するべきT2のタプルに対し、そのｘの値はア
ウタ・タプルのｘの値と適合しなければならない。しか
し、他の責任領域のｘの値すべてはこの責任領域のｘの
値より小さいか又は大きい値を有する。
【００７８】故に、T2のタプルは他の責任領域の如何な
るタプルとも適合することができず、上記の条件を満足
する。これは、タプルがその責任領域に適合してさえ真
実であることに留意する。次に、C11,…,C1kは個有のキ
ーを形成しないものと想定する。T2のタプルがその責任
領域に適合しない場合、それは、そのｘ値がこの責任領
域のアウタ・タプルのｘ値に等しくないか、又はP2がフ
ォールス(false）であったことを意味する。この場合、
形式 P12の述部は許されないことに留意する。
【００７９】ｘ値が適合しない場合、それらはこの責任
領域より小さいか又は大きいｘ値を有するため、他の如
何なる領域においても適合することはない。ｘは適合す
るが、P2がフォールスであった場合、それはT1のコラム
の関数ではないので、P2はすべての領域でフォールスで
あるから、この述部は適合しない。故に、第２の条件も
保持される。T1が空き(empty）の場合、T2のタプルすべ
ては保存されなければならない。この方法において、T1
が空きであれば、領域＝“＜∞”である。故に、アクセ
ス(ACCESS)はT2のタプルすべてを検索し、タプルのどれ
も適合しないため、それらのすべては保存される。
【００８０】アウタ・ジョインは、又この場合における
ハッシュ・ジョインについても使用することができる。
本発明によるアウタ・ジョイン方法はハッシュ・バケッ
トにおいて使用することができる。すなわち、アウタの
ハッシュ・バケットを形成した後、ジョイン・コラムの
タプルを分類し、この方法に従ってバケット・ジョイン
を行う。最初、与えられたイナー・タプルに対して１つ
の責任領域のみがあることを見定める。これは、イナー
・タプルは単に１バケットの一部であるためであり、そ
れ故、１バケット・ジョインにおいてのみ関与する。そ
して、バケット内において、上記の方法は各イナー・タ
プルに対する１責任領域を保証する。又、イナー・タプ
ルがその責任領域のアウタ・タプルに適合しない場合、
それはどこでも適合しない。これは上記方法によるハッ
シュ・バケットにおいて保証される。イナー・タプルは
如何なる他のハッシュ・バケットとも適合しないので、
他の如何なるタプルとも適合しない。
【００８１】アクセス(ACCESS)はACCESS述部の一部のみ
を使用することができる。レギュラ・ジョインにおい
て、残りの述部は残余として使用されなければならな
い。イナー・タプルの保存を処理するこの方法において
は、適合したタプルを見出するために残余の述部を使用
することが必要である。ACCESSはACCESS述部の一部のみ
を使用するので、この責任領域の一部でないかもしれな
いタプルを戻す。故に、残余の責任領域の述部を使用し
て保存に必要なものを識別しなければならない。適合及
び保存を行うこの方法の一部は下記のように変更しなけ
ればならない。
【００８２】｛if（空白領域) ｛レギュラ・ジョインと
同一ジョインを行う；｝ else ｛適合せず＝FALSE;残余述部を使用；if（適合した） ｛非残余述部を使用する if（適合した）｛結果を出力する；｝ else｛適合せず＝TRUE；｝
【００８３】｝ else｛適合せず＝TRUE；｝ if（適合せず＝TRUE） ｛if（T2のタプルのｘが領域にある） ｛／* タプルを保存する *／ T1に対する空白の値と共にT2タプルを出力す
る；｝｝｝｝
【００８４】この方法において、C11,…,C1kに対する重
複値を有するタプルがある場合、T2の前のACCESSの結果
がキャッシュ記憶され、最後の１つを除き、T1の次の重
複タプルの処理において再び使用される。最後の１つは
適合するタプル及び保存されるタプルの両タプルをアク
セスしなければならない。キャッシング方式もレギュラ
組合せジョインに対して使用可能であり、又アウタが分
類される場合、ネストされたループでさえ使用可能であ
る。
【００８５】前述のように、この類別において、C11,
…,C1kが個有のキーを形成しない場合、形式 P12の述部
は許されない。次に、その理由を明らかにする例を述べ
る。照会１に対する下記の変動があるものと想定する。
【００８６】照会３： SELECT* FROM ls RIGHT JOIN sc ON ( ls.ptype＝cs.ptype ANDls.profit ／ls.sal
se＜cs.profit ／cs.sales)
【００８７】最初の述部はキー・コラムにはなく、第２
の述部は形式P12 のものである。次に、下記のデータに
ついて考察する。lsテーブルはこの方法が要求するよう
に、コラム製品型式(ptype) に従って順序付けされなけ
ればならない。csテーブルは如何なる順序をも持つ必要
はないが、見易くするため、lsテーブルのそれと同一順
序を持つように示してある。
【００８８】 去年の販売 （lsテーブル） タプル番号 pno 製品型式 販売 利益 １ １ １ ＄１００ ＄１０ ２ ７ ２ ＄５０ ＄７ ３ ８ ２ ＄１５０ ＄４０ ４ ３ ２ ＄２００ ＄６０ ５ ２ ２ ＄３００ ＄２５ ６ １０ ２ ＄４００ ＄７０ ７ １５ ３ ＄２５０ ＄７５
【００８９】 今年の販売 （csテーブル） タプル番号 pno 製品型式 販売 利益 １ １ １ ＄１００ ＄１０ ２ １１ ２ ＄５０ ＄７ ３ ９ ２ ＄１５０ ＄２０ ４ ３ ２ ＄２００ ＄３０ ５ ２ ２ ＄２００ ＄２５ ６ １０ ２ ＄４００ ＄６０ ７ １５ ３ ＄４００ ＄１００
【００９０】csのタプル５はlsのタプル４に適合し、ls
のタプル６には適合しない。lsのタプル６は、csのタプ
ル５が所属する責任領域を形成する。その結果、csのタ
プル５はその責任領域においては適合がないので、それ
は保存されるが、他に適合を持つため誤りである。換言
すると、このタプルはその責任領域のアウタ・タプルに
合致しないが、他の場所において適合を有するというこ
とである。その結果、この特殊方法の第２の条件は維持
しない。
【００９１】特殊方法１においては、ACCESSの後、ON節
の述部を使用する。その結果、ACCESSで使用されるON節
の一部が２回使用される。すなわち、その理由は、ACCE
SSが適合するタプルと保存されなければならない両タプ
ルをアクセスし、後にそれらを分離しなければならない
からである。これは明らかに、空白(NULL)責任領域に対
しては無効とすることができる。この高度な方法は、以
下記述する特殊方法２で処理され、それは適合するタプ
ルと保存するタプルの両処理を分離する。イナーに対し
て２つの異なるアクセスを使用する。それらは、適合す
るタプルをアクセスするべきものと、保存するタプルを
アクセスするべきものである。この特殊方法２はイナー
の１走査を要求する（故に１ACCESS）組合せジョインの
ような方法に対しては使用されない。
【００９２】特殊方法２ − 順次版 ｊ＝０； ／* 下記において、ｓはT1のカーサである *／ T1にｓを開く； ｓo ＝タプルなし； while(eof(ｓj ) ではない） ｛ｓj+1 ＝ fetch next；／* ファイルの終端であれば
＝ eof *／ ／* X(ｓo ) ＝−∞及びX(ｓeof ) ＝∞と仮定する *／ if (X(ｓj ）＝X(ｓj+1 )) ｛領域＝NULL；／* NULL領域 *／｝
【００９３】else ｛領域＝’≧X(ｓj ）∧＜X(ｓj+1 ）; ｝ ／* 適合するタプルを得る *／ ACCESS T2 where ＜ON節＞；戻された各タプルに対し
｛結果を出力する；｝ if（領域≠NULL) ｛／* 保存の必要があるタプルを得る *／
【００９４】ACCESS T2 where T2のタプルのｘが戻された各タプルに対し 領域∧NOT ＜ON節＞にある場合 ｛T1に対するNULLの値と共にT2タプルを出力する；｝｝ ｊ＝ｊ＋１；｝
【００９５】特殊方法１と類似するように、C11,…,C1k
に対し重複する値を有するタプルがある場合、適合した
タプルはキャッシュ記憶することができ、T1の次の重複
タプルの処理において再び使用される。明らかに、カー
サがこれら重複の最後の１つにある場合、保存の必要な
タプルのためにイナーをアクセスしなければならない。
【００９６】類別２に対する方法 以下、数個の場合について考察する。 １．すべての不等式はT1の順序付けの最下位のもの（す
なわち C1k）があるT1のコラムに関連する。多くの不等
式はこのコラムに対して指定されるかもしれないことに
留意する。例えば、 C1k＞ Fk1（…) ∧ C1k≦ Fk2（…))． 前述の照会１はこの類別に入る。
【００９７】・責任領域の割当ては等式の場合とわずか
に異なる。T2のタプルはｘの値の（たぶん空きの）範囲
“range ”にマップされる。この範囲の下及び上境界を
それぞれｌ及びｕと呼ぶことにする。ｕの値は等式の場
合において説明した方法と同じ方法を使用して責任領域
を決定する。（又、責任領域を決定するためにｌの値も
使用する。）形式＜，≦の特別不等式がない場合、ｕは
∞である。ｕを決定するため、指定した述部から＜，≦
型式の不等式を選択する。例えば、すべての不等式が形
式leを持つ場合、これら不等式の右手の最小(minimum)
はｕである。T2のタプルを想定し、C1k ≦２００∧C1k
≦１００であると、ｕ の値は１００である。
【００９８】・第１の特殊方法において、タプルを保存
するイナーのアクセスを下記のものに代えなければなら
ない。 ACCESS T2 ここで、T2のタプルの＜ON節＞vuはｘをｕに代える領域
にある。
【００９９】第２の特殊方法において、タプルを保存す
るイナーのアクセスを下記のものに代えなければならな
い。 ACCESS T2 ここで、T2のタプルのｕは領域∧NOT ＜ON節＞にある。
【０１００】ｖの第１のオペランドがイナーの適合する
タプルに対してツルー又は真値であり、第２オペランド
は、保存されなければならないタプルに対して真値であ
る。第２オペランドは、又、オペランドが相互に排他的
でないため、適合するタプルに対しても真値であるかも
しれないことに留意する。
【０１０１】不等式が形式＜，≦のもののみである場
合、ｖの第２オペランドは第１独立変数を包含するた
め、第１オペランド及びｖ演算子は省略することができ
る。故に、特殊方法１において変更の必要がない。この
ように簡単にしたことにより、ACCESS述部は単に範囲述
部（オア(OR)を含まない）となるため、T2の索引の使用
を更に良くすることができる。
【０１０２】不等式述部すべてが形式＞，≧のものであ
れば、上記同様な簡素化を達成することができる。この
ため、責任領域決定のため、変数ｌの値を使用しなけれ
ばならない。前述したように、T2のタプルはｘ値の（た
ぶん空きの）範囲にマップし、この範囲の下及び上境界
は変数ｌ及びｕの値である。又、責任領域を決定するた
め、いずれかの値を使用するオプションを有する。
【０１０３】・ジョイン述部が指定されなかった場合、
すなわち、述部が指定されないか、又はP2のみが指定さ
れるかどちらかの場合、形式 C11＜∞の特別不等式述部
を加えて、上記の方法に使用することができる。
【０１０４】・コラム数がいずれかの不等式の場合 汎用方法を使用しなければならない。これに対する理由
は、この場合特殊方法に対する第２の条件を保持しない
からである。照会１に下記のような変動があるものと想
定する：照会４：
【０１０５】SELECT* FROM ls RIGHT JOIN cs ON ( ls.ptype＝cs.ptype AND ls.sales≦cs.sales AND ls.profit ≦cs.profit）
【０１０６】類別１の例において使用されたものと同一
のデータベースを有するものと想定する。この場合、テ
ーブルlsは Pタイプ(Ptype) ，販売(sales) 、及び利益
（profit）に分類されなければならない。csのタプル５
がlsのタプル１に適合し、lsのタプル３に適合しない。
lsのタプル３は、csのタプル５が所属する責任領域を形
成する。従って、特殊方法の第２条件は保持されない。
【０１０７】順序付け ネストされたループ，組合せ走査のような（ハッシュ・
ジョインはない）あるジョイン方法は出力における入力
テーブルのあるものの順序付けを保存する。例えば、ネ
ストされたループはアウタ・テーブルの順序付けを保存
する。組合せ走査も同様であり、更にアウタ・テーブル
が重複を持たない場合、（アウタ・テーブル内に）イナ
ー・テーブルの順序付けを保存する。前述のように、汎
用方法はこれらの特性を失う。
【０１０８】しかし、特殊方法は、順序付け保存の利益
を持つものである。特殊方法１は拡張として使用される
ジョイン方法の順序付け特性を変更しない。特殊方法２
はアウタの順序付けを保存するのみである。それに対す
る理由は、適合したイナー・タプルと保存したイナー・
タプルとを別々に出力するのでイナーの順序を失うから
である。
【０１０９】〔並列遂行〕並列化は最適化した照会の応
答時間を減少するために使用される主な方式である。高
度の並列化を得るため、入力テーブルは区画され、多く
のタスクは並列に遂行される。各タスクは照会部分を遂
行するため、１以上の区画と共同する。各タスクは作業
の一部を実行するので、それに比例した短い時間でその
作業を完了する。
【０１１０】ロードは平衡し、タスクを実行するために
使用可能な資源が十分存在するものと仮定すると、全ジ
ョインは順次遂行時間の小数部で完了する。作業にスキ
ューの分配があると、１以上のタスクが隘路となるかも
しれず、そのため完了まで長時間かかるかもしれない。
その結果、応答時間の短縮は理想的な場合より少くなる
かもしれない。故に、遂行方法はロードを平衡にしうる
よう柔軟性がなければならない。
【０１１１】最初、特殊方法の並列版を提供し、それに
基づき、汎用方法の並列版を提供する。
【０１１２】アウタ・ジョインの並列遂行において、同
じタプルが１つのタスク（他ではない）において適合を
有することが可能である。故に、他のタスクはそのタプ
ルを保存してはならない。又、適合しなかったタプルは
異なるタスクによって数回保存されてはならない。より
素朴な取り組みとしては、タプルが適合するものを持つ
か、又は全く持たないか、及びその場合、タスクがタプ
ルの保存を選択するということ等の事実を伝達するた
め、タスクに相互通信を要求すればよい。しかし、本発
明により異なるタスク間通信を要求しない特殊方法の拡
張が提供される。
【０１１３】これは、より簡単且つより効率のよい方法
を提供するものである。この方法の背景にある思想は順
次の場合に使用されるものと同一である。順次の場合、
タプルの適合特性及び保存特性に関する如何なる情報を
も記憶することなく（例えば、汎用方法のスタイルで T
IDのリストを）イナーのタプルを保存することを希望す
る。情報を記憶するということの同等物は並列の場合に
おける多重タスク通信と解釈される。故に、順次方法の
同一思想を使用してタスク間通信を回避することができ
る。並列特殊方法を下記に示す。
【０１１４】１．区画１．T1はC11,…,C1k｝順に並べら
れることに留意する。これらのコラムに対し、数個の隣
接区画が重複値を持つかもしれない。 ２．タスクにT1の区画を割当てる。 ３．タスクを並列に実行する。
【０１１５】４．各タスクはその区画と共同するカーサ
位置に対する特殊方法を遂行する。（この方法はT2の区
画分けについていかなる想定をも行わない。故に、オプ
ティマイザはT2タプルをフェッチするための如何なるア
クセス通路を選択することも自由である。例えば、オペ
レーションがフル・ナチュラル・アウタ・ジョインの場
合、T1及びT2はジョイン・コラムのキー範囲に区分さ
れ、T1の区画と共同する各タスクは対応するT2タスクを
アクセスする必要があるのみである。これは、対応する
T1及びT2区画が並列機構の同一ノードにある場合、最適
化される。）
【０１１６】この方法の作業を行うキーとなるものは、
責任領域が定義される方法である。与えられたT1のタプ
ルに対し、その責任領域はそのタプルの値と、次のタプ
ルのコラムの値（次のタプルが次の区画に所属していて
さえ）とに依存する。すなわち、責任領域は全く順次の
場合と同一方法で定義され、区画とは無関係である。与
えられたアウタのタプルは一つのタスクによって処理さ
れる。故に、アウタ・タプルの保存は正に順次の場合と
同様に行われる。
【０１１７】特殊方法は責任領域を決定するため、アウ
タの走査の一部として先に１タプルを読出す。故に、カ
ーサが区画の終端に達したとき、次の区画の最初のタプ
ルを読出す必要がある。代替方法としては、タスク開始
時に各タスクに対してのタプルを与えることである。最
終区画はその次の区画の最初のタプルとして eofを得
る。
【０１１８】並列化の程度はT1の区画の数と同一である
（ロードの平衡を想定する）。並列化の度合は分離した
タスクの一部として、イナーのACCESSの並列遂行によっ
て増加することができる。これにより、並列化の程度は
アウタ・タスクの数とイナー・タスクの数の積まで上昇
することができる。通常、そのような高度の並列化は必
要がない。
【０１１９】ハッシュ・ジョインに対する異なるハッシ
ュ・バケットは並列にジョインすることができる。各バ
ケットのジョインも上記方法を使用して並列に行うこと
ができる。これはジョイン・コラムがアウタ及びイナー
によく現れる値であれば、非常に有益となることができ
る。これらの場合、ハッシュ・バケットは非常に大規模
となり、許容できる応答時間に短縮するため並列に遂行
しなければならない。
【０１２０】アウタ・テーブルは、又タスク当り１区画
となるよう区分される。この方法はその順次の場合と同
一順序の保存特性を有する。明らかに、各タスクは同一
順序の保存特性を有するので、出力テーブルの各区画は
順次の場合と同一順序を有する。T1のコラムは最高位を
形成し、イナーのコラムは（適用可能な場合は常に）最
下位順のコラムを形成する。アウタの区画は順序付けさ
れ、各アウタ区画に対しデータを出力する１タスクがあ
るので出力区画は順次の場合と同一順序を形成する。
【０１２１】スキューなロード配分の処理 前述したように、並列遂行方法はタスク間の不平衡なロ
ードを避けるため、同調しうるよう柔軟性がなければな
らない。この章では、この方法がそれに対して与える柔
軟性について説明する。
【０１２２】タスクは、T1と共同する作業がより多く、
又はT2のアクセスのため、及びジョイン述部の使用のた
め、他より更に多い作業を行わなければならないかもし
れない。T1と共同する作業は、各区画における多数のタ
プルの配分がスキューされているため、又はT1の特別な
区画をアクセスするに必要な余分な作業のため、スキュ
ーされるかもしれない。T2と共同する作業はアウタ・タ
プルに適合するT2タプルの数の配分のスキューのため、
又はカーサがアウタ・タプルに位置付けされるときに保
存されなければならないタプルの数のために、スキュー
されるかもしれない。ジョイン・コラムの値の不均等な
配分はそのようなスキューを引き起こす。次に、数個の
スキューの場合について説明する。
【０１２３】１．スキューなしかわずかなスキューの場
合：タスクがオーバーロードの場合、そのT1区画は縮小
することができる。この方法は区画のサイズが任意に許
されることに留意しよう。アウタの一様な重複タプルを
異なるタスクに割当てることができる。極端の場合、T1
区画に１つのタプルのみがあり、なお、その該当するタ
スクはオーバーロードの場合である。これは“高度スキ
ュー”の場合と呼ばれる。この場合の例はジョイン・コ
ラム値がT2における頻繁な値のときである。
【０１２４】２．高度スキューの場合：この類別に入る
タスクに対し、分離したタスクの一部としてT2のACCESS
を並列に遂行する。故に、T1の区画と共同し、それと共
同するタスクがあり、T2をアクセスし、アウタ・タスク
にデータを戻す多くのタスクがある。残りの作業、すな
わちジョイン述部の使用、その結果の保存及び出力等は
アウタ・タスクによって行わなければならない。T2をア
クセスするタスクの一部としてジョイン述部及び保存の
評価も行うことができる。この作業量はタスクをオーバ
ーロードするとは思われない。これが発生した場合、こ
れは超高度スキューの場合と呼ばれる。
【０１２５】３．超高度スキュー(VHS) の場合：この場
合を処理するため、次のようにこの方法を変更する。T1
の各 VHS区画に対し、T2を区分し、各区画に対して１タ
スクを割当てる。各タスクは個々にアウタ・ジョインを
行う。T1の各タプルは複数のタスクによって処理され、
その結果複数回保存されるかもしれない。
【０１２６】各T2のタプルは１タスクによって保存する
ことができるのみであるから上記のような問題は発生し
ない。T1のタプルの複数保存の問題を取扱うために２つ
の方法がある。１つはそのように保存されたアウタ・タ
プルをマークすることであり、又、それらの TIDを出力
タプルと共に保持することである。最後に、 VHSタスク
の出力を分類し（それ自体並列に行うことができる）、
保存されたタプルの重複を除却することである。
【０１２７】この方法は余分な分類に対するオーバーヘ
ッドを有する(VHSタスクの出力に対してのみ）。これは
照会処理の次段に対する全出力のパイプライン処理が許
されないという副作用がある。第２の解決方法は VHSタ
スクによって保存されたT1のタプルを分離した場所に出
力することである。このリストを分類し、重複を除去し
て、それらを使用者に出力する。この解決方法は VHSタ
スクの全出力に対する余分な分類を回避する。しかし、
解決方法１の順序保存特性を失う。
【０１２８】本発明による並列方法は、又レギュラ・ジ
ョインに対しても使用することができる。そのため、た
だ、タプルの保存と共同するロジックを除去する必要が
ある。又、T1の順序付けアクセスは必要がない。これ
は、例えば、組合せ走査が順序付けアクセスを要求する
というように、使用するジョイン方法によって異なる。
【０１２９】汎用方法の並列遂行は直線的である。第１
の部分はレギュラ・ジョインの並列遂行である。第２の
部分は、又組合せジョインのスタイルを使用する。それ
故、組合せ走査の並列版を使用して遂行することができ
る。
【０１３０】副照会の遂行におけるアウタ・ジョインの
適用：アウタ・ジョイン方法の変動は SQLにおける副照
会（存在的且つ普遍的(ALL))の遂行の成果を増加する。
本章においては、アウタ・ジョインの２つの方法、すな
わちERJOIN及びARJOINについて説明する。 SQL副照会の
遂行のため、如何にこれらの演算子を使用することがで
きるかについて示す。前述のアウタ・ジョイン方法を変
更してこれら演算子の遂行を行う。
【０１３１】以下の説明に対し、 SQLの副照会の構文を
普遍化する。これはスターバースト(Starburst)SQLに使
用される構文である（エル・ハースほかによる“Starbu
rstMid-Flight：ダスト・クリヤとして(IEEE Transacti
ons on Knowledge and DataEngineering）１４３−１６
０頁，１９９０年３月）。この構文の変動はANSI/ISO標
準 SQLの一部として考えられる。この形式は SQLのすべ
ての形式の存在的／普遍的副照会を包含する。
【０１３２】EXISTS (＜テーブル＞，＜述部＞） この解釈は、IN及びANY に対して許された＝，＞、等の
ような単なる演算子の代りに、＜述部＞（＜predicate
＞）がいかなる汎用述部でもよいことを除き、標準SQL
のIN及びANY 副照会に対するものと全く同一である。従
って、＜述部＞（＜predicate ＞）がTRUE（真値）の場
合、＜テーブル＞（＜table ＞）に１タプルが存在する
と、結果はTRUEである。＜テーブル＞の全タプルに対し
＜述部＞が FALSE（フォールス）であれば、結果はフォ
ールスである。その他の場合、結果は UNKNOWN（未知）
である。同様に、以下、 ALL副照会の汎用形式について
説明する。
【０１３３】ALL(＜テーブル＞，＜述部＞）：これは、
＜述部＞が汎用化される(EXISTに対するように）ことを
除き、SQL ALL と同一の意味を有する。この後者は汎用
数量子のために使用する。
【０１３４】ERJOIN方式 ２つのテーブルT1及びT2があるものと想定する。この２
つの間に存在する述部は次のように書くことができる。
【０１３５】SELECT T2.* FROM T1 ERJOIN T2 ON (Q) このERJOINは存在的右ジョインを表わす。述部Q を満足
するようなT1タプルが存在する場合、T2タプルを出力す
る。このERJOINは、T1の複数タプルがこのT2のタプルに
適合する場合、T1及びT2間のレギュラ・ジョインが出力
におけるT2タプルの複数の重複を作成するかもしれない
というようなレギュラ・ジョインとは異なる。レギュラ
・ジョインと同様に、アウタ・テーブル及びイナー・テ
ーブルとしてのT1によりERJOINを遂行することができる
ような最適化が重要である。アウタ・ジョインに似てい
る、アウタとしてのT2によるERJOINの遂行は普通のもの
である。
【０１３６】T2の各タプルに対し、適合するT1があれ
ば、T2のタプルを出力する（１回）。適合するタプルが
発見されると直ちにT1の走査を停止する。アウタ・ジョ
インに似ているように、困難性はT2がイナー・テーブル
のときにある。いかにしても、T1の複数タプルに適合す
るT2のタプルの重複コピーの作成は避けなければならな
い。類似する問題（及び解決）はアウタ・ジョインの実
行に対しても存在する。
【０１３７】今、右アウタ・ジョインを行っているもの
と想定する。 SELECT T1.* , T2.* FROM T1 RIGHT JOIN T2 ON(Q)
【０１３８】ここで、T1及びT2の適合するタプルを出力
しなければならない。又、如何なるT1タプルにも適合し
ないT2のタプルはT1コラムに対し空白(NULL)値が出力さ
れる（これはT2の保存する不適合タプルと呼ばれる）。
その上、T1の各不適合タプルは１回のみ保存されなけれ
ばならない。この後の要求は、何回T1タプルと適合する
かに関係なく、１回のみT2のタプルを出力するべきであ
る本発明のERJOIN要求と大変類似している。ここでも、
先に説明した責任領域の概念を使用する。この方法にお
いて、T2の各タプルは個有の責任領域が割当てられ、各
責任領域はT1のタプルに対して割当てられる。
【０１３９】T1のそのタプルのみがT2のそのタプルに対
し何か特別なことを行うことができる。アウタ・ジョイ
ンの場合において、この特別なことはタプルを保存する
ことである。ここの場合、ある特別なことというのは、
T2のタプルがT1に適合した場合、T2のタプルを出力する
ことである。故に、T2のタプルは１回出力されるのみで
あることができ、従って重複の作成という問題を避ける
ことができる。ここの場合、アウタ・ジョインに使用さ
れた述部をわずか変更する場合、アウタ・ジョイン方法
の変形を持つ必要があるため、適合するタプルは、ほか
の場所ではなく、責任領域に出力される。アウタ・ジョ
インとのより速い通信のため、ON節の述語を保持してい
る。
【０１４０】最初、効率良い特殊化したアウタ・ジョイ
ン方法（汎用のものではない）を使用するのみであると
いうことを確認する。従って、ERJOINは特殊方法が適任
であるとする場合に使用されるのみであることができ
る。適合する各T2タプルを精確に１つの非空白(non-NUL
L)責任領域に置くことができる。責任領域のT2タプルを
アクセスするのみであり、空白(NULL)の責任領域はスキ
ップする。両特殊方法１及び２において、非空白領域に
おいて条件付きであるようイナーのACCESSを変更し、述
部として＜ON節＞を使用する。
【０１４１】／* ERJOINに対して変更する *／ if（非空白領域） ｛＜ON節＞の場合T2をACCESSする；戻された各タプルに
対し ｛T2タプルを出力する；｝ この方法の保存部分をスキップする；｝ ／* ERJOINに対する変更の終了 *／
【０１４２】ARJOIN方式 ARJOINは全（普遍的）右ジョインを表わす。これは前述
したERJOINに対するものと大変類似している。２つのテ
ーブルT1及びT2を有するものと想定する。
【０１４３】上記の形式の普遍的述部を次に示す。 ALL(T, NOT(Q)) 説明の便宜上、汎用性を失うことなく、NOTQを選択し
た。
【０１４４】これは次のように書くことができる。 SELECT T2.* FROM T1 ARJOIN T2 ON (NOT(Q))
【０１４５】全T1タプルに対し述部Q が満足しない場
合、T2タプルを出力する。その上、アウタとしてT1を選
択することを希望する（T1がイナーの場合に対する解決
は既に説明した）。この問題は、正に、ON節がアウタの
全タプルに対し満足ではないので、イナーのタプルを保
存しないという場合における右アウタ・ジョインの保存
部分に相当する。この特性はA.Rosenthal 及びD.Reiner
の論文（アウタ・ジョインの処理のため照会方法の代数
的構造を拡張する）に見ることができる。
【０１４６】その代り、ARJOINを実行しうるよう、次に
示すように、対応するアウタ・ジョインの公式化を変更
することができる。 SELECT T2.* FROM T1 RIGHT JOIN T2 ON(Q)
【０１４７】レギュラ・ジョインを演算し、T1に適合し
ない（すなわち、全T1に対し、 Qは満足しない）T2タプ
ルを保存する右ジョイン(RIGHT JOIN)とは異なり、ARJO
INはT2に対する保存部分を行うのみである。（実際に、
このアウタ・ジョインに対する拡張はEXCEPTオプション
を伴うアウタ・ジョインと称するＩＢＭのAS／４００照
会言語の一部である。しかし、AS／４００はアウタとし
てT1と共にこれを遂行する如何なる方法をも提供しな
い。 SQLは、NOT EXISTS副照会と表現することができる
ので、実際にはこの拡張を必要としない。遂行の観点か
ら本発明方法を変更する。）この方法で必要とする変更
はERJOINのそれらと類似する。第１に、空白(NULL)責任
領域をスキップしなければならない。第２に、保存する
タプルを処理する必要があるのみである（すなわち、適
合したタプルを無視する）。
【０１４８】・方法２において、単に適合するタプルを
処理し、出力する部分を除去する必要があるのみであ
る。（すなわち、／* 適合するタプルを得る *／の後の
行を除去するべきである。）
【０１４９】・方法１において、適合するイナー・タプ
ルのアクセスを除去しなければならない。すなわち、適
合するタプルをアクセスすることなく、非空白(non-NUL
L)領域において条件付きであるようイナー・アクセス(A
CCESS)を変更するべきである。
【０１５０】特殊方法１ − 順次版 ／* 下記において、ｓはT1のカーサである *／ T1にｓを開く； ｊ＝０； ｓj ＝タプルなし； while(eof(ｓj ) ではない） ｛
【０１５１】ｓj+1 ＝ fetch next；／* ファイルの終
りであれば＝ eof *／ ／* X(ｓo ) ＝−∞及びX(ｓeof ) ＝∞と仮定する *／ if（X(ｓj ）＝X(ｓj+1 )) ｛領域＝’＝X(ｓj ）’；／* NULL領域 *／ else ｛領域＝’≧X(ｓj ）∧＜X(ｓj+1 ) ’; ｝ ／* ARJOINに対し変更する *／
【０１５２】if(non-NULL 領域） ｛ACCESS T2 T2のタプルのｘが領域∧NOT ＜ON節＞にある場合；戻さ
れた各タプルに対し ｛T1に対するNULL値と共にT2タプルを出力する；｝｝ ／* ARJOINに対する変更の終了 *／ ｊ＝ｊ＋１；｝
【０１５３】以上説明した詳細な説明に基づき、本発明
方法は公知の標準プログラミングを使用して実施するこ
とができる。その結果作成されたプログラムはディス
ク，ディスケット，メモリー・カード，ROM 、又は他の
如何なる記憶装置にでも記憶することができる。データ
ベースを遂行するため、そのプログラムはコンピュータ
の RAMにコピーすることができる。以上説明したように
作成したプログラムと、適当な汎用コンピュータ又は専
用コンピュータ・ハードウェアとを組合わせてデータベ
ース機械及びデータベース・システムを作成すること
は、コンピュータ科学の当業者によっては容易なことで
ある。
【０１５４】以上、本発明の好ましい実施例を詳細に説
明したが、本発明の範囲から離れることなく、それを変
化変更しうることは明らかである。
【０１５５】
【発明の効果】以上説明したように、本発明は上記のよ
うに構成して、効率良いジョイン方法を拡張処理する特
殊方法を提供したことにより、ほとんどの特殊事例に対
して特に効率良くデータベースのジョインを遂行する事
ができるため、効率良いロードの平衡なデータベースの
コンピュータによる高速処理が可能となった。
【図面の簡単な説明】
【図１】アウタ・テーブルから、分類されたように見え
るイナー・テーブルに対し責任領域をマッピングする概
念を示す説明図
【図２】アウタ・テーブルから、分類されないため責任
領域が隣接していないイナー・テーブルに対し、責任領
域をマッピングすることを示す説明図
【図３】本発明の実施例に使用するテーブルを示す図
【符号の説明】
１１ 初期設定 １２，１３，１４，１５ 責任領域 １６ イナー・テーブル １７ アウタ・テーブル
フロントページの続き (72)発明者 チャンドラセカラン・モハン アメリカ合衆国95120、カリホルニァ州、 サン・ジョーゼイ、ポーツウッド・ドライ ブ、727番地 (72)発明者 ミル・ハミド・ピラェシュ アメリカ合衆国95120、カリホルニァ州、 サン・ジョーゼイ、クェイル・クリーク・ サークル、1282番地 (56)参考文献 特開 昭59−125461（ＪＰ，Ａ)

Claims (12)

    【特許請求の範囲】
  1. 【請求項１】 複数のコラムを有する複数のタプルから
    成るイナー及びアウタ・テーブルを有し、前記アウタ・
    テーブルは選択された組のコラムについて分類された順
    序に順序付けされ割出されるようにしたコンピュータ化
    データベース・システムにおけるジョインの実行方法で
    あって、（イ）前記イナー・テーブルのすべての各タプ
    ルは唯一の責任領域に属するよう、選択された組のコラ
    ムを使用して前記イナー・テーブルに複数の責任領域を
    決定し、（ロ）前記責任領域に属するイナー・テーブル
    の全タプルを出力することにより各責任領域を処理する
    各工程を含み、 イナー・テーブルの分類を必要とせず、イナー・テーブ
    ルのすべてのタプルをジョイン出力に出力することを特
    徴とするコンピュータ化データベース・システムにおけ
    るジョインの実行方法。
  2. 【請求項２】 前記決定する工程は、更に、選択された
    組のコラムの値が前記アウタ・テーブルの最初のタプル
    に対して選択された組のコラムの値より小さい値を有す
    るイナー・テーブルのすべてのタプルを含む初期責任領
    域を定義する工程を含む請求項１記載のジョインの実行
    方法。
  3. 【請求項３】 前記決定する工程は、更に、選択された
    組のコラムの値が前記アウタ・テーブルの最後のタプル
    に対して選択された組のコラムの値に等しいか大きい値
    を有するイナー・テーブルのすべてのタプルを含む最終
    責任領域を定義する工程を含む請求項１記載のジョイン
    の実行方法。
  4. 【請求項４】 前記決定する工程は、（イ）現行タプル
    及び次のタプルを参照してアウタ・テーブルのタプルを
    通して順序付けし、前記アウタ・テーブルの各個有な組
    のコラムの値に対し、最後のタプルのものを除き、前記
    アウタ・テーブルの現行タプルに対して選択された組の
    コラムの値より大きいか等しく及び前記アウタ・テーブ
    ルの次のタプルに対して指定された組のコラムの値より
    小さい選択された組のコラムの値を有するイナー・テー
    ブルのすべてのタプルに対応する前記イナー・テーブル
    からの一組のタプルを含むよう責任領域を定義し、
    （ロ）前記アウタ・テーブルの最後のタプルに対し、如
    何なる責任領域にも割当てられなかったイナー・テーブ
    ルからのすべてのタプルを含むよう責任領域を定義する
    各工程を含む請求項１記載のジョインの実行方法。
  5. 【請求項５】 前記処理する工程は、（イ）現行タプル
    及び次のタプルを参照してアウタ・テーブルのタプルを
    通して順序付けし、前記アウタ・テーブルの各個有な組
    のコラムの値に対し、最後のタプルのものを除き、前記
    アウタ・テーブルの現行タプルに対して選択された組の
    コラムの値より大きいか等しく及び前記アウタ・テーブ
    ルの次のタプルに対して指定された組のコラムの値より
    小さい選択された組のコラムの値を有するイナー・テー
    ブルのすべてのタプルに対応する一組のタプルを前記イ
    ナー・テーブルから出力し、（ロ）前記アウタ・テーブ
    ルの最後のタプルに対し、以前出力しなかったイナー・
    テーブルからのすべてのタプルを出力する各工程を含む
    請求項１記載のジョインの実行方法。
  6. 【請求項６】 イナー・テーブルと、複数のコラムを有
    する複数のタプルから成り選択された組のコラムに基づ
    き分類された順に順序付けされたアウタ・テーブルとを
    有し、コンピュータ化データベース・システムにおける
    アウタ・ジョインの実行方法であって、（イ）選択され
    た組のコラムの値が前記アウタ・テーブルの最初のタプ
    ルに対して選択された組のコラムの値より小さいイナー
    ・テーブルのすべてのタプルを出力し、（ロ）現行タプ
    ル及び次のタプルを参照してアウタ・テーブルのタプル
    を通して順序付けし、前記アウタ・テーブルの各個有な
    組のコラムの値に対し、最後のタプルのものを除き、前
    記アウタ・テーブルの現行タプルに対して選択された組
    のコラムの値より大きいか等しく及び前記アウタ・テー
    ブルの次のタプルに対して特定された組のコラムの値よ
    り小さい選択された組のコラムの値を有するイナー・テ
    ーブルのすべてのタプルに対応する一組のタプルを前記
    イナー・テーブルから出力し、（ハ）前記アウタ・テー
    ブルの最後のタプルに対し、以前出力されなかった前記
    イナー・テーブルからのすべてのタプルを出力する各工
    程を含み、 イナー・テーブルの分類を必要とせず、イナー・テーブ
    ルのすべてのタプルをアウタ・ジョイン出力に出力する
    ことを特徴とするコンピュータ化データベース・システ
    ムにおけるアウタ・ジョインの実行方法。
  7. 【請求項７】 前記アウタ・ジョインの実行方法は、更
    に、（イ）前記アウタ・テーブルをコラムの値による順
    序付けに基づき複数の区画に区分し、（ロ）前記アウタ
    ・テーブルの区画に複数のタスクを割当て、（ハ）前記
    タスクを並行に走行する各工程を含み、前記アウタ・ジ
    ョインの並列遂行を達成するようにしたことを特徴とす
    る請求項６記載のアウタ・ジョインの実行方法。
  8. 【請求項８】 前記工程（ハ）は更に、前記選択された
    組のコラムの値が前記アウタ・テーブルの最後のタプル
    に対して指定された組のコラムの値より大きいか等しい
    値を有するイナー・テーブルのすべてのタプルを出力す
    る工程を含むことを特徴とする請求項６記載のアウタ・
    ジョインの実行方法。
  9. 【請求項９】 複数のコラムを有する複数のタプルから
    なる記憶付きイナー及びアウタ・テーブルのジョインを
    実行する手段を有し、前記アウタ・テーブルは選択され
    た組のコラムに基づき分類された順に順序付け又は割出
    しするようにしたコンピュータ化データベース・システ
    ムであって、（イ）前記イナー・テーブルのすべてのタ
    プルが唯一の責任領域に属するよう、前記選択された組
    のコラムを使用して、前記イナー・テーブルの複数の責
    任領域を決定する手段と、（ロ）前記責任領域に属する
    前記イナー・テーブルのすべてのタプルを出力すること
    により各責任領域を処理する手段とを含み、 前記データベース・システムは前記イナー・テーブルの
    分類を必要とせず、前記イナー・テーブルのすべてのタ
    プルをジョイン出力に出力することを特徴とするコンピ
    ュータ処理データベース・システム。
  10. 【請求項１０】 前記決定する手段は、更に、（イ）現
    行タプル及び次のタプルを参照してアウタ・テーブルの
    タプルを通して順序付けし、前記アウタ・テーブルの各
    個有な組のコラムの値に対し、最後のタプルのものを除
    き、前記アウタ・テーブルの現行タプルに対して選択さ
    れた組のコラムの値より大きいか等しく及び前記アウタ
    ・テーブルの次のタプルに対して指定された組のコラム
    の値より小さい選択された組のコラムの値を有するイナ
    ー・テーブルのすべてのタプルに対応する前記イナー・
    テーブルからの一組のタプルを含むよう責任領域を定義
    する手段と、（ロ）如何なる責任領域にも割当てられな
    かった前記イナー・テーブルからのすべてのタプルを含
    むよう前記アウタ・テーブルの最後のタプルに対する責
    任領域を定義する手段とを含むことを特徴とする請求項
    ９記載のコンピュータ処理データベース・システム。
  11. 【請求項１１】 前記コンピュータ化データベース・シ
    ステムは、更に、（イ）現行タプル及び次のタプルを参
    照してアウタ・テーブルのタプルを通して順序付けし、
    前記アウタ・テーブルの各個有な組のコラムの値に対
    し、最後のタプルのものを除き、前記アウタ・テーブル
    の現行タプルに対して選択された組のコラムの値より大
    きいか等しく及び前記アウタ・テーブルの次のタプルに
    対して指定された組のコラムの値より小さい選択された
    組のコラムの値を有するイナー・テーブルのすべてのタ
    プルに対応する一組のタプルを前記イナー・テーブルか
    ら出力する手段と、（ロ）前記アウタ・テーブルの最後
    のタプルに対し、以前出力されなかった前記イナー・テ
    ーブルからのすべてのタプルを出力する手段とを含むこ
    とを特徴とする請求項９記載のコンピュータ処理データ
    ベース・システム。
  12. 【請求項１２】 前記決定する手段は、更に空白及び非
    空白両責任領域を含む請求項９記載のコンピュータ処理
    データベース・システム。
JP4178884A 1991-08-23 1992-06-15 コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム Expired - Lifetime JPH077422B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US74908891A 1991-08-23 1991-08-23
US749088 1991-08-23

Publications (2)

Publication Number Publication Date
JPH05197763A JPH05197763A (ja) 1993-08-06
JPH077422B2 true JPH077422B2 (ja) 1995-01-30

Family

ID=25012201

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4178884A Expired - Lifetime JPH077422B2 (ja) 1991-08-23 1992-06-15 コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム

Country Status (3)

Country Link
US (2) US5557791A (ja)
EP (1) EP0529916A3 (ja)
JP (1) JPH077422B2 (ja)

Families Citing this family (71)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5537589A (en) * 1994-06-30 1996-07-16 Microsoft Corporation Method and system for efficiently performing database table aggregation using an aggregation index
US5812996A (en) * 1994-07-12 1998-09-22 Sybase, Inc. Database system with methods for optimizing query performance with a buffer manager
GB9417314D0 (en) * 1994-08-27 1994-10-19 Int Computers Ltd Method for performing joins in a database system
US5680603A (en) * 1994-10-20 1997-10-21 International Business Machines Corporation Method and apparatus for reordering complex SQL queries containing inner and outer join operations
US5659728A (en) * 1994-12-30 1997-08-19 International Business Machines Corporation System and method for generating uniqueness information for optimizing an SQL query
US5615361A (en) * 1995-02-07 1997-03-25 International Business Machines Corporation Exploitation of uniqueness properties using a 1-tuple condition for the optimization of SQL queries
US5778354A (en) * 1995-06-07 1998-07-07 Tandem Computers Incorporated Database management system with improved indexed accessing
EP0752652B1 (en) * 1995-07-03 1998-12-16 Sun Microsystems, Inc. System and method for implementing a hierarchical policy for computer system administration
US5926815A (en) * 1995-07-27 1999-07-20 James, Iii; J. Colin Binary sort access method and apparatus
WO1997011433A1 (en) * 1995-09-21 1997-03-27 The Trustees Of Columbia University In The City Of New York Performing efficient join operations on large tables
US5666525A (en) * 1995-09-21 1997-09-09 The Trustees Of Columbia University In The City Of New York System and method for performing an efficient join operation on large tables with a small main memory
USRE37965E1 (en) * 1995-09-27 2003-01-07 International Business Machines Corporation Method for localizing execution or subqueries and determining collocation of execution of subqueries in a parallel database
US5745746A (en) * 1996-06-24 1998-04-28 International Business Machines Corporation Method for localizing execution of subqueries and determining collocation of execution of subqueries in a parallel database
US5797136A (en) * 1995-10-05 1998-08-18 International Business Machines Corporation Optional quantifiers in relational and object-oriented views of database systems
US5692181A (en) * 1995-10-12 1997-11-25 Ncr Corporation System and method for generating reports from a computer database
US5761657A (en) * 1995-12-21 1998-06-02 Ncr Corporation Global optimization of correlated subqueries and exists predicates
US5713015A (en) * 1996-05-30 1998-01-27 International Business Machines Corporation Reordering of complex SQL queries involving GROUPBYs, joins, outer joins and full outer joins
US5842209A (en) * 1996-09-03 1998-11-24 International Business Machines Corporation User interface for visually depicting inner/outer/left/right joins in a database system
US5924089A (en) * 1996-09-03 1999-07-13 International Business Machines Corporation Natural language translation of an SQL query
US6085186A (en) * 1996-09-20 2000-07-04 Netbot, Inc. Method and system using information written in a wrapper description language to execute query on a network
US5848408A (en) * 1997-02-28 1998-12-08 Oracle Corporation Method for executing star queries
US5987453A (en) * 1997-04-07 1999-11-16 Informix Software, Inc. Method and apparatus for performing a join query in a database system
US5873074A (en) * 1997-04-18 1999-02-16 Informix Software, Inc. Applying distinct hash-join distributions of operators to both even and uneven database records
US5983215A (en) * 1997-05-08 1999-11-09 The Trustees Of Columbia University In The City Of New York System and method for performing joins and self-joins in a database system
US6289335B1 (en) * 1997-06-23 2001-09-11 Oracle Corporation Fast refresh of snapshots containing subqueries
US5963933A (en) * 1997-06-25 1999-10-05 International Business Machines Corporation Efficient implementation of full outer join and anti-join
US5999924A (en) 1997-07-25 1999-12-07 Amazon.Com, Inc. Method and apparatus for producing sequenced queries
US6442543B1 (en) 1997-07-25 2002-08-27 Amazon.Com, Inc. Method and apparatus for changing temporal database information
US6253197B1 (en) * 1998-10-06 2001-06-26 International Business Machines Corporation System and method for hash loops join of data using outer join and early-out join
US6192357B1 (en) * 1998-11-03 2001-02-20 Platinum Technology, Inc. Method and apparatus for optimizing query generation by selectively utilizing attributes or key values
US6279004B1 (en) 1998-12-22 2001-08-21 International Business Machines Corporation Database index key versioning
US6532458B1 (en) * 1999-03-15 2003-03-11 Microsoft Corporation Sampling for database systems
US6105020A (en) * 1999-10-11 2000-08-15 International Business Machines Corporation System and method for identifying and constructing star joins for execution by bitmap ANDing
US6560595B1 (en) * 1999-11-15 2003-05-06 Novell, Inc. Operator for correlated predicates in a query
US6505187B1 (en) * 1999-12-08 2003-01-07 Ncr Corporation Computing multiple order-based functions in a parallel processing database system
US6397206B1 (en) * 1999-12-15 2002-05-28 International Business Machines Corporation Optimizing fixed, static query or service selection and execution based on working set hints and query signatures
US6640221B1 (en) 2000-07-10 2003-10-28 Sas Institute Inc. System and method for configuring, sequencing and viewing joins in a query
US6804678B1 (en) * 2001-03-26 2004-10-12 Ncr Corporation Non-blocking parallel band join algorithm
US7085769B1 (en) * 2001-04-26 2006-08-01 Ncr Corporation Method and apparatus for performing hash join
KR20030014011A (ko) * 2001-08-10 2003-02-15 (주)프리즘엠아이텍 이종의 데이터 베이스 자동 병합 시스템 및 그 방법
US6980976B2 (en) * 2001-08-13 2005-12-27 Oracle International Corp. Combined database index of unstructured and structured columns
US6850933B2 (en) * 2001-11-15 2005-02-01 Microsoft Corporation System and method for optimizing queries using materialized views and fast view matching
US7356542B2 (en) * 2003-08-22 2008-04-08 Oracle International Corporation DML statements for densifying data
US7426522B2 (en) * 2003-09-23 2008-09-16 International Business Machines Corporation Object oriented query path expression to relational outer join translator method, system, article of manufacture, and computer program product
US6944633B1 (en) * 2003-12-10 2005-09-13 Ncr Corporation Performing a join in a partitioned database system
US7873629B1 (en) 2004-06-07 2011-01-18 Teradata Us, Inc. Dynamic partition enhanced inequality joining using a value-count index
US7640244B1 (en) * 2004-06-07 2009-12-29 Teredata Us, Inc. Dynamic partition enhanced joining using a value-count index
US7478080B2 (en) * 2004-09-30 2009-01-13 International Business Machines Corporation Canonical abstraction for outerjoin optimization
US7814090B2 (en) * 2005-05-31 2010-10-12 Oracle International Corporation Query generator
US7376646B2 (en) * 2005-06-17 2008-05-20 International Business Machines Corporation Cost-based subquery correlation and decorrelation
US20070226264A1 (en) * 2006-03-22 2007-09-27 Gang Luo System and method for real-time materialized view maintenance
US7962476B2 (en) * 2006-07-26 2011-06-14 Applied Minds, Inc. Method and apparatus for performing a depth-first join in a database
US7698542B2 (en) * 2006-08-25 2010-04-13 Infineon Technologies Ag Circuit and method for comparing program counter values
KR100871784B1 (ko) * 2006-11-30 2008-12-05 주식회사 케이티프리텔 데이터 유효값의 현행화 관리 장치 및 그 방법
US8074219B2 (en) 2007-06-27 2011-12-06 Microsoft Corporation Order preservation in data parallel operations
JP5048417B2 (ja) * 2007-08-07 2012-10-17 株式会社富士通ビー・エス・シー データベース管理プログラム及びデータベース管理装置
US7730055B2 (en) * 2008-06-23 2010-06-01 Oracle International Corporation Efficient hash based full-outer join
US20130232133A1 (en) * 2010-12-03 2013-09-05 Awny K. Al-omari Systems and methods for performing a nested join operation
US9594573B2 (en) * 2011-01-14 2017-03-14 Hewlett Packard Enterprise Development Lp Systems and methods of block computation
US8793287B2 (en) 2011-05-27 2014-07-29 Sap Ag Equi-joins between split tables
US9552392B2 (en) * 2011-12-29 2017-01-24 Teradata Us, Inc. Optimizing nested database queries that include windowing operations
US9141646B1 (en) * 2011-12-30 2015-09-22 Teradata Us, Inc. Database redistribution in dynamically-configured database systems
JP5765244B2 (ja) * 2012-01-11 2015-08-19 富士通株式会社 テーブル処理装置、テーブル処理方法、及びプログラム
US8825633B2 (en) 2012-05-15 2014-09-02 Sas Institute Inc. System, method, and data structure for automatically generating database queries which are data model independent and cardinality independent
US10268639B2 (en) * 2013-03-15 2019-04-23 Inpixon Joining large database tables
US9519662B2 (en) * 2013-09-10 2016-12-13 International Business Machines Corporation Boolean term conversion for null-tolerant disjunctive predicates
US20150293947A1 (en) * 2014-04-10 2015-10-15 Raghuvira Bhagavan Validating relationships between entities in a data model
US10162857B2 (en) 2015-08-31 2018-12-25 Qatar Foundation For Education, Science And Community Optimized inequality join method
US10733187B2 (en) * 2018-02-09 2020-08-04 International Business Machines Corporation Transforming a scalar subquery
US11016978B2 (en) 2019-09-18 2021-05-25 Bank Of America Corporation Joiner for distributed databases
US11126401B2 (en) 2019-09-18 2021-09-21 Bank Of America Corporation Pluggable sorting for distributed databases

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS583031A (ja) * 1981-06-30 1983-01-08 Fujitsu Ltd リレ−シヨナル・モデルにおけるジヨイン演算処理方式
JPS59125461A (ja) * 1982-12-30 1984-07-19 Fujitsu Ltd リレ−シヨナル・デ−タベ−スにおけるアウタ−ジヨイン演算方式
US4506326A (en) * 1983-02-28 1985-03-19 International Business Machines Corporation Apparatus and method for synthesizing a query for accessing a relational data base
US4967341A (en) * 1986-02-14 1990-10-30 Hitachi, Ltd. Method and apparatus for processing data base
US5043872A (en) * 1988-07-15 1991-08-27 International Business Machines Corporation Access path optimization using degrees of clustering
US5121494A (en) * 1989-10-05 1992-06-09 Ibm Corporation Joining two database relations on a common field in a parallel relational database field
US5210870A (en) * 1990-03-27 1993-05-11 International Business Machines Database sort and merge apparatus with multiple memory arrays having alternating access

Also Published As

Publication number Publication date
US5557791A (en) 1996-09-17
US5551031A (en) 1996-08-27
EP0529916A2 (en) 1993-03-03
EP0529916A3 (en) 1993-10-20
JPH05197763A (ja) 1993-08-06

Similar Documents

Publication Publication Date Title
JPH077422B2 (ja) コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム
US6334125B1 (en) Method and apparatus for loading data into a cube forest data structure
US6185557B1 (en) Merge join process
US6424967B1 (en) Method and apparatus for querying a cube forest data structure
US6141655A (en) Method and apparatus for optimizing and structuring data by designing a cube forest data structure for hierarchically split cube forest template
US6529896B1 (en) Method of optimizing a query having an existi subquery and a not-exists subquery
US6289334B1 (en) Apparatus and method for decomposing database queries for database management system including multiprocessor digital data processing system
O'Neil et al. Multi-table joins through bitmapped join indices
US6032143A (en) Evaluation of existential and universal subquery in a relational database management system for increased efficiency
US5590324A (en) Optimization of SQL queries using universal quantifiers, set intersection, and max/min aggregation in the presence of nullable columns
US5864847A (en) Reordering of complex SQL queries involving groupbys, joins, outer joins and full outer joins
US7734620B2 (en) Optimizing a database query that fetches N rows
US6009432A (en) Value-instance-connectivity computer-implemented database
US20040172400A1 (en) Using associative memory to perform database operations
CA2178264A1 (en) Database management system with improved indexed accessing
US7542962B2 (en) Information retrieval method for optimizing queries having maximum or minimum function aggregation predicates
Rao et al. Using eels, a practical approach to outerjoin and antijoin reordering
US6253196B1 (en) Generalized model for the exploitation of database indexes
US6745173B1 (en) Generating in and exists queries using tensor representations
Jarke et al. Query processing strategies in the Pascal/R relational database management system
US20240394278A1 (en) Transforming relational statements into hierarchical data space operations
US20020138464A1 (en) Method and apparatus to index a historical database for efficient multiattribute SQL queries
Farias de Souza et al. Efficient materialization and use of views in data warehouses
Hellström Oracle SQL & PL/SQL Optimization for developers documentation
JPH02236778A (ja) 問い合わせ最適化処理方法