(57)【要約】      （修正有）【課題】エンコードされたトリプルを格納するデータベース、制御部、方法及びシステムを提供する。【解決手段】トリプルを格納するデータベースのデータベース制御部であって、各トリプルは、主語、述語及び目的語を有し、格納されたトリプルに従って順序付けられたデータアイテム内に格納され、各データアイテムは、ネットワーク内に分散する記憶ノードに格納され、前記データベース制御部は、前記データベースにトリプルを格納する要求を受信する記憶要求受信部、それぞれ異なるバージョンを有する２以上のデータアイテムを生成するデータアイテム生成モジュール、前記２以上のデータアイテムの各々について、前記データアイテムを格納する記憶ノードを順序付けられたセット内の前記データアイテムの位置に依存して選択する命令分配部を有し、少なくとも２つの異なる記憶ノードが前記トリプルのあるバージョンを有するデータアイテムを格納する。【選択図】図１
2013246828.tif 000002
【特許請求の範囲】
【請求項１】
トリプルとしてエンコードされたグラフデータを格納するデータベースのデータベース制御部であって、各トリプルは、主語、述語及び目的語を有し、各トリプルは格納されたトリプルに従って順序付けられたデータアイテムのセットの中のデータアイテム内に格納され、各データアイテムは、ネットワーク内に分散する複数の記憶ノードの中の記憶ノードに格納され、
前記データベース制御部は、
前記データベースにトリプルを格納する要求を受信するよう構成される記憶要求受信部、
データアイテム生成モジュールであって、
前記データアイテム内で前記主語が前記述語及び前記目的語より先行する第１のバージョン、
前記データアイテム内で前記述語が前記主語及び前記目的語より先行する第２のバージョン、
前記データアイテム内で前記目的語が前記主語及び前記述語より先行する第３のバージョン、のうちのそれぞれ前記トリプルの異なるバージョンを有する２以上のデータアイテムを生成するよう構成される、データアイテム生成モジュール、
命令分配部であって、前記２以上のデータアイテムの各々について、前記複数の記憶ノードの中から前記データアイテムを格納するよう指示する記憶ノードを選択するよう構成され、前記選択は、順序付けられたセット内の前記データアイテムの位置に依存して行われ、前記命令分配部は、前記複数の記憶ノードの中から少なくとも２個の異なる記憶ノードが前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成される冗長モジュールを有する、命令分配部、
を有するデータベース制御部。
【請求項２】
前記データアイテム生成モジュールは、前記第１のバージョン、前記第２のバージョン及び前記第３のバージョンのうちのそれぞれ前記トリプルの異なるバージョンを有する３個のデータアイテムを生成するよう構成される、請求項１に記載のデータベース制御部。
【請求項３】
前記冗長モジュールは、前記少なくとも２個の異なる記憶ノードがそれぞれ前記トリプルの異なるバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成される、請求項１又は２に記載のデータベース制御部。
【請求項４】
前記複数の記憶ノードの中に３個以上の記憶ノードがあり、前記冗長モジュールは、前記複数の記憶ノードの中から３個の異なる記憶ノードがそれぞれ前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成される、請求項１乃至３のいずれか一項に記載のデータベース制御部。
【請求項５】
各データアイテムは、前記トリプルの主語、述語及び目的語を有するストリングオブジェクトを含み、前記データアイテムは、前記ストリングオブジェクトのアルファベット順の比較に従って順序付けられる、請求項１に記載のデータベース。
【請求項６】
前記命令分配部は、順序付きハッシュテーブルを用いて前記複数の記憶ノードの中から前記データアイテムを格納するよう指示する記憶ノードを選択するよう構成され、前記順序付きハッシュテーブルは、コンシステントハッシング関数を用いる、請求項１乃至５のいずれか一項に記載のデータベース制御部。
【請求項７】
同一のトリプルの異なるバージョンを格納する前記２以上のデータアイテムの各々は、該トリプルの異なるバージョンを格納する他のデータアイテムの各々が格納される記憶ノードを識別するデータを有する、請求項１乃至６のいずれか一項に記載のデータベース制御部。
【請求項８】
前記データベース制御部は、
記憶ノードの分散型ネットワーク内の記憶ノードが障害になるときを検出し、該障害になった記憶ノードに格納されたデータアイテム内に格納されたトリプルを識別するよう構成される障害検出部、
を更に有し、
前記データベース制御部は、識別されたトリプルの各々について前記データアイテム生成モジュールにおける生成及び前記命令分配部における選択を実行するよう構成され、前記障害になった記憶ノードは、記憶ノードが選択される前記複数の記憶ノードから除外され、前記命令分配部は、選択した記憶ノードに、識別されたトリプルの１個のバージョンを有するデータアイテムを格納するよう指示し、及び現在選択されていない障害の前の記憶ノードにより格納されていた識別されたトリプルのバージョンを有するデータアイテムの削除を指示するよう構成される、請求項１乃至７のいずれか一項に記載のデータベース。
【請求項９】
前記命令分配部は、前記複数の記憶ノードの中から決定論的方法で前記データアイテムを格納するよう指示する記憶ノードを選択するよう構成され、前記冗長モジュールは、２以上のデータアイテムについての記憶ノードの選択の後に、前記２以上のデータアイテムを格納するために選択された記憶ノードの中から異なる記憶ノードの数の総数を得て、前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されるよう前記冗長モジュールが保証するよう構成された異なる記憶ノードの数より前記総数が少ない場合、前記冗長モジュールは、前記複数の記憶ノードの中から前記トリプルを有する更なるデータアイテムを格納する追加記憶ノードの数を指示するよう構成され、該数は、前記総数と前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されるよう前記冗長モジュールが保証するよう構成された異なる記憶ノードの数との間の差に等しい、請求項１乃至８のいずれか一項に記載のデータベース制御部。
【請求項１０】
前記追加記憶ノードにより格納される前記更なるデータアイテムは、データアイテムの前記順序付けられたセットの外部に格納される、請求項９に記載のデータベース制御部。
【請求項１１】
請求項１乃至１０のいずれか一項に記載のデータベース制御部として機能するよう構成されるコンピューティング装置。
【請求項１２】
前記コンピューティング装置は、ネットワーク内に分散された前記複数の記憶ノードの中の記憶ノードの１個である、請求項１１に記載のコンピューティング装置。
【請求項１３】
複数の請求項１２に記載のコンピューティング装置を有するシステム。
【請求項１４】
コンピューティング装置により実行されると、前記コンピューティング装置に請求項１乃至１０のいずれか一項に記載のデータベース制御部として動作させる、コンピュータプログラム。
【請求項１５】
データベース内にトリプルとしてエンコードされたグラフデータを格納する方法であって、各トリプルは、主語、述語及び目的語を有し、各トリプルは格納されたトリプルに従って順序付けられたデータアイテムのセットの中のデータアイテム内に格納され、各データアイテムは、ネットワーク内に分散する複数の記憶ノードの中の記憶ノードに格納され、
前記方法は、
前記データベースにトリプルを格納する要求を受信するステップ、
２個以上のデータアイテムを生成するステップであって、前記データアイテムの各々は、
前記データアイテム内で前記主語が前記述語及び前記目的語より先行する第１のバージョン、
前記データアイテム内で前記述語が前記主語及び前記目的語より先行する第２のバージョン、
前記データアイテム内で前記目的語が前記主語及び前記述語より先行する第３のバージョン、のうちの前記トリプルの異なるバージョンを有する、ステップ、
前記２個以上のデータアイテムの各々について、前記複数の記憶ノードの中から前記データアイテムを格納するよう指示する記憶ノードを選択するステップであって、前記選択は、順序付けられたセット内の前記データアイテムの位置に依存して行われ、前記複数の記憶ノードの中から少なくとも２つの異なる記憶ノードが前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証する、ステップ、
を有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶の分野に関する。特に、本発明の実施形態は、分散記憶環境でグラフデータを記述するトリプルの記憶に関連する。
【背景技術】
【０００２】
関係型データベースは、データを行と列で格納する。行及び列は、データを格納する前に定める必要のあるテーブルを構成する。テーブルの定義及びこれらのテーブルに含まれるデータ間の関係は、スキーマと称される。関係型データベースは、固定スキーマを用いる。グラフデータベースは、データをノード及びアークの形式で格納することにより、関係型データベースの重要な拡張を表す。ここで、ノードはエンティティ又はインスタンスを表し、アークは任意の２個のノード間の特定種類の関係を表す。無向グラフでは、ノードＡからノードＢへのアークは、ノードＢからノードＡへのアークと同じであると考えられる。有向グラフでは、２つの方向は別のアークとして扱われる。
【０００３】
グラフデータベースは、概して２つの主な種類に分類できる広範な種類の異なるアプリケーションで用いられる。第１の種類は、知的意思決定支援及び自己学習のようなクラス記述子の大規模な集合体（「知識ベースアプリケーション」と称される）を有する複雑な知識ベースシステムを有する。第２の種類は、社会的データ及びビジネスインテリジェンスのようなトランザクションデータに対するグラフ検索の実行を含むアプリケーション（「トランザクションデータアプリケーション」と称される）を有する。多くのアプリケーションは、両方の種類を表し得る。しかしながら、大部分のアプリケーションは、主に知識ベース又はトランザクションデータアプリケーションのいずれかで特徴付けられ得る。グラフデータベースは、種々の分野の膨大な構造化又は非構造化データを格納できる大規模な「意味ネットワーク」を維持するために用いることができる。意味ネットワークは、知識表現の形式として用いられ、コンセプトを表すノード及びコンセプト間の意味関係を表すアークを有する有向グラフである。
【０００４】
幾つかの種類のグラフ表現がある。グラフデータは、多次元アレイとして又は他のシンボルにリンク付けされたシンボルとしてメモリに格納されても良い。別の形式のグラフ表現は、各々指定された種類のオブジェクトの有限シーケンス又は順序付きリストである「タプル」の使用である。ｎ個のオブジェクトを含むタプルは、「ｎタプル」として知られる。ここで、ｎは零より大きい任意の非負整数である。長さ２のタプル（２タプル）は、通常、ペアと呼ばれる。３タプルはトリプルと呼ばれ、４タプルはクワドラプルと呼ばれ、以降同様である。
【０００５】
ＲＤＦ（Resource  Description  Framework）は、概念記述又は意味ネットワークの標準である情報のモデル化のための一般的方法である。今日利用可能なＲＤＦデータの量は、増大しており、既に単一のサーバに格納することが不可能である。膨大な量のデータを格納し検索可能にするために、データは複数のサーバに保持されなければならない。データの追加、削除及び検索は、分散システムのために特注されたアルゴリズム及びデータ構造を用いて協調的方法で行われなければならない。コンピュータ的に効率的にデータの検索、保守及び操作を可能にするような方法でグラフデータを格納することが望ましい。
【０００６】
全てのコンピューティングハードウェアと同様に、データが格納される（サーバのような）記憶ノードが故障する幾らかの危険は常に存在する。したがって、従来、記憶ノードの故障の場合に、データのコピーを格納する「冗長」記憶ノードを設けることが知られている。しかしながら、このような冗長ノードを設けることは、インフラ提供、保守及び運用コストの観点から費用が掛かり得る。記憶ノードの信頼性が向上するにつれて、別のノードの障害の場合のデータ復旧を単に可能にするために冗長記憶ノードを設けることは、稼働率当たりのコストの値を減少させる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
エンコードされたトリプルを格納するデータベース、制御部、方法及びシステムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の実施形態は、トリプルとしてエンコードされたグラフデータを格納するデータベースのデータベース制御部であって、各トリプルは、主語、述語及び目的語を有し、各トリプルは格納されたトリプルに従って順序付けられたデータアイテムのセットの中のデータアイテム内に格納され、各データアイテムは、ネットワーク内に分散する複数の記憶ノードの中の記憶ノードに格納され、前記データベース制御部は、前記データベースにトリプルを格納する要求を受信するよう構成される記憶要求受信部、データアイテム生成モジュールであって、前記データアイテム内で前記主語が前記述語及び前記目的語より先行する第１のバージョン、前記データアイテム内で前記述語が前記主語及び前記目的語より先行する第２のバージョン、前記データアイテム内で前記目的語が前記主語及び前記述語より先行する第３のバージョン、のうちのそれぞれ前記トリプルの異なるバージョンを有する２以上のデータアイテムを生成するよう構成される、データアイテム生成モジュール、を有するデータベース制御部を提供する。
【０００９】
前記データベース制御部は、命令分配部であって、前記２以上のデータアイテムの各々について、前記複数の記憶ノードの中から前記データアイテムを格納するよう指示する記憶ノードを選択するよう構成され、前記選択は、順序付けられたセット内の前記データアイテムの位置に依存して行われ、前記命令分配部は、前記複数の記憶ノードの中から少なくとも２個の異なる記憶ノードが前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成される冗長モジュールを有する、命令分配部、を更に有する。
【００１０】
有利なことに、本発明の実施形態は、トリプルとして格納されるグラフデータを格納し及びクエリする順序付けを有するフォールトトレラントな分散型記憶システムを提供する。実施形態は、格納されたデータに対する範囲クエリの実行及び記憶ノードの障害の場合に格納されたデータの復旧の両方で高い効率を可能にする、データを格納する技術を提供し又は実施する。
【００１１】
効率的な範囲クエリを実行するために、トリプルは、少なくとも２つの（例えば３つの）異なる順序で格納される。例えば、ＳＰＯ、ＰＯＳ、ＯＳＰの中から２つ（又は３つ）である（ここで、本明細書を通じて、Ｐは述語を表すため、Ｓは主語を表すため、Ｏは目的語を表すために用いられる）。これは、最重要であるトリプルの２以上の変形のうちの先行する要素の変形であり、残りの２要素の位置の変化は、本質的でないことが望ましい。冗長モジュール又は等価な機能は、効率的な範囲クエリを目的として提供されるトリプルの少なくとも２個のバージョンが、記憶ノードの障害の場合にフォールトトレランスを提供するための複製として機能できることを保証する。
【００１２】
纏めると、本発明の実施形態は、効率的な範囲クエリを提供するために、グラフデータを２以上のバージョンに複製されたエンコードされたトリプルとして格納するデータベースを提供するが、失われたデータの再生成のためにデータの冗長性を提供するためにもこれらの複製されたバージョンを用いる。２以上のバージョンの各々は、トリプルの（格納された形式の）先行する要素と異なる要素を有する。
【００１３】
本発明の実施形態では、（ＲＤＦトリプルのような）各トリプルは、データアイテム又はその一部として、例えば単純なストリングオブジェクトとして格納され、グラフＧ内で一意である。よって、Ｇに関する全ての情報は、データアイテム内に保持される。トリプルは、（ピアツーピアネットワーク環境のような）分散型ネットワーク環境のネットワーク記憶ノード内のプロセスを通じて分散された順序付けられたデータセット内のデータアイテムとして格納される（データアイテムにエンコードされる）。各記憶ノードで動作するプロセスは、データアイテムの順序付けられたサブセットの記憶を実現する。プロセス及びプロセスを動作させるネットワーク記憶ノードは、本願明細書では事実上同義的に表され、前者又は後者が排他的に意図されるときは文脈から明らかである。本発明の実施形態は、データに対して効率的な問い合わせプロシジャを行うことを可能にする。例えば、（発行されると）ｄｍｉｎとｄｍａｘとの間のデータアイテムの範囲を検索するプロシジャは、以下のステップを実行する。クライアントアプリケーションがプロセスのうちの１つＡに要求を送信する。Ａはマッピング関数を実行し、要求されたデータ範囲の１つのサブセットを含むプロセスの記憶ノードＩＤ（又はラベル）を得る（例示的な場合には、データアイテムは均等に分散され、各プロセスは多数のデータアイテムの格納を担う）。例として、クライアントアプリケーションにより要求されたキーがプロセスＡ及びＢで格納される場合を検討する。Ａは、要求されたデータアイテムの各サブセットを検索するサブ範囲要求を自身へ及びＢへブロードキャストする。各プロセスは、要求されたデータアイテムと共にＡに応答する。Ａは、（結果の順序を維持しながら）結果を集め、クライアントアプリケーションに応答する。
【００１４】
上述の例から、本発明の実施形態が更に効率的なデータの問い合わせを可能にすることが分かる。さらに、ステップは、従来技術の場合のように要求内のデータアイテム毎に繰り返される必要はない。
【００１５】
本発明の実施形態におけるグラフデータは有向グラフデータなので、第１のグラフノードから第２のグラフノードへのアークは、第２のグラフノードから第１のグラフノードへのアークと同じであるとは考えられない。意味ネットワークは、知識又は情報の表現として形成され、エンティティ又はインスタンスのようなコンセプトを表すグラフノード、及びコンセプト間の意味関係を表すアークを有する。
【００１６】
本発明の実施形態では、グラフデータは、トリプルとしてエンコードされる。トリプルは、それぞれ特定の種類である３つのオブジェクトの無限シーケンス又は順序付きリストである。
【００１７】
任意で、トリプルは、ＲＤＦ（Resource  Description  Framework）トリプルであっても良い。本願明細書を通じて、「ＲＤＦトリプル」への特定の参照が行われるとき、それはＲＤＦ標準に準拠するトリプルの例示的形式であることが理解されるべきである。さらに、「トリプル」への参照は、問題のトリプルがＲＤＦトリプルである可能性を有する。同様に、本願明細書のいずれかの箇所で議論されるＲＤＦプロセッサは、ＡＰＩラッパと格納されたデータアイテムとの間の相互作用のために用いられるプロセッサの例である。
【００１８】
ＲＤＦ（Resource  Description  Framework）は、概念記述又は意味ネットワークの標準である情報のモデル化のための一般的方法である。意味ネットワークにおける情報のモデル化の標準化は、共通の意味ネットワークで動作するアプリケーション間の相互接続性を可能にする。ＲＤＦは、ＲＤＦスキーマ（ＲＤＦＳ）をＲＤＦ内の語彙を記述するための言語として提供することにより、一義的な形式意味論と共に語彙を保持する。
【００１９】
任意で、トリプルの１又は複数の要素のうちの各々は（要素は、述語、目的語又は主語である）、ＵＲＩ（Uniform  Resource  Identifier）である。ＲＤＦ及び他のトリプルの形式は、識別するものの概念（つまり、オブジェクト、リソース又はインスタンス）を前提として、ＵＲＩのようなウェブ識別子を用い、それら識別される「もの」を簡易な特性及び特性値の観点で記述する。トリプルの観点では、そのトリプルのウェブリソースの具体化において、主語はエンティティを記述するウェブリソースを特定するＵＲＩであっても良く、述語は特性の種類（例えば、色）を特定するＵＲＩであっても良く、目的語は問題のエンティティに起因する特性の種類の特定のインスタンスを指定するＵＲＩであっても良い。ＵＲＩの使用は、トリプルに、個々の特性及び値と同様に、リソースを表すノード及びアークのグラフのようなリソースに関する簡易なステートメントを表すことを可能にする。ＲＤＦグラフは、SPARQLプロトコル及びＲＤＦクエリ言語（SPARQL）を用いて問い合わせることができる。SPARQLは、World  Wide  Web  ConsortiumのRDF  Data  Access  Working  Group  (DAWG)により標準化され、主要なセマンティックウェブ技術と考えられている。SPARQLは、クエリがトリプルのパターン、連結、分離、任意のパターンを有することを許容する。
【００２０】
トリプルは、グラフデータを複数の主語−述語−目的語の表現として特徴付けることにより、グラフデータのエンコードを提供する。この文脈では、主語及び述語は、グラフデータのグラフノードであり、オブジェクト、インスタンス又はコンセプトのようなエンティティであり、述語は、主語と目的語の間の関係の表現である。述語は、目的語への特定の種類のリンクを提供することにより、主語に関する何かを断言する。例えば、主語は、（例えば、ＵＲＩを介して）ウェブリソースを示しても良く、述語はリソースの個々の特性、特徴又は状況を示し、目的語は、該特性、特徴又は状況のインスタンスを示す。言い換えると、トリプルステートメントの集合は、元来、方向性グラフデータを表す。ＲＤＦ標準は、このようなトリプルの形式化された構造を提供する。
【００２１】
記憶ノードの分散型ノードネットワークは、互いに通信する１より多い異なる記憶ユニットのシステムを有しても良い。例示的な通信パラダイムはピアツーピア（Ｐ２Ｐ）である。したがって、記憶ノードの分散型ネットワークは記憶ノードのピアツーピアネットワークであっても良い。Ｐ２Ｐは、タスク又は負荷をピア間に区分する分散アーキテクチャである。ピア（個々の記憶ノード又はプロセス）は、等価な特権を有し、アプリケーション内で等しい力を有する参加者である。各ピアは、処理能力、ディスクストレージ又はネットワーク帯域幅のようなそれ自体のリソースの一部を、サーバ又は安定したホストによる集中的強調の必要無しに、他のネットワーク参加者に直接利用可能にするよう構成される。ピアは、リソースの供給者及び消費者の両方であると考えられ、サーバが供給しクライアントが消費するという従来のクライアント−サーバモデルとは対照的である。有利なことに、Ｐ２Ｐは、対数的な通信コストでメッセージを交換する記憶ノードの大規模なグループを維持できる。
【００２２】
実施形態では、トリプルの目的語が複雑な例では、順序付けられたデータに格納される目的語は、該目的語のために生成されるＵＵＩＤ（universal  unique  ID）であっても良い。この選択肢は、オブジェクトが大きく、そのサイズが範囲クエリプロシジャの効率を低下させてしまう実装シナリオで用いられる実施形態で有用である。
【００２３】
本発明の実施形態では、トリプルは、順序付けられたデータアイテムに格納されるので、データアイテムを返すクエリは、トリプルの表現が検索されるのを可能にする。
【００２４】
効率的な範囲クエリを目的とした同一トリプルの異なるバージョンの記憶は、異なるバージョンが１より多い異なる記憶ノードに格納される場合、データ復旧の目的でも有利であり得る。したがって、本発明の実施形態で冗長モジュールを設けることは、記憶ノードの障害の場合に復旧を可能にするためにデータの冗長性を提供するために、各データアイテムを複製する必要を取り除く。
【００２５】
任意的に、前記データアイテム生成モジュールは、前記第１のバージョン、前記第２のバージョン及び前記第３のバージョンのうちのそれぞれ前記トリプルの異なるバージョンを有する３個のデータアイテムを生成するよう構成される。
【００２６】
有利なことに、トリプルの３個の異なるバージョンのデータアイテムを有することは、トリプルの３個の要素のうちのいずれかによる効率的な範囲クエリを可能にする。つまり、主語、目的語又は述語の範囲が指定され、範囲に含まれるトリプルを格納するデータアイテムが効率的に返される。
【００２７】
前記冗長モジュールは、前記少なくとも２個の異なる記憶ノードがそれぞれ前記トリプルの異なるバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成されても良い。例えば、前記複数の記憶ノードの中に３個以上の記憶ノードがある実施形態では、前記冗長モジュールは、前記複数の記憶ノードの中から３個の異なる記憶ノードがそれぞれ前記トリプルの異なるバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成されても良い。
【００２８】
この特定の実装では、トリプルの３個の異なるバージョンを格納するデータアイテムは、それら自体がネットワーク内の３個の異なる記憶ノードに分散される（記憶ノード当たり１個）。これは、３個の異なるバージョンを有するという利点があるので、さらに、これらのバージョンのうちのいずれかを格納する記憶ノードが故障した場合に、トリプルの１個のバージョンを格納する２個の他の記憶ノードが存在し、したがって故障した記憶ノードに格納されたバージョンが効率的に再生成できるので、有利である。
【００２９】
代替として、冗長モジュールは、３個の異なる記憶ノードが、必ずしも異なるバージョンではないが、それぞれトリプルの１個のバージョンを格納することを保証するよう構成されても良い。例えば、命令分配部により実行されるマッピングプロシジャが１個の記憶ノードに同一のトリプルの２個の異なるバージョンを、別のノードに別の異なるバージョンを生じる場合、冗長モジュールは、トリプルの既存のバージョンのうちのどれが前記１個の記憶ノード及び前記別の記憶ノードに格納されているかに拘わらず、第３の記憶ノードに格納するためにトリプルの特定のバージョンの複製（例えば、ＳＰＯ）を単に生成しても良い。
【００３０】
本発明の実施形態では、データアイテムは、トリプルの要素を表すストリングオブジェクトの辞書順により順序付けられても良い。ストリングオブジェクトは、データアイテムであるか又はデータアイテムに含まれている。例えば、辞書順はアルファベット順であっても良い。本発明の実施形態の実装では、データアイテムの主語、述語又は目的語（又は目的語のＵＵＩＤ）のいずれかを固定することによりデータアイテムのセットをクエリすることが望ましい。このようなくえりの結果を効率的に返すために、トリプルの２以上の要素がデータアイテム内の最初の要素として格納されることが有利である。
【００３１】
順序付けられているデータアイテムは、データアイテム間の比較を行うこと及び範囲クエリを実行することを可能にする。Ｄ１とＤ２（Ｄ１＜Ｄ２）の間の範囲クエリは、データアイテムの特定の所定の順序メトリックに従って、Ｄ１より大きくＤ２より小さいデータアイテムの順序付けされたセットに含まれるデータアイテムを返す。勿論、データアイテムのセットは、分散型ノードネットワークのノードに渡って分割される（ここで、ノードは、サーバのようなリソース、又は該サーバで動作するプロセスである）。例示的な実施形態では、範囲クエリは、クエリをノードのうちの１つに送信することにより、アプリケーションの代わりにＲＤＦプロセッサのようなプロセッサにより開始される。ノードは、どの他のノードがクエリにより探し出されたデータアイテムを有するかを、データアイテムの論理表現をＤ１及びＤ２に適用し、サブ範囲クエリをこれらのノードに対して実行することにより計算するよう構成される。ノードは、次に、（データアイテムの順序を維持したまま）結果を集め、それらをクエリを行使したプロセッサに返すよう構成される。
【００３２】
トリプルがデータアイテム内に格納される形式の観点から、データアイテムの各々は、対応するトリプルの主語、述語及び目的語を有するストリングオブジェクトを含んでも良い。
【００３３】
有利なことに、ストリングオブジェクトは、一般に読み取り可能であり、その比較及び存在する他の処理要求では確立されたルーチンである。データベース自体及びデータベースにアクセスするアプリケーションは、ストリングオブジェクトを処理する確立したルーチンを有しても良い。さらに、ストリングオブジェクトは、検索及び比較（オーダ）するのが速い。
【００３４】
このような実施形態では、データアイテムは、ストリングオブジェクトのアルファベット順の比較に従って順序付けられても良い。
【００３５】
有利なことに、検索、範囲、他の比較関数のようなデータベース関数が利用可能である。データベース関数は、ストリングデータオブジェクトのアルファベットの内容を比較するために、コンピュータ的に効率的な観点で最適化される。したがって、このようにデータアイテムを順序付けする実施形態は、コンピュータ的効率の観点で特に有効である。上述の実施形態では、前記データアイテムは、該データアイテムのストリングオブジェクトのアルファベット順に従って順序付けられても良い。データアイテムは、単にストリングオブジェクトであっても良く、又は他のオブジェクト若しくはデータを有しても良い。ストリングは、英数字シンボルのシーケンスである。
【００３６】
任意的に、前記命令分配部は、順序付きハッシュテーブルを用いることにより、前記複数の記憶ノードの中からデータアイテムを格納するよう指示する記憶ノードを選択するよう構成されても良い。有利なことに、ハッシュテーブルは、データアイテムをノードにマッピングするコンピュータ的に効率的な方法を提供する（ここで、マッピングは、前記複数の記憶ノードの中からデータアイテムを格納するよう指示する記憶ノードを選択することと意味において等価である）。順序付きハッシュテーブルは、ハッシュ関数を用いて、データアイテムの内容に基づきデータアイテムをノードに割り当てる。
【００３７】
キー値体系では、ハッシュテーブル又はハッシュマップは、ハッシュ関数を用いてキーとして知られる特定する値をそれらの関連付けられた値にマッピングするデータ構造である。したがって、ハッシュテーブルは、連想配列を実施すると言われている。ハッシュ関数は、対応する値が検索されるアレイ要素（記憶場所、スロット又はバケットとも称される）のインデックス（ハッシュ）にキーを変換するために用いられる。
【００３８】
任意的に、前記順序付きハッシュテーブルは、コンシステントハッシング関数を用いても良い。
【００３９】
コンシステントハッシングは、データアイテムが格納される記憶ノードの数の変化に応答して再マッピングされる必要のある順序付けられたデータアイテムの数を調整する。例えば、Ｄ個のデータアイテムがピアツーピアシステム内のｎ−１個の「ピア」の間に分散されているシステムを考える。新しいピアがシステムに参加した場合、Ｄ／ｎ個のキーのみが再マッピングされる必要がある。コンシステントハッシングでは、新しいピアがシステムに追加されるとき、他のピアから格納されたデータアイテムのほぼ等しい分担を取り、ピアが削除されるとき、そのデータアイテムは残りのピアの間で分担される。
【００４０】
ハッシング関数又はその他かに拘わらず、特定のデータアイテムを格納するよう指示する記憶ノードを選択するために命令分配部により用いられる技術は、決定論的であるべきである。つまり、複数の記憶ノードの中からデータアイテムを格納するよう指示する記憶ノードを選択することは、決定論的選択である。したがって、選択の結果は、ネットワーク内の別のデータベース制御部により、又は後続の動作において同じデータベース制御部により決定できる。１より多いデータベース制御部を有する実施形態では、同じ決定論的選択プロシジャが各データベース制御部により用いられ、同じ入力変数が与えられた場合に同じ結果が生成されるようにする。
【００４１】
ＫＶＳ構成の値の中の追加情報として、又はその他の場合にはトリプルを有するデータアイテムに格納されたデータとして、本発明の実施形態では、同一のトリプルの異なるバージョンを格納する２以上のデータアイテムの各々は、該トリプルの異なるバージョンを格納する他のデータアイテムの各々が格納されている記憶ノードを識別するデータも有する。
【００４２】
有利なことに、同一のトリプルの異なるバージョンを格納する他のデータアイテムの各々が格納される記憶ノードを識別するデータを有することは、故障したノードに格納された、したがって復旧又は再生成される必要のあるデータアイテムを識別するために、故障していないノードに格納されたデータアイテムを用いることを可能にする。
【００４３】
記憶ノードは、ＩＤにより識別可能である。ＩＤは、記憶ノードのネットワークの中で分散され格納されるとき、データアイテムの順序付けられたセットの順序が維持されるように順序付けられる。例えば、ＩＤは、ネットワーク内の記憶ノードのアドレスにハッシング関数を適用することにより得られても良い。
【００４４】
本発明を実現する前記データベース制御部は、記憶ノードの分散型ネットワーク内の記憶ノードが障害になるときを検出し、該障害になった記憶ノードに格納されたデータアイテム内に格納されたトリプルを識別するよう構成される障害検出部、を更に有しても良く、前記データベース制御部は、識別されたトリプルの各々について前記データアイテム生成モジュールにおける生成及び前記命令分配部における選択を実行するよう構成され、前記障害になった記憶ノードは、記憶ノードが選択される前記複数の記憶ノードから除外され、前記命令分配部は、選択した記憶ノードに、識別されたトリプルの１個のバージョンを有するデータアイテムを格納するよう指示し、及び現在選択されていない障害の前の記憶ノードにより格納されていた識別されたトリプルのバージョンを有するデータアイテムの削除を指示するよう構成される。
【００４５】
有利なことに、障害検出部及びデータベース制御部の関連する機能は、記憶ノードの故障の場合に、効率的なデータ復旧プロセスを提供し、一方で、単にデータ復旧目的のためにデータのコピーを格納することに関するシステムコストを最小化する。
【００４６】
任意的に、本発明を具現化する命令分配部では、前記冗長モジュールは、２以上のデータアイテムについての記憶ノードの選択の後に、前記２以上のデータアイテムを格納するために選択された記憶ノードの中から異なる記憶ノードの数の総数を得て、前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されるよう前記冗長モジュールが保証するよう構成された異なる記憶ノードの数より前記総数が少ない場合、前記冗長モジュールは、前記複数の記憶ノードの中から前記トリプルを有する更なるデータアイテムを格納する追加記憶ノードの数を指示するよう構成されても良く、該数は、前記総数と前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されるよう前記冗長モジュールが保証するよう構成された異なる記憶ノードの数との間の差に等しい。
【００４７】
このような冗長モジュールは、命令分配部により用いられる選択プロシジャが決定論的であるとき、データアイテムとそれらが格納される記憶ノードとの間の関係の決定論的特性を阻害することなく、データアイテムの複製をデータ復旧目的のために格納させるので、特に有利である。冗長モジュールがトリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証するよう構成された異なる記憶ノードの数は、実装固有であるが、好適な実施形態では３である。したがって、トリプルの１個のバージョンを有するデータアイテムを格納するよう指示される異なる記憶ノードの数は、３から総数を減じたものである。トリプルの特定のバージョン（例えば、ＳＰＯ）を有するデータアイテムの複製が作成され、追加記憶ノードに格納されても良い。
【００４８】
さらに、前記追加記憶ノードにより格納される前記更なるデータアイテムは、データアイテムの前記順序付けられたセットの外部に格納される。
【００４９】
有利なことに、これは、データアイテムの順序付けられたセットの順序が維持され、データアイテムとそれらが格納されるノードとの間の関係の決定論的特性も維持されることを保証する。
【００５０】
代替の実施形態では、冗長モジュールは、データアイテムが格納される複数の記憶ノードの中から記憶ノードを選択するために命令分配部により用いられるハッシングアルゴリズムに組み込まれる。
【００５１】
本発明の実施形態は、サーバのような、本発明を具現化するデータベース制御部として機能するよう構成されるコンピューティング装置も含む。例えば、前記コンピューティング装置は、分散型ネットワーク内の記憶ノードのうちの１つであっても良い。さらに、前記コンピューティング装置は、複数の前記コンピューティング装置の中の１つであっても良い。したがって、記憶ノードの分散型ネットワークでは、複数の記憶ノードのうちの１より多いノード（例えば全部）は、本発明を具現化するデータベース制御部の機能を有する。
【００５２】
本発明の実施形態は、コンピュータプログラム又はコンピュータプログラムを格納する非一時的記憶媒体を含む。該コンピュータプログラムは、コンピューティング装置により実行されると、該コンピューティング装置に本発明を具現化するデータベース制御部として機能させる。
【００５３】
また、本発明は、トリプルとしてエンコードされたグラフデータをデータベースに格納する方法により具現化される。各トリプルは、主語、述語及び目的語を有し、各トリプルは格納されたトリプルに従って順序付けられたデータアイテムのセットの中のデータアイテム内に格納され、各データアイテムは、ネットワーク内に分散する複数の記憶ノードの中の記憶ノードに格納され、前記方法は、前記データベースにトリプルを格納する要求を受信するステップ、２以上のデータアイテムを生成するステップであって、前記２以上のデータアイテムの各々は、前記データアイテム内で前記主語が前記述語及び前記目的語より先行する第１のバージョン、前記データアイテム内で前記述語が前記主語及び前記目的語より先行する第２のバージョン、前記データアイテム内で前記目的語が前記主語及び前記述語より先行する第３のバージョン、のうちの前記トリプルの異なるバージョンを有する、ステップ、を有する。前記方法は、前記２以上のデータアイテムの各々について、前記複数の記憶ノードの中から前記データアイテムを格納するよう指示する記憶ノードを選択するステップであって、前記選択は、順序付けられたセット内の前記データアイテムの位置に依存して行われる、ステップ、前記複数の記憶ノードの中から少なくとも２個の異なる記憶ノードが前記トリプルの１個のバージョンを有するデータアイテムを格納するよう指示されることを保証するステップ、を更に有する。
【００５４】
本願明細書で議論するデータアイテムは、テーブルに行又はエントリとして格納される独立した情報片であっても良い。しかしながら、本発明の実施形態は、各前記データアイテムがキー値体系（ＫＶＳ）内のキー値ペアのキーである実施形態を含む。
【００５５】
有利なことに、キー値体系のキーに完全なトリプルを含むキーの格納は、関数が、トリプルが見付かるかも知れない場所への単なるリンク又は識別子ではなく、完全なトリプルを返すキーのセットに対して実行されるのを可能にする。
【００５６】
キー値ペアのキ―に格納されることは、キー値ペアのキ―であるストリングオブジェクトとしてトリプルの要素を表すことを含む。
【００５７】
キー値システム（ＫＶＳ）又はキー値ストアは、複数の格納されたキー及び値である。各キーは、関連付けられた値を有し、論理関数又は論理木、例えばハッシュテーブル又はハッシュマップを介して該関連付けられた値にマッピングされる。ハッシュテーブル又はハッシュマップは、ハッシュ関数を用いて（値を特定する）キーをそれらの関連付けられた値にマッピングするデータ構造である。本発明の実施形態では、ハッシュ関数は、キーを、記憶ノードの分散型ネットワークを形成する複数の記憶ノードのうちの記憶ノード（記憶リソース）の識別表示に変換するために用いられても良い。
【００５８】
実施形態は、複数の前記キー値ペアの各々の値は、キーに格納されたトリプルに関連する追加情報を有しても良い。一例として、トリプルに関するメタデータは、値に格納される。この文脈におけるメタデータは、トリプルの中の情報アイテムに関する説明データである。キーはトリプルを格納し、値は該トリプルに関する情報を格納する。
【００５９】
任意で、上述の実施形態では、前記追加情報は、アプリケーションのアイデンティティに依存して前記データベースにアクセスする前記アプリケーションに利用可能にされるデータである。
【００６０】
有利なことに、このような実施形態は、データベース内のデータを読み出し及び／又は書き込むアプリケーションに依存する特徴を有効にすることにより、データベースの機能を拡張する。データは、アプリケーション依存データであり、ＫＶＳにおいて不可解オブジェクトとして見なされ取り扱われても良い。値コンテナは、アプリケーション依存データを設定及び読み出すＡＰＩを有しても良い
任意的に、上述のＫＶＳ実装では、前記追加情報は、リード及び／又はライトアクセスが前記キー値ペアに格納されたＲＤＦトリプルに対して行われるとき通知を受信するために登録されるアプリケーションのリストを含む。さらに、追加情報は、コンテナを格納するノードによる実行のためにソフトウェアコードを有しても良い。例えば、ソフトウェアコードは、特定のイベントに応答して格納され呼び出されても良い。また、ソフトウェアコードの引数もコンテナに格納される。例えば、値は、ソフトウェアコードのブロックを更新関数として格納しても良い。関連付けられたトリプルが更新されるとき、更新関数が呼び出され、他のトリプルのリスト及びそれらの場所が引数である。他のトリプルのリストは、クライアントアプリケーションがトリプルを、特定のイベントと関連付けられたコンテナ内のリストに追加することにより、生成されても良い。
【００６１】
有利なことに、トリプルデータへの読み出し又は書き込みアクセスが行われるときを通知するアプリケーションは、格納されたデータを用いてデータベースとアプリケーションとの間の相互作用のレベルを向上させる。通知を受信するために登録されたアプリケーションのリストは、通知が管理され得るメカニズムを提供する。
【図面の簡単な説明】
【００６２】
本発明の好適な特徴は、単なる例として添付の図面を参照して以下に説明される。
【図１】本発明を具現化するデータベース制御部の概略図である。
【図２】本発明を具現化するシステムの概略図である。
【図３】図１のデータベース制御部のどの構成要素が図２のどのソフトウェアレイヤに対応するかの例を示す。
【発明を実施するための形態】
【００６３】
図１は、本発明を具現化するデータベース制御部を概略的に示す。データベース制御部１０は、複数の構成要素、つまり、記憶要求受信部１２、データアイテム生成モジュール１４、命令分配部１６を有する。命令分配部１６自体は、冗長モジュール１８を有する。構成要素自体は、専用ハードウェア、例えばプロセッサ、メモリ、記憶装置、及びネットワークインタフェースにより実現されても良い。これらの全ては、適切な場合には、以下に記載する方法で機能するよう構成される。代替として、データベース制御部は、サーバのようなそれ自体がノードの分散型ネットワーク２０内の記憶ノードであり得るコンピューティング装置で実行するコンピュータプログラム（又は１より多いコンピューティング装置で協調的に実行するコンピュータプログラムスーツ）により提供される機能であっても良い。このような実施形態では、構成要素は、それぞれコンピューティング装置自体の一部として設けられるハードウェアを用いてそれらの専用機能を実現する機能ユニット又はモジュールである。
【００６４】
データベース制御部１０は、単一の記憶ノードにある中央制御部として、協力する複数の記憶ノードによる中央制御部として、又はそれぞれ個々の記憶ノードにある複数の等価な制御部の中の制御部として実現され得る。例えば、データベース制御部１０は、ノードの分散型ノードネットワーク内の記憶ノードで実行するプログラムにより提供されても良く、１又は複数の他の記憶ノードも等価なプログラムを実行し、データベースが複数のデータベース制御部１０を介してアクセス可能になるようにしても良い。
【００６５】
データベース制御部１０は、記憶ノードの分散型ノードネットワーク２０に接続されるように示される。命令分配部１６から始まり記憶ノードで終わる矢印は、発行されているデータアイテムを格納する命令を表す方向を示す。しかしながら、データベース制御部と分散型記憶ノードのネットワークとの間のデータコネクションは双方向であっても良い。実際に、本発明の実施形態では、各記憶ノード及びデ―タベース制御部は、有線、無線又は両者の特定の組合せかに拘わらずネットワークを介して互いに通信可能であっても良い。ノードの分散型ネットワーク２０内の記憶ノードの各々は、データベース制御部１０のようなデータベース制御部を有しても良い。
【００６６】
記憶要求受信部１２は、データベースにトリプルを格納する要求を受信するよう構成される。要求は、例えば、データベースに新しいトリプルを追加したいアプリケーションを実行するクライアント装置から生じても良い。記憶要求受信部１２は、例えば、ＲＤＦレイヤ又はＲＤＦレイヤの一部であっても良く、データベースにトリプルを追加する、場合によってはデータベースからトリプルを削除し、データベースをリード若しくはそれに問い合わせる要求を処理する。データベースにアクセスしたいアプリケーションとデータベース自体との間の相互作用は、記憶要求受信部１２を介して生じ、データベース制御部１０及び／又はノードの分散型ネットワーク２０内の１又は複数の記憶ノードによりエクスポートされるＡＰＩ（application  programming  interface）により指定される形式であっても良い。記憶要求受信部１２は、アプリケーションからの要求を解釈し該要求に基づきデータベース制御部１０の他の構成要素のために命令を生成する処理を実行するよう構成されても良い。例えば、記憶要求受信部１２は、トリプル記憶要求の基礎を形成するトリプルを表すストリングを抽出し、抽出したストリング（又はトリプルの他のデータ表現）をデータアイテム生成モジュール１４に渡しても良い。
【００６７】
データアイテム生成モジュール１４は、それぞれ以下のトリプルの異なるバージョンを有する２以上のデータアイテムを生成するよう構成される。
【００６８】
第１のバージョンでは、データアイテム内で、主語が述語及び目的語より先行する。
【００６９】
第２のバージョンでは、データアイテム内で、述語が主語及び目的語より先行する。
【００７０】
第３のバージョンでは、データアイテム内で、目的語が主語及び述語より先行する。
【００７１】
各バージョンでトリプルの残りの要素が現れる順序も予め定められても良い。データアイテム生成モジュール１４は、それぞれ上述の３個のバージョンのうちの異なる１個を有する３個のデータアイテムを生成するよう構成される。データアイテム生成モジュール１４は、ＲＤＦレイヤ、ＲＤＦレイヤの一部、又はＲＤＦレイヤの部分と記憶レイヤの部分との組合せであっても良い。データアイテム生成モジュール１４は、トリプル又はトリプルを表現するデータを記憶要求受信部１２から受け付けるために、及び要求されたトリプルの異なるバージョンを生成するために、及び場合によってはトリプルのこれらの異なるバージョンを追加データを有する又は有しない特定フォーマットのデータアイテムにパッケージ化するために必要な処理を実行するよう構成される。データアイテム生成モジュール１４は、生成したデータアイテムを命令分配部１６に渡すよう構成される。
【００７２】
命令分配部１６は、２以上のデータアイテムの各々について、複数の記憶ノード２０の中からデータアイテムを格納するよう指示する記憶ノードを選択するよう構成される。この選択は、順序付きセット内のデータアイテムの位置に基づき行われる。命令分配部１６は、冗長モジュール１８を含み、複数の記憶ノード２０の中の少なくとも２個の異なる記憶ノードがトリプルの１個のバージョンを含むデータアイテムを格納するよう命令されるように構成される。命令分配部１６は、記憶レイヤの一部であっても良く、例えば、データアイテムを含む要求を記憶ノードへネットワークを介して送信することにより、又はそのような命令を送信させることにより、記憶ノードに特定のデータアイテムを格納するよう命令するために必要な処理を実行するよう構成される。例えば、（冗長モジュール１８を介して）命令分配部１６は、データアイテムを記憶ノードに決定論的方法で及び同一トリプルの２個のバージョンが同一の記憶ノードに格納されないことを保証するようにマッピングするよう構成されても良い。代替として、命令分配部は（例えば、決定論的ハッシング関数を用いて）データアイテムの記憶ノードへのマッピングを担い、冗長モジュールは、特定のトリプルの２個以上の異なるバージョンを有するデータアイテムのマッピングを再検討し、マッピングの結果が１個より多い記憶ノードがトリプルの１個のバージョンを格納していない場合、トリプルを有するデータアイテムの追加の複製を生成し、再検討されたデータアイテムを格納するよう指示された以外の記憶ノードに追加の複製を格納するよう指示するよう構成される。
【００７３】
ノードの分散型ネットワーク２０は、例えば、分散型ピアツーピアネットワークであり得る。このようなネットワークは、拡張可能であり、多数のサーバを有しても良い。実際、データアイテムの順序付きセットの分散レベルが高いほど、冗長モジュールにとって、必要数の記憶ノードがトリプルの１個のバージョンを含むデータアイテムを格納するよう指示されるよう保証することは容易である。
【００７４】
図２は、本発明を具現化するシステムを示す。図２では、各サーバ１〜Ｎ及びアプリケーション３０は、コンピュータで実行される。全てのコンピュータは、ネットワークを介して通信可能に接続される。異なるモジュール間の矢印は、ネットワーク通信を表す。しかしながら、これらは、以下に議論する通信を強調するためであり、可能なモジュール間通信をこのようなシステムアーキテクチャに限定しない。アプリケーション３０は、全てのサーバ１〜Ｎによりエクスポートされる特定のＡＰＩを用いて複数のサーバのうちの１個と相互作用する。各サーバは、以下の３個のソフトウェアコンポーネントにより構成されるデータベース制御部を有する。
【００７５】
・ＲＤＦレイヤ１１：ＲＤＦレイヤ１１は、アプリケーションからの要求を処理しデータを追加及び削除する、又は既存データに対して高レベルクエリを実行する。アプリケーション要求は、低レベル要求に変換され、記憶レイヤに転送される。ＲＤＦレイヤ１１は、ＲＤＦデータを単純且つ同型のトリプル表現に変換する。高レベルクエリも、範囲クエリのセットに変換されなければならない。ＲＤＦレイヤ１１は、記憶要求受信部１２の例である。
【００７６】
・記憶レイヤ１５：記憶レイヤ１５は、データアイテムの生成及び分配、並びに範囲クエリの実行を担う。記憶レイヤ１５は、データアイテム生成モジュール１４、命令分配部１６、冗長モジュール１８の例である。
【００７７】
・障害検出部１９：障害検出部１９は、サーバ障害を検出し、残りの（障害のない）サーバを記憶レイヤ１５に通知するウォッチドックの実行を担う。記憶レイヤ１５及び障害検出部１９は、通信ネットワークを用いて異なるサーバの同様のコンポーネントと通信する。
【００７８】
本実施形態のデータベースは、ネットワークを通じて通信する分散型のサーバ（記憶ノード）セット２０を有する記憶システムにより設けられる。システムを構成するサーバセット２０は、分散型順序付きハッシュマップも実装する。アプリケーション３０、例えばネットワークを介して１又は複数のサーバ２０に接続可能なクライアントマシンで実行するアプリケーションは、複数のサーバのうち１個に接続することにより、システムと相互作用する。クライアントアプリケーション３０は、例えば新しいトリプルを追加することにより、トリプルを削除することにより、及び範囲クエリを実行することにより、ＲＤＦデータを追加し、削除し、及び問い合わせるためにインタフェースを提供される。
【００７９】
サーバ２０は、ネットワークを通じて互いに通信し、ぞれぞれ、それらの個々のデータベース制御部１０のコンポーネントとして障害検出モジュール１９を実行することにより、分散型障害検出部１９を実行する。処理Ｐが失敗すると（処理Ｐは、分散型サーバセット２０のサーバにより実現される記憶処理を示す）、最終的に、他の処理は、障害検出部からＰが失敗したことを示す通知を受信する。本実施形態のデータベース内のデータは、トリプル、例えばＲＤＦトリプルとして格納される。ＲＦＤトリプルは、［主語（Subject），述語（Predicate），目的語（Object）］又は単にＳＰＯの形式のＲＤＦデータである。データは、同一のトリプルをＰＯＳ若しくはＯＳＰのような異なる順序で格納する複製を用いて範囲クエリが効率的に実行できるような方法で格納される。本発明の実施形態では、複製は、データ復旧処理でも用いられる。
【００８０】
データベースに格納されるデータセットは、各データアイテム内のトリプルデータに従って順序付けられる。データセットの範囲は、Ｎ個のセグメントに分けられる。ここで、Ｎは、記憶装置として用いられるサーバの数である。各サーバは、データのセグメントに対して責任がある。データがシステムに追加されるとき、各トリプルの少なくとも２個の（望ましくは３個の）バージョンが生成され、これらのバージョンは、少なくとも２個の（望ましくは３個の）異なるサーバに格納される。セグメント（及びその対応するサーバアドレス又はＩＤ）は、コンシステントハッシングのような決定論的技術を用いて、記憶レイヤ１５（命令分配部１６）により各トリプルバージョンについて計算される。各トリプルバージョンは、当然に異なるサーバに格納されるが、コンシステントハッシングは、常にこの特性を保証できない。各トリプルバージョンが異なるサーバに格納されない（又は複数のバージョンが少なくとも２個の異なるサーバに散在しない）場合、トリプルの余分の複製が異なるサーバのデータアイテムに格納される。特定のトリプルを有するデータアイテムが格納される全てのサーバは、決定論的プロシジャを用いて局所的に（例えば、各データベース制御部１０において）計算され得る。範囲クエリは既に順序付きセット内に格納されたデータに対して実行されるので、範囲クエリを開始するサーバは、局所的に問い合わせられる必要のないサーバのリストも計算できる。
【００８１】
トリプルの少なくとも２個の（望ましくは３個の）コピーは、以下の２つの目的を果たす。範囲クエリで指定されたプレフィックスに拘わらず範囲クエリを効率的に実行すること（つまり、範囲は主語、述語又は目的語により指定でき、依然として効率的に処理できる）、及び障害からデータを復旧させることである。ＳＰＯの形式でトリプルを含むサーバに障害が生じるとき、１又は複数の追加コピー、つまりＰＯＳ及びＯＳＰがシステムに存在する。これらのトリプルは、正確に同一のデータを含むが、異なる順序で表現されている。この情報を用い、本発明を実現するシステムは、トリプルの異なる表現から失われたデータを取り戻すメカニズムを提供する。失われたデータは復旧され、各トリプルの新しい位置が再計算される。あるサーバ（又は処理）が障害になるとき、生き残ったサーバは、どのトリプルが復旧され入れ替えられる必要があるかを理解するのに十分な情報を有する。復旧処理は、障害に対する耐性を保証するために必要な複製の数を維持するだけでなく、システム内の全てのサーバにより決定論的に到達可能なサーバ内にデータが置かれることを保証することが望ましい。
【００８２】
概要を前述したように、コンシステントハッシングは、データのセグメントをサーバにマッピングする非常に効率的な方法であり、本発明の実施形態において、トリプルのバージョンを含むデータアイテムを格納するよう指示すべき記憶ノード（サーバ）を選択するために記憶レイヤ１５（命令分配部１６）により用いられても良い。このようなハッシング方法は、同一のトリプルを格納する各データアイテムに対して異なるサーバを選択しても良いが、データアイテム、サーバの相対数及び（例えば、データアイテム間の相対的順序が維持されることを要求する）ハッシングアルゴリズムに依存して、必ずしも該当しない。したがって、本発明の実施形態は、同一トリプルの異なるバージョンを格納するデータアイテムが少なくとも２個の（望ましくは３個の）異なるサーバに格納されることを保証するメカニズムを備える。
【００８３】
より具体的には、記憶レイヤ１５（命令分配部１６）は、システムが例えば常に３個の異なるサーバ内にトリプルの少なくとも２個のコピーを有することを保証するために、３個の異なるシナリオを処理する機能（冗長モジュール１８）を備える。
【００８４】
・第２のシナリオでは、トリプルの３個のバージョン（ＳＰＯ、ＰＯＳ、ＯＳＰ）は、当然に異なるサーバに格納される。例えば、ＳＰＯはサーバ１に格納され、ＰＯＳはサーバ２に格納され、ＯＳＰはサーバ３に格納される。この例では、更なる動作を行う必要はない。
【００８５】
・第２のシナリオでは、トリプルの２個のバージョンは同一のサーバに格納され、１個のバージョンは別のサーバに格納される。例えば、ＳＰＯ及びＰＯＳはサーバ１に格納され、ＯＳＰはサーバ２に格納される。この例では、２個のサーバのみがトリプルの１個のバージョンを有し、システムは、この特定のデータアイテムについての障害に対する耐性が低い。これを回避するため、（例えば、冗長モジュール１８を介して）データベース制御部１０は、追加コピーが第３のサーバに格納されるために必要な処理を実行する。
【００８６】
・第３のシナリオでは、トリプルの３個のバージョン全て、つまりＳＰＯ、ＰＯＳ及びＯＳＰは、同一のサーバ（例えば、サーバ１）に格納される。この例では、システムは、サーバ１が障害となった場合、このデータアイテムを失ってしまう。同レベルの耐障害性を保証するため、（例えば、冗長モジュール１８を介して）データベース制御部１０は、追加コピーが（既に既存の３個のバージョンを格納しているサーバと異なる且つ互いに異なる）２個の異なるサーバに格納されるために必要な処理を実行する。
【００８７】
以上の３つのシナリオを上述の方法で処理することにより、システムは、データベース内の各トリプルについて、該格納されたトリプルの１個のバージョンを含む少なくとも３個のデータアイテムが存在することを保証する。トリプルの異なるバージョンを格納するデータアイテムが３個の異なるサーバにマッピングされない場合（シナリオ２及び３）、データアイテムのうちの１個の更なる複製が追加され、又はトリプルの１個のバージョンを有する新しいデータアイテムが追加される。シナリオ２では、システムは、トリプルのあるバージョンを有する４個のデータアイテムを格納する必要があるだろう。シナリオ３では、システムは、トリプルの１個のバージョンを有する５個のデータアイテムを格納する必要があるだろう。これは、この特定の実装では、元のデータアイテム（又はトリプル）が、データアイテムの順序付きセット内のそれらの場所から移動できないためである。シナリオ２及び３の発生頻度は、シナリオ１に比べて相対的に低いが、格納すべきデータ量及び利用可能なサーバの量に依存する。トリプルを格納する本方法は、任意のネットワーク構成において用いることができるが、多くのサーバを有する格納可能なピアツーピアネットワークを用いることは、シナリオ１の発生確率を上昇させ、したがってシステム内のトリプルのバージョンの複製の数を低減する。
【００８８】
さらに、この特定のシステムは、障害検出部１９を有する。障害検出部の単純なバージョンは、タイムアウト及び「ｐｉｎｇ」メッセージを用いるよう構成されるものである。各サーバの障害検出部１９は、「ｐｉｎｇ」メッセージを他の各サーバへ周期的に送信するよう構成される。例えば、サーバ１が、指定された時間量の後にサーバ２から「ｐｉｎｇ」メッセージ（又は他の種類の所定の応答）を受信しない場合、サーバ１は、サーバ２に障害が生じたと疑い、サーバ２を利用可能なサーバのリストから除外するために残りのサーバとの合意プロシジャを実行し、データ復旧処理を実行する。障害検出部を実施するこの特定の方法は、「最終的な完全な障害検出部」として知られ、ネットワークメッセージが失われない且つメッセージ遅延の（未知の）上限が存在するシステムにおいて特に有用である。任意的に、「ｐｉｎｇ」メッセージは、ネットワーク帯域幅を節約するために、定期的なサーバメッセージに抱き合わせることができる（piggyback）。更なる詳細事項及び障害検出部を実施する方法は、文献「Unreliable  failure  detectors  for  reliable  distributed  systems」、Tushar  Deepak  Chandra及びSamToueg、１９９６、J.ACM  ４３,  ２  (March  １９９６),  ２２５-２６７、DOI=１０.１１４５/２２６６４３.２２６６４７から得られる。
【００８９】
図２に示したシステムでは、各サーバは、等価な役割を実行するそれ自身のデータベース制御部を有する。各サーバは、以下のデータ構造を有する処理を実行する。
【００９０】
・記憶テーブル。各処理は、以下のフィールドを有するテーブルを格納する。
【００９１】
−triple_data：トリプル
−triple_order：Enum{SPO,POS,OSP}
−spo_node_ID：整数
−pos_node_ID：整数
−osp_node_ID：整数
記憶テーブル内で、エントリは、第１のフィールド（triple_data）により順序付けられ、各処理に対するローカルな範囲クエリを可能にする（例えば、トリプルを表現するストリングに基づくアルファベット順）。triple_orderは、トリプルがエンコードされる順序を表す数である。したがって、例えばtriple_orderに格納された数に基づき、トリプルのどの要素が例えば第２の要素により表現されるかを引き出せる。この特定の実装では、同一のトリプルの３個のバージョンの各々が格納されるノードのＩＤは、記憶テーブル内にトリプルと共に格納される。代替の実装では、記憶テーブル及び以下に議論する複製テーブルは、順序付きトリプルと検索可能なインデックスの両方をデータベース制御部に利用可能にするように、順序付きTrieと統合できる。
【００９２】
処理／サーバが格納し得る追加データ構造は、以下を含む。
【００９３】
・node_IDを記憶テーブルの行へのポインタにマッピングするインデックス。例えば、特定のサーバの障害の場合に、該サーバのnode_IDが決定され、インデックスは障害の起きたサーバにあるデータの復旧のために必要な行を効率的に識別可能にする。
【００９４】
・複製テーブル。これは、例えば３個の異なるサーバの各々が同一のトリプルの１個のバージョンを格納するという要件を満たすために生成されるトリプルのバージョンの複製を格納するために用いられる。トリプルの既存のバージョンの順序を維持するために、これらのトリプルは、主記憶テーブルの外部に格納される。したがって、この複製テーブルは、トリプルをＳＰＯ形式でのみ格納しても良く、以下のフィールドを有しても良い（ここで、replica１_IDはトリプルのＳＰＯバージョンの第１の複製が見付かるノードのＩＤを示す整数であり、第２の複製が存在する場合にはreplica２_IDはトリプルのＳＰＯバージョンの第２の複製が見付かるノードのＩＤを示す整数である）。
【００９５】
−triple_data：トリプル
−spo_node_ID：整数
−pos_node_ID：整数
−osp_node_ID：整数
−replica１_ID：整数
−replica２_ID：整数
・node_IDを複製テーブルの行へのポインタにマッピングするインデックス。再び、このようなインデックスは、データ復旧の目的のために都合が良い。
【００９６】
本実施形態では、各トリプルは、分散型記憶システムに３回、つまりＳＰＯの順序で、ＯＳＰの順序で、及びＰＯＳの順序で格納される。これは、データアイテムに格納された各トリプルの３個のバージョンが存在することを保証し、検索種類（主語による、述語による又は目的語による）に拘わらず範囲クエリが効率的に実行できることを保証する。以下の段落で、どのようにトリプルが格納され、処理が失敗したときにどのように情報が復旧されるかを説明する。
【００９７】
データは、線形データ空間を通じて順序付けられるトリプルのセットを有する。このデータ空間は、セグメントに分けられる。特定のデータアイテムが置かれたセグメントを効率的に検索するために、Trie（ソート木）のようなメカニズムを用いることができる。ここで、Trieの各々の葉はセグメントに対応する。このようなデータ構造は、システムの各記憶ノードの間で複製され、データアイテムをセグメントＩＤにマッピングする。データアイテムは常に順序付けられるので、範囲クエリを実行するために必要なセグメントＩＤを検索することが可能である。範囲クエリは、ｔ１とｔ２との間の全てのデータを検索する。ここで、ｔ１及びｔ２は、データアイテム（又はトリプル）である。したがって、問い合わせられる必要のあるセグメント（セグメントは、特定の記憶ノード／サーバ／機械に格納される全データセットの一部であると理解される）は、次の通りである。ｔ１が置かれたセグメント、ｔ２が置かれたセグメント、及びこれらの２つの間の全てのセグメント（それぞれが格納するデータアイテムの順序付きセットのセグメントの順序に従って順序付けられるとき、記憶ノードの順序の観点からそれらの間）である。セグメントＩＤを検索した後、コンシステントハッシングのようなメカニズムは、セグメントを機械にマッピングするツールとして用いられる。この機能では、データアイテム（トリプル）を特定の機械ＩＤ（machine  ＩＤ）に局所的にマッピングする機能／方法が提供される。
【００９８】
MachineID  getMachineID(Objecttriple)
このメソッドは、Trie構造（又は他の順序付きデータアイテムのセグメントＩＤ（segment  ＩＤ）へのマッピング）を用いてデータアイテムをセグメントＩＤにマッピングし、次に、コンシステントハッシングを用いてセグメントＩＤは機械ＩＤにマッピングされる（しかし、この第２のステップでは、セグメントＩＤを機械ＩＤにマッピングする任意のメカニズムが目的に合う）。本メソッドは、引数として提供されるトリプルの表現を有する命令「getMachineID」を介して呼び出される。例えば整数であっても良いMachineIDが返される。このメソッドは、トリプルの各バージョンを格納する記憶ノードを選択するために、記憶レイヤ１５（命令分配部１６）により用いられる。
【００９９】
機械ＩＤは、特定の記憶ノードを識別する。記憶ノードのＩＤは、例えばそのアドレスをハッシングすることによる、及びデータの線形空間におけるその相対位置に依存すると考えられても良い。これらのＩＤは、循環法で互いの間で順序を定めても良い。これは、例えばシステム内に３個の機械を有する場合、順序関係「Ａ＜Ｂ」（ＡはＢより小さい）は次のように定められる。
【０１００】
機械１＜機械２＜機械３＜機械１
データ挿入方法の記載では、演算「機械ＩＤ＋１」は、線形空間の次の機械に対応する。一例として、
機械１＋１は、機械３と同じである。
【０１０１】
機械３＋１は、機械１と同じである。
【０１０２】
最後に、２つの追加の方法がある。
【０１０３】
store(Object  triple,  MachineID  spoID,  machineID  posID,  MachineID  ospID)
storeReplica(Object  triple,  MachineID  spoID,  machineID  posID,  MachineID  ospID,  MachineID  replica１,  MachineID  replica２)
全ての記憶サーバは、これらのメソッドをそれらのデータベース制御部を介して提供する。これらのメソッドは、例えば、命令を記憶ノードに発行する際に、命令分配部により呼び出されても良い。store()メソッドは、特定のサーバの記憶テーブルにトリプルを記憶することを指示する。以上から分かることは、本実施形態では、メソッドを呼び出すときに含まれる引数は、トリプル自体、それが格納されるべき記憶ノードのＩＤ、及びトリプルの各バージョンが格納されるべき記憶ノードのＩＤであることである。
【０１０４】
storeReplica()メソッドは、必要な数の記憶ノードが特定のトリプルのあるバージョンを有することを保証するために、トリプルのあるバージョンが例えば冗長モジュール１８により複製されるとき、特定のサーバの複製テーブルにトリプルを格納する。本発明の実施形態の中核となる機能の任意的な拡張として、これらのメソッドは、トリプルの他のバージョンのＩＤを格納し、前述のインデックスを更新する。
【０１０５】
トリプルの３個のバージョン（及び必要な場合には複製）を格納するメカニズム（方法addTriple）は、次のように動作する。該メカニズムは、トリプルの表現を引数として有し、トリプルをデータベースに格納する要求を受信したデータベース制御部１０により実行されるメソッドの一例である。
【数１】
2013246828.tif 000003
【０１０６】
これらのプロシジャは、プレフィックスとしてトリプルデータのサブセットの任意の組合せを用いた範囲クエリを可能にするように、トリプルの各バージョン、つまりＳＰＯ、ＰＯＳ及びＯＳＰがシステムに格納されることを保証する。ＳＰＯ、ＰＯＳ及びＯＳＰのようなトリプルに対して「getmachineID」で用いられるハッシング関数が、トリプルの３個全てのバージョンに対して異なる機械ＩＤを返し、したがってそれらは全て異なるサーバに格納されることが保証されても良い。これが生じたか否かを調べると、必要な複製の数が決定され、複製が生成され、それらの記憶装置が指示される。これが生じない場合にのみ、１又は２個の余分な複製が格納される。これらの複製は、復旧処理でのみ用いられ、範囲クエリを実行するために用いられない。余分な複製は、システムが常に各プロシジャの少なくとも３個のコピーを有することを保証するために、単なるフォールバックプロシジャである。幾つかの場合には、システムは、同じデータの４又は５個のバージョンを格納しても良いが、コンシステントハッシングアルゴリズムは、これが最小限の数しか生じないこと、及び必要なときデータ冗長目的のためにしか生じないことを保証する。本発明の運用上の実装では、複製は、非常に小さい割合の場合でしか必要ない可能性が高い。
【０１０７】
最後に、削除演算は、正確に同じ方法で発行されるが、しかし、それぞれstore()及びstoreReplica()の代わりに、サーバでdelete()及びdeleteReplica()メソッドを実行することによる。これらのメソッドは、削除されるべきトリプルに対応する各テーブルの行を削除する。delete()及びdeleteReplica()メソッドは、必要な場合には個々のインデックスも更新する。
【０１０８】
サーバが障害になると、障害検出部は、最終的にこの事象を検出する。例えば、特定のサーバの障害検出部は、障害検出部又はネットワーク内の他のデータベース制御部の障害検出モジュールと協調することにより、この事象を検出しても良い。したがって、障害検出部は、ネットワーク内のサーバ（データベース制御部）の各々の間で分散されると考えられても良い。サーバ障害が検出されると、応答がトリガされる。例えば、障害になったサーバの検出は、生き残ったサーバ（例えば、それらのデータベース制御部）の「onFailed」イベントをトリガしても良い。サーバが、例えば「onFailed」イベント通知の受信により、別のサーバが障害になっていることを通知されると、サーバは、自身のデータベース制御部を介して回復動作を実行する。ＦＩＤが障害になった処理のＩＤであるとすると、データ復旧動作は、障害になっていない記憶ノードの各々のデータベース制御部において以下のステップを有しても良い。
【０１０９】
（１）ＦＩＤから（障害のない記憶ノードの）テーブルの行へのマッピングがあるかどうか、記憶インデックスを調べる。
【０１１０】
（２）インデックスにより識別される各トリプルについて、
ａ）該トリプルについて（つまり、該トリプルのあるバージョンを格納している各データアイテムについて）、新しいメンバ構成を用いて新しい機械ＩＤを再計算する。例えば、このような演算は、（命令分配部１６内の）記憶レイヤ１５で、場合によっては、３個の構成ＳＰＯ、ＰＯＳ、ＯＳＰの各々の中のトリプルを引数としてgetMachineIDメソッドを用いることにより、実行され得る。
【０１１１】
ｂ）トリプルのあるバージョンを格納したが、新しい構成では格納しないサーバがある場合、該トリプルをその機械から削除する。例えば、このような削除は、（命令分配部１６内の）記憶レイヤ１５によりdelete()メソッドを用いて指示され得る。
【０１１２】
ｃ）そのトリプルを格納するが、前の構成では格納していなかったサーバがある場合、該トリプルをサーバに追加する。例えば、このような追加は、（命令分配部１６内の）記憶レイヤ１５により、特定の実装の必要に応じて引数を有するが少なくとも格納されるべきトリプルのバージョンを有するstore()メソッドを用いて指示され得る。
【０１１３】
ｄ）前の構成でそのトリプルを格納し、新しい構成でも格納し続けるサーバがある場合、該サーバのテーブルのトリプルのＩＤを単に更新する。このような更新は、適切なサーバに更新命令を発行することにより実行され得る。
【０１１４】
（３）ＦＩＤからテーブルの行へのマッピングがあるかどうか、記憶インデックスを調べ、これらのトリプルについてステップ２を繰り返す。
【０１１５】
最後に、このプロシジャが同一のトリプルに対して複数回実行されるのを回避するために、本発明の実施形態は、トリプルの複製（又はバージョン）を含むサーバのうちの１個のみがデータ復旧動作を実行することを保証するメカニズムを有しても良い。これは、例えば、複製か否かに拘わらず、トリプルのあるバージョンを格納する（障害でない）サーバの最も小さい機械ＩＤを計算することにより達成されても良い。この値は、トリプルが同一のトリプルのバージョン又は複製を格納している他のノードの機械ＩＤと共に格納されているかどうか、記憶及び複製テーブルを調べることにより達成される。その他の場合、同一のトリプルのバージョン又は複製を格納している他の記憶ノードのＩＤは、命令分配部によりどのノードがトリプルのバージョンを指示するかを選択する際に用いられるマッピング関数に従って決定され得る。復旧プロシジャを実行しているサーバがそのトリプルについて最も小さいＩＤである場合、該サーバは、該トリプルについて復旧プロシジャを実行する。その他の場合、別のサーバが該トリプルを処理するので、これは単に無視される。
【０１１６】
図３は、図２の「レイヤ」が図１の構成要素とどのように関連するかの一例を示す。つまり、ＲＤＦレイヤ１１は記憶要求受信部１２を有し、記憶レイヤ１５はデータアイテム生成モジュール１４、命令分配部１６、冗長モジュール１８を有する。障害検出部１９は、どちらのレイヤにも属さないが、必要に応じてレイヤ／構成要素の一方又は両方とデータを交換し及びそれに命令を発行するよう動作可能な構成要素である。
【０１１７】
上述の態様の何れにおいても、種々の特徴は、ハードウェアで、又は１若しくは複数のプロセッサで動作するソフトウェアモジュールとして実施されても良い。ある態様の特徴は、他の態様の特徴に適用されても良い。
【０１１８】
本発明は、上述の任意の方法を実行するコンピュータプログラム又はコンピュータプログラムプロダクト、及び上述の任意の方法を実行するプログラムを格納しているコンピュータ可読媒体も提供する。本発明を実施するコンピュータプログラムは、コンピュータ可読媒体に格納されてもよい。或いは、例えば、インターネット・ウェブサイトから提供されるダウンロード可能なデータ信号のような信号形式又は任意の他の形式であってもよい。
【符号の説明】
【０１１９】
１１  ＲＤＦレイヤ
１２  記憶要求受信部
１４  データアイテム生成部
１５  記憶レイヤ
１６  命令分配部
１８  冗長モジュール
１９  障害検出部
２０  記憶ノード
３０  アプリケーション
【図１】
2013246828.tif 000004
【図２】
2013246828.tif 000005
【図３】
2013246828.tif 000006