JPH0623980B2 - 情報記憶・操作装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は情報ベース内の記憶情報の効率的な検索、操作
および解析に関するものである。

〔発明の背景〕

データ処理の分野においては、例えば、あるフィールド
または属性のいくつかの値を有する情報ベース内のすべ
ての情報エレメントの探索のように、質問にもとづいて
情報ベースに記憶された情報エレメントの検索を行うこ
とを必要とすることが多い。データ処理システムは、情
報ベースから所望の情報を検索するため、一般的に質問
の仕様を必要とする。したがって、特定の属性（または
フィールド）の数字的に正しい値を入力した後、これを
情報ベース内の情報エレメントの対応する属性（または
フィールド）値と比較し、正しく対応するエレメントを
選定する。これは、例えば並べ替えのようなデータ操作
についても当てはまる。この場合には、１またはそれ以
上の属性の順序づけの規則（最初に最も高い属性値、つ
いでその次に高い属性値……）にもとづいて情報エレメ
ントを出力することが要求される。このような選択的ア
クセスによれば、情報ベースの中から質問の仕様に合っ
たエレメントのみを選んで扱うシステムが可能になる。

このような選択的質問仕様は２つの広いクラスに分類さ
れる。その第１は情報ベースの各エレメントが質問の仕
様に合致していることを見出すため、それらを徹底的に
反復テストすることである。また、その第２は選定され
た（エレメントのアドレスに対応している）属性に対し
て重複して付した値、即ち、種々の値とそれに対応して
いる仕様に合致した情報エレメントに迅速にアクセスで
きるように作られた値（インデックス）を、すべてのエ
レメントについて記憶させることである。このような特
殊データ構造の例としては、配列したリスト、ツリー、
ハッシュしたインデックスおよびその僅かが商用されて
いる複数の他の変形が含まれる。

適用可能なこの種データ構造またはインデックスは繰返
し探索法に比しかなり早いアクセスを与えるが、一方次
のような制限を蒙る。

(1)情報ベースの属性への参照のために必要なインデッ
クスファイルのサイズが大となり、特に、情報エレメン
トが爾後の検索のためインデックスを付した多数の属性
を含む場合はそうである。ある場合には、インデックス
ファイルに対する記憶要求が情報ベースそれ自体に対す
る記憶要求に等しいかそれより大きいこともありうる。

(2)インデックスはそのためにインデックスが設計され
た特定の属性または属性の組合せに対してのみしか有効
なアクセスを与えない。すなわち、しばしば部分的で不
正確な仕様にもとづいた多数の属性の種々の組合せ間に
広範な論理的関係を含むような商業実務において遭遇す
る融通性のある間合せに対してそれらは有効でなく、あ
るいは適用不可能である。

したがって、これらの方法は、データ処理システムの最
低の要求は満足するが、複雑な多元属性仕様の有効な処
理への総体的アプローチに関する増大する臨界的要求に
対しては適当というには程遠い。

