JPH02240741A

JPH02240741A - 階層構造を有するデータの登録、検索方式

Info

Publication number: JPH02240741A
Application number: JP1061713A
Authority: JP
Inventors: Takahiko Murayama; 隆彦村山; Kazuhiko Kushima; 串間　和彦
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1989-03-14
Filing date: 1989-03-14
Publication date: 1990-09-25

Abstract

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

Description

【発明の詳細な説明】［産業上の利用分野］本発明は記号化された情報（データ）を処理する計算機
システムにおいて、階層化されたデータの選択を高速に
行うためのデータ管理方法の一つであり、実行時に生成
消滅を繰り返すグループ化されたデータに関して、グル
ープ間、及びデータ間に存在する優先順位に従って選択
を行う場合の効率的な管理方法に関するものである。

［従来の技術］グループ化された複数個のデータの集合が存在し、グル
ープ内の個々のデータが生成消滅を繰り返すシステムを
考える。グループには複数の種類が存在し、各グループ
間には優先順位（グループの優先順位）が定まっている
。さらに個々のデータに関しても優先順位（データの優
先順位）が決っている。ある時点で優先順位がもっとも
高いグループ内から優先順位のもっとも高いデータを１
つ選択することが要求される。グループの優先順位は各
グループ毎に異なる場合もあるし、全グループで同一な
場合もある。

グループの優先順位はデータの優先順位より強い。

すなわち、優先順位の高いグループがまず選択され、次
にそのグループ内で最も優先順位の高いデータが選択さ
れる。同一の優先順位を持つグループが複数存在する場
合は、同一の優先順序をもつ複数グループに属するデー
タの優先順位を比較し、データの優先順位がもっとも高
いものが選択される。

この種のデータ管理の一例として知識ベースシステムに
おける実行するルールの選択方法がある。知識ベースシ
ステムの構成を図５に示す。知識ベースシステム１は専
門家の有する経験的知識をｒｌＦ条件　ＴＨＥＮ　　結
論」という形式で表現したルール２、ルールが条件部で
参照する事実データを格納したワーキングメモリ３、ル
ールとワーキングメモリの内容から実行すべきルールを
選択し、選択したルールの結論部を実行する推論制御部
４から構成される。ルールはルールセット５という単位
でグループ化されている。ルールセット、ルールには優
先順位が指定される。

推論時にはワーキングメモリの状態に対して条件を満た
す複数のルールが存在する。−船釣には複数のルールセ
ットが起動され、起動された全てのルールセットから条
件を満たすルールの集合が決定される。これら条件を満
足するルールの集合を「競合集合」と呼ぶ、Ｕ台集合か
ら次に実行するルール１０を１つ決定することを「競合
解決」と呼ぶ。競合解決の方法にはいくつかの手法が考
えられる。代表的なものは優先順位の高いルールセット
を選択し、さらに選択されたルールセット内の競合集合
に含まれるルールから優先順位の高いルールを１つ選択
するといった方法がある。

上記競合解決を実現する方法として２つの方法が存在す
る。１つは競合集合をルールセット単位に管理する方法
、他方は起動中の全ルールセットに含まれる競合集合を
一元的に管理する方法である。前者の具体例を図６に、
後者の具体例を図７に示す。図６では複数のルールセッ
ト５について条件を満たすルールの集合が各ルールセッ
ト単位の競合集合７に登録されている。ルール２は競合
集合への登録時にソートされ、最も優先順位の高いルー
ル８が競合集合７の先頭におかれる。競合解決ではルー
ルセット毎の優先順位に従って競合集合６を検査し、最
も優先順位の高いルールセットに属する競合集合から次
に実行するルール１０を選択する。これに対し、図７で
は競合集合としてシステム全体の競合集合９のみが存在
し、条件を満たすルール２はそれの属するルールセット
の名前とともに、その競合集合９に登録される。ルール
２は競合集合９への登録時にソートされ、ルールの優先
順位が最も高いルール８が競合集合９の先頭におかれる
。競合解決では競合集合９内に優先順位順に並べられた
ルールから各ルールの属するルールセットの優先順位に
従って次に実行するルール１０を選択する。

［発明が解決しようとする課題］上で述べた２種類の選択方法は一長一短あり、必ずしも
すべての場合に充分なものでない、つまり、ルールセッ
ト間にそれぞれ異なる優先順位が指定された場合はルー
ルセット単位に競合集合を管理する方式が優れている。

一方、全ルールセットに同一の優先順位が指定された場
合はルールセット単位の管理では、優先順位のもっとも
高いルールを決定するために全ルールセットの競合集合
の検査が必要であり、効率的でない。逆に、競合集合を
一元的に管理する方法ではルールセット毎にそれぞれ別
の優先順位が指定された場合、優先順位の高いルールセ
ットに含まれるルールを優先順位の低いルールセットに
含まれるルールをも含めた競合集合の中から選択する必
要があり、効率的でない。これらの各方式の問題はルー
ルセット間の優先順位づけが一定でないため、特定の順
序づけに従った最適な管理がとれないことに起因してい
る。

