JPS6145329A - 論理言語におけるデ−タトランザクシヨン方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、人工知能言語Ｐｒｏｌｏｇ等の論理言語の上
で、高効率なデータトランザクション方式を実現する方
式に関する。

〔発明の背景〕

人工知能技術のひとつに、各種の概念を“Ａの０はＶで
ある″という形式で格納・検索する方式がある。例えば
Ｐ、　Ｈ，Ｖｉｎｓｔｏｎ、　Ｂ、　Ｋ、　Ｐ、　Ｈｏ
ｒｎ。

“ＬＩＳＰ”　、Ａｄｄｉｓｏｎ−ｖｅｓｌｅｙ　Ｐｕ
ｂｌｉｓｈｉｎｇ　ｃｏｍｐａｎｙ＋１９８１、２２章
他０例えば回路レイアウトにおいであるトランジスタの
レイアウト形状を記憶しておく場合”ｔｒｌのベース拡
散層の形状は４×５の大きさである”という情報の場合
、Ａをｔｒｉ、０をｂａｓｓ　−ｄｉｆｆ　、　Ｖ　ｔ
ｔｓｈａｐｅ　として（４，５）を記憶させておくこと
ができる。

逆にＡと０を与えて、■の値を検索することができる。

上側では、”　ｔ　ｒ　１のｂａｓａ−ｄｉｆｆの５ｈ
ａｐｅは何か”という質問をすると、（４，５）を得る
ことができる。

このように、Ａ、Ｏ，Ｖによる検索方式は簡単な検索キ
ーワード表現を利用しているのみであり自然言語的であ
るために、きわめて多くの概念を記憶、検索することが
できる。

このよう有用な、Ａ、Ｏ，Ｖ検索方式は、今後のＣＡＤ
用情報処理技術で多用されると考えられる。

他方、最近話題になってきている人工知能言語Ｐｒｏｌ
ｏｇ等の論理言語には、バックトラッキング・メカニズ
ム等が内在しており、各種の可能な計画代替案の中から
、有効なものを自動的に探索することができるので、今
後のＣＡＤ技術の中できわめで重要な位置を占めるよう
になると考えられている。

ところが、論理言語が、一般にグローバル変数すなわち
、　ＦＯＲＴＲＡＮ言語におけるコモン変数のようなも
のの使用を許さないために、論理言語上にＡ、Ｏ，Ｖ検
索方式を実現するには、当該言語を用いて記述したプロ
グラム自体をプログラム実行中に変更する方法を取るの
が普通であり、処理効率等が低下する。

〔発明の目的〕

本発明の目的は、論理言語の上にＡ、Ｏ，Ｖ検索等を実
現する論理言語におけるデータトランザクション方式を
提供することである。

〔発明の概要〕

イ、 ｉｉ　　　　　　　　上記目的を達成するため本発明は
、論理言語の持つ局所変数に木構造のデータをもたせ、
外部がら与えられる検索キーワード、Ａ、Ｏ，Ｖによっ
てこの木構造内の情報を検索する点に特徴がある。

〔発明の実施例〕

以下、本発明の一実施例を第１図以下により説明する。

第１図は、本発明のＡ、Ｏ，Ｖデータ検索システムのソ
フトウェア棉成を示している。

第１図に示すように１本システムは基本関数１１０と、
ＡＯＶ検索関数１２０とによって実現される。基本関数
には、木構造定義関数１３０以下３つの関数が利用され
る０本実施例では木構造として２進木を用いる。これら
の関数の本実施例での実際の名称はｂｉｎａｒｙ　（１
３２）　、　ｄｅｌｅｔｅ。

ｖｅｃａｌｌである。

ＡＯＶ検索関数は、データ読み出し関数１５０以下の関
数群より成り、各関数にレベル１の読み出し関数１５２
以下、レベル３までのものが用意されている。データ読
み出し関数のレベル１のもの名称はｆｇｅｔ−ａである
。他の関数にもそれぞれの名称がついている。

