JPH01162927A - トランジティブクロージャ生成方法、データベース圧縮方法、データベース生成システム、データベースストア方法および情報提供システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （発明の背景） ［発明の属する技術分野］ 本発明は、データベース管理システム及びその方法に関
し、特に、使用可能なデータから新たな情報を引き出す
ことができるインテリジェント・データベースシステム
及びその方法に関する。

〔従来技術の説明］ データハ′、−ス管理システムは、従来、賃金支払い処
理、収支会計処理、及び取引処理等のデータ処理への応
用に用いられてきている。現在では、データベース管理
システムは、エキスパートデータベースシステム等の新
たな応用分野において用いられる例が次第に多くなりつ
つある。そして、それに対応して、新しいデータベース
管理システム及びそのための機器が設計されつつある。

一般に、関連データベースは、大量のエントリを有し、
各々のエントリは複数のフィールドより成り立っている
。このエントリは、しばしばレコードあるいはチュープ
ルと呼称される。データベースにおける各々のチュープ
ルは、一般に、同一順序によって配列させられた同一フ
ィールドよりなり、チュープル間の差異は、各々のフィ
ールド値である。情報は、この様なデータベースから、
比較的限られた数でかつ組合わせることによって、非常
に強力な検索を行う、基本的な、すなわちプリミティブ
なオペレーションによって引き出される。

上述のプリミティブオペレーションの一例は、あらかじ
め選択されたフィールドの値に関する″セレクト”であ
る。このオペレーションは、所定のフィールド以外の全
てのフィールドを無視し、所定のフィールドを（チュー
プルを通じて）検索して特定の条件を満たす値を見出し
、当該検索基準（あるいはその所定の部分）を充足させ
るチュープルを引き出す。

ブルミティブオペレーションの他の例として“ユニオン
”があげられる。このオペレーションは、同一フィール
ドにわたって定義されている２つのデータベースを連結
して、より大規模なデータベースを形成する。連結がな
されると、あるチュープルは２つ以上含まれることにな
る可能性があるので、“ユニオン“オペレーションの一
部には、余剰のチュープルを消去する機能が含まれる。

“ディファレンス”というプリミティブオペレーション
も２つの個別のデータベースに対して作用するものであ
るが、“ディファレンス１オペレーシヨンによって生ず
るのは、第１データベースには含まれるが第２データベ
ースには含まれないチュープルのみを含むデータベース
である。

プリミティブオペレーションのもう１つの例は、“ジョ
イン”オペレーションとして知られているものである。

このオペレーションは、２つのデータベースの内の所定
の基準を満たす部分の結合を生成する。例えば、考えて
いる２つのデータベースのそれぞれのものの特定のフィ
ールドに対してジョインが実行されると、これら２つの
データベースに含まれるチュープルの内、選択した２つ
のフィールドにおいて（値カリ一致するものが連結され
て、新しいデータベースのチュープルとなる。

勿論、選択した２つのフィールドは共通の範囲にわたる
値を有していなければならない二そうでない場合には、
一致するものは見つからない。

上述のプリミティブオペレーションを注意深く検討する
と、データベースに明白に差込まれた情報を引出すため
に当該データベースに対して正規に検索を行うことによ
って、多くの情報が得られることが明らかとなる。しか
しながら、データベースは、直接、すなわち明白に差込
まれてはいない多くの情報も有している。そのような情
報は、既知のプリミティブオペレーションによっても引
出されうるが、余り効率的ではない。例えば、第１及び
第２フイールドがその間を直結する高速道路を有する都
市名を表わし、第３フイールドが高速道路に沿った当該
２都市間の距離をあられすようなデータベースで、ある
都市から高速道路によって直結されていない都市へのル
ートを探そうとしていると考える。従来のプリミティブ
オペレーションしか使用できない場合には、このような
検索に対する解答は、大量のプリミティブオペレーショ
ンを含むプログラムによってのみ得ることができる。し
かしながら、当該データベースを効率的に操作でき、そ
の結果当該検索に対する解答が直接得られるようなプリ
ミティブオペレーションが利用可能であるならば、多く
のこれまでは困難とされてきたタスクが容易になされう
ろことになる。上述の例に対して要求される能力は、一
般に“トランジティブクロージャ”と呼称される。これ
はしばしば要求される能力である。

多くの技術者がデータベースに対するプリミティブオペ
レーションセットの拡張の必要性を認識し、その内の何
人かは、本質的にトランジティブクロージトオペレーシ
ョンであるようなプリミティブオペレーションを提案し
ている。そのような提案の例は、アール・アグラワル（
Ｒ，Ａｇｒａｖａｌ）によって提案された“アルファ”
オペレータ（“アルファ：リカーシブ倹素のクラスを表
現するための、リレーショナル代数への拡張″、第３回
データエンジニアリング関する国際会議（１９８７年２
月、カリフォルニア州ロサンゼルルス）会議録）；エイ
・ローゼンクール（Ａ、Ｒｏｓｅｎｔｈａｌ）らによっ
て提案された“トラウ゛アーザルリカージョン“オペレ
ーター（“トラヴアーザルリカージョン：リカーシブな
応用を支援するための実際的なアプローチ”、ＡＣＭ−
５Ｉ　ＧＭＯＤ１９１１１Ｂデータマネージメントに関
する国際会議（１９８８年５月、ワシントン特別区）会
議録；及び、アール・クング（Ｒ，Ｋｕｎｇ）らによっ
て提案された“＊”オペレータ（“データベースシステ
ムにおける発見的検索°、第１回エキスパートデータシ
ステムに関する国際ワークシジップ（１９８４年ｌＯ月
、サウスカロライナ州キアワ島）会議録）である。

これまで当業界において用いられてきたトランジティブ
クロージャオペレーションを達成するための方法及び技
法について記す前に、トランジティブクロージャの模式
的な代表例を以下に示す。

既に述べたように、データベースリレーションは、各々
が幾つかのフィールドよりなるチュープルの組から成り
立っている。各々のフィールドの値は、所定の範囲にわ
たって定義されている。データベースにおける複合フィ
ールドは、２つあるいはそれ以上の同時に考慮されるべ
きフィールドより成り立っている。あるデータベースリ
レーションにおける２つのフィールド（あるいは２つの
複合フィールド）が同一範囲にわたって定義されている
ことはしばしばである。この様な２つのフィールドに存
在する各々の値をノード（節点）で表わし、各チュープ
ルを、当該チュープルのフィールドに見出された２つの
値を接続する方向性リンク（すなわち矢印）として表現
すると、その様にしてできたグラフ（ノード及びそれら
を連結しているリンクの接続を表わしたもの）がデータ
ベースを表わすことになる。データベースリレーション
の各々のチュープルに関する他のフィールドは、当該グ
ラフ中のリンクにラベル付けをするために用いられる。

ちなみに、無方向性リンクではなく方向性リンクを用い
た理由は、グラフを定義するために用いた、当該リレー
ションに含まれる２つのフィールドを区別するためであ
る。

前述のグラフそのものに注目すると、そのようなグラフ
における“パス”は、当該グラフの所定のソースノード
に至る場合に通過する連続したリンクの組により成り立
っている。我々の定義によれば、グラフの“トランジテ
ィブクロージャ″とは、パスが存在する全てのノード対
間にリンクを有する新たなグラフである。元のグラフの
リンクに対して付けられたラベルは、所定の関数に従っ
て変換されて、当該トランジイブクロージャによって生
成されたリンクに対する新たなラベルとなる。あるノー
ド対間にリンクが既に存在する場合においても、しばし
ば、異なったパスを見出すことによって当該リンクに対
するラベルが、ある所定の関数に従って、変換される、
ということが起こる。データベースリレーションのトラ
ンジティブクロージャとは、与えられた元のデータベー
スリレーションのグラフのトランジティブクロージャに
対応するデータベースリレーションである。

既存のデータベースシステムにおける成功の多くは、デ
ータベースにおける種々のプリミティブオペレータをイ
ンプリメントするための効率的な方法の発見によるもの
である。同一の手本に従って、多くの設計者がデータベ
ースリレーションのトランジティブクロージャを計算す
るための方法を構築しようと試みている。これらの方法
の多くは、反復法として分類されうる。

