JP2923917B2 - 大規模知識データベースシステムにおけるデータアクセス方式 - Google Patents

Description

【発明の詳細な説明】 〔概要〕 主記憶上のデータとファイル上のデータとのデータ変
換を効率的に実行することのできるデータアクセス方式
に関し、 主記憶上のデータとファイル上でのデータをほぼ同じ
形式として両者の間の変換効率を高めることを目的と
し、 電子計算機および外部記憶手段から成り、オブジェク
ト指向言語を用いて大規模なデータを取扱う知識データ
ベースシステムにおいて、主記憶および外部記憶手段上
の全てのオブジェクトを管理するオブジェクト管理手段
と、前記外部記憶手段上に格納されているオブジェクト
を関係データベースの形式で管理するデータ管理手段
と、主記憶上で絶対アドレスとポインタとによって指示
されるデータと、前記外部記憶手段上でオフセットを用
いて入れる構造で連続領域に格納されるデータとを、前
記オブジェクト管理手段とデータ管理手段との間で相互
に変換するデータ変換手段を有するように構成する。

〔産業上の利用分野〕

本発明は大規模なデータを取扱う知識ベースシステム
に係り、さらに詳しくは、主記憶上のデータとフィルム
上のデータとのデータ変換を効率的に実行することので
きるデータアクセス方式に関する。

〔従来の技術〕

電子計算機の技術進歩、普及に伴い、ソフトウエア生
産量も加速度的に増加してきている。ソフトウエアの開
発人口が不足しているために、ソフトウエア生産は需要
に追いつかないのが現状であり、生産性の向上が切実に
要求されている。

そのための一解決策としてオブジェクト指向言語の利
用が進みつつある。オブジェクト指向言語は、COBOLやF
ORTRAN、BASICといった従来の構造的プログラミング言
語よりもプログラムを自然に記述できるという特徴があ
り、また、プロトタイピングやソフウエアの再利用にも
向いているからである。

オブジェクト指向言語によるプログラミングの基本単
位はオブジェクトであり、オブジェクトはデータと、そ
のデータに対する手続きを構成要素とする。オブジェク
トにメッセージを送ることによって、オブジェクト自ら
がそのメッセージに該当する手続を実行し、ユーザ所望
の処理の実現が可能になる。オブジェクトにはクラスと
インスタンスがあり、インスタンスが具体的な値やデー
タであるのに対して、クラスはよく似た性質を持つオブ
ジェクトの集合である。また、クラス間に上位下位関係
を定義することも可能である。

第12図はクラスの説明図である。医者というクラスが
あり、その下位のクラスとして歯科医、内科医、外科医
等の各科の医者のクラスが定義できる。また各科の医者
のクラスは、その科の一人一人の医者をインスタンスと
する集合である。

同じクラスに属するインスタンスは、そのクラスに記
述された属性を継承して共通にもつ。例えば同図におい
て、内科医のクラスのインスタンスは内科医１、内科医
２等、一人一人の内科医の情報で、内科医のクラスに記
述された属性（名前、免許番号、患者名）を内科医のク
ラスに属する各インスタンスが共通にもっている。すな
わち、インスタンス内科医１の名前属性は佐藤、免許番
号属性は83、患者名属性は患者Ａ、患者Ｂ、患者Ｃ、イ
ンスタンス内科医２の名前属性は鈴木、免許番号属性は
103、患者名属性は患者Ｗ、患者Ｘ、患者Ｙ、患者Ｚで
ある。

〔発明が解決しようとする課題〕

上述のようにクラスとインスタンスをプログラミング
の基本単位とするオブジェクト指向言語がソフトウエア
の生産性向上のために利用されつつあるが、従来のオブ
ジェクト指向言語では、例えばデータ変換の速度が遅く
大量のデータを効率的に扱えないという問題があり、オ
ブジェクト指向言語の利用によるソフトウエアの生産性
向上を実現するためにこの問題の解決が望まれている。

また、従来のオブジェクト指向システムでは、主記憶
上でのみオブジェクトの処理が行われていた。最近では
大規模知識の管理が研究されているが、それらの研究で
は自システム以外の他のデータベースの検索が問題とな
り、その検索結果が自システムのデータ表現形態に変換
されていた。