また、部分的キーアクセス、明示レンジの時々の使用な
らびに“平易英語”による仕様の使用を許容しようとこ
ころみたある最近のシステムのような特定例もあるが、
この種システムは、このような入力を正しいキー構造に
翻訳またはクロスリレート（(cross-relate）するシス
テムの論理の能力に頼っている。したがって、部分的キ
ーは、部分的入力の初期キャラクタが完全なキーの初期
キャラクタに完全に整合する場合のみ、（多数の不正確
なレコードのオペレータ検査後）ツリーインデックス内
のレコードに置かれることになる。同じような制限が他
のすべてのこのような方法に当てはまり、性能（パーフ
ォーマンス）は仕様の厳密さが減るにしたがって、有効
性が低くなり、不正確さが増す。また、これは、通常あ
いまいさを明白にするための付加的入力の助けを借り
て、不完全かつ不正確な入力を最も明確で最も高い可能
性を有する出力に翻訳するためにきわめて複雑な（した
がって計算的に限度のある）解析論理、ルール論理およ
び類別論理を使用する“人口知能”システムにおける最
近の開発に関しても当てはまる。これに反して、意図的
に正確度の低いデータ表示を使用する従来の技術におい
ては、正確なデータ値の操作の効率性および妥当性を高
めようとする一般的アプローチが見られない。

本発明の目的はこのように一般化したシステムを提供し
ようとするものである。

〔発明の概要〕

本発明は情報ベースの属性の符号化マップ（以下トポロ
ジカルマップという。）の処理の容易さと独得なコンパ
クトさにもとづいて記憶情報ベース内の情報を操作する
方法および手段を提供するものである。この場合、各マ
ップは属性の値の予め定められたレンジに対応するコン
パクトな記号（シンボル）を含む。また、各エレメント
の属性の値を包含するレンジ用の記号を各エレメントに
対応して該マップに記憶し、情報エレメントおよびトポ
ロジカルマップを情報記憶装置内に記憶する。

質問は、質問の仕様にもとづいて関係するトポロジカル
マップにアクセスし、該マップから質問の仕様に合致し
た情報ベース内の情報エレメントを識別することにより
処理する。一つの属性に関する簡単な質問は、その属性
用の適切なトポロジカルマップにアクセスすることによ
り解かれ、一方、多くの属性を含むより複雑な質問は、
質問の論理オペレータにしたがって、質問内に含まれる
属性用のトポロジカルマップを組合せることにより解か
れる。

質問の仕様内の値のレンジあるいは属性値をその属性用
のトポロジカルマップ内の記号により表わされる所定の
レンジと比較する。したがって、情報ベースの情報エレ
メントが、トポロジカルマップ内のレンジ記号で示され
ているので、その属性値に対してマップされたレンジが
明らかに仕様の値または値のレンジの外側にあって質問
の仕様に合致する可能性のない情報ベースの情報エレメ
ントについては、単に、マップに問合わせるだけで早急
に考慮の対象外におくことができる。同じように、その
属性値に対してマップされたレンジが完全に質問に特記
されたレンジ内にあり、確実に質問の仕様に合致してい
ることが分るような情報ベース内の情報エレメントを迅
速に識別することができる。マップ内で使用されるシン
ボルは、正しい値よりはむしろ値のレンジを表示するの
で、質問の解は、質問の仕様に合致している“かも知れ
ない”が、単にマップに問合わせるだけでは確実に決め
られないようなある情報エレメントを見出すことである
といえる。したがって、質問の仕様に合致している“か
も知れない”情報エレメントのみを検査し、それらが質
問の仕様に合致しているかどうかを決定する必要がある
だけである。

このアプローチは、正確な値の効率的な操作のほか、同
じ有効性と効率をもって近似の値または定性的な値を同
時に取扱い、かつ相関連づけることを可能にする。した
がって、衣服の色に対応する属性は黄色、緑色、青色、
褐色、赤色等として決められたレンジを有し、任意の色
の変形あるいはこれらの基本カラーから導かれる専門用
語をそのカレーレンジ（黄褐色ないし褐色、ばら色から
赤色等）に属するものとしてコード化する。衣服ストア
のデータベース内の標準的レコードは、例えば、原価、
売価、手持ち数、販売高等のような定量的データのほ
か、衣服の形式、色、スタイル、ブランド等を含む。本
発明は双方の形式のデータを首尾一貫して取扱い、“過
去３年の秋季および夏期の場合の赤色および黒色の婦人
服の長身者用サイズおよび短身者用サイズの関連販売品
はなにか”というような質問に正しく返答することがで
きる。

このような広範な仕様は、このようにコード化したトポ
ロジカルマップのコンパクト性により１つまたは２つだ
けのキーを有する従来技術のキー構造の場合より少ない
記憶装置を用いて多数の属性をマップすることができる
ので、汎用コンピュータを使用して従来技術の場合より
段違いに速い速度で、完全な正確さと、特化性をもって
処理を行うことができる。したがって、１つの質問に対
して適合するすべてのマップを迅速に高速半導体メモリ
内に同時にロードすることができ、プロセッサが評価す
べきキーデータが大幅に減少 するだけでなく、そのコ
ンパクトなコードを簡単な高速論理で比較することがで
き、かつ、ディスク入出力転送速度より段違いに速い半
導体の速度でこのキーデータにアクセスすることができ
る。これらの処理速度の増加は、付加的というよりむし
ろ混合的であり、したがって正味の改良はこれらの効果
の和より大である。

情報ベースのエレメントを特徴づけるために値のレンジ
を使用することは、一見大幅にその特化性を減少させ、
したがってシステムの効率を低下させるように思われる
が、きわめて多数の質問を含む２つまたはそれ以上のレ
ンジおよび属性に関する質問の場合は、不確実なエレメ
ントの数はさして問題とならない。このアプローチによ
り導かれる可能性のある不確実性は、不確実なレコード
を直接チェックし、マップの通常処理行程内で識別する
ことにより容易に取除くことができる。したがって、こ
のようなチェックにより生ずる効率の減少は最初にレコ
ードを隔離する速度の格段の改良に比べればきわめて小
さいもので問題とはならない。

一次キーを介して特定レコードに直接アクセスすること
に関しては、現行の技術のスピードが既に人間の理解の
限界に到達しており、したがって、本発明は従来技術に
比し顕著な速度の改善を与えるものではない。しかしな
がら、本発明は直接キーファイルの記憶スペースの低減
という点に関して大きな改善を与えており、種々の二次
キーによる直接アクセスに要するスピードに大幅な改良
を与えることができる。また、このことは高速メモリへ
の完全なコンパクトコードマップの記憶の可能性にも関
係する。

本発明の原理に表面上類似した従来技術もいくつかあ
り、これらは、この分野における先導的権威者のひとり
として広く認められているドナルド・イー・クヌス（Do
nald E.Knuth）によるコンピュータプログラミング技
術、分類と探索、第３巻、“２次キー上での検索”（"R
etrieval on Secondary Keys" in Volume 3/Sorting an
d Searching/The Art of Computer Programming）のセ
クションに例示されている。このセクションの前置きと
概要の双方には、複雑な多元属性質問に対処することに
関する現行技術の制限および困難さが指摘されており、
利用範囲の狭い高度に専門化された技術として含まれる
例が説明されている。

クヌス（Knuth）は同書の554ページに、“直交レンジク
エリー”（２つの垂直ディメンション）（"orthogonal
range query"(two perpendicular dimensions）の例を
与えており、この場合、２つのディメンションの積（す
なわち領域（エリア）または範囲（ドメイン））と同等
の組合わされたクラスを決める限られた目的のためにの
み、２つのディメンションをレンジに区分することを提
案している。また、次に、これらの積クラスに対応する
レコードナンバーの逆リストを作成し、対応する各リス
トにそのディメンションが積クラスにより包囲されるど
のレコードをも含ませるようにすることを提案してお
り、最後に、各ディメンションに対する上下限（すなわ
ち、ドメイン内のエリア）を決める仕様に含まれている
任意の組の両ディメンションの値を包囲するすべての積
クラスに対してこのリストを処理することを提案してい
る。これは特定されたレンジ内にあるすべてのレコード
を分離するが、一方２つのレンジ仕様の２つでなく１つ
を満足する多数のレコードをも含む。クヌス（Knuth）
の方法のレンジは、２つの属性に従属しているため、各
レンジ／積クラスに対する特化性の欠如が複合される。
例えば、１つの質問を満足する値が２つのディメンショ
ンの各々に対する２つの隣接するレンジの中点の間に落
ちるエレメントの組の中に含まれる場合には、クヌス
（Knuth）の提案および本発明の双方とも25％の有効性
を示す（すなわち、選定された４つのうち１つが実際上
仕様に合致する）。しかしながら、２つの方法に対し
て、レンジの数を２倍にした場合は、本発明による選択
のすべてが仕様に合致する（すなわち、100％の有効性
を有する）が、クヌス（Knuth）の提案によるときは、
正確な１つのレコードに対して１つの無効レコードを生
じる（すなわち、50％の有効性となる）。したがって、
これらの不適切なレコードを放棄するには複雑な付加的
処理が必要となる。

このアプローチは、限定され、専門化された情報検索要
求に関する本発明のいくつかの機能に類似しているが、
クヌス（Knuth）の提案による構造は本来的に多元的な
ものであり、この多元的構造により記述された属性の１
つのみに関する質問は、この構造を使用して質問を満足
するレコードを見出すことの効率を極度に低下させる。
このように、顕著な相違は、クヌス（Knuth）の提案は
彼自身が指摘しているように、質問内で参照された属性
の組合せが機能的に決定され、優先順位が知られていな
い通常の質問の場合を満足させるため、他のこのような
リストとの有効な相互作用にまで直進的に拡張すること
ができないことである。これに対して、本発明の重要な
特性は、任意の数の情報のディメンションまたは形式の
同時処理を可能にし、かつ迅速な探索を可能にする“ト
ポロジカルマップ”の形状で対応性を決めることができ
るということである。これ以外にかなりの相違点がある
ことは本明細書から明らかであるが、上記の事実が本発
明を従来の技術から区別するのに充分であることも明ら
かである。

本発明は本明細書記載の実施例に限定されるものでな
く、本発明は他の変形をも包含するものである。したが
って、並列プロセッサ、専門論理プロセッサ、光デバイ
ス等と共働する手段ならびに反転マップ、デュアルクロ
スコーデッドマップ等を使用する方法を単独また組合せ
て種々の実施例を実現することも可能である。

以下図面により本発明を説明する。

〔実施例の説明〕

本発明は実質的に文脈基準情報検索システムで、このシ
ステムは情報の内容により情報に任意の基準を与え、仕
様に合った情報を効率的に検索する。

第１図に示すように、その全体を符号数字10で示すシス
テムは記憶装置14に蓄積されている情報ベース12にアク
セスし、これを操作するのに使用される。情報ベース12
は１またはそれ以上の情報エレメントを含み、各情報エ
レメントは１またはそれ以上の属性（またはフィール
ド）を含む。また、これらの属性は順序づけ可能な値を
有する。“順序づけ可能な値”とは、エレメントの属性
が評価可能であり、且つ情報ベース内の他のエレメント
のその属性の値に関してある順序に配置可能な値を有す
ることを意味する。これは数字、アルファベット文字、
記号、符号等を含むことを意味する。システム10は２つ
のサブシステム、すなわち、入力サブシステム20および
出力サブシステム30を含む。

入力サブシステム20は入力装置22から入力を受け入れ
る。入力装置22は情報ベースエレメントを受容する。こ
の場合、情報ベースエレメントは１またはそれ以上の属
性およびこれらの属性に対する対応値よりなる。入力サ
ブシステム20は、情報ベースに個々の情報エレメントが
入力される際、あるいは変更または削除がなされる際、
前記情報エレメントを処理し、かつ情報ベースエレメン
トの属性の処理表示または“トポロジカルマップ”16を
生成するために使用される。前記トポロジカルマップ16
は出力サブシステム30による爾後の使用のため記憶装置
14に記憶させる。

出力サブシステム30は入力として、質問32、すなわち１
またはそれ以上の属性の値の仕様にもとづいた情報に対
する照会を受ける。前記質問32は、任意の適当な入力装
置を用いて出力サブシステム30に入力するようにするこ
ともでき、また例えば、入力サブシステム20で使用して
いるのと同じ入力装置22を用いることもできる。また、
出力サブシステム30は仕様により参照された属性のトポ
ロジカルマップ16を検索するため記憶装置14を使用す
る。次に、これらのトポロジカルマップは質問に応じて
操作され、最終的に、 １）仕様に合致している（do meet）か ２）仕様に合致しているかも知れない（may meet）か ３）仕様に合致していない（do not meet）か のいずれかである情報エレメントを表示する１またはそ
れ以上の出力マップ18となる。

このように出力マップは質問の仕様に合致する情報ベー
ス内の情報エレメントの“スーパーセット”を定義づけ
る。

“スーパーセット”である理由は質問を満足する“かも
知れない”情報エレメントが含まれていることによる。

生成された出力マップはスーパーセット内のどの素子が
質問の仕様に合致しており、それらの素子のどれかが仕
様に合致しているかも知れないかを表示する。マップが
仕様に合致していることを示している素子は、記憶され
た情報エレメント自体にアクセスしたり検査したりする
ことなく確実に知ることができる。ここでは、出力マッ
プが仕様に合致しているかも知れないことを示している
素子のみにアクセスし、検査を行ってどの素子が仕様に
合致しているかを決めるようにし、質問の結果を出力装
置34によりユーザーに通報するようにしている。また、
以下の実施例から明らかなように、出力サブシステムは
ある属性の正確な値に関する質問、レンジ質問、ブール
論理を用いた複数属性に関する複雑な質問を含む色々な
種類の質問を迅速に解くことが可能である。

記憶装置14は特定形状に限定されるものでなく、本発明
をどのように実現するかに応じて種々の形状とすること
ができる。例えば、マイクロコンピュータを使用する場
合には、少なくともデータ記憶装置の一部を例えば半導
体メモリのような高速ランダムアクセスメモリにより形
成することが望ましい。この場合、トポロジカルマップ
は、マップの取扱いおよび処理を容易にするため、質問
の解明期間中高速ランダムアクセスメモリにロードする
ことが望ましい。また、付加的なデータ記憶、たとえ
ば、トポロジカルマップおよび情報ベースの情報エレメ
ントを固定記憶させるための記憶は、磁気媒体、バブル
メモリ装置、光（レーザ）メモリ装置等のような他の適
当なデータ記憶手段を用いて行うことができる。

以下、例示目的のため固定長ASCIIレコードにより表わ
されたエレメントにより構成した情報ベースにこの技術
を適用した実施例につき考えることにする。この場合、
情報ベース内の各エレメントは複数の属性よりなり、各
属性の形式は、文字または数字を記憶することが可能な
ことを意味する“アルファ（Alpha）”、または（ディ
ジットのASCIIストリングとして表示される）整数値を
記憶することが可能なことを意味する“インテジャ（In
teger）”のいずれかをとり得る。この情報ベースのエ
レメントに対する属性リストを以下に示す。

また、このサンプル情報ベースの内容は以下のとおりで
ある。

このように、情報ベースは103個（０からナンバーリン
グをしているため）のレコードを含み、したがってスロ
ット103はこの情報ベース用のファイルの終り（EOF）と
なる。

以下、上記のような情報ベースを使用し、プロセスの説
明をすることにする。

入力サブシステム (a)レンジ群界 トポロジカルマップを作成する前に、各属性についてレ
ンジの群を作成する必要がある。レンジの群は属性に対
する１またはそれ以上の独自の値の範囲、すなわちこの
属性に対する下限および上限からなる。属性についての
レンジ群を作り上げるすべてのレンジは、全体として、
情報ベース内のすべてのエレメントについてこの属性の
とり得るすべての値を含むものでなければならない。す
なわち可能なすべての属性値に対して、その値を含む少
なくとも１つのレンジが存在するものでなければならな
い。このようなレンジ群を決定する１つの方法はこれら
のレンジを随意に決めることである。“レンジ群”の一
例を次表に示す。

情報エレメントは、その情報エレメントについての属性
の値が特定のレンジ内に含まれる場合には、該特定レン
ジに“マップする”という。また、属性値もそのレンジ
にマップするという。

このレンジ群の場合に、マップする値とレンジのいくつ
かの例を次表に示す。

レンジは上記のようにオーバーラップするよう構成する
こともできるが、これらのレンジを相互に排他的となる
ように構成し、属性の任意の所定値がレンジ群のうちの
１つのレンジに正確にマップするようにする方が有利で
ある。さらに、通常、ほぼ同数の情報エレメントを属性
の各レンジにマップさせるようにすることが好都合であ
る。これは、情報ベース内の情報エレメントのサンプル
をとり、サンプル内の同数の情報エレメントが各レンジ
にマップするよう、換言すればレンジ群によりサンプル
が等しく分割されるようレンジ群を選定することにより
実現することができる。また、サンプルの大きさを十分
有効となるよう大きなものとした場合は、このレンジ群
が全体として情報ベースをほぼ等区画に分割することを
可能にする。

さらに、属性に関するレンジの各々に特有のコード表示
を組合せることが得策である。かくして、250のレンジ
を有するレンジ群を作成する場合は、最も低い属性値を
含むレンジに０を割当て、次に低いレンジに１を割当
て、……最も高いレンジに249を割当てるようにするこ
とが望ましい。

属性について便利なレンジ群は以下の方法により作るこ
とができる。

(a)レンジ群内にあるべきレンジ数（NUM-RANGES）を決
定する。（標準的なレンジ数の値は250。） (b)情報ベースから（レンジ数×レンジ当りサンプル
数）個のサンプルをとり、サンプルアレイ（SAMPLE-ARR
AY）とする。（標準的なレンジ当りサンプル数の値は3
0。） (c)サンプルアレイの各エントリーを（この形式の属性
に適する配列ルールにもとづいて）上昇順序に並べる。

(d)次に、サンプルアレイからレンジ当りサンプル数番
目ごとのアレイのエントリーを選び出し、これをレンジ
の上限とする（下限は前の上限により決められる）。こ
の結果をレンジ定義アレイ（RANGE-DEF-ARRAY）に記憶
させる。結局、レンジ定義アレイ内に記憶された最後の
値がこの属性に対してあり得る最高値である。

特定の実施例として上述の情報ベースの場合を考えるこ
とにする。いま、SALARYに関するレンジ群を作成するた
め、レンジ数＝８、レンジ当りサンプル数＝５と仮定す
る。この場合は、情報ベースから（レンジ数×レンジ当
りサンプル数）＝（８×５）＝40個のサンプルを取り、
選定された情報ベースエレメントからSALARYの値をと
り、これをサンプルアレイのエントリーに転送すること
が必要である。サンプリング操作は図示的には次のよう
になる。

かくして、ここにサンプル値で充たされたサンプルアレ
イを得、このアレイを上昇順序に並べる。アレイを並べ
た後は、並べられたサンプルアレイのレンジ当りサンプ
ル数番目の各値をレンジ間の上限値として使用する。こ
のプロセスを図示すると次表のようになる。

このプロセスの最終結果としてレンジ定義アレイが次の
ようになっている。

入力操作 入力手順は次にの処理ステップを含む。

(A)各エレメントが各々１つの値を有する１またはそれ
以上の属性を含むような１またはそれ以上の情報エレメ
ントを入力する。

(B)各属性に対して (1)各情報エレメントに対して (a)この属性に対して決められたレンジ群を用いてその
属性がマップするレンジを決定する。

(b)この属性がマップしたレンジを表わすコードを、こ
の情報エレメントのレコードナンバーに対応するこの属
性のトポロジカルマップ内の記憶場所に記憶させる。

値VALUEがマップするレンジを決定するため、次のアル
ゴリズムを適用する。

(a)FOR i：＝O TO NUM-RANGES (1)IF RANGE-DEF-ARRAY〔ｉ〕＞＝VALUE GOTO EXIT (b)EXIT：RETURN(i)； したがって、ｉはその値に等しいかそれより大きい境界
値が見付かるまで増加する。この時点において、レンジ
定義アレイへのインデックスがこの属性のこの値に対応
するレンジナンバーとなる。

このプロセスを図式的に示せば次のようになる。

上記の表示においては、入力に関係する属性であるSALA
RY属性を示すため情報ベースは省略してある。また、上
述の方法は各値に対してそれがマップするレンジを決定
するのに使用される。この場合、その値がマップするレ
ンジに対応するレンジナンバーを、そのもととなるレコ
ードに対応してSALARYトポロジカルマップに記憶させ
る。この場合には、各情報ベースエレメントのレコード
ナンバーを情報エレメントに対応するレンジナンバーを
記憶させるトポロジカルマップ内のオフセットとして使
用することにより、対応性が保持される。

次に、他の例示として、情報ベースに付加すべき新しい
エレメントについて考えることにする。

このレコードはファイルの終り（EOF）に記憶される。

新しいトポロジカルマップのエントリーは次のように作
られる。

前述の方法を有効に機能させるのに重要な１つの最適化
は“補正マップ”の概念である。ある情報ベースに上述
の方法を繰返し適用する場合は、新しい情報ベースエレ
メントを付加し、もしくは現存の情報エレメントの属性
を変更するたびごとに、各属性のトポロジカルマップに
対し更新を必要とする。本実施例における情報ベースの
場合には、３つの属性を有しているので、付加すべき各
レコードはトポロジカルマップを更新するのに３つのア
クセスを必要とする。各エレメントが12の属性（珍しい
ことではない）で記述されているような情報ベースの場
合には、付加されるエレメント当り12のアクセスを行う
ことが必要となる。本実施例の情報ベースの場合、情報
ベースに100のエレメントを付加する場合は（100×３）
＝300のアクセスが必要となる。

しかし、ここに提案する“補正マップ”を使用するとき
は情報エレメントのあらゆる属性に対するレンジナンバ
ーを記憶させることができるようになっている。したが
って、新しいレコードを付加するときは、３つでなく１
つのマップの更新を必要とするのみで、この１つの更新
は補正マップに対して行われる。補正マップのエントリ
ーは各属性に対するレンジナンバーとともに付加情報エ
レメントのレコードナンバーを有する。属性に対するマ
ップを検索する場合は、補正マップもまたロードされ、
補正マップ内の各エントリーは属性マップの記憶イメー
ジを更新するよう処理されて、100％最新のマップが得
られる。

補正マップ内のエントリーのすべては、後刻、各属性に
対してトポロジカルマップを更新するときに一緒に処理
することができる。本実施例の場合は、100素子を付加
し、それらはすべてファイルの終りにおいて付加されて
いるので、更新すべきトポロジカルマップのエレメント
はすべて同じ物理ブロック内に位置する。したがって、
各属性に対して１アクセスのみでよく、100のすべての
エントリーをトポロジカルマップに付加することができ
る。本方法を“手を加えない”状態で適用する場合に必
要なアクセスの総数は（100×３）＝300アクセスであっ
たが、この改良により、（100×１）＋（３×１）＝103
のアクセスだけで済み、かくして、記憶装置の入出力要
求を約３：１に減少させることが可能となった。

出力サブシステムの作動 質問の１つの一般的な形はブール質問（Booleanquery）
と呼ばれるもので、AND,ORまたはNOTにより結合された
１またはそれ以上のレンジ質問と定義することができ
る。前記レンジ質問は次のような形状の質問である。

（＜値＞〈＝＜属性の名称＞〈＝＜値＞） 本実施例の情報ベースの場合、レンジ質問は次のように
なる。

（3000〈＝SALARY〈＝4500） この質問は、3000と4500の間にある属性SALARYの値を有
するすべての情報ベースエレメントを検索したいことを
意味する。

出力手順は質問を入力として受信し、次いで、質問の仕
様に合致しているレコードのスーパーセットを生成する
ことよりなる。質問を与えられるこのスーパーセットの
生成を質問を“解く（resolving）”という。

その結果は情報ベース内の各情報エレメントに対して、
質問に関するエレメントの次の３つの状態の１つを記述
する。

(a)NO（ノウ） このエレメントは仕様に合致していない。

(b)YES（イエス） このエレメントは仕様に合致している。

(c)MAYBE（メイビー） このエレメントは仕様に合致しているかもしれない。レ
ンジに関する量子化誤差により、この情報エレメントが
仕様に合致しているかいないかが確認されない。

始めに、入力プロセスにより作成されたトポロジカルマ
ップを使用してレンジ質問を解く方法を示し、次に、レ
ンジ質問のブール組合せ（Boolean combinatin）を含む
質問の解を示す。

レンジ質問の解 次のような形の質問を考える。

（＜低い値＞〈＝＜属性＞〈＝＜高い値＞） この質問の例は次のようなものである。

（4500〈＝SALARY〈＝6350） 以下の議論において、アクセプタブル（ACCEPTABLE）と
は、属性のレンジ当り１つのエントリーを有する整数の
アレイで、このアレイ内の各エレメントは次の３つの値
の１つを有する。

(a)NO-VALUE（ノウの値） このレンジナンバーを有するエレメントは確実にレンジ
仕様に合致していないことを示す。

(b)YES-VALUE（イエスの値） このレンジナンバーを有するエレメントは確実にレンジ
仕様に合致していることを示す。

(c)MAYBE-VALUE（メイビーの値） このレンジナンバーを有するエレメントはレンジ仕様に
合致しているかもしれず、合致していないかもしれない
ことを示す。

このレンジ質問を解く方法は以下のとおりである。

（注：マップ（値）は属性に対するこの値のレンジナン
バーに戻る） (a)アクセプタブルアレイを生成する。これにより、ア
クセプタブルアレイを直線的に検索することによって情
報エレメントのレンジナンバーが分かり、レンジ質問を
解くことが可能になる。

(1)Set low-range＝map(low-value) (2)Set high-range＝map(high-value) (3)FOR i：＝Ｏ TO(low-range-1) (a)ACCEPTABLE〔ｉ〕：＝NO-VALUE (4)ACCEPTABLE〔low-range〕：＝MAYBEVALUE (5)FORｉ：＝（low-range＋１）TO(highrangE−１） (a)ACCEPTABLE〔ｉ〕：＝YES-VALUE (6)ACCEPTABLE〔high-range〕：＝MAYBEVALUE (7)FORｉ：＝（high-range＋１）TO MAXRANGE-NO (a)ACCEPTABLE〔ｉ〕：＝NO-VALUE (b)この属性に対しトポロジカルマップを検索し、トポ
ジカルマップTOPOLOGICAL-MAP内に記憶する。トポロジ
カルマップTOPOLOGICAL-MAPは整数のアレイである。

(c)トポロジカルマップTOPOLOGICAL-MAP内のエントリー
ごとに１つのエントリーを有する出力マップ、OUTPUT-M
APを作成する。出力マップOUTPUT-MAPは整数のアレイで
ある。

(d)FORｉ：＝０ TO(NUM-ENTRIES-IN-MAP-1)(1)OUTPUT-
MAP〔ｉ〕：＝ ACCEPTABLE〔TOPOLOGICAL-MAP〔ｉ〕〕 ここで、出力マップOUTPUT-MAP内の各エントリーは、対
応する情報ベースエレメントがそれぞれ仕様に合致して
いるか、合致していないか、あるいは合致しているかも
しれないかのいずれかを示すNO-VALUE,YES-VALUEまたは
MAYBE-VALUEの値をとる。

例えば、（3300〈＝SALARY〈＝7300）のような質問に対
するアクセプタブルアレイの作成を図示すると次のよう
になる。

このように、レンジ０または１にマップする値は明らか
に仕様の範囲内にはない。次に、レンジ２にマップする
値の場合は、このレンジにマップするいくつかの値はレ
ンジ仕様の範囲内にあり、またいくつかの値はレンジ仕
様の外側にあるため、レンジ仕様に対してmay beであ
る。また、レンジ３，４または５にマップする値は仕様
の範囲内にあり、レンジ６にマップする値はレンジ２の
場合と同じ理由により、レンジ仕様の範囲内にあるかも
しれず、またないかもしれない。最後に、レンジ７また
は８にマップする値は仕様の範囲内にない。

また、出力マップの作成を図示すると次のようになる。

ブール質問の解 一般に、上述のレンジ質問は、AND,ORおよびNOTと組合
せて、より複雑な質問を作ることができる。その例とし
ては、 ・（（3500〈＝SALARY〈＝5000)AND(2130〈＝JOB-CODE
〈＝2240）） ・（（7200〈＝SALARY〈＝7900)OR(4160〈＝JOB-CODE
〈＝5000）） ・（（7200〈＝SALARY〈＝7900)AND(NOT(4160〈＝JOB-C
ODE〈＝5000）） 前述のレンジ質問の解法では個別のレンジ質問は解ける
が、論理のブール組合せを取扱う方法については明らか
にされていない。

レンジ質問のブール組合せは次のような一般的方法によ
り取扱うことができる。

(a)ブール質問内の各レンジ質問を解き、その結果を各
レンジ質問用の異なるマップ（中間出力マップ）に置
く。

(b)その結果（中間出力マップ）をブール質問にしたが
ってレンジ質問用として論理的に組合せる。

各ブール演算子（Boolean operators）用の真理値表は
次のようになる。

この真理値表は実生活におけるこれらの言葉の意味を常
識的に適用することからなり明らかである。すなわち、
例えばN AND Y＝Ｎでは、もし、あるものが(a)であり且
つ(b)であると仮定したとき、それが(b)であって(a)で
ないとすれば、(a)であり且つ(b)であるという仮定は真
ではない。他の例Y AND M＝Ｍでは、あるものが(a)であ
り且つ(b)であると仮定したとき、それが(a)であること
が知られ、且つ(b)であるかもしれないとすれば、(a)で
あり且つ(b)であるとの仮定は満足されることもあり得
る。

この真理値表の場合も言葉の意味を常識的に適用するこ
とからなり明らかとなる。

（2000〈＝SALARY〈＝5250）の例を考えた場合は、次の
ように示される。

この場合は、明らかに、０はＮであり、１はＭであり、
２−３はＹであり、４はＭであり、かつ５−８はＮであ
る。次に、（NOT(2000〈＝SALARY〈＝5250)）を考えた
場合、対象値は次のようになる。

この例では、明らかに、レンジ０はＹ、１はＭ、２−３
はＮ、４はＭまたは５−８はＹである。このように、Ｙ
レンジがＮレンジに変わり、ＮレンジがＹレンジに変わ
り、ＭレンジはＭのままとなる。

ディスカッションおよび実施例 したがって、（RANGE-QUERY-1 AND RANGE-QUERY-2）の
ような形式の質問の場合には、レンジ質問RANGE-QUERY-
1を解いて、その結果を出力マップOUTPUT-MAP-1に置
き、レンジ質問RANGE-QUERY-2を解いて、その結果を出
力マップOUTPUT-MAP-2に置く。次に、ANDに対する前述
の真理値表にしたがってOUTPUT-MAP-1とOUTPUT-MAP-2の
論理積（AND）をとり、出力マップRESULTを与える。RES
ULTは仕様に合致する情報エレメント、仕様に合致して
いない情報エレメントおよび仕様に合致しているかもし
れない情報エレメントを示す。

ここで、特定例として次のような質問を考えてみる。

（（3500〈＝SALARY〈＝5500)OR(1300〈＝JOB-ID〈＝23
00）） 上記のSALARYに関するレンジ決定とこの質問に関するア
クセプタブルアレイは次のようになる。

また、この例については特定されていなかったJOB-IDに
関するレンジ群は次のようになる。

情報ベースの最初の部材を考えると、 SALARYとJOB-IDに関するトポロジカルマップおよび出力
マップは次のようになる。

したがって、これらを組合せる（相互にORをとる）と、 かくして、レコード０，１，２および４は考慮の対象か
らはずされ、またレコード３および５は質問を満足して
いるかもしれないし、満足していないかもしれない。

〔変形例および他の応用〕

マップの表示 本発明により使用されるトポロジカルマップは種々の方
法で表示することができる。標準的表示は通常、各々情
報ベースの情報エレメントまたはレコードに対応するコ
ードのアレイと考えることができる。他の可能な表示は
レコードあたり１つのビットマップを有し、各ビットを
所定コードに対応させることで、また他の可能な表示は
レコードの組ごとに１つのビットマップを有し、組内の
属性値がマップする各コードに対応するビットをセット
することである。さらに、他の可能性はマルチレベルの
ビットマップを有することである。

例えば、64コードの場合には、通常、その上に64の位置
を有するビットマップが必要であると考えられるが、次
のようにすればこの記憶要求をわずか16ビットに減少さ
せることができる。

２つの組のビットマップ １）コード／８（／は整数除算を意味する）に対応する
もの ２）コード％８（％はモジュラス除算を意味する）に対
応するもの を構成する。

したがって、いまコード28に対応する属性値を有するレ
コードの場合には、このレコードに対応するビットマッ
プに２つのビットをセットする。すなわち、（28／８）
＝＝３に対応するビットをマップ１にセットし、（28％
８）＝＝４に対応するビットをマップ２にセットする。

任意のコード、すなわち、コード35に対応するビットマ
ップを得るには、（35／８）＝＝４に対応するビットマ
ップをマップ１に取り出し、（35％８）＝＝３に対応す
るビットマップをマップ２に取り出す。次に、これら２
つのマップの論理積（AND）をとることにより、コード3
5にマップする属性を有するレコードを正しく表示する
マップを得ることができる。

同じことがビットによるマルチプルレコードについても
適用できる。ただし、この場合には、マップを再生する
際、ある不確かさが存在する。すなわち、コード35に対
して再生されるマップは、必ずしも、コード35にマップ
する属性を有するレコードのみを含むとはいえない。し
かし、この誤差は統計学的に制御することができる。

これらのビットマップはビットワイズに、すなわち、す
べてのマップのビット０は一緒に記憶され、ビット１は
すべて一緒に記憶され、すべてのビット２は一緒に記憶
される……というようにするときわめて好都合である。
このようにするときは、レンジ質問が与えられた場合、
所望のレンジに対応するすべてのマップを簡単に検索
し、これら相互の論理和（OR）をとることにより、特定
のレンジ内のレコードを含まないレコードのすべてのサ
ブセットを示すマップを形成することができる。

誘導された属性 情報エレメントに直接記憶された属性用マップはこれを
作成し、記憶させることが可能であるほか、情報ベース
内のフィールドから計算された属性用マップを記憶する
ようにすることもできる。例えば、各個人の総収入およ
び税率の双方を含む全員の記録を具えたデータベースが
あった場合には、正味の収入、すなわち、（総収入×税
率）に関する任意の数の質問を得ることができる。この
場合には、データベースに対応して正味の収入のマップ
を記憶させることができ、そこではレコードが記憶され
るごとに、正味の収入が計算され、次いでマップのエン
トリーが任意の属性として記憶される。この場合、正味
の収入に関する質問を受信した際には、このマップを使
用して、どのような値についても計算することなしにレ
コードを取り出すことができる。

“誘導（derived）”なる語句の範囲は以下の例により
僅かに拡張することができる。すなわち、税率をレコー
ド内に直接記憶させる代りに総収入および控除額を記憶
するようにしてもよい。総収入および控除額にもとづい
て、他のデータベースにおける調査を行い、それにより
税率を決定することができる。各レコードが記憶され、
レコード内で情報を与えられる税率を探索して、正味の
収入を計算し、マップのエントリーを記憶するようにし
た場合は、上述のように正味収入のマップを記憶させる
ことができる。この場合のポイントは、“誘導（derive
d）”というのは必ずしもまわりくどくない直進的な計
算を意味するものではないということで、それらはデー
タベース内で探し出された値でもよく、あるいはその問
題に関するエキスパートシステムから導出されたもので
もよい。

表示によるマルチプルレコード レコードのサブセットの概念は、マップを取扱うのに使
用される論理が首尾一貫したものである限り１を超える
レコードを有する範囲まで拡張することができる。

１つの例として、個人のマルチプルレコードを含むデー
タベースを有する場合を考えると、レンジ各々について
１つのビットを含むビットマップの表示によって、レコ
ードのサブセットがマップするレンジを選定することが
できる。したがって、レコードのサブセットが与えられ
ると、各個人のレコードの属性値がマップするレンジが
決定され、次にこれらのレンジに対応するビットがセッ
トされる。

また、この属性に関するレンジ質問が与えられた場合
は、質問レンジ内に含まれるか、質問レンジとオーバー
ラップするレンジに対応するすべてのビット内に１を含
むビットマップを設定することができる。次に、このマ
スクによりマップ内の各エントリーの論理積（AND）を
とり、その結果のなかに非ゼロビットが発見された場合
は、このサブセットは仕様に合致する１またはそれ以上
のレコードを含み、そうでない場合はこのサブセットは
確実に除外するようにする。これを図示すると次のよう
になる。

このように、サブセット内のレコードが（０〈＝Age〈1
0）のレコードを有する場合、ビット０はそのかなに１
を有し、サブセット内のレコードが（10〈＝Age〈20）
のレコードを有する場合、ビット１はそのなかに１を有
し、以下これに準ずる。例えば、サブセットあたり２人
のレコードを有し、サブセットはこれら２つのレコード
を含むものとする。

Name： Bill Age： 25 Salary： 35000 Name： Jim Age： 32 Salary： 42000 この場合は、このサブセットに対する年令に関する属性
マップ表示は次のように計算される。

０ ０ １ １ ０ ０ ０ ０ また、その計算は、次のとおりである。

ビル（Bill）は（Age＝＝25）を有するので（20〈＝Age
〈30）で、これはビット２にセットすることを意味す
る。また、ジム（Jim）は（Age＝＝32）を有するので、
（30〈＝Age〈40）で、これはビット３にセットするこ
とを意味する。

ここで留意すべきは、２つのマップに対するサブセット
ごとのレコードの数は異なるものとすることができ、こ
れらのマップは一緒に使用することができることであ
る。

データ解析 本発明の原理は２以上の変数の間でデータ内の相関を検
出するために使用することができる。２以上の変数なら
びにこれらの変数用のマップが与えられた場合は、これ
らの変数間に相関があるかどうかをきわめて単刀直入に
決定することができる。例えば、データベース内のすべ
てのレコードに適用する２つの変数、年令（Age）およ
び給与（Salary）を有するものとし、かつAgeおよびSal
aryを50のレンジに区分するものとする。

AgeとSalary間に相関があるかどうかを決定したいと思
う場合は、（50×50）の整数のアレイを生成することに
よりこれが可能となる。始めに、各ポジションを０にセ
ットし、次にAgeおよびSalaryに対応するマップを取り
出す。各レコードに対するAgeおよびSalaryに関するレ
コードの双方は順序づけした対を形成し、この対は（50
×50）アレイ内の特定のエレメントに対するリファレン
スとして使用できる。各レコードについて、Age用コー
ドおよびSalary用コードを用いて、このような順序づけ
した対を作成し、ついで対応するアレイエレメントを１
に変える。このプロセスはデータベース内の各レコード
に対して繰返し行うものとする。

このプロセスが終わると、全体のアレイが得られる。Ag
eとSalaryの双方に対する各レンジにおけるレコードの
数（それらをカウントすれば直ちにこの数が分る）は統
計的に知ることができるので、２つの変数が相互に独立
している場合、各“グリッドポイント”（すなわち、Ag
eレンジSalaryレンジの交点）における期待されるレコ
ードの数を見積ることができる。この数をカウントされ
た実際のレコードの数と比較することにより、観察され
ることを期待されるレコードの数と実際に観察されるレ
コードの数との間に統計的に顕著な差が存在しているか
どうかを決定することができる。これは、勿論、これら
２つの変数間には相関がある（またはない）ことをはっ
きり示すための根拠として役立つ。

このプロセスには２つの拡張がある。

１）それを２からｎ個の変数に拡張すること。

換言すれば、３−ｄマトリックスをセットアップする場
合は、３つの変数を有することができる。

２）全情報ベースの１つのサブセットのみを調べるこ
と。換言すれば、検討しようとする１つの職業について
のレコードに限定して上記の（AgeとSalary間の）よう
な相関を見ることである。

したがって、この場合、見られる相関はきわめて深いも
のである。

このように、本発明による標準的な質問の技術を用いる
ときは、サンプルを全情報ベース内のレコードの関連の
サブセットに狭めることができる。

マイクロコンピュータでの実施 前述の実施例ならびにそれに関する方法およびアルゴリ
ズムの記述から、デジタルコンピュータのプログラミン
グ技術者は容易に理解できるように、本発明の装置およ
び方法はマイクロコンピュータおよびメインフレームを
含む種々の形式のアーキテクチャとサイズのコンピュー
タを用い、かつ種々のプログラム言語およびプログラミ
ング技術を用いて実現することができる。例えば、前述
の実施例に記憶した手順を使用したデータベースの記憶
・検索システムをIBM-ATコンピュータに対して実現し
た。約15,000レコード、1.3メガバイトの大きさのテス
トファイルからデータレコードを検索するのに、このよ
うなシステムを使用してテストを行った結果、このシス
テムは最も一般的な商用データベースシステムより少な
くとも80倍はやい速度でレコードにアクセスし、レコー
ドを検索しうることが分った。

並列処理技術 本明細書に記載のすべての方法は容易に並列に行うこと
ができる。これは、この全システムが基本的にコードの
アレイであるマップをベースにしているという事実によ
る。アレイは相互に排他的な独立したセグメントに容易
に分割でき、これにより並列に作動させることが可能と
なる。

例えば、標準形ATシステムの４倍の速さで実行するAT準
拠システムを作りたいという場合には、第２図に示すよ
うに４つの独立システムを接続していくつかのネットワ
ーク接続上を交信しうるよう構成する。レコードが付加
された場合は、AT０はこの新しく付加されたレコードに
対してレコードナンバー、rec-numを使用すべきかどう
かを決定する。ここで、０……３の間のナンバーを生ず
る（rec-num MOD4）をとり、AT♯（♯＝＝rec-num MOD
4）にこのレコードの保管をさせるようにしたときは、
実際上４つのATの間でレコードを平等に分配することが
できる。いま、ここで、質問を受容したとすれば、AT０
はネットワークの他にATにその質問を送信することがで
き、各ATはその情報ベースの１／４上で質問の処理を始
め、この処理は並列（PARALLEL）に進められる。次に、
各ATはその結果（すなわち、マッチしたレコードナンバ
ーのアレイ）をAT０に送り戻すことができ、かくしてユ
ーザーは実効的な質問処理時間を１／４にできる。

他の例を与えるため、AgeとSalary間の相関を決定しよ
うとする上述のデータ解析例を考えることにする。ここ
で上述のようにマップを分配させるものとした場合は、
この分配解析は４つの各マシン上で並列に行うことがで
きる。この解析の結果は（50×50）の整数のアレイであ
る。各マシンがデータベースのそのセクションに対する
アレイの計算を終った後には、これらのアレイはAT０に
送達される。次いで、AT０は（50×50）アレイを加算し
て、全データベースに対する分配を完全に記述した１つ
の（50×50）アレイを得ることができる。このように、
中心部分による仕事は完全に４等分されていないが、多
数のレコードを扱えば、４等分に近くなる。

専用アーキテクチャ 本発明を使用するに当っての本来の利点は、データの関
連づけ操作を、デジタルコンピュータで容易に取扱うこ
とが可能な直接的な操作に簡易化することであるが、こ
れらの簡単な作用をし得るような特別なハードウェアを
設計することにより、さらに利便を得ることができる。

質問を処理する場合には、しばしば各々が１つのレンジ
に対応する整数のアレイ（“受容性テーブル（acceptab
ility table）”）が使用される。例えば、対応するレ
ンジが質問の仕様に合致する場合、アレイエントリーは
３とし、対応するレンジが質問の仕様に合致しているか
もしれない場合は１とし、また対応するレンジが質問の
仕様に合致していない場合は０とする。かくして、属性
に関するマップを検索し、マップ内の各エントリーを順
番に処理して整数のアレイへの捜索を行い、整数のアレ
イ内のエントリーが０の場合は、このレコードに対応す
る“受容性マップ（acceptability map）”内のポジシ
ョンに０を書込むことにより、このレコードを考慮の対
象からはずす。この特定の作用だけを実行する特別のチ
ップを形成することは、まわりくどさを排除することに
なる。“受容性テーブル”は作動開始時に、２つのベク
トル、すなわち、属性用マップに対するベクトルおよび
“受容性マップ”に対するベクトルとともに処理すべき
マップ内のエントリーの数のカウントをチップに直接ロ
ードすることができる。かくして、チップは処理を始め
ることができ、この場合、処理速度は次の２つの理由に
より大幅に改善される。

１）命令の呼出しにはバス帯域幅は使用されない。ま
た、これとともに、命令をデコードするのに実行時間は
費消されない。論理はチップの作動によってハードコー
ド化される。

２）“受容性テーブル”はチップ上に直接ロードされる
ので、受容性テーブルの調査には、バスの帯域幅は使用
されない。

実際上、チップは２つのバスサイクル当り１つのレコー
ドを処理することができる。

これをさらに少し拡張すると、ソフトウェアとハードウ
ェア間を分ける線はきわめて任意的である。通常は、価
格上の配慮のため、きわめて普遍的な論理ピースのみを
ハードウェアが実現し、次にソフトウェアのレベルによ
ってそのハードウェアベースを用いて機能性を与えるよ
うにしているが、本発明の場合には、基本的作動が直接
的であり、かつ一般に本発明のすべての利用分野に適用
できるので、このハードウェア組立ては特に有利である
と期待できる。

上記の説明から分かるように、本発明は多くのユニーク
かつ有利な特性を有する。また、本明細書記載の特許請
求の範囲はこれらの特性のいくつかを限定するもので、
これ以外のユニークかつ有利な特性は、上記の説明およ
び以下の利点の項から理解することができる。

本発明は、 (a)各々順序づけ可能な値をもった複数の属性を有する
複数の情報エレメントを情報記憶装置に記憶するステッ
プと、 (b)前記エレメントの該各属性に対して、全体的に情報
ベース内のすべての情報エレメントに対する属性値を含
む予め定められた数の属性値のレンジを表示する複数の
レンジコードを含むトポロジカルマップと、ならびに該
情報エレメントの各々とそれらがマップするレンジとの
間の対応を決定する該レンジコードのアレイとを情報記
憶装置に記憶するステップと、 (c)記憶情報エレメントの１またはそれ以上の属性に関
する特定のパラメータおよび論理にもとづいた仕様を有
する質問を受信するステップと、 (d)質問に特定された各属性についての適当なトポロジ
カルマップにアクセスし、それから情報ベース内の各情
報エレメントに対応し、かつ各関連情報エレメントが質
問の仕様に合致しているか、合致していないか、あるい
は合致しているかもしれないかを示すエレメントを有す
る出力マップを生成するステップと を含むことを特徴とする情報ベース内の情報を記憶し、
操作する方法を与えるものである。

さらに、本発明によるときは、以下のような付加的ステ
ップ、すなわち、 情報ベースに付加的情報エレメントを付加するステップ
と、 このように付加された各エレメントに対して、付加情報
エレメントの各属性についてのレンジコードを含む補正
マップを作成するステップと、 ステップ(d)によりトポロジカルマップにアクセスする
ごとに補正マップを処理してトポロジカルマップを更新
するステップと を含む上述形式の方法を提供することができる。

また、他の見地において、本発明は、質問を記憶された
情報エレメントの複数の属性ならびに属性に関する特定
パラメータに関連するブール論理にもとづいたものと
し、適当なトポロジカルマップにアクセスし、出力マッ
プを生成する該ステップは、 (1)該質問で特定された各属性に対するトポロジカルマ
ップにアクセスし、それから特定された各属性に対して
情報ベース内の各情報エレメントに対応し、かつ、個別
の各情報エレメントが質問に特定されたそれぞれの属性
の仕様に合致しているか、合致していないか、あるいは
合致しているかもしれないかを示すエレメントを有する
中間出力マップを生成するステップと、 (2)質問のブール論理にしたがって関連の中間出力マッ
プを組合せ、該出力マップを生成するステップと を含むようにした上述形式の方法を与えることができ
る。

【図面の簡単な説明】

第１図は本発明装置の主要構成素子を示すブロック図、 第２図は本発明を並列処理状態で実現するに適したマイ
クロコンピュータの配置を示すブロック図である。 10…装置、12情報ベース 14…記憶装置、16…トポロジカルマップ 18…出力マップ、20…入力サブシステム 22…入力装置、30…出力サブシステム 32…質問、34…出力装置 AT0,AT1,AT2,AT3…マイクロコンピュータ

フロントページの続き (56)参考文献 特開 昭62−182923（ＪＰ，Ａ) 特開 昭63−101963（ＪＰ，Ａ) 特開 昭56−153445（ＪＰ，Ａ)

