JPS59125461A - リレ−シヨナル・デ−タベ−スにおけるアウタ−ジヨイン演算方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、リレーショナル・データベースにおけるアウ
タージョイン処理方式、特に２つのりレーションのアウ
タージョイン演算を通常のジョイン演算（等号ジョイン
）及び集合差、集合和演算の組合せとして処理するので
はなく、ジョイン対ｉ　リレーションをジョイン・フィ
ールドでソートした後、それらの２つのソート・リレー
ションのレコードを同時スキャンし、ジョイン・フィー
ルドの大小・相等判定によってアウタージョイン結果の
レコードを高速に求めることのできるジョイン処理方式
に関するものである。

〔従来技術と問題点〕

従来のジョイン演算処理方式としては、等号ジョイン＋
件を満たすレコードを２つのりレーションから抽出し結
合することしか行なわず、一方のりレーションにのみ存
在するレコードはジョイン結果に含まれない。アウター
ジョイン演算は双方のりレーションのジョイン・フィー
ルドに対応する値をもつレコード同士を等号ジョイン演
算同様に結合するとともに、片方のりレーションのジョ
イン・フィールドにしか存在しない値ンもつレコードも
結果のりレーションに含めることができる。

このとき結合結果のあるフィールド（リレーションの属
性情報）は値をもちえないことが生ずるが未定義値（Ｎ
ＩＬ値）を補うのが普通である。

アウタージョイン演算は等号ジョイン演算と集合差・集
合和演算７用いて処理可能である。以下にその定義式ン
示す。

Ａ（ａｌ、Ｂ２） リレーションＡはフィールドａｌ、ａ２からなる。

Ｂ（ｂｌ、ｂｌ） リレーションＢはフィールドｂｌ、ｂ２からなる。

Ｅ（ａｌ、ａｚ、ｂｌ）＝ＡＣａｘ＝ｂ１’］　Ｂは、
ジョイ７−フィールドａｌ、ｂｌで対応する値ンもつレ
コード同志だげン結合した結果、リレーションＥはフィ
ールドａｌ（またはｂｌ）・ａ２ｓｂ２からなることを
示す。

アウタージョイン演算 ０（ａｌ、　Ｂ２．　ｂｌ）＝Ｅ（ａｌ、　Ｂ２．　ｂ
ｌ）Ｌ）Ａ　１　（ａｌ、　　Ｂ２．ＮＩＬ）ＵＢＪ（
ｂｔ、Ｎ１．ｌ）２ンたｘ　Ｌ　　ＡｌＣａ１ｅ　８２
）＝Ａ−ｇ（ｊＬ１＋　Ｂ２）Ｂ１（ｂｌ、ｂｌ）＝Ａ
−Ｅ（ａｔ、　ｂｌ）こＮでしをヱ果合和演算、−は集
合差演′ｘケ表す。

第１図は従来のアウタージョイン演算処理の手続き乞示
す。第１図に示す従来方式によれば、Ｅ。

Ａｌ、Ｂｌという中間結果乞作成すること及び最終結果
Ｏン求めろために、Ｅ、　Ａｔ、　Ｂｌ　ｙｇ−それぞ
れスキャンしなげればならず、ＡとＢから直接Ｏｉ作成
する場合に比較して、処理時間が大きくなる欠点がある
。Ａ、Ｂリレーションのレコード数が増加すると共に処
理効率の低下の原因になる。

〔発明の目的〕

本発明はアウタージョイン演算処理において、ジョイン
対象のりレーションがソートされていることを前提とし
て、それらのりレーション乞同時にスキャンし２つのジ
ョインフィールドの値の大小・相等比較の判定にもとづ
いてレコード同士のアウタージョイン結合を行い結果の
りレーションを作成することにより、等号ジョイン演算
、集合演算の組合せで処理する従来方式に比べ、中間リ
レーションを作成せず、比較的高速な処理方式ン笑現す
ることＺ目的としている。

〔発明の構成〕

