JPS5875245A

JPS5875245A - 関係代数演算装置

Info

Publication number: JPS5875245A
Application number: JP56173261A
Authority: JP
Inventors: Kazuhide Iwata; 岩田　和秀; Shigeki Shibayama; 柴山　茂樹; Yutaka Hitai; 比田井　裕; Shigeru Koyanagi; 滋小柳
Original assignee: Toshiba Corp; Tokyo Shibaura Electric Co Ltd
Current assignee: Toshiba Corp
Priority date: 1981-10-29
Filing date: 1981-10-29
Publication date: 1983-05-06

Abstract

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

Description

【発明の詳細な説明】本発明は関係データベースの属性データに対する関係代
数演算を効率良く実行することのできる関係代数演算装
置に関する。

データベースシステムを構築する場合、現実世界を抽象
化して割算機内部に表現するモデル化が必要であり、従
来より幾つかのデータモデルが提唱されている。その代
表的なものに、階層モデル、網モデル、関係モデル等が
ある。これらの中で、特に有望視されている関係モデル
は、数学の集合論における関係の概念を応用したもので
、何らかの意味を有するデータの集まりに着目してデー
タベースを構築したものである。上記した階層モデルや
網モデル等の従来一般的なモデルは、ポインタチェーン
で繋がれた複雑なデータ構造を有し、且つ応用プログラ
ムに依存しているのに対し、上記の関係モデルはそのデ
ータが集合で表現される為に、データ構造が単純であり
、しかも応用プログラムが変化してもその影響を受けな
いと云う優れた特徴を有している。この為、将来の大容
量データベースシステムヤ知識データベースシステムの
構築に備え、関係モデルの実働化に関する研究が種々性
われている。

ところが、現用の計算機の殆んどは、数値計算の高速処
理を目的として設計されている。この為、上記関係モデ
ルで示される非数値処理を汎用計算機で実行せんとする
と、その処理プログラムが非常に複雑化する上、処理時
間が非常に膨大となる不都合があった。つ−まり、関係
モデルにあられれる集合演算を従来の汎用計算機で実行
することは、そのアーキテクチャが本質的に異っている
ので、その特徴を十分に活かすことができなかった。こ
れ故、従来よりその対策が強く望まれ、関係モデルにお
ける種々の集合演算を効率良く実行できる装置の開発が
嘱望されている。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところｉｊ：、ｌＷｊ係データベースを扱
うデータペースシステムにおいて必要となる種々の集合
演算を効率良く、寸だ高速に実行することのできる簡易
で実用性の高い関係代数演算装置を提供することにある
。

本発明の概要は、属性単位で格納された関係データペー
スの成る属性データに着目して所定規則に従って例えば
ソート処理するに際し、上記属性データに仮想キーを付
・□してソート処理を行わしめ、このソート処理によっ
て変換された仮想キーをアドレスとして他の属性データ
をソート処理することによって、簡易にして上記目的を
効果的に達成するようにしたものである。

以下、図面を参照して本発明の詳細につき貌。

明する。

属性データの集゛まりとして表現される関係データベー
スは、例えば第１表の如く示される。

この関係表は、「レコード番号」「曲目」［作曲家ｊ「
レコード会社」からなる属性により構成された「レコー
ド目録」を示している。

第　　１　　表この第１表において、行はタラプル、列は属性と称され
る。今、このような関係表から、曲目をアルファベット
の順に整理する（並び換える）と云う集合演算を行い、
第２＠に示す如き関係表を作成するものとする。

第　　２　　表この演算を実行する場合、第１表に示される関係表をメ
モリに格納する方式として、１つけタラゾルをペースと
して第１図（、）に示すように（１４３，Ｃ，ｆ　、Ｔ
）（１５５，Ａ、ｂ、Ｓ）・・・なる組を形成する方式
と、第２図（ｂ）に示すように属性をペースとして（１
４３，１５５・・・）（Ｃ，Ａ・・・）・・・なる組を
形成する方式とがある。

このようなデータの格納法は、データペース設計におけ
る基本的な問題であシ、−概にどちらが優れていると結
論することはできない。