これらのことを解決するためには、グループ（上記例で
はルールセット）間に任意の優先順位がなされた場合に
、優先順序づけの特性により選択効率に差が発生しない
データ管理を実現することにある。

［課題を解決するための手段及び作用］上記課題を解決
するために、計算機システム内に存在するグループ化さ
れたデータの集合について、グループ間、及びデータ間
にに一定の優先順位が存在し、各グループ内のデータが
生成、消滅を繰り返す状態で、グループ間、データ間の
前記優先順位に従ったデータの選択が必要な場合に、デ
ータの登録と選択のためにそれぞれに専用の管理表を設
けることで前記優先順位の特性によらず、常に最適な効
率でデータの選択を可能とする。

具体的な手段と作用を本発明の基本となる基本構成を図
１をもとに示す。図１において、データ管理部は登録人
口１１、選択人口１２、データ１３を格納したリスト要
素１４から構成される。リスト要素は次のリスト要素の
アドレス１５を有しており、可変個数のデータをリスト
構造で管理するために使用される。データ１３はグルー
プ１６に属している。

登録人口１１はグループ１６に属するデータ１３が発生
した時にそのデータ１３を登録するために使用する。選
択人口１１は登録されたデータ１３からある優先順位に
従ってデータを選択する時に使用する。登録人口１１、
選択人口１２はともに配列で実現され、全グループ個数
分存在する。登録人口１１には選択人口１２のアドレス
が格納されている０選択人口１２には先頭のリスト要素
へのポインタが格納される。選択人口１２に属するリス
ト要素がない場合、選択入口にはヌル値（通常０）が格
納される。

選択入口にヌル値が格納された状態を「空な選択人口１
７」、もしくは「選択入口が空である」という。

本発明の方式を利用した場合、登録は各グループ毎に決
められた登録入口に対して行い、選択は選択入口を上か
ら順に見て行き、最初に見つかった空でない選択入口の
先頭にあるリスト要素を選択することで行うことができ
る。この登録／選択方法はグループ間の優先順位によら
ず、常に固定であり、かつグループ間のどのような順序
づけに対しても最適な選択効率が保証される。

本発明の実現上の特徴は登録入口と選択入口間の結合方
法にある。登録入口と選択入口は以下の手順によって結
合される。

手順１ニゲループ毎に一意の番号をふる。グループの個
数をＮ個とするとグループ番号は１からＮの範囲となる。

手順２：Ｎ個の登録人口１１、Ｎ個の選択人口１２を準
備する。かつ、全ての選択人口１２を未処理とする。

手順３：最高の優先順位を有するグループを選択する０
選択したグループのグループ番号に対応する入口番号を
持つ登録人口１１に、未処理な選択人口１２のうち先頭
のもののアドレスを格納する。同一の優先順位を有する
グループについてはそれらのグループ番号に対応する登
録人口１１が同一の選択人口１２のアドレスを持つよう
にする。登録人口１１にアドレスが登録された選択人口
１２は処理済みとする。

手順４：全でのグループについて手順３を繰り返す。グ
ループを全て処理すれば処理を終了する。

実際にデータ１３を登録する場合、まず発生したデータ
１３が属するグループに対応する登録人口１１を決定す
る。次にその登録人口１１に結合された選択人口１２の
先にあるリスト内に対象データ１３に対応するリスト要
素を登録する。リスト要素の登録時にはデータ１３の優
先順序に従い、最も優先順位の高いデータ１３がリスト
の先頭にくるようにソートして登録する。

上記の処理により、以下が保証される。

（１）登録人口１１からデータ１３を登録した場合、最
も優先順位の高いグループに属するデータ１３は先頭の
選択人口１２に結合される。すなわちある選択人口１２
に結合されるデータ１３の属するグループの優先順位は
、常にそれ以降の選択人口１２から結合されるデータ１
３の属するグループの優先順位より高い。

（２）同一の優先順位をもつグループに属するデータ１
３は同一の選択人口工２に結合される。

［実施例］図２．３．４に本発明による知識ベースシステムにおけ
る実行するルールの選択方法の一実施例を示す。以下に
、２つのルールセット１８．１９が存在し、それぞれの
ルールセットにおいて条件を満たす複数のルールから最
も優先度の高いルールを選択する処理の流れを示す。

ルールセット１８の優先度をＰｌ、ルールセット１９の
優先度をＰ２とし、数値が大きいほど優先度が高いもの
とする。ルールセット１８に属するルールを登録する登
録人口２０、ルールセット１９に属するルールを登録す
る登録人口２１、優先度の高いルールセットのルールを
格納したリストの先頭アドレスを有する選択人口２２、
優先度の低いルールセットのルールを格納したリストの
先頭アドレスを有する選択人口２３を用意する。