エイ・エフ・パンシルホン（Ａ、Ｐ、Ｂａｎｃｌ　Ｉｈ
ｏｎ）によって記述された半ナイーブ法（“再帰的に定
義されたりレーションのナイーブ評価“、Ｔｅｃｈ、Ｒ
ｅｐｌ　Ｄ　Ｂ　−００４−８５、ＭＣＣ（テキサス州
オースチン））は、長さ１のパスから始めて各々の反復
において１だけ長いパスを見出す。対数的方法は、ピー
φバルジュリエズ（ＰＪａｌｄｕｒＩｅｚ）ら（“ジョ
インインデックスを用いた再帰的検索の評価“、第１１
回エキスパートデータベースシステムに関する国際会議
（１９８６年４月、サウスカロライナ州チャールストン
）会議録）及びワイ・イー・アイオアニブイス（Ｙ、Ｅ
、ｌｏｇｎｎ！ｄｉｓ）　（″リレーショナルオペレー
タのトランジティブクロージャの計算について′、第１
２回巨大データベース国際会議（１９８６年８月、京都
、日本）会議録）によって記述されている。この方法に
おいては、各々の反復の際に既知のパスの長さよりも２
倍長い長さを有するパスまでの全てを計算するものであ
る。前述の方法の改良については、ワイ・イー・アイオ
ニディス（“リレーショナルオペレータのトランジティ
ブクロージャの計算について”、第１２回巨大データベ
ース国際会議（１９８６年８月、京都、日本）会議録）
、ニー・ギュンツァ−（υ、Ｇｕｎｔｚｅｒ）ら（“効
率的差分固定点反復法による演鐸型データベースシステ
ムにちける再帰の評価について″、第３回アイ・トリプ
ルΦイー・データエンジニアリング国際会議（１９８７
年２月、カリフォルニア州ロサンゼルス）会議録）、及
びエイチ・リュー（Ｈ，Ｌｕ）（′データベースリレー
ションのトランジティブクロージャの計算に関する新し
い戦略“、第１３回巨大データベース国際会ｉ　（１９
８７年９月、英国ブライトン）会議録）によって記述さ
れている。

上述の従来技術に係る方法には２つの主要な問題点があ
る。第１に、反復法の終了はグラフの最長パスに依存し
ていて、長大パスが存在する場合には、結果を得るため
に多くの反復をしなければならない。第２に、反復法は
、特にグラフがサイクルを含む場合には美大な数の重複
を生み出しくなぜなら、ノード対間のパスが見出だされ
た場合、当該ノード対間にパスが既に存在しているかど
うかをチエツクすることは容易ではないからである）、
それらを除去するために重大な実行損失を招くからであ
る。

プール行列（すなわち、各要素が１か０であるような行
列）のトランジティブクロージャを計算するための方法
も色々と導かれている。この型のよく知られた方法は、
ニス・ワーシャル（Ｓ、Ｗａｒｓｈａｌｌ）　（″ブー
ル行列に関する定理、ジャーナル・オブ・エイシーエム
（Ｊｏｕｒｎａｌ　ｏｆ　ＡＣＭ）、第９巻第１号（１
９６２年１月）、エイチ・ニス・ワレン（１１゜Ｓ、Ｗ
ａｒｒｃｎ）　　（“二進リレーションのトランジティ
ブクロージャに対するワーシャルのアルゴリズムの修正
”、コミュニケーションズ・オブ◆エイシーエム（Ｃｏ
ｍＩｌｕｎｉｃａｔｉｏｎｓ　ｏｌ’　ＡＣＭ）、第１
８巻第４号（１９７５年４月））、及び、シー・ピー・
シュノアＣＣ，Ｐ、５ｃｈｎｏｒｒ）　（“線型期待時
間によるトランジティブクロージャのためのアルゴリズ
ム１、ニスアイエイエム　ジャーナル　オブ　コンピユ
ーテイング（ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｒ　Ｃｏａ
＋ｐｕｔｌｎｇ）、第７巻第２号（１９７８年５月））
によって記述されている。

ワーシャルのアルゴリズムに従うと、与えられたＶ個の
ノードを有するグラフに対するＶｘＶのプール行列の要
素ａｌｊ（ここで、ノードｉからノードｊへの弧が存在
する場合には、ａｌｊは１であり、そうでない場合は０
、と定義されている）に関して、そのトランジティブク
ロージャは次のように求められる： に＝１ｔｏＶ −１ｔｏＶ ｊ−ＩＬｏＶ　　について ａ　　−ａ　　Ｕ　（ａ、ｋｍ　ａｋｊ）グラフｌｊ　
　　Ｉｊ 理論の術語によれば、当該アルゴリズムは次のように書
き表わすことができる： 全てのノードｋに対して ｋの全てのプリデセッサ目こ対して ｋの全てのサクセッサｊに対して ｊをｉのサクセッサにし、ｉをｊのブリデッサにする。

当該グラフが、各々のチュープルに係る弧を表わしてい
るリレーションによって表現されるならば、ブリデセッ
サ及びサクセッサのリストを有することによる効果を得
るために、当該リレーションを２通りの方法に分類して
維持しなければならない。それゆえ、ワーシャルのアル
ゴリズムのインプリメントには、各々のノードに対して
それに関するサクセッサ及びプリデセッサのリストをフ
ェッチして、その後各々のサクセッサ（ブリデセッサ）
に対して更新可能なプリデセツサ（サクセッサ）をフェ
ッチする、という段階が必要になる。

また、例えばサクセッサリストのみを有していて、ある
ノードのプリデセッサを決定するために、毎回当該リス
ト全体にわたってスキャンすることも可能である。

ワレンは、ワーシャルのアルゴリズムがプール行列から
ランダムなビットをフェッチする段階を含んでいること
を指摘し、ビット抽出のオーバーヘッドなしにプールベ
クトルに対する直接のオペレーションを可能とするよう
な修正案を提案したが、それは、２パスとなっているニ −１ｔｏＶ ｋ−１ｔｏｉ−１ −１ｔｏＶ ａ　−ａ、しくａＩｋｎａｋｊ） Ｉｊ　　　ＩＪ −１ｔｏＶ ｋ−ｉ＋ＩＬｏＶ ｊ−ＩＬｏＶ ａｌｊ″″ａｌｊ′Ｊ（ａｌｋρａｋｊ）ワレンのアル
ゴリズムに於ける変更点は、ｉとｋのループが交換され
ているという点のみである。

しかしながら、この交換によって、いくつかのパスが見
逃されてしまい、その結果、２パスが必要となる。第２
のループインデックスの範囲の修正は、２パスであるこ
とによる損失を低減するための最適化である。各々のパ
スにおける計算は、本質的には、 全てのノードｉに対して、 ｉの、ある範囲内の全てのサクセッサｋに対して、ｋの
全てのサクセッサｊに対して、 ｊをｉのサクセッサにする。

これらの方法の問題点は、データベース全体及びトラン
ジティブクロージャの計算結果がコンピュータのメイン
メモリに収まらなければ、これらの方法がデータベース
リレーションのトランジティブクロージャの効率的な計
算に用いられない、ということである。残念ながら、既
存のデータベースの大部分は、このためには大きすぎる
。

（発明の概要） 本発明により、データベースのトランジティブクロージ
ャを、当該データベースが磁気ディスク、光ディスク、
磁気テープあるいは低速のコアメモリ等の二次記憶媒体
にストアされている場合においても、当該二次記憶媒体
へのアクセスを最小限にすることによって、効率的に得
ることができる。

この方法は、データベースを分配し、それが好ましい具
体例においては、各々のノードに対して直接に連結して
いるノードのリストが付けられているようなノードの組
という形で維持され、ある時刻においては、その１つの
組を二次記憶媒体からメインメモリに転送し、メインメ
モリに存在しない部分のデータベースへのアクセスをを
最小にするような方法でそれを処理する、という段階よ
り成り立っている。データベースの分配は、ア拳プリオ
リに決定されている必要はない。データベースの未処理
の部分がメインメモリの所定の部分に収まるだけ一分配
分としてフェッチされ、当該部分の処理中にメインメモ
リが一杯になると、現在の分配分のデータベースの一部
を放棄することによって（この部分は次の分配分に含ま
れる）、当該分配分をダイナミックに縮小する。分配分
の処理には、当該分配分の各々のノードに対して、当該
ノードを通じて間接的に連結している全てのノード対間
に直接連結を生成するという操作が含まれる。

（実施例の説明） 第１図は、以下において本発明に係る、データベースリ
レーションのトランジティブクロージャを効率的に生成
するための方法及びその装置を記述するために用いられ
る、簡単なデータベースリレーションを示している。第
１図のデータベースは５つのフィールドを有し、第１及
び第３フイールドの双方が有効パーツ番号に関して定義
されており、第２及び第４フイールドの双方がパーツ名
に関して定義され、及び第５フイールドが正整数に関し
て定義されている。当該リレーションは、基本的には、
第１フイールドで番号そして第２フイールドでその名前
が規定されたパーツが、第３及び第４フイールドで規定
された製品に用いられており、後者を１ユニツトを生産
するために必要な前者の数が第５フイールドに与えられ
ている。

