JPS59502042A - ハイパエツジ実体関係デ−タベ−スシステム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ハイパエツジ実体関係データベースシステム侠歪分賢 本発明はコンピユータ化されたデータベース、特にハイパグラフの形でモデル化 されたエンティティ関係データベースに関する。

背景技術 データベースは４つの一般的なタイプに類別される。第１のタイプは階層的デー タベースでツリー形式にモデル化される。対象、すなわちデータベース中の情報 の項目は１葉のような基本的な項目に関連し、葉は技で関係づけられ、枝は幹で 関係付けられる。この形のデータベースはデータ項目間の上下関係を強調するも のであり、このような関係が本質的であるような組織図のようなデータには適当 している。

他のタイプのデータベースはネットワーク形であり、有向グラフとしてモデル化 される。ネットワーク中のデータ項目（グラフのノードすなわちバーテックス） はすべて等しい重みすなわち値を持ち、グラフの背向性のエツジによってシンボ ル化される関係によって相互接続される。この形のデータベース構造は多重階層 関係を持つデータベース、例えば共通の供給者および共通の倉庫によって相互に リンクされた在庫品目のような場合である。

データベースの第３の形態はデータ項目の関係的特性によってモデル化される。

このようなデータベースにおいては、各々の関係は、各行が特定の関係を共有し ている対象のひとつを一覧表としている表によって表わされる。仮想的にはこの ような関係データベースのすべての情報は対象そのものではなく、対象の間の関 係を形成する。

第４番目のデータベースのモデルは実体関係モデルと呼ばれる。

このモデルはまた有向グラフで表わすこともできるが、データの実体はグラフの バーテックスを形成し、一方有向性のグラフのエツジが実体のノードの間の関係 を表わす。典型的にはデータレコードはデータ項目そのものと、他のデータレコ ードに対するポインタの両方を含むノードである。ポインタはグラフのエツジ、 すなわち、バーテックス（データ項目）の間の関係を表わすのに使用される。こ のようなポインタは指される実体すなわちノードと、そのノードに対する関係の 表示を含んでいる。この場合も、実体関係モデルはデータの実体とこれらのデー タの実体の間の関係がモデル化されている実世界ψ状況に固有であるようなある 種のデータに適合している。実体関係モデルは基本であり、他の３つのモデルは 実体関係モデルの特殊ケースであるとする学者もいる。

本発明はこの最後のタイプのデータベース、すなわち、実体関係データベースに 関するものである。このようなデータベースのひとつについてはＲ，Ｇ、Ｇ、Ｃ ａｔｔｅ’ｌｌの　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｏｎ　 Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ、５ａｎｔａ　ｌ’１ｏｎｉｃａ＋ｃａ ｌｉｆｏｒｎ、ｉａの１９８０Ｐｒｏｃ、ＡＣＭ−５ＩＧＭＯＤ　１４４にある ”　Ａｎ　Ｅｎｔｉｔｙ　−ｂａｓｅｄ　ＤａｔａｂａｓｅＵｓｅｒ　Ｉｎｔｅ ｒｆａｃｅ　”と題する論文（１９８０年５月１４日〜１６日）を参照されたい 。

二つの対象の間の単一の関係が共通であって、有向性グラフのひとつのモデルで うまく表現できても、ある種の関係は二つ以上の実体に関連する。例えば、“〜 の親”というような関係では、−人の子供と二人の親が関係する。“〜のの親” という関係は二人の両親という関係を定めなければ完全には規定できない。親の 間の関係は単純（例えば、結婚している）であっても、このような関係は三人の 人、父、母、子供に関連した“〜の親１という関係には本質的でない。グラフ理 論では親を示すエツジはひとつ以上のバーテックスを同時に指すので、ハイパエ ツジと呼ばれている。ハイパグラフとハイパエツジについてはＣ，Ｂｅｒｇｅの Ｇｒａｒｈｓａｎｄ　Ｈｙｐｅｒｇｒａｐｈｓ”　Ｎｏｒｔｈ　Ｈｏｌｌａｎｄ 社、Ｎｅｗ　Ｙｏｒｋ　１９７３年刊のテキスト、特にその頁３８９−４１３に 詳細に述べられている。

多くの実世界の状況ではデータ対象の間に多重関係があるから、ハイパグラフの モデルは多くの実世界の状況に関するデータを表わすのに顕著に適合している。

残念なことに、従来はディジタル計算機で容易に処理することができ、能率良く 利用できる形で、このようなデータベースを表わすことは困難であるか、あるい は不可能であった。

発明の要約 本発明の一実施例に従えば、ハイパグラフのモデルに容易に適合でき、データベ ース中の種々のデータ項目の取扱い、アクセス、利用が容易にできるような実体 関係データベース構造が提供される。詳しく述べれば、各データレコード（ノー ドと呼ばれる）は有向性グラフのバーテックスを形成する実体を定義する本体部 を含んでいる。データレコードはまたそれによって単一の関係（エツジ）がひと つ、二つあるいはそれ以上のデータベースシステム中のノードとして表現された データ実体を参照するのに使用できる多重エツジ表現を含んでいる。

