文書ベースシステムおよびその実現方法
本発明は、解析器と、計画器と、最適化器と、実行器と、記憶操作モジュールとを含む文書ベースシステムを開示している。ここで、解析器はアプリケーションからの呼び出しを中間形式に変換し、計画器は中間形式を実行計画に変換し、最適化器は、計画器で生成された実行計画集合から１つの最適な実行計画を選択し、実行器は、選定された実行計画をスケジューリングして実行し、記憶操作モジュールは、物理記憶に対する操作を実行する。本発明に係る文書ベースシステムは、異なる層の実現が相対的に独立することができるため、拡張性、柔軟性および保守性を持つ。最適化器が複数の実行計画から１つの最適な実行計画を選択することができるため、文書ベースシステム全体は高い性能を持つ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電子文書処理技術に関し、特に、文書ベースシステムおよびその実現方法に関する。
【背景技術】
【０００２】
文書ベースシステムは大量の文書に対する組織、管理、セキュリティ、表示、記憶などの諸機能を提供している。本出願人が先に提出した基礎出願である出願番号ＣＮ２００５１０１３１０７２．０の明細書には、文書ベースシステム、記憶装置、アプリケーションを含む文書処理システムが提供されている。ここで、文書ベースデータが記憶装置に記憶され、文書ベースシステムとアプリケーションとが標準呼び出しインターフェースを介して接続される。アプリケーションによる文書の操作は事前定義の汎用文書モデルに対する統一の操作を含む。アプリケーションは標準呼び出しインターフェースを介して文書ベースシステムへ指令を送信し、この過程が即ちアプリケーションからの呼び出しである。文書ベースシステムは受信された指令に従って、記憶装置に記憶されている文書ベースデータに対して相応の操作を実行する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ここで、文書ベースシステムは大量の論理概念および操作にかかわり、多くの機能をサポートする必要があるため、一般的に、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることは極めて困難である。この課題をアーキテクチャーから解決しないと、最終的に実現される文書ベースシステムは、優れた拡張性、柔軟性、および保守性を持つことができない。
【０００４】
本発明は、文書ベースシステムおよびその実現方法を提供することを主な目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る文書ベースシステムは、
アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析する解析器と、
前記中間形式を、物理記憶に対する操作を含む実行計画に変換する計画器と、
前記実行計画を実行することにより、記憶操作モジュールをスケジューリングして、前記実行計画内の物理記憶に対する操作を実行する実行器と、
前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する記憶操作モジュールと、を含む。
【０００６】
本発明に係る文書ベースシステムは、判断条件に従って、計画器で生成された複数の実行計画から１つの最適な実行計画を選択する最適化器をさらに含む。
【０００７】
さらに、本発明に係る文書ベースシステムにおける最適化器は、計画器で生成された実行計画を最適化する。
【０００８】
前記実行計画を最適化するためのアルゴリズムは、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せを含む。
【０００９】
上記の判断条件は、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含む。
【００１０】
また、上記のアプリケーションからの呼び出しは、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式である。
【００１１】
上記の中間形式は、構文ツリーまたは文書オブジェクトモデルツリーを含む。
【００１２】
上記の記憶操作モジュールは、論理パーティション、物理ディスク、仮想記憶、またはメモリを含む物理記憶に対する操作をサポートする。仮想記憶はリモート記憶またはネットワーク記憶を含む。リモート記憶はネットワークファイルシステムまたは分散ファイルシステムを含み、ネットワーク記憶はストレージエリアネットワーク、グリッド、またはピアツーピア方式の記憶を含む。
【００１３】
ここからわかるように、上記解決手段は具体的な文書ベースシステム構成を提供している。そして、上記解決手段からわかるように、本発明では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、本発明に係る文書ベースシステムは、拡張性、柔軟性および保守性を持つ。本発明に係るによれば、複数の実行計画から１つの最適な実行計画を選出することができ、実行の性能を向上させるため、文書ベースシステム全体の性能を向上させる。初期実行計画に対する局所最適化によれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させる。
【００１４】
本発明に係る文書ベースシステムの実現方法は、
アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析するステップと、
中間形式を、物理記憶に対する操作を含む実行計画に変換するステップと、
前記実行計画内の物理記憶に対する操作をスケジューリングして実行するステップと、を含む。
【００１５】
ここで、前記中間形式を物理記憶に対する操作を含む実行計画に変換するステップは、
汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に変換するステップと、
判断条件に従って複数の実行計画から１つの最適な実行計画を選択するステップと、を含む。
【００１６】
また、前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択する前に、生成された実行計画を最適化することをさらに含む。ここで、前記生成された実行計画を最適化することは、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せに基づいて最適化することを含む。
【００１７】
ここで、上記のアプリケーションからの呼び出しは、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式である。中間形式は、構文ツリーまたは文書オブジェクトモデルツリーを含む。判断条件は、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含む。
【００１８】
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択することは、経験ルール優先度アルゴリズムまたは経験ルール重みアルゴリズムに基づいて、複数の実行計画から１つの最適な実行計画を選択することを含む。
【発明の効果】
【００１９】
ここからわかるように、上記解決手段は具体的な文書ベースシステムの実現方法を提供している。そして、上記解決手段からわかるように、本発明では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、文書ベースシステム全体の実現は、高い拡張性、柔軟性および保守性を持つ。本発明によれば、複数の実行計画から最適な実行計画を選択することができるため、選出された最適な実行計画のコストが比較的低くなり、実行の性能を向上させ、文書ベースシステムに比較的高い性能を持たせる。計画器で生成された複数の実行計画に対して局所最適化を行うことによって、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係る文書ベースシステムの階層を示す図である。
【図２】本発明に係る文書ベースシステムの構成を示す図である。
【図３】本発明に係る文書ベースシステムの実現方法のフローチャートである。
【発明を実施するための形態】
【００２１】
本発明の目的、解決手段およびメリットをさらに明確にするために、以下、図面を参照して実施形態をあげながら、本発明をさらに詳しく説明する。
【００２２】
本発明の実施形態では、文書ベースシステムの実現が複数の層に分けられ、隣接層の間のインターフェースについて標準規範が定義されている。
【００２３】
図１は本発明に係る文書ベースシステムの階層を示す図である。図１に示すように、本発明の実施形態において、文書ベースシステムの実現が図示の幾つかの層に分けられ、各層はそれぞれ、アプリケーションからの呼び出しを、論理操作を含む中間形式に変換し、論理操作を含む中間形式を、物理記憶に対する操作を含む実行計画に変換し、変換によって得られた実行計画を実行する。
【００２４】
このように、各層の出力結果が標準インターフェース規範に適合する条件で、各層の具体的な実現はそれぞれ複数の方式であってもよい。これにより、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることができる。
【００２５】
図２は本発明に係る文書ベースシステムの構成を示す図である。図２に示すように、本発明の実施形態に係る文書ベースシステムは、解析器と、計画器と、実行器と、記憶操作モジュールと、を含む。
【００２６】
解析器は、アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作からなる中間形式に解析する。
【００２７】
計画器は、解析器で解析して得られた中間形式を、物理記憶に対する操作からなる実行計画に変換する。
【００２８】
ここで、中間形式を構成する論理操作は比較的高い階層の概念である。１つの論理操作は、単一の物理操作にマッピングされることも、複数の物理操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。同一の中間形式について、毎回、計画器で変換して得られた実行計画が異なることは可能であるが、これらの実行計画は等価である。
【００２９】
実行器は、計画器で変換して得られた実行計画を実行することによって、記憶操作モジュールをスケジューリングして、該実行計画内の物理記憶に対する操作を実行する。
【００３０】
記憶操作モジュールは、前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する。
【００３１】
上記はある文書ベースシステムの具体的な構成である。そして、各層の出力結果が標準インターフェース規範に適合する条件で、各層の具体的な実現はそれぞれ複数の方式であってもよい。これにより、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることができる。
【００３２】
以下、上記文書ベースシステムにおける各モジュールをそれぞれ詳しく説明する。
【００３３】
具体的に、解析器から出力された中間形式は標準インターフェース規範に適合する。中間形式は具体的に構文ツリーまたは文書オブジェクトモデル（ＤＯＭ：Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）ツリーを含むようにしてもよい。アプリケーションによる文書ベースシステムの標準インターフェースに対する呼び出しは、まず解析器で処理される。標準インターフェースは、文書ベースシステムに関する基礎出願書類に説明された拡張可能なマークアップ言語（ＸＭＬ：ＥＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）形式のＵＯＭＬインターフェースであってもよく、命令列の形式、または他の形式であってもよいが、いずれも基礎出願に説明された文書処理システムにおける汎用文書モデルに適合する必要がある。
【００３４】
このように、アプリケーションからの呼び出しが解析器によって字句・構文解析された後、標準インターフェース規範に適合する、汎用文書モデルのオブジェクトまたは操作からなる中間形式が生成される。
【００３５】
実際の応用では、ＸＭＬ形式の標準インターフェースの場合、上記文書ベースシステムにおける解析器がＸＭＬ解析器であり、アプリケーションを解析してＤＯＭツリーを生成するようにしてもよい。命令列形式の標準インターフェースの場合、用いられる命令列は一般的にＬＡＬＲ（１）（Ｌｏｏｋａｈｅａｄ Ｌｅｆｔ ｔｏ Ｒｉｇｈｔ Ｐａｒｓｉｎｇ）文法に適合する。文法定義が与えられる場合、上記文書ベースシステムにおける解析器は、ｌｅｘ（Ｌｅｘｉｃａｌ ｃｏｍｐｉｌｅｒ）およびｙａｃｃ（Ｙｅｔ ａｎｏｔｈｅｒ ｃｏｍｐｉｌｅｒ ｃｏｍｐｉｌｅｒ）で生成された字句および構文解析器であってよい。ここで、ｌｅｘはスキャナを生成するツールであり、即ち字句解析器を生成するツールである。ｙａｃｃはＬＡＬＲ（１）解析器の自動生成ツールであり、そのバージョン１が１９７０年代初期に発表され、アメリカのベル研究所のソフトウェア製品である（作者はＳ．Ｃ．Ｊｏｈｎｓｏｎ）。現在、この２つのツールはＵＮＩＸ（登録商標）、ＤＯＳ（登録商標）などのシステムプラットフォームで広く流行している。具体的なＸＭＬ解析およびｌｅｘ、ｙａｃｃ解析は従来技術である。
【００３６】
以下、例をあげて、ＸＭＬ形式に基づく標準インターフェース呼び出しの解析を具体的に説明する。
<call>
<stringValval=″AppendLine″ name=″MethodName″/>
<stringValval=″0xabcd1234″ name=″PathObj″/>
<compoundValname=″LineObj″>
<line>
<startxCod=″1000.23″ yCod=″2193.324″/>
<endxCod=″3233.234″ yCod=″2342.234″/>
</line>
</compoundVal>
</call>
【００３７】
上記コードはＸＭＬ形式の標準インターフェース呼び出しを表し、インターフェースメソッドの名称はＡｐｐｅｎｄＬｉｎｅであり、該メソッドのタスクはハンドルが０ｘａｂｃｄ１２３４であるパスオブジェクトへの線分追加であり、該線分の両端点の位置はそれぞれ（１０００．２３，２１９３．３２４）および（３２３３．２３４，２３４２．２３４）である。
【００３８】
解析器は上記のＸＭＬ形式の標準インターフェース呼び出しを解析し、解析結果がＤＯＭツリーであり、該ＤＯＭツリーの構造は、ルート要素ｃａｌｌと、ｃａｌｌに含まれた３つのサブ要素（２つのｓｔｒｉｎｇＶａｌおよび１つのｃｏｍｐｏｕｎｄＶａｌ）とを含む。
【００３９】
即ち、以下のような形式である。
call
stringVal
stringVal
compoundVal
【００４０】
以下はＬＡＬＲ（１）文法に適合するカスタマイズ言語による文書ベースシステムに対する標準インターフェース呼び出しである。
call withname=AppendLine, params=(PathObj=″0xabcd1234″, LineObj=(StartPt=(1000.23,2193.324), EndPt=(3233.234, 2342.234)));
【００４１】
解析器は、対応の字句および構文解析器によって、上記のカスタマイズ形式のアプリケーションからの呼び出しを解析して、構文ツリーを生成する。上記字句および構文解析器は、ｌｅｘまたはｙａｃｃを予め呼び出してカスタマイズ言語の字句および構文を定義することによって、生成されるようにしてもよい。構文ツリーは下記のＣ構造で表されるようにしてもよい。
struct SyntaxTree
{
structNode *pRoot;
};
struct Node
{
struct Node *pLeft;
struct Node *pRight;
......
}
【００４２】
具体的なツリー構造は上記例示のＤＯＭツリーに類似している。
【００４３】
以下、中間形式が構文ツリーである場合を例として、計画器が論理操作を物理操作に変換するプロセスを詳しく説明する。
【００４４】
構文ツリー内の各論理操作Ｌ＿ＯＰを列挙する。ここでの論理操作は一組の論理操作のシーケンスであってもよい。まず、Ｌ＿ＯＰに対応する物理操作集合（Ｐ＿ＯＰ１、Ｐ＿ＯＰ２、…、Ｐ＿ＯＰｍ）を取得する。ここでの各物理操作Ｐ＿ＯＰｊは一組の物理操作のシーケンスであってもよい。次いで、Ｌ＿ＯＰに対してＰ＿ＯＰｉのような物理操作を選択する。そして、構文ツリー内の全ての論理操作に対して、上記プロセスに従って対応の物理操作を選択する。構文ツリー内の全ての論理操作が対応の物理操作に替えられると、実行計画が生成される。
【００４５】
ＤＯＭツリーおよび他の中間形式に対する変換は上記実現に類似している。
【００４６】
上記のＤＯＭツリーとなる中間形式を計画器で変換して生成された実行計画は以下の通りである。
AppendLine
PathObj
CreateLine
StartPt
EndPt
【００４７】
ここで、実行計画のルートノードＡｐｐｅｎｄＬｉｎｅは操作であり、その１番目のサブノードＰａｔｈＯｂｊはＰａｔｈオブジェクトのハンドルであるが、２番目のサブノードは線分オブジェクトを作成するためのＣｒｅａｔｅＬｉｎｅ操作であり、ＣｒｅａｔｅＬｉｎｅの２つのサブノードはそれぞれ作成しようとする線分の始点および終点である。
【００４８】
ＣｒｅａｔｅＬｉｎｅの実行結果、対応の線分オブジェクトが生成されるが、ＡｐｐｅｎｄＬｉｎｅ操作により、該線分オブジェクトはＰａｔｈオブジェクトに追加される。
【００４９】
図２に示すような文書ベースシステムにおける実行器について、普通、実行計画が物理記憶に対する操作を含むツリーであるため、実行器は実行計画に対応するツリーのルートノードから、トップダウンで再帰し、ツリーの最下位ノードから、ボトムアップで記憶操作モジュールをスケジューリングして実際の操作を実行し、実行計画全体を次第に完成する。
【００５０】
例えば、実行器は下記の実行計画を実行する。
OP1
Para1
Para2
OP2
Para3
Para4
OP3
Para5
Para6
【００５１】
ここで、ＯＰ１、ＯＰ２およびＯＰ３は３つの操作であり、Ｐａｒａ１〜Ｐａｒａ６は操作に対応する６つのパラメータである。実行器が上記実行計画を実行する手順は以下の通りである。
ＯＰ３（Ｐａｒａ５，Ｐａｒａ６）を実行し、結果はｒｅｓ３となり、
ＯＰ２（Ｐａｒａ３，Ｐａｒａ４，ｒｅｓ３）を実行し、結果はｒｅｓ２となり、
ＯＰ１（Ｐａｒａ１，Ｐａｒａ２，ｒｅｓ２）を実行し、結果はｒｅｓ１となる。
【００５２】
図２に示すような文書ベースシステムにおける記憶操作モジュールは、各種の物理記憶層、例えば物理エンティティに基づく物理記憶層または仮想の物理記憶層において構築されるようにしてもよく、性能や規模に異なる制限がある。
【００５３】
実際の応用では、物理記憶層により提供されたインターフェース類型、即ち記憶操作モジュールと物理記憶層との間のインターフェース類型が、実行計画を構成する物理操作の構成に影響を与えるため、計画器で生成された実行計画も所定のインターフェース類型に応じる必要がある。例えば、物理記憶層がバイナリストリームのリード／ライトのみを提供する場合、実行計画を構成する物理操作はおそらくリード／ライトの２種類の物理操作のみを含み、物理記憶層が文書ベースの作成、文書集合の作成などのようなより多くの操作を提供する場合、実行計画を構成する物理操作は多くなる。物理記憶層の提供必要な基本オブジェクトは文書ベース、文書集合、文書などを含み、物理記憶の割当、回収、リードライトの機能を提供することも必要である。
【００５４】
論理パーティション、物理ディスク、仮想記憶、メモリなどの媒体を使用するとき、記憶操作モジュールの実現は類似している。オペレーションシステムで提供されるファイルシステム、オペレーションシステムで提供される論理パーティション、オペレーションシステムで提供される、物理ディスクにアクセスするためのインターフェース、オペレーションシステムを経由せず物理ディスクにアクセスするためのインターフェース、オペレーションシステムで提供される、仮想メモリもしくは物理メモリにアクセスするためのインターフェース、オペレーションシステムを経由ぜず物理メモリに直接にアクセスするためのインターフェース、または仮想記憶装置を基に、記憶操作モジュールを構築するようにしてもよい。この上で、文書ベース、文書集合、文書などの物理記憶層のオブジェクトを実現する。
【００５５】
ここで、仮想記憶はリモート記憶を使用するようにしてもよい。即ち、実際の物理記憶は別のコンピューティングデバイスにある。例えば、ネットワークファイルシステム（ＮＦＳ）、分散ファイルシステム（ＤＦＳ）である。仮想記憶はネットワーク記憶を使用するようにしてもよい。即ち、実際の物理記憶はネットワークにより提供される。例えば、ストレージエリアネットワーク（ＳＡＮ：Ｓｔｏｒａｇｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、グリッド（ＧＲＩＤ）、ピアツーピア（Ｐ２Ｐ：ＰＥＥＲ−ｔｏ−ＰＥＥＲ）方式の記憶などである。
【００５６】
ファイルシステムを例として、記憶操作モジュールは以下のような操作を実行する。
【００５７】
あるディレクトリを文書ベースとして設定し、
文書ベースディレクトリの下に、１つまたは複数の文書集合ディレクトリを作成し、
文書集合ディレクトリの下に、文書として１つまたは複数のファイルを作成し、
文書に、ページ、層、ページストリームなどを作成するようにしてもよい。
【００５８】
最終的なディレクトリ構成は例えば以下のようになり、ここで、文書はファイルの形式で示され、ｄｏｃｌｉｓｔディレクトリの下に置かれる。
/……
docbase/
doclist/
doclist/
……
【００５９】
上記は本発明に係る文書ベースシステムの各モジュールの具体的な実現である。上記のように、異なるモジュールの間に標準のインターフェース規範がある。入出力が標準インターフェース規範に適合する条件で、各モジュールの具体的な実現は異なる方法を採用してもよい。これにより、文書ベースシステム全体の実現に拡張性、柔軟性および保守性を持たせることができる。
【００６０】
上記文書ベースシステムの計画器によって同一の中間形式を変換して得られた実行計画が異なることは可能である。これらの実行計画が等価であるが、異なる実行計画によって、実行にかかる時間や空間は常に大きな違いがある。そのため、対応の実行計画集合から決定された実行計画が最適であるかどうかは、文書ベースシステムの性能に大きな影響を与える。
【００６１】
従って、本発明の実施形態において、図２に示すような文書ベースシステムは、中間形式に対応する実行計画集合から、所定の判断条件に従って最適な実行計画を選出する最適化器をさらに含むようにしてもよい。
【００６２】
最適化器の実現の１つとして、計画器で所定数の実行計画を生成し、例えば、計画器は所定数の実行計画をランダムに生成してもよく、次いで、最適化器は判断条件に従って、生成された実行計画集合から最適な実行計画を選出する。説明すべきものとして、いわゆる「最適」とは、判断条件または実際のニーズという意味から言われたものである。例えば、実行時間が最少となることを図るという判断条件で選出された最適な実行計画は、実行に必要な最大空間が大きい可能性があるため、実行に必要な最大空間が最小となることを図るという判断条件で、最適な実行計画と言えない。上記の判断条件は経験ルールであってもよく、或いは、実行計画のコストに基づく比較、即ち、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せに基づく比較であってもよい。
【００６３】
実際の応用では、最適化器が様々な方式で実現できる。以下、例を挙げてそれぞれ説明する。
【００６４】
図２に示すような文書ベースシステムにおける最適化器は、経験ルールの優先度に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、最適化器の判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールの優先度がＲ１＞Ｒ２＞…＞ＲＬであるとすると、該最適化器は以下のような操作を実行する。
ａ１、実行計画集合を生成された全ての実行計画に設定し、現在の判断用経験ルールをＲｉ（初期化状態でｉ＝１）に設定する。
ａ２、実行計画集合内の全ての実行計画に対して、ルールＲｉに適合するかどうかを順次に判断し、ある実行計画がルールＲｉに適合しない場合、該実行計画を標記して、該実行計画を実行計画集合から除去する。
ａ３、実行計画集合が空になる場合、ａ２で標記された実行計画を実行計画集合に入れる。ｉがＬに等しいかどうかを判断し、ｉがＬに等しい場合、経験ルールの優先度に基づいて選択される最適な実行計画として、実行計画集合から１つの実行計画を任意に選出し、ｉがＬに等しくない場合、ｉに１を加えて、ａ２の操作を繰り返して実行する。
【００６５】
図２に示すような文書ベースシステムにおける最適化器は、経験ルールの重みに基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、最適化器の判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールＲｉの重みがＰＲｉであるとするとともに、各実行計画ごとに対応の重みを設けると、該最適化器は以下のような操作を実行する。
ｂ１、全ての実行計画に対して、その重みを０に初期化する。
ｂ２、各実行計画に対して、ルールＲｉ（ｉ＝１，…，Ｌ）に適合するかどうかを判断し、適合する場合、該実行計画の重みにＰＲｉを加える。
ｂ３、各実行計画の重みに基づいて、経験ルールの重みに基づいて選択される最適な実行計画として、重みが最大となる実行計画を選出する。条件に適合する最適な実行計画が複数ある場合、１つを任意に選出するようにしてもよい。
【００６６】
上記２種類の最適化器はいずれも経験ルールに基づいて最適な実行計画を選択するものであるが、本発明の実施形態に係る最適化器は実行計画のコストに基づいて最適な実行計画を選択するようにしてもよい。
【００６７】
ここで、実行計画のコストは時間コストと空間コストとを含む。時間コストは、実行計画全体の実行にかかる時間を指し、主にディスクＩ／Ｏ時間を含む。空間コストは、実行計画全体の実行過程中で最終結果および中間結果が占用可能な最大空間を指し、メモリとディスクとの両方の占用量にかかわる。
【００６８】
実行計画の時間コストに基づいて最適な実行計画を選択すると、最適化器は実行計画を若干の基本操作に分解し、各基本操作にかかる時間を基準にして、各基本操作の実際の実行回数によって累加し、最後に実行計画にかかる合計時間を見積る。通常の方法として、最適化器は再帰の実行順序に従って実行計画全体を走査して、各基本操作の実行回数を取得してから、実行計画全体にかかる時間を算出する。
【００６９】
実行計画の時間コストとの相違として、通常、実行計画の空間コストは実行過程中の空間の最大値を指す。算出の方法として、最適化器は再帰的順序に従って、ボトムアップで算出して、現在の実行に必要な空間を現在の最大空間値と比較し、現在の最大空間値より大きい場合、現在の最大空間を現在の実行空間で取り替え、実行計画の算出が終了した後、実行計画の最大空間、即ち、該実行計画の空間コストを得ることができる。
【００７０】
具体的に、最適化器は実行計画の時間コストの算出に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、実行計画がツリー構造であり、基本操作が（ＯＰ１、ＯＰ２、…ＯＰｎ）を含み、最適化器の実行計画の時間コストの算出関数がＴＩＭＥ＿ＣＡＬＣ（ＮＯＤＥ ｎｏｄｅ）であるとすると、以下はＴＩＭＥ＿ＣＡＬＣの算出過程の実現である。
ｃ１、実行時間変数Ｔを０に初期化する。
ｃ２、ｎｏｄｅのサブノード（ＳＵＢ１、ＳＵＢ２…ＳＵＢｍ）に対して、
Ｔ＝Ｔ＋ΣＴＩＭＥ＿ＣＡＬＣ（ＳＵＢｉ）（ダミー変数ｉの範囲は１〜ｍ）を実行する。
ｃ３、ｎｏｄｅにかかわる各基本操作の数を算出し、ここで、ＯＰｉの数をＣｉと略記し、ＯＰｉ自身に必要な時間をＯＴｉと略記する。
Ｔ＝Ｔ＋ΣＣｉ＊ＯＴｉ（ここで、ダミー変数ｉの範囲は１〜ｎ）である。
ｃ４、ＴをＴＩＭＥ＿ＣＡＬＣの結果として戻す。
【００７１】
また、最適化器は実行計画の時間コストの算出に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、実行計画がツリー構造であり、基本操作が（ＯＰ１、ＯＰ２、…ＯＰｎ）を含み、最適化器の実行空間の算出関数がＳＰＡＣＥ＿ＣＡＬＣ（ＮＯＤＥ ｎｏｄｅ）であるとすると、以下はＳＰＡＣＥ＿ＣＡＬＣの実現である。
ｄ１、実行空間変数Ｓを０に初期化する。
ｄ２、ｎｏｄｅのサブノード（ＳＵＢ１、ＳＵＢ２……ＳＵＢｍ）に対して、
Ｓ＝Ｓ＋ＭＡＸ（ＳＰＡＣＥ＿ＣＡＬＣ（ＳＵＢｉ））（ダミー変数ｉの範囲は１〜ｍ）を実行する。
ｄ３、ｎｏｄｅにかかわる各基本操作の数を算出し、ここで、ＯＰｉの数をＣｉと略記し、ＯＰｉ自身に必要な空間をＯＴｉと略記する。
Ｓ＝Ｓ＋ＭＡＸ（Ｃｉ＊ＯＴｉ）（ここで、ダミー変数ｉの範囲は１〜ｎ）である。
ｄ４、ＳをＳＰＡＣＥ＿ＣＡＬＣの結果として戻す。
【００７２】
上記の説明からわかるように、最適化器は判断条件に従って複数の実行計画から最適な実行計画を選出し、選出された実行計画は比較的低い時間コストまたは空間コストを持つことが多いため、文書ベースシステム全体の性能を向上させる。
【００７３】
本発明の実施形態に係る最適化器は、計画器で生成された実行計画から最適な実行計画を直接に選択するようにしてもよいし、まず、遺伝的アルゴリズム、人工神経ネットワークなどのような人工知能アルゴリズムを用いて、計画器で生成された実行計画を最適化し、最適化された実行計画から最適な実行計画を選択するようにしてもよい。
【００７４】
上記最適化器の実行計画に対する最適化は、実行計画のコストまたは他のメトリック値をメトリック関数として、遺伝的アルゴリズムにおける適応度や、焼きなまし法におけるエネルギーのような知能アルゴリズムにおけるメトリック値と関連付け、これらのアルゴリズムを用いて実行計画空間に対して空間探索を行って、局所最適化された実行計画を得ることを根本とする。
【００７５】
以下、最適化器の実行計画に対する最適化の実現過程をいくつか紹介する。
【００７６】
最適化器が遺伝的アルゴリズムに基づいて初期実行計画を改善する過程は、以下のようなステップを含む。
ｅ１、実行計画ツリーを文字列に符号化して、文字列の集合、即ち、遺伝的アルゴリズムで用いられる初期集団を形成する。
ｅ２、実行の時間または空間を適応度のメトリック関数として、初期集団を進化させる。
ｅ３、所定数の後代まで進化すると、進化を停止し、最終的に得られた集団を実行計画に復号化する。
【００７７】
説明すべきものとして、上記の適応度のメトリック関数は、実行の時間空間に対応する以外に、文書に対してページビットマップの取得を実行する操作回数のような他のメトリックを選択するようにしてもよい。
【００７８】
最適化器が焼きなまし法に基づいて初期実行計画を改善する過程は、初期実行計画集合内の各実行計画ごとに以下の操作を実行する。
ｆ１、現在の実行計画がＣであり、改善後の実行計画がＢであり、ＢをＣに初期化する。
ｆ２、現在の温度Ｔを初期化する。
ｆ３、温度降下因子ＡＬＰＨＡを０〜１の値に初期化する。
ｆ４、Ｔが所定の停止温度ＦＴより大きい場合、以下の操作手順を繰り返して実行する。
ｆ４１、現在の温度で、実行回数が所定のＣＯＵＮＴより小さい場合、以下の操作を繰り返して実行する。
ｆ４１２、現在の実行計画Ｃを一時実行計画Ｗにコピーする。
ｆ４１３、Ｗに対してランダムに微小調整を行うが、ＷとＣの等価性を確保する必要がある。
ｆ４１４、ＣのエネルギーＥｃおよびＷのエネルギーＥｗ（即ち実行コスト）をそれぞれ算出する。
ｆ４１５、Ｅｃ＞Ｅｗの場合、ＷをＣおよびＢにコピーする。
ｆ４１６、Ｅｃ≦Ｅｗの場合、以下の計算を実行する。
ＴＥＳＴを０〜１のランダム値に初期化する。
ＤＥＬＴＡ＝Ｅｗ−Ｅｃ
ＲＥＳＵＬＴ＝ＥＸＰ（−ＤＥＬＴＡ／Ｔ）
ＲＥＳＵＬＴがＴＥＳＴより大きいとき、ＷをＣにコピーする。
ｆ４２、現在の温度をＴ＝Ｔ＊ＡＬＰＨＡのように降下させる。
ｆ５、実行計画ＢをＣにコピーする。
【００７９】
上記２種類のアルゴリズム以外に、最適化器は進化的アルゴリズム、発見的アルゴリズム、分岐限定法、山登り法、人工神経ネットワークまたはダイナミックプログラミングなどの技術分野のアルゴリズムを採用して、実行計画を最適化するようにしてもよい。他のアルゴリズムに基づいて初期実行計画を改善する処理過程は、ポリシーが上記２種類の方法に類似している。
【００８０】
初期実行計画に対して局所最適化を行うことにより、最適化器で選出された最適な実行計画のコストがさらに低くなることができ、文書ベースシステム全体の性能をさらに向上させる。
【００８１】
説明すべきものとして、本発明に係る解析器、計画器、最適化器、実行器および記憶操作モジュールのうち１つまたは複数のモジュールは、独立のモジュールで実現されるようにしてもよい。例えば、Ｗｉｎｄｏｗｓ（登録商標）システムにおいて、各モジュールそれぞれを単独のＤＬＬで実現するようにしてもよく、全てのモジュールを１つのＤＬＬで実現するようにしてもよい。ｌｉｎｕｘ（登録商標）システムにおいて、各モジュールそれぞれを１つのｓｏファイルで実現するようにしてもよく、全てのモジュールを１つのｓｏファイルで実現するようにしてもよい。Ｊａｖａ（登録商標）環境において、各モジュールそれぞれを１つの．ｃｌａｓｓファイルで実現するようにしてもよく、全てのモジュールを１つの．ｃｌａｓｓファイルで実現するようにしてもよい。
【００８２】
各モジュールの実現について、Ｃ、Ｃ＋＋、Ｊａｖａ、Ｐｙｔｈｏｎ、Ｒｕｂｙ、Ｐｅｒｌ、ＳｍａｌｌＴａｌｋ、Ａｄａ、Ｓｉｍｕｌａ、Ｐａｓｃａｌ、Ｈａｓｋｅｌｌなどの言語を用いて開発するようにしてもよい。
【００８３】
図３は本発明に係る文書ベースシステムの実現方法のフローチャートである。図３に示すように、本発明の実施形態に係る文書ベースシステムの実現方法は、以下のようなステップを含む。
【００８４】
ステップ３０１で、アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作からなる中間形式に解析する。
【００８５】
本ステップでは、アプリケーションによる文書ベースシステム標準インターフェースの呼び出しは、文書ベースシステムに関する基礎出願書類に説明されたＵＯＭＬであってもよく、命令列の形式であってよいが、いずれも文書ベースシステムに関する基礎出願に指摘された汎用文書モデルに適合すべきである。アプリケーションからの呼び出しに対して字句・構文解析を行って、標準インターフェース規範に適合する、汎用文書モデルのオブジェクトまたは操作を含む中間形式を生成する。ＸＭＬの場合、ＸＭＬ解析器を用いてＤＯＭツリーを生成するようにしてもよい。命令列形式の場合、用いられる命令列は一般的にＬＡＬＲ（１）文法に適合する。文法定義が与えられる場合、ｌｅｘおよびｙａｃｃで生成された字句および構文解析器を用いて命令列を解析するようにしてもよい。
【００８６】
ステップ３０２で、中間形式を、物理記憶に対する操作を含む実行計画に変換する。
【００８７】
本ステップでは、中間形式を構成する汎用文書モデルのオブジェクトまたは操作は論理操作である。これらの論理操作は比較的高い階層の概念である。１つの論理操作は、物理記憶に対する単一の操作にマッピングされることも、物理記憶に対する複数の操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。同一の中間形式について、毎回変換後の実行計画が異なることは可能である。
【００８８】
構文ツリーで表された中間形式を例として、本ステップでは、中間形式を実行計画に変換する過程は具体的に以下のようなステップを含むようにしてもよい。
【００８９】
構文ツリー内の各論理操作Ｌ＿ＯＰを列挙する。ここでの論理操作は一組の論理操作のシーケンスであってもよい。
【００９０】
Ｌ＿ＯＰに対応する物理操作集合（Ｐ＿ＯＰ１、Ｐ＿ＯＰ２、…、Ｐ＿ＯＰｍ）を取得する。ここでの各物理操作Ｐ＿ＯＰｊは一組の物理操作のシーケンスであってもよい。
【００９１】
Ｌ＿ＯＰに対してＰ＿ＯＰｉのような物理操作を選択する。
【００９２】
構文ツリー内の全ての論理操作に対して、上記手順に従って対応の物理操作を選択し、構文ツリー内の全ての論理操作が対応の物理操作に替えられると、実行計画が生成される。
【００９３】
ＤＯＭツリーおよび他の中間形式に対する変換は上記実現に類似している。
【００９４】
ステップ３０３で、変換して得られた実行計画をスケジューリングして実行する。
【００９５】
具体的に、本ステップでは、実行計画に対応するツリーのルートノードから、トップダウンで再帰し、ツリーの最下位ノードに到着すると、ボトムアップで実際の操作を実行し、実行計画全体を次第に完成する。
【００９６】
上記方法によって実現された文書ベースシステムは、各ステップ間のインターフェースが標準インターフェース規範を満たす条件で、各ステップの具体的な実現が互いに独立であるため、文書ベースシステム全体の実現に優れた拡張性、柔軟性および保守性を持たせる。
【００９７】
上記プロセスでは、ステップ３０２で変換して得られた実行計画が複数ある場合、ステップ３０２は具体的に以下のようなステップを含む。
【００９８】
ステップ３０２１で、汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に解析する。
【００９９】
中間形式を構成する汎用文書モデルのオブジェクトまたは操作は論理操作である。これらの論理操作は比較的高い階層の概念である。１つの論理操作は、単一の物理操作にマッピングされることも、複数の物理操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。論理操作を含む中間形式に基づいて、対応の複数の実行計画をランダムに生成するようにしてもよい。
【０１００】
ステップ３０２２で、判断条件に従って複数の実行計画から最適な実行計画を選択する。
【０１０１】
上記ステップ３０２２では、判断条件に従って、生成された実行計画集合から最適な実行計画を選出するようにしてもよい。説明すべきものとして、いわゆる「最適」とは、判断条件または実際のニーズという意味から言われたものである。例えば、実行時間が最少となることを図るという判断条件で選出された最適な実行計画は、実行に必要な最大空間が大きい可能性があるため、実行に必要な最大空間が最小となることを図るという判断条件で、最適な実行計画と言えない。上記の判断条件は経験ルールであってもよく、或いは、実行計画のコストに基づく比較、即ち、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せに基づく比較であってもよい。
【０１０２】
具体的に、上記ステップ３０２２の操作過程は複数の方法で実現されるようにしてもよい。以下、例を挙げて説明する。
【０１０３】
１つは、経験ルールの優先度に基づいて最適な実行計画を選択する方法である。仮に、判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールの優先度がＲ１＞Ｒ２＞…＞ＲＬであるとすると、該方法は以下のようなステップを含む。
【０１０４】
実行計画集合を生成された全ての実行計画に設定し、現在の判断用経験ルールをＲｉ（ｉ＝１）に設定する。
【０１０５】
実行計画集合内の全ての実行計画に対して、ルールＲｉに適合するかどうかを順次に判断し、ある実行計画がルールＲｉに適合しない場合、該実行計画を標記して、該実行計画を実行計画集合から除去する。
【０１０６】
実行計画集合が空になる場合、ｂ２で標記された実行計画を実行計画集合に入れて、次のステップを実行する。ｉがＬに等しい場合、次のステップを実行し、ｉがＬに等しくない場合、ｉに１を加えて、ｂ２を繰り返して実行する。
【０１０７】
経験ルールの優先度に基づいて選択される最適な実行計画として、実行計画集合から１つの実行計画を任意に選出する。
【０１０８】
もう１つは、経験ルールの重みに基づいて最適な実行計画を選択する方法である。仮に、判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールＲｉの重みがＰＲｉであるとすると、該方法は以下のようなステップを含む。
【０１０９】
全ての実行計画に対して、その重みを０に初期化する。
【０１１０】
各実行計画に対して、ルールＲｉ（ｉ＝１，…，Ｌ）に適合するかどうかを判断し、適合する場合、該実行計画の重みにＰＲｉを加える。
【０１１１】
各実行計画の重みに基づいて、経験ルールの重みに基づいて選択される最適な実行計画として、重みが最大となる実行計画を選出する。重みが最大となる実行計画が複数ある場合、１つを任意に選出するようにしてもよい。
【０１１２】
上記は、経験ルールに基づいて最適な実行計画を選択する２種類の方法を説明したが、以下、実行計画のコストに基づいて最適な実行計画を選択する方法を紹介する。
【０１１３】
実行計画のコストは時間コストと空間コストとを含む。時間コストとは、実行計画全体の実行にかかる時間を指すが、空間コストとは、実行過程全体で最終結果および中間結果が占用可能な最大空間を指す。このような実行にかかわるディスクＩ／Ｏ時間が時間コストの主要部分となるため、時間コストの算出も主にディスクＩ／Ｏ時間の算出である。空間コストにとって、メモリとディスクとの両方の占用にかかわる。
【０１１４】
実行計画の時間コストおよび空間コストの算出方法について、上記最適化器の実現に関する相応内容を参照してよい。
【０１１５】
上記複数の実行計画を生成して最適な実行計画を選択するステップによれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の実現方法が高い性能を持つようになる。
【０１１６】
本発明の実施形態に係る文書ベースシステムの実現方法において、ステップ３０２１とステップ３０２２との間に、対応の複数の実行計画を最適化する過程をさらに含む。該最適化過程によって、複数の局所最適化された実行計画を取得することができる。
【０１１７】
このように、ステップ３０２２は、最適化された複数の実行計画から１つの最適な実行計画を選択する。
【０１１８】
上記実行計画に対する最適化は、実行計画のコストまたは他のメトリック値をメトリック関数として、遺伝的アルゴリズムにおける適応度や、焼きなまし法におけるエネルギーのような知能アルゴリズムにおけるメトリック値と関連付け、これらのアルゴリズムを用いて実行計画空間に対して空間探索を行って、局所最適化された実行計画を得ることを根本とする。
【０１１９】
実行計画を最適化する方法は、遺伝的アルゴリズムや、焼きなまし法などを含む。この２種類の方法の具体的なステップについて、最適化器に関する相応内容の説明を参照する。
【０１２０】
上記説明された２種類のアルゴリズム以外に、進化的アルゴリズム、発見的アルゴリズム、分岐限定法、山登り法、人工神経ネットワークまたはダイナミックプログラミングなどの技術分野のアルゴリズムを採用して、実行計画を最適化するようにしてもよい。他のアルゴリズムに基づいて初期実行計画を改善する方法は、ポリシーが上記２種類の方法に類似している。
【０１２１】
初期実行計画に対して局所最適化を行うステップによれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能がさらに向上する。
【０１２２】
要するに、本発明に係る文書ベースシステムおよびその実現方法では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、本発明に係る文書ベースシステムは、拡張性、柔軟性および保守性を持つ。本発明に係る最適化器および相応の最適化アルゴリズムによれば、複数の実行計画から１つの最適な実行計画を選出することができ、実行の性能を向上させるため、文書ベースシステム全体の性能を向上させる。初期実行計画に対する局所最適化によれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させ、文書ベースシステム全体の実現に高い性能を持たせる。
【０１２３】
上記は本発明の好ましい具体的な実施形態にすぎないが、本発明の保護範囲はこれに限られない。本発明に掲げる技術範囲内で、いかなる当業者が容易に想到できる変更または置換えは、全て本発明の保護範囲内に含まれるべきである。そのため、本発明の保護範囲は、特許請求の範囲の保護範囲に準すべきである。
【技術分野】
【０００１】
本発明は電子文書処理技術に関し、特に、文書ベースシステムおよびその実現方法に関する。
【背景技術】
【０００２】
文書ベースシステムは大量の文書に対する組織、管理、セキュリティ、表示、記憶などの諸機能を提供している。本出願人が先に提出した基礎出願である出願番号ＣＮ２００５１０１３１０７２．０の明細書には、文書ベースシステム、記憶装置、アプリケーションを含む文書処理システムが提供されている。ここで、文書ベースデータが記憶装置に記憶され、文書ベースシステムとアプリケーションとが標準呼び出しインターフェースを介して接続される。アプリケーションによる文書の操作は事前定義の汎用文書モデルに対する統一の操作を含む。アプリケーションは標準呼び出しインターフェースを介して文書ベースシステムへ指令を送信し、この過程が即ちアプリケーションからの呼び出しである。文書ベースシステムは受信された指令に従って、記憶装置に記憶されている文書ベースデータに対して相応の操作を実行する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ここで、文書ベースシステムは大量の論理概念および操作にかかわり、多くの機能をサポートする必要があるため、一般的に、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることは極めて困難である。この課題をアーキテクチャーから解決しないと、最終的に実現される文書ベースシステムは、優れた拡張性、柔軟性、および保守性を持つことができない。
【０００４】
本発明は、文書ベースシステムおよびその実現方法を提供することを主な目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る文書ベースシステムは、
アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析する解析器と、
前記中間形式を、物理記憶に対する操作を含む実行計画に変換する計画器と、
前記実行計画を実行することにより、記憶操作モジュールをスケジューリングして、前記実行計画内の物理記憶に対する操作を実行する実行器と、
前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する記憶操作モジュールと、を含む。
【０００６】
本発明に係る文書ベースシステムは、判断条件に従って、計画器で生成された複数の実行計画から１つの最適な実行計画を選択する最適化器をさらに含む。
【０００７】
さらに、本発明に係る文書ベースシステムにおける最適化器は、計画器で生成された実行計画を最適化する。
【０００８】
前記実行計画を最適化するためのアルゴリズムは、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せを含む。
【０００９】
上記の判断条件は、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含む。
【００１０】
また、上記のアプリケーションからの呼び出しは、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式である。
【００１１】
上記の中間形式は、構文ツリーまたは文書オブジェクトモデルツリーを含む。
【００１２】
上記の記憶操作モジュールは、論理パーティション、物理ディスク、仮想記憶、またはメモリを含む物理記憶に対する操作をサポートする。仮想記憶はリモート記憶またはネットワーク記憶を含む。リモート記憶はネットワークファイルシステムまたは分散ファイルシステムを含み、ネットワーク記憶はストレージエリアネットワーク、グリッド、またはピアツーピア方式の記憶を含む。
【００１３】
ここからわかるように、上記解決手段は具体的な文書ベースシステム構成を提供している。そして、上記解決手段からわかるように、本発明では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、本発明に係る文書ベースシステムは、拡張性、柔軟性および保守性を持つ。本発明に係るによれば、複数の実行計画から１つの最適な実行計画を選出することができ、実行の性能を向上させるため、文書ベースシステム全体の性能を向上させる。初期実行計画に対する局所最適化によれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させる。
【００１４】
本発明に係る文書ベースシステムの実現方法は、
アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析するステップと、
中間形式を、物理記憶に対する操作を含む実行計画に変換するステップと、
前記実行計画内の物理記憶に対する操作をスケジューリングして実行するステップと、を含む。
【００１５】
ここで、前記中間形式を物理記憶に対する操作を含む実行計画に変換するステップは、
汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に変換するステップと、
判断条件に従って複数の実行計画から１つの最適な実行計画を選択するステップと、を含む。
【００１６】
また、前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択する前に、生成された実行計画を最適化することをさらに含む。ここで、前記生成された実行計画を最適化することは、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せに基づいて最適化することを含む。
【００１７】
ここで、上記のアプリケーションからの呼び出しは、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式である。中間形式は、構文ツリーまたは文書オブジェクトモデルツリーを含む。判断条件は、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含む。
【００１８】
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択することは、経験ルール優先度アルゴリズムまたは経験ルール重みアルゴリズムに基づいて、複数の実行計画から１つの最適な実行計画を選択することを含む。
【発明の効果】
【００１９】
ここからわかるように、上記解決手段は具体的な文書ベースシステムの実現方法を提供している。そして、上記解決手段からわかるように、本発明では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、文書ベースシステム全体の実現は、高い拡張性、柔軟性および保守性を持つ。本発明によれば、複数の実行計画から最適な実行計画を選択することができるため、選出された最適な実行計画のコストが比較的低くなり、実行の性能を向上させ、文書ベースシステムに比較的高い性能を持たせる。計画器で生成された複数の実行計画に対して局所最適化を行うことによって、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係る文書ベースシステムの階層を示す図である。
【図２】本発明に係る文書ベースシステムの構成を示す図である。
【図３】本発明に係る文書ベースシステムの実現方法のフローチャートである。
【発明を実施するための形態】
【００２１】
本発明の目的、解決手段およびメリットをさらに明確にするために、以下、図面を参照して実施形態をあげながら、本発明をさらに詳しく説明する。
【００２２】
本発明の実施形態では、文書ベースシステムの実現が複数の層に分けられ、隣接層の間のインターフェースについて標準規範が定義されている。
【００２３】
図１は本発明に係る文書ベースシステムの階層を示す図である。図１に示すように、本発明の実施形態において、文書ベースシステムの実現が図示の幾つかの層に分けられ、各層はそれぞれ、アプリケーションからの呼び出しを、論理操作を含む中間形式に変換し、論理操作を含む中間形式を、物理記憶に対する操作を含む実行計画に変換し、変換によって得られた実行計画を実行する。
【００２４】
このように、各層の出力結果が標準インターフェース規範に適合する条件で、各層の具体的な実現はそれぞれ複数の方式であってもよい。これにより、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることができる。
【００２５】
図２は本発明に係る文書ベースシステムの構成を示す図である。図２に示すように、本発明の実施形態に係る文書ベースシステムは、解析器と、計画器と、実行器と、記憶操作モジュールと、を含む。
【００２６】
解析器は、アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作からなる中間形式に解析する。
【００２７】
計画器は、解析器で解析して得られた中間形式を、物理記憶に対する操作からなる実行計画に変換する。
【００２８】
ここで、中間形式を構成する論理操作は比較的高い階層の概念である。１つの論理操作は、単一の物理操作にマッピングされることも、複数の物理操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。同一の中間形式について、毎回、計画器で変換して得られた実行計画が異なることは可能であるが、これらの実行計画は等価である。
【００２９】
実行器は、計画器で変換して得られた実行計画を実行することによって、記憶操作モジュールをスケジューリングして、該実行計画内の物理記憶に対する操作を実行する。
【００３０】
記憶操作モジュールは、前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する。
【００３１】
上記はある文書ベースシステムの具体的な構成である。そして、各層の出力結果が標準インターフェース規範に適合する条件で、各層の具体的な実現はそれぞれ複数の方式であってもよい。これにより、文書ベースシステムに優れた拡張性、柔軟性、および保守性を持たせることができる。
【００３２】
以下、上記文書ベースシステムにおける各モジュールをそれぞれ詳しく説明する。
【００３３】
具体的に、解析器から出力された中間形式は標準インターフェース規範に適合する。中間形式は具体的に構文ツリーまたは文書オブジェクトモデル（ＤＯＭ：Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）ツリーを含むようにしてもよい。アプリケーションによる文書ベースシステムの標準インターフェースに対する呼び出しは、まず解析器で処理される。標準インターフェースは、文書ベースシステムに関する基礎出願書類に説明された拡張可能なマークアップ言語（ＸＭＬ：ＥＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）形式のＵＯＭＬインターフェースであってもよく、命令列の形式、または他の形式であってもよいが、いずれも基礎出願に説明された文書処理システムにおける汎用文書モデルに適合する必要がある。
【００３４】
このように、アプリケーションからの呼び出しが解析器によって字句・構文解析された後、標準インターフェース規範に適合する、汎用文書モデルのオブジェクトまたは操作からなる中間形式が生成される。
【００３５】
実際の応用では、ＸＭＬ形式の標準インターフェースの場合、上記文書ベースシステムにおける解析器がＸＭＬ解析器であり、アプリケーションを解析してＤＯＭツリーを生成するようにしてもよい。命令列形式の標準インターフェースの場合、用いられる命令列は一般的にＬＡＬＲ（１）（Ｌｏｏｋａｈｅａｄ Ｌｅｆｔ ｔｏ Ｒｉｇｈｔ Ｐａｒｓｉｎｇ）文法に適合する。文法定義が与えられる場合、上記文書ベースシステムにおける解析器は、ｌｅｘ（Ｌｅｘｉｃａｌ ｃｏｍｐｉｌｅｒ）およびｙａｃｃ（Ｙｅｔ ａｎｏｔｈｅｒ ｃｏｍｐｉｌｅｒ ｃｏｍｐｉｌｅｒ）で生成された字句および構文解析器であってよい。ここで、ｌｅｘはスキャナを生成するツールであり、即ち字句解析器を生成するツールである。ｙａｃｃはＬＡＬＲ（１）解析器の自動生成ツールであり、そのバージョン１が１９７０年代初期に発表され、アメリカのベル研究所のソフトウェア製品である（作者はＳ．Ｃ．Ｊｏｈｎｓｏｎ）。現在、この２つのツールはＵＮＩＸ（登録商標）、ＤＯＳ（登録商標）などのシステムプラットフォームで広く流行している。具体的なＸＭＬ解析およびｌｅｘ、ｙａｃｃ解析は従来技術である。
【００３６】
以下、例をあげて、ＸＭＬ形式に基づく標準インターフェース呼び出しの解析を具体的に説明する。
<call>
<stringValval=″AppendLine″ name=″MethodName″/>
<stringValval=″0xabcd1234″ name=″PathObj″/>
<compoundValname=″LineObj″>
<line>
<startxCod=″1000.23″ yCod=″2193.324″/>
<endxCod=″3233.234″ yCod=″2342.234″/>
</line>
</compoundVal>
</call>
【００３７】
上記コードはＸＭＬ形式の標準インターフェース呼び出しを表し、インターフェースメソッドの名称はＡｐｐｅｎｄＬｉｎｅであり、該メソッドのタスクはハンドルが０ｘａｂｃｄ１２３４であるパスオブジェクトへの線分追加であり、該線分の両端点の位置はそれぞれ（１０００．２３，２１９３．３２４）および（３２３３．２３４，２３４２．２３４）である。
【００３８】
解析器は上記のＸＭＬ形式の標準インターフェース呼び出しを解析し、解析結果がＤＯＭツリーであり、該ＤＯＭツリーの構造は、ルート要素ｃａｌｌと、ｃａｌｌに含まれた３つのサブ要素（２つのｓｔｒｉｎｇＶａｌおよび１つのｃｏｍｐｏｕｎｄＶａｌ）とを含む。
【００３９】
即ち、以下のような形式である。
call
stringVal
stringVal
compoundVal
【００４０】
以下はＬＡＬＲ（１）文法に適合するカスタマイズ言語による文書ベースシステムに対する標準インターフェース呼び出しである。
call withname=AppendLine, params=(PathObj=″0xabcd1234″, LineObj=(StartPt=(1000.23,2193.324), EndPt=(3233.234, 2342.234)));
【００４１】
解析器は、対応の字句および構文解析器によって、上記のカスタマイズ形式のアプリケーションからの呼び出しを解析して、構文ツリーを生成する。上記字句および構文解析器は、ｌｅｘまたはｙａｃｃを予め呼び出してカスタマイズ言語の字句および構文を定義することによって、生成されるようにしてもよい。構文ツリーは下記のＣ構造で表されるようにしてもよい。
struct SyntaxTree
{
structNode *pRoot;
};
struct Node
{
struct Node *pLeft;
struct Node *pRight;
......
}
【００４２】
具体的なツリー構造は上記例示のＤＯＭツリーに類似している。
【００４３】
以下、中間形式が構文ツリーである場合を例として、計画器が論理操作を物理操作に変換するプロセスを詳しく説明する。
【００４４】
構文ツリー内の各論理操作Ｌ＿ＯＰを列挙する。ここでの論理操作は一組の論理操作のシーケンスであってもよい。まず、Ｌ＿ＯＰに対応する物理操作集合（Ｐ＿ＯＰ１、Ｐ＿ＯＰ２、…、Ｐ＿ＯＰｍ）を取得する。ここでの各物理操作Ｐ＿ＯＰｊは一組の物理操作のシーケンスであってもよい。次いで、Ｌ＿ＯＰに対してＰ＿ＯＰｉのような物理操作を選択する。そして、構文ツリー内の全ての論理操作に対して、上記プロセスに従って対応の物理操作を選択する。構文ツリー内の全ての論理操作が対応の物理操作に替えられると、実行計画が生成される。
【００４５】
ＤＯＭツリーおよび他の中間形式に対する変換は上記実現に類似している。
【００４６】
上記のＤＯＭツリーとなる中間形式を計画器で変換して生成された実行計画は以下の通りである。
AppendLine
PathObj
CreateLine
StartPt
EndPt
【００４７】
ここで、実行計画のルートノードＡｐｐｅｎｄＬｉｎｅは操作であり、その１番目のサブノードＰａｔｈＯｂｊはＰａｔｈオブジェクトのハンドルであるが、２番目のサブノードは線分オブジェクトを作成するためのＣｒｅａｔｅＬｉｎｅ操作であり、ＣｒｅａｔｅＬｉｎｅの２つのサブノードはそれぞれ作成しようとする線分の始点および終点である。
【００４８】
ＣｒｅａｔｅＬｉｎｅの実行結果、対応の線分オブジェクトが生成されるが、ＡｐｐｅｎｄＬｉｎｅ操作により、該線分オブジェクトはＰａｔｈオブジェクトに追加される。
【００４９】
図２に示すような文書ベースシステムにおける実行器について、普通、実行計画が物理記憶に対する操作を含むツリーであるため、実行器は実行計画に対応するツリーのルートノードから、トップダウンで再帰し、ツリーの最下位ノードから、ボトムアップで記憶操作モジュールをスケジューリングして実際の操作を実行し、実行計画全体を次第に完成する。
【００５０】
例えば、実行器は下記の実行計画を実行する。
OP1
Para1
Para2
OP2
Para3
Para4
OP3
Para5
Para6
【００５１】
ここで、ＯＰ１、ＯＰ２およびＯＰ３は３つの操作であり、Ｐａｒａ１〜Ｐａｒａ６は操作に対応する６つのパラメータである。実行器が上記実行計画を実行する手順は以下の通りである。
ＯＰ３（Ｐａｒａ５，Ｐａｒａ６）を実行し、結果はｒｅｓ３となり、
ＯＰ２（Ｐａｒａ３，Ｐａｒａ４，ｒｅｓ３）を実行し、結果はｒｅｓ２となり、
ＯＰ１（Ｐａｒａ１，Ｐａｒａ２，ｒｅｓ２）を実行し、結果はｒｅｓ１となる。
【００５２】
図２に示すような文書ベースシステムにおける記憶操作モジュールは、各種の物理記憶層、例えば物理エンティティに基づく物理記憶層または仮想の物理記憶層において構築されるようにしてもよく、性能や規模に異なる制限がある。
【００５３】
実際の応用では、物理記憶層により提供されたインターフェース類型、即ち記憶操作モジュールと物理記憶層との間のインターフェース類型が、実行計画を構成する物理操作の構成に影響を与えるため、計画器で生成された実行計画も所定のインターフェース類型に応じる必要がある。例えば、物理記憶層がバイナリストリームのリード／ライトのみを提供する場合、実行計画を構成する物理操作はおそらくリード／ライトの２種類の物理操作のみを含み、物理記憶層が文書ベースの作成、文書集合の作成などのようなより多くの操作を提供する場合、実行計画を構成する物理操作は多くなる。物理記憶層の提供必要な基本オブジェクトは文書ベース、文書集合、文書などを含み、物理記憶の割当、回収、リードライトの機能を提供することも必要である。
【００５４】
論理パーティション、物理ディスク、仮想記憶、メモリなどの媒体を使用するとき、記憶操作モジュールの実現は類似している。オペレーションシステムで提供されるファイルシステム、オペレーションシステムで提供される論理パーティション、オペレーションシステムで提供される、物理ディスクにアクセスするためのインターフェース、オペレーションシステムを経由せず物理ディスクにアクセスするためのインターフェース、オペレーションシステムで提供される、仮想メモリもしくは物理メモリにアクセスするためのインターフェース、オペレーションシステムを経由ぜず物理メモリに直接にアクセスするためのインターフェース、または仮想記憶装置を基に、記憶操作モジュールを構築するようにしてもよい。この上で、文書ベース、文書集合、文書などの物理記憶層のオブジェクトを実現する。
【００５５】
ここで、仮想記憶はリモート記憶を使用するようにしてもよい。即ち、実際の物理記憶は別のコンピューティングデバイスにある。例えば、ネットワークファイルシステム（ＮＦＳ）、分散ファイルシステム（ＤＦＳ）である。仮想記憶はネットワーク記憶を使用するようにしてもよい。即ち、実際の物理記憶はネットワークにより提供される。例えば、ストレージエリアネットワーク（ＳＡＮ：Ｓｔｏｒａｇｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、グリッド（ＧＲＩＤ）、ピアツーピア（Ｐ２Ｐ：ＰＥＥＲ−ｔｏ−ＰＥＥＲ）方式の記憶などである。
【００５６】
ファイルシステムを例として、記憶操作モジュールは以下のような操作を実行する。
【００５７】
あるディレクトリを文書ベースとして設定し、
文書ベースディレクトリの下に、１つまたは複数の文書集合ディレクトリを作成し、
文書集合ディレクトリの下に、文書として１つまたは複数のファイルを作成し、
文書に、ページ、層、ページストリームなどを作成するようにしてもよい。
【００５８】
最終的なディレクトリ構成は例えば以下のようになり、ここで、文書はファイルの形式で示され、ｄｏｃｌｉｓｔディレクトリの下に置かれる。
/……
docbase/
doclist/
doclist/
……
【００５９】
上記は本発明に係る文書ベースシステムの各モジュールの具体的な実現である。上記のように、異なるモジュールの間に標準のインターフェース規範がある。入出力が標準インターフェース規範に適合する条件で、各モジュールの具体的な実現は異なる方法を採用してもよい。これにより、文書ベースシステム全体の実現に拡張性、柔軟性および保守性を持たせることができる。
【００６０】
上記文書ベースシステムの計画器によって同一の中間形式を変換して得られた実行計画が異なることは可能である。これらの実行計画が等価であるが、異なる実行計画によって、実行にかかる時間や空間は常に大きな違いがある。そのため、対応の実行計画集合から決定された実行計画が最適であるかどうかは、文書ベースシステムの性能に大きな影響を与える。
【００６１】
従って、本発明の実施形態において、図２に示すような文書ベースシステムは、中間形式に対応する実行計画集合から、所定の判断条件に従って最適な実行計画を選出する最適化器をさらに含むようにしてもよい。
【００６２】
最適化器の実現の１つとして、計画器で所定数の実行計画を生成し、例えば、計画器は所定数の実行計画をランダムに生成してもよく、次いで、最適化器は判断条件に従って、生成された実行計画集合から最適な実行計画を選出する。説明すべきものとして、いわゆる「最適」とは、判断条件または実際のニーズという意味から言われたものである。例えば、実行時間が最少となることを図るという判断条件で選出された最適な実行計画は、実行に必要な最大空間が大きい可能性があるため、実行に必要な最大空間が最小となることを図るという判断条件で、最適な実行計画と言えない。上記の判断条件は経験ルールであってもよく、或いは、実行計画のコストに基づく比較、即ち、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せに基づく比較であってもよい。
【００６３】
実際の応用では、最適化器が様々な方式で実現できる。以下、例を挙げてそれぞれ説明する。
【００６４】
図２に示すような文書ベースシステムにおける最適化器は、経験ルールの優先度に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、最適化器の判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールの優先度がＲ１＞Ｒ２＞…＞ＲＬであるとすると、該最適化器は以下のような操作を実行する。
ａ１、実行計画集合を生成された全ての実行計画に設定し、現在の判断用経験ルールをＲｉ（初期化状態でｉ＝１）に設定する。
ａ２、実行計画集合内の全ての実行計画に対して、ルールＲｉに適合するかどうかを順次に判断し、ある実行計画がルールＲｉに適合しない場合、該実行計画を標記して、該実行計画を実行計画集合から除去する。
ａ３、実行計画集合が空になる場合、ａ２で標記された実行計画を実行計画集合に入れる。ｉがＬに等しいかどうかを判断し、ｉがＬに等しい場合、経験ルールの優先度に基づいて選択される最適な実行計画として、実行計画集合から１つの実行計画を任意に選出し、ｉがＬに等しくない場合、ｉに１を加えて、ａ２の操作を繰り返して実行する。
【００６５】
図２に示すような文書ベースシステムにおける最適化器は、経験ルールの重みに基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、最適化器の判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールＲｉの重みがＰＲｉであるとするとともに、各実行計画ごとに対応の重みを設けると、該最適化器は以下のような操作を実行する。
ｂ１、全ての実行計画に対して、その重みを０に初期化する。
ｂ２、各実行計画に対して、ルールＲｉ（ｉ＝１，…，Ｌ）に適合するかどうかを判断し、適合する場合、該実行計画の重みにＰＲｉを加える。
ｂ３、各実行計画の重みに基づいて、経験ルールの重みに基づいて選択される最適な実行計画として、重みが最大となる実行計画を選出する。条件に適合する最適な実行計画が複数ある場合、１つを任意に選出するようにしてもよい。
【００６６】
上記２種類の最適化器はいずれも経験ルールに基づいて最適な実行計画を選択するものであるが、本発明の実施形態に係る最適化器は実行計画のコストに基づいて最適な実行計画を選択するようにしてもよい。
【００６７】
ここで、実行計画のコストは時間コストと空間コストとを含む。時間コストは、実行計画全体の実行にかかる時間を指し、主にディスクＩ／Ｏ時間を含む。空間コストは、実行計画全体の実行過程中で最終結果および中間結果が占用可能な最大空間を指し、メモリとディスクとの両方の占用量にかかわる。
【００６８】
実行計画の時間コストに基づいて最適な実行計画を選択すると、最適化器は実行計画を若干の基本操作に分解し、各基本操作にかかる時間を基準にして、各基本操作の実際の実行回数によって累加し、最後に実行計画にかかる合計時間を見積る。通常の方法として、最適化器は再帰の実行順序に従って実行計画全体を走査して、各基本操作の実行回数を取得してから、実行計画全体にかかる時間を算出する。
【００６９】
実行計画の時間コストとの相違として、通常、実行計画の空間コストは実行過程中の空間の最大値を指す。算出の方法として、最適化器は再帰的順序に従って、ボトムアップで算出して、現在の実行に必要な空間を現在の最大空間値と比較し、現在の最大空間値より大きい場合、現在の最大空間を現在の実行空間で取り替え、実行計画の算出が終了した後、実行計画の最大空間、即ち、該実行計画の空間コストを得ることができる。
【００７０】
具体的に、最適化器は実行計画の時間コストの算出に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、実行計画がツリー構造であり、基本操作が（ＯＰ１、ＯＰ２、…ＯＰｎ）を含み、最適化器の実行計画の時間コストの算出関数がＴＩＭＥ＿ＣＡＬＣ（ＮＯＤＥ ｎｏｄｅ）であるとすると、以下はＴＩＭＥ＿ＣＡＬＣの算出過程の実現である。
ｃ１、実行時間変数Ｔを０に初期化する。
ｃ２、ｎｏｄｅのサブノード（ＳＵＢ１、ＳＵＢ２…ＳＵＢｍ）に対して、
Ｔ＝Ｔ＋ΣＴＩＭＥ＿ＣＡＬＣ（ＳＵＢｉ）（ダミー変数ｉの範囲は１〜ｍ）を実行する。
ｃ３、ｎｏｄｅにかかわる各基本操作の数を算出し、ここで、ＯＰｉの数をＣｉと略記し、ＯＰｉ自身に必要な時間をＯＴｉと略記する。
Ｔ＝Ｔ＋ΣＣｉ＊ＯＴｉ（ここで、ダミー変数ｉの範囲は１〜ｎ）である。
ｃ４、ＴをＴＩＭＥ＿ＣＡＬＣの結果として戻す。
【００７１】
また、最適化器は実行計画の時間コストの算出に基づいて最適な実行計画の選択を実現するようにしてもよい。仮に、実行計画がツリー構造であり、基本操作が（ＯＰ１、ＯＰ２、…ＯＰｎ）を含み、最適化器の実行空間の算出関数がＳＰＡＣＥ＿ＣＡＬＣ（ＮＯＤＥ ｎｏｄｅ）であるとすると、以下はＳＰＡＣＥ＿ＣＡＬＣの実現である。
ｄ１、実行空間変数Ｓを０に初期化する。
ｄ２、ｎｏｄｅのサブノード（ＳＵＢ１、ＳＵＢ２……ＳＵＢｍ）に対して、
Ｓ＝Ｓ＋ＭＡＸ（ＳＰＡＣＥ＿ＣＡＬＣ（ＳＵＢｉ））（ダミー変数ｉの範囲は１〜ｍ）を実行する。
ｄ３、ｎｏｄｅにかかわる各基本操作の数を算出し、ここで、ＯＰｉの数をＣｉと略記し、ＯＰｉ自身に必要な空間をＯＴｉと略記する。
Ｓ＝Ｓ＋ＭＡＸ（Ｃｉ＊ＯＴｉ）（ここで、ダミー変数ｉの範囲は１〜ｎ）である。
ｄ４、ＳをＳＰＡＣＥ＿ＣＡＬＣの結果として戻す。
【００７２】
上記の説明からわかるように、最適化器は判断条件に従って複数の実行計画から最適な実行計画を選出し、選出された実行計画は比較的低い時間コストまたは空間コストを持つことが多いため、文書ベースシステム全体の性能を向上させる。
【００７３】
本発明の実施形態に係る最適化器は、計画器で生成された実行計画から最適な実行計画を直接に選択するようにしてもよいし、まず、遺伝的アルゴリズム、人工神経ネットワークなどのような人工知能アルゴリズムを用いて、計画器で生成された実行計画を最適化し、最適化された実行計画から最適な実行計画を選択するようにしてもよい。
【００７４】
上記最適化器の実行計画に対する最適化は、実行計画のコストまたは他のメトリック値をメトリック関数として、遺伝的アルゴリズムにおける適応度や、焼きなまし法におけるエネルギーのような知能アルゴリズムにおけるメトリック値と関連付け、これらのアルゴリズムを用いて実行計画空間に対して空間探索を行って、局所最適化された実行計画を得ることを根本とする。
【００７５】
以下、最適化器の実行計画に対する最適化の実現過程をいくつか紹介する。
【００７６】
最適化器が遺伝的アルゴリズムに基づいて初期実行計画を改善する過程は、以下のようなステップを含む。
ｅ１、実行計画ツリーを文字列に符号化して、文字列の集合、即ち、遺伝的アルゴリズムで用いられる初期集団を形成する。
ｅ２、実行の時間または空間を適応度のメトリック関数として、初期集団を進化させる。
ｅ３、所定数の後代まで進化すると、進化を停止し、最終的に得られた集団を実行計画に復号化する。
【００７７】
説明すべきものとして、上記の適応度のメトリック関数は、実行の時間空間に対応する以外に、文書に対してページビットマップの取得を実行する操作回数のような他のメトリックを選択するようにしてもよい。
【００７８】
最適化器が焼きなまし法に基づいて初期実行計画を改善する過程は、初期実行計画集合内の各実行計画ごとに以下の操作を実行する。
ｆ１、現在の実行計画がＣであり、改善後の実行計画がＢであり、ＢをＣに初期化する。
ｆ２、現在の温度Ｔを初期化する。
ｆ３、温度降下因子ＡＬＰＨＡを０〜１の値に初期化する。
ｆ４、Ｔが所定の停止温度ＦＴより大きい場合、以下の操作手順を繰り返して実行する。
ｆ４１、現在の温度で、実行回数が所定のＣＯＵＮＴより小さい場合、以下の操作を繰り返して実行する。
ｆ４１２、現在の実行計画Ｃを一時実行計画Ｗにコピーする。
ｆ４１３、Ｗに対してランダムに微小調整を行うが、ＷとＣの等価性を確保する必要がある。
ｆ４１４、ＣのエネルギーＥｃおよびＷのエネルギーＥｗ（即ち実行コスト）をそれぞれ算出する。
ｆ４１５、Ｅｃ＞Ｅｗの場合、ＷをＣおよびＢにコピーする。
ｆ４１６、Ｅｃ≦Ｅｗの場合、以下の計算を実行する。
ＴＥＳＴを０〜１のランダム値に初期化する。
ＤＥＬＴＡ＝Ｅｗ−Ｅｃ
ＲＥＳＵＬＴ＝ＥＸＰ（−ＤＥＬＴＡ／Ｔ）
ＲＥＳＵＬＴがＴＥＳＴより大きいとき、ＷをＣにコピーする。
ｆ４２、現在の温度をＴ＝Ｔ＊ＡＬＰＨＡのように降下させる。
ｆ５、実行計画ＢをＣにコピーする。
【００７９】
上記２種類のアルゴリズム以外に、最適化器は進化的アルゴリズム、発見的アルゴリズム、分岐限定法、山登り法、人工神経ネットワークまたはダイナミックプログラミングなどの技術分野のアルゴリズムを採用して、実行計画を最適化するようにしてもよい。他のアルゴリズムに基づいて初期実行計画を改善する処理過程は、ポリシーが上記２種類の方法に類似している。
【００８０】
初期実行計画に対して局所最適化を行うことにより、最適化器で選出された最適な実行計画のコストがさらに低くなることができ、文書ベースシステム全体の性能をさらに向上させる。
【００８１】
説明すべきものとして、本発明に係る解析器、計画器、最適化器、実行器および記憶操作モジュールのうち１つまたは複数のモジュールは、独立のモジュールで実現されるようにしてもよい。例えば、Ｗｉｎｄｏｗｓ（登録商標）システムにおいて、各モジュールそれぞれを単独のＤＬＬで実現するようにしてもよく、全てのモジュールを１つのＤＬＬで実現するようにしてもよい。ｌｉｎｕｘ（登録商標）システムにおいて、各モジュールそれぞれを１つのｓｏファイルで実現するようにしてもよく、全てのモジュールを１つのｓｏファイルで実現するようにしてもよい。Ｊａｖａ（登録商標）環境において、各モジュールそれぞれを１つの．ｃｌａｓｓファイルで実現するようにしてもよく、全てのモジュールを１つの．ｃｌａｓｓファイルで実現するようにしてもよい。
【００８２】
各モジュールの実現について、Ｃ、Ｃ＋＋、Ｊａｖａ、Ｐｙｔｈｏｎ、Ｒｕｂｙ、Ｐｅｒｌ、ＳｍａｌｌＴａｌｋ、Ａｄａ、Ｓｉｍｕｌａ、Ｐａｓｃａｌ、Ｈａｓｋｅｌｌなどの言語を用いて開発するようにしてもよい。
【００８３】
図３は本発明に係る文書ベースシステムの実現方法のフローチャートである。図３に示すように、本発明の実施形態に係る文書ベースシステムの実現方法は、以下のようなステップを含む。
【００８４】
ステップ３０１で、アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作からなる中間形式に解析する。
【００８５】
本ステップでは、アプリケーションによる文書ベースシステム標準インターフェースの呼び出しは、文書ベースシステムに関する基礎出願書類に説明されたＵＯＭＬであってもよく、命令列の形式であってよいが、いずれも文書ベースシステムに関する基礎出願に指摘された汎用文書モデルに適合すべきである。アプリケーションからの呼び出しに対して字句・構文解析を行って、標準インターフェース規範に適合する、汎用文書モデルのオブジェクトまたは操作を含む中間形式を生成する。ＸＭＬの場合、ＸＭＬ解析器を用いてＤＯＭツリーを生成するようにしてもよい。命令列形式の場合、用いられる命令列は一般的にＬＡＬＲ（１）文法に適合する。文法定義が与えられる場合、ｌｅｘおよびｙａｃｃで生成された字句および構文解析器を用いて命令列を解析するようにしてもよい。
【００８６】
ステップ３０２で、中間形式を、物理記憶に対する操作を含む実行計画に変換する。
【００８７】
本ステップでは、中間形式を構成する汎用文書モデルのオブジェクトまたは操作は論理操作である。これらの論理操作は比較的高い階層の概念である。１つの論理操作は、物理記憶に対する単一の操作にマッピングされることも、物理記憶に対する複数の操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。同一の中間形式について、毎回変換後の実行計画が異なることは可能である。
【００８８】
構文ツリーで表された中間形式を例として、本ステップでは、中間形式を実行計画に変換する過程は具体的に以下のようなステップを含むようにしてもよい。
【００８９】
構文ツリー内の各論理操作Ｌ＿ＯＰを列挙する。ここでの論理操作は一組の論理操作のシーケンスであってもよい。
【００９０】
Ｌ＿ＯＰに対応する物理操作集合（Ｐ＿ＯＰ１、Ｐ＿ＯＰ２、…、Ｐ＿ＯＰｍ）を取得する。ここでの各物理操作Ｐ＿ＯＰｊは一組の物理操作のシーケンスであってもよい。
【００９１】
Ｌ＿ＯＰに対してＰ＿ＯＰｉのような物理操作を選択する。
【００９２】
構文ツリー内の全ての論理操作に対して、上記手順に従って対応の物理操作を選択し、構文ツリー内の全ての論理操作が対応の物理操作に替えられると、実行計画が生成される。
【００９３】
ＤＯＭツリーおよび他の中間形式に対する変換は上記実現に類似している。
【００９４】
ステップ３０３で、変換して得られた実行計画をスケジューリングして実行する。
【００９５】
具体的に、本ステップでは、実行計画に対応するツリーのルートノードから、トップダウンで再帰し、ツリーの最下位ノードに到着すると、ボトムアップで実際の操作を実行し、実行計画全体を次第に完成する。
【００９６】
上記方法によって実現された文書ベースシステムは、各ステップ間のインターフェースが標準インターフェース規範を満たす条件で、各ステップの具体的な実現が互いに独立であるため、文書ベースシステム全体の実現に優れた拡張性、柔軟性および保守性を持たせる。
【００９７】
上記プロセスでは、ステップ３０２で変換して得られた実行計画が複数ある場合、ステップ３０２は具体的に以下のようなステップを含む。
【００９８】
ステップ３０２１で、汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に解析する。
【００９９】
中間形式を構成する汎用文書モデルのオブジェクトまたは操作は論理操作である。これらの論理操作は比較的高い階層の概念である。１つの論理操作は、単一の物理操作にマッピングされることも、複数の物理操作を含むシーケンスにマッピングされることも可能であり、しかも条件を満たすマッピングが複数でありうる。従って、単一の中間形式が複数の実行計画に対応する可能性がある。論理操作を含む中間形式に基づいて、対応の複数の実行計画をランダムに生成するようにしてもよい。
【０１００】
ステップ３０２２で、判断条件に従って複数の実行計画から最適な実行計画を選択する。
【０１０１】
上記ステップ３０２２では、判断条件に従って、生成された実行計画集合から最適な実行計画を選出するようにしてもよい。説明すべきものとして、いわゆる「最適」とは、判断条件または実際のニーズという意味から言われたものである。例えば、実行時間が最少となることを図るという判断条件で選出された最適な実行計画は、実行に必要な最大空間が大きい可能性があるため、実行に必要な最大空間が最小となることを図るという判断条件で、最適な実行計画と言えない。上記の判断条件は経験ルールであってもよく、或いは、実行計画のコストに基づく比較、即ち、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せに基づく比較であってもよい。
【０１０２】
具体的に、上記ステップ３０２２の操作過程は複数の方法で実現されるようにしてもよい。以下、例を挙げて説明する。
【０１０３】
１つは、経験ルールの優先度に基づいて最適な実行計画を選択する方法である。仮に、判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールの優先度がＲ１＞Ｒ２＞…＞ＲＬであるとすると、該方法は以下のようなステップを含む。
【０１０４】
実行計画集合を生成された全ての実行計画に設定し、現在の判断用経験ルールをＲｉ（ｉ＝１）に設定する。
【０１０５】
実行計画集合内の全ての実行計画に対して、ルールＲｉに適合するかどうかを順次に判断し、ある実行計画がルールＲｉに適合しない場合、該実行計画を標記して、該実行計画を実行計画集合から除去する。
【０１０６】
実行計画集合が空になる場合、ｂ２で標記された実行計画を実行計画集合に入れて、次のステップを実行する。ｉがＬに等しい場合、次のステップを実行し、ｉがＬに等しくない場合、ｉに１を加えて、ｂ２を繰り返して実行する。
【０１０７】
経験ルールの優先度に基づいて選択される最適な実行計画として、実行計画集合から１つの実行計画を任意に選出する。
【０１０８】
もう１つは、経験ルールの重みに基づいて最適な実行計画を選択する方法である。仮に、判断条件がＲ１，Ｒ２，…ＲＬというＬ個の経験ルールを含み、一般性を失わずに、経験ルールＲｉの重みがＰＲｉであるとすると、該方法は以下のようなステップを含む。
【０１０９】
全ての実行計画に対して、その重みを０に初期化する。
【０１１０】
各実行計画に対して、ルールＲｉ（ｉ＝１，…，Ｌ）に適合するかどうかを判断し、適合する場合、該実行計画の重みにＰＲｉを加える。
【０１１１】
各実行計画の重みに基づいて、経験ルールの重みに基づいて選択される最適な実行計画として、重みが最大となる実行計画を選出する。重みが最大となる実行計画が複数ある場合、１つを任意に選出するようにしてもよい。
【０１１２】
上記は、経験ルールに基づいて最適な実行計画を選択する２種類の方法を説明したが、以下、実行計画のコストに基づいて最適な実行計画を選択する方法を紹介する。
【０１１３】
実行計画のコストは時間コストと空間コストとを含む。時間コストとは、実行計画全体の実行にかかる時間を指すが、空間コストとは、実行過程全体で最終結果および中間結果が占用可能な最大空間を指す。このような実行にかかわるディスクＩ／Ｏ時間が時間コストの主要部分となるため、時間コストの算出も主にディスクＩ／Ｏ時間の算出である。空間コストにとって、メモリとディスクとの両方の占用にかかわる。
【０１１４】
実行計画の時間コストおよび空間コストの算出方法について、上記最適化器の実現に関する相応内容を参照してよい。
【０１１５】
上記複数の実行計画を生成して最適な実行計画を選択するステップによれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の実現方法が高い性能を持つようになる。
【０１１６】
本発明の実施形態に係る文書ベースシステムの実現方法において、ステップ３０２１とステップ３０２２との間に、対応の複数の実行計画を最適化する過程をさらに含む。該最適化過程によって、複数の局所最適化された実行計画を取得することができる。
【０１１７】
このように、ステップ３０２２は、最適化された複数の実行計画から１つの最適な実行計画を選択する。
【０１１８】
上記実行計画に対する最適化は、実行計画のコストまたは他のメトリック値をメトリック関数として、遺伝的アルゴリズムにおける適応度や、焼きなまし法におけるエネルギーのような知能アルゴリズムにおけるメトリック値と関連付け、これらのアルゴリズムを用いて実行計画空間に対して空間探索を行って、局所最適化された実行計画を得ることを根本とする。
【０１１９】
実行計画を最適化する方法は、遺伝的アルゴリズムや、焼きなまし法などを含む。この２種類の方法の具体的なステップについて、最適化器に関する相応内容の説明を参照する。
【０１２０】
上記説明された２種類のアルゴリズム以外に、進化的アルゴリズム、発見的アルゴリズム、分岐限定法、山登り法、人工神経ネットワークまたはダイナミックプログラミングなどの技術分野のアルゴリズムを採用して、実行計画を最適化するようにしてもよい。他のアルゴリズムに基づいて初期実行計画を改善する方法は、ポリシーが上記２種類の方法に類似している。
【０１２１】
初期実行計画に対して局所最適化を行うステップによれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能がさらに向上する。
【０１２２】
要するに、本発明に係る文書ベースシステムおよびその実現方法では、文書ベースシステムの実現が複数の層に分けられる。異なる層の実現が相対的に独立することができるため、本発明に係る文書ベースシステムは、拡張性、柔軟性および保守性を持つ。本発明に係る最適化器および相応の最適化アルゴリズムによれば、複数の実行計画から１つの最適な実行計画を選出することができ、実行の性能を向上させるため、文書ベースシステム全体の性能を向上させる。初期実行計画に対する局所最適化によれば、選出された最適な実行計画のコストがさらに低くなり、文書ベースシステム全体の性能をさらに向上させ、文書ベースシステム全体の実現に高い性能を持たせる。
【０１２３】
上記は本発明の好ましい具体的な実施形態にすぎないが、本発明の保護範囲はこれに限られない。本発明に掲げる技術範囲内で、いかなる当業者が容易に想到できる変更または置換えは、全て本発明の保護範囲内に含まれるべきである。そのため、本発明の保護範囲は、特許請求の範囲の保護範囲に準すべきである。
【特許請求の範囲】
【請求項１】
文書ベースシステムであって、
アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析する解析器と、
前記中間形式を、物理記憶に対する操作を含む実行計画に変換する計画器と、
前記実行計画を実行することにより、記憶操作モジュールをスケジューリングして、前記実行計画内の物理記憶に対する操作を実行する実行器と、
前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する記憶操作モジュールと、
を含むことを特徴とする文書ベースシステム。
【請求項２】
判断条件に従って複数の実行計画から１つの最適な実行計画を選択する最適化器をさらに含むことを特徴とする請求項１に記載の文書ベースシステム。
【請求項３】
前記最適化器が、さらに前記実行計画を最適化することを特徴とする請求項２に記載の文書ベースシステム。
【請求項４】
前記最適化が、実行計画の空間を探索し、前記判断条件に従って、最適化された実行計画を取得することを含むことを特徴とする請求項３に記載の文書ベースシステム。
【請求項５】
前記実行計画を最適化するためのアルゴリズムが、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せを含むことを特徴とする請求項３に記載の文書ベースシステム。
【請求項６】
前記判断条件が、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含むことを特徴とする請求項２〜５のいずれか１項に記載の文書ベースシステム。
【請求項７】
前記アプリケーションからの呼び出しの標準インターフェースが、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式であることを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項８】
前記中間形式が、構文ツリーまたは文書オブジェクトモデルツリーを含むことを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項９】
前記物理記憶に対する操作が、論理パーティション、物理ディスク、仮想記憶、メモリを含む１種または複数種の物理記憶に対する操作を含むことを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項１０】
前記仮想記憶がリモート記憶またはネットワーク記憶を含み、前記リモート記憶がネットワークファイルシステムまたは分散ファイルシステムを含み、前記ネットワーク記憶がストレージエリアネットワーク、グリッド、またはピアツーピア方式の記憶を含むことを特徴とする請求項９に記載の文書ベースシステム。
【請求項１１】
文書ベースシステムの実現方法であって、
アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析するステップと、
中間形式を、物理記憶に対する操作を含む実行計画に変換するステップと、
前記実行計画をスケジューリングして実行するステップと、
を含むことを特徴とする方法。
【請求項１２】
前記中間形式を実行計画に変換するステップが、
汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に変換するステップと、
判断条件に従って複数の実行計画から１つの最適な実行計画を選択するステップと、
を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択する前に、生成された実行計画を最適化することをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記生成された実行計画を最適化することが、実行計画の空間を探索し、前記判断条件に従って、最適化された実行計画を取得することを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記生成された実行計画を最適化することが、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せに基づいて最適化することを含むことを特徴とする請求項１３に記載の方法。
【請求項１６】
前記判断条件が、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含むことを特徴とする請求項１２〜１５のいずれか１項に記載の方法。
【請求項１７】
前記判断条件が、経験ルールを含み、
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択することが、経験ルール優先度アルゴリズムまたは経験ルール重みアルゴリズムに基づいて、複数の実行計画から１つの最適な実行計画を選択することを含む、
ことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記アプリケーションからの呼び出しが、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式であることを特徴とする請求項１１〜１５のいずれか１項に記載の方法。
【請求項１９】
前記中間形式が、構文ツリーまたは文書オブジェクトモデルツリーを含むことを特徴とする請求項１１〜１５のいずれか１項に記載の方法。
【請求項１】
文書ベースシステムであって、
アプリケーションから受信された呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析する解析器と、
前記中間形式を、物理記憶に対する操作を含む実行計画に変換する計画器と、
前記実行計画を実行することにより、記憶操作モジュールをスケジューリングして、前記実行計画内の物理記憶に対する操作を実行する実行器と、
前記実行器のスケジューリングで、前記物理記憶に対する操作を実行する記憶操作モジュールと、
を含むことを特徴とする文書ベースシステム。
【請求項２】
判断条件に従って複数の実行計画から１つの最適な実行計画を選択する最適化器をさらに含むことを特徴とする請求項１に記載の文書ベースシステム。
【請求項３】
前記最適化器が、さらに前記実行計画を最適化することを特徴とする請求項２に記載の文書ベースシステム。
【請求項４】
前記最適化が、実行計画の空間を探索し、前記判断条件に従って、最適化された実行計画を取得することを含むことを特徴とする請求項３に記載の文書ベースシステム。
【請求項５】
前記実行計画を最適化するためのアルゴリズムが、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せを含むことを特徴とする請求項３に記載の文書ベースシステム。
【請求項６】
前記判断条件が、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含むことを特徴とする請求項２〜５のいずれか１項に記載の文書ベースシステム。
【請求項７】
前記アプリケーションからの呼び出しの標準インターフェースが、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式であることを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項８】
前記中間形式が、構文ツリーまたは文書オブジェクトモデルツリーを含むことを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項９】
前記物理記憶に対する操作が、論理パーティション、物理ディスク、仮想記憶、メモリを含む１種または複数種の物理記憶に対する操作を含むことを特徴とする請求項１〜５のいずれか１項に記載の文書ベースシステム。
【請求項１０】
前記仮想記憶がリモート記憶またはネットワーク記憶を含み、前記リモート記憶がネットワークファイルシステムまたは分散ファイルシステムを含み、前記ネットワーク記憶がストレージエリアネットワーク、グリッド、またはピアツーピア方式の記憶を含むことを特徴とする請求項９に記載の文書ベースシステム。
【請求項１１】
文書ベースシステムの実現方法であって、
アプリケーションからの呼び出しを、汎用文書モデルのオブジェクトまたは操作を含む中間形式に解析するステップと、
中間形式を、物理記憶に対する操作を含む実行計画に変換するステップと、
前記実行計画をスケジューリングして実行するステップと、
を含むことを特徴とする方法。
【請求項１２】
前記中間形式を実行計画に変換するステップが、
汎用文書モデルのオブジェクトまたは操作を含む中間形式を、対応の複数の実行計画に変換するステップと、
判断条件に従って複数の実行計画から１つの最適な実行計画を選択するステップと、
を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択する前に、生成された実行計画を最適化することをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記生成された実行計画を最適化することが、実行計画の空間を探索し、前記判断条件に従って、最適化された実行計画を取得することを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記生成された実行計画を最適化することが、遺伝的アルゴリズム、進化的アルゴリズム、焼きなまし法、分岐限定法、山登り法、発見的アルゴリズム、人工神経ネットワークアルゴリズム、ダイナミックプログラミングアルゴリズムのうち１つまたは任意の組合せに基づいて最適化することを含むことを特徴とする請求項１３に記載の方法。
【請求項１６】
前記判断条件が、経験ルール、或いは、実行計画の時間コスト、空間コスト、または時間コストと空間コストとの組合せを含むことを特徴とする請求項１２〜１５のいずれか１項に記載の方法。
【請求項１７】
前記判断条件が、経験ルールを含み、
前記判断条件に従って複数の実行計画から１つの最適な実行計画を選択することが、経験ルール優先度アルゴリズムまたは経験ルール重みアルゴリズムに基づいて、複数の実行計画から１つの最適な実行計画を選択することを含む、
ことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記アプリケーションからの呼び出しが、ＸＭＬ形式、またはＬＡＬＲ文法に適合するカスタマイズ形式であることを特徴とする請求項１１〜１５のいずれか１項に記載の方法。
【請求項１９】
前記中間形式が、構文ツリーまたは文書オブジェクトモデルツリーを含むことを特徴とする請求項１１〜１５のいずれか１項に記載の方法。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２０１０−５０１９４８（Ｐ２０１０−５０１９４８Ａ）
【公表日】平成２２年１月２１日（２０１０．１．２１）
【国際特許分類】
【出願番号】特願２００９−５２５９０２（Ｐ２００９−５２５９０２）
【出願日】平成１９年８月１４日（２００７．８．１４）
【国際出願番号】ＰＣＴ／ＣＮ２００７／０７０４７６
【国際公開番号】ＷＯ２００８／０２５２８１
【国際公開日】平成２０年３月６日（２００８．３．６）
【出願人】（５０８１６６４１９）サーセン コーポレイション (5)
【Ｆターム（参考）】
【公表日】平成２２年１月２１日（２０１０．１．２１）
【国際特許分類】
【出願日】平成１９年８月１４日（２００７．８．１４）
【国際出願番号】ＰＣＴ／ＣＮ２００７／０７０４７６
【国際公開番号】ＷＯ２００８／０２５２８１
【国際公開日】平成２０年３月６日（２００８．３．６）
【出願人】（５０８１６６４１９）サーセン コーポレイション (5)
【Ｆターム（参考）】
[ Back to top ]