このような場合にはデータ変換に際して２重３重のコ
ピーが必要となり、コピーおよびデータ変換のコストが
嵩むという問題点があった。

さらに従来のシステムの中には他のデータベースに対
してデータベース言語を実行し、検索結果を自システム
の主記憶上で扱いやすい形式に変換するものもあった。
しかしながらこの場合にも可変長属性のデータは予めど
のくらいの領域をとってよいか不明のために、領域を確
認してからコピーする必要があった。そのため複数の可
変長属性がある場合はコピーを複数回実行する必要があ
り、やはり変換コストが嵩むという問題点があった。

本発明は、主記憶上のデータとファイル上でのデータ
をほぼ同じく形式として両者の間の変換効率を高めるこ
とを目的とする。

〔課題を解決するための手段〕

第１図は本発明の原理ブロック図である。同図におい
て大規模知識データベースシステムは電子計算機１およ
び外部記憶手段２から構成され、オブジェクト指向言語
を用いて大規模なデータを取扱うものである。電子計算
機１の内部にはオブジェクト管理手段３、データ管理手
段４、及びデータ変換手段５があり、データ管理手段４
は外部記憶手段２と接続されている。

オブジェクト管理手段３は主記憶および外部記憶手段
２上の全てのオブジェクトを管理するもので、クラスお
よびインスタンスの管理、プログラム管理などを行う。
データ管理手段４は外部記憶手段２、例えばディスク上
に格納されているオブジェクトを関係データベースの形
式で管理する。データ変換手段５は、例えばユーザから
のコマンドによって主記憶上で生成されたオブジェクト
を外部記憶手段２、例えばディスクに格納するに際し
て、主記憶上で絶対アドレスとポインタによって指示さ
れるデータを、外部記憶手段２上でオフセットを用いて
入れる構造で連続領域に格納される形式に変換する。逆
に外部記憶手段２に格納されている知識データを主記憶
上にコピーするために、オフセットを絶対アドレスに変
換する。

〔作用〕

本発明では主記憶上でのデータとファイル上でのデー
タをほぼ同じ形式にすることによりデータ変換、すなわ
ちマッピングの効率を高めている。ファイル上ではアク
セスの高速化のためにデータは連続領域に格納れるよう
に、可変長部分はオフセットで管理される。主記憶上で
はアクセス高速化のために、データは絶対アドレスとポ
インタによって管理される。すなわちオブジェクト管理
手段３上ではデータは絶対アドレスとポインタとによっ
て管理され、またデータ管理手段４上ではデータはオフ
セットによって管理され、かつ連続領域に格納される。
そこでデータ検索要求に応じてファイル上のデータを主
記憶上にコピーする際には、絶対アドレスとポインタと
を用いて領域の一括確保が行われ、データコピーとオフ
セットのアドレスへの変換が行われることになる。ま
た、オブジェクトのデータ外部記憶手段２への格納要求
に応じて、絶対アドレスのオフセットへの変換と主記憶
上のデータのファイル上へのコピーが実行される。

以上のように、本発明によれば、複数の可変長属性を
含むデータの場合にもコピーの回数を最小限におさえる
ことが可能になる。

〔実施例〕

第２図は本発明のアクセス方式を用いる大規模知識デ
ータベースシステムの全体構成ブロック図である。同図
において、システムは大型コンピュータ等の電子計算機
１、磁気ディスク装置、光ディスク装置等の外部記憶装
置６、および端末装置７から構成される。また、電子計
算機１は、CPU8を中心とし、CPU8は主記憶９および入力
制御部10、外部記憶制御部11と接続されている。端末装
置７はユーザによって操作され、オブジェクトの作成や
格納、検索、手続きの実行等のコマンドやデータを電子
計算機１に入力し、また電子計算機１からのオブジェク
ト情報や処理結果を受けてディスプレイ等に出力する。
また外部記憶装置６は、多数のオブジェクトを格納し知
識データベースを構成する。