前述したように、データベースの複合フィールドは、２
つ以上の同時に考慮さるべきフィールドから成り立って
いる。第１図の例においては、第１及び第２フイールド
が組み合わされて機械部品の番号と名前を与える複合フ
ィールドを形成している。同様に、第３及び第４フイー
ルドを組み合わせられうる。

第２図は、第１図に示したデータベースに対応する方向
性グラフを示し、第３図は、第２図に示したグラフのト
ランジティブクロージャを示している。第４図は、第３
図に対応するデータベースリレーションを示している。

第３図及び第４図において、リンクに対して新たなラベ
ルを生成するために用いられた関数は、新たなリンクを
生ぜしめたリンクに対する６乗加算”である。ここに示
す具体例においてこの関数を選択したのは、それが当該
データベースリレーションの元の意味を保存しているか
らである。すなわち、第５フイールドに対応するラベル
が、正確に、他のパーツの製造に直接あるいは間接に必
要なあるパーツの数を与えるからである。

一般に、データベースリレーションは汎用コンピュータ
のメインメモリに完全にストアするには大き過ぎ、必然
的に磁気（あるいは光）ディスクのような二次記憶媒体
にストアされなければならない。いつの時点においても
当該リレーションの一部のみが読み出されてメインメモ
リ上に保持される。問題となるのは、データベースリレ
ーションのトランジティブクロージャは、元のりレーシ
ョンに比べて常に大きく、一般にかなり大きいことであ
る。それゆえ、データベースリレーションのトランジテ
ィブクロージャがコンピュータのメインメモリに収まる
ことは、はとんどあり得ない。

今日のコンピュータにおいて一般に用いられている二次
記憶媒体の性質、及びコンピュータの制御と内在する高
速メモリとの相互の影響のために、二次記憶媒体及び二
次内在記憶媒体間のデータ転送にかなりの時間が必要と
なる。我々の目的は、内在メモリと二次メモリ間の転送
を低減して、データベースリレーションのトランジティ
ブクロージャを効率的に計算する装置を提供することで
ある。すなわち、我々の装置の目的は、従来からのデー
タベースを“トランジティブクロージャ完成”データベ
ースに効率的に変換することである。

我々の目的に従って、従来型データベースは二次記憶媒
体にストアされており、本発明に係るトランジティブク
ロージャ装置は第５図に示されているように、当該媒体
上のデータをアクセスし、変換を実行し、その結果束ず
る“トランジティブクロージャ完成”データベースを同
一媒体にストアする。プロセッサ２００はデータベース
１００にアクセスし、変換を実行してその結果をデータ
ベースＩＱＯに書き戻す。

我々のアプローチの要点は、二次記憶媒体へのアクセス
数を低減することであり、このことを達成するために、
本発明に係るトランジティブクロージャ計算方法おいて
は、データベースをプロセッサ２００のメモリ内に収ま
る適切なセグメントに分配し、効率的な方法でグラフに
おける全てのノードを考慮することが含まれている。こ
の様な考慮段階と関連して、本発明に係る方法において
は、（ａ）考慮中のノードに対して入射する方向のリン
クを有する全てのノードとの間のリンク及び対応するラ
ベルが、その様なリンクがまだ存在していない場合に、
生成されるあるいはくｂ）、その様なリンクが既存の場
合には、そのラベルが更新される。

更に詳細に述べれば、各々のチュープルが２つのノード
を有するリンクであるので、本発明に係る方法において
は、デスティネーションノードあるいはソースノードの
いずれかを考慮中のピボットノードとして取扱う。各々
のピボットノードに入射するリンクを有するノードと各
々のピボットノードから出射するリンクを有するノード
との間のリンクを生成することによって全体のトランジ
ティブクロージャが生成される。

既存の方法においては、データベース全体への繰返しア
クセスが必要とされたが、この必要性を可能な限り軽減
することが望ましい。それゆえ、本発明により、トラン
ジティブクロージャが以下のようにして求められる： （ａ）初期データベースｉｏｏを、第１にソースノード
に関して、次にデスティネーションノードに関してソー
ト（分類）する； （ｂ）ソートしたデータベースの一分配分をプロセッサ
２００に転送しくここで、前記データベースの一分配分
は、所定の数のピボットノードのエントリを形成する）
、当該分配骨の範囲内で情報を処理する； （ｃ）データベース１００内に残存しているリンクのそ
れぞれをプロセッサ２００へ渡し、彼転送分配分のピボ
ットノードに対する影響を考慮し、必要ならばトランシ
ティブリンクを生成する；（ｔｌ）前記分配分をデータ
ベース１００に書き戻す；（ｅ）次の分配分をデータベ
ース１００からプロセッサ２００に転送し、この手続き
を繰返す。

データベース１００のソートは、当該データベースが巨
大である場合においても困難ではない。例えば、プロセ
ッサ２００の一次メモリ内に収まる大きさのパケットに
ハツシュ（細断）シ、続いて各々のパケットをメモリ上
でソートする等の、従来からの技法が適用されうる。ピ
ボットノードがソースノードである場合には、その様な
ソートを行った後には、あるノードから出射する方向の
全てのリンクが一緒にまとめられる。実際、我々がソー
トを行なう目的が、あるノードから出射する方向の全て
のチュープルを一緒にまとめることであるから、同一結
果を生ずるような他の方法も適用されうる。

上記の段階（Ｃ）に関しては、データベース１００への
アクセスが必要とされるが、その手続きは、当該分配分
からエントリを選択し、もう１つのエントリを当該分配
分あるいはデータベースそれ自体から（データベース１
００をアクセスすることによって）選択することである
。選択されたエントリの一方は、当該エントリ対のヘッ
ドと見なされ、他方はテールと見なされる。その決定は
、ヘッドエントリのデスティネーションノードが、テー
ルエントリのソースノードと同一であるか苦力Ｖに関し
てなされる。そうであるならば、ヘッドエントリのソー
スノードからテールエントリのデスティネーションノー
ドへのチュープルが生成される。

エントリが生成された場合には、以下に記述されるよう
に、当該ノード対間に存在する他の１）ンクに対して（
それが存在する場合には）のラベル付けを含んで、全て
のフィールドが埋められる。但し、上述のようなノード
に対する検討を無思慮に行なうような手続きにおいては
、データベース１００に対する美大な回数のアクセスが
必要とされる。しかしながら、本発明に係る方法に従え
ば、各々のノード対に関して一度考慮すれば十分である
。　各々のノード対に関して一度考慮すれば、グラフに
関する完全なトランジティブクロージャが生成される、
ということの保証は、以下の２つの拘束条件より理解さ
れる。

拘束条件１：全てのソースノードに対して、デスティネ
ーションノードは段階（Ｃ）が適用されるリンク選択に
おけるのと同一の順序で考慮されなければならない。

拘束条件２：リンクＩＪ　（ソースノード１１デステイ
ネーシヨンノードｊ）に対して段階（Ｃ）が適用される
以前に、段階（Ｃ）が既に、ソート類でｊより前に現れ
る全てのノードｋに対するリンクｊｋに対して適用され
ていなければならない。

我々は、上記の２つの拘束条件を満足する全ての順序が
用いられうろことを見出した：そして、それを例示する
ために、以下に、グラフ中のノード対に対する段階（Ｃ
）の適用のための３つの異なった方法を示すことにする
。

第１の方法（第５図） ［第１段階（ブロック１０］ データベース１００にプロセッサ２００を相互作用させ
てサクセッサリストを生成する。詳細に述べれば、デー
タベース１００の各々のノードｉに対して、ノードｉが
ソースノードであるようなデスティネーションノードを
規定するリストを生成する。

データベースが最初にストアされるフィールドがソース
ノードフィールドである場合には、この段階は必要では
ない。なぜなら、ソーティング処理によって全てのリン
クが共通のソースノードに対してデータベース中に順次
ストアされているからである。

［第２段階（ブロック２０）］　　プロセッサ２００に
（ソートされたリスト中で）未だ処理されていない最上
位の分配分を転送する。被転送性配分の大きさは、プロ
セッサ２００の一次メモリの大きさ及び共通のソースノ
ードを共有しているリンクの数に依存する。プロセッサ
２００が新リンクを生成し、それらの内の幾つかが、現
在分配分に加わることになるので、一般には使用可能な
メモリの内、約５０％分程に転送されのみである。この
数値は、以下に述べる相反する２点に留意した上で、必
要な場合には、他の全ての段階においても選択されうる
ニ一方では、初期状態でメモリをあまりにも大息に占を
してはならない：なぜなら、収まりきる以上の数のリン
クが生成されると、その生成されたリンクに対して必要
なストレージ領域を確保するために実質的な計算のオー
バーヘッドが要求されるからである。他方、初期状態で
あまりにも少量のメモリしか占有しないことは避けなけ
ればならない；なぜなら、−分配分を大きくとることに
よって反復回数が減少し、その結果、処理速度が向上す
るからである。