ＰＩ＞Ｐ２の場合の構成を図２に示す。登録入口２０は
選択人口２２のアドレスを格納し、登録人口２１は選択
人口２３のアドレスを格納する。ルールセット１８に属
するルールが発生すると、登録入口２０を経由して、選
択人口２２に連なるリストに挿入される。挿入は、新た
に挿入しようとするルールの優先度と選択入口に連なる
リストの各要素（ルール）の優先度を順々に比較して、
より優先度の高いルールはどリストの前部に位置するよ
うに行われる。ルールセット１９に属するルールが発生
すると、登録人口２１を経由して、選択人口２３に連な
るリストに挿入される。選択は、選択人口２２に連なる
ルールセット１８に属するル、−ルのリスト、もし存在
しなければ選択人口２３に連なるルールセット１９に属
するルールのリストの先頭の要素から順に選択すること
で行うことができる。

ＰＩ＜Ｐ２の場合の構成を図３に示す。登録入口２０は
選択人口２３のアドレスを格納し、登録人口２１は選択
人口２２のアドレスを格納する。ルールセット１８に属
するルールが発生すると、登録入口２０を経由して、選
択人口２３に連なるリストに挿入される。ルールセット
１９に属するルールが発生すると、登録人口２１を経由
して、選択人口２２に連なるリストに挿入される。選択
は、選択人口２２に連なるルールセット１９に属するル
ールのリスト、もし存在しなければ選択人口２３に連な
るルールセット１８に属するルールのリストの先頭の要
素から順に選択することで行うことができる。

ＰＩ−Ｐ２の場合の構成を図４に示す。登録入口２０と
登録人口２工は選択人口２２のアドレスを格納する。ル
ールセット１８に属するルールが発生すると、登録入口
２０を経由して、選択人口２２に連なるリストに挿入さ
れる。ルールセット１９に属するルールが発生すると、
登録人口２１を経由して、選択人口２２に連なるリスト
に挿入される。すなわち、異なるルールセットに属する
ルールは異なる登録入口を経由するが、同じリストに挿
入され、ルールセント間の優先度の相違はない。選択人
口２３にはヌル値が格納され、リストは連ならない。選
択は、選択人口２２に連なるルールセット１８若しくは
ルールセット１９に属するルールのリストの先頭の要素
から順に選択することで行うことができる。もし存在し
なければ、選択入口２３に連なるリストを見にいくが、
ヌル値が格納されているため、何も選択されない。

［発明の効果］以上の説明から明かなように、本発明のデータ管理方式
によれば次のような効果が得られる。

（１）グループ間の優先順位が全て異なる場合、選択入
口からはそれぞれのクループに属し、データ固有の優先
順位に従ってソートされたデータが見える。

従って空でない選択入口の先頭データを選ぶのみで優先
順位の低い他のグループに属するデータを検査すること
なく、最も優先順位の高いデータが選択できる。

（２）グループ間の優先順位が同一の場合、選択入口か
らはデータ固有の優先順位に従ってグループと無関係に
ソートされたデータの並びが見える。従って空でない選
択入口の先頭データを選ぶのみでグループを意識しない
データの選択が可能となる。

（３）上記（１）、（２）のように本データ管理方式に
よれば、グループ、データの各優先順位のつけ方に左右
されない最適なデータ選択が可能である。

【図面の簡単な説明】

第１図は本発明によるデータ管理部の構成を示す図、第
２．３．４図は知識ベースシステムにおける一実施例を
示す図、第５図は従来の知識ベースシステムの構成例を
表すブロック図、第６図はルールセット単位に競合集合
を管理する場合の構成例を示す図、第７図はルールセッ
ト間で一元的に競合集合を管理する場合の構成例を示す
図である。１・・・知識ベースシステム２・・・ルール３・・・ワーキングメモリ４・・・推論制御部５・・・ルールセット６・・・競合集合７・・・ルールセット単位の競合集合８・・・最も優先順位の高いルール９・・・システム全体の競合集合１０・、・次に実行するルール１１・・・登録入口１２・・・選択入口１３・・・データ１４・・・リスト要素１５・・・次のリスト要素のアドレス１６・・・グループ１７・・・空な選択入口１８・・・ルールセット１１９・・・ルールセット２

Claims

【特許請求の範囲】

記号化された情報を生成、検索、編集する計算機システ
ムにおいて、該計算機システム内に存在するグループ化
されたデータの集合について、グループ間、及びデータ
間にに一定の優先順位が存在し、各グループ内のデータ
が生成、消滅を繰り返す状態で、グループ間、データ間
の前記優先順位に従ったデータの選択が必要な場合に、
データの登録、選択に専用の管理表を設け、前記優先順
位の特性によらず、最適な効率でデータの選択を可能と
することを特徴とする階層構造を有するデータの登録、
検索方式。