データベースを表現するこの簡単な方法によって、有向グラフのハイバエ、ジを 自動的に探索し、識別し、利用できるようになる。これはまた処理ソフトウェア によってハイパエツジの情報とこれらのハイパエツジによって指定される多数の ノードを迅速に、直接にアクセスできるようにする。

データベース中でこのようなハイパエツジの情報を陽にすることによって、これ 以外の方法では必要であった間接動作を避けることができ、これによってこの情 報へのアクセスを直接的で能率良くすることができる。

図面の簡単な説明 第１図はハイパエツジを示す有向性グラフ；第２図は標準ハイパエツジ表現を示 す第１図のグラフのノードのひとつのデータベースレコードの標準表現；第３図 は設備の利用者に対して設備を割当てるためのハイパエツジデータベースのひと つの応用のブロック図；第４図は電話サービスの提供に用いられる電話の外部プ ラント設備の一般化されたブロック図； 第５図は特定の電話加入者に対してサービスを提供するために使用される典型的 な外部プラント設備のグラフによる表現；第６図は第５図に示した設備の在庫を 示す有向グラフによる表現； 第７図は第５図の設備の接続を表わすハイパグラフ表現；第８凹は第７図のハイ パグラフのひとつのノードの完全なグラフ表現； 第９図はハイパエツジ表現を説明する第８図のノードの典型的なデータベースレ コード： 第１０図は第３図に示したデータベースマネージャの説明的ブロック図である。

詳細な説明 特に第１図を参照すれば、図には有向性ハイパグラフの回による表現が示されて いる。ハイパグラフはある種の関係データ構造の表現のためのひとつの方法であ る。

このような実体関係データベースはＰｅｔｅｒ　Ｃｈｅｎの八ＣＭ　Ｔｒａｎｓ 。

ｏｎ　Ｄａｔａ　Ｂａ５ｅ　Ｓｙｓｔｅｍｓ、Ｖｏｌ、１．Ｎｏ、１　（１９７ ６）の”　Ｔｈｅ　Ｅｎｔｉｔｙ−Ｒｅｌａｔｉｏｎｓｈｉｐ　Ｍｏｄｅｌ　− Ｔｏｗａｒｄｓ　ａ　Ｕｎｉｆｉｅｄ　Ｖｉｅｗ　ｏｆ　Ｄａｔａ”に述べられ ている。第１図の円はグラフのバーテックスを示し、データ構造中の情報実体を 表わす。矢印はエツジと呼ばれ、バーテックスの実体の間の関係を表わす。例え ば、ノードｌＯはエツジ１６によってノード１２と接続されている。すなわち、 実体１０は関係１６によって実体１２と関係付けられている。例えば、実体１０ は在庫の部品で、実体１２は在庫の供給元で、関係１６は“〜によって購入され る”という関係を表わすことができる。

実体１０はまた関係１７で実体１３と関連付けられている。実体１３は部品１０ が格納されている倉庫であるかもしれない。ここまでは実体１０．１２および１ ３と関係１６．１７はグラフ理論と実体関係データベースによって周知である。

ノード１０とノード１４．１５の関係はグラフ理論では周知であるが、実体関係 データベースでは能率良く取扱かうことはできなかった。

実体１０は実体１４．１５と関係１８で関連している。第１図のグラフのエツジ １８はひとつのバーテックスと二つ以上の他のバーテックスの関係を表わしてい るので、“ハイバエ、ジ”と呼ばれる。ハイパエツジを含むグラフはハイパグラ フと呼ばれる。

このようなハイパグラフの数学的性質は周知であり、Ｃ１ａ　ｄｅＢｅｒｇｅの Ｇｒａｐｈ　１ＩＴＩａ　Ｈｙｐｅｒｇｒａｐｈ　Ｎｏｒｔｈ　Ｈｏｌｌａｎｄ 社Ｎｅｗ　Ｙｏｒｋ刊、１９７３の頁３８９−４１３に述べられている。

実体１５は先の例に従えば、部品１０が部分となっているサブアセンブリである 。実体１４はこれに対して部品１０をサブアセンブリ１５に組込むための工具で ある。従来技術のデータベース構造に従えば、エツジ１８はひとつはバーテック ス１４へ、ひとつはバーテックス１５へゆく二つのエツジで表わされた。バーチ ７クス１０．１４および１５の間の関係はこれらの二つの関係と関係２２から推 論される。しかし、ノード１０．１３および１４の同様の関係は、バーテックス １３は単に貯蔵用倉庫であるから、組立てるのに使用する工具は意味しない。従 って従来技術のシステムでこのような関係が間接化されているということは能率 を低下し、従来技術のシステムである種の問題を解決するのに要する時間を増大 するのみならず、誤った推論の可能性を生ずる。例えば、部品１０で不足が生じ たとき、それに影響されるアセンブリ（例えば、１５）を知る必要があるばかり でなく、余って来る影響を受ける工具（例えば、１４）も知りたいことになる。

この情報は単純なエツジだけを持つ従来技術のデータ構造でも知ることはできる が、これにはモデルに対してデータを追加することによって誤った関係を除去す る必要がある。