また、入出力制御部10は端末装置７およびCPU8、主記
憶９と接続され、電子計算機１と端末装置７等の入出力
装置をつなぐ入出力インターフェイスの役目をする。ま
た、外部記憶制御部11は外部記憶装置６およびCPU8、主
記憶９と接続され主記憶９と外部記憶装置６間での知識
データの入出力を制御する。

一方、電子計算機１内の主記憶９には、知識データベ
ースの核となる知識ベースシステム（Jasmine）12が格
納され、そのプログラムに従ってCPU8が知識ベースに対
する各種処理を実行する。さらに主記憶９内には一部の
知識データ13が格納されるが、本発明ではこの知識デー
タ13と外部記憶装置６内に格納されたデータとの変換が
問題となる。

第３図は、知識ベースシステム（Jasmine）12の構成
図である。システムはモジュール化されており、主制御
機構14、解析機構15、最適化機構16、コード生成機構1
7、インタプリタ18、オブジェクト管理機構19、データ
管理機構20からなる。次に、各モジュールの役割を簡単
に説明する。

本実施例の知識ベースシステムは、ユーザにオブジェ
クト指向のプログラミング言語と会話型処理システムを
提供する。そして、主制御機構14はこれらオブジェクト
指向プログラムと会話型処理システムの実行制御を行
う。また解析機構15はオブジェクト指向プログラミング
言語で記述されたプログラミングの構文を解析し中間コ
ードを生成するとともに、会話型処理システムは会話型
処理により入力されるオブジェクト操作文を解析し、実
行可能な形にする。実行可能な形に変換されたオブジェ
クト操作文はインタプリタ18が実行する。

前述の解析機構15によって生成された中間コードは最
適化機構16に送られ最適化する。すなわち、最適化機構
16は例えばジョインの順序変換による高速化などの最適
化を施し、選択演算、結合演算などの演算ブロックを中
間情報として作成し、コード生成機構17に渡す。コード
生成機構17は、最適化機構16で最適化された中間コード
からＣソース・プログラムを生成する。生成されたＣソ
ース・プログラムは、電子計算機１の主記憶９に本知識
にベースシステムとは別に格納されているＣコンパイラ
によってコンパイルされ、知識ベースシステムの実行ラ
イブラリのリンクして実行可能ファイルを構成し、デバ
ッガがこれを実行する。

一方、オブジェクト管理機構19はオブジェクトの管理
を実行する。すなわち、クラスとインスタンスの管理
や、クラス−インスタンス間あるいは上位下位関係があ
るクラス間で属性や手続きを継承する遺伝の管理、プロ
グラムの管理を実行する。

データ管理機構20は、例えば拡張関係データベースを
管理するもので、非正規形のテーブルを管理でき、また
インデックス検索やハッシュジョイントという高速アク
セスメソッドを持っている。さらにタプル、すなわち関
係データベースの表における行ごとの処理を後述関数や
マッピング関数というコンパイルコードで与え、それを
実行できる高速かつ汎用的なデータベースシステムエン
ジンである。またオブジェクト管理機構19は例えばアク
ティブオブジェクトスペースを用いてデータ管理機構29
とのインターラクションが少なくなるようになってい
る。

本発明のデータアクセス方式はオブジェクト管理機構
19およびデータ管理機構29の内部にプログラムとして実
行されている。

本発明におけるデータ変換のアルゴリズムを説明する
前に、本発明における主記憶上およびデータベース（フ
ァイル）上での格納データの具体例を第４図に示す。同
図において、スズキフミオの好きな女優がサガラハルコ
とミナミノヨウコであり、またサガラハルコが付き合っ
ている友達がサイトウユキとアサカユウイであるという
ことが各人の年令とともにデータの内容として示され
る。（ａ）の主記憶上では、フミオの後のポインタがハ
ルコとヨウコの絶対アドレスを指示し、またハルコの後
のポインタがユキとユイの絶対アドレスを指示してい
る。

