【手続補正書】
【提出日】平成19年2月28日(2007.2.28)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】    【請求項１】データベースにおいて、第１の複数のフラグメントを有する第１の表（table）と第２の複数のフラグメントを有する第２の表との間に結合述語を有している結合への応答を生成するためのコンピュータに実装された方法であって、  前記第１の表からの各対応フラグメントに対して、前記第１の表からの前記対応フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表からのフラグメントを識別する、結合フラグメントマップを検索し；かつ  前記結合述語を満足させることができないフラグメントを削除するためにマップを用い、  削除されなかった前記フラグメント上の前記結合述語を実行する段階を具備することを特徴とする方法。    【請求項２】データベースにおいて、第１の複数のフラグメントを有する第１の表（table）と第２の複数のフラグメントを有する第２の表との間の結合を処理するためのコンピュータに実装された方法であって、  前記第１の表からの各対応フラグメントに対して、前記第１の表からの前記対応フラグメントからの記録を伴う前記結合の結合述語を満足させる記録を含む前記第２の表からのフラグメントを識別する、結合フラグメントマップを検索し；  前記マップを適用することによって前記結合述語を満足させる記録を有することが可能なフラグメントを識別し；かつ  前記識別されたフラグメント上の前記結合述語を実行する段階を具備することを特徴とする方法。    【請求項３】前記結合の単一表述語を満足させる前記第１の表からの第１のフラグメントのセットを識別する段階を更に具備することを特徴とする請求項２に記載の方法。    【請求項４】フラグメントを識別する段階は、前記フラグメントの第１のセットを伴う前記結合述語を満足させる前記第２の表からの第２のフラグメントのセットを識別するために前記マップを含むことを特徴とする請求項３に記載の方法。    【請求項５】前記質問を実行する段階は、前記第１のフラグメントのセット及び前記第２のフラグメントのセット上で該質問を実行することを含むことを特徴とする請求項４に記載の方法。    【請求項６】フラグメントを識別する段階は、前記結合述語を満足させうる前記第１の表からの第１のフラグメントのセットを識別するために前記マップを含むことを特徴とする請求項２に記載の方法。    【請求項７】フラグメントを識別する段階は、前記第１のフラグメントのセットを伴う前記結合述語を満足させうる前記第２の表からの第２のフラグメントのセットを識別するために前記マップを用いることを更に含むことを特徴とする請求項６に記載の方法。    【請求項８】フラグメントを識別する段階は、前記第２のフラグメントのセットを伴う前記結合述語を満足させうる前記第１のフラグメントのセットのサブセットを識別するために前記マップを用いることを更に含むことを特徴とする請求項７に記載の方法。    【請求項９】フラグメントを識別する段階は、前記第１のフラグメントのセットを伴う前記結合述語を満足させうる前記第２のフラグメントのセットのサブセットを識別するために前記マップを用いることを更に含むことを特徴とする請求項８に記載の方法。    【請求項１０】前記サブセットを識別する段階は、更なるフラ���メントが削除されなくなるまで繰り返されることを特徴とする請求項９に記載の方法。    【請求項１１】データベースにおいて、データベース表の質問を実行すべく動作しかつフラグメントへの表（table）の分離を支持するシステムにおいて、第１の表及び第２の表に結合演算を適用するためのコンピュータに実装された方法であって、  前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のそれらのフラグメントを前記第１の表の各フラグメントに対して識別し；  前記質問の単一表述語を満足させる記録を有する前記第１の表からの第１のフラグメントのセットを識別し；  前記マップを適用することによって前記第１のフラグメントのセットからの記録を伴う前記結合述語を満足させる記録を含む第２の表からの第２のフラグメントのセットを識別し；かつ  前記第１のフラグメントのセット及び前記第２のフラグメントのセット上の前記質問を実行する段階を具備することを特徴とする方法。    【請求項１２】データベースにおいて、第１の複数のフラグメントを有する第１の表（table）と第２の複数のフラグメントを有する第２の表との間の結合を処理するためのコンピュータに実装された方法であって、  前記第１の表からの各対応フラグメントに対して、前記第１の表からの前記対応フラグメントからの記録を伴う前記結合の結合述語を満足させる記録を含む前記第２の表からのフラグメントを識別する、マップを検索し；  前記第１の表から記録を受け取り；  前記受け取った記録の前記フラグメントを伴う前記結合述語を満足させる前記第２の表からのフラグメントのセットを識別するために前記マップを使用し；かつ  前記受け取った記録を伴う前記結合述語を満足させる記録に対して前記識別されたフラグメントのセットを走査する段階を具備することを特徴とする方法。    【請求項１３】前記結合述語を満足させる記録を含むフラグメントを選択するために前記マップを使用することを更に具備し、かつ前記受け取り、使用及び走査段階は、前記選択したフラグメントの全ての記録に適用されることを特徴とする請求項１２に記載の方法。    【請求項１４】データベース表の質問を実行すべく動作しかつフラグメントへの表（table）の分離を支持するシステムにおいて、第１の表及び第２の表に結合演算を適用するためのコンピュータに実装された方法であって、  前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のそれらのフラグメントを前記第１の表の各フラグメントに対して識別しかつマップに前記識別を記憶し；  前記質問の単一表述語を満足させる記録を有する前記第１の表からの第１のフラグメントのセットを識別し；  前記第１の表から記録を受け取り；  前記マップを適用することによって前記受け取った記録を伴う結合述語を満足させる記録を有する前記第２の表からのフラグメントのセットを識別し；かつ  前記受け取った記録を伴う前記結合述語を満足させる記録に対する前記識別されたフラグメントのセットを走査する段階を具備することを特徴とする方法。    【請求項１５】フラグメントへの表の分離を支持するデータベースシステムにおいて、第１の表（table）及び第２の表に結合述語を有し���いる結合を最適化する方法であって、  結合フラグメントマップを生成すべく前記結合述語を有している簡略化された質問を実行する段階を具備し、前記結合フラグメントマップは、前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のフラグメントを前記第１の表の各フラグメントについて識別することを特徴とする方法。    【請求項１６】前記結合フラグメントマップは、前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のフラグメントを前記第１の表の各フラグメントについてリストすることを特徴とする請求項１５に記載の方法。    【請求項１７】前記結合フラグメントマップは、前記第１の表及び前記第２の表からの各対のフラグメントに対するビットを有しているビットマップであることを特徴とする請求項１５に記載の方法。    【請求項１８】前記ビットマップを圧縮することを更に含むことを特徴とする請求項１７に記載の方法。    【請求項１９】前記第１の表から第１のフラグメントを選択し、前記第２の表から第２のフラグメントを選択し、かつフラグメントのペアリングが前記結合述語を満足させる記録を含むかどうかを決定すべく前記第１のフラグメントと第２のフラグメントの前記ペアリングに対応するビットをチェックすることを更に含むことを特徴とする請求項１７に記載の方法。    【請求項２０】前記ビットマップの生成は、当該ビットマップがいっぱいになったならば打ち切られることを特徴とする請求項１７に記載の方法。    【請求項２１】前記第１及び第２の表は、前記ビットマップが十分にスパースであるかどうかを決定すべくサンプルされることを特徴とする請求項１７に記載の方法。    【請求項２２】前記ビットマップの生成は、サーバが、オンにされたスパースな数のビットを有するビットマップを探し出すために異なる表の種々のカラムを結合するようなディスカバリ処理によってトリガされることを特徴とする請求項１７に記載の方法。    【請求項２３】結合フラグメントマップは、揮発性メモリに記憶されることを特徴とする請求項１５に記載の方法。    【請求項２４】結合フラグメントマップの前記生成は、明示的ユーザデータ定義コマンドによってトリガされることを特徴とする請求項１５に記載の方法。    【請求項２５】結合フラグメントマップの前記生成は、二つの表の間の参照保全規約の定義によってトリガされることを特徴とする請求項１５に記載の方法。    【請求項２６】前記簡略化された質問は、前記質問からの単一表述語を含まないことを特徴とする請求項１５に記載の方法。    【請求項２７】前記簡略化された質問は、単一簡略結合述語を含むことを特徴とする請求項１５に記載の方法。    【請求項２８】前記第１の表または前記第２の表からの記録が追加されるかまたは変更されたならば前記結合フラグメントマップを更新することを更に含むことを特徴とする請求項１５に記載の方法。    【請求項２９】最初の質問と同じ結合述語及び少なくとも一つの異なる述語を有している新しい質問に対して前記結合フラグメントマップを検索することを更に含むことを特徴とする請求項１５に記載の方法。    【請求項３０】前記最初の質問を適用する前記��１の表のフラグメント及び前記第２の表のフラグメントを選択するために前記結合フラグメントマップを使用することを更に具備することを特徴とする請求項１５に記載の方法。    【請求項３１】リレーショナルデータベース表（table）の質問を実行すべく動作しかつフラグメントへの表の分離を支持するシステムにおいて、第１の表及び第２の表で結合述語を有している質問を最適化する方法であって、  前記結合述語を満足させることができる記録を有している前記第１の表のフラグメントである第１のフラグメントのセットを識別し；  前記結合述語を満足させることができる記録を有している前記第２の表のフラグメントである第２のフラグメントのセットを識別し；かつ  前記識別されたフラグメントの前記質問を実行する段階を具備することを特徴とする方法。    【請求項３２】前記第１のフラグメントのセットは、前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のフラグメントを前記第１の表の各フラグメントに対して識別する結合フラグメントマップによって識別されることを特徴とする請求項３１に記載の方法。    【請求項３３】前記識別されたフラグメントの前記質問を実行する段階は、  前記第１のフラグメントのセットからの選択したフラグメントからの記録を検索し；  前記第２のフラグメントのセットからのフラグメントのサブセットを識別し、    前記サブセットは、前記選択したフラグメントを伴う前記結合述語を満足させることができる記録を有している前記第２の表のフラグメントであり；かつ  前記結合述語を満足させている記録に対して前記フラグメントのサブセットを走査する段階を具備することを特徴とする請求項３１に記載の方法。    【請求項３４】リレーショナルデータベース表（table）の質問を実行すべく動作しかつフラグメントへの表の分離を支持するシステムにおける結合述語を処理する方法であって、  結合フラグメントマップを生成すべく結合述語を有している簡略化された質問を実行し、前記結合フラグメントマップは、前記第１の表フラグメントからの記録を伴う前記結合述語を満足させる記録を含む前記第２の表のフラグメントを前記第１の表の各フラグメントに対して識別し；  前記結合述語を満足させる記録を有している前記第１の表のフラグメントである第１のフラグメントのセットを識別すべく前記結合フラグメントマップを使用し；  前記結合述語を満足させる記録を有している前記第２の表のフラグメントである第２のフラグメントのセットを識別すべく前記結合フラグメントマップを使用し；  前記第１のフラグメントのセットからの選択したフラグメントからの記録を検索し；  第２のフラグメントのセットからのフラグメントのサブセットを識別し、      前記サブセットは、前記選択したフラグメントを伴う前記結合述語を満足させる記録を有している前記第２の表のフラグメントであり；かつ  前記結合述語を満足させる記録に対して前記フラグメントのサブセットを走査する段階を具備することを特徴とする方法。    【請求項３５】コンピュータ読取り可能媒体であって、請求項１−３４のいずれか１項に記載の方法の各ステップをコンピュータに実行させるためのプログラムを記録したコンピュ���タ読取り可能媒体。【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】    そのような技術の一例は、以下の質問で説明されうる：SELECT * FROM R, S                           [例１］WHERE R.r = S.sand R.r 10;  この質問は、結合述語R.r = S.s を満足させる全ての記録を見つけることを試みる。  また、表Ｒからの記録は、述語R.r 10も満足させなければならないしかつR.r は、S.s に等しくなければならないので、推移の代数律(algegraic rule of transitivity)を適用することによって、データベースシステムは、表Ｓのマッチング記録が条件S.s 10も満足させなければならないということを決定する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】  図４を参照すると、結合フラグメントマップは、二つのフラグメントマップ６０及び７０を組み合わせることによって形成された、単一フィールド−フラグメントマップ８０から構成されうる。フィールド−フラグメントマップは、二つのフィールド−フラグメントマップから州列６４及び７４を削除することによって生成されうる。フィールド−フラグメントマップ結合マップ８０は、１２のエントリ８２、即ち、表Ｒの各フラグメントに対して一つのエントリ、を含む。エントリ８２は、表Ｒの関連付けられたフラグメント８４からの記録を伴う結合述語を満足させる記録を含む表Ｓからのフラグメント番号のリスト８６を含む。例えば、最初のエントリは、表Ｒの第１番目のフラグメントからの一つ以上の記録を伴う結合述語を満足させる記録を含む表Ｓからのフラグメント（５、７、２７、３０、３１、４５）のリストを有する。この説明では、フィールド−フラグメントマップ８０は、二つのフィールド−フラグメントマップ６０及び７０の最初の二つの行だけを組み合わせることによって生成された。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】  図１２を参照すると、辞書管理装置１９０は、先のビットマップが現行の質問の結合述語に対して生成されたかどうかを決定することによって始動する（ステップ１９２）。先のビットマップが存在するならば、古いビットマップは、廃棄され（ステップ１９４）かつ新しいビットマップが保存される（ステップ１９６）。この質問に対して古いビットマップが存在しないならば、先のビットマップを廃棄する段階は、省略される。最後に、データベースシステムは、ビットマップ発生装置サブルーチンに戻る（ステップ１９８）。 図１３を参照することにより、実行装置２００は、データベースシステムがステップ１０６において結合述語を実行するときに呼び出される（図７参照）。簡単に言うと、実行装置は、表の一つのアクティブフラグメントからの記録を受け取る。実行装置は、走査されるべき他の表からのフラグメントを識別するためにフラグメント番号及びビットマップを用いる。実行装置は、それらのフラグメントを走査し、フラグメントからのマッチング記録を収集し、かつマッチング記録をユーザに戻す。実行装置は、一つの表Ｒのアクティブフラグメントからの記録を受け取ることによって始動する（ステップ２０２）。記録は、表ＲとＳが以下に説明する動作において切り替えうるけれども、この例では表Ｒから受け取られる。次いで、データベースシステムは、マッチング記録に対して走査されるべき表Ｓのフラグメントを識別するために結合フラグメントマップを用いる（ステップ２０４）。特に、結合フラグメントマップがビットマップであるならば、データベースシステムは、フラグメントのその対が結合述語を満足させる記録を含むかどうかを決定すべく表Ｒのフラグメント番号に等しい行及び表Ｓのフラグメント番号に等しい列におけるビットをアクセスする。表Ｓの識別されたフラグメントは、結合述語を満足させる記録に対して走査される（ステップ２０６）。これらの記録は、収集され（ステップ２０８）かつユーザに戻される（ステップ２１０）。最後に、完了メッセージがユーザに送られ（ステップ２１２）かつ実行装置が終了する（ステップ２１４）。