さらに、ハイパグラフの表現によって関係の変更を実現することも容易である。

例えば、部品１０がアセンブリ１５の部品ではなくなったときには、単一のハイ パエツジを消せばよく、それ以上の処理は必要ない。

データのこのようなハイパグラフによる表現はデータベース中の関係が二つ以上 の実体の関係を含む必要があるような実体関係データベースにおいて特に有用で ある。上に示したように部品−アセンブリー工具の関係はこのような状況にある 。電気コネクタの電気端子に接続された線もこのような関係の他の例である。特 定の航空便の座席、特定の磁気記憶ディスク上の記憶ブロックも他の例である。

これらの状況の各々とそれ以外の同様な多数の状況ではハイパエツジによる表現 と本発明に従う処理によって多大な利益が得られるものである。

第２図には第１図のハイパグラフの一部、特にノード１０を表わすのに使用され る一般的なデータベースレコードを示している。

ノード１０のレコードはひとつの本体（すなわち実体１０そのもの）と複数個の エツジを含み、すべてのエツジはノード１０を始点としている。線（ａｌ）乃至 （ａ４）はノード１０の本体をタイプ（例えば部品の共通の名前）と特定の部品 の特定の識別番号（例えばシリアルナンバ）に関して識別するものである。単純 なエツジ１６および１７はそれぞれ行ｂｌ−ｂ３およびｃｌ−ｃ３で表わされ、 これらはエツジ１６と１７によってノード１０に接続されたノードの各々の実体 のタイプと実体の識別番号を含んでいる。

ハイパエツジ１日は第２図において行ｄｉ−ｄ５で表わされている。この表現の フォーマントは単純なエツジ１６および１７について使用したのと同一である。

唯一の差はひとつ以上の接続されたノードがハイパエツジに関連しているという ことである。これらのノードはまたタイプと識別番号情報によって表わされてい る。

以上ではハイパエツジ表現の計算の簡単さ、きれいさおよび能力はあまり明らか ではないので、以下にそれについて述べる。第１にハイパエツジと単純エツジは アクセスプログラムによって同様に見え、データベースマネージャのプログラム がハイパエツジを含んでいるかどうかを知ることが不必要になっている。アクセ スプログラムは一組だけ必要であり、このプログラムはエツジのタイプとは全く 関係がないようになっている。すなわちデータベースの基本命令はデータベース の構造で指されるノードの数には透明になっている。これはユーザが作った応用 プログラムでハイパグラフを識別する必要があることを示す。特定のレコードも またユーザが指定するものであるから、データベースマネージャがすべての種類 のエツジを同様に扱かえるように一般的になっていることは可成り価値があるこ とになる。これらのプログラムはどのような異なるデータベースの応用にも使用 することができる。

第１図および第２図の例は三つのノードだけに関連し７たハイパエツジを示して いることに注目されたい。しかし、ハイパエツジはその番号が２を越えていさえ すれば、任意の数のノードを取扱かうことができる。このようなハイパエツジの 単純な例は、住居番号、街路、市、郡、州、国から形成される住所であり、その 各々はハイパグラフ中の別々のノードとしてうまく表わせるようになっている。

特に第３図、を参照すれば、図にはハイパグラフ表現が有用であるデータベース の応用の一般的ブロック図を示している。第３図の情報処理システムは磁気ディ スクパックに含まれているものとして図示されているデータベース３０、データ ベースマネージャ３１、応用プログラムのグループ３２、入力装置３３および出 力装置３３を含んでいる。データベースマネージャ３１と応用プログラム３２は 共にコンパイラプログラム（図示せず）によってオブジェクトコードにコンパイ ルされ、汎用データプロセッサ３５の内部メモリに格納されたコンピュータのプ ログラムである。

入力装置３３はデータベース３０中の情報を要求するサービスについて応用プロ グラム３２に対して要求を出す。応用プログラム３２はサービス要求を満足する ために何の情報が要求されるかを判定し、特定のレコードあるいはレコードの部 分についての要求を形成し、その要求をデータベース中ふ−ジャ３１に転送する 。

応用プログラム３２は利用者の要求から、ハイパエツジ情報が検査されるかどう かを判定してもよい。しかしデータへ・−、スマネージャ３１は単にデータベー スの全体の構造を考えることなく単にレコードあるいはレコードの部分を検索す る。データベースへのアクセスは要求ノードとして加算され、ノードへのエツジ を使用して要求された情報あるいはサービスを提供する目的でハイパグラフを通 してノードをナビゲートすることができる。

データベースマネージャ３１のノードアクセスルーチンはデータベース３０から 所望の情報を検索して、情報を値として応用プログラム３２に与える。第２のレ コード構造について考えれば、これらの値はレコード（あるいはその一部）から 要求された本体およびエツジについての実体タイプ、識別番号および応用データ である。これらの値は次に応用プログラム３２によってフォーマント変更され、 入力装置３３によって要求される特定のサービスを与える。その結果は出力装置 ３４に転送される。もしデータベースマネージャ３１によってハイパエツジの値 が検索されていれば、すてにハイパエツジの情報を予期している応用プログラム ３２は要求されたサービスを与えるのに必要な形式で多ノードのハイパエツジ情 報を適切に組合わせてフォーマット化する。