Claims (19)

【特許請求の範囲】
1. 【請求項１】情報ベース内の情報を記憶し、操作するシ
   ステムにおいて、 (a)情報記憶装置と、 (b)該情報記憶装置に記憶され、各々順序づけ可能な値
   を有する少なくとも１つの属性を具えた複数の情報エレ
   メントと、 (c)該情報記憶装置に記憶された該各属性についてのト
   ポロジカルマップであって、 (1)全体として情報ベース内のすべての情報エレメント
   の属性値を含む予め定められた数の属性値のレンジを表
   示するための手段、および (2)該情報ベース内の情報エレメントの各々とそれらが
   マップするレンジとの間の対応を決定するための手段 を有するトポロジカルマップと を具えたことを特徴とする情報記憶・操作装置。
2. 【請求項２】さらに、 (d)記憶された情報エレメントの属性に関する特定のパ
   ラメータにもとづいた仕様を有する質問を受信するため
   の、前記情報記憶装置と協働する入力装置と、 (e)質問の受信に応答し、該質問にもとづいて該トポロ
   ジカルマップにアクセスし、情報ベース内の情報エレメ
   ントを検査することなしに、質問の仕様に合致している
   ことがはっきりしている情報ベース内の情報エレメント
   群を該マップから識別するための手段と を含むことを特徴とする請求項１記載の装置。