［第３段階（ブロック３０）］ 前記転送した分配分内の各々のノードｊに対して、順次
当該付配分内における当該ノードｊをデスティネーショ
ンノードとするような全てのリンクを考える。その様な
リンクの各々に対して、当該リンクのソースノードから
ノードｊがソースノードであるようなリンクによって連
結されたデスティネーションノードの各々へ向かうリン
クを生成する。

［第４段階（ブロック４０）］ データベース１００の、現在分配分には含まれない全て
のノードのプロセッサリストを順次リードする。そのよ
うなノードにの各々に対して、それが、現在分配分向の
ソースノードであるようなノードｉに向かうようなリン
クのソースノードであるか否かを決定する。そうである
場合には、ノードにとノードｉの全てのプロセッサであ
るノードｊとの間のリンクを生成する。ちなみに、１Ｊ
ンクが生成されると、それはデータベースにストアされ
る。ソートされた状態を維持するために、生成されたリ
ンクのストアは挿入の形でなければならない。このこと
は、従来技術にかかる方法によって実現される；例えば
、挿入ソーティングとして知られている技法によってで
ある。生成された各々のエントリを直ちにストアするの
ではなくて、エントリがある数だけ生成されるまで、あ
るいは当該分配分の処理が完了するまで、ストアを延期
することも可能である。

［第５段階（ブロック５０）］ 各々の分配分に対して第３段階及び第４段階を繰り返す
。

第６図は、第４段階をより詳細に記述したものである。

第６図に従って、処理が完了していない、すなわちデー
タベース１００のノードに全てにわたる考慮が終了して
いない場合には、ブロック４１において、制御がブロッ
ク４２に移されることによって、処理が続行される。ブ
ロック４２では、プロセッサ２００内に現時点で存在し
ている分配分内には存在しないノードｋに対するプロセ
ッサリストをデータベース１００から読み出す。ブロッ
ク４３及び４４の組み合わせにより、ノードにの全ての
プロセッサノードが考慮される。ブロック４５において
は、ノードにの現在考慮中のプロセッサが実際には現時
点でプロセッサ２００内に存在している分配分内のノー
ド、例えばノード１１であるか否かが決定される；そし
て、そうである場合には、ブロック４Ｇにおいてノード
ｋからノードｉのプロセッサへの必要なリンクが生成さ
れ及び／あるいは更新される。ノードにの各々のプロセ
ッサが考慮された後には制御はブロック４３に戻る；そ
して、ｋのサクセッサ全てが考慮された後には、ブロッ
ク４３からブロック４１に制御が復帰する。

第２の方法（第７図） Ｔ５１の方法に係るデータ処理においては、各々のノー
ドのプロセッサリストがプロセッサ２００に読み込まれ
（第４段階）、その時になって初めてリンクが生成され
なければならないか否かが決定される。ここに示す第２
の方法によれば、通例前記ソーティング処理の結果生じ
るプロセッサリストに加えて、各々のノードのプリデセ
ッサを規定する（ソースノード及びデスティネーション
ノードに関する情報のみを保持している）プリデセッサ
リストが生成されて維持される（データベース１００内
に、あるいは容量が足るならばプロセッサ２００内に）
。このプリデセッサリストは、データベース１００をデ
スティネーションノードに関してソートすることによっ
て生成される。当該プリデセッサリストは、リンクが生
成されないようなノードに関するプロセッサリストへの
アクセスの必要性を除き、それによって、データベース
１００へのアクセス数を更に低減する。

新たなリンクが生成される場合に、プリデセッサリスト
及びプロセッサリストは、双方共、維持されていなけれ
ばならないことに留意されたい。

サクセッサリストに関しては、現時点でプロセッサ２０
０内に存在する分配分内のあるノードに対するサクセッ
サリストがプリデセッサリスト内のエントリによって指
示された通りに、プロセッサ２００内に読み込まれた場
合、生成されたリンクに関するサクセッサリストへの挿
入ソーティングは直ちに実行される；なぜなら、サクセ
ツサリストは、プロセッサ２００内に存在するからであ
る。他方、プリデセッサリストは直ちには更新されない
；なぜなら、新たなプリデセッサリストがプロセッサ２
００内のメモリ内に読み込まれなければならないからで
ある。一般に、プリデセツサリストは第４段階の終了時
に更新される。プリデセツサリストの生成及びその更新
は、第６図のブロック１５及び５５に示されている。第
７図のブロック４９には、第５図のブロック４０と同一
の字句が記入しであるが、第８図に示すように、第７図
ブロック４９の手続きは、ブロック４０のそれとは若干
具なるものである。

第８図においては、ブロック４１に引続いて決定ブロッ
ク４７がおかれ、そこにおいてプリデセッサリストが用
いられる。ノードｋが、現時点でプロセッサ内に存在す
る分配内のあるノードのサクセッサリストに属している
場合のみ、制御がブロック４２に移る。

第３の方法（第９図） 第１の方法及び第２の方法は、ソースノードをピボット
ノードと考え、分配分内の各々のリンクに対して、考慮
中のソースノードをデスティネーションノードとして有
するような他のリンクがデータベース内に存在するか否
かということを問題にしてきた。ここに示す第３の方法
では、デスティネーションノードをピボットノードと考
え、考慮中のデスティネーションノードをソースノード
として有するようなリンクをデータベース中で検索する
。

この第３の方法においては、第１の方法の第３段階から
第５段階までが以下に示すステップによって置換される
。

［第３段階（ブロック７０及び第１０図）］以前に処理
した分配分に属する各々のノードｊに対して、現時点で
プロセッサ２００内に存在する分配分内に、あるノード
ｌからノードｊへのリンクが存在する場合には、ノード
ｊのサクセツサリストを読み込み、ノードｉとノードｊ
のサクセツサリスト内のデスティネーションノードとの
間の全てのリンクを生成する。この段階は、当該分配分
内の１つのエントリのデスティネーションノードを、当
該分配分内の他のエントリが同一デスティネーションノ
ードを有しているか否か観察することによって増強され
る。

［第４段階（ブロック３０）］ ノードｊが現時点でプロセッサ２００内に存在する分配
分に属している場合には、考慮中のリンクのソースノー
ドから、ノードｊがソースノードであるリンクのデステ
ィネーションノードの各々へのリンクを生成する。

［第５段階（ブロック２Ｏ−８０−５０）　］全ての分
配分が一度処理された後、当該処理が繰返され、第１パ
ス（の第３段階及び第４段階）で考慮される対象となら
なかった全てのノードｊについての考慮がなされる。こ
こで、サクセッサリストの大きさが変化したために、一
般には、第２パスにおける分配分と第１パスにおける分
配分とが異なることに留意されたい。

第１の方法及び第２の方法においては、分配分によって
メモリの５０％が占有されることが合理的であったが、
第３の方法においては、プロセッサ２００内に存在する
分配分のみが拡張されていくので、それより小さな数値
が恐らくより適切であることにも留意されたい。

上述した３つの方法の全てにおいて、基本となるポイン
トは、与えられたデータベースが分配され、かつ、処理
がプロセッサ内に存在しない分配分内のチュープルに対
する参照を住かに押さえて実行される点である。処理が
進行するにつれて新たなリンクが見出だされ、プロセッ
サ内に存在する分配分の大きさが大きくなっていくこと
が期待される。既に述べたように、ある場合には分配分
が大きくなり過ぎてメモリ内に収まらなくなる。

その様な場合には、メモリ内に存在する分配分のプロセ
ッサリストの最後のものを削除して、次の分配分に含ま
せるようにする。

プロセッサ２００のメインメモリが一杯になってしまう
ことは、本発明に係る方法においては、同等破局を引き
起こすことはないが、メインメモリから削除されなけれ
ばならなかったプロセッサリストは、メモリ上の分配分
と共に読み込まれたが無駄になってしまった、というこ
とを意味していることは明らかである。そのような読み
込合におけるロスを最小にするために、新たに読み込ま
れる分配分の大きさは、メモリの一部のみを占め、それ
が大きくなることを許容できるものでなければならない
。

′Ｔ５１図のデータベースについて考える。トランジテ
ィブクロージャを生成するために第１の方法を適用し、
最初の２つのチュープルのみが第１分配分を成している
とする。第３段階による修正は、生じない。残存してい
るチュープルの各々が読み出され、メモリ上の分配分に
は含まれず、“キャパシダをそのデスティネーションと
するようなチュープルが存在しないか否かが決定される
。そして第４段階による修正は生じない。続いて次の分
配分、すなわち次の３つのチュープルからなる分配分が
読み込まれる。“マイクロプロセッサ”から“コントロ
ーラ°へのリンク及び“コントローラ１から“ワークス
テーション”へのリンクが存在するが、共にメモリ上の
分配分内に存在するので、新たなリンク、“マイクロプ
ロセッサ“→“ワークステーション”、が生成される。