装置３３はキーボードで、装置３４はディスプレイスクリーンで、これらは人間 のユーザによって操作される一体化された端末であっても良く、装置３３は同様 に自動的な電気装置あるいは機械装置（例えば、アセンブリラインの部品計数器 ）であり、装置３４は同様に自動装置（例えば在庫量が低くなりすぎたときに再 注文する購入伝票発生器）であっても良い。この場合には第３図のシステムは単 純な情報提供システムではなくサービス提供システムである。このサービス（在 庫管理、設備割当、切符発行その他）はデータベース３０の情報の利用可能性に 依存するが、外界に対しである種のサービスを提供するために、その情報以上の ことをするようになっている。

データベース３０はデータベース保守設備３６によって生成され、最新の状態に 保たれる。設備３６はまたデータベース３０にアクセスするのにデータベースマ ネージャ３１を使用するが、この場合はデータベース３０中のレコードを生成し 、更新するためである。この活動はデータベース３０の装Ｗ３３および３４．に よる利用とは完全に分離されており、別個であるが、異なる時点でで同一の人員 が同一の設備を使って実行することもある。

以上第１図乃至第３図に関連して本発明を一般的に説明したが、残りの図面はハ イパグラフによるデータベース表現の特定の応用を詳細に説明するために使うも のとする。この応用は加入者の電話機をローカルの交換局に接続するために電話 加入者に対して物理的設備（線、ケーブル、端子箱その他）を割当てる問題であ る。

このような割当は比較的長期間の間不変であるが、顧客が引越しをすれば、設備 の割当の変更をしなければならない。数十万もの顧客を取扱かう交換局において は、このような設備の割当は大きな、人手を要する仕事になる。このような割当 変更の能率を最大化し、コストを最小化することは従って電話会社の重要な仕事 である。

次に第４図を参照すれば、図には電話加入者をローカル交換局ち接続するのに使 用する典型的な設備の説明図を示している。このような設備はすべて交換局４０ の外にあるから、これらは外部プラント設備と呼ばれる。このような外部プラン ト設備はケーブル４１乃至４５のような多厚体ケーブルから成り、その各々は互 いにより合わされた多数の銅線の対を含んでいる。一般に、このような対のひと つが、−人の顧客に電話サービスを提供するのに使用される。ケーブルは電話局 に対する近さで識別され、例えば、ｆ１ケーブル４１．４２および４３とｆ２ケ ーブル４３．４４および４５は相互接続端子４６および４７によって分離されて いる。

一部の地域では外部プラント相互接続システムに三つあるいはそれ以上のレヘル のケーブル（ｆ３、ｆ４その他）を必要とする。

相互接続端子４４および４７は電気的線の対を相互に接続するための装置である 。これらは交換局からの線対を接続するためのバインディングポストの集合（内 側の集合）と他の方向（フィールド側）からの線対を接続する他方の集合（外側 の集合）とから成っている。さらに、相互接続端子は選択された内側の対と選択 された外側の対を接続し、これによって分配ケーブル対とフィーダケーブル対の 間の物理的相互接続を行うジャンパ線を持っている。ケーブルと対には交換局側 の端とフィールド側の端がある。

ケーブル４１乃至４５の選択された点には分配端子４８がある。

これらの分配端子もまたケーブル対を顧客の家５１および５２に接続されたそれ ぞれドロップ線４９あるいは５ｏのような顧客サービス線に接続するためのバイ ンディングポストを持っている。

分配端子は典型的には加入者の家の集中点に設けられており、歩道あるいは顧客 構内の電柱に設けられる。

電話サービスを電話加入者の家に提供する際における割当問題はデータベースの 中で加入者の電話機セントと交換局の間で完全な連続した電気回路（ローカルル ープ）を形成するために必要な線、端子、バインディングポストおよび顧客サー ビス線を割当てる問題である。データベース中で一度割当をした後、サービスを 開始する時点で、フィールドにおいて対応する物理的接続を形成しなければなら ない。データベースはまだ完成していない指示と完成された指示の両方を反映し ていなければならない。すべての設備は稼動中か空きであり、新しい顧客に対す る割当は一般に空きの設備から選択される。物理的設備の配置を変更することは 非常に金のかかることであるから、たいていの割当アルゴリズムでは、プラント 設備の配置変更を最小化するようになっている。例えば、ある家に割当てられた 設備は顧客が引越した後も割当てられたままにされる。その前提は新しい顧客が また引越して来てサービスを要求するということである。これに対して、ある経 験的に定められた期間の後（数ケ月）では、その家に再び人が住む確率は低くな り、その設備を他で使用する方が良い方針となる。

