【発明の詳細な説明】〔技術分野〕本発明はデータベースの記憶及び検索に係る。
〔先行技術〕普通の情報処理システムにおいては、−組の情報が「フ
ァイム」として処理されることがある。
ここで「ファイル」とは、同じ型の情報を含む複数のレ
コードの集まりを意味する。各レコードは情報単位を表
わす幾つかのフィールドに分けられ、選択や分類などの
オペレーションはフィールド・データに基づいて行なわ
れる。複数のファイルの集まりが一般に「データベース
」と呼ばれるもので６る。特定の属性フィールドに従っ
てデータベースからレコードを選択するプロセスは「デ
ータベース検索」と呼ばれる。
データベース検索システムの笑用性は、メモリに格納で
きるレコード数及びレコードのアクセス方式によって左
右される。従来のデータベース検索システムでは、所与
の属性フィールドで一致が明示された後でのみレコード
を検索し得る順次検索が一般的であった。検索引数とし
て使用可能な属性の数はシステムの仕様に応じて制限を
受ける。
データベースの検索にもつと融通性を持たせるというこ
とで考え出されたのが関係アクセス（リレーショナル・
アクセス）である。それによれば、レコードを構成して
いる鵠性フィールドの任意のものを探索することによっ
て、レコードを暗黙的に検索することができる。例えば
、順次アクセスでは「キーワード航空学＃を待ったすべ
ての刊行物ｔ リストせよ」という照会文が使用される
が、関係アクセスではデータベースの照会範囲を拡げＩ
ることかでき、［キーワード航空学＃を待った刊行物の
うち、５０ドル以上で且つ次の２ケ月の間に管理職のと
ころに受取られるはずのもの’ｋ リストせよ」という
照会文を使用できる。このように、関係アクセスの照会
文には照会乃至は検索のための複数の条件が含まれてお
り、検索されたレコードはこれらの条件をすべて満たし
ている。これに対し、順次アクセスによって複数の条件
を満たすレコードを検索するためには、例えば上述の順
次アクセス照会文によって検索されたレコードを更に処
理する必要がある。
関係アクセス方式が順次アクセス方式より優れているこ
とは明らかであるが、これまで余り使用されていなかっ
たのは、大容量のメモＩＪ ’に必要とし、処理時間が
長く、且つインデックス方式が複雑なためである。
〔本発明の概要〕本発明の目的は、データベースを記憶するメモリの容量
が少なくてすみ且つ処理時間が短縮されたデータベース
処理方式を提供することにある。
本発明においては、データベースの各レコードからサマ
リ・リスト及びインデックス・テーブルと呼ばれるもの
が作成される。サマリ・リストは一意的なデータ要素（
フィールド）のみから成っている。即ち、サマリ・リス
トラ構成しているデータ要素はすべて異なっている。イ
ンデックス・テーブルはサマリ・リストの作成に使用さ
れたデータベースの同形写像であって、データ要素の代
りに、元のデータペ・−スに含まれていたすべてのデー
タ要素がサマリ・リスト中のどこに位置しているかを示
すポインタを保持する。重複するデータ要素が除かれて
いるサマリ・リスト、及びデータ要素よりも簡単なポイ
ンタのみを保持するインデックス・テーブルを使用すれ
ば、元のデータベースをそのまま記憶する場合に比べて
メモリの容′ｉｔをかなり節約することができ、しかも
本発明によって実現されるデルタベース・ファイルは実
質的に転置ファイル（インバーテツド・ファイル）であ
る。インデックス・テーブルのポインタは、関係アクセ
ス方式の照会を短時間で処理するのに有用であり、しか
もそのときのメモリの割振りは最小限ですむ。
〔実施例の説明〕以下、第１図に示される対話式テキスト処理システムで
本発明を実施した場合について説明する。
第１図のテキスト処璋システムは、キーボード１０、マ
イクロプロセッサ１１、表示リフレッシュ・バッファ１
２、表示装置１４、プリンタ１５、ディスクの如き補助
の直接アクセス記憶装置（ＤＡＳＤ）１６及びシステム
の各二二ッｉ同期的に作動させるためのクロック信号ｃ
１発生するクロック装置１７から成っている。
キーボード１０は、文字キー、数字キー、句読点キーな
どの通常のグラフィック・シンボル・キーと、キャリッ
ジ復帰キー、タブ・キー、インデックス・キーなどのテ
キスト様式キーと、７ステムに特殊制御指令を与えるた
めの制御キーとを備えている。制御キーはカーソル移動
、キーボード１０のモード設定などに使用される。キー
ボード１０は母線２０によってマイクロプロセッサ１１
に接続される。
マイクロプロセッサ１１は、第２図に示したように、入
力ポート２１、出力ポート２２、ランダム・アクセス・
メモリ（ＲＡＭ）２５及び実行ユニット２４から成って
おり、キーボード１０の他に、表示リフレッシュ・バッ
ファ１２、プリンタ１５及びＤＡＳＤ’１６にも接続さ
れる。マイクロ□ プロセッサ１１はインテル８０８６
の如き市販のものでよい。
ＲＡＭ２３は命令及びデータを記憶するもので、第５図
に示したように、幾つかの特殊領域を含んでいる。例え
ば、キーボルド１０から人力されたデータは、入力ポー
ト２１を介してバイト形式でＲＡＭ２３のキーストロー
ク待ち行列領域２６に書込まれる。データ會表示装置１
４で表示する場合には、キーストローク待ち行列領域２
６にあるデータがまずテキスト・バッファ領域２７に移
され、次いでマイクロプロセッサ１１の出力ボート２２
１１−して表示リフレッシュ・バッファ１２に移される
。周知の如く、マイクロプロセッサ１１で一連の移動命
令を実行すれば、このようなデータ移動を行なえる。
第１図及び第３図では、表示リフレッシュ・バッファ１
２及び表示１ｉｉ１ｉ１４が別々に示されているが、実
際には、表示リフレッシュ・バッファ１２は表示装置１
４に内蔵されている。
ＲＡＭ２３に記憶されているデータはプリンタ１５及び
ＤＡＳＤ１６にも供給され得る。ＲＡＭ２３からプリン
タ１５又はＤＡＳＤ１６へデータを転送するための指令
は、操作員によってキーボード１０からマイクロプロセ
ッサ１１に与えられる。プリンタ１５はデータを印刷す
るだけであるＩＥ、ＤＡＳＤ１６はマイクロプロセッサ
１１によるランダム・アクセスが可能である。ＤＡＳＤ
Ｉ６から読取られた空間的に関係するデータは、符号化
された形でＲＡＭ２３の表示データ領域２８に１込１れ
る。ＲＡＭ２３の残りの領域は表示様式バッファ領域２
９で、本発明に従って空間的に関係するデータを復号さ
れた形で取扱うときに使用される。
第４図は表示装置１４のスクリーンを示したもので、垂
直方向に２５文字、水平方向に８０文字表示できるよう
になっている。文字はマトリックス状に配列されたドツ
ト（ベルとも言う）によって表示される。第４図の例で
は、ドツト・マトリックス５２は１０行６列のドツトか
ら成っている。
なお、このドツト・マトリックス３２は、スクリーン、
の２５番目の行Ｒ２４と７５番目の列Ｃ７２との交点に
あるドツト・マトリックスを拡大して示したものである
。表示装置１４は一般にマイクロプロセッサ１１の助け
を借りることなく、表示リフレッシュ・バッファ１２に
あるデータをドツト・マトリックスでの表示に適した形
に変換する。
表示装置１４に関しては、マイクロプロセッサ１１はア
ドレスを供給し且つ表示すべきデータ全表示リフレッシ
ュ・バッファ１２ｖＣロードするタケである。
ＤＡＳＤ１６においては、データがＲＡＭ２３の表示デ
ータ領域２８から転送されてきた場合にはバイトからビ
ットへの変換（並直列変換）が行なわれ、データを表示
データ領域２８に書込む場合にはビットからバイトへの
変換（並直列変換）が行なわれる。
第３図には示していないが、ＲＡＭ２３は以上の如き種
々の機能を実現させるためのプログラムも記憶している
。これらのプログラムは、キーボード１０からの入力や
システム内部で発生された割込み信号によって呼出され
る。
次に、説明の都合上、表１の如き簡単なデー）ベース全
仮定する。
ｑ−Ｃ％Ｊ ド〕 寸Ｓ ヰ
琳 球表１のデータベースは人事ファイルであって、４個のレ
コード＃１〜＃４から成っている。各レコードは、「名
前」フィールド、「勤務地」フィールド、「上司」フィ
ールド、「職位」フィールド及び「給与」フィールドに
分けられる。各フィールドには、必要な情報？記憶する
ための一定数のバイトが割当てられている。これらのバ
イト数はフィールド毎に異なっていてもよい。例えば、
名前フィールドが２０バイトで、勤務地フィールドが１
０バイトでもよい。ただし、これらのバイト数はデータ
ベースのすべてのレコードにおいて同じである。
実際のデータベースは、人事ファイル、在庫ファイル、
注文ファイルなどの多数のファイルから成っており、各
ファイルのレコード数ＩＥ１０００を越え、各レコード
のフィールド数が１０を越えることもまれではない。従
来は、このように大きなデータベースは、大容量のラン
ダム・アクセス・メモＩＪ ’に備えた大型の情報処理
システムでのみ処理されていた。
本発明は、大容量のランダム・アクセス・メモリの必要
性をなくすために、言い換えれば小型のシステムでもデ
ータベースを処理できるようにするために、独特のやり
方でデータベース情報を短縮し符号化する。次に第５図
を参照しながら、データベース情報の短縮及び符号化に
ついて説明する。
最初のブロック６０では、表１の如き短縮されるべきデ
ータベースがシステムに入力される。例えば、データベ
ースはＤＡＳＤ１６に記憶されてもよく、筐た遠隔のシ
ステムから通信回線を介して伝送されてきたものであっ
てもよい。
以下のブロック６１〜６５は１つの大きなループ全構成
しており、その繰返しの度に、ブロック６０で入力され
たデータベースの各レコードを１つずつ処理する。まず
ブロック６１では、データベースにおいて次に処理すべ
きレコードがアクセスされる。表１の例では、例えば１
回目の繰返しのときには１番上のレコードがアクセスさ
れ、以下繰返しの度に各レコードが上から順番に１つず
つアクセスされる。ブロック６２では、データベースの
終りに達したか否か、即ちブロック６１でレコード７５
ゾクセスされなかつｆｃ（データベースの終り）か否か
が調べられる。まだ終りに達していなければ、ブロック
６３〜６５から成る小ループに入る。この小ループでは
、ブロック６１でアクセスされたレコードの各フィール
ドが繰返しの度に１つずつ取出されて、ＲＡＭ２３の作
業域に保管される。
フィールドの取出し及び保管はブロック６３で行なわれ
る。ブロック６４では次のフィールドが指示され、そし
てブロック６５では、保管すべきフィールドがまだ残っ
ているか否かが調べられる。
もし残っていればブロック６５に戻って、前のブロック
６４で指示されていた次のフィールドが取出され、作業
域に保管される。ブロック６３〜６５のループは、ブロ
ック６１でアクセスされたレコードの全フィールドの内
容が保管されてしまうまで続キ、次いでブロック６１に
戻って次のレコードがアクセスされる。
データベースの最後のレコードの処理が終ると、ブロッ
ク６２からブロック６６に分岐し、作業域に保管されて
いたフィールドの情報が「サマリ・リスト」と呼ばれる
一覧表の形に分類される。サマリ・リストは下記の表２
に示したように、全レコードの全フィールドの情報全重
複することなく所定の順序、例えばアルファベット順及
び数字順に並べたものである。
Ｉ ＡＣＣＯＵＮＴＡＮＴ”２ ＨＡＲＲＩＳＯＮ％Ｌ３
ＪＯＮＥＳ％ＢＬ４ ＮＥＷ ＹＯＲＫ５ ＰＲＥＳＩＤＥＮＴ６ ｓＡＬＥｓＭＡＮ７ ８ＭＩＴＨ，Ｊ Ｃ８ＴＨＯＭＡｓ％ｗｇ９ ＷＡＳＨＩＮＧＴＯＮｌｏ ２７０００．００１１
３８０００．００１２
４００００．０（Ｉ１１３ ５３００
０．００情報を表２のように分類することを「サマリ・
ソート」と言う。表１のデータベースは全部で２０個の
フィールドから成っているが、サマリ・ソートによって
作成されたサマリ・リストは１５個のフィールド情報し
か含んでいない。これは、重複するフィールド情報（例
えばＷＡＳＨＩＮＧＴＯＮ）が１つにまとめられている
ためである。従って、サマリ・ソーｉｆ利用すれば、デ
ータベースを記憶するのに必要な記憶容積全節約できる
。
勿論、節約の度合はフィールド情報がどれ程重複してい
るかによって異なる。
第５図に戻って、サマリ・リストの編集が終ると、ブロ
ック６７で同じデータベースが再び指示嘔れる。次のブ
ロック６８及び６９は前のブロック６１及び６２と同じ
である。データベースの終りに達していなければブロッ
ク６９からブロック７０に進み、アクセスされたレコー
ドから次のフィールドが取出される。ブロック７１では
、取出されたフィールドとサマリ・リストの内容とを比
較することによって、該フィールドの情報がサマリ・リ
ストのどこに位置しているかカ調べられる。
例えば、表１のデータベースにおける！初のレコードの
最初のフィールド（名前フィールド）にある情報ｒＪＯ
ＮＥｓ％Ｂ ＬＪは、表２のサマリ・リストにおいて
は３番目の項目になっている。
サマリ・リストにおけるフィールドの位置は相対的なも
のである。ブロック７２では、ブロック７１で調べられ
た位ｇｔヲ示すコードが、下記の表５の如きインデック
ス・テーブルを構成するインデックス・レコードの対応
するフィールド中に保管される。
表３（インデックス・テーブル）名前勤務地 上司 職位 給与フィールド情報ｒＪＯＮＥｓ、Ｂ ＬＪの場合は、位
置コード「３」が最初のインデックス・レコード＃１の
最初のフィールド（名前）に保管されることになる。表
３の各インデックス・レコード＃１〜＃４は、ｆｆ１の
各データベース・レコード＃１〜＃４の同形写像になっ
ている。ただし、 ・インデックス・レコードのフィ
ールドは、データベース・レコードのフィールド情報そ
のものではなく、表２のサマリ・リストにおけるフィー
ルド情報の位置を表わすコードを営むだけである。従つ
て、サマリ・リストの項目数が例えば６４０００であれ
ば、各々の位置コード金保管するためのフィールド長は
２バイトでよい。その場合、インデックス・レコードが
１０個のフィールドから成っていれば、インデックス・
レコード長は２０バイトになり、これは同じ＜１０個の
フィールドから成るデータベース・レコードの普通の長
さく例えば８０バイト）に比べてかなり短いから、記憶
容量の節約になる。
ブロック７３では、ブロック６８でアクセスされたレコ
ードに未処理のフィールドが残っているか否かが調べら
れる。もし残っていればブロック７０に戻り、さもなけ
ればブロック７４に進んで、インデックス・レコード全
インデックス・テ・−プルに書込んだ後、次のレコード
を処理するためにブロック６８に戻る。データベースの
最後のレコードが処理されてしまうと、ブロック６９が
らブロック７５への分岐が行なわれ、サマリ・リスト及
びインデックス・テーブル７’）ＥＤＡＳＤ１６に保管
される。かくして、短縮されたデータベースの記憶が終
了する。
最後に第６図全参照しながら、短縮されたデータベース
から情報を検索するためのプロセスについて説明する。
第１図のシステムでデータベース検索動作を開始する場
合、操作員はキーボード１ｏがら照会文を入力する。周
知のように、照会文はデータベースレコードのフィール
ドに関係するキーワード（複数でもよい）を含んでいる
。データベース検索システムは照会文中のキーワードを
正しく識別する必要があるから、各々のキーワードは例
えば引用符によって他から区別される。
最初のブロック８０では、入力キーワード及びサマリ・
リスＨ）ｉ処理可能な状態におかれる。ブロック８１で
は、入力キーワードとサマリ・リストが比較され、サマ
リ・リスト中で入力キーワードに相当する項目が見つか
ると、次のブロック８２で、その位置を表わす値が人力
キーワードの位置コードとして保管される。ブロック８
３では、処理されるべき入力キーワードが残っているか
否かが調べられる。もし残っていればブロック８１に戻
って上述のプロセス全繰返し、さもなければ次のブロッ
ク８４に進む。最後の入力キーワードの位置コードが保
管されてしまうと、ブロック８４で、１ずインデックス
・テーブルが指示され、その複数の列のうち各りの入力
キーワードに対応する列がアクセスされる。
表５のインデックス・テーブルは複数の行（インデック
ス・レコード）及び列（フィールド）から成るマトリッ
クスの形をしてい冬。照会文への応答に必要なフィール
ドだけ奮例えばＤＡＳＤ１６からＲＡＭ２５に持ってく
れば、このようなマトリックスをより効率よく処理する
ことができる。
次のブロック８５〜８７から成るループは、ブロック８
２で保管されていた各入力キーワードの位置コードと、
ブロック８４でアクセスされた各列のフィールドとを順
次に比較する。まずブロック８５で、各列のフィールド
が順次に指示され、ブロック８６で、対応する入力キー
ワードの位置コードと比較される。ブロック８７では、
これらが一致しているか否かが調べられる。もし不一致
であればブロック８５に戻って、各列の次のフィールド
即ち１つ下のフィールドとの比較が行なわれる。ブロッ
ク８７で一致が検出されるとブロック８８に進み、一致
したすべてのフィールドが出力レコード・テーブルに保
管される。ブロック８９では、各々の列に比較されるべ
きフィールドが残っているか否かが調べられ、もし残っ
ていれば、ブロック８５〜８７のループが繰返される。
ブロック８４でアクセスされた列のすべてのフィールド
が比較されてしまうとブロック９０に進み、最終処理の
ために出力レコード・テーブル及びサマリ・リストが指
示される。出力レコード・テーブルはサマリ・リストに
対する１以上のアドレス・ポインタを含んでいる。最後
のブロック９１では、出力レコード・テーブルによって
指定された項目がサマリ・リストから読取られ、それに
よって出力ファイル用のデータ・レコードが作成□され
る。ブロック９１の処理が終了すると、操作員は出力フ
ァイル全表示装置１４で表示したり、プリンタ１５で印
刷したりすることができる。その際、出力ファイル用の
データ・レコードは、ＲＡＭ２３の表示データ領域２８
から表示様式バッファ２９へ移され、次いで表示りフレ
ッシュ・バッファ１２又はプリンタ１５の方へ転送され
る。
【図面の簡単な説明】第１図は本発明を実施し得るシステムの一例を示すブロ
ック図、第２図はマイクロプロセッサ１１の構成を示す
ブロック図、第３図はＲＡＭ２３の各種領域を示すブロ
ック図、第４図は表示装置１４のスクリーンを示すブロ
ック図、第５図はデータベースを記憶するときの動作を
示す流れ図、第６図はデータベースを検索するときの動
作を示す流れ図である。出願人 インターナショナル・ビジネス・マシーノズ
・コゴｔ’Ｌ−づタン代理人 弁理士 頓 宮
孝 −（外１名）−笹