3. 【請求項３】また該手段(e)は情報ベース内の情報エレ
   メントを検査することなしに、質問の仕様に合致してい
   ないことがはっきりしている情報ベース内の情報エレメ
   ント群を該マップから識別するための手段を含むことを
   特徴とする請求項２記載の装置。
4. 【請求項４】該手段(e)は、また、情報ベース内の情報
   エレメントを検査することなしに、質問の仕様に合致し
   ているかも知れない情報ベース内の情報エレメントを含
   む情報エレメント群を該マップから識別するための手段
   を含むことを特徴とする請求項２記載の装置。
5. 【請求項５】質問の仕様に合致しているかも知れない情
   報ベースの情報エレメントを含む情報エレメント群のみ
   を検査し、それら検査されたエレメントのうちどのエレ
   メントが質問の仕様に合致しているかを識別するための
   手段を含み、かくして、質問の仕様に合致している情報
   ベースのすべての情報エレメントを識別するよう形成し
   たことを特徴とする請求項４記載の装置。
6. 【請求項６】さらに、 (d)記憶された情報エレメントの属性に関する特定のパ
   ラメータにもとづいた仕様を有する質問を受信するため
   の、前記情報記憶装置と協働する入力装置と、 (e)質問の受信に応答し、該質問にもとづいて該トポロ
   ジカルマップにアクセスし、それにより情報ベース内の
   各情報エレメントに対応し、かつ個別の各情報エレメン
   トが質問の仕様に合致しているか、合致していないか、
   あるいは合致しているかも知れないかを表示するエレメ
   ントを有する出力マップを生成するための手段と を含むことを特徴とする請求項１記載の装置。