然し乍ら、上記した第１表に示される関係表から第２表
に示される関係表を得る場合、その集合演算はノート処
理であるから、属性をペースとした方が有利であると云
える。即ち、タラグルをペースとした場合、全タラゾル
をソートエンジンに導びき、その「曲目」の属性にのみ
着目してソート処理を行うことになるのに対し、属性を
ペースとした場合には、「曲目」なる項の属性データの
みをソートエンジンに供給してソート処理することが可
能となる。従ってメモリとソートエンジンとの間のデー
タ転送量を少なくすることができ、またソートエンジン
に余分なバッファメモリ容量を設ける必要がないことか
ら、属性をペースとした方が有利となる。

然し乍ら、このようにして属性をペースとした場合には
、そのソート処理結果に応じて他の属性データを並び換
える処理、っ壕シデータの振分は処理が必要となると云
う問題が生じる。

本発明は、基本的には上記関係データペースの属性デー
タをペースとしてソート処理を実行することにより、デ
ータ転送量を少なくし、また必要とするバッファメモリ
容量を少なくしてソートエンジンの小型化を図ると共に
、そのソート処理結果に基づく他の属性データのソート
処理（並び換え）を簡易に且つ効率良く実行できるよう
にして、演算処理の簡易化と高速化を図るようにしたも
のである。

第２図は実施例装置の概略構成図であり、１は関係デー
タベースを属性単位で格納しているメモリである。この
メモリ１に格納されたデータペースは、着目された成る
属性につきそのデータが読出されて仮想キー付加部２に
導ひかれる。この仮想キー付加部２には仮想キー発生部
３が発生する加想キーが与えられており、上記属性デー
タにそれぞれ付加されるようになっている。この仮想キ
ーは、例えばキー列ｋ（０，１，２・・・）からなるも
ので、先の第１表に示される関係表から読出された属性
データの列（Ｃ１Ａ１Ｆ、Ｂ・・・）に対してそれぞれ
付加される。

これによって、そのデータは（Ｃ，Ｏ）、（Ａ１１）、
（Ｆ、２）・・なるデータの組として生成され、関係代
数演算部としての例えばソートエンジン４に供給される
。

しかしてソートエンジン４では、これらのデータに対し
て、属性に与えられた規則に従い、上記属性データ（Ｃ
，Ａ、Ｆ・・・）の並び換え、つまシソート処理を実行
する。このとき、上記付加された仮想キーも同時に並び
換えられることになる。従って、ソート処理の結果、仮
想キーの列ｋ（０，１，２・・・）は、例えばに’（１
，３、Ｏ・・・）のように変換される。このようにして
ノート処理された属性データは、メモリ１に書込まれた
のち出力され、また上記ソート処理によって変換された
仮想キー列は、アドレス制御部５に与えられる。これに
よってアドレス制御部５は上記変換された仮想キー列を
アドレス情報としてメモリ１に格納された他の属性デー
タを順次読出す。これによって、必要とする属性データ
が、先の成る属性に対して与えられた規則に従ってソー
トされて出力されることになる。例えば関係表が第１図
（ｂ）に示すようにタラプルをペースとしてメモリ１に
格納されている場合、各属性のデータ数がＴで、各属性
に与えられた番号をｎ、バイアス値をαとしたとき、仮
想キーに′で示されるアドレスは α＋Ｔ１１ｎ＋に′ となる。第１表に示される関係表の場合、Ｔが６である
から、変換された最初の仮想キーに′（＝１）によって
示されるアドレスは α＋１．　α＋７．　α＋１３．　α＋１９となる。こ
れによってメモリ１からは（１５５、Ａ、ｂ、Ｓ）なる
タラプルをペースとしたデータが読出されることになる
。そして、次の１１位の仮想キーに′は「３」となるこ
とから、今度はアドレス α＋３．　α＋９．　α＋１５．　α＋２１が指定され
、データ（１４４、Ｂ、ａ、Ｔ）が読出されることにな
る。以下、仮想キーに′の列（１，３、Ｏ１５，４，２
）に従って順次アドレス指定されてデータが読出され、
ここに第２表に示される関係表が作成されることになる
。

このように本装置によれば、着目した属性のデータに仮
想キーを付加し、この属性データを所定の規則に従って
ソート処理したのち、このソート処理によって変換され
た仮想キーをアドレス情報として他の属性データを指定
するだけで、簡易に関係モデルの集合演算（ソート処理
）を実行できる。しかもソートエンジンには、成る属性
データに仮想キーを付加したものだけを供給すればよい
ので、エンジンにおけるノ々ツファメモリの容量を十分
小さく設定することができ、その小型化を図ることがで
きる。しかもデータ転送量を少なくすることができるの
で、データの取扱いが簡単であり、制御も容易である。

