(57)【特許請求の範囲】
【請求項１】
中央演算処理手段、バス手段、表示手段、データ入力手段、メモリ手段、データ記憶手段、及びグラフィカルユーザインタフェースを備えたデータベースの設計仕様を指定するための汎用プログラム可能なデジタルコンピュータを含む装置であって、
モデル化される情報を表現する図表を前記表示手段上に表示するための図表手段と、
前記図表上でカーソルの動きを制御するためのカーソル制御手段と、
前記コンピュータ上で実施される関係データベース手段を含むリポジトリ手段と、
ユーザが、データオブジェクト、該データオブジェクトに関する事実、及び該データオブジェクトに対する制約を項目に含むコンパイルのためのソーステキストを、前記データ入力手段を用いて編集ウィンドウに入力できるテキスト入力手段と、
前記テキストを確認するための、ユーザが選択可能なテキスト確認手段と、
前記テキスト入力手段から入力されたテキストを前記図表に変換するための、ユーザが選択可能な変換手段と、
前記テキストを前記リポジトリ手段にのみコンパイルするための、ユーザが選択可能な第１のコンパイル手段と、
からなる装置。
【請求項２】
中央演算処理手段、バス手段、表示手段、データ入力手段、メモリ手段、データ記憶手段、グラフィカルユーザインタフェース、及びコンピュータ上で実施される関係データベース手段を含むリポジトリ手段を備えた汎用プログラム可能なデジタルコンピュータ上で、データベースの設計仕様を指定するための方法であって、
モデル化される情報を表現する図表を前記表示手段上に表示するステップと、
前記図表上でカーソルが移動されたことを示す指示を受信するステップと、
前記データ入力手段から編集ウィンドウに入力された、データオブジェクト、該データオブジェクトに関する事実、及び該データオブジェクトに対する制約を項目に含むコンパイルのためのソーステキストを受け取るステップと、
ユーザが選択可能なオプションに応答して、前記テキストを確認するステップと、
ユーザが選択可能なオプションに応答して、前記テキスト入力手段から入力されたテキストを前記図表に変換するステップと、
ユーザが選択可能なオプションに応答して、前記テキストを前記リポジトリ手段にのみコンパイルするステップと、
からなる方法。
【請求項３】
中央演算処理手段、バス手段、表示手段、データ入力手段、メモリ手段、及びデータ記憶手段、並びに、データベースの設計仕様を指定し、該データベースに対する照会文を作成し、該照会文を自然言語で記述するためのグラフィカルユーザインタフェースを備えた汎用プログラム可能なデジタルコンピュータを含む装置であって、
モデル化される情報を表現する図表を前記表示手段上に表示するための図表手段と、
前記図表上でカーソルの動きを制御するためのカーソル制御手段と、
前記コンピュータ上で実施される関係データベース手段を含むリポジトリ手段と、
ユーザが、データオブジェクト、該データオブジェクトに関する事実、及び該データオブジェクトに対する制約を項目に含むコンパイルのためのソーステキストを、前記データ入力手段を用いて編集ウィンドウに入力できるテキスト入力手段と、
前記テキストを確認するための、ユーザが選択可能なテキスト確認手段と、
前記テキスト入力手段から入力されたテキストを前記図表に変換するための、ユーザが選択可能な変換手段と、
前記テキストを前記リポジトリ手段にのみコンパイルするための、ユーザが選択可能な第１のコンパイル手段と、
前記照会文に基いて事実ツリーを形成するための事実ツリー形成手段と、
根ノードを含む前記事実ツリーに関する説明を前記自然言語で生成するための事実ツリー記述手段と、
前記根ノードを入力として用い、前記根ノードに対応する第１の照会文を前記データベースに適したコンピュータ言語で返すことにより、照会文を前記関係データベース手段にマッピングするための、照会文マッピング手段と、
からなる装置。
【請求項４】
中央演算処理手段、バス手段、表示手段、データ入力手段、メモリ手段、データ記憶手段、及びグラフィカルユーザインタフェースを備えた汎用プログラム可能なデジタルコンピュータ上で、データベースの設計仕様を指定し、該データベースに対する照会文を生成し、該照会文を自然言語で記述するための方法であって、
モデル化される情報を表現する図表を図表手段を用いて前記表示手段上に表示するステップと、
前記図表上でカーソルが移動されたことを示す指示を受信するステップと、
前記コンピュータ上で実施される関係データベース手段を含むリポジトリ手段を作成するステップと、
データオブジェクト、該データオブジェクトに関する事実、及び該データオブジェクトに対する制約を項目に含むコンパイルのためのソーステキストを、前記データ入力手段を用いて編集ウィンドウに入力するステップと、
ユーザが選択可能なテキスト確認手段を用いて、前記テキスト入力手段からの前記テキストを確認するステップと、
ユーザが選択可能な変換手段を用いて、前記テキストを前記図表に変換するステップと、
ユーザが選択可能な第１のコンパイル手段を用いて、前記テキストを前記リポジトリ手段にのみコンパイルするステップと、
事実ツリー形成手段を用い、前記照会文に基いて事実ツリーを形成するステップと、
事実ツリー記述手段を用いて、根ノードを含む前記事実ツリーに関する説明を自然言語に近いコンピュータ言語で生成するステップと、
照会文マッピング手段を用いて、前記根ノードを入力として用い、前記根ノードに対応する第１の照会文を前記データベースに適したコンピュータ言語で返すことにより、照会文を前記関係データベース手段にマッピングするステップと、
からなる方法。
【発明の詳細な説明】
技術分野
本発明は、コンピュータ・データベース・システムの構築、及びそこに含まれるデータの照会に関する。特に、本発明は、データベース設計をモデル化し、そのデータベースに含まれるデータの照会を指定するためのコンピュータ化されたツールに関する。
技術分野の背景
コンピュータ化された関係データベースは、現実の世界の問題をモデル化する情報システムを形成するのに用いられ、オブジェクト、関係（即ちそれらのオブジェクト間の事実）、及びこれらの関係とオブジェクトを管理する制約とルールから構成される。オブジェクトは物理エンティティー又は論理エンティティーであり、ユニークなものとして識別されうる。この点で、オブジェクトは基本的に名詞に似ていると言われる。事実は、オブジェクトの相互作用の方法を定義し、基本的に動詞であるかまたは動詞に似ている。制約は、オブジェクトと事実の間の相互関係を修正または制限し、このようなものは副詞かまたは代名詞に類似している。情報システムが多く利用されるにつれて、及びこのシステムの設計が進歩するにつれて、正確にモデル化しようとする現実の世界の問題も複雑になってくる。
情報システムを構築する際に、ユーザは正確に（データの外部ビューとしても知られる）現実世界のモデルを、実際の物理的な実施に、特定のコンピュータ・システムに関する特定のデータベース言語を用いて変換する必要がある。この実施は物理ビューとも呼ばれる。関係データベースにおける固有の能力を引き出すためには、コンピュータの知識がないかまたはコンピュータ教育を受けていない人が、情報管理システムの設計と実施、及びそこから意味のあるデータを特別なコンピュータ言語を習得する必要無しに照会することができなければならない。
情報システムの物理ビューは多くのデータベース設計言語のうちの１つで表現される。当業者に周知のデータベース設計言語の例は、構造化照会言語（SQL）とマイクロソフト社のACCESSである。これらのデータベース設計言語は記憶を実行し、その後データベースに記憶されたデータを検索するのに非常に適しているが、言語自身は自然言語でなく、高度な技術を要する。このことは、データベース設計言語が通常、その言語による情報システム・モデルのエンド・ユーザによって使用されていないか又は理解されていないと言うことを意味している。
外部ビューから物理ビューへの情報システムの変換には、時間を要し、それが技術的な形式から成る何かである限りは、すぐに形式化される。情報システム設計に関するデータをモデル化する際のデータベース分析を支援するために、いくつかのCASEツール・セットが開発されており、当業者には周知である。
従来のCASEツール・セットは一般にエンティティー関係モデル（ER）に基づいていた。ERモデルは、アプリケーションの大部分の特徴を集約する便利な手段を提供するものの、通常は、そのアプリケーションで共通に発生する多くの制約と、派生ルールを表現することができない。ERベースのツールの概略は、Ovum（1992年）とReiner（1992年）に見ることができる。この技術の状況の例はCzejdo他において議論されている（IEEE Computer,1990年３月26−27ページ）。
アプリケーションの、より詳細な部分を把握するために、事実指向モデルとしても知られる、オブジェクト役割モデル（ORM）が開発された。当業者の周知のORMのバージョンは、自然言語情報分析技法（NIAM）、２進関係モデル（BRM）、自然オブジェクト役割モデル（NORM）、及び述語生成器セット・モデル（PSM）を含んでいる。あるORMのバージョンでは、形式オブジェクト役割モデル（FORM）が、NIAMに対する拡張に基づいており、グラフィック、及びテキスト形式の両方を有する（HalpinとOrlowska、1992年）支援言語（FORML）を備えている。FORMとFORMLの一部は、本発明の発明者の１人によって開発された。
シンボル駆動型CASEツール・セットを使用することによって、所与の情報システム・モデルを概念化するための強力な手段が提供されるが、これを使用することは、訓練されていないユーザにとって直感的な明確さに欠ける。こうしたユーザにとって、ユーザが既に容易に使いこなせる言語を用いて情報システムをモデル化できると言うことは、より強力なアプローチである。FORMLはユーザに自然言語に似たコマンド・セットを提供し、従って習得が容易である。
オブジェクト役割モデルに関するいくつかのCASEツール・セットが存在する。当業者に周知のこれらのツール・セットは、RIDL（1988年、Detroyer他;1989年、Detroyer;1990年、Nienhuys−cheng）、GIST（1988年、Shoval他）、及びIAST（1982年、Control Data）である。RIDLは現在Intellibaseによって販売されている。RIDLには最近、さらに大きなアリティの事実タイプの支援が追加されたが、それらのORMベースのCASEツール・セットは一般に、２進のみのバージョンのORMにしか適合しない。概して、これらのシステムは、図表上のシンボルの明白な「描画」に基づいている。これらのツール・セットのユーザは通常、図表上に直接シンボルを置くことによって情報システムを指定する。典型的なCASEツール・セットでは、使用されるシンボルのタイプ毎に別のツールが使われる。これらのツール・セットの重要な点は、シンボルの表記法に関するものであり、それは、その表記法が基づく言語の潜在的な意味に関するものではないことを意味している。
ORMから標準化された関係テーブルへのマッピングに関する「最適標準形式」技法は、1970年にNIAMにおいて紹介されている。この技法は、あるケースを無視し、制約マッピングに関する方法論について非常に不完全な仕様を提供した。NIAMに対する多くの拡張によって、FORMLのグラフィック・バージョンにおいて表現されるすべての概念スキーマを冗長フリーの関係スキーマに完全にマッピングすることができ、これはRMAP（関係マッピング、1992年、RitsonとHalpin）として紹介されている。RMAPは、例えばｎに関する（ｎ−ary）サブセット、同等、排他、閉鎖、及びリングなどの制約のバリエーションをより多くすることができる点で、RIDL−Ｍのような他のマッピング技法とは異なる。
ORMベースのCASEツール・セットを使用しているデータベースのプロは、そのツール・セットを使用していない同等の作業者よりも極めて生産性が高い。RMAPのようなマッピング・スキーマを含むツール・セットは、より強力でもあり、更に生産性を向上させる。RMAPを実装したFORMLベースのツール・セットは、ORMベースのツール・セットに関する技術の現在の状況を表現している。FORMLのグラフィカル、及びテキスト言語形式が提供されると、現代のコンピュータ・システムで共通のグラフィカル・ユーザ・インタフェースで簡単で迅速に使用することができるORMベースのCASEツール・セットの能力、柔軟性、及び正確さを兼ね備えることになる。このことは、コンピュータのプロによって使用された場合にCASEツール・セットの生産性を更に向上させる効果があるばかりでなく、コンピュータの初心者が使用した場合にも同様に強力なソフトウエア・エンジニアリング・ツールを提供する効果を有する。
従来の自然言語CASEツールがそれらの基本概念の約束のいくつかを果たしてはいるが、それらは、複雑なデータベースを容易にモデル化するためのシンボル駆動型システムの能力に欠ける。本発明の前までは、自然言語に似た構造をORMのシンボルに変換し、こうして形式化された概念スキーマを、多くのSQLに似たデータベース言語に関して実施される関係スキーマに自動的にマッピングするためのグラフィカル・ユーザ・インタフェースを備え、自然言語に似た構造を用いる、ORMの能力、柔軟性、及び正確さを兼ね備えたデータベース設計のためのCASEツール・セットはなかった。本発明は、ORMベースの図表上にシンボルを描画するのに必要なユーザ・オペレーションの数を、ユーザが自然言語に近いもので情報を記述できることによって1/6にするという効果を有する。ユーザは情報の意味について考えることができ、シンボルを描画するのに時間を費やさなくてすみ、このことが意味を考える処理を縮小させる。
前述した、従来のER、及びORMベースのツール・セットに加え、異なる方法論を用いてデータベースの指定処理を自動化する努力が研究者によってなされてきた。より関係のある試みのいくつかを後述する。
Thompson他による米国特許第4,688,196号は、初心者がメニュー駆動型インタフェースのシステムに基づいてデータベースを生成、照会できる、自然言語インタフェース生成システムを教示している。ユーザが自然言語で、インタフェース生成システムに対しコマンド・ワードを指定する場合は、ワードが入力されたときに各ワードの後に合法的に続くワードのメニューが提供される。このメニューは、事前に定義され、常駐するファイルを参照することによって提供される。Thompsonはこれらのファイルを文法、及び辞典と呼んでいる。ユーザによって入力されたコマンドは、システムによって変換され、それはその後、以下に示す方法で、必要なインタフェースを生成するための自動相互作用システムを提供する。
データベースがロードされた後、インタフェース生成システムは、ユーザの技術熟練者に対して一連の質問を行う。これらの質問に応答して、ユーザ、またはその熟練者はデータベース内のどのテーブルが使用されるべきか；特定のテーブルのどの属性がキー属性か；データベース内の様々なテーブル間の様々な接続は何か；及びこれらの関係を記述するフレーズと接続している自然言語は何かを確認しなくてはならない。
Davis他による米国特許第4,939,689号は、テキスト駆動型アウトライン・システムを使用することによって、データベース構造の生成と、これらの構造をその後照会するためのシステムを教示している。Davisのシステムは別の形式の常駐辞書テーブルを使用し、これもまた事前に定義される。Davisのシステムでは、ユーザはデータベースのフォーマットを定義するテキストのアウトラインを入力する。このアウトラインは次に、データ入力を容易にするデータ入力スクリーンを生成するのに用いられる。
データベース情報システムを生成した後で（かつ、これらのシステムに属するデータが、入力されたと仮定すると）、この情報システムは正確に照会されなければならない。他の当業者による努力によって、初心者に照会文の作成を可能にする２つの広い戦略が教示されている。
照会文を生成する問題に対する従来技術における解決法は、自然言語解析型を用いることである。この方法論は、英語や日本語のような好ましい自然言語で入力される照会文を採用し、照会文をその構成要素部分に解析する。照会文の各構成要素は次に、元の自然言語照会文をデータベース言語の照会文に変換するために使用される。本発明の前までは、これは通常、解析されたワードやフレーズを、それぞれデータベース設計言語におけるそれらの同義語に変換する常駐データベースまたは辞書の何らか形式によって達成される。
Takanashi他の、1992年７月10日に出願されたヨーロッパ特許出願、EP 0522591A2は、典型的なこの「解析とルップアップ」戦略のシステムを教示しており、このシステムによって、自然言語照会文が入力され、その構成要素部分に解析される。解析系は、常駐文法テーブルと常駐用語辞典を使用して、個々のコマンド・ワードとフレーズの意味をデータベース設計言語に変換する。この解決法を完全に実施する際に困難なのは、費用と能力であり、即ちほとんどの自然言語のサイズと可変構造である。可能な各ワード、および多くのフレーズは、システムを本当に役立つものにするため、常駐テーブル内に対応するエントリを有する必要がある。このエントリがないと、自然言語インタフェースの能力は、コマンドがシステムに理解されないという点で実質的に低下する。
金銭上、及びコンピュータのオーバヘッドにおいて、大きな、常時常駐する、任意の実質的な情報システムに対する自然言語インタフェースが生成され、維持コストは法外なものになる。更に、エンド・ユーザは依然として、解析系と常駐辞書ファイルが理解できる質問とキーワードのタイプを知る必要がある。これは、常駐テーブルの方法論が十分にデータ・オブジェクトとそれらのオブジェクトに関する制約の間の関係を考慮に入れていないためである。例えば、ユーザがスミス氏の年を知りたい場合、スミスは人であったり塔であったりするので、「How old is Smith?」と訪ねるだけでは不十分である。そうではなく、ユーザは「How old is the person called Smith?」とタイプしなければならない。従って、自然言語解析系を使用した場合の学習曲線は、依然として極めて高い。
従来技術における照会文生成の問題を解決する第２の方法は、照会ツールを使用することである。照会ツールはデータベースの物理構造に基づいており、その中の情報に基づいたものではない。情報が、相互作用概念オブジェクトの集合、即ち記憶させたいもの、例えば人、住所などの集合として広範に分類されうる。事実は、例えば、「a Person lives at an address」といったオブジェクト間の関係である。情報がデータベース内に記憶されたときに、その情報は、例えばテーブルのような物理構造の集合として表現される。エンド・ユーザの一部に、データベースの専門技術がかなり欠けているものがいる場合、データの物理表現は、彼らにとっては相変わらず理解できないものとなる。従って、こうした初心者が前記物理構造で記憶されたデータの、物理構造に基づく照会を行なうためには、これらの物理構造をしっかり理解するようにかなりの訓練を積む必要がある。
自然言語解析系、または物理構造照会ツールを用いて照会文を記述する際に、最後の問題が残っている。ユーザは最終的にどちらかの処理によって形成される照会文が、実際に正しく解析されるものになることを保証することができない。物理構造を照会する場合、十分な訓練がないと、初心者ユーザはデータが記憶される方法を理解できない。自然言語解析系を使用した場合、その自然言語におけるあいまいな固有情報のために同様の問題が生じる。例えば、ユーザが「How old is Smith?」と尋ねると、コンピュータは「55」と答える。この答えは、スミスという人に関するものかもしれないし、スミスの塔に関するものかもしれない。これは、ケーリー・グラントの年を尋ねようと彼の代理人に電報を打ったレポーターを思い出させる。レポーターは、送信する電報の文字数毎の料金を気にして、「ケーリー・グラントの年は幾つですか？（HOW OLD CARY GRANT?）」という質問文を打った。その俳優は、不注意でその電報が彼に配達されたとき、電報で「年をとったがケーリー・グラントは元気だよ（OLD CARY GRANT JUST FINE）」と返信した。明らかに、照会文の構文が正しくなければ、初心者ユーザは不確かな答えを得るかまたは、意図していない照会文に対する答えを得ることになる。
前述した、従来技術のCASEツール共通の設計上の特徴は、事前に定義されたテーブル、または自然言語入力の変換を行い、データ・オブジェクト、事実、制約、及びそれらの相互関係の正確な性質を指定するテーブルを使用することである。前述のように、この方法論は費用がかかり、効果的でなく、十分な効果が得られない。
現在情報システムの指定に使用されているCASEツールの更なる設計上の特徴は、自然言語の代わりにシンボルを使用していることである。シンボル駆動型CASEツール・セットは、シンボルのチャートからコンピュータ言語におけるデータベース指定に変換を行うためにいくつかのステップを必要とするため、すぐに不正確で厄介なものになる。
従って、ユーザが自然言語または自然言語に似たコマンドを用いて、情報システムを指定し、生成できる装置に対する需要があり、それは、システム・オブジェクト、事実、及び制約を、曖昧さや過度のオーバヘッドなしに正確に指定するものである。これは、曖昧さのない方法でデータ要素間の相互関係を定義するために、グラフィカルな描写が可能であることを意味している。システムを生成するために使用される情報は、データベース自身の構造と、一旦完成したデータベースに対するその後の照会文を定義するのに使用できる。初心者ユーザが、以前に入力された変換テーブル内の定義に制限されることのない、自然言語に似たコマンドを再び使用して、システムに対するこうした照会文を指定できる手段に関する別の需要がある。更に、情報システムにアクセスするために生成された任意の照会文が正確に、曖昧さなく、ユーザの意図する質問を伝えて、正確で曖昧さのない答えを返答することを保証する手段に関する別の需要がある。
発明の開示
本発明は、ユーザが、
1.自然言語に似たコンピュータ言語（こうした言語の１つはFORMLである）に対するグラフィカル・ユーザ・インタフェースを用いて情報システム記述を開発でき、
2.照会文生成に関する事実ツリーを指定でき、
3.意味が正しいか照会文をチェックでき、
4.データベース・システムに対して照会文を生成できるような方法、及び装置を提供する。
情報システムを生成する必要があるという決定がなされたら、本発明の事実コンパイラが実行される。事実コンパイラのコンパイル機能は、ユーザに自然言語に似たコンピュータ言語を使用した、テキストでのタイプを可能とする。このような言語の１つはFORMLである。テキストはシステムによって提供されるウインドウ内にタイプされ、オブジェクト（ここでは名詞としても呼ばれる）、事実（ここでは事実タイプまたは文としても呼ばれる）、及び／または制約を含む可能性がある。「図表上のドラッグ・アンド・ドロップ」と呼ばれる変換関数とグラフィカル・ユーザ・インタフェースを用いて、ユーザは、テキストを入力ウインドウから事実コンパイラのORM概念スキーマ図表上の適当な場所にドラッグする。次にユーザは、そのテキストを図表上にドロップする。事実コンパイラはその入力されたテキストを確認し、発生したエラーをユーザに知らせる。確認の間、事実コンパイラは最初にテキストを解析し、オブジェクト・リスト、事実リスト、及び制約リストをメモリ内に生成する。次に、事実コンパイラは反復的にテキストをリポジトリにコンパイルする。このリポジトリは、基本的に「データベースのデータベース」である。最後に、確認されたオブジェクト、事実、及び／または制約がORM概念スキーマ図表上に適当な記述で描写される。この時点で、情報システムの指定が完了したものと見なされる。
情報システムが生成された後、ユーザは以前に入力された情報をチェックし、及び／または編集することができる。これは、事実コンパイラの逆コンパイラ機能を使用して達成される。逆コンパイラは、それがORMの概念スキーマ図表をとり、リポジトリ内に入力されたオブジェクト、事実、及び制約からなるテキストのリストに戻るという点で、基本的に前述のコンパイラ機能の逆である。ユーザは、情報システムの指定を確認するかまたは、システムが存在する場合にシステムを編集するために、このリストを使用することができる。
情報システムの指定が一旦完了すると、情報システムのORM表現で描写された概念スキーマは、RMAPを用いて関係データベースにマッピングされる。RMAP処理は、McCormack他（1993年）に詳細に記述があり、ここで参照することにより、詳細な説明がなされたものとして本明細書に組み込まれる。事実の集合の例を以下に示す。
0003639972.tif 000002
事実ツリーの例に関連する関係データベースが、
0003639972.tif 000003
である場合、関連するRMAPのマッピングは以下のようになる。
0003639972.tif 000004
照会処理の第１ステップは、事実ツリーを指定する。事実ツリーの指定では、ユーザは照会に関連する名詞を選択する。例えば、ユーザがスミス氏の住所、電話番号、勉強科目、及び先生を見つけたい場合、照会が基本的に人に関するものなので、人という名詞から始める。照会文の根として人を選んだ後、その人の住所などを見つけるために、その人に関する他の情報をさらに選択することができる。選択可能な情報は、事実に含まれるその人に関する情報だけである。即ち、次のようなものである。
0003639972.tif 000005
この事実の集合は、特定の人に関する入手可能な情報全てである。この情報は概念的に表示され、ユーザは任意の特定キーワードやフレーズを知る必要がない。この場合、ユーザは以下の事実を選択する。
0003639972.tif 000006
なぜなら、それがスミス氏について彼らが知りたいことであるからである。これにより、以下の事実ツリーが構成される。
0003639972.tif 000007
最後に、ユーザは、スミス氏にしか興味がないので、ツリーの根にある人を、スミス氏であると制限する。
最終的なツリーの意味は、スミス氏という人、彼の住む住所、彼の持っている電話番号、彼が勉強している科目を表示し、彼の勉強している科目に関して、それらの科目を教えている人を表示するものである。
事実ツリーを生成した後、ユーザはその事実ツリーが正しいことを、本発明のツリー・インタプリタを使用して確認する。そうすることによって、生成された照会文が曖昧さを有する可能性を、あらかじめ除外することになる。ツリー・インタプリタの使用中に、ツリー・インタプリタ・アルゴリズムが、事実ツリーの自然言語記述を構成する。このアルゴリズムは、以下の最良の形態のセクションで記述される再帰的depth−first検索関数である。この解釈は、ユーザに、ユーザの質問が所望の情報を得ることを確認できるようにする。
ユーザが事実ツリーを指定し、それをツリー・インタプリタを使ってチェックし終えれば、後は関係照会文自体を生成するだけである。これを行うアルゴリズムは、再帰的depth−first検索関数であり、本発明を実施する最良の形態を詳述する以降のセクションで詳細に説明する。
【図面の簡単な説明】
本発明の様々な特徴と利点が、添付図面に関連して行われる以下の、好適実施例の詳細な説明によって、より容易に理解される。この図面は、同じ参照番号が同じ要素を示している。
図１は、本発明の動作のために構成された、プログラム可能な、デジタル汎用コンピュータの外観を示す図である。
図２は、本発明によって構成された、図１のコンピュータのブロック図である。
図３は、本発明の事実コンパイラを選択した後に、本発明の初期選択メニューを例示するフロー・チャートである。
図４は、３つの主要関数を含んだ、本発明の事実コンパイラを例示するフロー・チャートである。
図５は、本発明の事実コンパイラの「図表上のドラッグ・アンド・ドロップ」関数を例示するフロー・チャートである。
図６は、「図表上のドラッグ・アンド・ドロップ」関数によって実行される、「ドラッグ・アンド・ドロップ解析」関数のフロー・チャートである。
図７は、事実コンパイラによって実行される、「リポジトリのみへのコンパイル」関数のフロー・チャートである。
図８は、「リポジトリのみへのコンパイル」関数によって実行される、解析関数のフロー・チャートである。
図９は、解析関数によって実行される、走査関数のフロー・チャートである。
図10は、本発明に従う、エラー条件を入力する手順を示すテーブルである。
図11は、解析関数によって実行される、「オブジェクト指定検索」関数を例示するフロー・チャートである。
図12は、解析関数によって実行される、「事実指定検索」関数を表すフロー・チャートである。
図13は、解析関数によって実行される、「制約指定検索」関数を表すフロー・チャートである。
図14は、「オブジェクト指定検索」関数によって実行される、「新オブジェクト割り当て」関数を例示するフロー・チャートである。
図15は、「事実指定検索」関数によって実行される、「新事実割り当て」関数を例示するフロー・チャートである。
図16は、「制約指定検索」関数によって実行される、「新制約割り当て」関数を例示するフロー・チャートである。
図17は、「ドラッグ・アンド・ドロップ解析」関数と、「リポジトリのみへのコンパイル」関数の両方によって実行される、「リポジトリ内のレコード更新」関数を表すフロー・チャートである。
図18は、本発明に従う、「事実ツリー指定」関数が選択された後の、本発明の初期選択メニューを例示するフロー・チャートである。
図19は、「事実ツリー形成」関数と本発明の照会文マッパ、または「ツリー・インタプリタ」関数のどちらかの選択を例示するフロー・チャートである。
図20は、ユーザが本発明の照会文マッパを選択した場合に実行される、「事実ツリー＝＞SQL照会文」関数を表すフロー・チャートである。
図21は、「事実ツリー＝＞SQL照会文」関数によって実行される、「ノード＝＞SQL」関数を例示するフロー・チャートである。
図22は、「ノード＝＞SQL」関数によって実行される、「ジョイン生成」関数を表すフロー・チャートである。
図23は、「ノード＝＞SQL」関数によって実行される、「セレクタ１追加」関数を例示するフロー・チャートである。
図24は、「ノード＝＞SQL」関数によって実行される、「セレクタ２追加」関数を例示するフロー・チャートである。
図25は、ユーザが本発明のツリー・インタプリタを選択した場合に実行される、「事実ツリー＝＞記述」関数のフロー・チャートである。
図26は、「事実ツリー＝＞記述」関数によって実行される、「根に関するテキスト作成」関数のフロー・チャートである。
図27は、「事実ツリー＝＞記述」関数によって実行される、「ノードに関するテキスト作成」関数を例示するフロー・チャートである。
本発明を実施する最良の形態
本発明の好適実施例は、図１に示すように構成されたコンピュータ・システム１に組み込まれる。コンピュータ・システム１はプログラム可能なデジタル・コンピュータである。本発明はインテル80386、またはそれ以上のチップセットを有し、MS−DOSオペレーティング・システム、バージョン5.0以上で動作するIBM互換コンピュータで実行可能である。実行には最小で６メガバイトの利用可能なRAMと、最小で６メガバイトのハードディスク記憶域が必要である。これらのコンピュータは通常CPU、主記憶装置、I/O資源、及び手動のキーボードとマウスを含むユーザ・インタフェースを含んでいる。本発明は、グラフィカル・ユーザ・インタフェースも必要であり、マイクロソフト・ウインドウズは周知な例の１つである。
本発明は、インテル80486のチップセットを有し、マイクロソフトのMS−DOSオペレーティング・システム、バージョン5.0で動作するIBM互換コンピュータにおいてプログラムされている。マイクロソフト・ウインドウズ・バージョン3.1がインストールされ、必要なグラフィカル・ユーザ・インタフェースを提供する。最後に、以下に説明するシステムは、ボーランドのＣ言語でプログラムされている。
図２は、図１のプログラム可能汎用コンピュータのバス構成を示しており、本発明は、このコンピュータ上で実施される。
図３を参照すると、ユーザは手動入力50でシステムを初期化し、関数セレクタ51で所望の関数を選択する。
本発明は、ユーザが、
1.自然言語に似たコンピュータ言語（こうした言語の１つはFORMLである）に対するグラフィカル・ユーザ・インタフェースを用いて情報システム記述を開発でき、
2.照会文生成に関する事実ツリーを指定でき、
3.意味が正しいか照会文をチェックでき、
4.データベース・システムに対して照会文を生成できるような方法、及び装置を提供する。
情報システムを生成する必要があるという決定がなされたら、本発明の事実コンパイラが実行される。事実コンパイラのコンパイル機能により、ユーザは自然言語に似たコンピュータ言語を使用してテキストで入力することが可能になる。このような言語の１つはFORMLである。テキストはシステムによって提供されるウインドウ内にタイプされ、オブジェクト、事実、及び／または制約を含む可能性がある。「図表上のドラッグ・アンド・ドロップ」と呼ばれる変換関数とグラフィカル・ユーザ・インタフェースを用いて、ユーザは、テキストを入力ウインドウから事実コンパイラのORM概念スキーマ図表上の適当な場所にドラッグする。次にユーザは、そのテキストを図表上にドロップする。事実コンパイラはその入力されたテキストを確認し、発生したエラーをユーザに知らせる。確認の間、事実コンパイラは最初にテキストを解析し、オブジェクト・リスト、事実リスト、及び制約リストをメモリ内に生成する。次に、事実コンパイラは反復的にテキストをリポジトリにコンパイルする。このリポジトリは、基本的に「データベースのデータベース」である。最後に、確認されたオブジェクト、事実、及び／または制約が、ORM概念スキーマ図表上に適当な記述で描写される。この時点で、情報システムの指定が完了したものと見なされる。
情報システムが生成された後、ユーザは以前に入力された情報をチェックし、及び／または編集することができる。これは、事実コンパイラの逆コンパイラ機能を使用して達成される。逆コンパイラは、それがORMの概念スキーマ図表をとり、リポジトリ内に入力されたオブジェクト、事実、及び制約からなるテキストのリストに戻るという点で、基本的に前述のコンパイラ機能の逆である。ユーザは、情報システムの指定を確認するかまたは、システムが存在する場合にシステムを編集するために、このリストを使用することができる。
情報システムの指定が一旦完了すると、情報システムのORM表現で描写された概念スキーマは、RMAPを用いて関係データベースにマッピングされる。RMAP処理は、McCormack他（1993年）に詳細に記述があり、ここで参照することにより、詳細な説明がなされたものとして本明細書に組み込まれる。事実の集合の例を以下に示す。
0003639972.tif 000008
例の事実ツリーに関する関係データベースが、
0003639972.tif 000009
である場合、関連するRMAPのマッピングは以下のようになる。
0003639972.tif 000010
照会処理の第１ステップは、事実ツリーを指定する。事実ツリーの指定では、ユーザは照会に関連する名詞を選択する。例えば、ユーザがスミス氏の住所、電話番号、勉強科目、及び先生を見つけたい場合、照会が基本的に人に関するものなので、人という名詞から始める。照会文の根として人を選んだ後、その人の住所などを見つけるために、その人に関する他の情報をさらに選択することができる。選択可能な情報は、事実に含まれるその人に関する情報だけである。即ち、次のようなものである。
0003639972.tif 000011
この事実の集合は、特定の人に関する入手可能な情報全てである。この情報は概念的に表示され、ユーザは任意の特定キーワードやフレーズを知る必要がない。この場合、ユーザは以下の事実を選択する。
0003639972.tif 000012
なぜなら、それがスミス氏について彼らが知りたいことであるからである。これにより、以下の事実ツリーが構成される。
0003639972.tif 000013
最後に、ユーザは、スミス氏にしか興味がないので、ツリーの根にある人を、スミス氏であると制限する。
最終的なツリーの意味は、スミス氏という人、彼の住む住所、彼の持っている電話番号、彼が勉強している科目を表示し、彼の勉強している科目に関して、それらの科目を教えている人を表示するものである。
事実ツリーを生成した後、ユーザはその事実ツリーが正しいことを、本発明のツリー・インタプリタを使用して確認する。そうすることによって、生成された照会文が曖昧さを有する可能性を、あらかじめ除外することになる。ツリー・インタプリタを使用すると、ツリー・インタプリタ・アルゴリズムにより、事実ツリーに関する自然言語での説明が構成される。このアルゴリズムは、再帰的depth−first検索関数であり、以下で要約して示す。
0003639972.tif 000014
このInterpret_Treeを先の事実ツリーの例に対して実行すると、次のような結果が得られる。
0003639972.tif 000015
この解釈によって、ユーザがした質問が、所望の情報を得られるか確認できる。
ユーザが事実ツリーを指定し、それをツリー・インタプリタを用いてチェックし終えれば、後は関係照会文を生成するだけである。これを実行するアルゴリズムも、事実ツリーのノードに対して再帰的に実施される。
0003639972.tif 000016
child i（ｉ＝1...n）のどれかが子を持つ場合、Create_Queryを子に適用し、その結果を外部ジョインを用いて既存の照会文の中に含める。その結果、事実ツリーの例の場合、Create_Queryは科目を勉強する人の科目ノードに対して実行され、以下の照会文が得られる。
0003639972.tif 000017
SQLが記述上便利なものとして使用され、かつその使用がアルゴリズムを背景とした論理とは無関係であることに注意すべきである。任意の関係言語が使用可能であることは、本発明の大きな特徴である。本発明の事実コンパイラ、照会文マッパ、及びツリー・インタプリタのアルゴリズムの利点は、それらが実質的に概念の数と、初心者が関係データベースにおいて意味のある照会文を表現できるために必要な訓練の時間を削減したことである。本発明のアルゴリズム・セットによって、ユーザは、キーワードや物理構造を知ることなく、概念的な照会文を形成することができる。また、本発明のアルゴリズムは、照会文が文法的に正しいことを保証するために、照会文の自然言語表現を生成する。これらの利点は、前述した例と、自然言語、及びSQLの実施における現在の技術で表現された同様の例を対比することによって例示される。
照会文を自然言語で表現するためには、ユーザは、次のような文を構成し、照会文としてタイプする必要がある。
0003639972.tif 000018
この照会文を作成するために必要な情報は次のようなものである。
1.この照会文（Personなどのキーワードを含める必要がある）を表現する方法に関する全体的知識。
2.住所、電話番号、科目などを尋ねるときの知識。
事実コンパイラ
本発明の事実コンパイラは100において選択される。本発明の事実ツリーは300で選択される。前述したように、事実コンパイラが本発明によって提供され、以下により詳細な説明がなされる。図４を参照すると、事実コンパイラを選択（100）した後で、ユーザはモデル化される情報システムの１つのレベルを表現する図表を開く。その事実コンパイラの図表を開いた後で、ユーザは、自然言語に似たコンピュータ言語を用いて、実際の文でオブジェクト・タイプ、又は制約をタイプする。こうした言語の１つはFORMLである。そのような入力の例は、‘the INSTRUCTOR with the ID“100"is qualified to teach the SUBJECT with the name“database design"at the SUBJECT LEVEL“300"'である。この時点で、ユーザは３つのオプションのうち、１つを選択できる。３つのオプションは、確認専用の関数105を使用して入力を確認すること、リポジトリのみに情報をコンパイルする（140）こと、および関数120で事実を図表上にドラッグ・アンド・ドロップすることである。
本発明の図４に示された確認専用の関数105を参照すると、全てのテキストが編集ウインドウから組み合わせられた（110）後で、関数111を用いて構成要素のワードに解析される。112のエラー・チェックが、入力されたテキスト内にエラーがあるかどうか判定する。エラーがなければ、システムは113で確認が成功したことを示す。エラー・チェッカー112が、テキスト入力にエラーがあったと判定した場合、エラーがエラー・ウインドウ114に示される。
「図表上のドラッグ・アンド・ドロップ」関数120が、図５に詳細に示されている。ユーザがドラッグ・アンド・ドロップ関数120を選択した後、ユーザはマウスを用いて編集ウインドウ121からアイコン上にポインタを移動させる。ユーザは左のマウス・ボタンを押下し、その状態を保持する（122）。システムは、編集ウインドウ内に入力された項目のタイプに関するテストを行う（123）。項目種類セレクタ124は、編集ウインドウ内に入力された情報のタイプに応じてカーソルの性質を変化させる。入力データが事実なら、カーソルが事実カーソルに変化する（125）。入力データに制約がある場合、カーソルは制約カーソルに変化する（126）。入力データがオブジェクトである場合、カーソルはオブジェクト・カーソルに変化する（127）。ユーザは、変化したカーソルを図表上にドラッグする（128）。カーソルが移動している間、編集ウインドウは消える。カーソルが描画禁止領域の上を移動する場合、カーソルは「描画禁止」カーソルに変化する。ユーザが、入力データの方向を再び回転させる場合、右側のマウス・ボタンが使用される。右側のマウス・ボタンがクリックされる度に、アイコンはその方向を90゜回転させる（130）。ユーザが左のマウスのボタンを放すと（131）、カーソルはデータを図表上にドロップする。カーソル・チェッカー132は、カーソルが実際に図表上にいるかどうかを判定する。図表上にいる場合、「ドラッグ・アンド・ドロップ解析」関数135が実行される。図表上にいない場合は、カーソルが図表上にないことをユーザに知らせる。
「ドラッグ・アンド・ドロップ解析」関数135は、図６に詳細に示されている。現在の編集ウインドウにあるテキストを収集した後、テキストは、解析関数142を用いて解析される。解析の後、エラー・チェッカー161が、入力テキスト内にエラーが生成されたかどうか判定する。エラーが生成されていなかった場合、リポジトリにレコードを更新する関数149を用いて、そのレコードがリポジトリに更新される。レコードがリポジトリに更新された後で、図表上への項目描画関数164を用いて、図表上に項目が描画される。エラー・チェッカー161で、エラーが存在すると判定された場合、エラー条件入力関数162が実行され、関数135が165で終了する。
再び図４に戻ると、関数140によってユーザに、入力をリポジトリのみにコンパイルするオプションが与えられる。関数140が図７に詳細に記されている。関数140、即ち「リポジトリのみへのコンパイル」関数を選択した後、システムは全てのテキストを編集ウインドウから組み合わせ（141）、解析関数142を使用して入力データを解析する。エラー・チェッカー143は入力テキスト内にエラーが生成されたかどうかを判定する。エラーが生成されている場合、そのエラーはエラー・ウインドウに表示される（145）。エラーがなかった場合、状況バーにコンパイルの成功が表示される（144）。反復的な処理が146に示されている。生成されたオブジェクト・リスト、事実リスト、及び制約リストのそれぞれは、レコード毎に検索される。各レコードは、それぞれのリストから検索されて（147）、その状況が148でテストされる。レコードが変更された場合、レコードをリポジトリに更新する関数149が実行される。レコードが変更されなかった場合、リスト・ポインタが150でインクリメントされて、新しいレコードがリストから検索される。レコードが新しいものである場合は、関数149が再び実行され、その後レコード・タイプが152でテストされる。新しいレコードがオブジェクトである場合、新しいオブジェクトを割り当てる関数154が実行される。新しいレコードが事実データある場合、関数154を用いて新しい事実が割り当てられる。新しいレコード・タイプが制約である場合、新しい制約が155で割り当てられる。これらの割り当てのいずれかの後で、リスト・ポインタが再び150でインクリメントされる。
図６及び７の解析関数142の詳細が、図８に示されている。解析関数142が実行された後、走査関数170が実行され、トークンを検索する。トークンが検索された後、それが171でセクションに区分化される。トークンのそれぞれにわたる反復的なループが172で設定される。各トークンは、そのタイプに関するテストを173で受ける。セクションがオブジェクトである場合、オブジェクト指定を検索する関数174が実行される。セクションが事実である場合、事実指定を検索する関数175が実行される。テストされたセクションが制約であった場合、制約指定を検索する関数176が実行される。関数174、175、又は176のいずれかが実行された後、テストされたセクションがターミナル・セクションかどうか判定するテストが行われる。ターミナル・セクションでない場合、次のセクションが、同じテストの対象になる。セクションがターミナル・セクションである場合、解析関数142は179で終了する。
図８の走査関数170は、図９に詳細に示されている。解析関数142の後に、走査関数170を実行する。これは、180で入力ソース・テキストからの文字を読み込む。その関数は、181で辞書アナライザ宣言における通常表現として示されたトークン指定と、それぞれの文字シーケンスをマッチングさせ、その後トークンが182で戻される。
図６で以前に実行されているエラー条件入力関数162は、図10で詳細に示されている。エラーが起こる度毎に、システムはエラーの起こった文字位置と行番号を検索する。この関数は次に、このエラー番号、エラー・テキスト、及びエラー・リスト内のエラー内容情報を記憶する。
再び図８に戻ると、「オブジェクト指定検索」関数174が図11に詳細に示されている。関数174が実行されると、オブジェクトが190で任意の「オブジェクト宣言」によって文法的に指定される。この関数は「解析」と「走査」を継続して行う。オブジェクトが依然としてオブジェクト・セクションであるかどうかに関して、判定が191で行われる。オブジェクト・セクションでない場合、関数は192で終了する。オブジェクトがまだオブジェクト・セクションにある場合、関数はテキストの構成要素をオブジェクト・リスト内に記憶される構造に分割する（193）。194で、オブジェクトの状況がテストされる。新しいオブジェクトである場合、新しいオブジェクトを割り当てる関数220が実行される。オブジェクトが既にオブジェクト・リストに存在する場合は、関数174が198で終了する。オブジェクトがリポジトリ内に存在し、オブジェクト・リスト内にない場合、システムは、196でリポジトリからその構造を読み取り、それをオブジェクト・リスト内に出力する。関数196または220のどちらかが実行された後で、この関数が再び198で終了する。
以前図８で実行された、事実指定を検索する関数175が、図12において詳細に示されている。関数175が実行された後、事実が「事実宣言」によって文法的に指定される。この関数は「解析」と「走査」を継続して行う。事実が依然として事実セクションであるかどうかに関して、判定が201で行われる。事実セクションでない場合、関数175は202で終了する。事実がまだ事実セクションにある場合、システムはテキストの構成要素を事実リスト内に記憶される構造に分割する（203）。その後、事実の状況が204でテストされる。事実が新しい事実である場合、新しい事実を割り当てる関数230が実行され、その後、事実解析は206で終了する。事実が既に事実リストに存在する場合は、関数175がまたも206で終了する。事実がリポジトリ内に存在し、事実リスト内にない場合、システムは、205でリポジトリからその構造を読み取り、それを事実リスト内に出力する。その後関数175がもう一度206で終了する。
同様に以前図８で実行された関数176が、図13に詳細に示されている。制約指定の検索のために関数176が実行された場合、210で制約が「制約宣言」によって文法的に指定される。このシステムは「解析」と「走査」を継続して行う。211で、制約が依然として制約セクションであるかどうかの判定が行われる。制約セクションでない場合、関数176は212で終了する。制約がまだ制約セクションにある場合、システムはテキストの構成要素を制約リスト内に記憶される構造に分割する（213）。その後、事実の状況が214でテストされる。制約が新しいものである場合、新しい制約を割り当てる関数240が実行される。制約が既に制約リストに存在する場合は、関数176が217で終了する。制約がリポジトリ内に存在し、制約リスト内にない場合、この関数は、216でリポジトリからその構造を読み取り、それを制約リスト内に出力する。関数240または処理216のどちらかが達成された後で、関数176が217で終了する。
以前に図11で実行された関数220が、図14に詳細に示されている。関数220は、221で空のオブジェクト構造体を生成し、その構造体に222で名前と全てのオブジェクト属性を入力し、そのオブジェクト構造を223でオブジェクト・リスト内に配置し、224で終了する。
以前に図12で実行された関数230は、図15に詳細に示されている。関数230は、231で空の事実構造体を生成する。232で、この関数は、その構造体に述部テキスト、含まれるオブジェクト、及び内部制約情報を入力する。233で、この関数は、事実構造を事実リストに配置し、234で終了する。
以前に図13で実行された関数240は、図16で詳細に示されている。関数240は以下のように、新しい制約を割り当てる。この関数は241で空の新しい制約構造を生成する。242で、この関数はその構造体に制約情報（役割位置、述部ID）を入力する。243で、この関数は、制約構造を制約リストに配置し、244で終了する。
以前に、図７及び８で実行された関数149は、図17に詳細に示されている。関数149が実行された後で、更新されたレコードは、250に示すように、事実リスト、オブジェクト・リスト、又は制約リスト内に存在する。251で、このレコード・タイプがテストされる。このレコードがオブジェクトであれば、オブジェクト構造が252でオブジェクト更新関数に送られる。レコードが事実であれば、事実構造が254で事実更新関数に送られ、制約であれば、制約構造が253で制約更新関数に送られる。前述の更新関数のいずれかが実行された後に、関数149が256で終了する。
事実ツリー形成
図18を参照すると、関数選択51で可能な第２のオプションは、「事実ツリー指定」300の起動であり、図19に詳細に示されている。
図19を参照すると、事実ツリーが300で形成される。事実ツリーの例は以下のようなものである。
0003639972.tif 000019
事実ツリーの各ノードは名詞（例えば、Person）を持つ。
事実ツリーの各ノードは制限（例えば、“＝Mr.Smith"）を有する場合がある。
事実ツリーの根でない各ノード（最上位のノード以外全て）はフレーズ（例えば、“is taught by"）を持つ。
次に301でツリーの根が変数Rootに割り当てられる。この場合、影付きのノード（Person）がRootに割り当てられる。
事実ツリーをSQL照会文にマッピングする場合、Rootは、関数Fact_Tree_To_SQL400にパラメータとして渡される。この関数の戻り値はSQL照会文となる。関数Fact_Tree_To_SQLは、関数400ないし465を用いて記述される。
事実ツリーを英語の説明にマッピングする場合、Rootは、関数Fact_Tree_To_SQL500にパラメータとして渡される。この関数の戻り値はない。関数Fact_Tree_To_Descriptionにより、ツリーの説明がプリントアウトされる。関数Fact_Tree_To_Descriptionは、関数500ないし535を用いて記述される。
ツリー・インタプリタ
本発明は、以下で説明するように、関数Fact_Tree_To_Descriptionとして呼び出されるツリー・インタプリタも提供する。図25を参照すると、関数Fact_Tree_To_Description（500）は、事実ツリーのノードを入力とし、そのツリー又はサブ・ツリーによって表現される照会文の説明を返す、再帰的な関数である。パラメータRootは、関数が動作するノードである。
関数501は、いくつかの作業変数を割り当てる。Rootはサブツリーのツリーの根であって、親を有する場合も有しない場合もあり、子を有する場合も有しない場合もある。例えば、先のツリーの例において関数Fact_Tree_To_Descriptionに渡された影付きのノード（Person）には親がなく、子が３つある。Parent（この場合はヌル）をRootの親に割り当てる。NodesをRootの子（３つ）に割り当てる。Child（i...Nodes）は、Rootの子に割り当てられた配列である。Personは、“that lives at Address",“that has a phone number",および“that studies a subject"の３つの子をもつ。
次に、一時変数TextをRootの「説明」に割り当てる（502ないし504）。Rootが親を持たない場合（それは事実ツリーの根である）、Rootは関数Create_Text_For_Root（503）に渡される。Rootが親を持つ場合、Rootは関数Create_Text_For_Node（507）に渡される。それらの関数の戻り値は、いずれもRootに関する説明である。
505で、Textをプリントアウトし、改行復帰する。RootがノードPersonを指している場合、関数Create_Text_For_Root（503）が使用され、Textは“For all Person（ｓ）（where Person＝Mr.Smith）show:"になる。Rootが“that studies subject"というノードを指している場合、関数Create_Text_For_Node（504）が使用され、Textは“the Subject（ｓ）that the Person studies,and for those Subject（ｓ）show:"になる。
次のステップは、505ないし510の関数に示すdepth−first検索アルゴリズムを用いてRootの子を再帰的に処理することである。NodesはRootが有する子の数であり、Child［i...Nodes］はRootが有する実際の子である。
変数Ｉは、カウンタ変数として使用される。506で変数Ｉは最初に１に割り当てられる。Ｉが「ノード」より大きい場合（処理すべき子が、もうない場合）、関数Fact_Tree_To_Descriptionの具体化が完了し（507−508）、それ以外の場合、509で関数Fact_Tree_To_DescriptionがChild［１］に対して実行され、501でＩをインクリメントし、処理すべき子がなくなるまで、このループを継続する（507）。
関数Fact_Tree_To_Descriptionを先のツリーの例におけるノードPersonに適用した場合、その結果は次のようなものになる。
0003639972.tif 000020
図25の503で、事実ツリーの根ノードを引数（Root）として関数Create_Text_For_Rootを実行し、そのノードの説明を返す。
520で、根は名詞（例えば、Person）を有し、これがnounに割り当てられる。「根」は制限（例えば、“＝Mr.Smith"）をさらに有することがあり、これがRestrictionに割り当てられる。変数Textに、‘For all'＋noun＋‘s'（例えば、‘For all Person（ｓ）が割り当てられる。
根が「制限」を有する場合、521および522で、その制限をTextに追加する（例えば、Text＝“For all Person（ｓ）（where Person＝Mr.Smith）”のように）。
523で“show:"をTextに追加し、524でそのText（例えば、Text＝“For all Person（ｓ）（where Person＝Mr.Smith）”）を返す。
図25に戻り、事実ツリーの根でないノードを引数（Root）としてとり、そのノードの説明を返す関数Create_Text_For_node504の詳細は、図27に記されている。例えば、“that studies a Subject"というノードが引数として渡される。
530で、「根」は名詞（例えば、Subject）を有し、それがNounに割り当てられる。Rootはフレーズ（例えば、“studies"）を含み、それがPhraseに割り当てられる。Rootの親は名詞（例えば、Person）を有し、これがParent−Nounに割り当てられる。根は制限（例えば、＝スミス氏）をさらに有することがあり、これがRestrictionに割り当てられる。変数Textには、‘the'＋noun＋‘（ｓ）that the'＋Parent−Noun＋‘’＋Phrase（例えば、‘Subject（ｓ）that the Person studies'）が割り当てられる。
「根」が制限を有する場合、531および532で、その制限がTextに追加される。
「根」が子を有する場合、533および534で、‘,and for those'＋Noun＋‘：（ｓ）show:'がTextに追加される。
535で、Textを返す（例えば、Text＝‘the Subject（ｓ）that Person studies,and for those Subject（ｓ）show:'）。
照会文マッパ
本発明はさらに、Fact_Tree_to_SQL_Queryとして実行される照会文マッパも提供する。以下では、これについて詳細に説明する。図19に戻り、関数400の詳細は、図20に記されている。この関数は事実ツリーの根ノードを入力としてとり、それに対応するSQL照会文を返す。パラメータRootは、この関数の実行対象となるツリーの根である。
事実ツリーの根以外のノード（最上位のノード以外）はそれぞれ、そのノードに関する関係マッピングを有する。この関係マッピングは、関係データベースにおけるノードの表現を指定する。例として、以下に事実の集合の例を示す。
0003639972.tif 000021
事実ツリーの例に関する関係データベースが、
0003639972.tif 000022
である場合、関連するRMAPのマッピングは以下のようになる。
0003639972.tif 000023
テーブルは、事実の記憶されたテーブルを示す。第１の名詞カラムはノードの親に関するカラムを表す。第２の名詞カラムは、ノードの名詞に関するカラムを表す。
例えば、“（Person）lives at Address"に関連するマッピングは、全住所がPerson_Tableに記憶され、その住所に住んでいる人がPersonカラムに、そして実際の住所が住所カラムに記憶されることを意味している。
述部のマッピングは、McCormackとHalpinの、Automated Mapping of Conceptual Schemas to Relational Schemas、Proc CAiSE 93、Sorbonne大学，パリ、1993年、に記載されるものと同様のアルゴリズムによって導出される。
SQL照会文は、SelectList、FromList、及びWhereClauseの３つの部分を含む。これらは、関数Node_To_SQLを再帰的に呼び出すことによって徐々に構築される。
最初に、SelectList、FromList、及びWhereClauseを空の文字列（“”）にセットする（401）。
402で、Rootをパラメータとして関数Node_To_SQLを呼び出し、照会文を構築する。
403、404、及び405で、SelectList、FromList、及びWhereClauseをそれぞれフォーマットする。406で関数により照会文を組み立て、407でそれを返す。
402で、関数Node_To_SQLを実行する。これは、事実ツリーのノードをSQL照会文にマッピングする再帰関数である。この関数を連続して呼び出すことによって、SelectList、FromList、及びWhereClauseの変数が構築される。
関数Node_To_SQLは３つのパラメータを持っている。第１のパラメータRootは、マッピングされるツリーまたはサブ・ツリーの根である。第２、及び第３のパラメータは、根のサブ・ツリーに関する照会文を残りの照会文に結合するのに使用される、テーブルおよびカラムである。
410で、ParentはRootの親であり、NodesはRootの子の数であり、Child［i...Nodes］はRootの子である。
Rootが子を持たない場合、処理の必要はなく、この関数は単純にリターンする（411、412）。
それ以外の場合、Rootの子が以下のようにして照会文に追加される。
Rootが親を有している場合、関数JoinTalbe413および関数JoinColumn414を用いてその親を照会文に結合し、415でRootを照会文のselectlistに追加しなければならない。
Rootの子を全て照会文に結合するためには、それらの子を以下のように順番に処理する。416で、カウンタ変数ｉを１に初期化する。417で、ノードの値をチェックし、ｉがノードよりも小さければ、419でAdd_Selector_2（node）を実行する。419でAdd_Selector_2を用いて子のそれぞれをselectlistに追加し、421で関数Node_To_SQLを再帰的に呼び出すことにより、その子の子を照会文に追加する。420で、各ノードについてセレクタを使用し、サブ・ツリーの照会文をまとめて結合する。414で実行される関数Create_Joinの詳細を図22に示す。この関数は、内部ジョインをwhere節に追加することによって、副照会文を主照会文に結合する。この結合は、通過ノード（Node）内の第１の名詞と送られたパラメータに基づいて行なわれる。
再び図21に戻ると、関数Add_Selector_1（415）の詳細が図23に示されている。この関数は、NodeのテーブルをFromListに追加し、Nodeの第１の名詞に関するカラムをSelectListに追加する。
もう一度図21に戻ると、関数Add_Selector_2（419）の詳細が図24に示されている。この関数は、NodeのテーブルをFromListに追加し、Nodeの第２の名詞に関するカラムをSelectListに追加する。
前述の実施例は、本発明の原理に基づくアプリケーションを表す多くの特定の実施例のうちのいくつかを例示しているに過ぎないことが理解される。当業者には、本発明の範囲から逸脱することなく、数多くの変更を容易に実施できることは明らかである。
【図１】
0003639972.tif 000024
【図２】
0003639972.tif 000025
【図３】
0003639972.tif 000026
【図９】
0003639972.tif 000027
【図４】
0003639972.tif 000028
【図５】
0003639972.tif 000029
【図６】
0003639972.tif 000030
【図７】
0003639972.tif 000031
【図８】
0003639972.tif 000032
【図１０】
0003639972.tif 000033
【図１４】
0003639972.tif 000034
【図１１】
0003639972.tif 000035
【図１２】
0003639972.tif 000036
【図１３】
0003639972.tif 000037
【図１５】
0003639972.tif 000038
【図１６】
0003639972.tif 000039
【図１７】
0003639972.tif 000040
【図１８】
0003639972.tif 000041
【図１９】
0003639972.tif 000042
【図２０】
0003639972.tif 000043
【図２１】
0003639972.tif 000044
【図２２】
0003639972.tif 000045
【図２３】
0003639972.tif 000046
【図２４】
0003639972.tif 000047
【図２５】
0003639972.tif 000048
【図２６】
0003639972.tif 000049
【図２７】
0003639972.tif 000050