“マイクロプロセッサ”及び“コントローラ０の双方が
、“インフォメーションステム２へのリンクを有する“
ワークステーション”へのリンクを持つため、これら双
方のノードから“インフォメーションシステム″へのリ
ンクが生成される。第４段階に進み、“キャパシタ０か
ら“コントローラ”へのリンクが見出されるので、“キ
ャパシタ”から“コントローラ”のプロセッサの各々へ
のリンクが生成される。このようにして処理を続行する
ことによって、第４図に示されているような、トランジ
ティブクロージャ完成データベースが得られる。

第２の方法は、本質的に同一の様式で作用する。

留意すべき主要な点は、第１分配分が一部メモリにある
場合には、他の分配分内にあるチュープルは一部メモリ
上に読み込まれる必要がない、という点である。なぜな
ら、“キャパシタ“のプリデセッサリストより直ちに“
キャパシダをデスティネーションノードとするようなチ
ュープルが存在しないことが理解されるからである。

第３の方法は、第１分配分に対しては、第１の方法と同
様に作用する。第２分配分がメモリ上にある場合には、
既に、処理した分配分内のリンクのみが“キャパシダを
ソースノードとして有し、一方で”キャパシタ゛はメモ
リ上にある分配分のどのリンクのデスティネーションノ
ードでもないので、第３段階においてはデータベースの
修正は生じない。第４段階は第１の方法の第３段階と同
一である。最後の第３分配分は第１図のデータベースの
最後の２つのチュープルを有している。第３段階を適用
することによって、既に処理したソースノード“ワーク
ステーション１を有するチュープルが見出される。この
チュープルのデスティネーション“インフォメーション
システム”は、“デイスプレィ”をソースノードとする
新たなチュープルのデスティネーションであり、それは
メモリ上の分配分内の“ワークステーション”をデステ
ィネーションノードとして有するチュープルのソースノ
ードである。第４段階を適用することによって、“デイ
スプレィ２のプロセッサが“グラフィックス”のプロセ
ッサとされる。このことによって第１パスは完了する。

第２パスでは、第１分配分がメインメモリに読み込まれ
て、今度は“コントローラ”及び“グラフィックス”の
サクセッサ全てが“キャパシタ２のプロセッサとされる
。第２及び第３分配分には変更がなされない。以上より
、第４図に示すトランジティブクロージャ完成データベ
ースが得られる。

［ラベル処理コ 既に述べたように、データベースの各々のチュープルは
幾つかのフィールドより成り立っている。

上述の議論は、主として、データベースのグラフによる
表示においてソースノード及びデスティネーションノー
ドとなる２つの単一あるいは複合フィールドに関するも
のである。ソースノード及びデスティネーションノード
に加えて、各々のチュープルには他のフィールドがあり
、それらは３つのグループに分類されうる；ソースノー
ドのみに関するフィールド、デスティネーションのみに
関するフィールド、及びソースノードとデスティネーシ
ョンノードとの間の関係を特徴付けるフィールドある。

例えば、第１及び第２フイールドがそれぞれ２つの都市
を規定し、第３及び第４フイールドがそれぞれ、各々の
都市の空港の大きさを規定し、２都市間の距離が第５フ
イールドのフィールド値であるようなデータベースにお
いては、各フィールドが属するカテゴリーは明らかであ
る。

トランジティブクロージャの作成に伴って生成されたチ
ュープルのソース及びデスティネーションノード以外の
フィールドの処理に関して問題が生じる。

本発明に従うと、新たなチュープルが生成された場合、
当該新チュープルのソースノードを生成したノードに関
するフィールドが、当該ソースノードに関するフィール
ドに複写される。デスティネーションノードに関するフ
ィールドについても同様である。ソース及びデスティネ
ーション間の関係を特徴付けるフィールドは、多くの相
異なる方法によって導出されうる。一般に、そのような
フィールドは、新たなリンクの生成に関与したリンクに
対応した、チュープルについてのある特定の関数として
記述されうる。同一のソース及びデスティネーションノ
ード間に多重経路（すなわち、一連の連結されたリンク
よりなる経路）が見出された場合には、それぞれの関係
フィールドに適切な値を有する多重経路が同一ソース−
デスティネーション対間に生成される、あるいは、単一
のリンクのみが生成されて、各々のパスに対して導かれ
たフィールドの値のある関数として、関係フィールドの
フィールド値が独立に得られる。例えば、前述の都市の
例においては、各々の経路に対する距離のフィールドが
、最も論理的に、各々のその経路を構成しているリンク
の距離フィールドの総和として計算される。ある場合に
は、最終的に生じるリレーションにおいて可能な経路及
び距離の全てを保持しておく必要が生ずる。しかしなが
ら、より一般的には、可能な経路の各々に関するフィー
ルド値の中から距離フィールドのフィールド値を選択す
る“最小″関数を用いて、各々の都市対に対して単一の
チュープルを保持しておくことが必要となる。

［データベース圧縮］ 今までに述べたことより、トランジティブクロージャ完
成データベースは、元のデータベースよりも大きく、し
ばしば非常に大きい、ということが容易に認識される。

その大きさがより大きくなるにもかかわらず、それは当
該リレーションについての全ての情報を含んでいる訳で
はない。例えば、元のデータベースにおいて２つのノー
ド間に経路が存在することを示すために、当該ノード間
にリンクが生成される；ところが、トランジティブクロ
ージャ完成データベースは当該経路を特定しない。他方
、そのような経路が存在するか否かのみに興味がある場
合がしばしばあり、実際その経路に係るラベル（例えば
費用）には、それほど興味がない場合がある。しかしな
がら、全ての場合において、トランジティブクロージャ
が適用されるシステムのニーズがあると、生成されるデ
ータベースを可能な限り圧縮することには利点がある。

主要な要求が２つのノード間の経路が存在することを知
る、という応用例においては、本発明に係る圧縮技法に
よって元のデータベースよりもしばしば小さいデータベ
ースが得られる。当該方法は、３つの段階から成り立っ
ている。第１段階においては、データベースを表現して
いるグラフが最小限のチェーンに分割される。ここでチ
ェーンとは、あるソースノードから他のソースノードへ
の経路である。この目的を達成するにあたって、あるノ
ードが２本以上のチェーンに属することは許されている
。第２段階においては、チェーン上のノードが、そのチ
ェーンにおける出現順に従って、番号が付けられる。最
後の第３段階においては、各々のソースノードが、当該
ソースノードから達する全てのチェーンのデスティネー
ションノードの内の最小の番号を持つもののみと関係付
けられる。

ソースノードに関するリンクの内の住かの部分のみがス
トアされる必要がある、ということから、圧縮が実現さ
れる。

一度、圧縮した形のストレーシスドラクチャが生成され
ると、ある与えられたノードＡが他の与えられたノード
Ｂへのリンクを当該トランジティブクロージャにおいて
有するか否かが、ノードＡが、あるチェーン上でノード
Ｂより、その位置番号によって決定されるように、先に
現れるあるノードＣに対するリンクを有するか否かをチ
エツクすることによって、決定されるようになる。

例えば、第２図のグラフ（あるいは第３図のグラフ）を
用いて、各々のノードが少なくとも一方の上にあるよう
な２本のチェーンを生成することができる。第１チエー
ンは１マイクロプロセッサ−コントローラーワークステ
ーション−インフォメーションシステム“、第２チエー
ンは“キャパシターグラフィックス−デイスプレィ”と
いうようになるであろう。ここで“キャパシタ１ノード
について考慮する。第３図において、当該ノードから出
射する５つのリンクの内、１つのみが明白にストアされ
る必要がある二　″コントローラ”ノードへのリンクで
ある。キャパシタがデイスプレィの製造に用いられてい
るか否か、すなわち第３図において“キャパシタ“ノー
ドから“デイスプレィ”ノードへのリンクが存在するか
否かが検索された場合には、肯定的な応答がなされる。

なぜなら“デイスプレィ”は第２チエーンの“キャパシ
タ”の後に現れるからである。と同様に、キャパシタが
ワークステーションの製造に用いられているか否かが検
索された場合には、肯定的な応答がなされる。なぜなら
、第１チエーンにおいて“ワークステーション１ノード
より前に現れる。

“コントローラ１ノードへの“キャパシタ１ノードから
のリンクが存在するからである。しかしながら、キャパ
シタがマイクロプロセッサの製造に用いられるか否か問
われた場合には、否定的な応答がなされる。なぜなら、
“キャパシタ１ノードから、“マイクロプロセッサ“ノ
ードあるいはチェーン上で“マイクロプロセッサ１より
前に現れるノードへのリンクが存在しないからである。