7. 【請求項７】該情報記憶装置に記憶された情報エレメン
   トは各々複数の異なる属性を有すること、および該装置
   はさらに、 (d)記憶された情報エレメントの複数の属性ならびに属
   性に関する特定のパラメータに関係するブール論理にも
   とづいた仕様を有する質問を受信するための、前記情報
   記憶装置と協働する入力装置と、 (e)質問の受信に応答し、該質問に特記された各属性に
   ついてのトポロジカルマップにアクセスし、それによ
   り、特記された各属性についての第１の出力マップであ
   って、情報ベース内の各情報エレメントに対応したエレ
   メントを有し、該エレメントは個別の各情報エレメント
   が質問に特記された属性の仕様に合致しているか、合致
   していないか、あるいは合致しているかも知れないかを
   表示するエレメントを有する第１の出力マップを生成す
   るための手段と、 (f)質問のブール論理にしたがって各々の第１の出力マ
   ップを組合せ、情報ベース内の各情報エレメントに対応
   し、かつ個別の各情報エレメントが質問の仕様に合致し
   ているか、合致していないか、あるいは合致しているか
   も知れないかを表示するエレメントを有する第２の出力
   マップを生成するための手段と を含むことを特徴とする請求項１記載の装置。
8. 【請求項８】さらに、 (g)該第２の出力マップ内にそれらが質問の仕様に合致
   しているかも知れないことが表示されている情報ベース
   の情報エレメントのみを検査して、それらのエレメント
   のうちどのエレメントが質問の仕様に合致しているかを
   識別し、かくして質問の仕様に合致する情報ベースのす
   べての情報エレメントを識別しうるよう形成した手段 を含むことを特徴とする請求項７記載の装置。