第５図には第４図の家５２に対して電話サービスを提供するために割当てられる 特定の設備を回示している。この場合の交換局４０を相互接続端子４６に接続す るケーブル４１は、ケーブル“０１”として示されている。家５２に割当てられ たケーブル０１の中の特定の対は対“２１”であり、これは二項記法“０１：２ １”で表わされる。対０１：２１のフィールド端は端子４６の内側のバインディ ングポスト５２に接続されている。内側のバインディングポスト５２はジャンパ 線によって外側のバインディングポスト３０２に接続されている。ケーブル４４ の１２１番目の対（対０１０１：１２１）の交換局側の端は、端子４６のバイン ディングポスト３０２と接続されている。他端（フィールド端）においては、対 ０１０１：１２１は分配端子４８を通してドロップ線５０に接続され、そこから 家５２に行っている。

このループに使用されている設備はタイプ（対、ケニブル、端子その他）、内部 識別番号の両方を持ち、オプションとして外部識別番号を持っていることがわか る。例えば、識別番号の一部（例えば対０１：２１、端子４６、バインディング ポスト３０２）は外部的であり、一部は内部的である。（その設備のノードへの 単純なポインタである。）内部識別番号は第２図のレコードの例で使用されてい る。一般的な問題は設備の在庫管理に用いられ、同時に顧客と交換局の間のサー ビスを提供するループにこれらの設備を割当てたり、割当変更したりするのに使 用できるデータベースを形成することである。

第６図には、第５図にグラフで示した外部プラント設備を形成する設備在庫の有 向グラフによる従来技術の標準的な表現を示している。第６図の各ボックスはグ ラフのバーテックスであり、ひとつのバーテックスが在庫の中の各々の物理的実 体ごとに設けられている。この場合はボックス６０はケーブル４１を表わすグラ フのバーテックスであり、バーテックス６１は相互接続端子４６を表わし、バー テックス６２は、対０１：２１を表わし、バーテックス６３はケーブル４４を表 わし、バーテックス６４は対０１０１　：１２１を表わし、バーテックス６５は 分配端子４８を表わし、バーテックス６６は家５２を表わす。これらのバーテッ クスは実体関係データベースの中の実体である。

これらの実体の間の関係（グラフのエツジ）は第６図でバーテックスの間の矢印 によって表わされる。この場合矢印６７はケーブル４１が端子４６に接続されて いるので“接続されている”という関係を表わす。矢印６８は対０１：２１がケ ーブル４１に含まれているから、“含まれている”という関係を表わす。最後に 矢印６９は“接続されている”という情報と、さらにパインディングポスト（“ ＣＯＢＰ　５２”）に関する他の情報すなわち、端子４６の交換局側（内側）の パインディングポスト５２の情報を表わす。第６図の他の矢印も同様の意味を持 つが、分配端子４８と家５２が“取扱かわれる”と“取扱かう”という相互関係 を持ち、顧客サービス線５０については簡単のため省略しであるということ以外 はここでは説明しない。

第６図に含まれた在庫情報はループプラントで使用される物理的設備を追尾する のに必要である。しかしこれは顧客に対して電気回路（ループ）を割当てるのに 、特に便利ではない。第７回にはこれらと同一のバーテックスの間の矢印（エツ ジ）の他の集合でループの割当にもっと適したものを示す。

第７図においては、第６図に示したのと同一のバーテックス（ケープルバーテッ クスを除く）が繰返されており、これに回線バーテックス８０が加わっている。

第７図のグラフは部品の在庫とは区別された通信回線の接続を表わしている。回 線（バーテックス８０の電話番号で区別される）は三つの部分、すなわち、対０ １：２１、対０１０１　：１２１および家（ドロップ線５０に関連する）から成 っている。これらの三つの部分は端子を通して相互に接続されている。割当処理 の効率化のためには、対０１：２１が対０１０１　：　１２１に接続されている ことを直接知ることが望ましい。これと同時に、これらの相互接続が端子と特定 のパインディングポストで行われていることを知る必要がある。ハイパエツジ８ １と８２は接続された対とそれを通して接続が行われている端子を同時に示して いる。第６回の表現では、対と対の接続は検出することができるが、設備の割当 のためにデータベースをさらに探索することは非常に能率が悪い。

対０１０１：１２１　（ボックス６４）と家５２　（ボックス６６）の相互接続 は同様に二つのハイパエツジ８３および８４で表わされており、これは回線のこ の部分と同一の機能を持っている。在庫を変更することなく、ジャンパ線を使っ て物理的設備を他の回線に割当てできることに注意していただきたい。すなわち 第７図の接続は第６図の在庫を変化することなく変えられるのである。

第７図のハイパグラフは割当てられた電気的回線の在庫を管理するのに使用され 、一方第６図は物理的部品の在庫の管理に使用される。これらは両方共電話加入 者を適切に取扱かうために必要である。

第８図には第４図に示した物理的設備と回線割当の両方を表わすのに使用される ハイパグラフデータベースのひとつのノードのグラフ表現を示している。第８図 で表わされたノードは対０１０１　：１２１を示すものである。先に述べたよう にノードは本体部（ボックス６２）と複数のエツジ部８２．８３．８６．８７． ８８および８９を含み、その一部（８２，８３）はハイバエ・ノジである。