これに対してデータベース、すなわちファイル上では
データは連続領域に格納される。まず最初に全体のデー
タの行としてのタプル長が格納され、その後にフミオが
格納される。フミオの次のオフセットは図のように可変
長サイズを指示する。この可変長サイズはインナーテー
ブル、ここではスズキフミオが好きな女優がサガラハル
コとミナミノヨウコの２人であることを示すためのイン
ナーテーブルのサイズであり、そのテーブルの行数、す
なわちタプル数はこの場合は２となる。

タプル数の次に格納されているレングス（length）
は、サガラハルコのデータとサガラハルコが付き合って
いる友達がサイトウユキとアサカユウイであるというこ
とを示すデータを格納するための領域の長さであり、ハ
ルコの次に格納されているオフセットによりサイトウユ
キとアサカユイのデータが指示される。

そしてその後に格納されているNIL（レングス）によ
ってインナーテーブルの１つのタプルが終わったことが
示され、その後にミナミノヨウコのデータが格納され
る。フミオの年令“27"の下に格納されているオフセッ
トにより、フミオの姓スズキが指示され、ここまでが全
データであることになる。またハルコの年令“20"の次
のオフセットによりハルコの姓サガラが示され、さらに
ヨウコの年令“22"の次のオフセットによりヨウコの姓
ミナミノが示される。

第５図はデータ変換のアルゴリズムの概要である。同
図（ａ）はデータ検索のアルゴリズムの概要を示し、ス
テップ21でタプル識別子tidによりデータベース、すな
わちファイルの検索が行われ、検索結果がステップ22で
主記憶上にコピーされる。そしてステップ23でオフセッ
トが絶対アドレスに変換され、ステップ24で後述するア
クティブオブジェクトテーブルへの登録が行われる。第
５図（ｂ）はオブジェクト生成時、すなわち主記憶上に
形成されたオブジェクトをファイルに格納する場合のア
ルゴリズムの概要である。まずステップ25で絶対アドレ
スがオフセットに変換される。この時データが連続領域
にない場合には、このオフセットへの変換はデータの連
続領域への並べ換えと同時に行われる。そしてステップ
26で連続領域の情報がファイルへ書き込まれる。次のス
テップ27の処理は必要に応じて例外的に行われるもので
あり、ステップ25でデータが連続領域にすんで並んでい
る場合に、アクセスを高速にするためにオフセットをも
う一度絶対アドレスに戻すものである。すなわち主記憶
上のデータをそのままコピーする場合にはオフセットに
変換する必要はないが、コピーに際しては多くの領域が
必要であり、また時間がかかるために、ステップ25では
データが連続領域にあると否とにかかわらずオフセット
への変換が行われる。

第５図（ｃ）はデータ更新のアルゴリズムの概要であ
り、ステップ28で更新属性のみについて変換が行われ、
ステップ29で更新属性のみの更新が行われる。また像区
（ｄ）はデータ消去時のアルゴリズムであり、ステップ
30でタプル識別子tidを用いてデータ消去が行われる。

第６図は第５図のステップ24におけるアクティブオブ
ジェクトテーブルの実施例である。図においてデータベ
ースファイルの患者クラスから、オブジェクト識別子oi
dが3:36:1であるデータが主記憶上のアクティブオブジ
ェクトテーブルに格納される様子が示されている。

第７図は共通データ構造としてのデータ変換、すなわ
ちマッピングの補助情報の構造である。同図（ａ）はク
ラスのインスタンスのマッピング補助情報mapinfoのデ
ータ構造を示し、インスタンスのトータルサイズ、ポイ
ンタ属性を含む可変長属性の個数、データベース中のテ
ーブルについての情報、例えばシーケンシャルかインナ
ーかを示すrb情報へのポインタ、および各属性のマッピ
ング情報の配列からなる。同図（ｂ）はセル（mapinfoc
ell）の内容を示し、その属性のアドレス、実データへ
のポインタ、その属性のタイプ、すなわちポインタかイ
ンナーテーブルかあるいは可変長データかを示す整数、
およびインナーテーブルの場合にmapinfoへのポインタ
が格納される。