第２図は本発明を実施する際のハードウェア環境を示す
図である。結線データの入力はキーボード２．ライトベ
ン３．タブレット４などにより行われる。知識ベース、
データベース等はメモリ装置６．磁気ディスクファイル
５などにより実現される。レイアウト結果や、中間結果
は出力装置であるディスプレイ７、作図機８．プリンタ
９などにより実現される。

第１図１３２の木構造定ａ関数の実体をプログラムリス
ト（１）に示す、２００は２進水中のノードＫ　（Ｋ、
Ｐ）から、キーにに対応した情報Ｐｒｏｐを検索する関
数であり、２１０は２進木の主枝検索用関数、２２０は
有枝検索用関数、２３０は空枝検索時に新規情ノードＫ
　（Ｋ、　Ｐｒｏｐ）を木に追加する関数である。なお
１図でｔ　（Ｘ　ｖ　Ｋ　（Ｋ　ｒ！’ｒ吐）Ｉ　ｚ＞
は、２進水を示しており、Ｘは主枝。

Ｚは有枝−Ｋ　（Ｋ　ｐ　Ｐｒｏｐ）はキーに、情報Ｐ
ｒｏｐを持つノードであるａ　ｖｏｉｄは空枝を示して
いる。

プログラムリスト（１） ｂｉｎａｒｙ（ｔ（Ｘ＋Ｋ（ＫｔＰｒｏｐ）　＋Ｚ）　
Ｊ（Ｋ、Ｐｒｏｐ）　。

ｔ（Ｘ、Ｋ（に、Ｐｒｏｐ）、ｚ））−２００ｂｉｎａ
ｒｙ（ｔ（Ｘｅに（Ｙ＋Ｐ）ｔＺ）ｖＫ（Ｋ、Ｐｒｏｐ
）。

ｔ（Ｘｉ、Ｋ（Ｙ、Ｐ）　、Ｚ））ニー　　　　　　　
　　　　　　　　２１０に＠＜Ｙｅｂｉｎａｒｙ（Ｘｅ
Ｋ（ＫｔＰｒｏｐ）　ｅＸｌ）　−ｂｉｎａｒｙ（ｔ（
Ｘ、Ｋ（Ｙ、Ｐ）、Ｚ）ｗＫ（ＫｖＰｒｏｐ）ｔｔ（Ｘ
、ｘ（Ｙ、ｐ）、ｚｉ））ニー　　　　　　　　　　　
　　　　２２０に＠）Ｙ、ｂｊｎａｒｙ（ＺｅＫ（Ｋ、
Ｐｒｏｐ）　、Ｚｌ）。

ｂｉｎｎｒｙ（ｖｏｉｄ、Ｋ（Ｋ、Ｐｒｏｐ）　。

ｔ　（ｖｏｉｄ　、　Ｋ　（Ｋ　＊　Ｐｒｏｐ　）　、
　ｖｏｉｄ　））、　　　　　　　　　　　　２３０プ
ログラムリスト（２）は木構造から情報を消去するため
の関数である。３００は、木構造ｔ　（Ｘ。

Ｋ　（Ｋ、　Ｐｒｏｐ）　ｅ　ｖｏｉｄ）からノードＫ
　（Ｋ、　Ｐｒｏｐ）を消去すると、残りはＸになると
いうことを示している。３１０から３５０も木構造から
情報を消去するための関数である。各々は消去する方法
が木構造の特性に依存するため、特性に応じて消去操作
を実施するようになっている。

プログラムリスト（２） ｄｅｌｅｔｅｃｔ　（ＸＪ（Ｋ、Ｐｒｏｐ）　ｐＶｏｉ
ｄ）　Ｊ、　（Ｋ、Ｐｒｏｐ）　、Ｘ）、　−３００ｄ
ｅｌｅｔｅ（ｔ（Ｘ、Ｋ（Ｋ、Ｐｒｏｐ）　ｙｔ（ｖｏ
ｉｄｅＹｌ＊Ｚ１））　ｔＫ（Ｋ、Ｐｒｏｐ）、ｔ（Ｘ
、Ｙｌ、Ｚｌ））、　　　　　　　　　　　３１０ｄｅ
ｌｅｔｅ（ｔ（Ｘ、Ｋ（Ｋ、Ｐｒｏｐ）　、ｔ（ＸＩ、
ＹｌｓＺｌ））　ｔＫ　（Ｋ　＝Ｐｒｏｐ）　−ｔ　（
Ｘ　ｙＹｅ　ｔ　（Ｘ２．Ｙｌ−Ｚｌ）　））　ニー３
２０ｓｕｃｃｅｓｓｏｒ（Ｘｉ、Ｙ、Ｘ２）。