そしてそのため、本発明のリレーショナル・データベー
スにおけるアウタージョイン演算方式は、複数の属性情
報２１組のレコードにまとめ、同一種類のレコードの集
合を１つのりレーションとして扱い、複数のりレーショ
ンから構成されろリレーショナル・データベース乞有し
、複数個のりレーショノンジョイン・フィールドに関す
るアウタージョイン演算処理馨行ない結果馨りレーショ
ンとして求めろデータ処理システムにおいて、上記ジョ
インされるリレーションのジョイン・フィールドの値に
もとづいて昇順にレコードを配列したソート・リレーシ
ョンを作成するソート・リレーション作成過程を備える
と共に、複数のソート・リレ、ジョンの先頭レコードか
ら逐次ジョイン・フィールドの！乞抽出・比較し、その
大小・相等に対応して、アウタージョイン結果のレコー
ド７作成し、それχ結果のりレーションに挿入するアウ
タージョイン演算処理過程７有すること乞特徴とするも
のである。

〔発明の実施例〕

アウタージョイン演算処理は等号ジョイン演算処理方式
の拡張と考える。等号ジョイン演算処理は、ジョイン対
象りレーションンジョイン嶽フィールドでソートした後
、それらのソート・フィールド−ｙＦＪ時スギャンし、
等しい値をもつレコード対だけン抽出するが、一致しな
いレコードは読み飛ばす。抽出したレコード同士を結合
し、１つのレコードにして結果のりレーションに挿入す
る。

本発明ばアウタージョイン演算を実現する処理方式め具
体的な処理アルゴリズムン等号ジョイン演算の処理アル
ゴリズムの拡張によって考案したものである。第２図に
アウタージョイン演算処理の流れ図ン示−ｆ′。第２図
において、記号は下記のような意味を持っている。

ｔｌ、　　ｔ２ リレーションＡのレコード・スキャン・ポインタ ｒ　ｌ、　　ｒ　２ リレーション早のレコード・スキャン・ポインタ ＆１ｔ　１ ポインタｔ１が現在指すりレーションＡ（１））ヨイン
・フィールドａｌＱ値 ｔｔｌ ポインタｔ１が指すＡのレコード ｒｘ ポインタｒ１が指すＢのレコード ＥＯＰ　　　　　　　　　　！ スキャンの終了点 （ＮＩＬ、　Ｌｒ　１　＞ ＮＩＬ値とレコードｔｒｌｋこの順に結合する。

アクタ−ジョイン演算処理では下記のような処理が行わ
れる。

ステップ５Ｏ １１と１２’ｆｆリレーシヨンへの先頭レコードに設定
し、ｒｌとｒ２’ｌｌリレーションＢの先頭レコードに
設定する。

ステップ８１０ ｔ１＝ＥＯＰで且つｒ１＝ＥＯＰの条件Ｙ満足している
か、否かン調べる。Ｙｅｓのときは終了となり、Ｎ０Ｏ
）ときは、ステップ１】に移る。

ステ　ッ　フ゛　５ｌｌ ｔ１＝ＥＯＰで且つｒ１＼ＥＯＰの条件乞満足している
か、否かン調べる。Ｙｅｓりときはステラ１８１２に移
り、Ｎｏのときはステップ５１３４ろ。

ステップＳ１２ ＜ＮＩＬ、ｔｒ　１）ｖＯに挿入し、ｒｌ＝＝ｒ＋ｌ、
即ちポインタｒ１ン進めろ。次にステツノ８１０に戻る
。

ステップ５１３ ｔ１＼ＦＯＰで且つｒｌ＝ＥＯＰの条件を満足している
か、否か欠調べる。Ｙｅｓのときはステラ７’８１４に
移り、ＮＯのときはステップ８２０に移る。

ステップＳ］４ ＜ｔｔｌ、ＮＩｊ＞ンＯに挿入し、ｔｓ＝ｔｘ＋１、即
ちポインタｔ１７ｆ進める。次にステップ８１０に移る
。

ステップ５２０ ａｌＬｌ＝ｌ）ｌｙｌであるか、否かを調べる。

Ｙｅｓのときはステップ８２１に移り、Ｎｏのときはス
テップ８．２２に移る。

ステップＳ２１ ＜ｔｔｌ、ｔｒｌ”）ｙｔＯに挿入し、ｒｌ＝ｒｌ＋ｌ
にし、次にステップ８３０に移る。

ステップ５２２ ａｌｔｌ＞ｂｌ、ｙｉであるか、否かを調べる。Ｙｅｓ
りときはステップ８２３に移り、ＮＯのときは８２４に
移る。

ステップ８２３ ＜ＮＩＬ、ｔｒｌ＞’ａ’ＯＫ挿入し、ｒ、＝ｒ、＋ｌ
とし、ｒ２＝ｒ１とし、ステップ８１０に戻る。