9. 【請求項９】予め定められた数のレンジを表示するため
   の該手段は２つのコードが同じ値を持たない、即ち別個
   の特有の値を有する複数のコードを含むこと、および該
   各エレメントとそれらのエレメントがマップするレンジ
   との間の対応を決定する手段は、情報ベース内の情報エ
   レメントと同数の一連のコードを有し、該一連のコード
   の各々を該情報エレメントの各々の１つに対応させ、且
   つ該一連のコードの各々の値により各情報エレメントと
   そのエレメントの属性値がマップするレンジとの間の対
   応を決定するようにしたことを特徴とする請求項１記載
   の装置。
10. 【請求項１０】該各トポロジカルマップを該コードのア
    レイにより表示するようにしたことを特徴とする請求項
    ９記載の装置。
11. 【請求項１１】該各トポロジカルマップをビットマップ
    により表示し、各ビットマップを所定コードに対応させ
    るようにしたことを特徴とする請求項９記載の装置。
12. 【請求項１２】該情報記憶装置に記憶された複数の該情
    報エレメントは、各々順序づけ可能な値をもつ複数のデ
    ータフィールドよりなる複数のデータレコードを含み、 該トポロジカルマップは、該各フィールドに対するトポ
    ロジカルマップであって、該各トポロジカルマップを該
    情報記憶装置に記憶させるようにするとともに、該トポ
    ロジカルマップは、 (1)フィールドについて予め定められた数の値のレンジ
    を表示する別個の特有の値を有する複数のレンジコード
    で、全体としてデータベース内のすべてのレコードのフ
    ィールド値を含むレンジについてのレンジコードと、 (2)データベース内のレコードと同数のエレメントのア
    レイで、アレイ内の各エレメントはデータベース内の該
    レコードの各々の１つに対応しており、各エレメントは
    各レコードとレンジコードがマップするそのフィールド
    値との間の対応を決定するためのレンジコードをもつも
    のであるエレメントアレイと を具えたことを特徴とする請求項１記載の装置。