上述の例では、あるノードから他のあるノードへのリン
クが存在するか否かを決定することが可能であったが、
そのようなリンクにどんなラベルがついているかを言う
ことができなかった。言い換えれば、キャパシタが実際
にワークステーションの製造に要求されていることは確
認されたが、各々のワークステーションの製造にいくつ
用いられるのかを決めることができなかった。

到達情報のみではなく、経路及びそのラベルも重要とな
る応用例においては、異なった圧縮技法が用いられる。

本発明に係る方法によれば、各々のソースノードに対し
である表が関係付けられるる。その表の各々のエントリ
は３つの領域から成り立っている：（１）デスティネー
ションノード、（２）ソースノードからこのデスティネ
ーションノードへの経路上で第１跳躍点として用いられ
るべきノード、及び（３）この経路のラベル。あるソー
スノードとあるデスティネーションノードとの間に多重
経路が存在し、全ての経路が同−第１跳躍点を経由する
場合には、前述の表には唯一つのエントリしかないこと
になる。他方、あるソースノードとあるデスティネーシ
ョンノードとの間に多重経路が存在して、その各々が相
異なる第１跳躍点を経由するならば、経路数と同じ数の
エントリが表に存在する。

ここに示したストラフチャは、ソースノードに関する表
においてデスティネーションノードの内チェーンにおい
て最も前に置かれているエントリのみをソーティングす
ることによって更に（前述の３段階からなる方法に従っ
て）圧縮される。それゆえ、同一チェーン上に２つのデ
スティネーションが置かれていて一方が他方よりも前で
あるならば、先に表われるノードに対するエントリのみ
が表に存在することになる。

［システムの応用コ 本発明に係るトランジティブクロージャ作成法及びその
装置には、輸送業、遠距離通信産業、建設業、生産コン
トロール、あるいはエキスパートシステム等の無数の応
用例が考えられる。例えば、航空産業においては、種々
の都市間直行便の基本的なデータベースが維持されてい
る。そこにトランジティブクロージャオペレータを作用
させることによって、データベースにおける全ての、そ
の間に直行便を有するあるいは有しない、２都市間の経
路情報が得られる。遠距離通信産業においては、地点間
の直結基幹中継線の信頼性及びその容量についてのデー
タベースが存在する。そのようなデータベースにトラン
ジティブクロージャオペレータを作用させることによっ
て、２つの交換センター間の最も信頼できる中継線及び
当該交換センタの総容量を決定することができる。建設
業においては、アクティビティに関するデータベースが
用いられ、それにトランジティブクロージャオペレータ
を作用させることによって、クリティカルパスを決定す
ることができる。（ＰＥＲＴチャートの方法で）。例え
ば、自動車のような複雑なシステムの製造に関する部品
の管理においては、トランジティブクロージャを生成す
ることによって、ある部品を組み立て、製品に適切な費
用を付けるのに必要な材料及び情報に関するリストが得
られる。エキスパートシステムのインプリメントに関連
して、エキスパートシステムにおいては、エントリ間の
関係を表現するために、しばしば、インへりタンスヒエ
ラルキーが用いられていることに留意されたい。例えば
、あるエキスパートシステムにおいては、あるエントリ
が“弁理士は人間である”ということを述べ、他のエン
トリが“人間は呼吸する”ということを述べているかも
知れない。ここにトランジティブクロージャオペレータ
を作用することによって、“弁理士は呼吸する′という
叙述が生成される。

第１１図は、本発明の原理に係るシステムの構成を示し
たものである。第１１図においては、航空機の予約シス
テム等の分散型のデータアクセスシステムが示されてい
るが、本発明に係るシステムは、他の多くの応用例にお
いて用いられるものである。

第１１図においては、データベース管理システム３００
に接続された、複数の検索用ターミナル４００が存在し
、これらはデータベース管理システム３００に接続され
ている。。航空機予約システムにおいては、ターミナル
４００は、航空会社のカウンターあるいは旅行社の予約
係のためのアクセスポイントである。ターミナル４００
から検索は時々、データベースの２つのフィールド上の
トランジティブクロージャを必要とする情報が必要とな
る。、データベース管理システム３００はデータベース
１００とコミュニケートし、データベース１００トラン
ジテイブクロージヤ生成器２００とコミュニケートする
。トランジティブクロージャ生成器２００には、ターミ
ナル５００が接続されている。ターミナル５００は航空
機予約操作制御センターにあり、データベース１００に
おける基本的情報に影響を及ぼす情報を与える。この情
報は、都市から都市への便の基本的変更、天候その他に
よるキャンセル便に関する変更、あるいはある便に関す
る過剰予約等のより一時的な情報である。言い換えれば
、ターミナル５００はトランジティブクロージャ生成器
３００に対してデータベース１００内の基本的データベ
ース情報のトランジティブクロージャ完成データベース
への変換を開始させる能力を有する。

データベース管理システム３００は、ユーザの要求を満
足するものであればどのようなデータベース管理システ
ムであっても構わない。従来技術において知られている
管理システムは数多くあるので、ここでは、データベー
ス管理の複雑さについて探求しない。トランジティブク
ロージャ生成器２００に関しては、既に述べた第５−１
０図に示した流れ図における記述より、生成器２００に
必要とされる機能は、従来のデジタルコンピュータによ
って効率的に実現されることが理解される。第１１図の
システムにおいては、オフィシャル・エアーライン・ガ
イド（北アメリカ版）のトランジティブクロージャの生
成が、従来のデジタルコンピュータを用いて、実質的に
１時間以内になされることが期待される。より速い処理
速度が必要な場合には、生成器２００は、第１１図に示
すように、特定機能志向のハードウェアによって容易に
実現される。

特定機能ハードウェアによるトランジティブクロージャ
生成器２００の実現に関して、ブロック２１０はデータ
ベース１００とコミュニケートし、その唯一の機能はデ
ータをソートすることである。

ソーティングは、２組のレジスタ、１つのコンパレータ
、ある大きさのメモリ及び制御回路を用いて従来技術に
係る方法によってなされる。

生成器２００には、処理中の各々の分配分がストアされ
るメモリ２２０、メモリ２２０にストアされたデータに
対応するチュープル分析生成装置２３０及び制御信号生
成ブロック２４０が含まれる。装置２３０のチュープル
分析部は、最も望ましいのは、ストアされたプログラム
によって制御されるデバイス、例えばマイクロプロセッ
サ、であり、−刃装置２３０のチュープル生成部は、組
み合わせ回路である。

以上の記述及び本発明の原理に係る３つの方法更にはそ
れを行なうための装置は、模式的なものであって、本発
明の原理を開示し、当業者に本発明を利用させることを
意図したものである。″ソースノード“と“デスティネ
ーションノード”の意味を逆転させる等の変更がなされ
うるが、それらは全て本発明の精神及びその範鴫に含ま
れるものである。

【図面の簡単な説明】

第１図は、デーベースを模式的に示した図；第２図は、
第１図のデータベースをグラフ表示した図； 第３図は、第２図のグラフのトランジティブクロージャ
を示した図； 第４図は、第３図のグラフに対応するデータベースを示
した図； 第５図は、本発明の原理に係る１つの方法を示した図； 第６図は、第５図においてブロック４０で表わした部分
の詳細を示した流れ図； 第７図は、本発明の原理に係る第３の方法を示した図； 第８図は、第７図においてブロック４９で表わした部分
の詳細を示した流れ図； 第９図は、本発明の原理に係る第３の方法を示した流れ
図： 第１Ｏ図は、第９図においてブロック７０で表わした部
分の詳細を示した流れ図；及び 第１１図は、本発明に係るトランジティブクロージャ生
成器を含むデータベースシステムの実行例を示した図で
ある。 出　願　人：アメリカン　テレフォン　アンド手続補正
書坊均 平成１年２月　９日

Claims (26)

【特許請求の範囲】
1. （１）二次メモリ、及び一次メモリを有するコントロー
   ラよりなるシステムにおける、 前記二次メモリにストアされたデータベースのトランジ
   ティブクロージャの一部分を生成する方法において、 前記データベースは複数のエントリを含み、当該エント
   リの各々は複数個のフィールドを有し、前記データベー
   スの所定の属性に割当てられており、 前記フィールドの各々における信号値が当該エントリに
   対する、対応する属性に係る値を規定し、前記トランジ
   ティブクロージャがソースノードと呼称される前記デー
   タベースの所定のフィールド及びデスティネーションノ
   ードと呼称される前記データベースの所定のフィールド
   とに関して生成されるトランジティブクロージャ生成方
   法において、 当該方法が、 前記データベースにおける前記ノードの順序付けを行な
   う段階； 前記データベースを分割して、前記二次メモリより当該
   分配分を読み出し、それを前記一次メモリに配置する段
   階、 ここにおいて、前記分配分は、前記データベース内の、
   ある選択されたソースノードの組を共有するエントリ全
   てを含む； 前記分配分から、及び前記分配分あるいは前記データベ
   ースのいずれかから、それぞれ１つずつのエントリを選
   択して、それらの一方がヘッドエントリ及び他方がテー
   ルエントリとなるようにし、前記データベースの前記ト
   ランジティブクロージャに対するエントリを、前記ヘッ
   ドエントリのソースノードがソースノードで、前記テー
   ルエントリのデスティネーションノードがディステネー
   ションノードとなるようにして生成する段階、ここにお
   いて、前記ヘッドエントリのデスティネーションノード
   は、前記テールエントリのソースノードと同一である；
   及び 当該データベース全体に対する処理が終了するまで、前
   記分割及び読み出し段階を繰返す段階；よりなることを
   特徴とするトランジティブクロージャ生成方法。