ステツノ５２４ （ｔｚｘ、ＮＩＬ＞乞Ｏに挿入し、１１＝１１＋１゜ｔ
２＝１１とし、ステップ８１０に戻る。

ステップ８３０ ｒ１＝ＥＯＰか否かン調べる。Ｙｅｓのときは、ステッ
プＳ３］に移り、ＮＯのときはステップ３３２に移る。

ステップ５３１ ７１＝ｔ１＋１とし、ステップ８１０に戻る。

ステップ５３２ ａｌ／−１＝ｂｌｒｌか、否か乞調べる。Ｙｅｓのとき
はステップ８３３に移り、ＮＯのときはステップ８３４
に移る。

ステップ８３３ ＜ｔ　１１　、　ｔ　ｒ　１＞Ｙ　Ｏに挿入し、ｆ１＝
ｆｌ＋１として、ステップ８３０に戻る。

ステップ８３４ ｊｌ＝ｔ１＋１とする。

ステップ５３５ ｚ１＝ＥＯＰか否か乞調べろＹｅｓりときはステップ３
６に移り、ＮＯのときはステップＳ３７に移る。

ステップ８３６ ＜Ｎ　Ｉ　Ｌ　、　ｔ　ｒ　１　＞Ｙ　Ｏに挿入し、ｒ
ｌ＝ｒ＋１とし、ステップＳＩＯに戻る。

ステップ５３７ ａｌｔｌ＝ａｌｔ２であるか、否かン調べ、ｙｅｓのと
きはステップ８３８に移り、ＮＯのときはステップ３３
９に移る。

ステップ８３８ ｒｌ＝ｒ２．即ちスキャン・ポインタｒ　Ｉ　Ｙ　−１
する。次忙ステップ８３２に移る。

ステップ８３９ ｔ２＝ｆ１會ｒ２＝ｆ］とし、次にステップｓ２０に戻
、。　　　　。

第３図は本発明の１実施例の構成乞示すものである。第
３図において、１はリレーショナル・データベース処理
機構、２はリレーショナル演算制御部、３は解釈実行部
、４はデータ・アクセス部、５は問い合わせ解、′折部
、６は実行制御部、７はりダクンヨンソ、−ト部、８は
ジョイン実行部、９は等号ジョイン笑行部、１０はアウ
タージョイン実行部、１１はデータベース、１２はデー
タ辞書、】３はリレーションｔそれぞれ示している。

リレーショナル・データベース処理機ｍ１は、リレーシ
ョナル演算制御部２、解釈実行部３およびデータ・アク
セス部４乞有している。リレーショナル演算制御部２は
問い合せ解析部５および実行制御部６から構成され、解
析実行部３はリダクション・ノート部７およびジョイン
実行部８から構成されている。ジョイン実行部８は、等
号ジョイン実行部９とアウタージョイン実行部１０とン
有している。データベース１】は、データ辞書】２と複
数のりレーション１３を有している。

第３図において、リレーショナル・データベース処理機
構１はユーザの問い合せ（リレーショナル演算処理）ン
受付はリレーショナル演算制御部２に渡丁。リレーショ
ナル演算制御部２は、問い合せ解析部５で問い合せの構
文と意味の正当性欠チェックする。実行制御部６は、正
しい問い合せからリレーショナル演算７分類・抽出し、
その実行手順乞決定する。実行計画の立てられた問い合
せは、解釈実行部３に渡され、実行される。解釈実行部
３は、データ・アクセス部４乞介してデータベースｊ１
の中のりレーションの属性情報ヲ管理するデータ辞書１
２を参照したり、笑データ馨もつ複数のりレーション１
３ンアクセスしたりてる。リダクション・ソートやジョ
イン処理の結果のりレーションを作成したり、対象りレ
ーションをスキャン丁石基本機能は、データ・アクセス
部４がその手段乞提供する。

第４図はアウタージョイン演算を含む問い合せの具体例
７示す。この問い合せは、従業員り給与リレーションか
ら月給３０万円以上の従業員の氏名と給料ケ求めろ一万
、所属リレーションからマ管理部マ又はマ技術部マで働
く従業員を求め、双方の結果を氏名をジョイン・フィー
ルドとしてアウタージョイン演算を行うべきことン意味
している。