第８図に図示されたノードは対０１０１：１２１に関するデータベース中のすべ ての情報を含んでいる。外部世界（対０１０１　：１２１）でわかるこの対の名 前はエツジ９０によって指される別個の実体になっていることに注意されたい。

各ノードの内部での識別は内部番号によって行われ、これによって関連するレコ ードに直接アクセスごきるようになっている。さらに、その内部参照番号をすべ て変更しなくても、実体の外部名は変更できる。

第９図には第２図で示した記法による対０１０１　：１２１のデータベースのレ コードの表現を示している。レコードの本体部分がまず現われるが、エツジの順 番は任意である。このような構成では特定のエツジは探索によって見付けること になる。次に第９図のデータレコードの内容について説明する。

まず各々の物理的設備は外部世界において知られている名前とは異なった内部識 別番号によって識別されることに注意しておく。

これらの内部識別番号は識別されたレコードに対して一義的であり、これによっ てコンピュータによるレコードの管理を隼純化し、外部世界の名前を任意にし、 しかも変更できるようにする。第８図に示すように特別のエツジ９０が外部名９ １　じ対０１０１：１２１”）を指しており、これは第９図の行ｇｌ−ｇ３に示 されている。

行ｃ１−Ｃ５と行ｆ１−ｆ５のエツジはハイパエツジであり、各々は二つのレコ ード識別番号を含んでいる。各々の本体およびエツジは“応用データ”と呼ばれ るひとつあるいはそれ以上の行を含んでおり、これはデータベース情報を外部世 界の問題に応用するときに有用な情報である。例えば、行Ｃ−５ではエツジは端 子の交換局側のパインディングポスト（これは端子のフィールド側のパインディ ングポストと区別される）を指すものであることが示される。行ｅ−３では対は 分配端子の内側（外側でなく）の“青−緑”のスタブ線に接続されていることが 示される。工・ノジｎはこの対が一部となっているループ回線を示している。

第１０図には第３図のデータベースマネージャ３１の一般的ブロック図を図示し ている。このデータベースマネージャはもちろんコンピュータのプログラムによ って実現されているので、ブロック回は単に種々のソフトウェアモジュールの間 のやりとりを示しているだけである。第１０図においては、要求デコーダ１００ によって、データベース３０への追加、削除あるいは修正の要求が受信される。

デコーダ１００は要求を分解（要求コマンドを解釈）して７個の特定の手続き１ ０１乃至１０７のひとつを付勢する。

手続き１０１は外部識別情報（例えば第８図のノード６２の対０１０１：１２１ ）を与えられて内部識別番号（例えば、第８図のノード６２のＩＤ３８８）を得 るものとする。この翻訳を実行するために外部／内部ＩＤリストと呼ばれるルッ クアツプ表１０８が維持されている。将来の使用のために内部ＩＤはバッファ１ ０９に記憶される。この内部ＩＤ番号を使用して、フェッチノード手続き１０７ は記憶マネージャ１１０に指示してデータベース３０から適切なノードデータを 得る。例えば、もしデータへ−ス３０が磁気ディスク上に存在すれば、記憶マネ ージャ１１０はディスクの適切なものの適切なセクタの必要なトランクのひとつ を探索してアクセスするのに必要な回路を含んでいる。しかし、データベースは 磁気コア、磁気テープ、磁気バブル、ビデオディスク、レーザディスクその他の 種々の形態の記憶装置中に存在しても良い。いずれの場合でも、記憶マネージャ １１０はそのレコードの一義的な内部ＩＤが与えられたときに、データレコード を回復するのに必要な回路をすべて含んでいる。このような検索の動作は当業者 には周知であるから、ここではこれについてそれ以上は述べない。

記憶マネージャ１１０によって得られたデータレコードはノードバッファ１１１ に記憶され、ここでこれは次の処理のために利用できるようになる。バッファ１ ０９と１１１および第１０図の他のバッファはここに述べたデータ項目を記憶す るために予約されたコンピュータのメモリー中の単なる記憶位置にすぎないこと に注意しておく。同様にリスト１０８は上述した情報を含む連続して予約された 単なる複数の記憶位置である。

ノードは手続き１０２を使用して生成したり削除したりすることができる。手続 き１０２はデコーダ１００が空き記憶リスト１１２から未使用の記憶空間のアド レスを得たのに応動してこの記憶ブロックに内部ＩＤ番号を付与して、このＩＤ 番号をバッファ１０９に入れる。新しいノードの内容は次に以下に述べる方法に よって発生される。

逆に、もはや使用されないノード（例えば、消されたりあるいは使用されなくな った施設）は、リスト１０８から対応する内容を取除き、対応する記憶空間を空 き記憶リスト１１２に加えることによってデータベースから削除される。データ ベース３０中の実際のデータはただちに削除する必要はなく、この記憶空間を生 成された新しいノードに再び割当てることによって重ね書きされる。

ノード情報が一部ノードバソファ１１１に書き込まれたならば、ノードの本体あ るいは特定のエツジはそれぞれ手続き１０３および１０５によってフェッチする ことができる。このとき本体のデータはバッファ１１３に記憶され、ここでこの データは手続き１０４によって変更される。新しく生成されたノードは同一の手 続き１０４によって本体バッファ１１３に挿入された本体データを持つ。同様に 手続き１０５によるエツジフェッチ要求に応動して、エツジのデータはエソシバ ソファ１１４に記憶され、手続き１０６によって追加、変更、削除のために利用 できることになる。