ｄｅｌｅｔｅ（ｔ（ＸＪ（ＹｔＰ）　ｔＺ）　Ｊ（Ｋｔ
Ｐｒｏｐ）　ｖｔ（Ｘｉ、Ｋ（Ｙ、Ｐ）、Ｚ）戸−□３
３０に＠＜Ｙ、ｄｅｌｅｔｅ（Ｘ、Ｋ（Ｋ、Ｐｒｏｐ）
、ＸＩ。

ｄｅｌｅｔｅ（ｔ　（ＸＪ　（ＹｔＰ）　ｔＺ）　ｔＫ
　（Ｋ、Ｐｒｏｐ）　、　ｔ　（Ｘ、　Ｋ（Ｙ、Ｐ）　
ｔＺｌ））　ニー□３４０ に＠＞Ｙ、ｄｅｌｅｔｅ（Ｚ、Ｋ（Ｋ、Ｐｒｏｐ）　、
Ｚｌ）。

ｄｅｌｅｔｅ　（ｖｏｉｄ　、に（Ｋ、Ｐｒｏｐ）、ｖ
ｏｉｄ）、　−３５０ｓｕｃｃｅｓｓｏｒ（ｔ　（ｖｏ
ｉｄ−ＹｙＺ）　＋Ｙ＋Ｚ）　−３６０ｓｕｃｃｅｓｓ
ｏｒ（ｔ（Ｘ、Ｙ＋Ｚ）　＋Ｙ１．ｔ（Ｘｉ、Ｙ、Ｚ）
）　ニー　　　　　　　　３７０ｓｕｃｃｅｓｓｏｒ（
Ｘ、Ｙ１＋Ｘ１）。

３２０で使用する関数９１ＪＣＣＯ５５０ｒは、木構造
内のあるノードに著呂して、そのノードの後続木を取り
出す関数であり、実体は３６０，３７０に示したものに
なっている。

第１図中の木構造検索関数を、プログラムリスト（３）
に示す、４００は、木構造を持つ局所変数Ｄｉｃｔｉｏ
ｎａｒｙの中から、キーＫｅｙを持つノードを見出し、
その内容をＡｎｓに出力する関数である。

関数の右辺では、上述したｂｉｎａｒｙ関数を用いてい
る。

第１図中のＡＯＶ検索関数の実体をプログラムリスト（
４）に示す、５００は、木構造局所変数Ｄｉｅの中から
、単一レベルのキーＡで、情報内容をＡｎｓに取り出す
関数である。５０５は、２レベルのキーＡ、Ｏで、Ａ　
ｎ　ｓに情報を取り出す。

５０６は３レベルＡ、Ｏ，Ｖに対応する情報を取り出す
。

５１５は、旧い木Ｄｉｃｏｌｄ内に、キーＡしこ対応し
て情報Ｉｎを記入したものを、新しＮ木Ｄｉｃｎｅすと
する関数である。５２０，５２５はキーを２レベル、３
レベルにした関数である。

５３０〜５４０は木構造の１部を消去する関数、５４５
〜５５５は木構造の１部を変更する関数である・ プログラムリスト（３） ｒｅｃａｌｌ（Ｋｅｙ、Ｄｉｃｔｉｏｎａｒｙ、Ａｎｓ
）　ニー　　　　　　　　　　　４００ｂｉｎａｒｙ（
Ｄｉｃｔｉｏｎａｒｙ、Ｋ（Ｋｅｙ、Ａｎｓ）、−）。

プログラムリスト（４） ｆｅｅｔ−ａ（Ａ、Ａｎｓ、Ｄｉｃ）　ニーｒｅｃａｌ
ｌ（Ａ、Ｄｉｃ、ムｎｓ）、　−ｓｏ。