第５図は、具体的なりレーションに対し第４図の問い合
せを行った場合における解釈実行部３が処理する内容と
、処理結果の中間リレーションと、最終結果の所属−給
与リレーション乞説明図的に表わしたものである。シス
テムはりダクション・ソート部７において給与りレーシ
ョンと所属リレーションからそれぞれの制限条件ン満す
レコードだＩｒｊｙｘ抽出し、氏名フィールドの値で昇
順にソートーシた後そゆれぞれの中間リレーションＡお
よびＢン作成する。また、問い合せ中に複数のりレーシ
ョンに対する等号ジョイン演算を含むときジョイン実行
部８の等号ジョイン笑行部９がジョイン演算結果暑中間
リレーションとして作成する。さらに中間リレーション
Ａ、Ｈに対してアウタージョイン実行部】０が第２図に
示した演算アルゴリズムに従って、アウタージョイン処
理７行ない最終結果である給与所属リレーションン作成
する。

本発明は等号ジョイン演算の処理アルゴリズムの拡張と
して、アウタージョイン演算処理７行うものであり、基
本的手段の１つと考えてよい。

本発明では２個のりレーションに対するアウタージョイ
ン演Ｘｙｘスキャン、ジョインフィールド値の大小比較
、ＮＩＬ値とレコードの結合処理で達成している。ル（
メ３）個のりレーションに対するアウタージョイン演算
は本発明による２個のりレーションに対するアルゴリズ
ムの繰返し適用で容易に達成できる。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、ゴ等
号ジョイン演算処理で取り出せないレコード（ジョイン
・フィールド値が片方のりレーションにしかないような
レコード〕も抽出できリレーショナル・データベースＺ
使うユーザに大変な便宜を与えうるアウタージョイン演
算処理乞提供する。またアウタージョイン演算自身は等
号ジョイン演算、集合演算（相と差〕によって処理可能
であるが、そのような万代は余分の中間リレーションと
それらのスキャンを複数回必要とし処理速度ン早めろこ
とができない。、本方式によれば、２っのリレーション
の同時スキャンとジョインフィールドの大小比較及びＮ
ＩＬ値・レコード同士の結合処理のみで実現できる。等
号ジョイン演算処理との差はＮＩＬ値・レコードの結合
処理の有無だけである。以上の理由で本発明によれば、
従来方式に比べ格段に処理速度ン早めることができる効
果がある。

【図面の簡単な説明】

第１図は従来方式によるアウタージョイン演算処理方式
乞説明する図、第２図は本発明におけるアウタージョイ
ン演算処理方式乞説明する図、第３図は本発明の具体的
−実施例７示すシステム構成図、第４図はアウタージョ
イン演算処理Ｚ含む問い合せの具体例７示す図、第５図
は問い合せに対する解釈芙行処理の流れ図である。 １・・・リレーショナル・データベース処理機構、２・
・・リレーショナル演算制御部、３・・・解釈実行部、
４・・・データ・アクセス部、５・・・問い合わせ解析
部、６・・・実行制御部、７・・・リダクションソート
部、８・・・ジョイン実行部、９・・・等号ジョイン実
行部、】０・・・アウタージョイン実行部、１１・・・
データベース、１２・・・データ辞書、】３・・・リレ
ーション。 特許出願人　　富士通株式会社 代理人弁理士　　京　谷　四　部 太１　図 〉［２図（イ） 太５圀

Claims (1)

【特許請求の範囲】
1. 複数の属性情報２１組のレコードにまとめ、同一種類の
   レコードの集合乞１つのりレーションとして扱い、複数
   のりレーションから構成されるリレーショナル・データ
   ベースを有し、複数個のりレーションをジョイン・フィ
   ールドに関するアクタ−ジョイン演算処理を行ない結果
   をリレーションとして求めるデータ処理システムにおい
   て、上記ジョインされるリレーションのジョイン・フィ
   ールドの値にもとづいて昇順にレコードを配列したソー
   ト・リレーションを作成するソート・リレーション作成
   過程ンそなえると共に、複数のノート・リレーションの
   先頭レコードから逐次ジョイン・フィールドの値を抽出
   ・比較し、その大小・相等に対応して、アウタージョイ
   ン結果のレコードを作成し、それを結果のりレーション
   に挿入するアウタージョイン演算処理過程を有すること
   を特徴とするリレーショナル・データベースにおけるア
   ウタージョイン処理方式。