13. 【請求項１３】(d)記憶されたデータレコードの１また
    はそれ以上のフィールドに関する特定のパラメータ及び
    論理にもとづいた仕様を有する質問を受信するための、
    前記情報記憶装置と協働する入力装置と、 (e)質問の受信に応答し、質問に特記されたフィールド
    について記憶されたトポロジカルマップを選定し、質問
    に特記された論理に対応する関連づけ操作を選定するた
    めの手段と、 (f)選定したトポロジカルマップを使用して選定した関
    連づけ操作を実行し、質問の仕様に合致した情報ベース
    のすべてのレコードと質問の仕様に合致するかも知れな
    いデータベースのすべてのレコードからなるデータベー
    ス内のデータレコードのスーパーセットを識別するため
    の手段と を含むことを特徴とする請求項12記載の装置。
14. 【請求項１４】各々順序づけ可能な値と関係づけられる
    少なくとも１つの属性を有する複数のエレメントよりな
    る情報ベースの普遍化トポロジカルマッピングを行う方
    法において、 (a)エレメントの属性を選定するステップと、 (b)選定した属性について、予め定められた数の属性値
    のレンジで、全体として情報ベース内のすべてのエレメ
    ントに対応して選定された属性値を含むレンジを決定す
    るステップと、 (c)選定した属性について、該エレメントとそれらがマ
    ップするレンジとの間の対応を決定するトポロジカルマ
    ップを情報記憶装置に記憶させるステップと を含むことを特徴とする情報ベースの普遍化トポロジカ
    ルマッピング方法。