2. （２）前記分配分の内の少なくとも１つが、複数のソー
   スノードよりなる所定の組より構成されていることを特
   徴とする特許請求の範囲第１項に記載のトランジティブ
   クロージャ生成方法。
3. （３）前記選択段階が、次の条件（ａ）、（ｂ）（ａ）
   前記順序付けにおいて、ｋがｊより小であるところの、
   ソースノードｉ及びデスティネーションノードｋを有す
   る全てのエントリが、既にヘッドエントリとして選択さ
   れており、及び （ｂ）前記順序付けにおいて、ｋがｊより小であるとこ
   ろのソースノードｊ及びデスティネーションノードｋを
   有する全てのエントリが、既にヘッドエントリとして選
   択されている、 を満たすようなソースノードｉ及びデスティネーション
   ノードｊを有するヘッドエントリを選択することのみ適
   用されることを特徴とする特許請求の範囲第１項に記載
   のトランジティブクロージャ生成方法。
4. （４）エントリ生成段階の終了後に、生成されたエント
   リを前記二次メモリ内に順にストアする段階を有するこ
   とを特徴とする、特許請求の範囲第１項に記載のトラン
   ジティブクロージャ生成方法。
5. （５）各々の前記分配分におけるソースノードの前記所
   定の組の大きさが、前記一次メモリのメモリサイズにお
   ける所定の部分以上を占有しないように選択されている
   ことを特徴とする特許請求の範囲第１項に記載のトラン
   ジティブクロージャ生成方法。
6. （６）更に、前記エントリ生成段階に応じて、生成され
   たエントリの数に従ってソースノードの前記選択された
   組の大きさを変化させる段階を有することを特徴とする
   特許請求の範囲第１項に記載のトランジティブクロージ
   ャ生成方法。
7. （７）更に、前記エントリ生成段階によって、前記デー
   タベース中にソースノードとデスティネーションノード
   との間の２つの経路が生じた場合に、ラベルを更新する
   段階を有することを特徴とする特許請求の範囲第１項に
   記載のトランジティブクロージャ生成方法。
8. （８）前記エントリ生成段階が、 前記分配分内のノードの処理を行なう段階、及びそれら
   に引続く、前記分配分内に存在しないノードを処理する
   段階； よりなることを特徴とする特許請求の範囲第１項に記載
   のトランジティブクロージャ生成方法。
9. （９）前記分配分内のノードを処理する前記段階が、Ｋ
   を所定の定数とした場合に、 前記分配分から、ソースノードｉ及びデスティネーショ
   ンノードｊを有し、その積和ｉ＋ｊＫが、前記分配分内
   のまだ選択されていない全てのエントリに対する最低の
   積和となるヘッドエントリを選択する段階Ａ； 段階Ａによって選択されたヘッドエントリのデスティネ
   ーションノードと同一のソースノードを有する、前記分
   配分内のテールエントリを選択する段階Ｂ； 当該ヘッドエントリのソースノードと同一なソースノー
   ド、及び、当該テールエントリのデスティネーションノ
   ードと同一なデスティネーションノード、を有する新し
   いエントリを生成する段階Ｃ； 前記段階Ａによって選択されたヘッドエントリのデステ
   ィネーションノードと同一なソースノードを有する、他
   のテールエントリが前記分配分内において見出された場
   合に、段階Ｂ及びＣを繰返す段階Ｄ；及び 前記分配分内において他のヘッドエントリが見出された
   場合に段階ＡからＤを繰返す段階Ｅ；よりなることを特
   徴とする特許請求の範囲第８項に記載のトランジティブ
   クロージャ生成方法。
10. （１０）前記分配分内に存在しないノードを処理する前
    記段階が、前記分配分内に存在しないソースノードＡを
    選択する段階Ａ； 当該選択されたソースノード、及び、前記順序付けにお
    いて、まだ考慮されておらず、更に前記分配分内にソー
    スノードとして存在する、最も早く現れるデスティネー
    ションノード、を有するヘッドエントリを選択する段階
    Ｂ； 当該ヘッドエントリのソースノードと同一なソースノー
    ド、及び、当該テールエントリのデスティネーションノ
    ードと同一なデスティネーションノード、を有する新し
    いエントリを生成する段階Ｃ； 前記段階Ｂによって選択されたヘッドエントリのデステ
    ィネーションノードと同一なソースノードを有する、他
    のテールエントリが前記分配分内において見出された場
    合に、段階Ｃを繰返す、段階Ｄ； 前記段階Ｂにおいて他のヘッドエントリが見出された場
    合に段階ＢからＤを繰返す段階Ｅ； 前記分配分内に存在しない全てのソースノードが処理さ
    れるまで段階ＡからＥを繰り返す段階Ｆ；よりなること
    を特徴とする特許請求の範囲第８項に記載のトランジテ
    ィブクロージャ生成方法。
11. （１１）前記トランジティブクロージャ生成方法が、更
    に、各々のノードに対する、当該ノードがソースノード
    であるところの全てのエントリを規定している、サクセ
    ッサリストを維持する段階を有し、前記サクセッサリス
    トが、１つのエントリを前記分配分内より、更に１つの
    エントリを前記分配分あるいは前記データベースより選
    択する前記段階の実行の際に用いられることを特徴とす
    る特許請求の範囲第１項に記載のトランジティブクロー
    ジャ生成方法。
12. （１２）前記トランジティブクロージャ生成方法が、更
    に、各々のノードに対する、当該ノードがソースノード
    であるところの全てのエントリを規定している、サクセ
    ッサリストを維持する段階；及び各々のエントリに対す
    る、当該ノードがデスティネーションノードであるとこ
    ろの全てのエントリを規定している、プリデセッサリス
    トを維持する段階；を有し、 前記サクセッサリスト及びプリデセッサリストが、１つ
    のエントリを前記分配分内より、更に１つのエントリを
    前記分配分あるいは前記データベースのいずれかより、
    選択する段階の実行の際に用いられることを特徴とする
    特許請求の範囲第１項に記載のトランジティブクロージ
    ャ生成方法。
13. （１３）前記エントリ生成段階が、 ソースノードが前記ヘッドエントリのソースノードであ
    り、デステネーションノードが前記テールエントリのデ
    スティネーションノードであるような、既存のエントリ
    のラベルを修正する段階を有することを特徴とする特許
    請求の範囲第１項に記載のトランジティブクロージャ生
    成方法。
14. （１４）前記トランジティブクロージャ生成方法が、更
    に、あるソースノード及びあるデスティネーションノー
    ドを有するエントリのラベルを、同一のソースノード及
    び同一のデスティネーションノードを有する他のエント
    リが存在する場合に、更新する段階を有することを特徴
    とする特許請求の範囲第１項に記載のトランジティブク
    ロージャ生成方法。
15. （１５）二次ストレージ領域、及び一次ストレージ領域
    を有するコントローラよりなるシステムにおける、 前記二次ストレージ領域にストアされたデータベースの
    トランジティブクロージャの一部分を生成する方法にお
    いて、 前記データベースは、前記データベースの所定のフィー
    ルドに割当てられた信号値を持つエントリを有し、 前記トランジティブクロージャがソースノードと呼称さ
    れる前記データベースの所定のフィールドと及びデステ
    ィネーションノードと呼称される前記データベースの所
    定のフィールドとに関して生成されるトランジティブク
    ロージャ生成方法において、 前記データベースにおける前記ノードの順序付けを行な
    う段階； 前記データベースの分配を行なう段階； ここで各々の分配分は、前記データベース内の、ある選
    択されたソースノードの組を共有するエントリ全てを含
    む； 前記分配分の全てを、１つずつ考慮することによって、
    前記データベースのエントリを生成する段階よりなる第
    １パス、 ここで、各々の分配分を考慮する場合には、まず、前記
    分配分内の各々のデスティネーションノードに対する、 前記分配分内の、当該デスティネーションノードを有す
    るエントリのソースノードを、既に考慮した分配分内の
    、前記デスティネーションノードと同一のソースノード
    を有するエントリのデスティネーションノードと、関係
    付けるエントリを生成し、 次に、前記分配分内のデスティネーションノードの各々
    に対する、 当該デスティネーションノードを有する前記分配分内の
    エントリのソースノードを、前記分配分内の前記デステ
    ィネーションノードと同一のソースノードを有するエン
    トリのデスティネーションノードと、関係付けるエント
    リを生成する；前記分配分の全てを、１つずつ、考慮す
    ることによって、前記データベースのエントリを生成す
    る第２パス、 ここで、各々の分配分を考慮する場合には、前記分配分
    内の、前記第１パスにおいて考慮されなかったデスティ
    ネーションノードに対する新たなエントリを作成する； よりなることを特徴とするトランジティブクロージャ生
    成方法。
