(57)【要約】      （修正有）【課題】範囲クエリの処理方法及びプログラムを提供する。【解決手段】データアイテムは複数の記憶ユニットに分散され、１又は２つのデータ要素はプレフィックス部分として指定される。データベース制御部１０は、プレフィックス部分のデータ要素に対する範囲クエリを受信するクエリ受信モジュール１２、順序付きリストを格納し、順序付きリストは、データアイテムの各々について記憶ユニット３０の識別情報を含み、識別情報の順序は、データアイテムのプレフィックス部分に適用された順序付けメトリックにより決定される、順序付きリスト記憶モジュール１４と、プレフィックス部分として指定されたデータ要素の値とその数とを記録する、プレフィックス頻度記憶モジュール１６と、頻度に基づき、リスト位置を計算するリスト位置計算モジュール１８と、リスト位置で識別された記憶ユニットからデータアイテムを要求する結果読み出しモジュール１９と、を有する。【選択図】図１
2014232532.tif 000002
【特許請求の範囲】
【請求項１】
データアイテムのセットとして符号化された情報のデータベースのためのデータベース制御部であって、前記データアイテムは、個々の識別情報により互いに区別可能な複数の記憶ユニットの間に分散され、各データアイテムは、２以上のデータ要素の各々の値を有し、前記データアイテムのセットは、前記２以上のデータ要素の所定の順序を有し、前記順序の最初の１又は２つのデータ要素はプレフィックス部分として指定され、前記データベース制御部は、
１又は複数のデータ要素の各々の値を検索プレフィックス部分として指定する範囲クエリを受信するよう構成されるクエリ受信モジュールであって、範囲クエリ結果として返される各データアイテムは、自身のプレフィックス部分に前記検索プレフィックス部分を含まなければならない、クエリ受信モジュールと、
前記データアイテムのセットからの前記データアイテムの各々について個々に、前記データアイテムが格納される記憶ユニットの前記識別情報を有する順序付きリストを格納するよう構成される順序付きリスト記憶モジュールであって、前記識別情報の順序は、前記個々のデータアイテムのプレフィックス部分に適用される順序付けメトリックにより決定される、順序付きリスト記憶モジュールと、
頻度レコードを維持するよう構成され、前記データアイテムのセットのプレフィックス部分として指定されたデータ要素の値と、各プレフィックス部分を有するデータアイテムの数と、を記録する、プレフィックス頻度記憶モジュールと、
前記頻度レコードに基づき、データアイテムのプレフィックス部分に前記検索プレフィックス部分を含むデータアイテムが格納される記憶ユニットの識別情報において、前記順序付きリスト内の１又は複数のリスト位置を計算するよう構成されるリスト位置記憶モジュールと、
前記計算された１又は複数のリスト位置で識別された記憶ユニットから、前記検索プレフィックス部分をプレフィックス部分に含むデータアイテムを要求するよう構成される結果読み出しモジュールと、
を有するデータベース制御部。
【請求項２】
前記プレフィックス頻度記憶モジュールは、前記順序付けメトリックを前記データアイテムの前記プレフィックス部分に適用することにより決定された順序で前記頻度レコードを維持するよう構成され、
前記リスト位置計算モジュールは、前記順序付けメトリックにより決定された順序で前記検索プレフィックス部分に先行するプレフィックス部分を有するデータアイテムの数を加算することにより、前記１又は複数のリスト位置の開始点を計算し、前記検索プレフィックス部分を有するプレフィックス部分を含むデータアイテムの数を前記開始点に足すことにより、前記１又は複数のリスト位置の終了点を計算する、よう構成される、
請求項１に記載のデータベース制御部。
【請求項３】
前記データアイテムのセットは１又は複数回複製され、各複製セットは、同じ情報のデータベースを前記データアイテムのセットとして格納し、異なる固定された順序及び前記データアイテムのセットのデータ要素からプレフィックス部分として指定された異なる１又は２つのデータ要素を有し、
前記順序付きリスト記憶モジュールは、各複製セットについて順序付きリストを格納するよう構成され、前記順序付きリストは、個々にデータアイテムの前記複製セットからのデータアイテムの各々について、前記複製されたデータアイテムが格納される記憶ユニットの識別情報を有し、前記識別情報の順序は、個々の複製データアイテムのプレフィックス部分に適用される順序付けメトリックにより決定され、
前記プレフィックス頻度記憶モジュールは、各複製セットについて、頻度レコードを維持するよう構成され、前記複製セットのプレフィックス部分と、各プレフィックスを有する複製データアイテムの数を記録する、
請求項１又は２に記載のデータベース制御部。
【請求項４】
データアイテムの１又は２つの複製セットが存在し、前記データアイテムのセット及び前記１又は２つの複製セットは、それぞれのデータ要素の固定された順序の各位置に互いに異なるデータ要素を有する、請求項３に記載のデータベース制御部。
【請求項５】
前記リスト位置計算モジュールは、データアイテムのセット又は１若しくは複数の複製セットのうちの１つについて前記頻度レコードを選択し、前記選択された頻度レコードに値が記録されたデータ要素が、前記検索プレフィックス部分で値が指定されたデータ要素と同じになるように、構成される、請求項３又は４に記載のデータベース制御部。
【請求項６】
前記頻度記憶モジュールは、前記１又は複数の頻度レコードの各々について、前記頻度レコードのプレフィックス部分に含まれ値が記録されたデータ要素のうちの１つのプレフィックス検索ｔｒｉｅを格納し、プレフィックス検索ｔｒｉｅの各々について、各リーフに対応するテーブルを格納するよう構成され、
前記プレフィックス検索ｔｒｉｅは、全ての値のデータ要素に対する共通根と、前記データアイテムのセット又は複製セットに現れる異なる値のデータ要素の各々に対応するリーフと、を有し、
各リーフは、データ要素の対応する値を有するデータアイテムのセット又は複製セット内のデータアイテムの数を表す数値を格納し、
各リーフに対応する前記テーブルは、前記リーフに対応する値と共に現れるプレフィックス部分の中の他のデータ要素の値のレコードを格納し、前記他のデータ要素の各値について、前記リーフに対応する値及び前記他のデータ要素の値を有するプレフィックス部分を含むデータアイテムのセット又は複製セットの中のデータアイテムの数を表す共起数を格納する、
請求項１乃至５のいずれか一項に記載のデータベース制御部。
【請求項７】
各リーフに対応する前記テーブルは、ハッシュテーブルである、請求項６に記載のデータベース制御部。
【請求項８】
前記順序付きリストは、前記記憶ユニットから受信した情報に基づき周期的に更新され、各更新の後、前記順序付きリスト内の各占有されたリスト位置の後に所定数の空きリスト位置が続き、
新しいデータアイテムがデータアイテムのセット又は複製セットに追加されるとき、前記新しいデータアイテムが格納される記憶ユニットの識別情報を個々の順序付きリストの空きリスト位置に追加し、前記空きリスト位置は、前記プレフィックス頻度記憶モジュールを参照することにより、個々の占有されたリスト位置のプレフィックス部分に関連して前記新しいデータアイテムのプレフィックス部分に前記順序付けメトリックを適用することにより決定され、直前の占有されたリスト位置が、前記順序付けメトリックに従って前記新しいデータアイテムのプレフィックスに先行する又は等しいプレフィックスを有するデータアイテムの識別情報を格納し、直後の占有されたリスト位置が、前記順序付けメトリックに従って前記新しいデータアイテムのプレフィックスに続く又は等しいプレフィックスを有するデータアイテムの識別情報を格納するようにする、
請求項１乃至７のいずれか一項に記載のデータベース制御部。
【請求項９】
記憶ユニットへのデータアイテムの割り当てを制御し、記憶ユニットへのデータアイテムの前記割り当てを更新するよう構成される適応型ロケータと、
前記１又は複数の順序付きリスト及び前記１又は複数の頻度レコードを更新して前記適応型ロケータにより実行された周期的更新を反映するよう構成される更新モジュールと、
を更に有する請求項１乃至８のいずれか一項に記載のデータベース制御部。
【請求項１０】
前記プレフィックス部分は、３つのデータ要素のうちの最初の２つであり、前記検索プレフィックス部分は、１又は２つの指定されたデータ要素である、請求項１乃至９のいずれか一項に記載のデータベース制御部。
【請求項１１】
前記情報のデータベースはグラフデータベースであり、前記グラフデータベースを符号化するデータアイテムのセットは、それぞれ３つのトリプル要素の各々の値を有するトリプルのセットである、請求項１乃至１０のいずれか一項に記載のデータベース制御部。
【請求項１２】
請求項１乃至１１のいずれか一項に記載のデータベース制御部と、前記複数の記憶ユニットと、を有するデータ記憶システム。    
【請求項１３】
データアイテムのセットとして符号化された情報のデータベースから範囲クエリ結果を得る方法であって、前記データアイテムは、個々の識別情報により互いに区別可能な複数の記憶ユニットの間に分散され、各データアイテムは、３つのデータ要素の各々の値を有し、前記データアイテムのセットは、前記３つのデータ要素の所定の順序を有し、前記順序の最初の１又は２つのデータ要素はプレフィックス部分として指定され、前記複数の記憶ユニットはデータベース制御部に接続され、前記データベース制御部は、
個々に前記データアイテムのセットからのデータアイテムの各々について、前記データアイテムが格納される記憶ユニットの識別情報であって、前記識別情報の順序は、個々のデータアイテムのプレフィックスに適用された順序付けメトリックにより決定される、記憶ユニットの識別情報と、
頻度レコードであって、前記データアイテムのセットのプレフィックス部分として指定されたデータ要素の値及び各プレフィックス部分を有するデータアイテムの数を記録する、頻度レコードと、
を格納し、
前記方法は、
範囲クエリ結果として返される各データアイテムが該データアイテムのプレフィックス部分に含まなければならない検索プレフィックス部分として、１又は複数のデータ要素の各々の値を指定する範囲クエリを受信するステップと、
頻度レコードに基づき、プレフィックス部分に前記検索プレフィックス部分を含むデータアイテムが格納される記憶ユニットの記憶ユニットＩＤにおいて、前記順序付きリスト内の１又は複数のリスト位置を計算するステップと、
前記計算された１又は複数のリスト位置で識別された記憶ユニットから、プレフィックス部分に前記検索プレフィックス部分を含むデータアイテムを要求するステップと、
を有する方法。
【請求項１４】
１又は複数のコンピューティング装置により実行されると、前記１又は複数のコンピューティング装置に請求項１３に記載の方法を実行させる、コンピュータプログラム。
【請求項１５】
１又は複数のコンピューティング装置により実行されると、前記１又は複数のコンピューティング装置に請求項１乃至１１のいずれか一項に記載のデータベース制御部又は請求項１２に記載のデータ記憶システムとして動作させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶及び検索の分野に関する。特に、本発明は、データアイテムのセットとして符号化された情報のデータベースに提出される広範なクエリの処理に関する。
【背景技術】
【０００２】
分散型データ記憶、例えばグラフデータベースは、過去数年間集中的に研究されている。有力な技術的ソリューションは、特定の提示に対して調整される種々のデータ区分アプローチ及び／又はデータキャッシュソリューションを含む。これら２つのソリューションは理想的ではない。データ区分及び／又はクラスタリングは、本質的に複雑であり、一般的にＮＰ完全であり得る。オントロジのためのグラフ表現を用いるとき、複数の記憶ユニットに渡りデータバランスを維持しデータの重複を最小限に抑え、同時に分散処理中にいかなる知識も失われないことを保証することは困難である。したがって、サブグラフ間参照が頻繁に生じ、グラフ区分及びクラスタリングアプローチの大部分はデータノード間通信を有意に低減することができない。同様に、広く用いられるキャッシュアルゴリズムは、グラフ表現のために設計されていない。このような問題は、グラフデータに限られず、他の種類の分散型データ記憶の場合にも生じ得る。
【０００３】
キー値記憶のような分散型データ記憶にデータをどのように格納し及びデータを読み出すかという幾つかのアプローチがある。１つのアプローチは、実行範囲クエリをキーに渡り可能にする順序付きキー／値記憶を用いることである。このアプローチは、システムがサーバセット全体からデータを読み出しフィルタリングする必要がないので、スキャン動作の性能を向上する。別のアプローチは、通常（つまり、順序付きでない）キー／値記憶にデータを格納することである。キーの順序が保持される必要がないので、リード動作は、一緒にリードされる同一場所にあるデータにより最適化できる。このアプローチは、分散型データ記憶の横断時間を最適化する。しかしながら、将来のリード動作を最適化するために周りの（同一場所にある）データを移動しながら順序付きデータセットを維持することは困難であるため、一般的に、キーの順序を遵守せず、スキャン動作に対しては高価である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、範囲クエリを処理するデータベース制御部、方法及びプログラムを提供する。
【課題を解決するための手段】
【０００５】
本発明の実施形態は、データアイテムのセットとして符号化された情報のデータベースのためのデータベース制御部を含む。前記データアイテムは、個々の識別情報により互いに区別可能な複数の記憶ユニットの間で分散され、各データアイテムは、２以上のデータ要素のうちの各々の値を有し、前記データアイテムのセットは、前記２以上のデータ要素の所定の順序を有し、該順序の最初の１又は２つのデータ要素は、プレフィックス部分として指定される。データベース制御部は、範囲クエリ結果として返される各データアイテムがプレフィックス部分に含まなければならない検索プレフィックス部分として、１又は複数のデータ要素のうちの各々の値を指定する範囲クエリを受信するよう構成されるクエリ受信モジュールと、順序付きリストを格納するよう構成される順序付きリスト記憶モジュールであって、前記順序付きリストは、前記データアイテムのセットからのデータアイテムの各々について個々に、前記データアイテムが格納される記憶ユニットの識別情報を格納し、前記識別情報の順序は、個々のデータアイテムのプレフィックス部分に適用された順序付けメトリックにより決定される、順序付きリスト記憶モジュールと、頻度レコードを維持するよう構成され、前記データアイテムのセットのプレフィックス部分として指定されたデータ要素の値と各プレフィックス部分を有するデータアイテムの数とを記録する、プレフィックス頻度記憶モジュールと、前記頻度レコードに基づき、プレフィックス部分に前記検索プレフィックス部分を含むデータアイテムが格納された記憶ユニットの識別情報における前記順序付きリスト内の１又は複数のリスト位置を計算するよう構成されるリスト位置計算モジュールと、前記計算された１又は複数のリスト位置で識別された記憶ユニットから、プレフィックス部分に前記検索プレフィックス部分を有するデータアイテムを要求するよう構成される結果読み出しモジュールと、を有する。
【０００６】
有利なことに、本発明の実施形態は、スキャンするためにクエリを個々の記憶ユニットにブロードキャストする前に、どの記憶ユニットがクエリを満たすデータアイテムを格納するかを定め、それにより結果読み出しモジュールに、クエリ結果に対する要求をクエリを満たすデータアイテムを格納すると分かっている記憶ユニットに限定することにより、効率的な方法で範囲クエリを処理することを可能にする。しかしながら、範囲クエリの処理のために最適化される既知のデータベース記憶システムと異なり、本発明の実施形態は、データアイテム自体が特定の順序で格納されることを要求しない。したがって、記憶ユニットの間でデータアイテムの分散の柔軟性が実現する。例えば、データアイテムは、グラフトラバース動作における共起の可能性に基づきグループ化され得る。次に、各グループは、異なる記憶ユニットに格納される。したがって、記憶ユニットの境界を跨る高価なグラフトラバース動作は削減される。しかし、データは依然として効率的にクエリできる。纏めると、本発明の実施形態は、（記憶ユニット識別情報の順序付きリストに基づき）データアイテムに渡る順序付けを組み合わせる。それにより、（データアイテムが任意の順序で格納可能なお陰で）データを動的に同一場所に配置でき、同時に、範囲クエリの性能を最大化するキー（プレフィックス部分）に渡る順序付けを提示する。
【０００７】
本発明の実施形態は、順序付きキー値記憶（記憶ユニット識別情報をインデックス付けするために用いられるプレフィックス部分）をデータ位置の柔軟性と組み合わせる（データアイテムを格納する順序についての要求はない）。頻度レコード内に格納されたプレフィックス部分は、記憶ユニット識別情報の順序付きリストのインデックスを形成し、特定のプレフィックス部分を有するデータアイテムを格納する記憶ユニットの識別情報を決定可能にする。
【０００８】
順序付けメトリックは、どれが他者より高い又は低い値を有するかを定めるためにデータアイテム間又はデータアイテムの部分間の比較を可能にするルールセットである。したがって、データアイテム又はデータアイテムの部分は、順序付けメトリックに関する値を有すると考えられる。順序付けメトリック値は、データアイテム自体の固有の特性であっても良い。例えば、データアイテムが英数字シンボルストリングである場合、順序付けメトリックは、英数字準であっても良い。したがって、各ストリングは、又は１つのストリングの各部分は、英数字の値又は英数字順の順序付けメトリックの値である／を表す。
【０００９】
例えば、データの実際の記憶位置は、同じグラフトラバース動作で頻繁にアクセスされたデータアイテムを同一場所に配置する動的ロケータにより管理されても良い。したがって、本発明の実施形態は、特定の順序で格納されているデータアイテムに依らずに、格納されたデータの効率的な範囲クエリを可能にする。
【００１０】
有利なことに、本発明の実施形態は、データベース制御部が、どの記憶ユニットが特定のプレフィックス部分（検索プレフィックス部分）を有するデータアイテムを格納するかを定めることができるメカニズムを提供する。したがって、クエリ結果は、範囲クエリを満たすデータアイテムを格納すると分かっている記憶ユニットのみから要求される。ネットワークトラフィックは削減され、（範囲クエリを満たすデータアイテムを格納していない記憶ユニットにおいて）不必要なスキャンを実行するために必要な処理は除去される。
【００１１】
データアイテムは、データベースの所定のフォーマットを有する情報片又は情報の提示である。例えば、データアイテムは、１又は複数のデータ要素、より詳細には、１又は複数のデータ要素の値を含む。ここで、データ要素は、所定のフィールド、情報の種類、ステートメント若しくは情報片の構成要素であり、データ要素の値がデータアイテムに記録／格納される。
【００１２】
識別情報は、該識別情報が関連する記憶ユニットを残りの記憶ユニットから区別する任意の形式の情報であり得る。例えば、識別情報は、物理アドレス若しくは物理アドレスの一部、ソケットアドレス（又はその一部）、又は特定の他の形式のＩＤであり得る。テーブル又はハッシュマップ又は特定の他の追加情報ソースが、識別情報から記憶ユニットの実際のアドレス指定可能な場所を発見するために必要とされても良い。
【００１３】
頻度レコード記憶モジュールは、指定された検索プレフィックス部分から１又は複数のインデックスを計算できるようにする情報を格納する。１又は複数のインデックスは、指定された検索プレフィックス部分を有するデータアイテムを格納する記憶ユニットの識別情報を格納する順序付きリスト内のエントリに対応し又は該エントリを識別する。頻度レコード記憶モジュールにより格納される情報の例示的な実施形態は、プレフィックスインデックス付けツリー／プレフィックス検索ツリー／プレフィックスｔｒｉｅ／プレフィックス検索ｔｒｉｅ／プレフィックスインデックス付けｔｒｉｅである。１又は複数のインデックスは、順序付きリスト内の位置又はエントリをマッピングする又は識別するデータの形式である。
【００１４】
実施形態は、グラフデータベースであり且つグラフデータベースを符号化するデータアイテムのセットがそれぞれ３つのトリプル要素の各々の値を有するトリプルセットである情報のデータベースを含む。トリプル要素は、データ要素の例である。
【００１５】
関係型データベースは、データを行と列で格納する。行及び列は、データを格納する前に定める必要のあるテーブルを構成する。テーブルの定義及びこれらのテーブルに含まれるデータ間の関係は、スキーマと称される。関係型データベースは、固定スキーマを用いる。或いは、データグラフは、グラフデータベース又はグラフデータセットとして参照され、関係型データベースの代替データ表現であり、意味的知識モデルの表現を提供する。グラフデータベースは、データをノード及びアークの形式で格納することにより、関係型データベースの重要な拡張を表す。ここで、ノードはエンティティ又はインスタンスを表し、アークは任意の２個のノード間の特定種類の関係を表す。無向グラフでは、ノードＡからノードＢへのアークは、ノードＢからノードＡへのアークと同じであると考えられる。有向グラフでは、２つの方向は別のアークとして扱われる。
【００１６】
グラフデータベースは、概して２つの主な種類に分類できる広範な種類の異なるアプリケーションで用いられる。第１の種類は、知的意思決定支援及び自己学習のようなクラス記述子の大規模な集合体（「知識ベースアプリケーション」と称される）を有する複雑な知識ベースシステムを有する。第２の種類は、社会的データ及びビジネスインテリジェンスのようなトランザクションデータに対するグラフ検索の実行を含むアプリケーション（「トランザクションデータアプリケーション」と称される）を有する。多くのアプリケーションは、両方の種類を表し得る。しかしながら、大部分のアプリケーションは、主に知識ベース又はトランザクションデータアプリケーションのいずれかで特徴付けられ得る。グラフデータベースは、種々の分野の膨大な構造化又は非構造化データを格納できる大規模な「意味ネットワーク」を維持するために用いることができる。意味ネットワークは、知識表現の形式として用いられ、コンセプトを表すノード及びコンセプト間の意味関係を表すアークを有する有向グラフである。
【００１７】
記憶のためにグラフデータベースをエンコードする幾つかのアプローチがある。グラフデータは、多次元アレイとして又は他のシンボルにリンク付けされたシンボルとしてメモリに格納されても良い。別の形式のエンコーディングは、各々指定された種類のオブジェクトの有限シーケンス又は順序付きリストである「タプル」の使用である。ｎ個のオブジェクトを含むタプルは、「ｎタプル」として知られる。ここで、ｎは零より大きい任意の非負整数である。長さ２のタプル（２タプル）は、通常、ペアと呼ばれる。３タプルはトリプルと呼ばれ、４タプルはクワドラプルと呼ばれ、以降同様である。
【００１８】
トリプルは、それぞれ指定された種類の３つのトリプル要素（タプル）を有する。種類は、トリプル自体の中のデータにより（つまり、「種類（type）＝値（value）」と等価な形式でデータを格納することにより）指定されても良く、トリプルに又はトリプルが属するトリプルセットに適用するためにシステム内で知られているメタデータであっても良い。例えば、各トリプルは、グラフデータベースを完全に符号化するトリプルセットに属しても良い。また、各セットは、それぞれ３つのトリプル要素の値を同じ（つまり固定された）順に格納するトリプルを有することが分かっている。したがって、最初の値は、トリプル要素の最初の種類であることが分かっており、以下同様である。
【００１９】
用語「トリプル要素」は、一般的に、トリプル要素の種類、例えば主語、目的語又は述語を表す。トリプル要素の特定のインスタンスは、トリプル要素の値として参照される。例えば、３つのトリプル要素は、主語、目的語及び述語であっても良い。したがって、特定のトリプルは、主語、目的語及び述語の各々の値を有する。記載されるエンティティは、トリプルの主語として表されても良い。識別されたプロパティの範囲は、目的語として表されても良い。また、範囲とエンティティとの間の関係は、述語として表されても良い。トリプルは、グラフデータを複数の主語−述語−目的語の表現として特徴付けることにより、グラフデータのエンコードを提供する。例えば、主語は、（例えば、ＵＲＩを介して）ウェブリソースを示しても良く、述語はリソースの個々の特性、特徴又は状況を示し、目的語は、該特性、特徴又は状況のインスタンス、範囲、又は例を示す。言い換えると、トリプルステートメントの集合は、元来、方向性グラフデータを表す。ＲＤＦ標準は、このようなトリプルの形式的構造を定める。本発明の実施形態におけるトリプルは、ＲＤＦトリプルであっても良い。
【００２０】
３つのトリプル要素のうち固定された順序で最初の１つ又は最初の２つのトリプル要素は、プレフィックス部分として指定され、本願明細書に記載される本発明の実施形態においてインデックス付けの目的で用いられる。したがって、プレフィックス部分は、トリプルセットの中の各トリプル内の特定の値に適用されるラベルである。
【００２１】
任意で、前記プレフィックス頻度記憶モジュールは、前記順序付けメトリックを前記データアイテムの前記プレフィックス部分に適用することにより決定された順序で前記頻度レコードを維持するよう構成され、前記リスト位置計算モジュールは、前記順序付けメトリックにより決定された順序で前記検索プレフィックス部分に先行するプレフィックス部分を有するデータアイテムの数を加算することにより、前記１又は複数のリスト位置の開始点を計算し、前記検索プレフィックス部分を有するプレフィックス部分を含むデータアイテムの数を前記開始点に足すことにより、前記１又は複数のリスト位置の終了点を計算する、よう構成される。
【００２２】
有利なことに、以上に概要を説明した特定の形式の頻度レコードは、特定のプレフィックス部分に対応するリスト位置を特定し、したがって該プレフィックス部分を有するトリプルを格納する記憶ユニットを識別するために、頻度レコード内の情報を有効に使う単純な手順を提供する。
【００２３】
特定の実装オプションとして、データアイテムのセットは、１又は複数回複製されても良い。各複製セットは、データアイテムのセットと同じ情報のデータベースを格納し、前記データアイテムのセットと異なる固定された順序及びプレフィックス部分として指定された異なる１又は２つのデータ要素を有し、順序付きリスト記憶モジュールは、各複製セットについて順序付きリストを格納し、前記順序付きリストは、データアイテムの複製セットからのデータアイテムの各々について個々に、複製データアイテムが格納される記憶ユニットの識別情報を有し、前記識別情報の順序は、個々の複製データアイテムのプレフィックス部分に適用された順序付けメトリックにより決定され、前記プレフィックス頻度記憶モジュールは、各複製セットについて頻度レコードを維持するよう構成され、前記複製セットのプレフィックス部分及び各プレフィックスを有する複製データアイテムの数を記録する。
【００２４】
有利なことに、データアイテムの種々のセット及び複製セットは、指定された異なるデータ要素の値を有する範囲クエリを、効率的な方法で検索することを可能にする。データアイテムのセットのプレフィックス部分として指定されたデータ要素は、値が範囲クエリで指定できるデータ要素であり、範囲クエリは効率的に処理される。したがって、複製セット及び複製セットをインデックス付けする対応する順序付きリストは、本発明の実施形態の、範囲クエリを効率的に処理する能力を強化する。
【００２５】
データアイテムの複製セットがどのように実現されるかの特定の例として、実施形態は、１又は２つの複製データアイテムセットを含み、データアイテムのセット及び１又は２つの複製データセットは、データ要素の個々の固定された順序の各位置において互いに異なるデータ要素を有する。つまり、セットは、それぞれ、同じデータ要素を有するが、データ要素が現れる順序は各セットで異なる。
【００２６】
上述のデータアイテムのセットの特定の構成は、範囲クエリの効率的な処理から得られる性能の利益と、セットの複製及び順序付きリストにより多くの記憶空間を割く性能オーバヘッドとの間のバランスを最適化する。
【００２７】
データベース制御部の動作を複数のデータアイテムセットに更に合わせるために、リスト位置計算モジュールは、データアイテムセットのうちの１つ又は１若しくは複数の複製セットに対して頻度レコードを選択し、値が選択された頻度レコードに記録されているデータ要素が、値が検索プレフィックス部分で指定されたデータ要素と同じになるようにする。
【００２８】
上述のように、本発明の実施形態は、順序付きリスト、頻度レコード、及びデータアイテムセットを用いて、値が検索プレフィックス部分で指定されたデータ要素に依存して、クエリに応答するよう構成される。値が範囲クエリで指定された同じデータ要素の順序付きリスト及び頻度レコードは、検索プレフィックス部分に一致するプレフィックス部分を有するデータアイテムを有する記憶ユニットの識別情報を見付けるために利用される。
【００２９】
任意で、頻度レコードは、プレフィックスツリーにより実現されても良く、プレフィックスｔｒｉｅ、プレフィックス検索ツリー、又はプレフィックス検索ｔｒｉｅとも表される。例えば、前記頻度記憶モジュールは、前記１又は複数の頻度レコードの各々について、前記頻度レコードのプレフィックス部分に含まれ値が記録されたデータ要素のうちの１つのプレフィックス検索ｔｒｉｅを格納し、プレフィックス検索ｔｒｉｅの各々について、各リーフに対応するテーブルを格納するよう構成され、前記プレフィックス検索ｔｒｉｅは、全ての値のデータ要素に対する共通根と、前記データアイテムのセット又は複製セットに現れる異なる値のデータ要素の各々に対応するリーフと、を有し、各リーフは、データ要素の対応する値を有するデータアイテムのセット又は複製セット内のデータアイテムの数を表す数値を格納し、各リーフに対応する前記テーブルは、前記リーフに対応する値と共に現れるプレフィックス部分の中の他のデータ要素の値のレコードを格納し、前記他のデータ要素の各値について、前記リーフに対応する値及び前記他のデータ要素の値を有するプレフィックス部分を含むデータアイテムのセット又は複製セットの中のデータアイテムの数を表す共起数を格納しても良い。
【００３０】
プレフィックス検索ｔｒｉｅは、最初のキャラクタから開始して進み、データ要素の任意の値の対が、該値の対が互いに異なるまで、ルートからｔｒｉｅ内の共通経路を共有するように構成される。ｔｒｉｅは、記憶空間の観点で効率的な方法で、情報、この場合特定のデータ要素の異なる値を格納するメカニズムを提供する。さらに、ｔｒｉｅは、ｔｒｉｅが形成されるデータ要素の各値を有するセット内のデータアイテムの数を表す情報を格納し体系化するメカニズムを提供する。
【００３１】
任意で、各リーフに対応するテーブルは、ハッシュテーブルであっても良い。ハッシュテーブルは、テーブルデータを格納する空間的に効率的なメカニズムを提供する。詳細には、トリプル要素のうちの別の１つと一緒に、トリプルセットのプレフィックス部分の一部として割り当てられた、トリプル要素のうちの特定の１つに対するプレフィックス検索ｔｒｉｅでは、各リーフは（ここで、リーフは、トリプル要素のうちの特定の１つの値を表す／に対応する）、ハッシュテーブル又はハッシュテーブルへのリンクを格納する。ハッシュテーブルのキーは、少なくとも、トリプル要素のうちの特定の１つの値を有するトリプルセット内のプレフィックス部分で生じるトリプル要素の別の１つの値であり、場合によっては、トリプル要素のうちの別の１つの全ての値である。各キーを介してアクセスされる値（キー値では、トリプル要素の値と混同しないように）は、ハッシュテーブルにリンクする又はハッシュテーブルを格納するリードにより示されるトリプル要素のうちの１つの値がキーを形成する別のトリプル要素の値と共に生じるトリプルセット内のプレフィックス部分の数である。
【００３２】
新しい情報はデ―タベースに追加されても良い。したがって、データベース制御部は、新しいデータを収容するために特定の処理動作を実行するよう要求される。例えば、前記順序付きリストは、前記記憶ユニットから受信した情報に基づき周期的に更新されても良く、各更新の後、前記順序付きリスト内の各占有されたリスト位置の後に所定数の空きリスト位置が続き、新しいデータアイテムがデータアイテムのセット又は複製セットに追加されるとき、前記新しいデータアイテムが格納される記憶ユニットの識別情報を個々の順序付きリストの空きリスト位置に追加し、前記空きリスト位置は、前記プレフィックス頻度記憶モジュールを参照することにより、個々の占有されたリスト位置のプレフィックス部分に関連して前記新しいデータアイテムのプレフィックス部分に前記順序付けメトリックを適用することにより決定され、直前の占有されたリスト位置が、前記順序付けメトリックに従って前記新しいデータアイテムのプレフィックスに先行する又は等しいプレフィックスを有するデータアイテムの識別情報を格納し、直後の占有されたリスト位置が、前記順序付けメトリックに従って前記新しいデータアイテムのプレフィックスに続く又は等しいプレフィックスを有するデータアイテムの識別情報を格納するようにする。
【００３３】
有利なことに、空きリスト位置は、新しいトリプルがトリプルセットに追加される度に順序付きリストの完全な更新を実行する必要を取り除く。勿論、実施形態は、順序付きリストに維持されている順序に依存する。したがって、リスト位置計算ユニットは、どのリスト位置がどのプレフィックス部分に対応するかを確実に決定できる。空きリスト位置は、特定の時点まで（特定の時点は、新しいトリプルの追加で１つの空きリスト位置が必要な場合に、空きリスト位置が存在しないときである）、新しいトリプルが追加されるとき順序を維持できるようにする。空きリスト位置の欠如により、リストへの新しいエントリが正しい位置で行うことが出来ないと、新しい空きリスト位置を生成するために、順序付きリストの完全な再構成が必要であっても良い。勿論、新しい空きリスト位置を生成するための順序付きリストの更新も、例えばシステムアイドル時間に実行されても良い。
【００３４】
データアイテムの（又はデータアイテムに対応する）識別情報は、データアイテムが格納されている記憶ユニットの識別情報である。
【００３５】
本発明の実施形態は、データアイテムの特定の順序を維持する必要のような制約を有しないで、データを分布するための自由を、他の機能モジュールに可能にする方法で、実施されても良い。任意で、実施形態は、これらの更なる機能モジュールを有しても良い。実施形態は、記憶ユニットへのデータアイテムの割り当てを制御し、記憶ユニットへのデータアイテムの前記割り当てを更新するよう構成される適応型ロケータと、前記１又は複数の順序付きリスト及び前記１又は複数の頻度レコードを更新して前記適応型ロケータにより実行された周期的更新を反映するよう構成される更新モジュールと、を更に有しても良い。
【００３６】
有利なことに、適応型ロケータは、トリプルを記憶ユニットに割り当てるメカニズムを提供する。どのトリプルをどの記憶ユニットに割り当てるかの決定は、例えば、グラフトラバース／トリプル対のリード動作における前の共起頻度に基づいても良い。したがって、前の活動に基づき、一緒にアクセスされる可能性の高いトリプルは、一緒に格納される。記憶ユニット境界に跨るグラフトラバース動作の回数を最小化することにより、性能の利益が生じる。
【００３７】
データアイテム及びデータ要素の多くの異なる構成が予測できる。しかしながら、実施形態は、３つのデータ要素のうちの最初の２つをプレフィックス部分として指定しても良く、このような場合には、検索プレフィックス部分は、１又は２つの指定データ要素であっても良い。
【００３８】
有利なことに、プレフィックス部分が３つのデータ要素のうちの最初の２つであることは、１又は２つのデータ要素のうちのいずれかの値を指定する範囲クエリが効率的に処理できること、及び順序付きリスト及び頻度レコードを格納するために必要な空間が非常に大きくならないことを保証する。
【００３９】
任意で、トリプルは、トリプル要素の値毎にサブストリングを有するストリングとして格納される。ストリングオブジェクトは、速く比較され、処理動作の要件に従って操作できる（例えば、分割され又は連結される）。トリプル全体（又は、実際にはプレフィックス部分又は検索プレフィックス部分）は、１つの値の終わり又は別の値の始めを示すために用いられる空白を有する単一のストリングオブジェクトであっても良い。各ストリングオブジェクトは、値がストリングオブジェクトに格納されているトリプル要素の順序の指標を含み又は該指標と共に格納されても良い。代替で、どの値がトリプルに現れるかの順序は、単に、トリプルが属するトリプルセットの既知の特性であっても良い。
【００４０】
本発明の別の態様の実施形態は、本発明を具現化するデータベース制御部と、複数の記憶ユニットと、を有するデータ記憶システムを有する。      
記憶ユニットは、それぞれ、コンピューティングリソースであっても良い。例えば、それらは、それぞれ、プロセッサ、メモリ及び／又はネットワークインタフェースカード、マザーボード、入力／出力装置のような追加構成要素に加えて、記憶ユニットを有しても良い。
【００４１】
このようなコンピューティング装置は、例えばサーバであっても良い。記憶機能に加えて、コンピューティング装置は、処理動作を実行し、記憶ユニットの分散型ネットワーク内の他の記憶ユニットと及び／又は中央制御部と通信するよう構成される。
【００４２】
実施形態は、本発明を具現化するデータベース制御部と、本発明を具現化する複数のコンピューティング装置と、を有し、記憶ユニットの分散型ネットワークとして動作するよう構成されるシステムの形式で提供されても良い。
【００４３】
このような実施形態では、複数のコンピューティング装置は、データベース制御部を形成するよう協調して動作するよう構成されても良い。
【００４４】
本発明の別の態様の実施形態は、データアイテムのセットとして符号化された情報のデータベースから範囲クエリ結果を得る方法を含む。前記データアイテムは、個々の識別情報により互いに区別可能な複数の記憶ユニットの間で分散され、各データアイテムは、３つのデータ要素のうちの各々の値を有し、前記データアイテムのセットは、前記３つのデータ要素の所定の順序を有し、該順序の最初の１又は２つのデータ要素は、プレフィックス部分として指定され、複数の記憶ユニットはデータベース制御部に接続され、前記データベース制御部は、順序付きリストを格納し、前記順序付きリストは、データアイテムのセットからのデータアイテムの各々について個々に、データアイテムが格納される記憶ユニットの識別情報であって、前記識別情報の順序は個々のデータアイテムのプレフィックスに適用される順序付けメトリックにより決定される、識別情報と、頻度レコードであって、データアイテムのセットのプレフィックス部分として指定されるデータアイテムの値及び各プレフィックス部分を有するデータアイテムの数を記録する、頻度レコードと、を有する。方法は、範囲クエリ結果として返される各データアイテムがプレフィックス部分に含まなければならない検索プレフィックス部分として、１又は複数のデータ要素のうちの各々の値をしていすｒう範囲クエリを受信するステップと、頻度レコードに基づき、プレフィックス部分に検索プレフィックス部分を含むデータアイテムが格納される記憶ユニットの記憶ユニットＩＤにおいて、順序付きリスト内の１又は複数のリスト位置を計算するステップと、計算した１又は複数のリスト位置で識別される記憶ユニットからプレフィックス部分に検索プレフィックス部分を含むデータアイテムを要求するステップと、を含む。
【００４５】
本発明の別の態様の実施形態は、１又は複数のコンピューティング装置により実行されると、前記１又は複数のコンピューティング装置を本発明を具現化するデータベース制御部として機能させる、コンピュータプログラムを含む。
【００４６】
本発明の別の態様の実施形態は、１又は複数のコンピューティング装置により実行されると、前記１又は複数のコンピューティング装置を本発明を具現化するデータベース制御部及び／又はデータ記憶システムとして機能させる、コンピュータプログラムを含む。
【００４７】
さらに、本発明の実施形態は、コンピューティング装置の分散型ネットワークにより実行されると、コンピューティング装置の分散型ネットワークに、本発明を具現化するシステムとして機能させる、コンピュータプログラムスーツを有しても良い。
【００４８】
さらに、本発明の実施形態は、記憶ユニットの分散型ネットワークを有するコンピューティング装置のシステムにより実行されると、前記システムに、本発明を具現化する方法を実行させるコンピュータプログラム又はコンピュータプログラムスーツを有する。
【００４９】
態様（ソフトウェア／方法／装置）が別個に議論されたが、１つの態様に関連して議論されたその特徴及び影響は、他の態様にも等しく適用できる。したがって、方法の特徴が議論される場合、装置の実施形態はその特徴を実行する又は適切な機能を提供するよう構成されるユニット又は装置を有すること、及びプログラムは該プログラムが実行されるコンピューティング装置に前記方法の特徴を実行させるものと解釈される。
【００５０】
上述の態様のいずれにおいても、種々の特徴は、ハードウェアで、又は１又は複数のプロセッサで動作するソフトウェアモジュールとして実装されても良い。一態様の特徴は、他の態様のいずれにも適用できる。
【００５１】
本発明は、上述の任意の方法を実行するコンピュータプログラム又はコンピュータプログラムプロダクト、及び上述の任意の方法を実行するプログラムを格納しているコンピュータ可読媒体も提供する。本発明を実施するコンピュータプログラムは、コンピュータ可読媒体に格納されてもよい。或いは、例えば、インターネットウェブサイトから提供されるダウンロード可能なデータ信号のような信号形式又は任意の他の形式であってもよい。
【図面の簡単な説明】
【００５２】
本発明の特徴は、単なる例として添付の図面を参照して以下に説明される。
【図１】本発明を具現化するデータベース制御部を有するデータ記憶システムを示す。
【図２】本発明の実施形態におけるプレフィックスツリーを示す。
【図３】本発明の実施形態の例示的なハードウェア構成を示す。
【発明を実施するための形態】
【００５３】
データ記憶システムは、データベース制御部１０及び複数の記憶ユニット３０を有する。
【００５４】
複数の記憶ユニット３０は、互いに及びデータベース制御部と、典型的な目的のために図１にバスとして示される有線若しくは無線ネットワークを介してデータ通信を行う。必要に応じて及び個々のモジュールはそれらがそれらの機能を実行する際に必要なとき、データを交換するよう構成されると仮定されるので、データベース制御部１０内のデータ接続は示されない。アプリケーション２０は、データ記憶システムの外部又は内部にあると考えられても良く、範囲クエリのソースであるとき重要である。アプリケーション２０は、データ記憶システム、例えばＳＰＡＲＱＬクエリインタフェース内で動作する機能層であり、外部アプリケーションからクエリを受信し、それらをクエリ受信モジュール１２に転送するのに適した形式に処理する。
【００５５】
データベース制御部１０は、符号化されたデータベース情報を格納する記憶ユニットに接続可能な機能エンティティである。特定の実施形態の説明では、情報のデータベースはグラフデータベースであり、データアイテムはトリプルである。トリプルは、特にＲＤＦトリプルであっても良い。データベース制御部１０は、範囲クエリを処理するよう構成される。他のエンティティは、他のデータベース制御機能、例えば新しいデータの挿入及びデータ更新、アプリケーションのためのアクセス処理を担っても良い。したがって、本発明を具現化するデータベース制御部１０は、必ずしもデータベースに対する排他的制御を有しないで、単に特定の機能に対する制御を有する。データベース制御部１０は、専用ハードウェア装置として、又はトリプルを格納する記憶ユニットを有するサーバを含む１又は複数のコンピュータで実行するソフトウェアにより実現されても良い。データベース制御部は、マスタサーバ、又は記憶ユニット３０の制御を担う特定の他の中央装置で動作する機能モジュールであっても良い。
【００５６】
データベース制御部１０は、クエリ受信モジュール１２、順序付きリスト記憶モジュール１４、プレフィックス頻度記憶モジュール１６、リスト位置計算モジュール１８、及び結果読み出しモジュール１９を有する。任意で、データベース制御部は、複数の記憶ユニット３０の間でトリプルの記憶位置を管理するよう構成される適応型ロケータ１７、を更に有しても良い。適応型ロケータ１７は、取得した又は観察した性能統計に基づき、同じグラフトラバース動作で頻繁にアクセスされたトリプルを同一場所に配置するよう構成されても良い。例えば、適応型ロケータ１７は、グラフデータベースを符号化するトリプルセットにクラスタリングアルゴリズムを適用し、各クラスタを複数の記憶ユニット３０の中の異なる記憶ユニット３０に割り当てるよう構成されても良い。適応型ロケータ１７は、図１に破線の四角で示されるように任意機能である。
【００５７】
データアイテムの実際の記憶位置は、データアイテム間の関連付けの強度の評価に基づき同じサーバ／記憶ユニットにデータアイテムを同一場所に配置する適応型ロケータ１７により管理される。例えば、可能な技術の中でも特に、関連付け強度は、データアイテムの意味特性、オントロジ特性を比較することにより、又はデータベースリード動作を表す履歴データを分析することにより、評価されても良い。もちろん、１より多い有力要因が、データアイテム間の関連付け強度を測定する関連付けメトリックに組み込まれても良い。１より多い有力要因は、関連付けメトリックスコアを計算する際に、重み付けされ結合されても良い。特定の実装例では、適応型ロケータ１７は、同じリード動作でどのデータアイテムが頻繁にアクセスされたかを決定し、そのようなデータアイテムを同じ記憶ユニットに同一場所に配置するために、履歴データを用いても良い。
【００５８】
適応型ロケータ１７は、データアイテムを物理的位置に割り当てるために処理を実行する。物理的位置は順序付きリストに格納され、個々のデータアイテムのプレフィックス部分によりインデックス付けされる。したがって、順序付きリストは、適応型ロケータ１７により実行された処理の結果を格納する。もちろん、特定の他の機能モジュール又はユニットが、データアイテムの物理的位置を（どの記憶ユニットにデータアイテムが格納されるかという観点で）管理するために用いられても良い。
【００５９】
本発明の実施形態は、順序付けメトリックにより決定されるデータアイテムの順序を維持しなければならないという制約を有しないで、データアイテムを記憶ユニットに割り当てるために任意のアルゴリズム、システム、原理、又はモジュールを用いる柔軟性を有する。唯一の制約は、運用上のもの、つまり、決定されると、記憶位置（識別情報）が順序付きリストに格納されることである。したがって、本発明の実施形態は、プレフィックス部分をインデックス付けメカニズムとして用いることにより物理的位置が順序付きリストから読み出し可能なので、特定の順序で格納されているデータアイテムに依存しない、格納されたデータアイテムの効率的な範囲クエリを可能にする。
【００６０】
適応型ロケータ１７の機能は、２つの主な構成要素を有すると考えられる。第一に、データアイテム間の関連付け強度の計算である。つまり、データアイテム対がどれだけ密接に関連付けられているかを表す関連付けメトリックのスコアを計算することである。例えば、このような関連付けメトリックは、同じリード動作の一部として、データアイテム対がどれだけ頻繁にアクセスされたかに比例しても良い。第二に、関連付けメトリックスコアを用いて、どのデータアイテムが同じ記憶ユニットに同一場所に配置されるべきかを決定するために、クラスタリングアルゴリズムのようなアルゴリズムを適用することである。例えば、適応型ロケータ１７は、データアイテム対の複数の順列について関連付けメトリックのスコアを計算し、データアイテム対の複数の順列についての関連付けメトリックのスコアに依存して同一場所に配置するデータアイテムを選択することにより、データアイテムセットの中から同じ記憶ユニットに同一場所に配置するデータアイテムを選択するよう構成されても良い。
【００６１】
関連付けメトリックは（又は２つのデータアイテムがどれだけ密接に「リンク付けされているか」又は「関連付けられているか」を評価するためにどのプロセスが用いられるとしても）、データベース又はデータアイテムセットに対して実行されたリード動作を表す履歴データのような、特にどのデータアイテムが各リード動作で読み出されたかを指定できる情報源を用いるメカニズムを提供する。２つのデータアイテム間の関連付けメトリックのスコアは、２つのデータアイテムがどれだけ密接に関連付けられているかを表す。履歴データに基づく特定の実装では、２つのデータアイテム間の関連付けメトリックのスコアは、前のリード動作で２つのデータアイテムがどれだけ密接に関連付けられたかを表す。
【００６２】
適応型セグメントロケータモジュールは、動作中、データアイテムを該データアイテムの現在の記憶ユニットに保持するか否か、又はデータアイテムを別の記憶ユニットに移動するか否かを決定するために同じ検討材料を用いるよう構成されても良い。
【００６３】
適応型ロケータ１７は、同じ記憶ユニットに同一場所に配置されるデータアイテムの対の間の関連付けメトリックの総スコアを最適化するアルゴリズムを実行することにより、各データアイテムが格納されるべき記憶ユニットを選択するよう構成されても良い。
【００６４】
このようなアルゴリズムは、データベース内の同一場所に配置されたデータアイテムの各対の間の関連付けメトリックの最適合計スコアを決定するために用いられても良い。或いは、アルゴリズムは、他のポリシを続行するよう構成可能であっても良い。例えば、他のポリシは、新しい記憶ユニットがシステムに追加され、適応型ロケータ１７が、新しい記憶ユニットに格納すべき所定数の又は所定合計記憶領域のデータアイテムを決定するためにアルゴリズムを実行するよう構成されても良い。最適合計スコアが決定される多数の異なる方法が存在する。また、各々の場合に、このような最適化を追求するよう構成されたアルゴリズムは適応型ロケータ１７により実行されても良いことが理解される。例えば、最適化は、同じ記憶ユニットに同一場所に配置されたデータアイテムセットの中のデータアイテム対の間の関連付けメトリックの最高の可能な合計スコアであっても良い。代替で、関連付けメトリックの閾スコアが存在し、適応型ロケータ１７は、同じ記憶ユニットに同一場所に配置される、閾スコアを超える関連付けメトリックスコアを有するデータアイテム対の数を最大化するよう構成されても良い。例えば、アルゴリズムは、記憶ユニットに存在する対の間の関連付けメトリックのスコアを最大化するデータアイテムを単に移動しても良く、又はデータアイテムを該データアイテムの現在の場所から移動することの影響を考慮して、最終的な利益をもたらす移動のみが実行されるようにしても良い。適応型セグメントロケータモジュール１７でアルゴリズムを実行することにより関連付けメトリックを利用する可能性は限りなく存在することが理解される。
【００６５】
さらに、関連付けメトリックの設計は、設定可能であり、特定の実装に合うように設計できることが理解される。例えば、データベースに対して実行されたリード動作を表す履歴データは、同じリード動作で読み出されたデータアイテムのレコードを有しても良く、データアイテム対の関連付けメトリックのスコアは、データアイテム対のうちの両者が同じリード動作で読み出された回数に比例する構成要素を有する。
【００６６】
クエリ受信モジュール１２は、アプリケーション２０から範囲クエリを受信するよう構成される。クエリ受信モジュール１２は、トリプルセットをクエリするために必要な検索プレフィックス部分を得るために、受信した範囲クエリに対してパーシング及び他の処理動作を実行するよう構成される。範囲クエリは、３つのトリプル要素の各々の境界（bound）及び非境界（unbound）値を有しても良い。例えば、範囲クエリは、１つの又はトリプル要素の値を指定しても良い。したがって、該要素又は要素対は境界であり、トリプルは、クエリ結果に含まれるためにトリプルの境界部分の指定された値と一致しなければならない。他の１又は複数のトリプル要素は非境界又は変数であり、トリプルの非境界部分の任意の１又は複数の値はクエリを満たす。
【００６７】
リスト位置計算モジュール１８は、順序付きリスト記憶モジュール１４に格納された順序付きリスト及びプレフィックス頻度記憶モジュール１６に格納された頻度レコードを用いて、複数の記憶ユニット３０の中で、受信した範囲クエリ内で指定された又はそれから抽出された検索プレフィックス部分と一致する又はそれを含むプレフィックス部分を有するトリプルを格納している記憶ユニットの識別情報を得るよう構成される。
【００６８】
順序付きリストは、単に、数字のシリーズ（又は記憶ユニットの物理的アドレスのような任意の形式の識別情報のリスト）を有しても良い。また、順序付けは、順序付きリストに格納された情報により決定できなくても良いが、順序付きリスト内のエントリに対応するトリプルの特定により決定されても良い。それぞれプレフィックス部分ｐ１、ｐ２、ｐ３を有する３つのトリプル、ｔ１、ｔ２、ｔ３を検討する。トリプルｔ１は記憶ユニットｓ１に、ｔ２は記憶ユニットｓ２に、ｔ３は記憶ユニットｓ３に記憶されても良い。プレフィックス部分に適用される順序付けメトリックは、例えば、プレフィックス部分として指定された１又は２つのトリプル要素の値の連結により形成されたストリングのアルファベット（又は英数字）順であっても良い。この任意の例で、このような順序付けメトリックにより、ｐ２がｐ３の上に配置され、ｐ３がｐ１の上に配置される可能な結果を検討する。順序付きリストは、ｓ２、ｓ３、ｓ１となるだろう。したがって、順序付けメトリックをトリプルのプレフィックス部分に適用することにより、リスト内のどの位置が各プレフィックス部分に適合するか、したがって、特定のプレフィックス部分を有するトリプルが決定されたリスト位置で識別される記憶ユニットから読み出し可能であることを決定できる。しかしながら、順序付きリストは、識別情報を有しても良い。順序付けメトリックは、一貫性があり反復可能なように選択され、つながりを切断する１又は複数のルールを更に有しても良い。
【００６９】
順序付きリストは、特定のプレフィックス部分を有するトリプルが格納されている記憶ユニットの記憶ユニット（データノード）識別情報のみを格納しても良いが、各トリプルの実際の物理アドレスは、それらが格納されている記憶ユニット３０により保持されても良い。
【００７０】
プレフィックス頻度記憶モジュール１６は、異なるプレフィックス部分の頻度レコード、及び各プレフィックス部分を有するトリプルのセットの中のトリプル数を格納する。したがって、特定の検索プレフィックス部分について、順序付きリストを順序付ける際に、プレフィックス部分に適用されるとき、同じ順序付けメトリックが頻度レコードの中のプレフィックス部分に適用される場合、順序内の検索プレフィックス部分に先行するプレフィックス部分に対応する順序付きリスト内のエントリの数は、リスト位置計算モジュール１８により計算できる。頻度レコードは、順序付けメトリックをプレフィックス部分に適用することにより決定された順序でレコードを格納しても良い。或いは、リスト位置計算モジュールは、プレフィックス頻度記憶モジュールから読み出したレコードに順序付けメトリックを適用するよう構成されても良い。
【００７１】
リスト位置が、複数の記憶ユニット３０の中から、プレフィックス部分を有するトリプルが格納されている記憶ユニットの識別情報を格納するという意味で、リスト位置は、プレフィックス部分に対応すると考えられる。もちろん、プレフィックス部分に対応するリスト位置の数は、プレフィックス部分を有するトリプルの数に等しく、該トリプルの各々を格納する記憶ユニットの識別情報は、リストに格納される。例えば、同じプレフィックス部分を有する２つのトリプルが同じ記憶ユニットに格納されている場合、該記憶ユニットの識別情報は、プレフィックス部分に対応するリスト位置に２回現れる。
【００７２】
リスト位置計算モジュールは、検索プレフィックス部分に一致する又はそれを含むプレフィックス部分に対応するリスト位置を決定すると、これらのリスト位置を占有する識別情報は、（転送又は他の方法により）結果読み出しモジュール１９に利用可能にされる。結果読み出しモジュールは、１又は複数の識別された記憶ユニットへ、検索プレフィックス部分を有するトリプルについての要求を送信するよう構成される。任意で、結果読み出しモジュールは、要求の中で、要求が送信された記憶ユニット３０に存在する、検索プレフィックス部分を有するトリプルの数を指定しても良い。したがって、全ての結果が読み出されたときの不必要なスキャンを未然に防ぐ。結果読み出しモジュールは、記憶ユニットからクエリ結果を受信し、アプリケーション２０に収集した結果を送信するよう更に構成されても良い（図１に破線により示される）。代替で、記憶ユニット３０へ送信される要求は、結果を送信すべき場所を指定しても良い。或いは、異なる機能モジュールが、結果の収集と、該結果のアプリケーション２０への返送を担っても良い。
【００７３】
（１又は複数の）頻度レコード及び（１又は複数の）順序付きリストを構築し及び維持する例示的な技術を以下に説明する。さらに、範囲クエリを実行するために格納された情報を利用する例示的な方法も説明する。
【００７４】
頻度レコードの構成要素として、Ｔｒｉｅ、プレフィックス検索ツリーが３つのトリプル要素の各々の値の別個のインデックスを構成するために用いられる。ここで、本例における３つのトリプル要素は、Ｓ（主語）、Ｐ（述語）、Ｏ（目的語）と表される。３つの異なるＴｒｉｅはが得られ、Ｓ−Ｔｒｉｅ、Ｐ−Ｔｒｉｅ、Ｏ−Ｔｒｉｅと表記される。例としてトリプル＜Ｓｉ，Ｐｉ，Ｏｉ＞を考える。図２は、主語Ｓｉのインデックスをルーティングする検索経路を有するＳ−Ｔｒｉｅを示す。ここで、ｎがトリプルセットにより符号化されたＲＤＦデータモデル（グラフデータベース）に現れる主語の合計数であるとき、０≦ｉ≦ｎである。本例では、主語は、オントロジの主語及びそのインスタンスの合計数を含み、オントロジは、グラフデータベースにより表現される知識ドメインである。最初のストリングキャラクタから始めて進むと（場合によっては人為的に導入した共通ルート（根）を有する）、ストリングオブジェクト（本例では、主語を形成するトリプルストリングの部分）は、２つ分岐するキャラクタに達するまで、ｔｒｉｅ内の共通経路を辿り、該キャラクタで経路が分岐する。したがって、ストリングオブジェクトへの共通の始点は、１回だけソートされ、重複しないので、記憶空間が節約される。ｔｒｉｅのリーフはトリプル要素の値に対応するので、Ｓ−ｔｒｉｅの各リーフは、異なる値の主語トリプル要素である。各ｔｒｉｅのリーフにおいて、数字のシリーズが記録され又はアクセスされ、必要な場合には更新される。これらの数字は、特定のプレフィックス部分に対応するリスト位置を計算するために用いられる。リスト位置は、順序付きリストが関連するトリプルセットの中のトリプルと１：１対応を有するので、リスト位置は、トリプルＩＤとも考えられる。つまり、トリプルは、トリプルのプレフィックス部分に対応するリスト位置により識別可能である。
【００７５】
順序付きリストは、仮想順序付きリストであっても良く、トリプルセット毎に格納され管理される。各トリプルセットは、異なる形式のトリプル要素を有する。例えば、グラフデータベース内のデータは、より良い範囲クエリ性能のために形式ＳＰＯ、ＰＯＳ、ＯＳＰを有するトリプルに符号化されても良い。順序付きリストは、形式のそれぞれ異なる変形について確立される。
【００７６】
順序付きリストは、トリプルＩＤをキー（つまり、リスト位置）として有し、トリプルが格納される記憶ユニットの識別情報又は物理アドレス（ソケットアドレス）をＫＶペアの値として有する、キー値（ＫＶ）マップのような論理シーケンスとして実現されても良い。柔軟性を増大するために、トリプルＩＤは連続的ではない。言い換えると、セット内のトリプルの記憶ＩＤにより占有されるリスト位置は、占有されたリスト位置間にギャップが存在しないように、又は少なくとも初期に又は更新時に連続的でないように割り当てられても良い。このようにして、トリプルＩＤ又はリスト位置は、新しいトリプルのために利用可能なままである。連続するリスト位置の間のギャップは、新しいＩＤが既存のＩＤの間の順序で追加されるとき簡単な挿入を可能にするために、所定のギャップであっても良い。
【００７７】
頻度レコード内のｔｒｉｅの各リーフ頂点に、情報が記録される。情報は、以下を含んでも良い。
ε：リーフにより示されるｔｒｉｅのトリプル要素の値を有するトリプルの合計数である。
ｈ：テーブル、例えばハッシュテーブル、又はハッシュテーブルへのリンクであり、プレフィックス部分に現れる他のトリプル要素のＴｒｉｅと現在のＴｒｉｅとの連結を用いてインデックス付けされた特定のプレフィックス部分を有する。キーは、他のトリプル要素のｔｒｉｅのリーフである。値は、現在のリーフによりインデックス付けされたトリプル要素の値と、他のトリプル要素のｔｒｉｅのリーフにより表されるトリプル要素の値との連結によりインデックス付けされたトリプルの合計数である。トリプル要素のうちの別の１つと一緒に、トリプルセットのプレフィックス部分の一部として割り当てられた、トリプル要素のうちの特定の１つに対するプレフィックス検索ｔｒｉｅでは、各リーフは（ここで、リーフは、トリプル要素のうちの特定の１つの値を表す／に対応する）、ハッシュテーブル又はハッシュテーブルへのリンクを格納する。例えば、ハッシュテーブルのキーは、少なくとも、トリプル要素のうちの特定の１つの値を有するトリプルセット内のプレフィックス部分で生じるトリプル要素の別の１つの値であり、場合によっては、トリプル要素のうちの別の１つの全ての値である。各キーを介してアクセスされる値（キー値では、トリプル要素の値と混同しないように）は、ハッシュテーブルにリンクする又はハッシュテーブルを格納するリードにより示されるトリプル要素のうちの１つの値がキーを形成する別のトリプル要素の値と共に生じるトリプルセット内のプレフィックス部分の数である。
【００７８】
例えば、トリプル要素形式ＯＳＰを有しプレフィックス部分ＯＳが割り当てられたトリプルセットについて、頻度レコード及び順序付きリストを考える。Ｓｉで示される主語ストリングを示すＳ−Ｔｒｉｅのリーフは、以下の情報を格納しても良い。
【００７９】
Ｓｉのεは、主語Ｓｉを有するトリプルセット内のプレフィックス部分の合計数を与える。つまり、主語Ｓｉを有するトリプルセット内のトリプルの合計数である。
【００８０】
Ｓｉのｈは、プレフィックスＯｊＳｉ（ここで、１≦ｊ≦ｍ、ｍはトリプルセット内に現れる目的語トリプル要素の異なる値の数である）を有するトリプルの合計数を与える。つまり、特定の組合せＯｊＳｉを有するトリプルの数を読み出すために、主語Ｓｉ及び目的語トリプル要素の各値を有し、ＯＳＰ形式で格納され、検索キーとしてＯｊを有する、トリプルの合計数である。
【００８１】
Ｓｉのリーフに記録される任意の要素は、次の通りである。
【００８２】
λ：順序付きリスト及び頻度レコードが最後に更新されて以来、リーフにより示される値を有する新しく挿入されたトリプルの合計数である。
【００８３】
この数は、挿入されたデータを有する論理シーケンスを正規化するときに用いられても良い。
【００８４】
ハッシュテーブルの使用は、初めは、リーフレベルの記憶のデータサイズを増大するように見える。しかしながら、本発明の実施形態は、トリプルのプレフィックス部分の頻度レコードのみを保持し、全ての形式の完全なストリングプレフィックスインデックスを保持しないので、リーフレベルの記憶の増大は、単に補償だけに留まらない。
【００８５】
以下の例は、どれだけ多くの頻度レコード及び順序付きリストが管理されるかを示す。本例では、各トリプルは、３つの形式、つまりＳＰＯ、ＰＯＳ、ＯＳＰで格納される。トリプル＜ｓ１ｐ１ｏ１＞及び＜ｓ２ｐ１ｏ１＞の場合。
【００８６】
（１）トリプルｓ１ｐ１ｏ１をインデックス付けする間、各形式について１つの、３つのプレフィックス部分が頻度レコードに追加される。各プレフィックス部分は２回記録される。１回は、プレフィックス部分のトリプル要素のうちの１つのＴｒｉｅのリーフにおける値である。１回は、プレフィックス部分の他のトリプル要素の値により形成されるキーによりアクセスされるハッシュテーブル値における該リーフのハッシュテーブルにである。
ａ）プレフィックスｓ１は、ｓ１を示すＳ−ｔｉｒｅのリーフのεの更新を生じ、ｓ１のハッシュテーブル内のキーｏ１によりアクセスされる値の増大を生じる。
ｂ）ｐ１の更新されたεとハッシュテーブル内のｓ１キーでｐ１を続ける。
ｃ）ｏ１の更新されたεとハッシュテーブル内のｐ１キーでｏ１を続ける。
【００８７】
（２）同様に、ｓ２ｐ１ｏ１のインデックス付けでは、
ａ）プレフィックスｓ２は、ｓ２のεの増大を生じ、ｓ２のハッシュテーブル内のｏ１キーの増大を生じる。
ｂ）ｐ１の更新されたεとハッシュテーブル内のｓ２キーでｐ１を続ける。
ｃ）ｏ１の更新されたεとハッシュテーブル内のｐ１キーでｏ１を続ける。
【００８８】
最後に、ｓ１、ｓ２は、それぞれ１つのトリプルをインデックス付けし、ｐ１及びｏ１は、それぞれ２つのトリプルをインデックス付けする。
【００８９】
特定のプレフィックス部分に対応するリスト位置を計算する、言い換えると特定のトリプルのＩＤ又はトリプルプレフィックス部分を計算する例示的な技術を以下に説明する。さらに、リスト位置を計算する例示的な技術を含み範囲クエリを処理する技術を説明する。
【００９０】
本例では、所定のギャップＣが、隣接する占有されたリスト位置間に（隣接するトリプルＩＤ間に）残されているとする。主語Ｓｉの開始位置starting-positionは、次の通り計算できる。
【数１】
2014232532.tif 000003
【００９１】
上述の計算では、εｋは、主語値Ｓｋを示すリーフに記録されたεである。
【００９２】
範囲クエリは、トリプル内の任意の位置に現れ、主語、述語及び目的語のうちの１又は２つを置き換えるワイルドカードキャラクタを有し形成できる。トリプルは、異なる形式、＜Ｘ，＊，＊＞又は＜Ｘ，Ｙ，＊＞で複製される。ここで、Ｘ及びＹは、例えば目的語及び述語であり、任意のＲＤＦトリプル範囲クエリをエミュレートするために用いることができる。＜Ｓｉ，Ｐｊ，Ｏｋ＞を例にとる。正規化された（以下を参照）データ記憶システムでは、範囲クエリの開始位置及び終了位置は以下のように計算される。
【００９３】
＜Ｓｉ，＊，＊＞では、開始位置は、上式で計算される。終了位置ending-positionは、次のように計算される。
【数２】
2014232532.tif 000004
【００９４】
ここで、
【数３】
2014232532.tif 000005
は、主語ｔｉｒｅ（ｓ）内のリーフ頂点に記録された最初の数を与える。
【００９５】
＜Ｓｉ，Ｐｊ，＊＞について、開始位置及び終了位置は次のように計算される。
【数４】
2014232532.tif 000006
【００９６】
ギャップＣは、既知の開始位置の前に挿入された可能性のある新しく追加されたデータアイテムを検索するために、ずらされる。単純に、上記の和のうち最初の項を順序付けメトリックに従って主語Ｓｉの前に現れる主語を有するトリプルの数と見なし、２番目の項の和を順序付けメトリックに従って同じ主語Ｓｉを有しＰｊに先行する１又は複数の同じ述語を有するプレフィックス部分を有するトリプルの数と見なす。
【００９７】
異なる形式及び異なるトリプルシーケンスを用いる他の種類の範囲クエリの開始位置及び終了位置を得るために、同じ計算が適用できる。範囲クエリの開始位置及び終了位置は、本例では、前のデータ正規化の後に新たに追加されたデータについて、限られた空間（占有されたリスト位置毎にＣ−１個のギャップ）を有する正規化シーケンスに対して計算される（正規化は、更新及び初期化において生じる）。
【００９８】
開始位置及び終了位置が計算されると、範囲内のリスト位置のスキャンが実行され、特定のプレフィックス部分（上述の例ではＳｉＰｊ）を有するトリプルを格納する記憶ユニットの全てのソケットアドレス／記憶ユニット識別情報を読み出す。
【００９９】
リスト位置にあるリストエントリは、単に、宛先データサーバを指すソケットアドレス（つまり、記憶ユニットの識別情報）を記録しても良い。効率のために、可能な場合には、範囲クエリは、結果読み出しモジュールにより、サブ範囲にわたる複数のクエリに分割される。サブ範囲は、特定の記憶ユニットに格納されるトリプルである。したがって、検索プレフィックス部分（本例ではＳｉＰｊ）を有するトリプルを格納するそれぞれ個々のデータサーバ／記憶ユニットは、自身のトリプルについてクエリされる。各記憶ユニットは、要求されたトリプルを読み出すためのローカルなインデックス付けメカニズムを有しても良い。計算されたリスト位置にあるソケットアドレス又は他の記憶ユニット識別情報は、範囲クエリの部分を実行するために、どのデータノードに連絡すべきか及び委任すべきかを識別するために用いられる。
【０１００】
特定のトリプルを得るとき、上述の開始点及び終了点は、最初の２つのトリプル要素に基づき特定のトリプルのプレフィックスについて計算される。これは、与えられた範囲内の全てのトリプルに対応するデータノードのソケットアドレスを返す。次に、ｇｅｔ動作は、特定のトリプルを読み出すために全てのデータノードにブロードキャストされる。与えられたトリプルを保持しないデータノードは、「偽」を返し、その他の場合「真」を返す。特定のトリプルのＧＥＴは、データレポジトリ内のトリプルの存在を効率的に調べる。
【０１０１】
新しいデータのデ―タベースへの挿入を管理する例示的な手順を以下に説明する。挿入は次のように実行される。
【０１０２】
（１）データアイテムは、それぞれ順序付けメトリックに対応する新しいトリプルのプレフィックス部分の前後に現れるプレフィックス部分に対応する２つの既存のリスト位置の中点に、リスト位置又はトリプルＩＤを割り当てられる。
【０１０３】
（２）ε及びλは、相応して更新される。λの更新は以下により行われる。
ａ）新しく追加されたトリプルのプレフィックス部分に対応するリスト位置を得る。
ｂ）最初の後続のリスト位置のλを増大する。
【０１０４】
システムがアイドルのとき、論理シーケンスは均一に／正規化され、占有されたリスト位置の間の所定のギャップを定める。例えば、Ｔｒｉｅ内の特定のリーフにより示されるトリプル要素の値を有するトリプルを格納する記憶ユニットの識別情報では、これは、順序付けメトリックに従って特定のリーフに先行する全てのリーフにおけるλ値を加算する（そして、現在のリストエントリに影響を与えるリストの部分に含まれなければならない新しい識別情報エントリの数を確定することにより）ことにより、及び所定のギャップＣにより乗算された加算されたλ値と等しいリスト位置の数だけリストエントリを移動することにより、達成されても良い。
【０１０５】
所定のギャップは、データベース設計者又はデータベース管理者により設定可能な変数である。ギャップが小さすぎる場合、新しいデータを挿入するとき、新しく挿入されるデータアイテムのための空間を作るために、挿入されるデータアイテムより大きく全てのデータアイテムをずらさなければならないかも知れない。他方で、ギャップが大きすぎる場合、Ｔｒｉｅのサイズが大きくなり過ぎる。
【０１０６】
上述のように、データアイテムを挿入するとき、対応するλ値は更新される。非ゼロのλ値を用い、シーケンスがどこから正規化されるべきかを（データアイテム間のギャップさえも）識別することも可能である。
【０１０７】
順序付きリストの正規化又は更新は、システムがアイドルのとき周期的に実行されても良く、又は最後の更新以来、所定のギャップが満たされているとき強制的に実行されても良い。ギャップサイズを注意深く選択することにより、後者の状況は大体は回避でき、ギャップは、隣接するシステムアイドルイベント間で存続するには十分である。正しいギャップサイズを選択する経験的ルールは、データセット全体のサイズ及びデータ挿入のサイズとレートを反映する履歴に基づきギャップサイズを推定するために用いることができる。次に、ギャップサイズは、２つの正規化動作の間に挿入されるべきデータセットの最大サイズに近似されるべきである。書き込みの集中するレポジトリでは、大きなギャップが予約されるべきである。
【０１０８】
図３は、本発明を実施するデータ記憶システムの例示的なハードウェア構成を示す。システムは、アプリケーションティア２０、データベース制御部の機能を実現するために協調して動作する多数のサーバを有するインデックスティア１０、及び複数の記憶ユニット３０を有する記憶ティア３０を有する。インデックスティア１０で、複数のＴｒｉｅを維持するために、複数のサーバが必要である。もちろん、これは、データベースのサイズ及び各トリプル要素の異なる値の数に依存する。各インデックスサーバは、データベース制御部機能を提供するソフトウェアスタックを含む。グラフレイヤ１１は、クエリ受信モジュール１２の例であり、クエリをＲＤＦグラフトランザクションに変換するためにアプリケーションと通信する。ＫＶＳレイヤ１５は、クエリの部分に対応するストリングオブジェクトをリスト位置／トリプルＩＤに変換する。したがって、ＫＶＳレイヤ１５は、順序付きリスト記憶モジュール１４、プレフィックス頻度記憶モジュール１６、及びリスト位置計算モジュール１８の例である。ＫＶＳレイヤ１５は、適応型ロケータの例である適応型ロケータレイヤ１７によりトリプルに割り当てられたトリプルＩＤと記憶ユニット識別情報との間のマッピングを保持する。正確なデータ位置は、適応型ロケータレイヤ１７により調整され管理される。インデックスサーバは、通信ネットワークを通じて互いに通信する。
【０１０９】
オブジェクトが適格なＵＲＩのようなＵＲＩとは別の任意の値を取り得るとき、インデックスサーバの数は、主にオブジェクトｔｒｉｅのサイズに依存する。単一のインデックスツリーは、１つのインデックスサーバにより全体が維持できないこともあり得る。これは、グラフデータベース内のオブジェクトの値により多くの多様性が存在する場合が多いため、Ｏ−Ｔｒｉｅに関連する場合に起こる可能性が高い。次に、プレフィックスツリーは、分散される必要がある。プレフィックスツリー（ｔｒｉｅ）を分散させる単純なアプローチは、階層的分散構造を採用することである。例えば、ルート（根）及びプレフィックスツリーの下方向の限られた深さを有するツリーは、スーパーピアに格納でき、プレフィックスツリーのサブツリーを管理するインデックスサーバにマッピングするリーフを有する。
【０１１０】
記憶ティア３０は、ローカルデータを維持し及び例えば適応型ロケータレイヤ１７を介して互いの間で通信ネットワークを通じてインデックスレイヤ１０と通信可能な多数のデータ記憶サーバを有する。記憶は、分散型キー値記憶を用いて実現される。
【０１１１】
纏めると、本発明の実施形態は以下を提供する。
・キー／値記憶のキー（リスト位置）に順序を保持し（ここで、値は記憶ユニットの識別情報である）、全てのサーバにクエリする必要を回避しデータをフィルタリングすることにより、範囲クエリ動作を改善する、システム。
・データ位置の柔軟性を保ち、単一の動作で頻繁に一緒に読み出されるデータアイテムが同一場所に配置され得るようにする、システム。
・データアイテムの順序付き記憶内のデータを同一場所に配置する手順を結合し、２つの範囲クエリ及びデータの局所性を最適化する、フレームワーク。
【０１１２】
トリプル自体の内容に基づきトリプルをインデックス付けすることは、幾つかの他のデータ記憶技術におけるインデックスツリーよりも大きなインデックスツリーをもたらす。システムが必ずしも、クエリ結果を含まないデータ記憶ユニットにクエリする必要がないという利点がある。システムが、共起性トリプルを同じサーバに同一場所に配置する柔軟性を保有し、ネットワークトラフィックを低減するという利点がある。したがって、記憶要件の控えめな増大で、ネットワークI/Oの劇的な削減が達成される。
【符号の説明】
【０１１３】
１０  データベース制御部
１１  グラフレイヤ
１２  クエリ受信モジュール
１４  順序付きリスト記憶モジュール
１５  ＫＶＳレイヤ
１６  プレフィックス頻度記憶モジュール
１７  適応型ロケータ
１８  リスト位置計算モジュール
１９  結果読み出しモジュール
２０  アプリケーション
３０  記憶ユニット
【図１】
2014232532.tif 000007
【図２】
2014232532.tif 000008
【図３】
2014232532.tif 000009