従って処理効率の向上を図り、高速化を図ることができ
る。

さて、このような演算処理を実行する本装置は、具体的
には第３図に示すように構成される、。

即ち、関係データベースを属性単位で格納したメモ＋）
１１、ソートエンジン１２、マージエンジン１３を、中
央処理装置（ＣＰＵ）１４のＩ１０パスライン１５およ
びメモリパスライン１６に接続し、これらのパスライン
１５．１６を介してデータ転送すべく構成する。そして
、」二記ＣＰＵ７４にＩ１０パスライン１５を介して仮
想キー発生カウンタ１７を接続し、ソート処理の対象と
なる属性データがメモリ１１からソートエンジン１２に
送られる都度、カウンタ１７が発生する仮想キーをソー
トエン・シン１２に与えて上記属性データに付加する。

ソートエンジン１２では、上記仮想キーをマスクして属
性データのソート処理を実行し、その結果を仮想キーと
共にＣＰＵ　１４に与える。これによってＣＰＵ１４は
、上記ソート処理によって変換された仮想キーに基づい
てメモリ１ノのアドレス指定を行うことによシ、同メモ
リ１１′からソート処理された関係表を得る。

このように装置を構成することによって前述したソート
処理を極めて簡易にして、且つ効率良く実行することが
可能と々る。しかも着目すべき属性のデータについての
みソート処理を実行することにより、簡易にその演算目
的を達成することができ、実用的利点が多大である。

尚、ここではソート処理について実行したが、マージエ
ンジン１３を用いたマージ処理についても、上記仮想キ
ーを用いて簡易に効率良く演算することができる。また
これらの関係データベースシステムの演算のみ力らず、
他の関係モデル演算にも効果を奏する。例えば２つの関
係モデルＲ１、Ｒ２についてそれぞれ仮想キーに１、ｋ
２を与えることによって、２つの関係モデルにまたがる
Ｊｏｉｎ　、　Ｄｉｖｉｓｉｏｎ　、　ＡＮＤ、ＯＲ等
の集合演算を効率良く実行することができる。つまり、
仮想キーを導入することによって、データ転送量を少々
くして効率の良い関係代数演算を実行できる。

以上説明したように本発明によれば、関係データベース
の成る属性データに仮想キーを付加したのち所定の関係
代数演算を行ったのち、これによって変更された仮想キ
ーをアドレスデータとして他の属性データを関係代数演
算処理するので、上記関係データベースを高速度に且つ
簡易、に効率よく関係代数演算処理することができ、し
かもデータ転送量を少なくして処理効率の向上を図り得
る等の実用上多大なる効果を奏する。

尚、本発明は上記実施例にのみ限定されるものではない
。例えば仮想キーに従うアドレス制御をＣＰＵ１４によ
って行うことのみならず、専用のアドレス制御部をハー
ドウェアによって構成してもよい。また扱う関係モデル
も上述した例に限られるものではなく、属性の数やタラ
ゾルの数は仕様に応じて定めればよい。また複数の関係
モデルにそれぞれ仮想キーを付加して、各関係データモ
デル間の関係、代数演算を行うようにしてもよい。要す
るに本発明はその要旨を逸脱しない範囲で種々変形して
実施することができる。

【図面の簡単な説明】

第１図（、）　（ｂ）はそれぞれ関係データベースのメ
モリ格納例を示す図、第２図は本発明装置の基本的な構
成図、第３図は本発明の一実施例を示す装置構成図であ
る。１・・・メモリ、２・・・仮想キー付加部、３・・仮想
キー発生部、４・・・ソートエンジン、５・アドレス制
御部、１１・・・メモリ、１２・・・ソートエンジン、
１３・・・マージエンジン、１４・・・ＣＰＵ。

Claims

【特許請求の範囲】

メモリに属性単位で格納された関係データベースの成る
属性データを読出し、この属性データに仮想キーを付加
したのち仮想キーをマスクして上記属性データを所定規
則に従って関係代数演算し、この関係代数演算によって
変換された上記仮想キーをアドレスデータとして前記関
係データベースの他の属性データを関係代数演算処理す
ることを特徴とする関係代数演算装置。