15. 【請求項１５】情報ベースの各エレメントは各々順序づ
    け可能な値を有する複数の関係づけ可能な属性を含むこ
    と、および該方法は該複数の関係づけ可能な属性の各々
    についてトポロジカルマップを生成記憶するための繰返
    しステップ(a),(b)および(c)を含むことを特徴とする請
    求項14記載の方法。
16. 【請求項１６】情報ベースの各エレメントはレコードま
    たはレコード群を含むことを特徴とする請求項14または
    15に記載の方法。
17. 【請求項１７】エレメントの少なくとも１つの属性に関
    する特定のパラメータおよび論理にもとづく仕様を有す
    る質問に応じて、請求項16によりトポロジカルマッピン
    グされた複数のエレメントよりなる１つの情報ベースの
    制御トポロジカル操作方法であって、 (d)質問に特記された属性に対応する請求項16により生
    成された適切なトポロジカルマップを選定するステップ
    と、 (e)質問に特記された論理に対応する関連づけ操作を選
    定するステップと、 (f)選定したトポロジカルマップを使用して選定した関
    連づけ操作を行い、質問の仕様に合致する情報ベースの
    すべてのエレメントと質問の仕様に合致するかも知れな
    い情報ベース内のすべてのエレメントからなる情報ベー
    ス内のエレメントのスーパーセットを決定するステップ
    と を含むことを特徴とする情報ベースの制御トポロジカル
    操作方法。
18. 【請求項１８】質問はエレメントの複数の属性に関する
    特定のパラメータおよび論理にもとづくものであり、こ
    のような属性に関する複数のトポロジカルマップはステ
    ップ(d)で選定するようにし、該ステップ(f)は選定した
    関連づけ操作にしたがって選定した複数のトポロジカル
    マップを組合せ、該スーパーセットを生成するステップ
    を含むことを特徴とする請求項17記載の方法。
19. 【請求項１９】情報ベース内の情報を記憶し、操作する
    方法において、 (a)各々順序づけ可能な値を有する複数の属性を持つ複
    数の情報エレメントを情報記憶装置に記憶するステップ
    と、 (b)情報エレメントの該各属性について、 (1)全体として情報ベース内のすべてのエレメントに対
    応する属性値を含む予め定められた数の属性値のレンジ
    を決定し、 (2)該エレメントとそれらがマップするレンジとの間の
    対応を決定するトポロジカルマップを情報記憶装置に記
    憶し、それにより該複数の属性の各々に対応してトポロ
    ジカルマップを生成記憶させるステップと、 (c)記憶されたエレメントの１またはそれ以上の属性に
    関する特定のパラメータおよび論理にもとづいた仕様を
    有する質問を受信するステップと、 (d)質問に特記された属性に対応する記憶されたトポロ
    ジカルマップを選定するステップと、 (e)質問に特記された論理に対応する関連づけ操作を選
    定するステップと、 (f)選定したトポロジカルマップを使用して選定した関
    連づけ操作を実行し、質問の仕様に合致した情報ベース
    のすべてのエレメントが含まれる情報ベース内のエレメ
    ントのスーパーセットを決定するステップと、 (g)このように決定されたスーパーセットを使用して情
    報ベースの記憶されたエレメントに選択的にアクセスす
    るステップ とを含むことを特徴とする情報記憶操作方法。