(57)【要約】  レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するためのシステムおよび方法が提供されており、システムは、プロセッサ、プロセッサと信号通信する、データベース・データをデータ・セグメントにセグメント化し、かつデータ・セグメントをデータ・クォードラントにペアリングするためのセグメント化およびペアリング・ユニット、およびプロセッサと信号通信する、各クォードラントについて重複を検出するための重複検出ユニットを含み；方法は、データベース・データを受け取ること、データベース・データをデータ・セグメントにセグメント化すること、データ・セグメントをデータ・クォードラントにペアリングすること、および各クォードラントについて重複を検出することを含む。  【選択図】      図２
2007527582.tif 000002
【特許請求の範囲】
【請求項１】
レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するための方法であって、
データベース・データを受け取ること；
前記データベース・データをデータ・セグメントにセグメント化すること；
前記データ・セグメントをデータ・クォードラントにペアリングすること；
および、各クォードラントについて重複を検出すること；
を包含する方法。
【請求項２】
前記セグメント化は、大きなデータベースを多数の交差しない、実質的に等しいセグメントに分割することを包含する請求項１に記載の方法。
【請求項３】
各セグメントは、メモリ容量内に２つのセグメントが収まるように前記メモリ容量ならびにレコードのサイズに応じた数のレコードを含む請求項１に記載の方法。
【請求項４】
ｓ個のセグメントから形成される前記セグメントのペアの数は、ｓ（ｓ‐１）／２個のセグメントのペアまたはクォードラントである請求項１に記載の方法。
【請求項５】
各ペアまたはクォードラントは、セグメント番号ｉとセグメント番号ｊを結合することによって形成され、それにおいてｉはｊより小さい、請求項４に記載の方法。
【請求項６】
Ｎ個のレコードのデータベース上における重複の検出が、２Ｎ／ｓ個のレコードのデータベースのためのｓ（ｓ‐１）／２個の重複検出のジョブに分割され、その結果それらのジョブのそれぞれが２つのデータベース読み出しを行う請求項４に記載の方法。
【請求項７】
前記ジョブを処理する順序が、すべての（ｓ（ｓ‐１）／２）個のクォードラントのためのデータベース読み出しの数が、Ｎ個のレコードのあらゆるペアが同時に前記メモリ内に見つかることを保証するための最も少ないデータベース読み出し数である（ｓ（ｓ‐１）／２＋１）となるように整理される請求項６に記載の方法。
【請求項８】
前記クォードラントのジョブを処理する順序が、（１，２）（１，３）．．．（１，ｓ）（２，ｓ）（２，ｓ‐１）．．．（２，３）（３，４）（３，５）．．．（ｓ‐１，ｓ）である請求項７に記載の方法。
【請求項９】
各クォードラントについて重複を検出することは、
セグメント（１，２）のクォードラントについて全てのペアを考慮すること；
クォードラント（１，ｉ）については、１つのレコードがセグメント１内にあり、他方のレコードがセグメントｉ内にあるか、もしくは両方のレコードがセグメントｉ内にある場合に２つのレコードのペアを考慮すること；および、
ｊ＞ｉ＞１とするクォードラント（ｉ，ｊ）については、１つのレコードがセグメントｉ内にあり、他方のレコードがセグメントｊ内にある場合に２つのレコードのペアを考慮することを包含し、
Ｎ個のレコードからの任意のペアが１つのクォードラントの中だけで考慮されることになる請求項１に記載の方法。
【請求項１０】
レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するためのシステムであって、
少なくとも１つのプロセッサ；
前記少なくとも１つのプロセッサと信号通信する、データベース・データをデータ・セグメントにセグメント化し、かつ前記データ・セグメントをデータ・クォードラントにペアリングするためのセグメント化およびペアリング・ユニット；および、
前記少なくとも１つのプロセッサと信号通信する、各クォードラントについて重複を検出するための重複検出ユニット；
を包含するシステム。
【請求項１１】
さらに、少なくとも１つの入力／出力アダプタおよび前記プロセッサと信号通信するデータベース・データを受け取るための通信アダプタを包含する、請求項１０に記載のシステム。
【請求項１２】
前記セグメント化およびペアリング・ユニットは、大きなデータベースを多数の交差しない、実質的に等しいセグメントに分割するための手段を包含する、請求項１０に記載のシステム。
【請求項１３】
前記セグメント化およびペアリング・ユニットは、メモリ容量内に２つのセグメントが収まるように前記メモリ容量ならびにレコードのサイズに応じた数のレコードを各セグメント内に含めるための手段を包含する、請求項１０に記載のシステム。
【請求項１４】
前記セグメント化およびペアリング・ユニットは、ｓ個のセグメントから形成される前記セグメントのペアの数を、ｓ（ｓ‐１）／２個のセグメントのペアまたはクォードラントと決定するための手段を包含する、請求項１０に記載のシステム。
【請求項１５】
前記セグメント化およびペアリング・ユニットは、各ペアまたはクォードラントを、セグメント番号ｉとセグメント番号ｊを結合することによって形成するための手段を包含し、それにおいてｉはｊより小さい、請求項１０に記載のシステム。
【請求項１６】
前記重複検出ユニットは、タスクを２Ｎ／ｓ個のレコードのデータベースのためのｓ（ｓ‐１）／２個の重複検出のジョブに分割することによってＮ個のレコードのデータベース上において重複を検出するための手段を包含し、その結果それらのジョブのそれぞれが２つのデータベース読み出しを行う、請求項１０に記載のシステム。
【請求項１７】
前記重複検出ユニットは、すべての（ｓ（ｓ‐１）／２）個のクォードラントのためのデータベース読み出しの数が、Ｎ個のレコードのあらゆるペアが同時に前記メモリ内に見つかることを保証するための最も少ないデータベース読み出し数である（ｓ（ｓ‐１）／２＋１）となるように前記ジョブを処理する順序を整理するための手段を包含する、請求項１６に記載のシステム。
【請求項１８】
前記重複検出ユニットは、前記クォードラントのジョブを処理する順序を（１，２）（１，３）．．．（１，ｓ）（２，ｓ）（２，ｓ‐１）．．．（２，３）（３，４）（３，５）．．．（ｓ‐１，ｓ）として設定するための手段を包含する、請求項１７に記載のシステム。
【請求項１９】
前記重複検出ユニットは、各クォードラントについて重複を検出するための手段を包含し、前記手段は：
セグメント（１，２）のクォードラントについてすべてのペアを考慮するための手段；
クォードラント（１，ｉ）については、１つのレコードがセグメント１内にあり、他方のレコードがセグメントｉ内にあるか、もしくは両方のレコードがセグメントｉ内にある場合に２つのレコードのペアを考慮するための手段；
および、ｊ＞ｉ＞１とするクォードラント（ｉ，ｊ）については、１つのレコードがセグメントｉ内にあり、他方のレコードがセグメントｊ内にある場合に２つのレコードのペアを考慮するための手段；
を包含し、Ｎ個のレコードからの任意のペアが１つのクォードラントの中だけで考慮されることになることを特徴とする請求項１０に記載のシステム。
【請求項２０】
レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するためのプログラム・ステップを実行するべくマシンによって実行可能なインストラクションのプログラムを有体として具体化するマシン可読プログラム・ストレージ・デバイスであって、前記プログラム・ステップが、
データベース・データを受け取ること；
前記データベース・データをデータ・セグメントにセグメント化すること；
前記データ・セグメントをデータ・クォードラントにペアリングすること；および、
各クォードラントについて重複を検出すること；
を包含するマシン可読プログラム・ストレージ・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願に対するクロスリファレンス
本件出願は、２００４年３月５日に『オプティマイジング・データベース・アクセス・フォア・レコード・リンケージ・バイ・タイリング・ザ・スペース・オブ・レコード・ペア（Ｏｐｔｉｍｉｚｉｎｇ  Ｄａｔａｂａｓｅ  Ａｃｃｅｓｓ  ｆｏｒ  Ｒｅｃｏｒｄ  Ｌｉｎｋａｇｅ  ｂｙ  Ｔｉｌｉｎｇ  ｔｈｅ  Ｓｐａｃｅ  ｏｆ  Ｒｅｃｏｒｄ  Ｐａｉｒｓ）』と題して出願された米国特許仮出願第６０／５５０，４５４号（代理人ドケット番号第２００４Ｐ０３６８２ＵＳ）の恩典を主張するものであり、当該出願は、その全体が参照によりこれに援用される。
【背景技術】
【０００２】
データベースのためのレコードのリンクは、同一のエンティティ（実体としてのデータ集合）を表すデータベース内のレコードのペアまたはセットを見つけ出す問題である。ランダム・アクセス・メモリ内に全体が収まらない大きなデータベースの場合、レコードのすべての可能ペアの比較は、比較が必要なデータ・レコードをメモリ内に持ち込むために多くのデータベース読み出しが必要になる。これは、非効率かつ時間を要する操作である。
【０００３】
従来考えられていた技術においては、各データベースの読み出しの際、同一のブロッキング・キー値を有するレコード等とのごとき比較すべきレコードがメモリ内にロードされる。この種の方法にはいくつかの欠点がある。１つの欠点は、その種のブロックの数が多く、その結果、必要とされるデータベース読み出しの数が大きくなる。別の欠点は、ブロック・サイズが広い範囲にわたって変動し得ることである。小さなブロックについては、この方法がメモリ・リソースの無駄を招く。大きすぎるブロックについては、領域外参照又はメモリ不足が生じる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、レコードのリンクのためのデータベース・アクセスを最適化することが望ましい。
【課題を解決するための手段】
【０００５】
従来技術におけるこれらの、およびこのほかの欠点ならびに不利益は、レコードのペアの空間のタイリングによるレコードのリンクのためのデータベース・アクセスの最適化のための例示的なシステムおよび方法によって取り扱われる。
【０００６】
レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するための例示的なシステムは、プロセッサ、プロセッサと信号通信する、データベース・データをデータ・セグメントにセグメント化し、かつデータ・セグメントをデータ・クォードラントにペアリングするためのセグメント化およびペアリング・ユニット、およびプロセッサと信号通信する、各クォードラントについて重複を検出するための重複検出ユニットを含む。
【０００７】
レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するための例示的な方法は、データベース・データを受け取ること、データベース・データをデータ・セグメントにセグメント化すること、データ・セグメントをデータ・クォードラントにペアリングすること、および各クォードラントについて重複を検出することを含む。
【０００８】
この開示のこれらの、およびこのほかの側面、特徴、および利点については、添付図面に関連して記述された以下の例示的実施態様の説明から明らかなものとなろう。
【０００９】
この開示は、添付の例示的な図面に従ってレコードのペアの空間のタイリングによるレコードのリンクのためのデータベース・アクセスの最適化のためのシステムおよび方法を教示する。
【発明を実施するための最良の形態】
【００１０】
レコードのリンクにおけるデータベース読み出しを最小化する、レコードのペアの空間のタイリングによるレコードのリンクのためのデータベース・アクセスの最適化を含むタイリング・テクニックが提供されている。このタイリング・テクニックは、大きなデータベースについてのレコードのリンクまたは重複検出の問題を、メモリ内に完全にロードすることが可能なより小さなデータベースについてのいくつかのレコードのリンク問題に分割する。このテクニックは、データベース読み出しの数を最小化し、ブロック・サイズの範囲を狭め、メモリ・リソースの効率的な利用を最大化し、さらに、領域外参照やメモリ不足エラーといったいわゆるアウトオブメモリーを回避する。
【００１１】
この開示の例示的な実施態様は、データベース読み出しの数を最小化する一方、任意のレコードのペアが所定の時間期間にわたってメモリ内において利用可能となることを保証する。それに加えてこの実施態様は、各読み出しのためにメモリ内に読み込まれることになるレコードの数を安定化し、かつ最大化する。
【００１２】
図１に示されているとおり、この開示の例示的な実施態様に従った、レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するためのシステムが、参照番号１００によって包括的に示されている。システム１００は、システム・バス１０４と信号通信する少なくとも１つのプロセッサまたは中央処理ユニット（ＣＰＵ）１０２を含む。読み出し専用メモリ（ＲＯＭ）１０６、ランダム・アクセス・メモリ（ＲＡＭ）１０８、ディスプレイ・アダプタ１１０、Ｉ／Ｏアダプタ１１２、ユーザ・インターフェース・アダプタ１１４、および通信アダプタ１２８もまたシステム・バス１０４と信号通信する。ディスプレイ・ユニット１１６は、ディスプレイ・アダプタ１１０を介してシステム・バス１０４と信号通信する。たとえば磁気または光ディスク・ストレージ・ユニット等のディスク・ストレージ・ユニット１１８は、Ｉ／Ｏアダプタ１１２を介してシステム・バス１０４と信号通信する。マウス１２０、キーボード１２２、および目追跡デバイス１２４は、ユーザ・インターフェース・アダプタ１１４を介してシステム・バス１０４と信号号通信する。
【００１３】
セグメント化およびペアリング・ユニット１７０および重複検出ユニット１８０もまた、システム１００内に含まれており、ＣＰＵ  １０２およびシステム・バス１０４と信号通信する。セグメント化およびペアリング・ユニット１７０および重複検出ユニット１８０は、少なくとも１つのプロセッサまたはＣＰＵ  １０２に結合されているとして例示されているが、これらのコンポーネントは、好ましくはメモリ１０６、１０８、および１１８のうちの少なくとも１つの中にストアされたコンピュータ・プログラム・コードとして具体化されており、それにおいて当該コンピュータ・プログラム・コードは、ＣＰＵ  １０２によって実行される。
【００１４】
図２を参照すると、この開示の例示的な実施態様に従ったレコードのペアの空間のタイリングによるレコードのリンクのためのデータベース・アクセスを最適化するための方法が包括的に参照番号２００によって示されている。この方法２００は、開始ブロック２１０を含み、それがコントロールを入力ブロック２１２に渡す。入力ブロック２１２は、データベース・データを受け取ると関数ブロック２１４にコントロールを渡す。関数ブロック２１４はデータベース・データをセグメント化し、関数ブロック２１６にコントロールを渡す。関数ブロック２１６もまた、セグメントをクォードラントにペアリングすると関数ブロック２１８にコントロールを渡す。関数ブロック２１８は、各クォードラントについて重複を検出し、コントロールを終了ブロック２２０に渡す。
【００１５】
動作においてはこのテクニックが、レコードのリンクの大きなタスクまたはジョブから多くのより小さいジョブまたはクォードラントへの分割を可能にする。各クォードラントは、完全にプロセッシング・ユニットのＲＡＭ内に収まる。したがって、クォードラントは、１つのＣＰＵ上においてシーケンシャルに、または別々のＣＰＵ上においてパラレルに処理することができる。
【００１６】
大きなデータベースは、ｓ個の交差しない、実質的に等しいセグメントに分割される。セグメント内のレコードの数は、２つのパラメータ：すなわち（１）メモリ容量、および（２）レコードのサイズを基礎として、２つのセグメントをメモリ内にロードできるように決定される。分割基準は、メモリ内へのセグメントの読み込みがもっとも効率的となるように選択される。たとえばセグメントは、レコードＩＤの範囲によって決定される。
【００１７】
ｓ個のセグメントから、ｓ（ｓ‐１）／２個のセグメントのペアが形成されることになる。各ペアは、クォードラントと呼ばれるが、セグメント番号ｉとセグメント番号ｊを結合することによって形成され、それにおいてはｉ＜ｊである。
【００１８】
各クォードラントについて重複検出が実行される。要約すると、Ｎ個のレコードのデータベースに対する重複検出ジョブが、２Ｎ／ｓ個のレコードのデータベースのためのｓ（ｓ‐１）／２個の重複検出ジョブに分割される。これらのジョブのそれぞれは、２回のデータベース読み出しを必要とする。ジョブを処理する順序は、すべての（ｓ（ｓ‐１）／２）個のクォードラントのためのデータベース読み出しの数が（ｓ（ｓ‐１）／２＋１）となるように整理することができる。その種の順序の一例を挙げると次のとおりとなる：（１，２）（１，３）．．．（１，ｓ）（２，ｓ）（２，ｓ‐１）．．．（２，３）（３，４）（３，５）．．．（ｓ‐１，ｓ）。これは、Ｎ個のレコードのあらゆるペアが同時にメモリ内に見つかることを保証するために行われることになる最も少ない数のデータベース読み出しである。
【００１９】
クォードラントの処理は１つずつわずかに異なる。セグメント（１，２）のクォードラントについては、すべてのペアが考慮される。各クォードラント内においては、考慮されたすべてのペアが実際に比較されるわけではない。言い換えると、２つのレコードは、それらが同一のブロッキング・キーを有している場合に限って比較される。ブロッキング・キーは、あらかじめ指定されたインデクスのセットであり、レコードのブロッキング・キー値は、それらの指定されたポジションにおける文字列である。クォードラント（１，ｉ）については、２つのレコードのペアは、（１）１つのレコードがセグメント１内にあり、他方のレコードがセグメントｉ内にある場合、もしくは（２）両方のレコードがセグメントｉ内にある場合に考慮されることになる。ｊ＞ｉ＞１とするクォードラント（ｉ，ｊ）については、１つのレコードがセグメントｉ内にあり、他方のレコードがセグメントｊ内にある場合に２つのレコードが考慮されることになる。このバリエーションは、Ｎ個のレコードからの任意のペアが１つのクォードラントの中だけで考慮されることを保証する。
【００２０】
したがって、この好ましい教示の優れたパフォーマンスが、（１）データベース読み出しの数の最小化、（２）利用可能なメモリ容量の最大利用、および（３）２回比較されるレコードのペアがないことの保証によって達成される。
【００２１】
装置１００の代替実施態様においては、コンピュータ・プログラム・コードの一部もしくは全部をプロセッサ・チップ１０２上に配置されるレジスタ内にストアすることができる。それに加えて、セグメント化およびペアリング・ユニット１７０ならびに重複検出ユニット１８０をはじめ、システム１００のほかの要素について種々の代替構成および実装を行うことができる。
【００２２】
ここで理解する必要があるが、この開示の教示は、種々の形式のハードウエア、ソフトウエア、ファームウエア、専用プロセッサ、またはそれらの組み合わせにおいて実装することができる。もっとも好ましくは、この開示の教示がハードウエアとソフトウエアの組み合わせとして実装されることである。
【００２３】
さらに、ソフトウエアは、好ましくはプログラム・ストレージ・ユニット上において有体として具体化されるアプリケーション・プログラムとして実装される。このアプリケーション・プログラムを、任意の適切なアーキテクチャを構成するマシンにアップロードし、それによって実行することができる。好ましくはこのマシンが、１ないしは複数の中央処理ユニット（ＣＰＵ）、ランダム・アクセス・メモリ（ＲＡＭ）、および入力／出力（Ｉ／Ｏ）インターフェース等のハードウエアを有するコンピュータ・プラットフォーム上に実装される。
【００２４】
コンピュータ・プラットフォームは、オペレーティング・システムおよびマイクロインストラクション・コードも含む。ここで述べている種々のプロセスおよび関数は、これらのマイクロインストラクション・コードの部品もしくはアプリケーション・プログラムの部品、またはそれらの組み合わせとしてもよく、それらはＣＰＵによって実行することができる。それに加えて、追加のデータ・ストレージ・ユニットおよびプリント・ユニットといった、このほかの種々の周辺ユニットをこのコンピュータ・プラットフォームに接続することもできる。
【００２５】
さらにここで理解が必要であるが、添付図面に図示されている構成システム・コンポーネントならびに方法のいくつかが好ましくはソフトウエアにおいて実装されることから、システム・コンポーネントまたはプロセスの関数ブロックの間の実際の接続が、この開示がプログラムされる態様に応じて異なることがある。この教示が与えられれば、この開示のそれらの、および類似の実装もしくは構成を当業者が企図することは可能となろう。
【００２６】
添付図面を参照して例示的な実施態様を説明してきたが、この開示がそれらの実施態様そのままに限定されることはなく、この開示の範囲または精神から逸脱することなしにそれらへの種々の変更および修正が当業者によってもたらされ得ることを理解する必要がある。それらの変更ならびに修正のすべては、付随する特許請求の範囲によって定義されるとおりのこの開示の範囲内に含まれることが意図されている。
【図面の簡単な説明】
【００２７】
【図１】この開示の例示的な実施態様に従った、レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するためのシステムを示した概略図である。
【図２】この開示の例示的な実施態様に従った、レコードのペアの空間のタイリングによってレコードのリンクのためのデータベース・アクセスを最適化するための方法を示したフローチャートである。
【符号の説明】
【００２８】
１００  システム
１０２  中央処理ユニット（ＣＰＵ）；プロセッサ・チップ
１０４  システム・バス
１０６  読み出し専用メモリ（ＲＯＭ）
１０８  ランダム・アクセス・メモリ（ＲＡＭ）
１１０  ディスプレイ・アダプタ
１１２  Ｉ／Ｏアダプタ
１１４  ユーザ・インターフェース・アダプタ
１１６  ディスプレイ・ユニット
１１８  ディスク・ストレージ・ユニット
１２０  マウス
１２２  キーボード
１２４  目追跡デバイス
１２８  通信アダプタ
１７０  セグメント化およびペアリング・ユニット
１８０  重複検出ユニット
【図１】
2007527582.tif 000003
【図２】
2007527582.tif 000004
【国際調査報告】
2007527582.tif 000005
2007527582.tif 000006