ＩＤ番号をシステムによって確保し、記憶空間を予約しく手続き１０２）、本体 を生成しく手続き１０４）、一時にひとつずつエツジを生成する（手続き１０６ ）によって新しいノードが生成される。ノードが生成され、あるいは修正され１ こあと、これは手続き１０７によってデータベース中で置換することができ、こ れは記憶マネージャ１１０によってデータをノードバッファ１１１からデータベ ースに移すようになっている。一方、バッファ１０９．１１１．１１３、および １１４に記憶されたデータは第３Ｍの応用プログラム中の他の手続きによる処理 のために利用できる。

第１０図のデータベースマネージャは本発明のハイパエツジに対しては完全にト ランスペアレントになっていることがわかる。

このようなハイパエツジはもちろん検索されたときにエツジバッファ１１４に記 憶され、従って処理に利用できるようにな、る。しかし第１０図のデータベース マネージャに関する限り、これらのハイパエツジは単に単純な（ハイパでない） エツジと全く同一に取扱かわれるエツジデータである。ハイパエツジデータであ ることについて知り、ハイパエツジデータを使用する機能を与えるのは応用プロ グラム３２である。

第１０図のシステムの動作例として、次の第１表は新しいエツジ情報がエソシバ ソファ１１４に入れられたことを仮定してノードに新しいエツジを追加するのに 必要なプログラムを示している。

ルーチン“ａｄｄｅｄｇｅ”はまずノードにエツジがすでに存在しているかをチ ェックする。もしそうであれば、メソセージはエツジが既に存在することを示し て戻る。もしエツジが未だ存在しなければ、これがノードに加えられ、その結果 を知らせるメツセージが戻る。

ａｄｄｅｄｇｅ　（ｎｏｄｅ、ｅｄｇｅｂｆｒ）／宰　バッファｅｄｇｅｂｆｒ のエツジをノードに追加する＊／Ｉｆ　ｎｏｄｅ　ｈａｓ　ｅｄｇｅ＞ｅｄｇｅ ｂｆｒ；ｔｈｅｎ　ｒｅｔ＊ｒｒｒ　’ｅｘｉｓｔｓ”；Ｅｌｓｅ　ａｄｄ　ｅ ｄｇｅｂｆｒ　ｔｏ　ｎｏｄｅ　；Ｔｈｅｎ　ｒｅｔｕｒｎ　’ａｄｄｅｄ″； ｎｄ 第２表には第１表の“ａｄｄｅｄｇｅ　”ルーチンを使用して二つのノードから 他のノードへのハイパエツジを生成する“ｒｅ　Ｉａ　ｔｅ−ｎｏｄｅ−１ｏｄ ｅ”のプログラムを示す。

ｒｅｌａｔｅ　ｎｏｄｅ　ｎｏｄｅ　（ｎｏｄｅ−Ａ、　ｅｄｇｅｂｆｒ　Ａ、 ｎｏｄｅ−８゜ｅｄｇｅｂｆｒ　Ｂ、　ｎｏｄｅ　Ｃ）７本　エソシバソファ中 のエツジを使用して　＊／／本　ノードＡからノードＢおよびＣへのハイバエ・ ノジを生成し、＊／ ／＊　ノードＢからノードＡおよびＣへの第２のハイパエツジを生成する。宰／ Ｓｅｔ　ｒｉｄ　（Ａ）　ａｎｄ　ｒｉｄ　（Ｃ）　ｉｎ　ｅｄｇｅｂｆｒ　Ｂ ；Ｓｅｔ　ｒｔｙｐｅ（Ａ）　ａｎｄ　ｒｔｙｐｅ（Ｃ）　ｉｎ　ｅｄｇｅｂｆ ｒ　Ｂ；Ｓｅｔ　ｒｉｄ　（Ｂ）　ａｎｄ　ｒｉｄ　（Ｃ）　ｉｎ　ｅｄｇｅｂ ｆｒ−＾：Ｓｅｔ　ｒｔｙｐｅ（Ｂ）　ａｎｄ　ｒｔｙｐｅ　（Ｃ）　ｉｎ　ｅ ｄｇｅｂｆｒ　Ａ；／宰　ノードＡとＢにエツジを追加する。本／ｉｆ　ａｄ’ ｄｅｄｇｅ（ｎｏｄｅ　Ａ、　ｅｄｇｅｂｆｒ−＾）　ａｎｄａｄｄｅｄｇｅ（ ｎｏｄｅ　Ｂ、　ｅｄｇｅｂｆｒ　ｂ）ｒｅｔｕｒｎ　ｓａｍｅ　ｍｅｓｓａｇ ｅ；ｔｈｅｎ　ｒｅｔｕｒｎ　ｔｈａｔ　ｍｅｓｓａｇｅ；７本　さもなければ メソセージは異なっており、誤りがある。＊／ ｅｌｓｅ　ｒｅｔｕｒｎ　’ｅｒｒｏｒ”：最後に第３表はデータベースで設備 を割当てるのに有用なデータベースレコード中に二つの対が相互に接続されてい ることを示すための“ｒｅｌａｔｅ　−ｎｏｄｅ　−ｎｏｄｅ　”を使用した応 用プログラムを示す。