第８図はデータベースへの格納のための補助情報のデ
ータ構造である。データ管理機構20により行われるデー
タベース内のデータの更新はフィールドポインタアレー
（field pointer array）によって行なわれるために、
この情報はfpainfoで示され、第８図（ａ）のように可
変長データ属性の個数を示す整数、及び各属性のデータ
ベース補助情報の配列からなる。同図（ｂ）はセル（fp
ainfocpll）の内容であり、フィールド番号を示す整
数、相対アドレスを示す整数、タイプを示す文字、およ
び多値か否かを示す文字が格納される。

第９図は第５図のステップ25の詳細アルゴリズム、す
なわち絶対アドレスのオフセットへの変換アルゴリズム
である。同図（ａ）は全体のアルゴリズムであり、ステ
ップ31で可変長属性の更新の有無が判定され、ない場合
にはステップ32でデータのコピーを行うことなくオフセ
ットへの変換を行うトランスオフセットリストサブ（tr
ansoffsetlistsub）が実行される。また可変長属性の更
新がある場合には、ステップ33で可変長属性のコピーが
行われ、それを用いて絶対アドレスからオフセットへの
変換がトランスオフセットリストサブ（transoffsetlis
t sub）として行われる。

第９図（ｂ）はトランスオフセットサブのアルゴリズ
ムであり、ステップ34で第７図（ａ）のmapinfoにおけ
る可変長属性の数だけ次の処理が行われる。すなわちス
テップ34aでその属性の相対位置が求められ、ステップ3
4bでポインタかインナーテーブルかあるいは可変長デー
タかのタイプが調べられ、ポインタであればオフセット
の値としてNULLがセットされ、可変長データであればサ
イズが更新され先頭からのオフセットが求められ、その
登録が行われる。またもしインナーテーブルがあれば各
タプルについてトランスオフセットサブが呼ばれる。

第９図（ｃ）はトランスオフセットリストサブのアル
ゴリズムである。まずステップ35で第７図（ａ）のfapi
nfo可変長属性の数だけスキャンが行われ、データの総
サイズが求められる。その際可変長データのアドレスの
登録が行われる。またインナーテーブルの場合には、そ
のインナーテーブルの各タプルについてトランスオフセ
ットリストサブが呼ばれる。次にステップ36で領域の確
保と固定長領域のみのコピーが行われ、ステップ37で可
変長属性の個数だけ次の処理が行われる。すなわステッ
プ37aでその属性データの相対位置が求められ、37bでタ
イプが調べられる。タイプがポインタの場合にはオフセ
ット値としてNULLがセットされ、可変長データであれば
その長さだけデータ領域のコピーが行われる。

第10図は第５図のステップ23、または27のオフセット
の絶対アドレスへの変換のアルゴリズムである。同図
（ａ）は全体のアルゴリズムであり、まずステップ38で
可変長属性の更新があるか否かが判定される。更新がな
い場合には可変長データについてオフセットをアドレス
に変換する必要があるので、ステップ40で連続領域のオ
フセットの絶対アドレスへの変換処理がトランスアドレ
ス−ｓ（transaddr−ｓ）として実行され、また更新が
ある場合にはステップ39で固定長領域がコピーされて復
元される。同図（ｂ）はトランスアドレス−ｓのアルゴ
リズムである。この処理では第７図（ａ）のmapinfoに
おける可変長属性の個数だけ以下の処理が行われる。す
なわちステップ41aでその属性について相対位置が求め
られ、ステップ41bでその属性のタイプが調べられる。
そして可変長データの場合にはオフセットが絶対アドレ
スに変換され、インナーテーブルの場合には各タプルに
ついてトランスアドレス−ｓが呼ばれ、先頭と末尾のア
ドレスが埋められる。

第11図は属性の更新処理におけるアルゴリズムであ
る。このアルゴリズム、アップデータfpa（update fp
a）においてはステップ42で第８図（ａ）のデータベー
ス補助情報としてのfpainfoの属性の数だけ以下の処理
が行われる。すなわちステップ42aでその属性のタイプ
が調べられ、もし可変長データであれば絶対アドレスが
fpaに登録される。またインナーテーブルの場合には各
タプルについてアップデータfpaが呼ばれる。そしてス
テップ42bでfpaに基づいて属性の更新が行われる。

