(57)【特許請求の範囲】
【請求項１】
メモリを備え、該メモリ内の１セットのロケーションがキャッシュを形成し、該キャッシュは、１つまたはそれ以上の意味論的領域から成る１セットの各々について、コンテンツを含んでおり、該コンテンツは１つまたはそれ以上のデータアイテムを含んでいるシステムを用いて、問い合わせに対する応答を得る方法であって、
（ａ）問合せＱを得ること、
（ｂ）前記問合せＱを用いて問合せシグネチャＳQを得ること、及び
（ｃ）前記問合せシグネチャＳQと少なくとも１つの前記意味論的領域についての領域シグネチャＳRとを用いて、前記問合せＱに対し、１つの前記意味論的領域のコンテンツから少なくとも１つのデータアイテムを含む応答を得ること、から成り、
前記キャッシュは各意味論的領域について更に前記領域シグネチャＳRを包含し、
前記ステップ（ｃ）が、
（ｃ３）任意の意味論的領域についてＳQ＝ＳRかどうかを決定し、
そうでない場合には、任意の意味論的領域についてＳQ∩ＳR＝ＳRかどうかを決定し、
そうでない場合には、任意の意味論的領域について｜ＳQ∩ＳR｜≧｜ＳR｜−ｋかどうかを決定すること（ｋは項シグネチャのビット１の数）、及び
（ｃ４）もし前記（ｃ３）が１領域についてＳQ＝ＳRと決定したならば、その領域のコンテンツを問合せＱに対する応答として得ること、
もし前記（ｃ３）が１つ又はそれ以上の領域についてＳQ∩ＳR＝ＳRと決定したならば、１つの領域のコンテンツにおいて前記問合せＱにマッチするデータアイテムを含む応答を得ること、
もし前記（ｃ３）が１つ又はそれ以上の領域について｜ＳQ∩ＳR｜≧｜ＳR｜−ｋと決定したならば、少なくとも１つの前記意味論的領域の中のサブセット（部分セット）のコンテンツからデータアイテムを含む応答を得ること、
から成ることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、オンライン情報検索システム（たとえば、インターネット／ＷＷＷ、イントラネット）、より詳細にはシグネチャ・ファイルをベースとする、問合せの意味論的キャッシング(semantic caching)に関するものである。
【０００２】
【従来の技術】
Tavakoli, N.およびRay, A. の論文“A New Signature Approach for Retrieval of Documents from Free-Text Databases”, Information Processing & Management, Vol. 28, No.2, 1992, pp. 153-163 は、情報検索のシグネチャー手法を述べている。その手法では、シグネチャ・ファイルのサイズはアルファベットの固有記号の数によって決まる。
【０００３】
クライアント・サーバー情報システムでは、データーをキャッシュし、そしてサーバーとの将来の対話を最小限度にするため、主としてローカルクライアント・メモリが使用されている。このデーター・キャッシングは、応答を引き渡す際にネットワーク通信量と低速サーバーが長い遅延を引き起こすことがあるウェブに対し特別な重要性を有する。標準ページをベースとするキャッシングはウェブに対して技術的に実施不可能であり、また組（tuple）をベースとするキャッシングは一定の制限を有するので、考えられる将来の再使用のためユーザー問合せと応答をキャッシュすることに大きな努力が払われてきた。そのような技法は、たとえばGodfrey, P., およびGryz, J., の論文“Semantic  Query  Caching for Heterogeneous Databases”, in Proceedings of the 4th KRDB Workshop, Athens, Greece, 30-August-1997,  pp. 6-1 to 6-6 に記載されている。
【０００４】
問合せキャッシングは、たとえばキーワードを加えたり、または除去することによって、ユーザーがかなり頻繁に問合せを改良する場合に特別な利点を有する。このケースでは、応答の組の多くはそれまでにキャッシュすることができるので、直ちにユーザーへ引き渡すことができる。
【０００５】
ウェブをベースとする問合せシステムは、異種分配型(heterogeneous distributed)データ・リポジトリに接触し、いわゆるラッパー(wrappers) を呼び出してユーザー問合せを目標の問合せ言語へ変換し、サーバーからのデータ・フローを管理する。データーは通例ＨＴＭＬフォーマットでネットワークを通じて転送されるので、最終応答がユーザーに報告される（そしてキャッシュに記憶される）前に、ラッパーも検索したＨＭＴＬファイルから応答の組を抽出する。
【０００６】
典型的なウェブ問合せは、項(term)の論理積(conjunction)である。問合せ内の各項はおそらく演算子 NOTで否定されたキーワードであり、１つまたはそれ以上の属性（題名、著者、等）に付けられる。ほとんどのウェブ・サーバーでは、演算子 NOTは ＡＮＤ  ＮＯＴと同じであり、問合せは少なくとも１個の非否定項を含むことが強制される。
【０００７】
意味論的キャッシングはクライアントキャッシュを意味論的領域(semantic region)の集まりとして管理することができる。すなわち、意味論的領域の単位でアクセス情報が管理され、キャッシュ置換が実行される。そのような技法は、Dar, S., Franklin, M. J., Jonsson, B.T., およびTan, M.の論文 “Semantic Data Caching and Replacement”, in Proceedings of the 22th VLDB Conference, Mumbai (Bombay), India, 1996, pp. 330-341 に記載されている。意味論的領域は、たとえばユーザー問合せによって扱われる意味的に関係があるドキュメントをグループに分ける。
【０００８】
意味論的キャッシングの解決法では、各意味論的領域は、そのコンテンツを記述する制約論理式、コンテンツ内の組(tuple)のカウンタ、キャッシュ内の実際の組の集合のためのポインタ、および置換戦略によって領域をランク付けするため使用される追加情報を有することができる。問合せと同様、すべての領域論理式は項の論理積である。
【０００９】
クライアントで問合せが出されると、問合せは２つの別個の部分、（１）ローカルキャッシュ内で入手できる応答の部分と（２）サーバーからの応答に欠けているすべての組を検索する残りの問合せに分けられる。もし残りの問合せがヌルでなければ（すなわち、問合せはキャッシュされない情報空間の部分を取り扱う）、残りの問合せはサーバーへ送られ、そこで処理される。
【００１０】
【発明が解決しようとする課題】
問合せキャッシングの多くの重要な原理について説明したが、どれもキャッシュ項に対する問合せ評価のための効率的な方法を提供していない。さらに、一部の技法においては、問合せ評価はコンピュータの使用が難しいデータログ問合せ評価になっている。
【００１１】
【課題を解決しようとする手段】
本発明は、プロセッサとメモリを備え、前記メモリ内の複数の所定ロケーションがキャッシュを形成し、前記キャッシュが１つまたはそれ以上の意味論的領域から成る情報処理システムにおいて実施する方法であって、（ａ）対応する問合せシグネチャＳQをもつ問合せＱを受け取ること、（ｂ）前記問合せシグネチャＳQに頼って、前記問合せＱに対応する応答として前記１つまたはそれ以上の前記領域のコンテンツを戻すこと、の諸ステップから成る方法を提供する。
【００１２】
本発明は、さらに、プロセッサとメモリを備え、前記プロセッサはメモリに結合され、そして前記メモリと協力して前記方法の諸ステップに対応する命令を実行するように動作することができるプログラム可能な情報処理システムであって、上記の方法を実施するため適切にプログラムされた場合の情報処理システムを提供する。
【００１３】
本発明は、ウェブ問合せをキャッシュする新しいメカニズムを提供する。そのメカニズムは、いわゆるシグネチャ・ファイルに基づいており、キャッシュ項の数に比例する効率的な問合せ評価を考慮に入れている。本発明の実施例に従って、キャッシュ内の各意味論的領域はシグネチャに関連付けられている。ユーザー問合せの場合、シグネチャは同様な仕方で作られ、キャッシュに保存されている領域シグネチャに対し確かめられる。提案したキャッシング・メカニズムは問合せに適格とされたすべてのキャッシュ項を識別する手続きを含む。すなわち、手続きはどのキャッシュ項を直ちに再使用できるか、そしてサーバーから欠けているどの情報を要求しなければならないかを検出する。
【００１４】
このメカニズムは３つの長所を有する。第１に、このメカニズムは、１）問合せがキャッシュに含まれているとき、または２）問合せが幾つかの領域を共有するとき、２つの重要なケースを同じ洗練されたやり方で処理する。その結果、提案したメカニズムは組複製物(tuple duplications)のほとんどのケースを回避し、適度な記憶装置要求を有する。第２に、このメカニズムは部分応答の効率的な報告と、問合せの残りの効率的な生成をサポートする。最後に、このメカニズムは領域合体および置換方針のための簡単な解決法を提供する。
【００１５】
【発明の実施の形態】
本発明が通常のコンピュータ・ネットワーク技術を使用してイントラネットによって、またはより適切にインターネットによって実施できることは理解されるであろう。本発明はインターネットを通じてクロスプラットフォーム通信とドキュメント転送を行う通常のＷＷＷウェブ・ブラウザ・ソフトウェア（たとえば、Netscape）を使用して実施することができる。図１は、このやり方を示す。ネットワーク２１の一部を構成する各マシン２２，２４，２６は、この分野で周知のWindows で動作するＰＣ、MacOSで動作するMac 、またはUNIXで動作するマイクロコンピュータでもよいことは理解されるであろう。しかし、異なるシステム構成（たとえばヨーロッパ特許出願公開ＥＰ−Ａ−７７２，８５７号、米国特許第５，６９２，０７３号）を使用して本発明を実施できることは理解されるであろう。
【００１６】
マシン２２におけるユーザーの要求に応じて、マシン２６に保存されたドキュメントまたは他の情報（たとえば問合せに対する応答）を検索し、インターネットを通じてマシン２６から幾つかの中間マシン２４を経由してマシン２２へ送ることができる。周知のように、ドキュメントは、固有の識別子として、たとえば検索エンジンへの適当な問合せ入力を用いて得たWorld Wide Web URLを使用して検索することができる。
【００１７】
シグネチャ・ファイルはそもそも問合せワードを含むフルテキスト断片を検索するため計画されたものである。最も広く知られているスーパーインポーズ・コーディングによって、各意味論的領域(semantic region)は論理積形式で論理式と関連付けられる。領域論理式内の各項は１と０の２進シーケンスである項シグネチャが割り当てられる。領域シグネチャは、領域論理式から生成されたすべての項シグネチャをスーパーインポーズ（ビット状ＯＲ演算）することによって生成される。
【００１８】
図２は領域シグネチャの構造を示し、図３は問合せのサンプルとそれらのシグネチャを示す。
【００１９】
図２は意味論的領域“問合せ∧キャッシング”に関するシグネチャの生成を示す。同様に論理積であるユーザー問合せの場合は、すべての項がシグネチャと関連付けられ、キャッシュ領域と同様なやり方でスーパーインポーズされ、問合せシグネチャが生成される。その後、問合せシグネチャはイグネチャ・ファイル内の各領域シグネチャと突き合わされ、部分応答を得て、問合せの残り(query remainder)が作られる。
【００２０】
ここで述べる２つの異なるキャッシング技法は意味論的領域と問合せ間の異なる意味論的関係を取り扱う。第１のキャッシング技法は一方が他方を含んでいる場合に、問合せと意味論的領域との意味論的包含関係(semantic containment)をうまく処理する。第２のキャッシング技法は、領域が問合せを含んでいない場合または問合せが領域を含んでいない場合に、処理を意味論的ＡＮＤ演算(semantic intersection)のより頻度の高い、複雑なケースへ拡張する。
【００２１】
３つのケースから成る意味論的包含関係から始める。もし論理式が同等であれば、問合せＱは領域Ｒと同等である。もし１つまたはそれ以上の項を落とすことによって問合せ論理式から領域論理式を得ることができれば、領域Ｒは問合せＱを含んでいる。このケースの場合、問合せに対する応答は領域コンテンツの適当なサブセットである。逆に、もし１つまたはそれ以上の項を落とすことによって領域論理式から問合せ論理式を得ることができれば、意味論的領域Ｒは問合せＱに含まれる。さらに、領域包含は応答が領域コンテンツのサブセットであることを意味する。上に述べた３つのケースのいずれにおいても、領域Ｒは問合せＱに適格とされる。
【００２２】
ＳQとＳRはそれぞれ問合せシグネチャと領域シグネチャを表す。意味論的包含関係は、シグネチャのビット状比較によって以下のように検出される。
領域包含（ＳQ⊂ＳR）：  １に設定された問合せシグネチャ内の各ビットについて、領域シグネチャ内の対応するビットも同様に１に設定される（図３の問合せ２）。
同等（ＳQ＝ＳR）：  領域シグネチャと問合せシグネチャは１に設定された同じビットを有する（図３の問合せ３）。
問合せ包含（ＳQ⊃ＳR）：  １に設定された領域シグネチャ内の各ビットについて、問合せシグネチャ内の対応するビットも同様に１に設定される（図３の問合せ４）。
【００２３】
シグネチャ・ファイルは問合せに適格とされないほとんどの領域（全部ではない）を除去する。図３の最後の問合せは誤り選択（false drop）である。誤り選択は、そのシグネチャは問合せに適格とされるが、領域には適格とされない意味論的領域である。実際には、もし用語“スキー”と“リゾート”にそれぞれシグネチャ“０１１０  ００００  １０００”と“００００  ０１１０  ０００１”を割り当てれば、問合せ“スキー∧リゾート”のシグネチャは“０１１０  ０１１０  １００１”であり、従って、領域“問合せ∧キャッシング”のシグネチャと同等である。
【００２４】
誤り選択は問合せと領域を詳しく比較することによって除去されるが、もし誤り選択が多ければ、性能は低下する。誤り選択の確率を最小限にするために、シグネチャ内の０と１の予想数を同じにしなければならない。そうすれば、領域または問合せ論理式内の同数の別個のキーワードの場合、シグネチャの長さが増加すると、シグネチャ内の１の密度が減少し、それに応じて、誤り選択をする機会が減少するであろう。しかし、それにより、記憶装置オーバーヘッドは増加するであろう。もしシグネチャの長さがＦビットで、問合せ内の項の最大限の数がｔであれば、項シグネチャ内の１に設定されたビットの最適の数kopt （一様な確率分布に従って）は、
kopt=(F・ln2)/t    (1)
である。
【００２５】
キャッシュ編成  問合せをより迅速に処理するため、本発明の実施例によるキャッシュ・アーキテクチャは領域コンテンツとは別個に領域シグネチャを保有する（図４参照）。シグネチャ部内の各エントリ(領域)は、シグネチャのほかに、領域論理式、組(tuple)のカウンタ、対応する領域コンテンツへのリンク、および置換関数の値を含んでいる。適格とされた領域はシグネチャ部内で検出される。意味論的領域が完全または部分応答に適格とされたら、領域コンテンツに保存された問合せとマッチする（ぴったり合う）組がユーザーに報告される。
【００２６】
否定  すべての領域論理式は、キーワードのほかに、それらの否定を含んでいる。否定をもつ問合せを円滑に処理するために、キーワードのシグネチャとその否定のシグネチャを関連付けることができる。否定項に基本的な項シグネチャのビット状否定であるシグネチャを割り当てることができるが、項シグネチャ内の１に設定されたビットの数kはシグネチャの長さFよりかなり小さいので、これにより、否定項シグネチャの中に１に設定されたF−kビットが生じるであろう。従って、この解決法は、論理式が否定項を含むどの領域においても誤り選択の確率を著しく増加させるであろう。この問題が起きるのを避けるため、キーワードとその否定（および割り当てられたそれらのシグネチャ）はどのシグネチャにおいても１に設定されたkビットをもつ２つの独立項として扱われる。
【００２７】
第１の技法は、意味論的包含関係の３つのケース、すなわち(1) 同等、(2) 問合せ包含、および(3) 領域包含を処理する。もし問合せがキャッシュ内の領域と同等であれば、問合せ応答は領域コンテンツと一致する。もし領域が問合せを含んでいれば、フィルタとして使用した問合せ論理式を用いて、領域コンテンツから完全応答を生成することができる。さらに、もし２つまたはそれ以上の領域が問合せを含んでいれば、それらの領域はどれも応答を生成することができる。フィルタリング・オーバーヘッドを減らすために、アルゴリズムは領域のコンテンツが最小限の数の組をもつ領域を選択し、フィルタする。領域包含のケースでは、アルゴリズムは領域コンテンツから部分応答を抽出し、サーバーヘ送る問合せの残りを生成する。もし問合せに数個の領域が含まれていれば、それらのどれかまたはすべてが部分応答を生成することができる。そのような領域の数が大きいことがあるので、アルゴリズムは最大限の数の組をもつ上位m個の領域を選択する。
【００２８】
もし意味論的包含が検出されなければ、そのキャッシュは使用されず、問合せはサーバーへ送られる。応答を受け取ると、問合せに対応する新しいキャッシュ領域が生成される。もしキャッシュがその領域のための自由空間を持っていなければ、アルゴリズムは将来ほとんど使用する価値のない１つまたは数個の領域をキャッシュから廃棄しなければならない。基本的な置換戦略として、LRU（least recently used ）法を使用する。この戦略は、探索がナビゲーションおよび発見に結びついており、また新しい問合せが前の問合せの改良であることが多いウェブに適している。
【００２９】
上に述べたアルゴリズムのフレームワークに関して、３つの重要な問題は、より詳しい分析、すなわち領域の残り(query remainder)の作成、領域合体(resion coalescing)、およびキャッシュ領域置換(cache region replacement)を必要とする。
【００３０】
問合せにm個の意味論的領域R1，  ．．．，Ｒmが含まれていると仮定する。問合せの残りは、Ｑr＝Ｑ−Ｒ1−．．．−Ｒm＝Ｑ∧¬Ｒ1∧．．．∧¬Ｒmとして作ることができるが、そのような制約論理式は、単純化すると、論理和（disjunction）を含むことがあり、論理積の問合せだけを受け取るサーバーを考慮に入れることができない。たとえば、問合せaと領域ａ∧ｂ∧ｃの場合（キーワードを示すため、アルファベットの始めから文字が使用される）、制約論理式ａ−ａ∧ｂ∧ｃは以下の論理和論理式になる。
ａ−ａ∧ｂ∧ｃ＝ａ∧¬（ａ∧ｂ∧ｃ）＝ａ∧¬ｂ∨ａ∧¬ｃ
【００３１】
問合せの残りを論理和形にする領域とそうしない領域とを区別するために、問合せ論理式と領域論理式との差の尺度を導入する必要がある。差は問合せに存在しない領域論理式内の項の数として定義される。この定義により、Ｒ1，．．．，Ｒmの集合はグループ（グループ内のすべての領域は問合せとＩ項差（I＝１，２，．．．．）をもつ）に分けられる。上記例の場合、領域論理式ａ∧ｂ∧ｃは問合せａと２項差を有する。Ｉ＝０のケースも可能であり、問合せと領域が同等であるとき、あるいは領域が問合せを含んでいるとき、従って問合せの残りがヌルであるとき、Ｉ＝０のケースが現れることに注目されたい。
【００３２】
差の尺度の助けを借りて、１項差をもつ領域は問合せの残りの論理積形を保つことができ、以下のことが当てはまる。
結果１（残りの構造）  キャッシュはｍ個の領域（論理式は問合せＱの論理式と１項差たとえばａ1，ａ2，．．．，ａmを有する）を含んでいると仮定する。問合せの残りＱrはＱ∧¬ａ1∧¬ａ2∧．．．∧¬ａmである。
【００３３】
図５は、意味論的包含のケース、すなわち（ａ）単一領域包含、（ｂ）複数領域包含、（ｃ）単一問合せ包含、および（ｄ）複数数問合せ包含を示す。
【００３４】
問合せ包含と同等のケースでは、問合せの残りはヌルである。従って、問合せは局部的に処理され、キャッシュのコンテンツは不変である。問合せ応答を与える領域は対応する置換値を更新する（以下参照）。
【００３５】
領域包含のケースでは、問合せの残りはヌルでなく、さらに、意味論的領域Ｒに対する補数(complement)である（図５（ａ）参照）。問合せの残りＱrに対する応答を受け取ったとき、その応答をキャッシュに加える２つの方式がある。非合体戦略では、問合せの残りのため新しいキャッシュ領域が生成される。合体戦略では、新しい領域は追加されない。代わりに、残りに対する応答を用いて領域Ｒのコンテンツが拡張され、領域論理式ＲはＱで置き換えられる。上記２つの方式は組を保存するため同じキャッシュ空間を占有するが、非合体戦略が２つの領域を使用するのに対し、合体戦略は１つの領域のみを使用するので、合体戦略のほうが好ましい。
【００３６】
もしｍ個の意味論的領域Ｒ1，．．．，Ｒmが領域包含を生じさせれば（図５（b）参照）、合体戦略の利点はいっそう大きい。問合せの残りＱr＝Q−R1−．．．−Ｒmは領域の合体(union)に対する補数（complement）であり、合体戦略は、領域Ｒ1，．．．，Ｒmと問合せの残りの代わりに、１つの領域（論理式Ｑと共に）のみを保有するであろう。領域Ｒ1，．．．，Ｒmは組の複製物(tuple duplications)を含むことがあるので、合体戦略はキャッシュのシグネチャ部とコンテンツ部の両方で記憶域をより上手に利用する。
【００３７】
キャッシュのサイズは制限されているので、空間を新しい領域に解放するためキャッシュはＬＲＵ領域を廃棄することができる。キャッシュ内の組のページを置き換えるために計画された標準ＬＲＵ法は同じサイズのことを指しており、１ページまたは１組が置換単位であり、それは問合せとマッチすることもあり、ないこともある。
【００３８】
問合せキャッシングの場合は、状況が違っている。もし領域Ｒが問合せに適格とされれば、応答内の領域の掛かり合い(involvement)は異なることがある。もし問合せが領域を含んでいれば（図５（ａ）参照）、領域コンテンツからのすべての組が応答に現れるので、領域コンテンツは完全に応答と関係がある。対照的に、もし領域が問合せを含んでいれば（図５（ｃ）参照）、領域の組の一部のみが問合せとマッチするので、領域の掛かり合いは部分的である。
【００３９】
従って、置換関数は問合せ応答内の領域の掛かり合いを考慮に入れなければならない。もし領域の掛かり合いが完全であれば、問合せ応答がサーバーから送られるときのケースのように、領域の新しい置換値は“最新値”である。もし領域の掛かり合いが部分的であり、かつ領域コンテンツ内に問合せとぴったり合わない組が存在すれば、“最新値”への置換値の変更はぴったり合った組の部分がどのくらいの大きさかによって決まる。「領域の掛かり合い」はｐ＝ＴR／Ｔとして測定することができる。ここで、ＴRは問合せ応答に現れた組の数であり、ＴRは領域コンテンツ内の組の総数である。
【００４０】
一般性を失わずに、「最新値」Ｖtopは新しい問合せが出されるたびに１だけ増加されると仮定する。もし領域Ｒの現在の置換値がＶR（ＶR<Ｖtop）で、領域の掛かり合いがｐであれば、新しい置換関数は、ＶR＝ＶR＋（Ｖtop−ＶR）ｐとして計算される。もしｐ＝１であれば、ＶR＝Ｖtopである。もしｐ＝１／２であれば、ＶR＝（Ｖtop＋ＶR）／２である。この置換関数は、問合せに適格とされた、そして適格とされないキャッシュ内のどの領域にも実施できることに留意されたい。もし領域が問合せに適格とされなければ、従って、掛かり合いｐ＝０であれば、領域置換値は変わらない。
【００４１】
例１
図6は、領域合体の例、すなわち（ａ）問合せＱ＝ｄが出される、（ｂ）問合せ後、合体した領域、（ｃ）問合せｂ∧ｄ∧ｆが出される、および（ｄ）問合せ後、更新された領域を示す。
【００４２】
キャッシュはａ∧ｂ∧ｃとｂ∧ｄとｄ∧¬ａをもつ３つの領域を含んでいる。図６（ａ）は、置換値をもつ領域を示す（Ｖtop＝６と仮定して）。新しい問合せはｄであると仮定する。第２および第３の領域は領域包含関係を生じさせる。２つの領域論理式は１ワードだけ（第２領域ではｂ、第３領域では¬ａ）問合せ論理式と違っているので、生成された問合せの残りはｄ∧ａ∧¬ｂになるであろう。完全応答が生成された後、第２および第３領域と問合せの残りは論理式ｄをもつ１つの領域で置き換えられる（図５（ｂ））。その置換値はＶtop＝７である。
【００４３】
ここで、問合せはｂ∧ｄ∧ｆであると仮定する（図６（ｃ）参照）。２つの領域ｂ∧ｄとｄ∧¬ａは問合せを含んでいる。前者はコンテンツ内により少ない組を有するので、問合せに対し応答するため前者が選ばれる。その置換値は、領域コンテンツ内の問合せとぴってり合う組の部分に従って更新される（３から４へ）。
【００４４】
キャッシング・アルゴリズム（１）
図７〜９は第１の技法に従ってキャッシングを実施する処理ステップを示す。
入力．  意味論的領域をもつキャッシュと問合せＱ
出力．  Ｑに対する応答と更新したキャッシュ
１．  キャッシュ内のすべての領域シグネチャと対比して問合せシグネチャを確かめる（ステップｓ１，ｓ２）。
２．  ＳQ＝ＳR：  もし論理式が問合せと同等である領域が存在すれば、領域コンテンツを問合せ応答として戻す。領域の置換関数値を更新し、終了する（ステップｓ３，ｓ４）。
３．  ＳQ⊃ＳR：  もし１つまたはそれ以上の領域が問合せを含んでいれば、最小限の基数をもつ領域を選択する。領域コンテンツ内の組を走査し、問合せとマッチする組を戻す。領域の置換関数値を更新し、終了する（ステップｓ１２〜ｓ１５）。
４．  ＳQ⊂ＳR：  もし幾つかの領域が問合せを含んでいれば、最大限の基数をもつ上位ｍ個の領域Ｒ1，．．．，Ｒmを選択する。領域Ｒ1，．．．，Ｒmの領域コンテンツからすべての組を戻し、複製物を廃棄する（ステップｓ５〜ｓ１１）。以下に述べるように問合せの残りを作る（ステップｓ７１〜ｓ７７；図８）：
・問合せの残りを問合せＱに設定する（ステップｓ７１）。
・各領域Ｒiについて、領域包含を規定し、領域論理式と問合せとの差を計算する（ステップｓ７３）。もし差が１項ａiだけであれば、¬ａiをもつ問合せの残りを拘束する。その問合せの残りをサーバーへ送る。応答を受け取った後、領域Ｒ1，．．．，Ｒmを１つの領域Ｑで置き換える。Ｑの置換値としてＶtopを置き、終了する。
５．  もしそうでなければ（ステップｓ１６〜ｓ２０；図９）、問合せＱをサーバーへ送る。応答を受け取ったら、Ｑのためキャッシュ内に新しい領域を生成する。その領域に空間を解放するため、問合せＱがキャッシュに適合するまで、最小の置換値をもつ領域を除去する。
【００４５】
前節で述べたキャッシング技法は意味論的包含関係(semantic containment)のケースを効率的に処理する。しかし、意味論的領域が応答の一部を生成できるが問合せを含んでいないし、また問合せに含まれていない場合には、前記技法は意味論的ＡＮＤ演算(semantic intersection)のより頻度の高い、より複雑なケースをうまく処理しない。
【００４６】
図１０は、意味論的ＡＮＤ演算の例を示す。
例２．キャッシュは論理式“∧問合せ”をもつ領域Ｒ１を含んでおり、問合せＱは“最適な∧問合せ”であると仮定する（図１０（ａ）参照）。論理式“最適な∧問合せ∧キャッシング”とマッチする領域コンテンツ内の組は問合せとマッチするけれども、包含関係が存在しないので、アルゴリズム１はＲ1を部分応答に利用しない。さらに，アルゴリズム１はサーバーから問合せＱに対する応答を受け取ると、同じ論理式“最適な∧問合せ”をもつ新しい意味論的領域Ｒ2を生成する（図１０（ｂ）参照）。２つの意味論的領域Ｒ1，Ｒ2はそれらのＡＮＤ演算論理式“最適な∧問合せ∧キャッシング”とマッチする組複製物を含んでいる。言い替えると、意味論的ＡＮＤ演算のケースでは、アルゴリズム１は低いキャッシュ使用と高い組複製物レベルを維持する。
【００４７】
この節では、包含のケースの外に、キャッシュの利用を改善し、組複製物を減らすように意味論的ＡＮＤ演算を処理する拡張キャッシング技法について説明する。
【００４８】
意味論的領域Ｒと問合せＱのＡＮＤ演算は、それらの論理式ＡＮＤ演算(formula intersection)Ｒ∩Ｑの論理積によって与えられる。領域シグネチャＳRと問合せシグネチャＳQが与えられたとして、ここでは、ＳQとＳRのビット状ＡＮＤ演算によって得られたそれらのシグネチャＡＮＤ演算ＳQ∩ＳRを使用する。従って、シグネチャＳの場合、シグネチャ基数(signature cardinality)｜Ｓ｜はシグネチャ内の１に設定されたビットの数を示す。
【００４９】
意味論的領域Ｒと問合せＱの意味論的ＡＮＤ演算の場合には、ここでは、２つの主要なケースを区別する。すなわち、
補数(complement)： Ｑ∩Ｒ＝φ；論理式ＡＮＤ演算はヌルである。たとえば、問合せａ∧ｂは領域ａ∧¬ｂに対する補数である。従って、領域は問合せに対する応答の組を含んでいない。しかし、補数のケースでは、領域合体は可能である。上記の問合せと領域の場合、合体は論理式ａをもつ１つの領域をもたらすであろう。
ＡＮＤ演算(intersection)：  Ｑ∩Ｒ≠φ；論理式ＡＮＤ演算はヌルでない。以下の２つのサブケースが存在する。すなわち、
・問合せおよび領域の論理式はＡＮＤ演算に現れる幾つかの共通項を有する（たとえば領域“キャッシング∧問合せ”と問合せ“最適な∧問合せ”は共通項“問合せ”を有する）。
・問合せおよび領域の論理式は共通語を持たない。たとえば、領域ａと問合せｂは共通項を持たないが、それらのＡＮＤ演算ａ∧ｂは空でなく、従って領域は部分応答に貢献できる。
【００５０】
シグネチャ・ファイル内の意味論的ＡＮＤ演算．  もし問合せＱと領域Ｒが幾つかの共通項を持っていれば、それらのシグネチャは共通項のシグネチャに対応する１に設定されたビットを有する。論理式ＱとＲが持つ共通項がを多ければ多いほど、一緒に１に設定されるビットの数は大きいので、２つのシグネチャ内の１に設定された対応するビットの数｜ＳQ∩ＳR｜によって、ＲとＱの意味論的ＡＮＤ演算を測定することができる。しかし、これは常に真ではない。たとえば、論理式ａをもつ領域と問合せｂの場合、それらのシグネチャＡＮＤ演算は１に設定されたビットを持つことはない。しかし、領域は論理式ａｂ∧ｂとマッチする組をユーザーに報告することができる。
【００５１】
本節の残りの部分では、問合せによって一部が共有されたどの領域が部分応答に貢献し、そして問合せの残りを拘束できるかを、シグネチャ・ファイル法がどのように迅速に検出できるかを示す。意味論的ＡＮＤ演算に関する以下の検討は、同等または問合せ包含はキャッシュ内で検出されないこと、従って、問合せの残りはヌルでないと仮定していることに留意されたい。
【００５２】
意味論的包含と同様に、論理積問合せは許されるだけであるので、問合せと共有部分をもつ領域のすべてが問合せの残りに貢献できるのではない。どの領域が貢献できるかを検出するために、前に導入した項差を再び使用する。さらに、意味論的包含のために導出したが、意味論的ＡＮＤ演算に完全に適用できる残りの構造を使用する。すなわち、もしキャッシュがｍ個の領域を含んでおり、その論理式は問合せＱに含まれていないが、１項差たとえばａ1，ａ2，．．．，ａmを有していれば、問合せの残りＱrは、Ｑ∧¬ａ1∧¬ａ2∧．．．∧¬ａmとして作ることができる。
【００５３】
例２（続き）  領域“キャッシング∧問合せ”は問合せ“最適∧問合せ”と１項差を有するので、領域は部分“最適∧問合せ∧キャッシング”をユーザーに報告し、問合せの残り“最適∧問合せ∧¬キャッシング”を作ることができる。同様に、領域ａは問合せｂと１項差を有する。部分ａ∧ｂは報告され，問合せの残りはｂ∧¬ａである。
【００５４】
問合せの残りを拘束する場合に問合せと１項差をもつ意味論的領域のこの著名な特徴は、キャッシュのコンテンツに対する問合せの二重走査評価をもたらす。領域シグネチャにわたる最初の高速走査は、問合せの残りを迅速に作って、最初の部分応答を生成するため１項差をもつすべての領域を識別する。第２の低速走査は、他のＡＮＤ演算が部分応答を質的に向上させることができるかを調べる。領域シクネチャにわたる２つの走査は領域シグネチャに適用されるフィルタリング関数に違いがある。
【００５５】
最初の走査のときにフィルタされる各領域Ｒは問合せとせいぜい１項差をもつべきである。従って、もし領域シグネチャが１に設定された｜ＳＲ｜ビットをもち、問合せシグネチャとそのＡＮＤ演算が｜ＳR∩ＳQ｜ビットをもっていれば、２つの数の差はせいぜいｋビットにすべきである。ここで、ｋは項シグネチャ内の１に設定されたビットの数である。以下の結果はこの事実を明白に述べている。
結果２  もし領域Ｒが問合せＱと１項差を有していれば、
｜ＳR∩ＳQ｜≧｜ＳR｜−ｋ    （２）
である。
【００５６】
最初の走査は領域シグネチャについて条件（２）を確かめる。もし条件が領域シグネチャに当てはまれば、領域論理式が１項差に関して調べられる。意味論的包含と同様に、もし条件（２）は当てはまるが、領域論理式が１項差を与えなければ、誤り選択が生じる。多くの実験を行った結果、論理式（１）で計算したシグネチャ・ファイルのパラメータを適切に選択することによって、条件（２）を確かめる時の誤り選択の数を少なく保つことができることが判った。
【００５７】
第２の走査は、論理式が２項以上の差を有し、問合せの残りを拘束することができない領域を検出する。１項差との類推により論理式が問合せとＩ（Ｉ≧２）項差をもつ領域は条件（３）を満たす。
｜ＳR∩ＳQ｜≧｜ＳR｜−ｋ・Ｉ    （３）
しかし、この条件は、第２の走査に全面的に用いることができない。第１に、条件（３）は、増加するｋの値に対してはその重要性を失う。実際には、典型的なウェブ問合せまたは領域論理式は３または４項の平均を有しており、条件（３）は｜ＳR∩ＳQ｜≧０に簡単化されることが多い。この簡単化された条件はすべての領域シグネチャを掃引し、多くの誤り選択と高いフィルタリング・オーバーヘッドを引き起こすであろう。第２に、問合せと２またはそれ以上の項差をもつ領域は，通例、１項差をもつ領域と比べて応答にほとんど貢献しない。第３に、貢献する組は、それらの論理式が問合せの残りから除外されなかったので、とにかく問合せの残りに対する応答の中に複製されないであろう。
【００５８】
それらの引数を考慮に入れて、第２の走査に対する以下の２つの条件だけを検討する。
・｜ＳR∩ＳQ｜≧｜ＳR｜−２ｋ：この条件は主として問合せと２項差をもつ領域をフェッチする。従って，より多くの項差をもつ幾つかの領域はフェッチされない。
・｜ＳR∩ＳQ｜≧０：すべての領域論理式はこの条件を満たす。従って、この条件は多くの誤り選択を引き起こす。しかし、この条件は問合せとマッチするキャッシュ内のすべての組を検索する。
【００５９】
ほとんどのケースでは、誤り選択の数と検索した組の数との間で良好のトレードオフが得られるので、最初のオプションのほうが好ましい。第2のオプションは、キャッシュが小さい場合や、アプリケーションが問合せとマッチするキャッシュからすべての組を検索しようとしているときに使用できる。
【００６０】
領域合体と領域置換  意味論的ＡＮＤ演算は合体戦略に対し新しい拡張部分を与える。一体化した論理式が論理積でありさえすれば、合体戦略は問合せと領域を合体することができる。例えば、合体戦略は問合せａ∧ｂと領域ａ∧¬ｂを１つの領域に合体することができる。次の３つの条件：１）領域が問合せと１項差、たとえばａ1を有すること、２）対称的に、問合せが領域と１項差、たとえばａ2を有すること、３）ａ1はａ2の否定であること、が守られてさえいれば、上記操作を行うことができる。明らかに、そのような状況は同じ条件２）で検出して、あとで処理することができる。
【００６１】
置換戦略は、意味論的包含(semantic containment)のために計画されたので、意味論的ＡＮＤ演算(semantic intersection)に対しても変わらない。新しい問合せが出されたとき、キャッシュ内のどの意味論的領域も応答内の領域掛かり合い(region involvement)に比例してＶtopの方に向かって更新された置換値を有している。
【００６２】
第２キャッシング技法  ここに開示する第２キャッシング技法は、問合せと意味論的領域間の２つの関係、すなわち前に述べた意味論的包含と本節で述べる意味論的ＡＮＤ演算を扱う。さらに、この技法は、問合せ包含を与える領域と意味論的ＡＮＤ演算を与える領域とを区別しないで、それらを一様に処理して１項差をもつ領域を識別する。
【００６３】
キャッシング・アルゴリズム（２）
図１１〜１４は、第２の技法に従ってキャッシングを実施する処理ステップを示す。
入力．意味論的領域をもつキャッシュと問合せＱ
出力．Ｑに対する応答と更新したキャッシュ
１．（最初の走査）  キャッシュ内の領域シグネチャと対比して問合せシグネチャを調べる（ステップｓ２１）。
２．ＳQ＝ＳR：もし論理式が問合せと同等である領域が存在すれば、領域コンテンツを応答として戻す。領域の置換値を更新し（ｓ２４，ｓ２４）、終了する。
３．ＳQ∩ＳR＝ＳQ：もし１つまたはそれ以上の領域が問合せを含んでいれば、最小限の基数(minimal cardinality)をもつ領域を選択する。領域コンテンツを走査し，問合せとマッチする組を戻す。領域の置換値を更新し（ｓ２５〜ｓ２８）、終了する。
４．｜ＳQ∩ＳR｜≧｜ＳR｜≧ｋ．問合せと１項差をもつすべての領域、たとえばＲ0，．．．，Ｒm（ｍ≧０）を識別する。Ｒ0，．．．，Ｒmの意味論的領域内の問合せとマッチする組を戻し、複製物を廃棄する（ステップｓ２９〜ｓ３６）。問合せの残りＱr＝Ｑ∧¬Ｒ0．．．∧¬Ｒkを以下のように作る（ステップｓ３１１〜ｓ３１５；図１２）：
・問合せの残りをＱに設定する（ステップｓ３１２）。
・各領域Ｒi（ｉ＝０，．．．，ｍ）について、問合せとの差ａiを計算し（ステップｓ３１４）、¬ａiをもつ問合せの残りを拘束する。問合せの残りをサーバーへ送る。
５．（第２の走査）条件Ｔをもつ領域シグネチャを走査する（ステップｓ３３１〜ｓ３３６、図１３）。Ｔは｜ＳR｜−２ｋ≧｜ＳR∩ＳQ｜＜｜ＳR−ｋと、０≦｜ＳR∩ＳQ｜＜｜ＳR｜−ｋとの選択である。フェッチした各領域Ｒについて、Ｑ∩Ｒ論理式ＡＮＤ演算を調べる（ステップｓ３３２）。もし論理式がヌルでなければ、問合せとマッチする領域コンテンツからの組を報告する（ステップｓ３３５）。
６．問合せの残りＱrに対する応答を受け取ったら、以下のようにキャッシュを更新する（ステップｓ３５１〜ｓ３５５、図１４）。
・もし領域Ｒi1．．．，Ｒipが問合せを含んでいれば、それらを論理式Ｑをもつ新しい領域で置き換える。
・もし領域Ｒが問合せＱに対する補数であり、論理式Ｒ∪Ｑが論理積(conjunction)であれば、ＲとＱを新しい領域で置き換える。
・さもなければ、論理式Ｑrをもつキャッシュに新しい領域を加える。
・部分応答に貢献するすべての領域について置換値を更新する。
【００６４】
例３
図１５は、意味論的ＡＮＤ演算のための領域合体：（ａ）問合せｃ∧ｄが出される、及び（ｂ）問合せの後、を示す。
【００６５】
キャッシュは論理式ａ∧ｂ，ｃ∧ｄ∧¬ｅをもつ領域を含んでおり、ユーザー問合せはｂ∧ｃであると仮定する。図１５（ａ）は、置換値（Ｖtop＝７と仮定する）をもつ２つの領域と問合せを示す。最初の走査は、領域ａ∧ｂが問合せと１項差を有し、そして問合せの残りＱr（ｂ∧ｃ∧¬ａ）を拘束できることを検出する。問合せとマッチする領域コンテンツからのすべての組は部分応答を与える。第２の走査は、領域ｃ∧ｄ∧¬ｅについて意味論的ＡＮＤ演算を検出する。領域コンテンツが走査される。問合せとマッチする組は部分応答を完成させる。
【００６６】
問合せの残りＱrに対する応答が受け取られると、論理式ｃ∧ｄ∧¬ｅをもつ新しい領域が生成される。置換値はＶtop＝８に等しい。同様に、ａ∧ｂとｃ∧ｄ∧¬ｅは共に、応答への貢献に比例する更新された置換値を有する｛図１５（ｂ）参照｝。
【００６７】
以上、ウェブ論理積問合せをキャッシュするための新しいメカニズムを提示した。このメカニズムはシグネチャ・ファイルに基づいており、過去の問合せを効率的に再利用することを考慮に入れている。２つのキャッシング・アルゴリズムは、ユーザー問合せと意味論的領域との意味論的包含関係とＡＮＤ演算関係をうまく処理する。
【図面の簡単な説明】
【図１】マシンのネットワークを示す略図である。
【図２】領域シグネチャの構造を示す図である。
【図３】サンプルの問合せとそれらのシグネチャを示す図である。
【図４】適当なキャッシュ・アーキテクチャを示す図である。
【図５】意味論的包含のケース  −（ａ）単一領域包含；（ｂ）複数領域包含；（ｃ）単一問合せ包含；および（ｄ）複数問合せ包含を示す図である。
【図６】領域合体の例  −（ａ）問合せＱ＝ｄが出される；（ｂ）問合せの後、合体された領域：（ｃ）問合せｂ∧ｄ∧ｆが出される；および（ｄ）問合せの後、更新された領域を示す図である。
【図７】第１の技法に従ってキャッシングを実施する処理ステップを示すフローチャートの前部分である。
【図８】同フローチャートの中間部分である。
【図９】同フローチャートの後部分である。
【図１０】（ａ），（ｂ）は意味論的ＡＮＤ演算の例を示す図である。
【図１１】第２の技法に従ってキャッシングを実施する処理ステップを示すフローチャートの第１部分である。
【図１２】同フローチャートの第２部分である。
【図１３】同フローチャートの第３部分である。
【図１４】同フローチャートの第４部分である。
【図１５】意味論的ＡＮＤ演算のための領域合体  −（ａ）問合せｃ∧ｄが出される、（ｂ）問合せの後、を示す図である。
【符号の説明】
２１  ネットワーク
２２  受信マシン
２４  中間マシン
２６  送信マシン
【図１】
0004418555.tif 000002
【図２】
0004418555.tif 000003
【図３】
0004418555.tif 000004
【図４】
0004418555.tif 000005
【図５】
0004418555.tif 000006
【図６】
0004418555.tif 000007
【図７】
0004418555.tif 000008
【図８】
0004418555.tif 000009
【図９】
0004418555.tif 000010
【図１０】
0004418555.tif 000011
【図１１】
0004418555.tif 000012
【図１２】
0004418555.tif 000013
【図１３】
0004418555.tif 000014
【図１４】
0004418555.tif 000015
【図１５】
0004418555.tif 000016