第３表 相互接続対 ７本　これは対“Ａ”を端子“ｔｅｒ　”で対“Ｂ″に接続する＊／／＊　ため の応用プログラムである　＊／ｎｏｄｅ　Ａ　＝ｒｅａｄ　（ｐａｉｒ　Ａ　） 　；ｎｏｄｅ　Ｂ　＝ｒｅａｄ　（ｐａｉｒ　Ｂ　）　；ｎｏｄｅ　Ｃ＝ｒｅａ ｄ　（ｔｅｒ　）　；２１ ７本　応用データＡとデータＢをバッファに追加する７本　１対の色、パインデ ィングポストその他　ネ／ａｄｄ　ｄａｔａ　Ａ　ｔｏ　ｅｄｇｅｂｆｒ　Ａ　 ；ａｄｄ　ｄａｔａ　Ｂ　ｔｏ　ｅｄｇｅｂｆｒ　Ｂ　；ｍｅｓｓａｇｅ　＝ｒ ｅｌａｔｅ　ｎｏｄｅ　ｎｏｄｅ　（ｎｏｄｅ−八。

ｅｄｇｅｂｆｒ　Ａ＋　ｎｏｄｅ　Ｂ＋ｅｄｇｅｂｆｒ　Ｂ、ｎｏｄｅ　Ｃ）； ｉｆ　ｍｅｓｓａｇｅ＝　”　ｅｒｒｏｒ　”　。

ｐｒｉｎｔ（ｃａｎｎｏｔ　ｃｒｏｓｓ−ｃｏｎｎｅｃｔ　”　。

ｐａｉｒ　Ａ、”ａｎｄ　”、　ｐａｉｒ　Ｂ。

”ｉｎ　ｔｅｒｍｉｎａｌ　”、　ｔｅｒ　）　；ｅｎｃｌ　； ＦＩＧ　／ ｒｕ；、８ レコード対０１０１１１２１ 国際調査報告

Claims (1)

【特許請求の範囲】
1. １．各々が信号を記憶するための本体部と複数のエツジ部を含む複数のレコード を含むデータベースを含み、該エツジ部の少なくともひとつは複数個の他のレコ ードへのポインタ信号を含み、 該レコードに記憶された信号にアクセスして利用する手段を含むことを特徴とす るデータベース。 ２、請求の範囲第１項に記載のデータベースにおいて、該部分の各々は実体タイ プと実体識別番号と実体応用を表わす記憶された信号を含むことを特徴とするデ ータベースシステム。 ３、請求の範囲第１項に記載のデータベースにおいて、さらに該レコードにアク セスし、生成し、削除し、修正するためのデータベースマネージャプログラムを 含むことを特徴とするデータベースシステム。 ４、請求の範囲第１項に記載のデータベースにおいて、さらに該レコードに記憶 された信号を利用するための複数のユーザプログラムを含むことを特徴とするデ ータベースシステム。 ５、請求の範囲第４項に記載のデータベースにおいて、該ユーザプログラムは該 ノートで識別された資源を資源利用手段に選択的に割当てる手段を含むことを特 徴とするデータベースシステム。 ６、類似したフォーマットの複数のレコードを持つデータベースにおいて、 該レコード中に複数の割当可能な設備の各々を識別する情報を表わす信号を記憶 する手段と、 該レコード中に該設備の任意の二つの間の複数の関係の各々を表わす信号を記憶 する手段と、 該レコード中に該設備の内の三つあるいはそれ以上の間の少なくともひとつの関 係を表わす信号を記憶する手段と、該レコードにアクセスし、修正し、利用する 手段とを含むデータベース。 ７、請求の範囲第６項に記載の組合せにおいて、該設備は電話外部プラント装置 を含み、 該利用手段は該装置を電話加入者に割当てる手段を含むことを特徴とする組合せ 。 ８、請求の範囲第６項に記載の組合せにおいて、該レコードフォーマットは実体 関係データベースの各エントリーを表わすことを特徴とする組合せ。 ９、　各レコードが本発明が本体部と複数のエツジ部を含むノードを含み、 該ノードの本体部の各々に物理的設備の識別番号と属性を表わす信号を記憶する 手段と、 該レコードの該エツジ部の一部には他のひとつのノードに到る単純エツジを表わ すエツジ信号を記憶する手段と、該レコードの該エツジ部の他のものは該ノード の他のひとつ以上のノードに到るハイパエツジを表わすハイパエツジ信号を記憶 する手段と、 該物理的設備を該設備の利用者に割当てるために該レコードにアクセスする手段 と を含むことを特徴とするデータベースシステム。 １０、該物理的設備は電話の外部プラント装置であることを特徴とする請求の範 囲第９項に記載の組合せ。