なお、上述の実施例では、フィルタ上でのデータを主
記憶上に持ってくるにあたってはオフセットを絶対アド
レスに変換するものとしたが、このオフセットのアドレ
スへの変換を行わずにファイル上のデータを利用するこ
とも可能である。この場合にはマッピングのコストがよ
り低減でき、また主記憶上のデータにもファイル上のデ
ータを対象とする関数が適用できることになるが、主記
憶上でのアクセスもオフセットによるため、個々のアク
セスは遅くなる。

〔発明の効果〕

以上詳細に説明したように、本発明によれば、絶対ア
ドレスとオフセットの変換のみで主記憶上のデータとフ
ァイル上のデータを相互に変換することが可能になり、
オブジェクトのデータをファイルから主記憶へ持ってき
たり、主記憶からファイルへ書き込む時の変換に要する
処理を極めて少なくすることができ、システムの高速化
に寄与するところが大きい。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明のアクセス方式を用いる大規模知識デー
タベースシステムの全体構成を示すブロック図、 第３図は知識ベースシステム（Jasmine）の構成を示す
ブロック図、 第４図（ａ）、（ｂ）は主記憶上およびファイル上での
格納データの具体例を示す図、 第５図（ａ）〜（ｄ）はデータ変換のアルゴリズムの概
要を示す図、 第６図はアクティブオブジェクトテーブルの実施例を示
す図、 第７図（ａ）、（ｂ）はマッピングの補助情報の構造を
示す図、 第８図（ａ）、（ｂ）はデータベースへの格納のための
補助情報の構造を示す図、 第９図（ａ）〜（ｃ）は絶対アドレスのオフセットへの
変換アルゴリズムの実施例を示す図、 第10図（ａ）、（ｂ）はオフセットの絶対アドレスへの
変換アルゴリズムの実施例を示す図、 第11図は属性の更新アルゴリズムの実施例を示す図、 第12図はクラス−インスタンスの説明図である。 １……電子計算機、 ６……外部記憶装置、 ８……CPU、 ９……主記憶、 12……知識ベースシステム（jasmine）、 13……知識データ、 19……オブジェクト管理機構、 20……データ管理機構．

フロントページの続き (56)参考文献 特開 昭63−67638（ＪＰ，Ａ) 特開 昭63−136147（ＪＰ，Ａ) 特開 昭63−158643（ＪＰ，Ａ) 特開 平１−159750（ＪＰ，Ａ) 鈴木文雄，他，”オブジェクト指向型 マルチメディア知識ベースＪａｓｍｉｎ ｅの実現”情報処理学会研究報告，情報 処理学会，平成元年７月20日，ＶＯＬ. 89，ＮＯ．63（ＤＢＳ−72），Ｐ．57〜 Ｐ．64 鈴木文雄，他，”オブジェクト指向型 マルチメディア知識ベースＪａｓｍｉｎ ｅのプログラムインターフェースの実現 について”，情報処理学会第37回（昭和 63年後期）全国大会講演論文集，情報処 理学会，昭和63年10月，ＶＯＬ．37ｔ ｈ，ＮＯ．１，Ｐ．405〜Ｐ．406 (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 12/00 G06F 15/40

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】電子計算機（１）および外部記憶手段
   （２）から成り、オブジェクト指向言語を用いて大規模
   なデータを取扱う知識データベースシステムにおいて、 主記憶および外部記憶手段（２）上の全てのオブジェク
   トを管理するオブジェクト管理手段（３）と、 前記外部記憶手段（２）上に格納されているオブジェク
   トを関係データベースの形式で管理するデータ管理手段
   （４）と、 主記憶上で絶対アドレスとポインタとによって指示され
   るデータと、前記外部記憶手段（２）上でオフセットを
   用いて入れる構造で連続領域に格納されるデータとを、
   前記オブジェクト管理手段（３）とデータ管理手段
   （４）との間で相互に変換するデータ変換手段（５）を
   有することを特徴とする大規模知識データベースシステ
   ムにおけるデータアクセス方式。