16. （１６）前記トランジティブクロージャ生成方法が、更
    に、 前記エントリ生成段階において、前記データベース内の
    ソースノード及びデスティネーションノード間に２つの
    経路が生成された場合に、ラベルを更新する段階を有す
    ることを特徴とする特許請求の範囲第１５項に記載のト
    ランジティブクロージャ生成方法。
17. （１７）前記エントリ生成段階が、 ソースノードが前記ヘッドエントリのソースノードであ
    り、デスティネーションノードが前記テールエントリの
    デスティネーションードである、既存のエントリのラベ
    ルを修正する段階を有することを特徴とする特許請求の
    範囲第１５項に記載のトランジティブクロージャ生成方
    法。
18. （１８）前記トランジティブクロージャ生成方法が更に
    、 あるソースノード及びあるデスティネーションノードを
    有するエントリのラベルを、同一のソースノード及び同
    一のデスティネーションノードを有する他のエントリが
    存在する場合に、更新する段階を有することを特徴とす
    る特許請求の範囲第１５項に記載のトランジティブクロ
    ージャ生成方法。
19. （１９）所定のフィールドに割当てられた信号値を持つ
    エントリを含むデータベースを圧縮してストアするデー
    タベース圧縮方法において、 前記データベースは、最低限、ソースノードと呼称され
    る前記データベースの所定のフィールド及びデスティネ
    ーションノードと呼称される所定のフィールドとに関し
    てトランジティブクロージャ完成であり、当該方法が、 チェーンの組を生成する段階、 ここで、各々のチェーンは、前記データベースのエント
    リの順序付けられた組からなり、前記チェーンの、最後
    のエントリ以外の、全てのエントリのデスティネーショ
    ンノードが、各々当該チェーン上の次のエントリのソー
    スノードと同一であり、 前記チェーンの組は、全てのノードが最低限当該チェー
    ンの組において、あるチェーンのあるエントリのソース
    ノードあるいはデスティネーションノードとして１回現
    れるように選択されている；及び 前記データベースの各々のソースノードに対して、当該
    ソースノードを共有しているエントリの組から、当該エ
    ントリの組の他のエントリのデスティネーションノード
    よりもあるチェーン上で後に現れるデスティネーション
    ノードに対するエントリを削除する段階、 このことによって圧縮したデータベースが生成される； よりなることを特徴とするデータベース圧縮方法。
20. （２０）前記データベース圧縮方法において、更に、前
    記生成段階と前記削除段階との間に、 各々のノードに対して、当該ノードが属するチェーン及
    び当該チェーン内での当該ノードの位置を識別するため
    に、識別子を割当てる段階を含むことを特徴とする特許
    請求の範囲第１９項に記載のデータベース圧縮方法。
21. （２１）ストレージ領域中に存在する元のデータベース
    から、増大したデータベースを生成するシステムにおい
    て、 前記元のデータベースは、複数のエントリを含み、当該
    エントリの各々は複数個のフィールドを有し、前記デー
    タベースの所定の属性に割当てられており、 前記フィールドの各々における信号値が当該エントリに
    対する対応する属性に係る値を規定し、前記増大したデ
    ータベースは、トランジトリーデータベースのシーケン
    スによって実現され、最初のトランジトリーデータベー
    スは元のデータベースであり、それ以降のトランジデー
    タベースが、その前のトランジトリーデータベースの修
    正によって生成され、 前記増大したデータベースは、元のデータベースのトラ
    ンジティブクロージャの少なくとも一部であり、前記ト
    ランジティブクロージャがソースノードと呼称される前
    記データベースの所定のフィールド及びデスティネーシ
    ョンノードと呼称される前記ベースの所定のフィールド
    とに関して生成され、 前記システムが、関連したメモリを持つコントローラを
    有し、 当該コントローラが、 前記ストレージ領域内の前記トランジトリーデータベー
    スをソートする手段； 前記トランジトリーデータベースを分割する手段、 ここで、各々の分配分は、分割されたデータベースにお
    ける共通のソースノードを共有するエントリを含む； 前記トランジトリーデータベースの１分配分を前記スト
    レージ領域より読み出して前記メモリに配置する手段； 前記増大したデータベースのエントリ対の考慮に応じて
    、前記増大したデータベースに対するエントリを生成す
    る手段、 ここで、前記エントリ対の一方は、前記メモリ内のエン
    トリであり、前記エントリ対のもう一方は前記メモリあ
    るいは前記ストレージ領域における前記トランジトリー
    データベースのエントリであり、生成されたエントリは
    前記トラジトリデータベースの修正である；及び 前記ストレージ領域に、前記エントリ生成手段によって
    生成されたエントリを、次のトランジトリーデータベー
    スを形成するように、配置する手段、 ここで、前記読み出し手段は、各々の分配分を最高２回
    読み出し、前記エントリ生成手段は、考慮中のエントリ
    対の一方のデスティネーションノードが当該エントリ対
    の他方のソースノードでもある場合に、前記エントリを
    生成する； を有することを特徴とするデータベース生成システム。
22. （２２）他のデータベースのトランジティブクロージャ
    の少なくとも一部分を表現しているデータベースをスト
    アするシステムにおいて、 当該システムが、 前記データベースをストアする手段；及び 前記トランジティブクロージャ完成データベースにおけ
    るエントリの生成あるいは修正に係る、前記データベー
    ス中のエントリの識別をストアする手段、 よりなることを特徴とするデータベースストアシステム
    。
23. （２３）前記データベースの所定のフィールドに割当て
    られた信号値を持つエントリを有するデータベースをス
    トアする方法において、 当該方法が、 前記データベースに対応するトランジティブクロージャ
    完成データベース（ＴＣＣ−ＤＢ）の少なくとも一部分
    をストアし、 ここで、前記トランジティブクロージャは、ソースノー
    ドと呼称される前記データベースの所定のフィールド及
    びデスティネーションノードと呼称される前記データベ
    ースの所定のフィールドとに関して生成される；及び 前記ＴＣＣ−ＤＢの前記ストアされている部分のエント
    リの生成に係る前記データベース内のエントリの識別を
    、前記ＴＣＣ−ＤＢの前記ストアされている部分の各々
    のエントリに、当該ＴＣＣ−ＤＢのソースノードを当該
    データベースにおける、ａ）前記ＴＣＣ−ＤＢのエント
    リと同一のソースノードを有し、かつｂ）当該データベ
    ースの他のエントリと共に前記ＴＣＣ−ＤＢのエントリ
    の生成に用いられる、エントリのデスティネーションノ
    ードを関係付けることによって、ストアすることを特徴
    とするデータベースストア方法。
24. （２４）前記データベースストア方法が、更に、前記Ｔ
    ＣＣ−ＤＢのエントリに関する識別子の前記組の各々の
    識別子に関するラベルを有することを特徴とする特許請
    求の範囲第２３項に記載のデータベースストア方法。
25. （２５）情報に関するデータベースを保持するストレー
    ジ手段； データベースに含まれている情報を要求するためのター
    ミナル； 前記ターミナル及び前記ストレージ手段に応じて、前記
    データベースのトランジティブクロージャの少なくとも
    一部分を生成し、かつ前記ターミナルによって要求され
    た前記情報を読み出すために前記データベースを検索す
    る増強データベースマネージャ； 前記データベースにストアされた情報を修正する手段；
    及び 前記データベースにストアされた情報が修正された場合
    に前記データベースのトランジティブクロージャの前記
    部分の生成を開始する手段；からなることを特徴とする
    、情報提供システム。
26. （２６）前記増強データベースマネージャがコントロー
    ラ及びメモリを有し、前記データベースのトランジティ
    ブクロージャの前記部分を、前記データベースを分割し
    、各々の分配分を前記データベースから前記メモリへ最
    大２回ロードすることによって、生成することを特徴と
    する特許請求の範囲第２５項に記載の情報提供システム
    。