ｆｓａｔ−ａ−ｏ−ｖ（Ａ、Ｏ，Ｖ、Ａｎｓ、Ｄｉｃ）
ニーｆｓａｔ−ａ−ｏ（Ａ、０．Ｄｉｃｌ、Ｄｉｃ）、
　−５１０ｆｓｅｔ−ａ（Ｖ、ＡｎｓｅＤｉｃｌ）。

ｆｐｕｔ−ａ（０，Ｉｎ、Ａｎｓ、Ａｎｓｎｅｗ）　。

ｆｐｕｔ−ａ（Ａ、Ａｎｓｎｅｖ、Ｄｉｃｌ、Ｄｉｃｎ
ｅｖ）。

ｆｐｕｔ−ａ−ｏ−ｖ（Ａ、Ｏ，Ａｎｓｇ、Ｄｉｃｏｌ
ｄ、Ｄｉｃｎｅｗ）ニー　　　　　　５２５ｆｄｅｌ−
ａ（Ａ＊Ａｎｓｌ、Ｄｉｃｏｌｄ、Ｄｉｃｌ）　。

ｆｐｕｔ−ａ−ｏ（０，ｖＪｎｓ、Ａｎｓｌ、Ａｎｓ２
）　。

ｆｐｕｔ−ａ（Ａ、Ａｎｓ２．Ｄｉｃｌ、Ｄｉｃｎｅｖ
）　。

ｆｄａｌａ（Ａ、Ａｎｓ、Ｄｉｃｏｌｄ、Ｄｉｃｎａｖ
）　ニーｄｅｌｓｔａ（Ｄｉｃｏｌｄ、Ｋ（Ａ、Ａｎｓ
）、Ｄｉｃｎｅｗ）、　−５３０ｆｄｅｌ−ａ−ｏ＜Ａ
、０．Ａｎｓ、Ｄｉｃｏｌｄ、Ｄｉｃｎｏｖ）　ニーｄ
ｅｌｅｔｅ　（Ｄｉｃｏｌｄ　、　Ｋ　（＾、Ｉｎｔ）
、Ｄｉｃｌ）、　−５３５ｄｅｌｅｔｅｓ（Ｉｎし、Ｋ
（０，Ａｎｓ）Ｊｎｔ２）＋ｆｐｕｔ−ａ（Ａ、Ｉｎｔ
２．Ｄｉａｌ、口１ｃｎｅｖ）　。

ｆｄｅｌ−ａ−ｏ−ｖ（Ａ、Ｏ，Ｖ、Ａｎｓ、Ｄｉｃｏ
ｌｄ、Ｄｉｃｎａｖ）ニー　−５４０ｆｄｅｌ−ａ（Ａ
＋ＡｎｓｌｖＤｉｃｏｌｄ、Ａｎｓ２）。

ｆｄｅｌ−ａ−ｏ（０，Ｖ、Ａｎｓ、Ａｎａｌ　、Ａｎ
ｓ３）　ｖｆｐｕｔ−ａ（Ａｔ＾ｎｓ３．Ａｎｓ２．Ｄ
ｉｃｎａｖ）。

ｆｃｈａｎｓｅ−ａ　（＾、Ｉｏ１ｄ、Ｉｎｏｗ、Ｄｉ
ｃｏｌｄ、Ｄｉｃｎａｖ）ニー　−□　５４５ｆｄａｌ
ａ（ＡＪｏｌｄ、Ｄｉｃｏｌｄ、Ｄｉｃｌ）　。

ｆｐｕｔ−ａ（Ａ、Ｉｎａｖ、Ｄｉｃｌ、Ｄｉｃｎｅｗ
）。

ｆｃｈａｎｓｅ−ａ−ｏ（Ａ、Ｏ，Ｉｏｌｄ、Ｉｎｅｖ
、Ｄｉｃｏｉｄ、Ｄｉｃｎｅｖ）ニー　−５５０ｆｄｅ
ｌ−ａ−ｏ（Ａ、０．Ｉｏｌｄ、ＤＪ、ｃ、ｏｌ、ｄ、
Ｄｉａｌ）。

ｆｐｕｔ−ａ−ｏ（Ａ、Ｏ９工ｎｅｔｓ、ＤｉｃｌｅＤ
ｉｃｎｅｖ）。

ｆｃｈａｎｓｅ−ａ−ｏ−ｖ　（Ａ　、　Ｏ、Ｖ　、　
Ｉｏｌｄ　、　Ｉｎｅｖ　。

Ｄｉ＋；、、ａ、Ｄｉｚ：：＝ｚ、ニー　　−−−−一
−−−−−−−−−５５５ｆｄｓｌ−ａ（Ａ、Ａｎｓｌ
、Ｄｉｃｏｌｄ、Ａｎｓ２゜ｆｃｈａｎｓａ−ａ−ｏ（
０，Ｖ、Ｉｏｌｄ、Ｉｎｅｗ、ＡｎｓＬ、Ａｎｓ３）　
。

ｆｐｕｔ−ａ（Ａ、＾ｎｓ３．Ａｎｓ２．Ｄｉｃｎｅｖ
）。

プログラムリスト（５） ＡｎシＩ：４，５］、　−−−−−６１０プログラムリ
スト（５）は、プログラムリスト（４）の関数の使用例
を示すものである。

６００は、トランジスタ（ｔｒｉ）のベース拡散ＪＩＦ
Ｆ　（ｂａｓｅ−ｄｉｆｆ）の形状（ｓｈａｐｅ）は［
４，５］であるという情報を、木構造Ｄｉｃｌに追加し
て新しい木構造Ｄｉｃ２を作成したのち、再度。

ｔｒｉのｂａｓｅ　−ｄｉｆｆの５ｈａｐｅは何かと質
問して、６１０に示すＡｎｓ＝　［４，５］と返答を得
たことを示している。

６２０は、同じ情報を木構造Ｄｉｃ２に記憶させたのち
、形状（４，５）を（６，８）に変更させ、正しく変更
されたか否かを出力チェックした例である６６３０に示
ずように、正しく変更されている。

以上述べたように、本発明方式が、検索効率等を低下さ
せることなく、論理言語の上に実現できる理由は、検索
効率の良い木構造を論理言語上に作成し、それを用いて
ＡＯＶ検索方式を実現しているからである。

以上述べた内容により１本発明はＣＡ　Ｄ　ｕＱ計自動
化等の図形情報、！！？計情報等のデータベース。

知識ベースの検索、入力変更、＠正アップデート等を従
来の言語で極めて高速化する事を可能とする。

またその適用範囲はデータトランザクションの伴う分野
において、翻訳、認識、ルール処理等に広く適用して効
率向上効果をもたらすものである。

〔発明の効果〕

本発明によって、今後のＣＡＤシステム等で重要となる
といわれているＰｒｏｌｏｇ言語等の論理言語の上に、
これまでＣＡＤシステムで重要と言ねれていながら、こ
れらの盾語の上に実現することは検索効率等の面から問
題であったＡＯＶ検索方式を検索効率を低下させること
なく実現することが）１　　　　　　できる。従来のよ
うにプログラム自体をグローバル変数を使用したプログ
ラムに変更する場合に校べ、桁違いに高速化することを
可能とするものである。

レイアウトＣＡＤのように、数多くの複雑な形状物を計
算機システムに記憶させておき、形状物同志の間の配置
位置案を各種試行して、その中から最適なものを選択す
るには、論理言語のもつ代替案探７ｆＪ機能と、ＡＯＶ
検索方式の持つ形状物等の表現力を双方とも利用できる
ことが望ましい。

本発明によって、これが可能となる。

【図面の簡単な説明】

第１図は本発明ＡＯＶ検索方式を構成する関数の説明図
、第２図は本発明実施例実施の際のバー第　２　　図

Claims (1)

【特許請求の範囲】
1. 論理言語における局所変数に木構造の情報を持たせてお
   き、該木構造上の情報検索、情報記入、情報変更などの
   トランザクションをおこなう基本関数群と、該基本関数
   群を使用して、キーワードによる木構造上の情報トラン
   ザクションをおこなう一連の関数群とから成る、論理言
   語におけるデータトランザクション方式。