(57)【特許請求の範囲】
【請求項１】
クエリシステムのプロセッサによって実行される方法であって、前記方法は、
データソースからオブジェクトを取り出し、前記取り出されたオブジェクトのそれぞれが、データおよび前記データを記述するメタデータを含み、
前記取り出されたオブジェクトの新しいオブジェクトのそれぞれのために、前記オブジェクトの前記メタデータおよび前記オブジェクトの要素の推論されたタイプに基づいて、
前記新しいオブジェクトからスキーマを推論することと、
前記新しいオブジェクトを記述する前記推論されたスキーマを、以前に取り出されたオブジェクトのために推論されたスキーマの間における以前の併合動作から生成された既存の累積スキーマと併合することにより統一スキーマを生成することと、
前記統一スキーマを前記累積スキーマとして記憶することと、
によって累積スキーマを動的に生成すること、
前記取り出されたオブジェクトのそれぞれの前記データをストレージサービス内に記憶すること、
を含む方法。
【請求項２】
前記累積スキーマを関係スキーマに変換すること、
前記関係スキーマをユーザに提示することであって、前記ユーザからのクエリが前記関係スキーマ上で構築される、当該提示することを更に含む、請求項１に記載の方法。
【請求項３】
前記取り出されたオブジェクトの第１のオブジェクトの前記データを第１のインデックスおよび配列インデックスの少なくとも１つ内に記憶することであって、前記ストレージサービスが前記第１のインデックスおよび前記配列インデックスを含む、当該記憶することと、
前記第１のインデックスおよび前記配列インデックスの少なくとも１つからのデータに基づいて前記クエリに応答することを更に含む、請求項２に記載の方法。
【請求項４】
キーと値のペアとして前記第１のインデックス内の第１のオブジェクトからのデータを記憶することを更に含み、前記キーと値のペアの前記値は前記データであり、前記キーと値のペアの前記キーは、前記関係スキーマと矛盾しない前記データのパスおよび前記第１のオブジェクトの固有識別子に基づく、請求項３に記載の方法。
【請求項５】
前記キーと値のペアの前記キーは、前記第１のインデックスが、キーと値のペアを最初に前記パスによって、その後、前記固有識別子によって併置するように構築される請求項４に記載の方法。
【請求項６】
配列の一部であるデータが、前記配列インデックス内に記憶される、請求項３に記載の方法。
【請求項７】
前記第１のインデックスを順序を保つインデックスストア内に記憶することを更に含み、前記ストレージサービスは、前記順序を保つインデックスストアを含む請求項３に記載の方法。
【請求項８】
マップとして前記累積スキーマのオブジェクトを選択的に識別することを更に含む、請求項２に記載の方法。
【請求項９】
前記累積スキーマの前記オブジェクトは、前記取り出されたオブジェクト内の前記オブジェクトのフィールドの発生の頻度に基づいて、マップとして識別され、
前記累積スキーマを動的に生成する間に、前記発生の頻度を追跡すること、
累積スキーマの前記オブジェクトは、閾値より下の前記発生の頻度の平均に応答して、マップとして識別されること、
の少なくとも１つを更に含む、請求項８に記載の方法。
【請求項１０】
前記マップに対応するデータをキーと値のペアとしてマップインデックスの中に記憶することを更に含み、前記キーと値のペアの前記値は前記データであり、前記キーと値のペアの前記キーは、前記関係スキーマと矛盾しない前記データのパス、第１のオブジェクトが前記データを提供する前記取り出されたオブジェクトの前記第１のオブジェクトの固有識別子、前記マップの結合キー、および前記マップ内の前記データのマップキーに基づき、
前記キーと値のペアの前記キーは、前記マップインデックスが、キーと値のペアを最初に前記パスによって、次に、前記固有識別子によって、次に、前記結合キーによって、その後、前記マップキーによって併置するように、構築され、または、
前記マップに対応するデータを補助マップインデックスの中にキーと値のペアとして記憶し、前記キーと値のペアの前記値は前記データであり、前記キーと値のペアの前記キーは、前記関係スキーマと矛盾しない前記データのパス、前記マップ内の前記データのマップキー、前記第１のオブジェクトが前記データを提供する、前記取り出されたオブジェクトの第１のオブジェクトの固有識別子、および前記マップの結合キーに基づき、
前記キーと値のペアの前記キーは、前記補助マップインデックスが、キーと値のペアを最初に前記パスによって、次に、前記マップキーによって、次に、前記固有識別子によって、その後、前記結合キーによって併置するように、構築される、請求項８に記載の方法。
【請求項１１】
前記累積スキーマを前記関係スキーマに変換することは、前記累積スキーマのトップレベルにおける各要素についてカラムでルート表を生成することを含む、請求項２に記載の方法。
【請求項１２】
前記累積スキーマを前記関係スキーマに変換することは、前記累積スキーマにおける各配列について前記関係スキーマ内に追加表を生成することをさらに含み、
前記追加表は、結合キーカラム、インデックスカラム、および、前記配列における各スカラ型データについての、値カラムを含み、前記方法は、前記配列が前記累積スキーマの前記トップレベルにあるときに、結合キーカラムを前記追加表および前記結合キーカラムに挿入することを更に含み、
前記配列が前記トップレベルより下の前記累積スキーマ内にネストされるときに、結合キーカラムを前記追加表におよび結合キーコラムを中間表に挿入することを更に含む、請求項１１に記載の方法。
【請求項１３】
前記累積スキーマを前記関係スキーマに変換することは、前記累積スキーマ内にあるよう決定された各マップについて、前記関係スキーマ内に追加表を生成することを更に含み、
前記追加表は結合キーカラム、キーカラム、および前記マップにおける各スカラ型データについての、値カラムを含み、
前記方法は、前記マップが前記累積スキーマの前記トップレベルにあるときに、結合キーカラムを前記追加表に、および結合キーコラムを前記ルート表に挿入し、および、前記マップが前記トップレベルより下の前記累積スキーマ内にネストされるときに、結合キーカラムを前記追加表におよび結合キーカラムを中間表に挿入することを更に含む、請求項１１に記載の方法。
【請求項１４】
前記関係スキーマは構造化クエリ言語（ＳＱＬ：Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）スキーマであり、前記クエリはＳＱＬであり、または、前記クエリはＨｉｖｅ‐ＱＬクエリ、ｊａｑｌクエリ、およびＸＱｕｅｒｙのうちの１つである、請求項２または請求項２に従属するいずれかの請求項に記載の方法。
【請求項１５】
プロセッサで実行可能な命令を記憶する非一時的なコンピュータで読み取り可能な媒体であって、
１つ以上のプロセッサで実行されるとき、前記命令は前記１つ以上のプロセッサに：
データソースからオブジェクトを取り出すことを行わせ、前記取り出されたオブジェクトのそれぞれが、データおよび前記データを記述するメタデータを含み、
累積スキーマを動的に生成することを行わせ、前記累積スキーマを動的に生成するために、前記取り出されたオブジェクトのそれぞれのために、前記命令は前記１つ以上のプロセッサに：
前記取り出されたオブジェクトの新しいオブジェクトのそれぞれのために：
前記オブジェクトの前記メタデータおよび前記オブジェクトの要素の推論されたタイプに基づいて、前記新しいオブジェクトからスキーマを推論することと、
前記新しいオブジェクトを記述する前記推論されたスキーマを、以前に取り出されたオブジェクトのために推論されたスキーマの間における以前の併合動作から生成された既存の累積スキーマと併合することにより統一スキーマを生成することと、
前記統一スキーマを前記累積スキーマとして記憶することと、
前記取り出されたオブジェクトのそれぞれの前記データをストレージサービス内に記憶すること、
を行わせることを特徴とする非一時的なコンピュータで読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
この出願は、２０１２年１２月２１日に出願された米国特許出願第１３／７２５，３９
９号および２０１１年１２月２３日に出願された米国仮出願第６１／５８０，１９３号に
対する優先権を主張するものである。
【０００２】
本開示は、スケーラブルな双方向データベースプラットフォームに関するものであり、
より詳細には、ストレージおよび計算を組み込む半構造データのためのスケーラブルな双
方向データベースプラットフォームに関するものである。
【背景技術】
【０００３】
本明細書に提供される背景技術の記載は、開示の文脈を一般に提示する目的のためのも
のである。現在名を挙げられた発明者らの研究は、それがこの背景技術の欄に記載される
範囲内で、ならびに、そうでない場合には出願時に先行技術として資格を与えられ得ない
背景技術の記載の態様は、本開示に対する先行技術として明示的にも暗示的にも認められ
ない。
【０００４】
伝統的なデータベースシステムは、典型的には、計算能力を有さないブロックでアドレ
ス指定可能な持続的ストレージデバイスから成る、基礎的ストレージバックエンドと密に
集積されたクエリ実行エンジンを特徴とする。これらのデバイス（ハードディスクドライ
ブおよび／またはソリッドステートドライブ）は、（ａ）データが順次または無作為にア
クセスされるかどうかに著しく依存して異なるアクセス時間、（ｂ）ブロックの粒度に設
定された固定した最小サイズを有するアクセス単位、および（ｃ）メインメモリよりも（
数桁）著しく遅いアクセス時間によって特徴付けられる。これらの特徴は、ストレージバ
ックエンドが何の重要な計算能力も有さないという想定と共に、ストレージ管理からクエ
リ実行やクエリの最適化までデータベースシステムの設計に重要な影響を与えている。
【０００５】
データベースは、本来、ビジネスの毎日の活動を管理する操作可能ストアとして機能し
ていた。データベース技術が性能と費用の両方を改善したことにつれて、ビジネスは、後
の分析のためにますます増える量の操作履歴およびビジネス状態を保持する必要性を理解
していた。そのような分析は、ビジネスが、それらの処理への洞察を得て、それらを最適
化するのに役立ち、それによって、競争的利点をもたらし、利益を増す。
【０００６】
データウェアハウジングは、この必要性から生まれた。ビジネスデータは、よく構成さ
れていることが多く、関係表に容易に適合する。データウェアハウスは、このビジネスデ
ータのオフライン分析のために構造化クエリ言語（ＳＱＬ）を提供する本質的にスケーラ
ブルな関係データベースシステムであり、読み出しを主とする作業負荷のために最適化さ
れる。例えば、データウェアハウスは、Ｔｅｒａｄａｔａや、Ｖｅｒｔｉｃａ、Ｇｒｅｅ
ｎｐｌｕｍ、およびＡｓｔｅｒ  Ｄａｔａなどの新たなベンダーのような伝統的なシステ
ムを含む。それらは、ＳＱＬインターフェース、インデックス、および高速カラム型アク
セスを提供する。
【０００７】
典型的には、データウェアハウスは、種々のソースおよび運用システムから採集される
データを、周期的に、例えば毎夜または毎週、ロードされる。このデータをクリーニング
し、キュレーションし（ｃｕｒａｔｉｎｇ）、単一スキーマに統一し、それをウェアハウ
スの中にロードする処理は、ＥＴＬ（ｅｘｔｒａｃｔ‐ｔｒａｎｓｆｏｒｍ‐ｌｏａｄ：
抽出‐変換‐ロード）として知られる。様々なソースおよびデータが増加するにつれて、
ＥＴＬ処理の複雑さもまた増加する。うまくＥＴＬを実装することは、適切なスキーマを
定義し、入力データを所定のスキーマに合致させることを含み、専門家を数週間から数カ
月間かけさせ得、変更は、実施することが困難であり得るか不可能であり得る。ＥＴＬ処
理を支援するために市場には、Ａｂｉｎｉｔｉｏ、Ｉｎｆｏｒｍａｔｉｃａ、およびＰｅ
ｎｔａｈｏなどの多くのツールがある。しかしながら、ＥＴＬ処理は、一般に、煩雑で、
脆弱で、高価なままである。
【０００８】
データ分析市場は、ビジネスユーザがウェアハウスにおけるデータの反復分析をその場
限りで実行することを容易にさせる多数のビジネスインテリジェンスおよび可視化ツール
で爆発的に増加している。ビジネスインテリジェンスツールは、ウェアハウスデータの多
次元集計を構築し、ユーザがこのデータの種々の断片および射影を通して操作して見るこ
とを可能にする。例えば、ビジネスユーザは、製品カテゴリ、地域、および店による毎月
の売上総計を見ることを望む可能性がある。次いで、彼らは、特定のカテゴリについての
毎週の売上をより深く掘り調べること、または全国についての売上を見るために画面を上
方に送ることを望む可能性がある。多次元集計はまた、オンライン分析処理（ＯＬＡＰ：
ｏｎｌｉｎｅ  ａｎａｌｙｔｉｃａｌ  ｐｒｏｃｅｓｓｉｎｇ）キューブとしても呼ばれ
得る。Ｂｕｓｉｎｅｓｓ  ＯｂｊｅｃｔおよびＣｏｇｎｏｓなどの多数のビジネスインテ
リジェンス（ＢＩ）ツールは、そのような分析を可能にし、キューブをクエリするための
Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  Ｅｘｐｒｅｓｓｉｏｎｓ（ＭＤＸ）と呼ばれる言語
をサポートする。また、ビジネスユーザが、これらのキューブおよびデータウェアハウス
を直感的に操作することを可能にする、ＭｉｃｒｏＳｔｒａｔｅｇｙ、Ｔａｂｌｅａｕ、
およびＳｐｏｔｆｉｒｅなどの多数の可視化ツールがある。
【０００９】
ここ最近、ビジネスが分析することを望むデータの型は変化している。伝統的な現実世
界のビジネスがオンラインおよび新たなオンラインのビジネス形態を進めるにつれ、これ
らのビジネスは、ＧｏｏｇｌｅやＹａｈｏｏなどの先導企業が氾濫させるデータの型を分
析する必要性がある。これらは、ウェブページ、ページビューのログ、クリックストリー
ム、ＲＳＳ（Ｒｉｃｈ  Ｓｉｔｅ  Ｓｕｍｍａｒｙ）フィード、アプリケーションログ、
アプリケーションサーバログ、システムログ、トランザクションログ、センサデータ、ソ
ーシャルネットワークフィード、ニュースフィード、およびブログ投稿などのデータの型
を含む。
【００１０】
これらの半構造データは伝統的なウェアハウスにうまく適合しない。それらは、いくつ
かの固有構造を有するが、構造は矛盾し得る。構造は、経時的に迅速に変化し得、異なる
ソースにわたって変動し得る。それらは、本来、表形式ではなく、ユーザがこれらのデー
タ上で動作させることを望むクラスタ化、分類、予測などの分析は、ＳＱＬで容易に表わ
されない。これらのデータの効果的な使用を行うための既存のツールは、煩雑で不十分で
ある。
【００１１】
結果として、新たな高度にスケーラブルなストレージおよび分析プラットフォームは、
ウェブクロールや検索を管理するためにＧｏｏｇｌｅに実装される技術によって着想を得
たＨａｄｏｏｐを生じた。それの核心において、Ｈａｄｏｏｐは、それのデータを信頼性
をもって記憶するためのクラスタ化されたファイルシステム、ＨＤＦＳ（Ｈａｄｏｏｐ  
Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）、および、より複雑な分析をサポー
トするための基本的な並列分析エンジン、ＭａｐＲｅｄｕｃｅを提供する。これらの実例
をはじめとして、Ｈａｄｏｏｐエコシステム（ｅｃｏｓｙｓｔｅｍ）は、インデックス付
きの、操作可能なストア、ＨＢａｓｅ、および、ＭａｐＲｅｄｕｃｅに頼る新たなクエリ
インターフェース、ＰｉｇやＨｉｖｅを含むように成長した。
【００１２】
Ｈｉｖｅは、クエリ最適化、キャッシング、およびインデックス付けのために伝統的な
ウェアハウスにおいて見付けられる何の最適化も無しに、クエリレイヤをＨａｄｏｏｐの
トップ上に追加するＡｐａｃｈｅプロジェクトである。代わりに、Ｈｉｖｅは、（Ｈｉｖ
ｅ‐ＱＬと呼ばれる）ＳＱＬのような言語でクエリをＨａｄｏｏｐクラスタに対して動作
されることになるＭａｐＲｅｄｕｃｅジョブに単純に変える。伝統的なビジネスユーザに
ついてのＨｉｖｅに関する３つの主な問題がある。Ｈｉｖｅは、標準ＳＱＬをサポートし
ないし、動的スキーマを有さない。更に、各Ｈｉｖｅクエリは、ソースデータの全てを再
度構文解析するＭａｐＲｅｄｕｃｅジョブを要求し、ソースデータを通した多数のパスを
要求することが多いので、Ｈｉｖｅは、双方向クエリを可能にするほど十分高速ではない
。
【００１３】
Ｉｍｐａｌａは、ＣｌｏｕｄｅｒａのＨａｄｏｏｐ実装上のＨｉｖｅ‐ＱＬクエリのた
めのリアルタイムのエンジンである。それは、Ｈｉｖｅのシーケンスファイル上の分析を
提供し、ネストされたモデルを結局はサポートし得る。しかしながら、それは動的スキー
マを有しておらず、代わりに、ユーザが、クエリされることになるデータについて前もっ
てスキーマを依然として提供することを要求する。
【００１４】
Ｐｉｇは、別のＡｐａｃｈｅプロジェクトであり、Ｈａｄｏｏｐにおけるログファイル
を処理するためにスキーマの無いスクリプト言語を提供する。ＨｉｖｅのようなＰｉｇは
、すべてをマップリデュースジョブに変換する。同様に、それは、何のインデックスも活
用せず、双方向性のために十分高速ではない。
【００１５】
Ｊａｑｌは、Ｊａｖａ（登録商標）スクリプトオブジェクト表記（ＪＳＯＮ：Ｊａｖａ
Ｓｃｒｉｐｔ  Ｏｂｊｅｃｔ  Ｎｏｔａｔｉｏｎ）ログを分析するための（ＳＱＬのよう
な宣言型言語とは対照的に）スキーマの無い宣言型言語である。Ｐｉｇのように、それは
、Ｈａｄｏｏｐ上のマップリデュースプログラムにコンパイルされ、双方向的ではない速
度を含む同じ欠点の多くを共有する。
【００１６】
Ｈａｄｏｏｐ自体は、かなり迅速に流行しており、クラウド内で容易に利用可能である
。Ａｍａｚｏｎは、クラウド内で動くＨａｄｏｏｐのＭａｐＲｅｄｕｃｅ実装に事実上等
価であり得る、Ｅｌａｓｔｉｃ  Ｍａｐ‐Ｒｅｄｕｃｅを提供する。それは、Ａｍａｚｏ
ｎのクラウドをベースとしたＳ３（Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｉｃｅ）内
に記憶されたデータに作用し、結果をＳ３に出力する。
【００１７】
Ｈａｄｏｏｐエコシステムの利点は、３つの部分からなる。第１に、システムは、極端
なサイズまでスケーリングし、任意のデータ型を記憶することができる。第２に、それは
、伝統的なウェアハウスに比べて極端に費用が低い（２０倍ほども安い）。第３に、それ
は、単一ベンダーとの固定化を回避するオープンソースである。ユーザは、正しいジョブ
のための正しいツールを選び取る能力を望み、それらのジョブを行わせるためにシステム
間でデータが動くことを回避する。Ｈａｄｏｏｐはより柔軟であるが、Ｈａｄｏｏｐの使
用は、普通は見つけることが困難である深い知識を有し特殊な技術を有するアドミニスト
レータやプログラマーを必要とする。その上、Ｈａｄｏｏｐは、双方向型であるには遅す
ぎる。最も単純なクエリでさえ、実行するのに数分から数時間かかる。
【００１８】
Ｄｒｅｍｍｅｌは、Ｇｏｏｇｌｅで内部的に開発されたツールであり、それは、ネスト
された関係的または半構造データ上でＳＱＬをベースとした分析クエリを提供する。元の
バージョンはＰｒｏｔｏＢｕｆ形式でデータを取り扱っていた。Ｄｒｅｍｍｅｌは、全て
のレコードのためにユーザが前もってスキーマを定義することを要求する。ＢｉｇＱｕｅ
ｒｙは、Ｄｒｅｍｍｅｌのクラウドをベースとした商業化であり、ＣＳＶおよびＪＳＯＮ
形式を取り扱うために拡張される。Ｄｒｉｌｌは、Ｄｒｅｍｍｅｌのオープンソースバー
ジョンである。
【００１９】
Ａｓｔｅｒｉｘは、ＪＳＯＮの一般化である抽象データモデル（ＡＤＭ）および注釈ク
エリ言語（ＡＱＬ：ａｎｎｏｔａｔｉｏｎ  ｑｕｅｒｙ  ｌａｎｇｕａｇｅ）を使用する
半構造データを管理し分析するためのシステムである。Ａｓｔｅｒｉｘは、標準ＳＱＬを
サポートせず、本開示によってもたらされる高速アクセスを有さない。
【発明の概要】
【００２０】
クエリシステムを操作する方法は、データソースからオブジェクトを取り出すことを含
み、取り出されたオブジェクトのそれぞれは、（ｉ）データおよび（ｉｉ）データを記述
するメタデータを含む。方法は、取り出されたオブジェクトのそれぞれからスキーマを推
論することによって累積スキーマを動的に生成することと、推論されたスキーマを累積ス
キーマと併合することと、を含む。方法は、取り出されたオブジェクトのそれぞれのデー
タをストレージサービス内に記憶することを含む。方法は、クエリをユーザから受信する
ことと、ストレージサービスによって記憶されたデータに基づいてクエリに応答すること
と、を含む。
【００２１】
方法はまた、累積スキーマを関係スキーマに変換することと、関係スキーマをユーザに
提示することと、を含み、ユーザからのクエリは、関係スキーマ上で構築される。方法は
また、取り出されたオブジェクトのそれぞれのデータを（ｉ）第１のインデックスおよび
（ｉｉ）配列インデックスの少なくとも１つ内に記憶することを含み、ストレージサービ
スは、第１のインデックスおよび配列インデックスを含む。方法はまた、第１のインデッ
クスおよび配列インデックスの少なくとも１つからのデータに基づいてクエリに応答する
ことを含む。
【００２２】
方法はまた、取り出されたオブジェクトからのデータをキーと値のペアとして第１のイ
ンデックス内に記憶することを含み、キーと値のペアの値はデータであり、キーと値のペ
アのキーは、（ｉ）関係スキーマと矛盾しないデータのパスおよび（ｉｉ）取り出された
オブジェクトの固有識別子に基づく。キーと値のペアのキーは、第１のインデックスが、
キーと値のペアを最初にパスによって、その後、固有識別子によって併置するように、構
築される。配列の一部であるデータは、配列インデックス内に記憶される。配列の一部で
あるデータは、第１のインデックス内に記憶されない。
【００２３】
データは、配列インデックス内にキーと値のペアとして記憶され、キーと値のペアの値
はデータであり、キーと値のペアのキーは、（ｉ）関係スキーマと矛盾しないデータのパ
ス、（ｉｉ）取り出されたオブジェクトの固有識別子、および（ｉｉｉ）配列内のデータ
の位置のインデックスに基づく。キーと値のペアのキーは、配列インデックスが、キーと
値のペアを最初にパスによって、次に、固有識別子によって、その後、インデックスによ
って併置するように、構築される。キーと値のペアのキーは、結合キーに更に基づく。キ
ーと値のペアのキーは、配列インデックスが、キーと値のペアを最初にパスによって、次
に、固有識別子によって、次に、結合キーによって、その後、インデックスによって併置
するように、構築される。方法はまた、補助配列インデックス内にデータを選択的に記憶
することを含む。
【００２４】
データは、補助配列インデックス内にキーと値のペアとして記憶され、キーと値のペア
の値はデータであり、キーと値のペアのキーは、（ｉ）関係スキーマと矛盾しないデータ
のパス、（ｉｉ）配列内のデータの位置のインデックス、および（ｉｉｉ）オブジェクト
の固有識別子に基づく。キーと値のペアのキーは、補助配列インデックスが、キーと値の
ペアを最初にパスによって、次に、インデックスによって、その後、固有識別子によって
併置するように、構築される。キーと値のペアのキーは、結合キーに更に基づく。キーと
値のペアのキーは、補助配列インデックスが、キーと値のペアを最初にパスによって、次
に、インデックスによって、次に、固有識別子によって、その後、結合キーによって併置
するように、構築される。
【００２５】
方法はまた、順序を保つインデックスストア内に第１のインデックスを記憶することを
含み、ストレージサービスは、順序を保つインデックスストアを含む。方法はまた、順序
を保つインデックスストア内に配列インデックスを記憶することを含む。関係スキーマは
構造化クエリ言語（ＳＱＬ）スキーマであり、クエリはＳＱＬクエリである。クエリは、
Ｈｉｖｅ‐ＱＬクエリ、ｊａｑｌクエリ、およびＸＱｕｅｒｙのうちの１つである。
【００２６】
方法はまた、マップとして累積スキーマのオブジェクトを選択的に識別することを含む
。累積スキーマのオブジェクトは、取り出されたオブジェクト内のオブジェクトのフィー
ルドの発生の頻度に基づいてマップとして識別される。方法はまた、発生頻度を追跡する
間に、累積スキーマを動的に生成することを含む。累積スキーマのオブジェクトは、閾値
より下の発生の頻度の平均に応答して、マップとして識別される。
【００２７】
方法はまた、マップに対応するデータをキーと値のペアとしてマップインデックスの中
に記憶することを含み、キーと値のペアの値はデータであり、キーと値のペアのキーは、
（ｉ）関係スキーマと矛盾しないデータのパス、（ｉｉ）データを提供する取り出された
オブジェクトの固有識別子、（ｉｉｉ）マップの結合キー、および（ｉｖ）マップ内のデ
ータのマップキーに基づく。キーと値のペアのキーは、マップインデックスが、キーと値
のペアを最初にパスによって、次に、固有識別子によって、次に、結合キーによって、そ
の後、マップキーによって併置するように、構築される。
【００２８】
方法はまた、マップに対応するデータをキーと値のペアとして補助マップインデックス
の中に記憶することを含み、キーと値のペアの値はデータであり、キーと値のペアのキー
は、（ｉ）関係スキーマと矛盾しないデータのパス、（ｉｉ）マップ内のデータのマップ
キー、（ｉｉｉ）データを提供する取り出されたオブジェクトの固有識別子、および（ｉ
ｖ）マップの結合キーに基づく。キーと値のペアのキーは、補助マップインデックスがキ
ーと値のペアを最初にパスによって、次に、マップキーによって、次に、固有識別子によ
って、その後、結合キーによって併置するように、構築される。
【００２９】
累積スキーマを関係スキーマに変換することは、累積スキーマのトップレベルにおける
各要素についてのカラムを有するルート表を生成することを含む。累積スキーマを関係ス
キーマに変換することは、累積スキーマにおける各配列について関係スキーマ内に追加表
を生成することを含む。追加表は、（ｉ）結合キーカラム、（ｉｉ）インデックスカラム
、および（ｉｉｉ）配列における各スカラ型データについて、値カラムを含む。
【００３０】
方法はまた、配列が累積スキーマのトップレベルにあるときに、結合キーカラムを追加
表におよびルート表に挿入することを含む。方法はまた、配列がトップレベルより下の累
積スキーマ内にネストされるときに、結合キーカラムを追加表におよび中間表に挿入する
ことを含む。累積スキーマを関係スキーマに変換することは、累積スキーマにおける各マ
ップについて関係スキーマ内に追加表を生成することを含む。
【００３１】
追加表は、（ｉ）結合キーカラム、（ｉｉ）キーカラム、および（ｉｉｉ）マップ内の
各スカラ型データについて、値カラムを含む。キーカラムは文字列型である。方法はまた
、マップが累積スキーマのトップレベルにあるときに、結合キーカラムを追加表におよび
ルート表に挿入することを含む。
【００３２】
方法はまた、マップがトップレベルより下の累積スキーマ内にネストされるときに、結
合キーカラムを追加表におよび中間表に挿入することを含む。方法はまた、取り出された
オブジェクトのデータ値をキーと値のペアとして値インデックス内に選択的に記憶するこ
とを含み、キーと値のペアのキーは、（ｉ）関係スキーマと矛盾しないデータ値のパスお
よび（ｉｉ）データ値に基づき、キーと値のペアの値は、取り出されたオブジェクトの固
有識別子に基づき、ストレージサービスは、値インデックスを含む。
【００３３】
キーと値のペアのキーは、値インデックスが、キーと値のペアを最初にパスによって、
その後、データ値によって併置するように、構築される。データ値が配列の一部であると
き、キーと値のペアの値は、配列におけるデータ値のインデックスに更に基づく。キーと
値のペアの値は、配列の結合キーに更に基づく。データ値がマップの一部であるとき、キ
ーと値のペアの値は、マップにおけるデータ値のマップキーに更に基づく。
【００３４】
キーと値のペアの値は、マップの結合キーに更に基づく。方法はまた、メタデータをデ
ータソースから取得された生データに追加することによって、取り出されたオブジェクト
を生成することを含む。取り出されたオブジェクトについてスキーマを推論することは、
取り出されたオブジェクトのメタデータおよび取り出されたオブジェクトの要素の推論さ
れた型に基づいて実行される。取り出されたオブジェクトのそれぞれについて、取り出さ
れたオブジェクトのデータは値を含み、取り出されたオブジェクトのメタデータは、値の
名前を含む。
【００３５】
取り出されたオブジェクトのそれぞれは、Ｊａｖａスクリプトオブジェクト表記（ＪＳ
ＯＮ）オブジェクトである。累積スキーマは、Ｊａｖａスクリプトオブジェクト表記（Ｊ
ＳＯＮ）スキーマである。方法はまた、取り出されたオブジェクトのそれぞれを行インデ
ックス内に選択的に記憶することを含み、ストレージサービスは、行インデックスを含む
。取り出されたオブジェクトは、キーと値のペアとして行インデックス内に記憶され、キ
ーと値のペアのキーは、取り出されたオブジェクトの固有識別子であり、キーと値のペア
の値は、取り出されたオブジェクト全体の直列化である。
【００３６】
本開示の適用性の更なる範囲は、以下に提供される発明を実施するための形態から明ら
かになるであろう。発明を実施するための形態および特定の例は、例示目的のために意図
されるものであり、開示の範囲を限定することを意図されないことが理解されるべきであ
る。
【図面の簡単な説明】
【００３７】
本開示は、発明を実施するための形態および添付の図面からより十分に理解されること
になるであろう。
【図１Ａ】クラウドリソースを活用する半構造データのためのスケーラブルな分析プラットフォーム用のネットワークアーキテクチャ例を描写する。
【図１Ｂ】ユーザエンドにおけるサーバアプライアンスを用いる半構造データのためのスケーラブルな分析プラットフォーム用のネットワークアーキテクチャ例を描写する。
【図１Ｃ】サーバシステムの機能的ブロック図である。
【図２Ａ】半構造データのためのスケーラブルな分析プラットフォーム例の機能的ブロック図である。
【図２Ｂ】半構造データのためのスケーラブルな分析プラットフォームのクエリシステム例の機能的ブロック図である。
【図３】採集したデータを組み込む方法例を描写するフローチャートである。
【図４】スキーマを推論する方法例を描写するフローチャートである。
【図５】２つのスキーマを併合する方法例を描写するフローチャートである。
【図６】スキーマを折り畳む方法例を描写するフローチャートである。
【図７】データをインデックスにポピュレートする方法例を描写するフローチャートである。
【図８】マップ装飾を実行する方法例を描写するフローチャートである。
【図９】ＪＳＯＮスキーマから関係スキーマを生成する方法例を描写するフローチャートである。
【００３８】
図面中、参照番号は、類似および／または同一要素を識別するために再使用され得る。
【発明を実施するための形態】
【００３９】
概要
本開示は、半構造データをクエリするためにＳＱＬ（構造化クエリ言語）に準拠したイ
ンターフェースを提供することが可能な分析プラットフォームを記載する。例示目的のた
めだけに、半構造データは、ＪＳＯＮ（ＪａｖａＳｃｒｉｐｔ  Ｏｂｊｅｃｔ  Ｎｏｔａ
ｔｉｏｎ）形式で表現される。他の自己記述式の半構造形式は、本開示の原理に従って使
用され得る。ソースデータは自己記述式である必要はない。記述は、プロトコルバッファ
のようなものと同様の場合であろうように、データとは分離され得る。タグをデータに適
用するための規則、発見的問題解決法、またはラッパー関数がある限り、任意の入力デー
タは、ＪＳＯＮ形式に類似したオブジェクトに変えられ得る。
【００４０】
本開示に係る分析プラットフォームの種々の実装では、以下の利点のいくつかまたは全
てが実現される。
【００４１】
速度
分析プラットフォームは、その場限りの、探索的、および双方向型の分析をサポートす
るために高速のクエリ応答時間を提供する。ユーザは、クエリを送信し、その結果を見る
ためにその日または次の日の後で戻すこと無く、データにおける隠された洞察を迅速に発
見するためにこのシステムを使用することができる。分析プラットフォームは、インデッ
クス内に採集したデータの全てを記憶するインデックスストアに頼り、それは、高速応答
時間を可能にする。
【００４２】
２つの主なインデックス、ビッグインデックス（ＢＩ：ＢｉｇＩｎｄｅｘ）および配列
インデックス（ＡＩ：ＡｒｒａｙＩｎｄｅｘ）が使用され、それらは以下により詳細に記
載される。これらは、パスインデックスとカラム指向型ストアの中間物である。カラム指
向型ストアのように、それらは、クエリが、関連したフィールドにあるデータだけを取り
出すことを可能にし、それによって、Ｉ／Ｏ（入出力）デマンドを減らし、性能を改善す
る。しかしながら、カラムストアとは異なり、これらのインデックスは、非常に多くのフ
ィールドを有する複雑なネストされたオブジェクトおよびコレクションに適する。他のア
クセスパターンについて、分析プラットフォームエンジンは、値インデックス（ＶＩ：Ｖ
ａｌｕｅＩｎｄｅｘ）を含む、以下により詳細に記載される補助インデックスを維持する
。伝統的なデータベースインデックスのように、値インデックスは、特定のフィールド値
または値の範囲について高速の対数的アクセスを提供する。これらのインデックスは、ク
エリを満たすために取り出すことが必要なデータを著しく削減し、それによって、応答時
間を改善する。
【００４３】
動的スキーマ
分析プラットフォームは、ユーザが、予測されたスキーマを事前に知る必要がないよう
に、データ自体からスキーマを推論し、また、データがロードされ得る前に、スキーマを
予め宣言する。半構造データは、経時的にも異なるソースにわたっても可変な構造を有し
得る。従って、エンジンは、データが到着する際に動的にデータからスキーマ（または構
造）を計算し更新する。この計算されたスキーマに基づく関係スキーマは、ユーザに提示
され、彼らはそれをクエリを構成するために使用することができる。
【００４４】
プログラマーにデータコレクションのスキーマをそれらをクエリする前に指定すること
を要求する以前の分析エンジンとは異なり、本プラットフォームは、採集したオブジェク
トの全ての中で基礎的スキーマを計算する（または、推論する）。動的スキーマ特性が原
因で、かなりの柔軟性がある。ソースデータを生成するアプリケーションは、アプリケー
ションが進化するにつれ構造を変えることができる。分析家は、期間毎にどのようにスキ
ーマが変動するかを指定する必要性無しに、様々な期間からデータを集計しクエリするこ
とができる。その上、数か月かかり得、また、スキーマに適合しないデータの排除を要求
することが多い、グローバルスキーマを設計し実施する必要性は無い。
【００４５】
「スキーマフリー」として記載されることがあるＭａｐＲｅｄｕｃｅまたはＰｉｇのよ
うな他の分析システムは、２つの主な欠点を有する。第１に、それらは、推論されたスキ
ーマをユーザに自動的に提示する代わりに、データをクエリするためにユーザにスキーマ
を知ることを要求する。第２に、それらは、全てのクエリ上でオブジェクトおよびそれら
の構造を構文解析し解釈する一方で、分析プラットフォームは、ロード時にオブジェクト
を構文解析しインデックス付けする。これらのインデックスは、上述のように、後のクエ
リが、かなり高速に動作することを可能にする。以前のエンジンは、基礎的データからの
精密で簡潔なスキーマの自動的な推論を提供しない。
【００４６】
ＳＱＬ
分析プラットフォームは、ユーザが、既存のＳＱＬツール（例えば、報告、可視化、お
よびＢＩツール）や専門技術を活用することができるように、標準ＳＱＬクエリインター
フェース（例えば、ＡＮＳＩ  ＳＱＬ２００３に準拠したインターフェース）を露出する
。結果として、ＳＱＬまたはＳＱＬツールに精通するビジネスユーザは、データウェアハ
ウスをロードする必要性無しに、半構造データに直接的にアクセスしクエリすることがで
きる。伝統的なＳＱＬをベースとしたツールは、ＪＳＯＮまたは他の半構造データ形式を
取り扱わないので、分析プラットフォームは、ＪＳＯＮオブジェクトの計算されたスキー
マの関係ビューを提示する。それは、正規化ビューを提示し、サイズを管理することが可
能であるビューを保つための最適化を組み込む。関係ビューは、スキーマ内にいくつかの
表を提示し得るが、これらの表は、必ずしも具体化されない。
【００４７】
表形式の半構造データの表現をより良く適応させるために、分析プラットフォームは、
「マップ」オブジェクトを自動的に識別することができる。マップは、オブジェクト（ま
たはネストされたオブジェクト）であり、そのオブジェクトにおいて、フィールド名と値
の両方が検索され得、クエリされ得る。例えば、オブジェクトは、フィールド名として日
付と、値についてのページビューのような統計と、を含有し得る。関係ビューにおいて、
マップは別個の表に抽出され、キーがキーカラム内にあり、値が値カラム内にあるように
、データはピボットされる。
【００４８】
スケーリングおよび融通性
分析プラットフォームは、大きなデータセットサイズを取り扱うためにスケーリングす
る。分析プラットフォームは、独立ノードにわたって内部データ構造や処理を自動的にお
よび動的に分散することができる。
【００４９】
分析プラットフォームは、Ａｍａｚｏｎ  Ｗｅｂ  Ｓｅｒｖｉｃｅｓのようなパブリッ
ククラウドと、Ｒａｃｋｓｐａｃｅなどの、ユーザの組織によって運営されたまたは第３
者によって提供された仮想サーバ環境のような、プライベートクラウドを含む、仮想化「
クラウド」環境のために設計され構築される。Ｓ３（Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ  Ｓ
ｅｒｖｉｃｅ）、ＥＣ２（Ｅｌａｓｔｉｃ  Ｃｏｍｐｕｔｅ  Ｃｌｏｕｄ）、およびＥｌ
ａｓｔｉｃ  Ｂｌｏｃｋ  Ｓｔｏｒａｇｅ（ＥＢＳ）を含むＡｍａｚｏｎ  Ｗｅｂ  Ｓｅ
ｒｖｉｃｅｓの種々の構成要素が活用され得る。分析プラットフォームは融通がきき、そ
れは、オンデマンドで任意のサイズに拡大縮小できることを意味し、Ａｍａｚｏｎ  Ｓ３
などの長期ストア上にそれの内部データ構造を記憶することによって休止状態にすること
ができる。分析プラットフォームはまた、マルチテナンシーおよびマルチユーザサポート
を有する。
【００５０】
分析プラットフォームは、４つの構成要素、すなわち、プロキシ、メタデータサービス
、クエリエクゼキュータ、およびストレージサービスを有するサービスをベースとしたア
ーキテクチャを使用する。より多くのデータセットをサポートするように分析プラットフ
ォームエンジンをスケーリングすることは、より高速な応答を提供し、より多くのユーザ
をサポートし、実行エンジンは並列化され、ストレージサービスは独立の低費用のサーバ
ノードにわたって分割される。これらのノードは、ホスト型環境における現実のサーバま
たは仮想サーバとすることができる。エクゼキュータおよびストレージサービスは結合解
除されるので、それらは独立してスケーリングされ得る。この結合解除、スケールアウト
アーキテクチャは、ユーザが、ＡＷＳのようなクラウド環境が提供するストレージおよび
計算についての融通性をオンデマンドに活用することを可能にする。
【００５１】
ストレージサービスは、種々の分割手法を用いて構成可能である。その上、基礎的デー
タ構造（インデックスおよびメタデータ）は、使用中ではないときにシステムを休止状態
にするために、Ａｍａｚｏｎ  Ｓ３のような長期ストレージに移され得、それによって、
費用を減らす。
【００５２】
同期
分析プラットフォームは、それの内容をＨＤＦＳ（Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔ
ｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）、Ａｍａｚｏｎ  Ｓ３（Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ
Ｓｅｒｖｉｃｅ）、およびＭｏｎｇｏＤＢなどの非ＳＱＬストアのようなリポジトリか
らのソースデータと自動的に同期させ、それによって、そのソースデータを複製するよう
に構成され得る。これらのソースは、分析プラットフォームが変更したデータを採集する
ことができるように、変更、追加、および更新のために連続的に監視され得る。これは、
クエリ結果が比較的最新であることを可能にする。
【００５３】
スキーマ推論
分析プラットフォームは、ソース内に現れるデータに応答して以下のアクション、すな
わち、（１）データから統一された半構造（ＪＳＯＮなどの）スキーマを推論し、（２）
スキーマについての関係ビューを生成し、（３）物理インデックスにデータをポピュレー
トし、（４）そのインデックスを活用するクエリを実行することを取る。アクション１、
２、および３の一部または全ては、データソースからデータを通す単一パスだけを可能に
するようにパイプライン化され得る。
【００５４】
第１のアクション、スキーマ推論が最初に記載される。
【００５５】
半構造データの導入
ＪＳＯＮは、人気上昇中の自己記述型の、半構造データ形式であり、インターネット上
のデータ交換にごく普通に使用される。再び、ＪＳＯＮが例示のために、およびＪＳＯＮ
形式を使用する後の例のための文脈を提供するために、ここに記載されるが、本開示はＪ
ＳＯＮに限定されない。
【００５６】
簡単には、ＪＳＯＮオブジェクトは、文字列フィールド（またはカラム）および潜在的
に異なる型、すなわち、数字、文字列、配列、オブジェクト等の対応する値から成る。Ｊ
ＳＯＮオブジェクトはネストされ得、フィールドは、多値、例えば、配列、ネストされた
配列等とすることができる。明細は、ｈｔｔｐ：／／ＪＳＯＮ．ｏｒｇで見付けられ得る
。追加的な詳細は、ｈｔｔｐ：／／ｔｏｏｌｓ．ｉｅｔｆ．ｏｒｇ／ｈｔｍｌ／ｄｒａｆ
ｔ‐ｚｙｐ‐ｊｓｏｎ‐ｓｃｈｅｍａ‐０３で利用可能な、２０１０年１１月２２日の“
Ａ  ＪＳＯＮ  Ｍｅｄｉａ  Ｔｙｐｅ  ｆｏｒ  Ｄｅｓｃｒｉｂｉｎｇ  ｔｈｅ  Ｓｔｒ
ｕｃｔｕｒｅ  ａｎｄ  Ｍｅａｎｉｎｇ  ｏｆ  ＪＳＯＮ  Ｄｏｃｕｍｅｎｔｓ”、ＩＥ
ＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ）ｄｒａｆｔ
‐ｚｙｐ‐ｊｓｏｎ‐ｓｃｈｅｍａ‐０３において見付けられ、これらについては本明細
書では引用している。更なる型を含むためのＪＳＯＮの一般化、例えば、ＢＳＯＮ（Ｂｉ
ｎａｒｙ  ＪＳＯＮ）がある。その上、ＸＭＬ、Ｐｒｏｔｏｂｕｆ、Ｔｈｒｉｆｔ等のよ
うな他の半構造形式はすべて、ＪＳＯＮに変換され得る。ＸＭＬを使用する場合、クエリ
は、ＳＱＬの代わりにＸＱｕｅｒｙに準拠し得る。
【００５７】
以下はＪＳＯＮオブジェクト例である。
｛  ”ｐｌａｙｅｒ”：  ｛  ”ｆｎａｍｅ”：  ”Ｇｅｏｒｇｅ”，  ”ｌｎａｍｅ”
：  ”Ｒｕｔｈ”，  ”ｎｉｃｋｎａｍｅ”：  
”Ｂａｂｅ”｝，  ”ｂｏｒｎ”：  ”Ｆｅｂｒｕａｒｙ  ６，  １９８５”，  
”ａｖｇ”：  ０．３４２，  ”ＨＲ”：  ７１４，  
”ｔｅａｍｓ”：  ［  ｛  ”ｎａｍｅ”：  ”Ｂｏｓｔｏｎ  Ｒｅｄ  Ｓｏｘ”，  ”
ｙｅａｒｓ”：  ”１９１４−１９１９”  ｝，
｛  ”ｎａｍｅ”：  ”Ｎｅｗ  Ｙｏｒｋ  Ｙａｎｋｅｅｓ”，  ”ｙｅａｒｓ”：  ”
１９２０−１９３４”  ｝，  
｛  ”ｎａｍｅ”：  ”Ｂｏｓｔｏｎ  Ｂｒａｖｅｓ”，  ”ｙｅａｒｓ”：  ”１９３
５”  ｝  ］  ｝
【００５８】
半構造オブジェクトの構造は、オブジェクト毎に変動することができる。従って、同じ
野球データにおいて、以下のオブジェクトが見付けられ得る。
｛  ”ｐｌａｙｅｒ”：  ｛  ”ｆｎａｍｅ”：  ”Ｓａｎｄｙ”，  ”ｌｎａｍｅ”：
”Ｋｏｕｆａｘ”｝，  ”ｂｏｒｎ”：  
”Ｄｅｃｅｍｂｅｒ  ３０，  １９３５”，  
”ＥＲＡ”：  ２．７６，  ”ｓｔｒｉｋｅｏｕｔｓ”：  ２３９６，  
”ｔｅａｍｓ”：  ［  ｛  ”ｎａｍｅ”：  ”Ｂｒｏｏｋｌｙｎ  ／  ＬＡ  Ｄｏｄｇ
ｅｒｓ”，  ”ｙｅａｒｓ”：  ”１９５５−  １９６６”  ｝  ］  ｝
【００５９】
スキーマは、データコレクションにおいて見付けられる可能な構造およびデータ型を記
述する。このスキーマは、フィールドの名前、対応する値についての型、およびネスト化
関係を含む。それ故、上記２つのオブジェクトについてのスキーマは、
｛  ”ｐｌａｙｅｒ”：  ｛  ”ｆｎａｍｅ”：  ｓｔｒｉｎｇ，  ”ｌｎａｍｅ”：  
ｓｔｒｉｎｇ，  ”ｎｉｃｋｎａｍｅ”：  ｓｔｒｉｎｇ
｝，  ”ｂｏｒｎ”：  ｓｔｒｉｎｇ，  ”ａｖｇ”：  ｎｕｍｂｅｒ，  ”ＨＲ”：  
ｎｕｍｂｅｒ，  ”ＥＲＡ”：  ｎｕｍｂｅｒ，
”ｓｔｒｉｋｅｏｕｔｓ”：  ｎｕｍｂｅｒ，  
”ｔｅａｍｓ”：  ［  ｛  ”ｎａｍｅ”：  ｓｔｒｉｎｇ，  ”ｙｅａｒｓ”：  ｓｔ
ｒｉｎｇ  ｝  ］  ｝
であることになる。
【００６０】
上記は、スキーマを例示するためにドキュメント全体を通して使用される表記であるが
、より完全な明細は、ｈｔｔｐ：／／ＪＳＯＮ‐ｓｃｈｅｍａ．ｏｒｇで利用可能なＪＳ
ＯＮスキーマである。例えば、ＪＳＯＮスキーマにおける型は、文字列または“ｉｎｔ．
”のような引用符に一般に含まれる。この開示における簡潔性および可読性のために、引
用符は省略されることになる。
【００６１】
あるいは、半構造オブジェクトは、ノードとしてフィールドおよびアトミック値として
葉を有するツリーとして見られ得る。オブジェクトまたはスキーマにおけるパスは、この
ツリーにおけるパス、例えば、“ｐｌａｙｅｒ．ｆｎａｍｅ”、“ｔｅａｍｓ［］．ｎａ
ｍｅ”である。
【００６２】
反復的スキーマ推論
ユーザがデータセットの質問をすることができる前に、彼らは、スキーマ、すなわち、
どのフィールドまたは次元がクエリのために利用可能であるかを知る必要がある。多くの
場合において、分析家は、データを生成することを担当しないので、彼らは、何がレコー
ドされていて利用可能であるかに気付いていない。例えば、上記野球例において、分析家
は、打者だけがコレクションにおいて観察されている場合、“ＥＲＡ”フィールドが利用
可能であったことを知り得ない。従って、分析プラットフォームは、採集したデータから
統一されたスキーマを計算し（または、推論し）、分析家がクエリを定式化する際に支援
するためにスキーマの関係ビューを提示する。
【００６３】
分析プラットフォームは、スキーマの精密さおよび簡潔さを最適化することを目的とし
たスキーマを作り出すことを目的とする。一般に、精密さは、スキーマが、観察されたか
採集したデータにおける全ての構造を表現することを意味し、まだ見られていない構造を
許可しない。簡潔さは、スキーマが十分に小さいので、人間によって読み取られ解釈され
得ることを意味する。
【００６４】
スキーマを動的に生成する一般的なアプローチは、過去のオブジェクトから推論された
「現在の」スキーマで開始し、新たなオブジェクトが採集されたときにスキーマを増やす
ことである。単純に、新たなスキーマ（Ｓ＿ｎｅｗ）に到着するように新たなオブジェク
ト（Ｏ＿ｎｅｗ）のスキーマ（ｔｙｐｅ）と現在のスキーマ（Ｓ＿ｃｕｒｒ）を併合する
。
Ｓ＿ｎｅｗ＝ｍｅｒｇｅ（Ｓ＿ｃｕｒｒ，ｔｙｐｅ（Ｏ＿ｎｅｗ））
【００６５】
概略を言えば、併合処理は、２つのスキーマの融合を取り、共通フィールド、サブオブ
ジェクト、および配列を折り畳み、新たなものが現れるときにそれらを追加する。これは
、以下に更に詳細に記述される。
【００６６】
オブジェクト
以下の例のいくつかは、Ｆｉｒｅｈｏｓｅとして呼ばれる、Ｔｗｉｔｔｅｒからのデー
タストリームの出力に似ているデータを使用する。ＴｗｉｔｔｅｒのＦｉｒｅｈｏｓｅは
、ツイート“ｔｗｅｅｔｅｄ（ツイート済）”およびそれらのツイートについてのメタデ
ータ、例えば、ユーザ、位置、トピック等）を表現するＪＳＯＮオブジェクトのストリー
ム（終わりのないシーケンス）を与える。これらのツイートは、現代のウェブフレームワ
ーク（例えば、Ｒｕｂｙ  ｏｎ  Ｒａｉｌｓ（ルビーオンレイルズ））、モバイルアプリ
ケーション、センサおよびデバイス（電力計、サーモスタット）等によって生成されたも
のなどの、多くの他の型のイベントログデータに類似する。Ｔｗｉｔｔｅｒデータに類似
するが、以下の例は、説明目的のために、実際のＴｗｉｔｔｅｒデータから逸れる。
【００６７】
基本的なＪＳＯＮオブジェクトは対処するのが簡単であり、オブジェクトに見られる型
を単純に推論する。例えば、以下のオブジェクトを考える。
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ”Ｔｈｕ  Ｎｏｖ  ０８”，  ”ｉｄ”：  ２６６３
５３８３４，  
”ｓｏｕｒｃｅ”：  ”Ｔｗｉｔｔｅｒ  ｆｏｒ  ｉＰｈｏｎｅ”，  
”ｔｅｘｔ”：  ”  ＠ｉｌｓｔａｖｒａｃｈｉ：  ｗｏｕｌｄ  ｌｏｖｅ  ｄｉｎｎｅ
ｒ．  Ｃｏｏｋ  ｔｈｉｓ：  
ｈｔｔｐ：／／ｂｉｔ．ｌｙ／９５５Ｆｆｏ”，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ２９４７１４９７，  ”ｓｃｒｅｅｎ＿ｎａｍｅ”：
”Ｍａｓｈａｈ０８”  ｝，  
”ｆａｖｏｒｉｔｅｄ”：  ｆａｌｓｅ｝
【００６８】
そのオブジェクトから推論されたスキーマは、
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ｓｔｒｉｎｇ，  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｓ
ｏｕｒｃｅ”：  ｓｔｒｉｎｇ，  ”ｔｅｘｔ”：  ｓｔｒｉｎｇ，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｓｃｒｅｅｎ＿ｎａｍｅ”：  ｓ
ｔｒｉｎｇ  ｝，  ”ｆａｖｏｒｉｔｅｄ”：  ｂｏｏｌｅａｎ  ｝
であることになる。
【００６９】
新たなオブジェクトが到着する際、新たなフィールドは、フィールドの組上で融合を実
行することによって追加され得る。時々、フィールドは繰り返されることになるが、それ
の型は変動し、条件は型多様性と呼ばれる。スキーマは、型多様性を表現するために同じ
キーで多数の属性を使用する。
【００７０】
ログ形式は変わることが多く、開発者は、新たなフィールドを追加し得、またはフィー
ルド型を変え得る。具体例として、本来、数字であった、ツイートを識別する“ｉｄ”フ
ィールドを考える。しかしながら、ツイートの数が増えるにつれ、一定のプログラミング
言語は、そのような多くの数を取り扱うことができず、従って、“ｉｄ”フィールドは、
文字列に変更されている。従って、次の形式の新たなレコード、
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ”Ｔｈｕ  Ｎｏｖ  １０”，  ”ｉｄ”：  ”２６６
３５３８４０”，  
”ｓｏｕｒｃｅ”：  ”Ｔｗｉｔｔｅｒ  ｆｏｒ  ｉＰｈｏｎｅ”，  
”ｔｅｘｔ”：  ”＠ｂｉｎｋｅｒｔ：  ｃｏｍｅ  ｗｉｔｈ  ｍｅ  ｔｏ  ＠ｉｌｓｔ
ａｖｒａｃｈｉ  ｐｌａｃｅ”，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ２９４７１４９７，  ”ｓｃｒｅｅｎ＿ｎａｍｅ”：
”Ｍａｓｈａｈ０８”  ｝，  
”ｒｅｔｗｅｅｔ＿ｃｏｕｎｔ”：  ０  ｝
を見たことを想定する。
【００７１】
ここで文字列“ｉｄ”が見られ、新たなフィールド“ｒｅｔｗｅｅｔ＿ｃｏｕｎｔ”が
現れているので、スキーマは以下のように拡張される。
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ｓｔｒｉｎｇ，  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｉ
ｄ”：  ｓｔｒｉｎｇ，  ”ｓｏｕｒｃｅ”：  
ｓｔｒｉｎｇ，  ”ｔｅｘｔ”：  ｓｔｒｉｎｇ，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｓｃｒｅｅｎ＿ｎａｍｅ”：  ｓ
ｔｒｉｎｇ  ｝，  
”ｒｅｔｗｅｅｔ＿ｃｏｕｎｔ”：  ｎｕｍｂｅｒ  ｝
【００７２】
“ｉｄ”は、文字列（ｓｔｒｉｎｇ）として１度、数字（ｎｕｍｂｅｒ）として１度の
２度現れることに留意する。時々、ネストされたオブジェクトの構造は変動する。例えば
、ユーザについてのより多くのプロフィール情報、
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ”Ｔｈｕ  Ｎｏｖ  １０”，  ”ｉｄ”：  ”２６６
３５３８７５”，  
”ｓｏｕｒｃｅ”：  ”Ｔｗｉｔｔｅｒ  ｆｏｒ  ｉＰｈｏｎｅ”，  
”ｔｅｘｔ”：  ”＠ｂｉｎｋｅｒｔ：  ｃｏｍｅ  ｗｉｔｈ  ｍｅ  ｔｏ  ＠ｉｌｓｔ
ａｖｒａｃｈｉ  ｐｌａｃｅ”，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ”２９４７１７５５”，  ”ｓｃｒｅｅｎ＿ｎａｍｅ
”：  ”ｍａｓｈａｈ０８”，  
”ｌｏｃａｔｉｏｎ”：  ”Ｓａｒａｔｏｇａ，  ＣＡ”，  ”ｆｏｌｌｏｗｅｒｓ＿ｃ
ｏｕｎｔ”：  ２２  ｝，  
”ｒｅｔｗｅｅｔ＿ｃｏｕｎｔ”：  ０  ｝
を追加したことを想定する。
【００７３】
その場合において、プラットフォームは、以下のスキーマを得るために“ｕｓｅｒ（ユ
ーザ）”ネスト化スキーマを再帰的に併合する。
｛  ”ｃｒｅａｔｅｄ＿ａｔ”：  ｓｔｒｉｎｇ，  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｉ
ｄ”：  ｓｔｒｉｎｇ，  ”ｓｏｕｒｃｅ”：  
ｓｔｒｉｎｇ，  ”ｔｅｘｔ”：  ｓｔｒｉｎｇ，  
”ｕｓｅｒ”：  ｛  ”ｉｄ”：  ｎｕｍｂｅｒ，  ”ｉｄ”：  ｓｔｒｉｎｇ，  ”ｓ
ｃｒｅｅｎ＿ｎａｍｅ”：  ｓｔｒｉｎｇ，  ”ｌｏｃａｔｉｏｎ”：  ｓｔｒｉｎｇ，
”ｆｏｌｌｏｗｅｒｓ＿ｃｏｕｎｔ”：  ｎｕｍｂｅｒ  ｝，  
”ｒｅｔｗｅｅｔ＿ｃｏｕｎｔ”：  ｎｕｍｂｅｒ  ｝
【００７４】
ヌルフィールドおよび空のオブジェクト
空のオブジェクトまたはヌルフィールドは、ＪＳＯＮレコード内に存在し得る。例えば
、人間の座標（緯度および経度）についてのレコードは、
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛｝  ｝
であり得る。
スキーマは、同一型、
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛｝  ｝
を有する。
厳密に言えば、｛｝はインスタンスと呼ばれ、型はオブジェクトである。この開示におけ
る例および説明は、説明のし易さのために厳密なＪＳＯＮと異なる。
【００７５】
同様に、以下のオブジェクト
｛  ”ｇｅｏ”：  ｎｕｌｌ  ｝
は、同一型、
｛  ”ｇｅｏ”：  ｎｕｌｌ  ｝
を有する。
【００７６】
後続のレコードがオブジェクトについての値を有する場合、空のオブジェクトは、併合
を適用することによって埋められる。例えば、レコード、
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛｝  ｝  
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛”ｔｙｐｅ”：  ”Ｐｏｉｎｔ”｝  ｝
は、スキーマ
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛”ｔｙｐｅ”：  ｓｔｒｉｎｇ｝  ｝
を作り出すことになる。
【００７７】
ヌル型は、観察された型に同様に置換される。例えば、レコード
｛  ”ｇｅｏ”：  ｎｕｌｌ  ｝  
｛  ”ｇｅｏ  ”：  ｔｒｕｅ  ｝
は、スキーマ、
｛  ”ｇｅｏ  ”：  ｂｏｏｌｅａｎ  ｝
を作り出すことになる。
【００７８】
配列
ツイートは、ハッシュタグ（強調されたトピックの語）、ＵＲＬ、および他のＴｗｉｔ
ｔｅｒユーザの言及などのアイテムを含有することが多い。ＴｗｉｔｔｅｒのＦｉｒｅｈ
ｏｓｅは、例えば、ツイートのＪＳＯＮオブジェクトに含めるためにこれらのアイテムを
自動的に構文解析し抽出し得る。以下の例では、ハッシュタグメタデータは、配列のため
のスキーマがどのように推論されるかを例示するために使用される。
【００７９】
最初に、以下のツイート（または文字列）におけるハッシュタグについての開始オフセ
ットのリストの抽出およびレコードを考える。
”＃ｄｏｎｕｔｓ  ＃ｍｕｆｆｉｎｓ  ＃ｂｉｓｃｕｉｔｓ”
それらのオフセットは、以下のような配列で表現され得る。
｛  ”ｏｆｆｓｅｔｓ”：  ［０，  ８，  １７］  ｝
【００８０】
ソースデータにおける配列は、特定の順序無しで、ソース配列において見付けられる要
素の型を含有する配列としてスキーマにおいて表現される。それ故、上記オブジェクトに
ついてのスキーマは、
｛  ”ｏｆｆｓｅｔｓ”：  ［ｎｕｍｂｅｒ］  ｝
である。
【００８１】
後の処理のためにオフセットと共にハッシュタグを含むことを望む可能性がある。その
場合において、ツイートオブジェクトは、以下のように、配列においてハッシュタグおよ
びオフセットの両方を列挙し得る。
｛  ”ｔａｇｓ”：  ［０，  ”ｄｏｎｕｔｓ”，  ８，  ”ｍｕｆｆｉｎｓ”，  １７
，  ”ｂｉｓｃｕｉｔｓ”］  ｝
対応するスキーマは、配列における両方の型、
｛  ”ｔａｇｓ”：  ［  ｎｕｍｂｅｒ，  ｓｔｒｉｎｇ  ］  ｝
を含むことになる。
【００８２】
あるいは、タグおよびオフセットは、以下のように逆にされ得、
｛  ”ｔａｇｓ”：  ［”ｄｏｎｕｔｓ”，  ０，  ”ｍｕｆｆｉｎｓ”，  ８，  ”ｂ
ｉｓｃｕｉｔｓ”，  １７］  ｝
また、“ｔａｇ”配列は、文字列または数字を含有することができるので、結果として生
じるスキーマは、
｛  ”ｔａｇｓ”：  ［  ｓｔｒｉｎｇ，  ｎｕｍｂｅｒ  ］  ｝  
である。
【００８３】
実際、タグテキストおよびタグオフセットは、隣接オブジェクト内に含まれ得る。
｛  ”ｔａｇｓ”：  ［”ｄｏｎｕｔｓ”，  ”ｍｕｆｆｉｎｓ”，  ”ｂｉｓｃｕｉｔ
ｓ”］  ｝，  
｛  ”ｔａｇｓ”：  ［０，  ８，  １７］  ｝
ここで、“ｔａｇｓ（タグ）”について２つのスキーマがある。
｛  ”ｔａｇｓ”：  ［ｓｔｒｉｎｇ］  ｝  ａｎｄ  ｛  ”ｔａｇｓ”：  ［ｎｕｍｂ
ｅｒ］  ｝
この場合において、配列は同じ深さにあり、上記のように同じスキーマを生むために併合
され得る。
｛  ”ｔａｇｓ”：  ［  ｓｔｒｉｎｇ，  ｎｕｍｂｅｒ  ］  ｝
【００８４】
また、以下のスキーマは同一であることに留意する。
｛  ”ｔａｇｓ”：  ［ｓｔｒｉｎｇ，  ｎｕｍｂｅｒ］  ｝  
｛  ”ｔａｇｓ”：  ［ｎｕｍｂｅｒ，  ｓｔｒｉｎｇ］  ｝
これは、型のリストがセットとして処理されることが原因である。配列要素についての型
は、可能であれば併合され、併合は、配列の内側でオブジェクトと配列について更に実行
される。種々の他の実装では、（配列およびオブジェクトの両方における）型の順序およ
び型間の従属性が保持され得る。しかしながら、これは、スキーマをそれほど簡潔にさせ
得ない。
【００８５】
ネストされたオブジェクト
ネストされたオブジェクトを例示するために、オフセットの始まりと終わりの両方が以
下のようにレコードされることを想定する。
｛  ”ｔａｇｓ”：  ［｛  ”ｔｅｘｔ”：  ”ｄｏｎｕｔｓ”，  ”ｂｅｇｉｎ”：  
０  ｝，  ｛  ”ｔｅｘｔ”：  ”ｄｏｎｕｔｓ”，  ”ｅｎｄ”：  ６  ｝］｝
結果として生じるスキーマは、
｛  ”ｔａｇｓ”：  ［｛”ｔｅｘｔ”：  ｓｔｒｉｎｇ，  ”ｂｅｇｉｎ”：  ｎｕｍ
ｂｅｒ，  
”ｅｎｄ”：  ｎｕｍｂｅｒ  ｝］  ｝
である。
示されるように、オブジェクト型は、別個に配列要素を型付ける代わりに併合される。
【００８６】
同様に、タグ文字列およびオフセットがネストされた配列内にある場合、
｛  ”ｔａｇｓ”：  ［  ［  ”ｄｏｎｕｔｓ”，  ”ｍｕｆｆｉｎｓ”  ］，  ［０，
８］  ］  ｝  ＝＝＞  
｛  ”ｔａｇｓ”：  ［［ｓｔｒｉｎｇ］，  ［ｎｕｍｂｅｒ］］｝，  
において、スキーマは、
｛  ”ｔａｇｓ”：  ［［ｓｔｒｉｎｇ，  ｎｕｍｂｅｒ］］  ｝
に更に減る。これは、スキーマの精密さとスキーマの簡潔さとの間で本開示の種々の実装
においてなされるトレードオフである。
【００８７】
空のオブジェクトおよび空の配列は、以下のように処理される。空のオブジェクトは上
記のように埋められるので、以下のスキーマ削減例が可能である。
｛  ”ｐａｒｓｅｄ”：  ｛  ”ｔａｇ”：  ｛｝，  ”ｔａｇ”：  ｛  ”ｏｆｆｓｅ
ｔ”：  ｎｕｍｂｅｒ  ｝  ｝  ｝  
＝＞  ｛  ”ｐａｒｓｅｄ”：  ｛  ”ｔａｇ”：  ｛  ”ｏｆｆｓｅｔ”：  ｎｕｍｂ
ｅｒ  ｝｝
同様に、配列に併合規則を使用すると、以下のスキーマ削減がなされる。
｛  ”ｔａｇｓ”：  ［［］，  ［  ｎｕｍｂｅｒ  ］］  ｝  ＝＞  ｛  ”ｔａｇｓ”
：  ［［  ｎｕｍｂｅｒ  ］］  ｝  
｛  ”ｔａｇｓ”：  ［［］，  ［［］］］  ｝  ＝＞  ｛  ”ｔａｇｓ”：  ［［［］
］］  ｝  
｛  ”ｔａｇｓ”：  ［［］，  ［［］］，  ［ｎｕｍｂｅｒ］］  ｝  ＝＞  ｛  ”ｔ
ａｇｓ”：  ［［［］］，  ［ｎｕｍｂｅｒ］］｝  ＝＞  ｛  ”ｔａｇｓ”：  ［［［
］，  ｎｕｍｂｅｒ］］］  ｝
【００８８】
併合手順
前のスキーマからの新たなスキーマおよび新たなオブジェクトを生成するために、分析
プラットフォームは、まず、新たなオブジェクトを型付けする（すなわち、新たなオブジ
ェクトについてスキーマを計算する）。この手順は、任意の特定の実装を記述すること無
く、型付けについて標準的な意味論を指定することが意図される。以下の記述では、変数
ｖ、ｗ、ｖ＿ｉ、ｗ＿ｊは、任意の有効なＪＳＯＮ値の範囲にわたる一方、ｊ、ｋ、ｊ＿
ｍ、ｋ＿ｎは、有効な文字列の範囲にわたる。型付けについての基礎的な規則は、
ｔｙｐｅ  （ｓｃａｌａｒ  ｖ）  ＝  ｓｃａｌａｒ＿ｔｙｐｅ  ｏｆ  ｖ  
ｔｙｐｅ  （  ｛  ｋ＿１  ：  ｖ＿１，  ．．．  ｋ＿ｎ：  ｖ＿ｎ  ｝）  ＝  
ｃｏｌｌａｐｓｅ  （  ｛  ｋ＿１  ：  ｔｙｐｅ（ｖ＿１），  ．．．，  ｋ＿ｎ
：  ｔｙｐｅ（ｖ＿ｎ）  ｝）  
ｔｙｐｅ  （  ［  ｖ＿１，  ．．．，  ｖ＿ｎ  ］  ）  ＝  
ｃｏｌｌａｐｓｅ  （  ［  ｔｙｐｅ（ｖ＿１），  ．．．，  ｔｙｐｅ（ｖ＿ｎ）
］  ）
である。
【００８９】
第１の規則は、３または“ａ”などのスカラについて、対応する型は、値自体（３とい
う数字または“ａ”という文字列）から直接的に推論されることを単純に述べる。第２お
よび第３の規則は、折り畳み関数を使用してオブジェクトおよび配列を再帰的に型付けす
る。
【００９０】
折り畳み関数は、オブジェクトにおける同じフィールドの型を繰り返して併合し、配列
の内側でオブジェクト、配列、および共通型を併合する。それは、スカラ型に到達するま
で再帰的に続く。オブジェクトの場合、折り畳み関数は、
ｃｏｌｌａｐｓｅ  （  ｛  ｋ＿１  ：  ｖ＿１，  ．．．，  ｋ＿ｎ：  ｖ＿ｎ  ｝）
：  
ｗｈｉｌｅ  ｋ＿ｉ  ＝＝  ｋ＿ｊ  ：  
ｉｆ  ｖ＿ｉ，  ｖ＿ｊ  ａｒｅ  ｓｃａｌａｒ  ｔｙｐｅｓ  ａｎｄ  ｖ＿ｉ
＝＝  ｖ＿ｊ  ＯＲ  
ｖ＿ｉ，  ｖ＿ｊ  ａｒｅ  ｏｂｊｅｃｔｓ  ＯＲ  ｖ＿ｉ，  ｖ＿ｊ  ａ
ｒｅ  ａｒｒａｙｓ：
ｒｅｐｌａｃｅ  ｛  ．．．，  ｋ＿ｉ  ：  ｖ＿ｉ，  ．．．，  ｋ＿ｊ
：  ｖ＿ｊ，  ．．．  ｝
ｗｉｔｈ      ｛  ．．．，  ｋ＿ｉ  ：  ｍｅｒｇｅ  （ｖ＿ｉ，  ｖ＿
ｊ  ），  ．．．  ｝
である。
【００９１】
配列の場合、折り畳み関数は、
ｃｏｌｌａｐｓｅ  （  ［  ｖ＿１，  ．．．，  ｖ＿ｎ  ］  ）  ：  
ｗｈｉｌｅ  ｖ＿ｉ，  ｖ＿ｊ  ａｒｅ  ｓｃａｌａｒ  ｔｙｐｅｓ  ａｎｄ  ｖ＿
ｉ  ＝＝  ｖ＿ｊ  ＯＲ  
ｖ＿ｉ，  ｖ＿ｊ  ａｒｅ  ｏｂｊｅｃｔｓ  ＯＲ  ｖ＿ｉ，  ｖ＿ｊ  ａｒｅ
ａｒｒａｙｓ：  
ｒｅｐｌａｃｅ  ［．．．，  ｖ＿ｉ，  ｖ＿ｊ，  ．．．］  
ｗｉｔｈ      ［．．．，  ｍｅｒｇｅ  （ｖ＿ｉ，  ｖ＿ｊ  ），  ．．
．］
である。
【００９２】
併合関数は、重複を除去し、配列／マップを組み合わせるためにどのように値をペアで
組み合わせるかを記述する。オブジェクトの場合、併合は、共通フィールドを折り畳むた
めに、単純に折り畳みを再帰的に呼び出す。
ｍｅｒｇｅ  （ｖ，  ｖ）  ＝  ｖ  
ｍｅｒｇｅ  （｛｝，  ｛  ｋ＿１  ：  ｖ＿１，  ．．．，  ｋ＿ｎ  ：  ｖ＿ｎ  ｝
）  ＝  ｛  ｋ＿１  ：  ｖ＿１，  ．．．，  ｋ＿ｎ：  ｖ＿ｎ
｝  
ｍｅｒｇｅ  （  ｛  ｊ＿１  ：  ｖ＿１，  ．．．，  ｊ＿ｎ：  ｖ＿ｎ  ｝，  ｛  
ｋ＿１  ：  ｗ＿１，  ．．．，  ｋ＿ｍ：  ｗ＿ｍ  ｝  ）
＝  ｃｏｌｌａｐｓｅ  （  ｛  ｊ＿１  ：  ｖ＿１，  ．．．，  ｊ＿ｎ：  ｖ＿
ｎ，  ｋ＿１  ：  ｗ＿１，  ．．．，  ｋ＿ｍ：  ｗ＿ｍ
｝  ）
【００９３】
同様に、配列の場合、
ｍｅｒｇｅ  （［］，  ［ｖ＿１，  ．．．，  ｖ＿ｎ］  ）  ＝  ［ｖ＿１，  ．．．
，  ｖ＿ｎ］  
ｍｅｒｇｅ（［ｖ＿１，  ．．．，  ｖ＿ｎ］，  ［ｗ＿１，  ．．．，  ｗ＿ｍ］  ）
＝  ｃｏｌｌａｐｓｅ  （  ［ｖ＿１，  ．．．，  ｖ＿ｎ，  ｗ＿１，  ．．．，
ｗ＿ｍ］  ）
である。
【００９４】
ヌルは、ここに示されるように、保持される。
ｍｅｒｇｅ  （  ｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛｝  ｝，  ｛  ”ｃｏｏｒｄｉ
ｎａｔｅｓ”：  ｎｕｌｌ  ｝，  
｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ［］  ｝  ）  
＝  ｛  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｛｝，  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ［］
，  ”ｃｏｏｒｄｉｎａｔｅｓ”：  ｎｕｌｌ  ｝
数字９が値であるのと全く同じように、ＪＳＯＮヌルは値である。関係において、ＮＵＬ
Ｌ（ヌル）は、指定された値が無かったことを示す。ＳＱＬでは、ヌルは、ｔａｇｓ＜ｎ
ｕｌｌ＞：ｂｏｏｌｅａｎとして提示され、ここで、ブール値は、ヌルが存在する場合に
は真であり、そうではない場合にはＮＵＬＬである。ＳＱＬユーザのためにスキーマを簡
略化するために、ｃｏｏｒｄｉｎａｔｅｓ＜ｎｕｌｌ＞カラムは、ユーザがＪＳＯＮヌル
をＳＱＬヌルから区別することを必要としない場合には省略され得る。
【００９５】
累積例
上記の簡単な規則を用いて、深くネストされたＪＳＯＮレコードを型付けることが可能
である。例えば、ウェブページについてのページビュー統計を表現する複雑な仮定的レコ
ードを考える。
｛  ”ｓｔａｔ”：  ［  １０，  ”ｔｏｔａｌ＿ｐａｇｅｖｉｅｗｓ”，  ｛  ”ｃｏ
ｕｎｔｓ”：  ［１，  ［３］］，  
”ｐａｇｅ＿ａｔｔｒ”：  ７．０  ｝，  ｛  ”ｐａｇｅ＿ａｔｔｒ”：  ［”ｉ
ｎｔｅｒｎａｌ”］｝  ］｝
以下のスキーマが作り出されることになる。
｛  ”ｓｔａｔ”：  ［ｎｕｍｂｅｒ，  
ｓｔｒｉｎｇ，  
｛  ”ｃｏｕｎｔｓ”：  ［ｎｕｍｂｅｒ，  ［ｎｕｍｂｅｒ］］，  
”ｐａｇｅ＿ａｔｔｒ”  ：  ｎｕｍｂｅｒ，  
”ｐａｇｅ＿ａｔｔｒ”  ：  ［ｓｔｒｉｎｇ］  
｝］  ｝
【００９６】
種々の実装において、ＪＳＯＮスキーマ形式が、推論されたスキーマを符号化するため
に使用され得る。この形式は、標準化され、追加メタデータ（例えば、オブジェクトがマ
ップであるかどうか）を組み込むために容易に拡張され得る。しかしながら、それはかな
り冗長であり、スペース的に非効率であり、従って、それは、この開示における例のため
に使用されない。例えば、ＪＳＯＮスキーマ形式では、上記スキーマは以下のように表現
される。
【数１】
0006617117.tif 000002
【数２】
0006617117.tif 000003
【００９７】
マップ装飾
開発者および分析家は、多くの異なる目的のためにＪＳＯＮオブジェクトおよび配列を
使用することができる。特に、ＪＳＯＮオブジェクトは、オブジェクトとしても「マップ
」としても使用されることが多い。例えば、開発者は、フィールドが日付であり、値がペ
ージビューのような収集された統計である、オブジェクトを生成する可能性がある。別の
例は、フィールドがユーザｉｄであり、値がプロフィールである場合である。これらの場
合では、オブジェクトは、静的オブジェクトではなくて、むしろマップデータ構造に近い
。とても多くの可能なフィールド名があり、フィールド名は動的に生成されるので、ユー
ザは、可能なフィールド名を必ずしも知っているとは限らない。結果として、ユーザは、
彼らが値をクエリするのと同じように、フィールドをクエリすることを望み得る。
【００９８】
この使用をサポートするために、分析プラットフォームは、マップを識別することがで
きる。分析プラットフォームは、マップを識別するために発見的問題解決法を組み込み、
また、ユーザが、ネストされたオブジェクトのどれがマップとして処理されるべきである
かおよび処理されるべきではないかを指定することを可能にする。オブジェクトをマップ
としてタグ付けすることは、装飾と呼ばれる。
【００９９】
一般に、装飾は、初期ロード後に実行され、すなわち、初期採集上でマップを識別する
必要はない。装飾は、第２のパス上で後で、あるいは、更なるデータが採集された後に実
行され得る。加えて、マップは、必要に応じて、単純にオブジェクトに返還され得る。
【０１００】
デフォルト設定で、ＪＳＯＮオブジェクトは、オブジェクト（または、Ｃ言語の構造）
として処理される。これは、オブジェクトに“ｏｂｊ＿ｔｙｐｅ”：ｏｂｊｅｃｔで注釈
を付けることによって、ＪＳＯＮスキーマにおいて明示的に示され得る。以下の例におい
て使用される省略表記はＯ｛｝である。
【０１０１】
マップにフラグを立てるために、発見的問題解決法は、グループとしてそれらの含有オ
ブジェクト（コンテナ）と比べて比較的まれに発生するフィールドを探す。マップのため
に、省略表現Ｍ｛｝が使用される。
【０１０２】
第１のパス上でスキーマを計算する間、フィールドが発生する頻度が追跡される。デー
タセット内に頻度Ｆで発生するオブジェクト（またはネストされたオブジェクト）を考え
る。ｖ＿ｉをオブジェクトにおけるフィールドｉの頻度とし、Ｎを（それの型とは無関係
に）オブジェクトの固有フィールドの数とする。割合（合計（ｖ＿ｉ）／Ｎ）／Ｆは、コ
ンテナの頻度に対する平均フィールド頻度の割合である。この割合が、ユーザが構成可能
であり得る０．０１などの閾値より下である場合には、含有オブジェクトは、マップとし
て指定される。種々の実装において、ＪＳＯＮスキーマにおける空のオブジェクトは、マ
ップとして処理される。
【０１０３】
関係スキーマの生成
ソースデータセットにおけるＪＳＯＮオブジェクトのスキーマが推論された後、分析プ
ラットフォームは、ＳＱＬユーザおよびＳＱＬをベースとしたツールに露出され得る関係
スキーマを作り出す。目標は、ＪＳＯＮスキーマにおける含有関係を表現する簡潔なスキ
ーマを生成する一方で、ユーザに標準ＳＱＬの能力を与えることである。この関係スキー
マは、装飾されたＪＳＯＮスキーマから作り出され、基礎的半構造データセット上のビュ
ーである。変換を実行するための一般化手順を記述する前に、どのようにＪＳＯＮスキー
マが関係ビューに変換されるかについてのいくつかの例が、ここに提示される。
【０１０４】
オブジェクト
最も単純な例は、以下のスキーマのような、簡単なスカラ型を有するオブジェクトであ
る。
【数３】
0006617117.tif 000004
この場合において、オブジェクトのフィールドは、関係のカラムに直接的に変換する。
【数４】
0006617117.tif 000005
【０１０５】
トップレベルのオブジェクトの関係（または表）はここでは“Ｒｏｏｔ（ルート）”と
呼ばれ、とはいえ、それは、例えば、ソースコレクションの名前に、そのような名前が存
在する場合には、置換され得る。スペースおよび可読性の利益のために、型名文字列、数
字、およびブールは、ｓｔｒ、ｎｕｍ、およびｂｏｏｌに短縮されている。
【０１０６】
型は、型多様性をサポートするために属性名に追加され得る。例えば、以下のスキーマ
を考える。
【数５】
0006617117.tif 000006
その場合、結果として生じる関係スキーマは、別個の“ｉｄ”および“ｉｄ”カラムを有
することになる。
【数６】
0006617117.tif 000007
【０１０７】
ネストされたオブジェクト
ネストされたオブジェクトは、外部キー関係との新たな関係を作り出す。例えば、ＪＳ
ＯＮスキーマ、
【数７】
0006617117.tif 000008
を考える。対応する関係スキーマは、
【数８】
0006617117.tif 000009
である。
【０１０８】
ネストされたオブジェクトは、それのパス、この場合では“Ｒｏｏｔ．ｕｓｅｒ”によ
って名付けられた別個の関係に「正規化」される。サブオブジェクトを表現する新たな表
におけるカラム“Ｒｏｏｔ．ｕｓｅｒ”．“ｉｄ＿ｊｋ”は、カラム“Ｒｏｏｔ．ｕｓｅ
ｒ”（表“Ｒｏｏｔ”における“ｕｓｅｒ”カラム）のための外部キーである。型は、そ
れを他のカラムから区別するために「結合キー」として指定されるが、実際の実装では、
ｊｏｉｎ＿ｋｅｙ型は典型的には整数である。
【０１０９】
オブジェクトは、いくつかのレベルの深さにネストされ得る。例えば、リツイートオブ
ジェクトは、リツイートしたユーザのプロフィールを含む、リツイートされた状態オブジ
ェクトを含み得、結果として、以下のスキーマになる。
【数９】
0006617117.tif 000010
対応する関係ビューは、
【数１０】
0006617117.tif 000011
である。“Ｒｏｏｔ．ｕｓｅｒ”、“Ｒｏｏｔ．ｒｅｔｗｅｅｔｅｄ＿ｓｔａｔｕｓ”、
および“Ｒｏｏｔ．ｒｅｔｗｅｅｔｅｄ＿ｓｔａｔｕｓ．ｕｓｅｒ”は、全て異なる表に
分離されることに留意する。
【０１１０】
１対１関係の最適化
ネストされたオブジェクトの関係では、メインの表における行からネストされたオブジ
ェクトについての表における行に１対１関係があることが多い。結果として、これらは、
カラム名についてドット付き表記を使用する単一の表に１対１に折り畳まれ得る。
【０１１１】
例えば、上記マルチ関係例は、
【数１１】
0006617117.tif 000012
に平坦化され、３レベルのネストされたオブジェクト例の場合には、
【数１２】
0006617117.tif 000013
に平坦化される。
【０１１２】
関係スキーマは単純にＪＳＯＮスキーマ上のビューであるので、平坦化された、部分的
に平坦化された、または別個の（平坦化されない）関係スキーマは、基礎的データを修正
すること無く、分析プラットフォームによって所望される際にユーザに提示され得ること
に留意する。唯一の限定は、ユーザが、矛盾する表定義を提示されないことである。
マップ
【０１１３】
フィールドの組をマップとして指定すること無く、対応する関係スキーマは、膨大な数
のカラムを含み得る。加えて、ユーザは、フィールド名をクエリすることを望み得、例え
ば、彼らは、１２月における平均ページビューを見付けることを望み得る。
【０１１４】
これらの問題を解決するために、マップとして装飾される（ネストされた）オブジェク
トについての表は、「ピボットされ」得る。例えば、ウェブサイト上の各ページについて
の種々のメトリック（ｍｅｔｒｉｃ）（毎日のページビュー、クリック、費やされた時間
等）の追跡を保持するために、以下のスキーマを考える。
【数１３】
0006617117.tif 000014
【０１１５】
毎日について、別個のカラムで表を作り出すのではなく、フィールドおよび値は、関係
におけるキーと値のペアとして記憶され得る。
【数１４】
0006617117.tif 000015
【０１１６】
この場合において、ｉｄカラムは、そのレコード内で各マップエントリが元々存在した
ことを示す外部キーである。１年に値するページビューの場合、表“Ｒｏｏｔ．ｍｅｔｒ
ｉｃ”において３６５個のカラムを有する代わりに、２個だけがある。“ｋｅｙ”カラム
はフィールド名を記憶し、“ｖａｌ”カラムは値を記憶する。例えば、上記スキーマの場
合、データベースは、
”ｗｗｗ．ｎｏｕｄａｔａ．ｃｏｍ／ｊｏｂｓ”（ｐａｇｅ＿ｉｄ２８４）について、こ
れらのレコードを含有し得る。
【数１５】
0006617117.tif 000016
【０１１７】
ピボットは、マップに型多様性があるときに依然として機能する。例えば、メトリック
が、カテゴリとカテゴリの強さを示すスコアの両方を含有する感情を表現することを想定
する。
【数１６】
0006617117.tif 000017
ＪＳＯＮスキーマは、
【数１７】
0006617117.tif 000018
であることになる。
【０１１８】
関係スキーマを生成すると、新たな“ｖａｌ”カラムが、新たな型を含むようにマップ
関係に追加され得る。他の“ｖａｌ”カラムが、示されるように、カラム名を区別するた
めにそれらの型と共に同様に添えられ得る。
【数１８】
0006617117.tif 000019
【０１１９】
上記ＪＳＯＮオブジェクトから結果として生じるエントリは、
【数１９】
0006617117.tif 000020
【数２０】
0006617117.tif 000021
として現れることになる。これらのマップが一旦ピボットされると、ユーザは、それらが
任意の他のカラムであることになるように、述語および関数をキーカラムに適用すること
ができる。
【０１２０】
ネストされたマップ
基本原理は、ネストされたマップについても同じである。日毎および時間毎の統計のリ
ストを考える。
【数２１】
0006617117.tif 000022
結果として生じるスキーマは、
【数２２】
0006617117.tif 000023
であることになる。
【０１２１】
オブジェクトはまた、マップの内側でネストされ得る。
【数２３】
0006617117.tif 000024
結果として生じる平坦化された関係スキーマは、
【数２４】
0006617117.tif 000025
である。
【０１２２】
空の要素
空のオブジェクトは、時々、データ内に現れる。スキーマ、
【数２５】
0006617117.tif 000026
を考える。
ＪＳＯＮオブジェクトは、ここに示されるように、ユーザ情報無しで受信され得る。
【数２６】
0006617117.tif 000027
【０１２３】
空のユーザオブジェクトは、以下の関係タプルで表現され得る。
【数２７】
0006617117.tif 000028
【０１２４】
全ての採集したユーザオブジェクトが採集したストリームにおいて空のオブジェクトを
有した場合、結果として生じるＪＳＯＮスキーマは、空のオブジェクトを含むことになる
。例えば、このスキーマにおける最後のフィールド（“ｕｓｅｒ”）を見る。
【数２８】
0006617117.tif 000029
この場合において、空のオブジェクト“ｕｓｅｒ”は、マップとして処理され得、結果と
して以下の関係スキーマになる。
【数２９】
0006617117.tif 000030
【０１２５】
Ｒｏｏｔ．ｕｓｅｒ＜ｍａｐ＞は、任意の値カラムを有さず、最初に空であることに留
意する。しかしながら、この設計は、Ｒｏｏｔにおける各レコードが、結合キーを既に割
り当てられていることになるので、新たなオブジェクトが採集される際にスキーマが変わ
る場合、カラムを後で追加することを簡単にさせる。
【０１２６】
配列
配列は、マップに類似して処理されるので、スキーマ変換はかなり類似する。主な違い
は、マップの文字列“ｋｅｙ”フィールドが、配列インデックスに対応する整数型（ｉｎ
ｔ）の“ｉｎｄｅｘ”フィールドに置換されることである。簡単な例は、
【数３０】
0006617117.tif 000031
であり、それは、関係スキーマ
【数３１】
0006617117.tif 000032
【数３２】
0006617117.tif 000033
を導く。
【０１２７】
型多様性およびネストされた配列は、マップと同じように機能する。以下のスキーマ、
【数３３】
0006617117.tif 000034
を考え、これは、関係スキーマ、
【数３４】
0006617117.tif 000035
を導く。
【０１２８】
オブジェクトは、ここでは、
【数３５】
0006617117.tif 000036
のように配列内にネストされ得る。結果として生じる関係スキーマは、
【数３６】
0006617117.tif 000037
として生成され得る。
【０１２９】
１対１平坦化の最適化を使用すると、関係スキーマは、
【数３７】
0006617117.tif 000038
になる。
【０１３０】
ネストされた空の配列
関係スキーマは、マップに類似する手法でネストされた空の配列について生成され得る
。以下のスキーマ、
【数３８】
0006617117.tif 000039
の場合、関係スキーマは、
【数３９】
0006617117.tif 000040
であることになる。
【０１３１】
ネストされた配列の場合、表の名前に“ｖａｌ”が添えられた別個の表が生成されるこ
とに留意する。空の配列の場合、別個の表は、“ｉｎｄｅｘ”カラムだけで、しかしなが
ら“ｖａｌ”カラム無しで、生成され、その“ｖａｌ”カラムは、配列の内容が一旦観察
され型付けされると、後で追加され得る。
【０１３２】
アトミック値上の型推論
上記型推論および関係スキーマへの変換手順は、ＪＳＯＮにおいて利用可能である基本
型に頼る。いかなる型システムが選択されても、同じ手順が、その型システムに等しく適
用される。換言すれば、分析プラットフォームは、アトミックスカラ型が値から推論され
得る限り、整数、浮動小数、および時間のようなより狭いスカラ型を推論することができ
る。ＢＳＯＮおよびＸＭＬは、そのような拡張された型システムを有する。その上、種々
の発見的問題解決法（正規表現など）が、日付や時間などのより複雑な型を検出するため
に使用され得る。
【０１３３】
ＡＮＳＩ  ＳＱＬは、ＪＳＯＮと同じ型をサポートしないので、推論された型は、これ
まで関係ビューについて見られた最も具体的な型に変換される。例えば、整数だけがフィ
ールド“ｆｒｅｑ”について見られる場合には、数字型は、“ｆｒｅｑ”についての関係
スキーマにおける整数に変換されることになる。同様に、整数と浮動小数の両方が観察さ
れている場合には、関係スキーマは、“ｆｒｅｑ”カラムを浮動小数として示すことにな
る。同様に、文字列フィールドは、関係スキーマにおいて文字可変型に変換する。換言す
れば、基本ＪＳＯＮ型より具体的な型が、追跡され得る。
【０１３４】
代替案は、データ値の型を推論するために、型多様性に頼り、より具体的な型システム
を使用することである。すなわち、ＪＳＯＮプリミティブ型を使用する代わりに、ＡＮＳ
Ｉ  ＳＱＬのプリミティブ型を使用する。
【０１３５】
以下は、採集の間に追跡される型のリスト（左側）と、どのようにそれらがＳＱＬスキ
ーマについて変換されるか（右側）である。ほとんどのＳＱＬデータベースは、クライア
ントによって所望される場合に使用され得るテキストを含む追加型をサポートする。留意
：オブジェクトＩｄ（ＯｂｊｅｃｔＩｄ）型はＢＳＯＮに特有である。
【数４０】
0006617117.tif 000041
【数４１】
0006617117.tif 000042
【０１３６】
手順
ＪＳＯＮスキーマから関係スキーマに変換することは、ネストされたＪＳＯＮスキーマ
構造の再帰的解凍を使用して達成され得る。実装例の疑似コード表現が、ここに示される
。
【数４２】
0006617117.tif 000043
【数４３】
0006617117.tif 000044
【０１３７】
上記手順は、１対１最適化無しに、関係スキーマを作り出すことになる。第２のパスは
、関係スキーマを通して実行され得、１対１関係でオブジェクト表を識別し、それらを折
り畳む。あるいは、１対１最適化は直列式に実行され得るが、これは、明瞭さのために示
されていない。ネストされたオブジェクトを有するスキーマのサブツリーが配列またはマ
ップによって「割り込まれ」ないときには、オブジェクトサブツリー全体は、サブツリー
のルートにそれらのパスによって名付けられた属性を有する単一の表に折り畳まれ得る。
マップまたはオブジェクトである属性は別個の表内にとどまるが、内に含有される任意の
サブオブジェクトは、再帰的に折り畳まれ得る。これらの原理は、ネストされたオブジェ
クトの任意の深さに適用する。
【０１３８】
データをインデックスにポピュレートすること
ＪＳＯＮおよび関係スキーマが新たなオブジェクトに応答して一旦更新されると、オブ
ジェクト内に含有されるデータは、以下に記載されるように、インデックス内に記憶され
得る。
【０１３９】
分析プラットフォームにおけるインデックスは、キーと値のペアを記憶する順序を保つ
インデックスに頼る。インデックスは、操作、すなわち、ルックアップ（プレフィックス
）、挿入（キー，値）、削除（キー）、更新（キー，値）、および範囲検索のためのｇｅ
ｔ＿ｎｅｘｔ（）をサポートする。そのようなインターフェースをサポートする多数のデ
ータ構造および低レベルライブラリがある。例は、ＢｅｒｋｅｌｅｙＤＢ、ＴｏｋｙｏＣ
ａｂｉｎｅｔ、ＫｙｏｔｏＣａｂｉｎｅｔ、ＬｅｖｅｌＤＢなどを含む。これらは、Ｂツ
リー、ＬＳＭ（ｌｏｇ‐ｓｔｒｕｃｔｕｒｅｄ  ｍｅｒｇｅ）ツリー、およびＦｒａｃｔ
ａｌツリーのような順序を保つ二次記憶データ構造を内部で使用する。オブジェクトＩＤ
などについて、順序を保たないインデックス（ハッシュ表など）が使用される特殊な場合
があり得る。順序を保たないインデックスを用いると、ｇｅｔ＿ｎｅｘｔ（）および範囲
検索を行う能力が犠牲にされ得る。
【０１４０】
種々の実装において、分析フレームワークは、ＬｅｖｅｌＤＢを使用し、そのＬｅｖｅ
ｌＤＢは、ＬＳＭツリーを実装し、圧縮を行い、高挿入速度でデータセットに良好な性能
を提供する。ＬｅｖｅｌＤＢはまた、分析フレームワークについての共通使用モデルと矛
盾し得ない性能のトレードオフを行う。例えば、ログデータなどのデータを分析するとき
、データは頻繁に追加されることになるが、既存のデータは、希に変えられるか、あるい
は、決して、変えられないことになる。有利には、ＬｅｖｅｌＤＢは、データ削除および
データ修正の遅さを代償にして、高速データ挿入のために最適化される。
【０１４１】
順序を保つインデックスは、それらがキー順序でキーと値のペアを併置する特性を有す
る。それ故、一定のキーの近くのキーと値のペアについて検索するとき、あるいは順序よ
くアイテムを取り出すとき、応答は、順序がばらばらでアイテムを取り出すときよりもか
なり速く戻ることになる。
【０１４２】
分析プラットフォームは、各ソースコレクションのための多数のキーと値のインデック
スを、また、いくつかの実装では、各ソースコレクションのための２つのインデックスと
６つのインデックスとの間を維持することができる。分析プラットフォームは、関係スキ
ーマ（ＳＱＬスキーマは具体化される必要はない）上でＳＱＬクエリを評価するためにこ
れらのインデックスを使用する。各オブジェクトは、ｔｉｄによって示された固有ｉｄを
割り当てられる。２つのインデックスであって、その２つのインデックスから他のインデ
ックスおよびスキーマが再構築され得る、２つのインデックスは、ビッグインデックス（
ＢＩ：ＢｉｇＩｎｄｅｘ）および配列インデックス（ＡＩ：ＡｒｒａｙＩｎｄｅｘ）であ
る。
【０１４３】
ビッグインデックス（ＢＩ：ＢｉｇＩｎｄｅｘ）
ＢｉｇＩｎｄｅｘ（ＢＩ）は、配列内に埋め込まれないデータ内の全フィールドを記憶
するベースデータストアである。値（ｖａｌ）は、ｃｏｌ＿ｐａｔｈおよびｔｉｄに基づ
いてキーによってＢＩから取り出され得る。
【数４４】
0006617117.tif 000045
【０１４４】
ｃｏｌ＿ｐａｔｈは、フィールドの型が添えられたルートオブジェクトからのフィール
ドへのパスである。例えば、以下のレコードの場合、
【数４５】
0006617117.tif 000046
以下のキーと値のペアが、ＢＩに追加される。
【数４６】
0006617117.tif 000047
【０１４５】
種々の実装において、基礎的インデックスストア（ＬｅｖｅｌＤＢなど）は、キーのセ
グメントの意義に気付いていない。換言すれば、“ｒｏｏｔ．ｔｅｘｔ＜ｓｔｒ＞，１”
がルート表内の文字列テキストフィールドの第１の要素を意味する一方、インデックスス
トアは、区別されないマルチ文字キーを単純に見得る。簡単な例として、キーは、ｃｏｌ
＿ｐａｔｈおよびｔｉｄを（重要なことには、その順序で）連結することによって単純に
生成され得る。例えば、上記に実例で示された第１のキーは、“ｒｏｏｔ．ｔｅｘｔ＜ｓ
ｔｒ＞１”としてインデックスストアに渡され得る。インデックスストアは、パス類似性
の任意の理解が原因ではなく、単純に、第１の１４文字が同じであるので、第２のキー（
“ｒｏｏｔ．ｔｅｘｔ＜ｓｔｒ＞２”）を第１のキーと併置することになる。カラム名お
よび型は、分類順序化が原因で、全てのキーの一部として記憶されるけれども、圧縮（プ
レフィックスをベースとした圧縮など）が、ストレージ費用を削減するために使用され得
る。
【０１４６】
ＢＩでは、全ての新たなカラムについて別個のカラムファイルを生成する伝統的なカラ
ムストアとは異なり、ソースデータの全てのカラムが単一構造に組み合わされる。ＢＩア
プローチは、単一インデックスインスタンスを可能にし、また、マップ検出が遅延される
ことを可能にする。新たなフィールドは、単純にＢＩ内にエントリとして現れるので、マ
ップをピボットしないことは、後でマップに戻される各フィールドについて多数の物理フ
ァイルを生成する物理的費用を生じさせない。
【０１４７】
ＢＩでは、各属性または「カラム」についてのキーと値のペアが併置される。それ故、
カラムファイルのように、ＢＩは、クエリエクゼキュータが、クエリにおいて参照されな
いフィールドを含有するデータを通して掃引することをそれに強制するのではなく、クエ
リにおける興味対象のフィールドに焦点を当てることを可能にする。
【０１４８】
配列インデックス（ＡＩ：ＡｒｒａｙＩｎｄｅｘ）
配列のために正規化表からのフィールドがＢＩに追加されるが、配列インデックスは、
それらの対応する値からのものであることになる。代わりに、配列フィールドは、インデ
ックス情報を保持する別個の配列インデックス（ＡＩ）に追加され得、同じ配列における
エントリが、インデックスストアによって併置されることを可能にし、それは、多くのク
エリのために良好な性能をもたらす。配列値は、以下の署名を使用してＡＩ内に記憶され
得る。
【数４７】
0006617117.tif 000048
【０１４９】
ｃｏｌ＿ｐａｔｈは、配列フィールドのパス、例えば、タグ配列内の要素についての“
ｒｏｏｔ．ｔａｇ”、またはタグ配列の内側のオブジェクト内の“ｔｅｘｔ”フィールド
についての“ｒｏｏｔ．ｔａｇ．ｔｅｘｔ”である。ｊｏｉｎ＿ｋｅｙおよびｉｎｄｅｘ
は、配列の外部キーおよび値のインデックスである。ｔｉｄはまた、各配列についてＢＩ
内に別個のエントリを記憶させることを回避するために記憶される。ｔｉｄは、同じオブ
ジェクト内で対応するカラムについて値をルックアップするために使用され得る。異なる
ツイートにおけるハッシュタグを表現するオブジェクトを考える。
【数４８】
0006617117.tif 000049
これらの場合、タグ表は以下のスキーマを有する。
【数４９】
0006617117.tif 000050
その表の場合、ＡＩ内のエントリは、
【数５０】
0006617117.tif 000051
であることになる。
【０１５０】
配列インデックスは、配列フィールドの値を通して迅速に繰り返すことを可能にする。
これは、例えば、これらのフィールド上で統計（例えば、合計、平均、分散等）を実行す
るとき、特定値を見付けるとき等に有用である。
【０１５１】
ネストされた配列例
ルートオブジェクト内の配列（トップレベルの配列）の場合、ｔｉｄおよびｊｏｉｎ＿
ｋｅｙフィールドは冗長であり（上記を参照）、最適化により除去され得ることに留意す
る。しかしながら、ネストされた配列の場合、別個のｊｏｉｎ＿ｋｅｙが必要とされ、余
分ではない。例えば、このＪＳＯＮオブジェクト
【数５１】
0006617117.tif 000052
を考える。対応する関係スキーマは、
【数５２】
0006617117.tif 000053
である。
ＡＩは、以下のキーと値のペアを使用することを思い起こす。
【数５３】
0006617117.tif 000054
それは、これらのＡＩエントリ、
【数５４】
0006617117.tif 000055
を結果としてもたらす。
【０１５２】
結合キーが、ネストされた配列キーと値のペアから除去された場合には、それは、マフ
ィン（ｍｕｆｆｉｎｓ）が第１のネストされた配列または第２のネストされた配列の一部
であったかどうかを知る可能性がないことになることに留意する。それ故、結合キーは、
トップレベルの配列には冗長であるが、ネストされた配列の場合には冗長ではない。
【０１５３】
配列インデックス２（ＡＩ２）
これらの２つのインデックス（ＢＩおよびＡＩ）は、全ての採集したデータを再構築す
るのに十分であるが、それらが効率的にサポートしないアクセスパターンがある。これら
のために、オプションとして追加スペースを犠牲にして性能を改善するために生成され得
る、以下のインデックスを導入する。
【０１５４】
これは、署名、
【数５５】
0006617117.tif 000056
を有し、それは、配列の特定のインデックス要素が迅速に見付けられることを可能にする
。例えば、インデックス１０（タグ［１０］）における全てのタグを戻すことは、ＡＩ２
を使用して簡単で高速である。
【０１５５】
マップインデックス（ＭＩ：Ｍａｐ  Ｉｎｄｅｘ）
マップインデックスは、それの機能性および署名、すなわち、
【数５６】
0006617117.tif 000057
において配列インデックスに類似する。
【０１５６】
第１の違いは、マップインデックスが初期採集の間に構築されず、代わりに非同期的に
構築されることである。初期ローディングの間、マップは、オブジェクトとして処理され
、通常通り、ＢＩに挿入されることになる。両方が一旦ポピュレートされると、より効率
的なクエリ処理のためにＢＩとＭＩの両方において利用可能であるエントリがある。ＢＩ
エントリは、ユーザまたはアドミニストレータがマップが装飾されないことを要求する場
合に関連したままである。関係スキーマだけが変えられることを必要とし、マップされな
いデータに対応する元のＢＩエントリは、次いで、クエリにおいて使用されることになる
。
【０１５７】
ＡＩのように、ＭＩは、統計関数を適用するために、特定のフィールド名に制限するな
どのために、マップの要素を通して繰り返すときに有用である。ページビュー統計を維持
するオブジェクトを再度考える。
【数５７】
0006617117.tif 000058
マップとしてフラグを立てられる場合、ｐａｇｅ＿ｖｉｅｗｓ表についての関係スキーマ
は、
【数５８】
0006617117.tif 000059
【数５９】
0006617117.tif 000060
である。
この順序化は、ｐａｇｅ＿ｖｉｅｗｓマップ内の値が各ページについて併置されることを
可能にする一方、ＢＩでは、値が日で併置されることになる。
【０１５８】
マップインデックス２（ＭＩ２）
加えて、補助マップインデックスが実装され得る。マップインデックスは、それの機能
性および署名、すなわち、
【数６０】
0006617117.tif 000061
において配列インデックスに類似する。
これは、“ａｌｌ  ｔｈｅ  ｄｉｆｆｅｒｅｎｔ  ｖａｌｕｅｓ  ｃｏｒｅｓｐｏｎｄｉ
ｎｇ  ｔｏ  ｍａｐ  ｋｅｙ  ２０１２‐１２‐０５”などの、特定のマップ要素につい
ての効率的な検索を可能にする。ＡＩ２とＭＩ２の両方の包括的表現は、以下のように書
かれ得る。
【数６１】
0006617117.tif 000062
ここで、キーは、配列のインデックスまたはマップのｍａｐ＿ｋｅｙに対応する。
【０１５９】
値インデックス（ＶＩ：ＶａｌｕｅＩｎｄｅｘ）
上記インデックスは、特定のフィールドについて値をルックアップし、それらの値を通
して繰り返すのに有用であるが、それらは、クエリが特定値または値の範囲だけを探す場
合に高速アクセスを可能にしない。例えば、クエリは、“ｍａｓｈａｈ０８”によって書
かれたツイートのテキストを戻すことを尋ね得る。そのようなクエリを支援するために、
値インデックスは、スキーマ内のいくつかのまたは全てのフィールドについて構築され得
る。値インデックスは、データが採集された際に構築され得るか、あるいは、後で非同期
的に構築され得る。値インデックスについてのキーは、
【数６２】
0006617117.tif 000063
であり、ここで、ｖａｌは、ソースデータにおける属性の値である。ＶＩにおいてそのキ
ーに対応する値は、どこでその値についてのフィールドが発生するかに依存する。上記イ
ンデックスのそれぞれについて、それは変動する。
【数６３】
0006617117.tif 000064
【数６４】
0006617117.tif 000065
【０１６０】
例えば、ツイート、
【数６５】
0006617117.tif 000066
は、
【数６６】
0006617117.tif 000067
として記憶される。
ＶＩを使用すると、キー：（ｒｏｏｔ．ｕｓｅｒ．ｓｃｒｅｅｎ＿ｎａｍｅ，“ｍａｓｈ
ａｈ０８”）を探し、全ての関連ｔｉｄを取り出すことにより、“ｍａｓｈａｈ０８”に
よって書かれた全てのツイートについて検索することができる。次いで、ＢＩは、各ツイ
ートの対応するテキストを戻すために、取り出されたｔｉｄを使用して検索され得る。
インデックス、特に、値インデックスの犠牲は、追加的なストレージスペースであり、新
たなオブジェクトとしてそれらを更新するために必要とされる実行時間がシステムに追加
される。スペースまたは更新オーバーヘッドに起因して、ユーザは、これらが原因で、全
ての可能なパスをインデックス付けることを望み得ない。従って、ユーザは、どのパスを
ＶＩにおいてインデックス付けるかを指定することができる。
【０１６１】
行インデックス（ＲＩ：ＲｏｗＩｎｄｅｘ）
（伝統的な行をベースとしたストアにおけるレコードを要求することに類似して）全て
の採集したオブジェクトの再生成を容易にするために、行インデックス（ＲＩ）が実装さ
れ得る。行インデックスは、キーと値のペア、
【数６７】
0006617117.tif 000068
を記憶する。
【０１６２】
ＪＳＯＮオブジェクトは、文字列表現として、ＢＳＯＮとして、または、ＪＳＯＮオブ
ジェクトの内部表現のために使用されるツリー構造などの任意の他の直列化形式として記
憶され得る。ＶＩに関して上述した２つのツイートの場合、対応するＲＩエントリは、
【数６８】
0006617117.tif 000069
であることになる。
【０１６３】
例
ＢＩ、ＡＩ、ＭＩ、およびＶＩについての例。上記に類似したツイートを考える。ここ
で、“ｒｅｔｗｅｅｔ＿ｆｒｅｑ”属性が追加され、それは、何回ツイートが一日にリツ
イートされたかの追跡を保持する。
【数６９】
0006617117.tif 000070
【０１６４】
これらのレコードのためのスキーマは、
【数７０】
0006617117.tif 000071
である。
【０１６５】
これらのレコードのためのＪＳＯＮスキーマは、
【数７１】
0006617117.tif 000072
【数７２】
0006617117.tif 000073
であることになる。
【０１６６】
ｒｅｔｗｅｅｔ＿ｆｒｅｑがマップとして処理されない場合、関係スキーマは、
【数７３】
0006617117.tif 000074
である。
【０１６７】
この場合において、上記レコード例は、これらの関係を以下のようにポピュレートする
ことになる。
【数７４】
0006617117.tif 000075
【数７５】
0006617117.tif 000076
【０１６８】
これらは、クエリが、“ｓｅｌｅｃｔ*”クエリがこれらの表上で動く場合に戻ること
になるタプルであることに留意する。これらのタプルは、それ自体はストレージエンジン
において必ずしも具体化されない。すなわち、これは、基礎的データ上で単純に仮想ビュ
ーであり得、描写されるように物理的に記憶され得ない。
【０１６９】
ｒｅｔｗｅｅｔ＿ｆｒｅｑがマップとして識別される場合、関係スキーマは、以下のよ
うにより簡潔（および追加データに更に適応すること）になる。
【数７６】
0006617117.tif 000077
【０１７０】
対応するタプルは、
【数７７】
0006617117.tif 000078
である。
【０１７１】
ＢＩに追加されるキーと値のペアは、
【数７８】
0006617117.tif 000079
である。
【０１７２】
ＡＩに追加されるキーと値のペアは以下のようなものである。この場合において、ネス
トされた配列が無いので、結合キーは（ｔｉｄと同様に）冗長であることに留意する。
【数７９】
0006617117.tif 000080
【０１７３】
ＲＩは、以下の２つのエントリを有することになる。
【数８０】
0006617117.tif 000081
【０１７４】
もしそれが構築される場合には、ＭＩは、以下のエントリを有することになる。
【数８１】
0006617117.tif 000082
【０１７５】
同様に、ＶＩは、（全パスがインデックス付けされ、マップがマップのように処理され
る場合）以下のエントリを有することになる。
【数８２】
0006617117.tif 000083
【数８３】
0006617117.tif 000084
【０１７６】
上記アクションは段階的に記述されるが、それらは、採集が単一パスにおいて実行され
ることを可能にするためにパイプライン化され得、ＢＩ、ＡＩ、およびＲＩをロードし、
ＪＳＯＮスキーマを計算する。他のインデックスは、非同期的に構築され得、所望された
通りに有効にされたり無効にされたりし得る。
【０１７７】
システムアーキテクチャ
分析プラットフォームは、サービス指向であるように設計される。種々の実装において
、５つの主なサービス、すなわち、プロキシ、メタデータサービス、クエリエクゼキュー
タ、ストレージサービス、および採集サービスがある。
【０１７８】
この結合解除アプローチは、いくつかの利点を有し得る。これらのサービスは、外部Ａ
ＰＩ（遠隔手順呼び出し）だけを通して通信するので、サービスは、多重化され得、独立
してそれぞれ共有され得る。例えば、多数のプロキシは、エクゼキュータ毎に使用され得
、また、多数のエクゼキュータは、ストレージサービス毎に使用され得る。メタデータサ
ービスはまた、エクゼキュータの多数のインスタンスおよびストレージサービスにわたっ
て共有され得る。
【０１７９】
エクゼキュータ、ストレージ、および採集サービスは並列化され、プライベートまたは
パブリックインフラストラクチャにおける仮想マシンインスタンス内の個々の部分を動か
すことができる。これは、これらのサービスを独立的に中断してスケーリングすることを
可能にする。これは、デマンドの変動に基づいてサービス容量を調整することによって費
用を削減するのに有用である。例えば、パブリッククラウドの融通性が、高速の夜通しの
ローディングのために採集サービスを高度に並列化するように使用され得る一方、実行お
よびストレージサービスを毎日のクエリ作業負荷についてサイズが削減されるよう維持す
る。
【０１８０】
プロキシは、クライアントへのゲートウェイであり、例えばＯＤＢＣ（Ｏｐｅｎ  Ｄａ
ｔａｂａｓｅ  Ｃｏｎｎｅｃｔｉｖｉｔｙ）、ｌｉｂｐｑ、ＪＤＢＣ（Ｊａｖａ  Ｄａｔ
ａｂａｓｅ  Ｃｏｎｎｅｃｔｉｖｉｔｙ）、ＳＳＬ（ｓｅｃｕｒｅ  ｓｏｃｋｅｔｓ  ｌ
ａｙｅｒ）等の、１つ以上の標準プロトコルをサポートする。ゲートウェイは、ファイア
ウォール、認証サービス、および内部サービスのための制御の場所としての機能を果たす
。例えば、クライアント接続（ネットワークソケットなど）は、プロキシでオープンに保
たれ得る一方、実行をサポートし、ストレージサービスは、費用を節約するために中断さ
れる。クライアント接続が再びアクティブになると、必要とされたサービスは、比較的短
い始動待ち時間でオンデマンドに呼び起こされ得る。
【０１８１】
メタデータサービスは、他のサービスの多くのインスタンスによって典型的に共有され
る。それは、スキーマ、ソース情報、分割情報、クライアントユーザ名、キー、統計（ヒ
ストグラム、値分布等）、および各サービスの現在の状態についての情報（インスタンス
の数、ＩＰアドレス等）を含むメタデータを記憶する。
【０１８２】
ストレージサービスは、インデックスを管理し、読み出しおよび書き込み要求を供する
。加えて、クエリエクゼキュータは、多くの関数をストレージサービスにプッシュダウン
することができる。種々の実装において、ストレージサービスは、結果をフィルタにかけ
るために、述語およびＵＤＦ（ユーザが定義した関数）を評価し、（例えば、オブジェク
トを再構築するために）局所的結合を評価し、プッシュダウンされた結合（例えば、ブロ
ードキャスト結合）を評価し、局所的集合を評価することができる。
【０１８３】
ストレージサービスは、分割並列処理と呼ばれる技法を通して並列化され得る。このア
プローチでは、ストレージサービスの非常に多くのインスタンスまたは分割が生成され、
採集されたオブジェクトは分割の間に分けられる。各分割は、単にそれが単一の全体的イ
ンスタンスであるかのように、インデックスの各型を記憶する。しかしながら、各分割は
、単に、採集されたデータのサブセットをインデックス付ける。
【０１８４】
分析エンジンは、１つ以上の分割手法をサポートする。簡単ではあるが効果的な手法は
、ｔｉｄによってオブジェクトを分割し、局所的インデックス内にそれらのそれぞれのエ
ントリを記憶することである。このようにして、採集されたオブジェクトは、クエリがオ
ブジェクトの多数の部分に頼る場合、かなりのネットワーク帯域幅を消費し得る、異なる
インスタンスにわたって分割されない。ｔｉｄは、ハッシュ割り当て、ラウンドロビン、
または範囲をベースとした割り当てを含む多くの手法で割り当てられ得る。これらの特定
の割り当ては、全てのインスタンスにわたって直近のデータを分散し、それによって、負
荷を分散する。
【０１８５】
別の手法は、ユーザｉｄまたはセッションｉｄなどの別のフィールド値（またはフィー
ルド値の組み合わせ）によって分割することである。代替の分割フィールド（カラム）は
、他の表またはコレクション、例えば、ユーザプロフィールで局所的結合を実行すること
を便利にする。分割手法は、ハッシュ分割であり得、あるいはサンプリングおよび範囲分
割を使用し得る。前者は、効率的なポイントルックアップのために使用され、後者は、効
率的な範囲検索をサポートするために使用される。
【０１８６】
分割手法に関わらず、オブジェクトまたは任意のサブセットのオブジェクトは、局所的
に再構築されることができるべきである。従って、ストレージサービス分割は、クエリ処
理の間にクロストークがなく、それらのＡＰＩ経由で実行サービスと通信する必要性だけ
がある。
【０１８７】
ストレージサービスはキャッシュを有する。各分割におけるキャッシュサイズを増やす
ことができ、あるいは、ストレージサービスの性能を改善するために分割の数を増やすこ
とができる。ストレージサービスは、メモリ内にあるいはローカルディスク上にインデッ
クスをキャッシュすることができ、インデックスは、Ａｍａｚｏｎ  Ｓ３のような外部ス
トレージ上に存続することができる。この特徴は、ストレージサービスノードの停止や破
壊を可能にし、また、必要な場合いつでも、それらを再配置することを可能にする。その
上、それは、極度の融通性、すなわち、低い費用でＳ３に対してストレージサービスを休
止状態にし、デマンドが変動する際にストレージサービス容量を変える能力を可能にする
。
【０１８８】
クエリ実行サービスは、クエリ計画段階によって生成されたクエリ計画を実行する。そ
れは、クエリ演算子、例えば、結合、融合、分類、集合などを実装する。これらの演算の
多くは、ストレージサービスにプッシュダウンされ得、可能であればである。これらは、
述語、射影、射影される属性を再構築するためのカラム型結合、ならびにＧＲＯＵＰ  Ｂ
Ｙステートメントを用いる分配的および代数的集合関数のための部分集合を含む。
【０１８９】
クエリ実行サービスは、ストレージサービスからデータを取り込み、非局所的演算、す
なわち、非局所的結合、再分割を必要とするＧＲＯＵＰ  ＢＹステートメント、分類など
を計算する。エクゼキュータは、分割並列処理エクゼキュータに類似する。それは、クエ
リ実行ステップ間で再分割するために交換演算子を使用し、中間結果を流すための局所的
ストレージを利用する。多くのクエリの場合、ストレージサービス内のクエリのほとんど
を動かし、結果を収集し、任意の小さな非局所的演算を実行するために単一のエクゼキュ
ータノードだけを要求することが可能である。
【０１９０】
採集サービス
採集サービスは、半構造データをそれがクエリされ得るストレージサービスにロードす
ることを担当する。ユーザは、オプションとして圧縮機構（例えば、ＧＺＩＰ、ＢＺＩＰ
２、Ｓｎａｐｐｙ）で圧縮される、様々なプラットフォーム（例えば、ＭｏｎｇｏＤＢ、
Ａｍａｚｏｎ  Ｓ３、ＨＤＦＳ）から様々な形式（例えば、ＪＳＯＮ、ＢＳＯＮ、ＣＳＶ
）でデータを提供する。基本手順は、使用される形式に関わらず当てはまる。
【０１９１】
採集タスクは、２つの部分、すなわち、大量の新たなユーザデータをロードする初期採
集タスクと、新たなデータが利用可能であるときに周期的に発生する増分採集と、に大ま
かに分けられ得る。
【０１９２】
初期採集
初期採集処理は、いくつかのステップに分けられ得る。最初に、分割は、データをチャ
ンクに入力する。ユーザは、ファイルのコレクションに、あるいは、それらのデータソー
スへの直接接続を提供することによって初期データを提供する。これらのファイルの位置
や形式は、メタデータサービス内にレコードされる。ユーザは、例えばログファイルロー
テーションに起因して、既に分割されたデータを提供し得るが、そうではない場合、ファ
イルは、並列ローディングをサポートするためにチャンクに分割され得る。これらのチャ
ンクは、典型的には約数百メガバイトであり、独立して処理される。
【０１９３】
入力ファイルを分割するための正確な機構は、データ形式に依存する。レコードが復帰
改行によって分離される非圧縮形式（例えば、ＪＳＯＮまたはＣＳＶ）の場合、単一ファ
イルは、チャンクの対象数に等しい多くの処理を使用して並列に処理され得る。処理は、
ファイル（ｆｉｌｅ＿ｓｉｚｅ／ｔｏｔａｌ＿ｎｕｍ＿ｃｈｕｎｋｓ）*ｃｈｕｎｋ＿ｎ
ｕｍ内の適切なオフセットで開始し、次いで、復帰改行が見付けられるまで検索する。圧
縮されたデータまたはＢＳＯＮのようなバイナリ形式のデータの場合、各入力ファイルは
、順次にスキャンされる必要がある可能性がある。各チャンク（ファイル、オフセット、
サイズ）の位置は、メタデータサービス内に記憶される。
【０１９４】
データが一旦チャンクに分けられると、実際のスキーマ推論および採集が実行される。
この処理の一部として、２つのサービス、すなわち、採集サービスおよびストレージサー
ビスが立ち上げられる。これらの２つのサービスは、作業をするための複数サーバを利用
することができる。２つのサービスはまた、任意の所与のマシン上に併置され得る。採集
サービスは、一時的であり、採集処理の間にだけ使用される一方、ストレージサービスは
、実際のデータを保持し、持続的である必要がある。採集に関係のあるサーバは、ストレ
ージサービスサーバにデータを送信し、採集サーバの数は、ストレージサーバの数と独立
しており、ここで、その数は、各サービスのスループット間の不均衡を最小限にするため
に選択される。チャンクは、採集サーバ間で分割される。各採集サーバは、それに割り当
てられた各チャンクについて以下のステップ、すなわち、（ｉ）構文解析と型推論、（ｉ
ｉ）ストレージサービスとの通信、ならびに（ｉｉｉ）局所的スキーマおよび統計の計に
ついて担当する。
【０１９５】
最初に、データレコードが、内部ツリー表現に構文解析される。矛盾しない内部表現は
、全てのソース形式（ＪＳＯＮ、ＢＳＯＮ等）について使用され得る。入力形式に従って
、型推論がまた、実行され得る。例えば、ＪＳＯＮは日付の表現を有さないので、それは
、文字列として日付を記憶するのが一般的である。日付は非常に一般的であるので、それ
らは、ユーザが日付を使用するクエリを発行することができるように、採集の間に検出さ
れる型の例についてのものである。ＣＳＶ入力ファイルの場合、カラムは型付けされない
ので、整数などの基本型もまた、検出される必要がある。
【０１９６】
一旦、レコードが構文解析され、型が推論されると、構文解析ツリーの圧縮された表現
が、ストレージサービスに送信される。このタスクは、ツリーの前順走査の形態を取る。
ストレージサービスは、インデックス（ＢＩ、ＡＩ等）のそれぞれに記憶するために値を
決定することと、タプルｉｄおよび結合キーを生成することと、を担当する。キー生成は
、キーが順次に生成され得るようにストレージサービスにゆだねられ、それは、基礎的イ
ンデックスストアに対する採集性能を改善する。
【０１９７】
レコードが採集される際、局所的ＪＳＯＮスキーマは、上記規則を使用して更新される
。スキーマは、単一採集マシンによって見られるレコードを反映することになり、異なる
マシンは、異なるスキーマを有し得る。
【０１９８】
スキーマを計算することに加えて、マップを識別することと同様にクエリ処理のために
有用である統計が維持される。これらは、各属性が現れる回数ならびにバイトでのそれの
平均サイズのようなメトリックを含む。例えば、以下のレコード
【数８４】
0006617117.tif 000085
【数８５】
0006617117.tif 000086
は、スキーマ｛ｉｄ：ｉｎｔ，ｉｄ：ｓｔｒｉｎｇ｝を作り出すことになり、ｉｄ：ｉｎ
ｔは、３の数で、ｉｄ：ｓｔｒｉｎｇは、２の数で注釈を付けられ得る。各採集マシンは
、それが計算したスキーマおよび統計をメタデータサービス内に記憶する。
【０１９９】
チャンクの全てが一旦採集されると、スキーマ全体が計算され、それは、クエリエンジ
ンによって使用され、ユーザに提示されることになる。これは、メタデータサービスから
部分的スキーマを読み取り、上記方法を使用してそれらを併合し、結果をメタデータサー
ビス内に戻して記憶する単一処理を使用して、達成され得る。スキーマの数は、採集マシ
ンの数に限定されるので、この処理は、性能に重要ではない。
【０２００】
マップ決定はオプションである。前に記載したように、発見的問題解決法が、どの属性
がＭＩ内にマップとして記憶されるべきであるかを決定するために、メタデータサービス
内に記憶された統計と共に使用され得る。これはクエリ処理に必要ではないが、それは、
いくつかのクエリをより自然に表現させ、効率を改善することを思い起こす。マップが一
旦識別されると、各ストレージサーバは、どの属性がマップであるべきかを識別するメッ
セージを受信する。ストレージサーバは、次いで、これらのカラムをスキャンし、それら
をＭＩに挿入する。
【０２０１】
増分更新
いくらかのユーザは、前もってそれらのデータの塊をロードし得るが、ほとんどは、周
期的に新たなデータを経時的に、多くの場合、規則的（例えば、毎時または毎日の）処理
の一部として、ロードすることになる。このデータの採集は、初期採集に概ね類似する。
新たなデータは、チャンクに分割され、スキーマはチャンク毎に計算され、局所的スキー
マは、メタデータサービス内に維持された大域的スキーマと併合される。
【０２０２】
システムは、新たなデータをそれが追加される際に自動的に検出する。方法はソースデ
ータプラットフォームに依存する。例えば、Ｓ３ファイルの場合、最も簡単なケースは、
Ｓ３バケットの変化を検出することである。特殊処理は、新たなキーと値のペア（すなわ
ち、新たなファイル）についてバケットを周期的にスキャンし、メタデータサービスに見
付けられる任意のものを追加する。一定数の新たなファイルが見付けられたか一定期間が
経過した後、処理は、データをロードするための新たな採集処理を立ち上げる。
【０２０３】
ＭｏｎｇｏＤＢにおいて実行される操作は、オペレーションログ（またはｏｐｌｏｇ）
と呼ばれる特殊コレクションにおいて記憶され得る。ｏｐｌｏｇは、複製のために内部で
ＭｏｎｇｏＤＢによって使用される書き込み操作の矛盾しないレコードを提供する。ｏｐ
ｌｏｇは、新たなレコードを記憶するＳ３内に１組の単層ファイルを生成するために読み
取られ、使用される。上記方法は、次いで、新たなデータ採集するために使用され得る。
【０２０４】
増分採集処理は、新たなデータ（例えば、新たなＪＳＯＮドキュメント）と、既存のド
キュメントへの更新（例えば、既存のＪＳＯＮドキュメントにおける新たな属性または既
存の属性についての新たな値）の両方を取り扱うことができる。各データソースプラット
フォームは、ソースファイルにおける更新を露出することに関して異なる可能性を有する
。この型の情報を“ｄｅｌｔａ”として呼び、それは、単層ファイルまたはログファイル
（例えば、ＭｏｎｇｏＤＢ）の形態を取り得る。増分採集処理は、“ｄｅｌｔａ”ファイ
ルからの情報を処理し、ストレージサービスに送信される新たなデータを生成するために
それを既存のスキーマ情報と組み合わせる。
【０２０５】
データのサブセッティング
データを採集し増分更新を行うための、ここに記載されたシステムは、ソースから全デ
ータを採集することができ、採集されることを望むデータのＪＳＯＮスキーマ（または関
係スキーマ）を前もって指定することによって、サブセットだけを採集することは比較的
簡単である。これは、ＪＳＯＮスキーマ自体を提供することによって、あるいは、サブセ
ットを指定するクエリを提供することによって行われる。このようにして、分析プラット
フォームは、ソースデータの具体化ビューとして考えられ得る。
【０２０６】
また、ユーザが採集されることを望まないデータを指定することも可能である。採集さ
れるべきではないデータの一部を記述するＪＳＯＮスキーマまたは関係スキーマが提供さ
れ得る。次いで、全ての将来の行のそれらの要素を単にスキップするように採集処理に告
げるその情報をメタデータサービスで記憶すればいいだけでのことである。これが、デー
タが既に採集された後に行われる場合、既に採集したデータは、単に利用不可能になり、
バックグラウンドのタスクによってガーベジコレクションをかけられ得る。このガーベジ
コレクションは、インデックスストア（例えば、ＬｅｖｅｌＤＢ）の圧縮処理に組み込ま
れることになる。
【０２０７】
耐障害性
初期採集の間にロード処理を開始するのが可能である一方、増分採集処理は、ユーザに
最初から全データをリロードさせることを防ぐために、システムにおける既存のデータを
破損させるべきではない。ファイル採集は冪等操作ではないので、ｉｄ生成に起因して、
簡単な耐障害性体系が、基礎的ストレージシステムのスナップショットを取ることに基づ
いて実装され得る。
【０２０８】
スナップショットを取ることは、ＬｅｖｅｌＤＢが行うように、基礎的ストレージシス
テムがある時点で矛盾しないスナップショットを取ることをサポートするときに簡単であ
り得る。このプリミティブで、増分ローディングのためのステップは、以下のようなもの
である。単一処理は、各ストレージサーバにスナップショットを局所的に取ることを導き
、全クエリをロードの期間にこのスナップショットに導く。各チャンクは、上記のように
ロードされる。完了すると、チャンクをロードすることを担当する採集サーバは、それを
メタデータサービスにおいて終了したものとして印を付ける。
【０２０９】
処理は、メタデータサービスを監視する。全チャンクがロードされている場合、それは
、クエリを状態の更新されたバージョンにアトミックに再び導く。次いで、第１のステッ
プにおいて取られたスナップショットは捨てられ得る。故障の場合には、スナップショッ
トは、状態の標準的なバージョンになり、部分的に更新された（および潜在的に破損され
た）状態の元のバージョンは捨てられる。次いで、採集処理が再開される。追加的に、ス
トレージシステムディスクボリュームのスナップショットが、サーバ故障の場合には回復
のために使用され得る。
【０２１０】
クエリの実行
クエリ例
実行例を示すために、簡単なクエリ、
【数８６】
0006617117.tif 000087
を考える。最初に、プロキシは、クエリを受信し、計画のためにそれをエクゼキュータノ
ードに発行する。次に、エクゼキュータノードは、どのコレクションおよびストレージノ
ードが使用のために利用可能であるかを決定するためにメタデータサービスを呼び出すク
エリ計画を生成する。エクゼキュータノードは、典型的には、計画を他のエクゼキュータ
ノードに分散させるが、ここでは、単一エクゼキュータノードだけを必要とする。
【０２１１】
実行ノードは、次いで、ＲＰＣ呼び出しをストレージサービスノードに行い、ｔ．ａ＞
１０述語およびカウント関数をプッシュダウンする。次に、ストレージノードは、サブカ
ウントを計算し、それらをエクゼキュータノードに戻す。エクゼキュータノードは、次い
で、プロキシが次の結果値をフェッチするときに結果をプロキシに戻す。
【０２１２】
動的型付け
データベースシステム（例えば、ＰｏｓｔｇｒｅＳＱＬ）のストレージエンジンは、強
く型付けされ、それは、カラム（または属性）の値の全てが、全く同じ型（例えば、整数
、文字列、タイムスタンプ等）を有する必要があることを意味する。ビッグデータ分析の
関連において、これは、かなり多くのアプリケーションが情報（属性）の特定の部分の表
現、その結果として、それらがそれを記憶するために使用するデータ型、を変えることを
必要とするので、かなりの限定である。例えば、アプリケーションは、整数を使用して特
定の属性の値を初期に記憶し得、次いで、浮動小数を使用することに切り替える。データ
ベースシステムは、そのような操作をサポートするように設計されていない。
【０２１３】
この問題を取り扱う１つの手法は、多数の関係カラムを各属性について、すなわち、１
つの関係カラムを各異なるデータ型のそれぞれについて、使用することである。例えば、
値３１４３２および“３１４３３”（すなわち、整数および文字列）を有する属性“ｕｓ
ｅｒ．ｉｄ”を見た場合、別個のカラムとして“ｕｓｅｒ．ｉｄ＜ｉｎｔ＞”および“ｕ
ｓｅｒ．ｉｄ＜ｓｔｒｉｎｇ＞”を記憶することができる。単一レコードは、そのレコー
ドにおける“ｕｓｅｒ．ｉｄ“の型に対応するこれらのカラムの１つだけについての値を
有することになる。そのレコードのための他のカラムについての値はＮＵＬＬであること
になる。
【０２１４】
同じ属性について多数のカラムを提示することは、ユーザが使用するには複雑すぎるこ
とが多い。ユーザの経験を簡略化するために、分析プラットフォームは、クエリ時間に動
的に、ユーザが使用することを意図する型を推論することができる。この目的のために、
ストレージサービスは、多数の型の追跡を保持する。例えば、ストレージサービスは、Ｎ
ＵＭＢＥＲと呼ばれる、数字についての包括的データ型を使用し、それは、整数と浮動小
数の両方をカバーする。ＮＵＭＢＥＲ型が使用されるとき、更に具体的なデータ型が、値
の一部として記憶される。例えば、属性“Ｃｕｓｔｏｍｅｒ．ｍｅｔｒｉｃ”の整数値１
０は、キーと値のペアとしてＢＩ内に記憶され、ここで、（Ｃｕｓｔｏｍｅｒ．ｍｅｔｒ
ｉｃ，＜ＮＵＭＢＥＲ＞，ｔｉｄ）がキーであり、（１０，ＩＮＴＥＧＥＲ）が値である
。同じ属性の浮動小数点値１０．５は、キー：（Ｃｕｓｔｏｍｅｒ．ｍｅｔｒｉｃ，＜Ｎ
ＵＭＢＥＲ＞，ＴＩＤ）、値：（１０．５，ＦＬＯＡＴ）として記憶されることになる。
【０２１５】
最終的に、クエリ時間に、分析プラットフォームは、これらの操作が情報損失を結果と
してもたらさない限り、クエリの特性（述語、キャスティング操作等）に従ってデータ型
間の動的キャスティングを実行できる。“ｎｕｍｂｅｒ”はＡＮＳＩ  ＳＱＬ型ではない
が、柔軟な型付けシステムは、クライアントが、クエリコンテキストから標準ＡＮＳＩ  
ＳＱＬ浮動小数、整数、または数値型としてそれを処理することを可能にする。例えば、
クエリ、
【数８７】
0006617117.tif 000088
を考える。“ｕｓｅｒ．ｉｄ＜ｉｎｔ＞”および“ｕｓｅｒ．ｉｄ＜ｓｔｒｉｎｇ＞”の
両方を有する場合において、システムは、オプションとして、クエリ時間に整数（例えば
、３１４３２）を単一文字列表現（例えば、“３１４３２”）に変換し、それによって、
ユーザが、ＡＮＳＩ  ＳＱＬ型ＶＡＲＣＨＡＲで単一カラム“ｕｓｅｒ．ｉｄ”を処理す
ることを可能にする。
【０２１６】
ＡＮＳＩ（Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔ
ｕｔｅ）／ＩＳＯ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  
Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ）ＳＱＬ：２００３が例として言及されるが、あるいは
、そうではない場合、他の実装では、他の標準、ＳＱＬと準拠するものが実現され得る。
単なる例として、露出されたインターフェースは、ＡＮＳＩ／ＩＳＯ  ＳＱＬ：２０１１
に準拠し得る。
【０２１７】
図面
図１Ａには、分析プラットフォームのクラウドをベースとした実装例が示される。分析
フレームワークを使用する組織のローカルエリアネットワーク（ＬＡＮ）またはワイドエ
リアネットワーク（ＷＡＮ）１００が、インターネット１０４に接続する。この実装にお
ける計算ニーズおよびストレージニーズは、いずれも、クラウドをベースとしたサービス
によって提供される。示される特定の実装では、計算サーバは、ストレージサーバから分
離される。特に、計算クラウド１０８は、分析フレームワークに処理能力を与える複数の
サーバ１１２を含む。サーバ１１２は、離散的なハードウェアインスタンスであってもよ
いし、あるいは、仮想サーバであってもよい。
【０２１８】
サーバ１１２はまた、それら自体のストレージを有し得、そのストレージ上で処理機能
が動作する。例えば、サーバ１１２は、クエリエクゼキュータとストレージサービスの両
方を実装し得る。伝統的なカラム型ストレージシステムは、ディスク上にカラムとしてデ
ータを記憶するが、そのデータがメモリに読み込まれたとき、行は、カラム型データから
再び組み立てられる。しかしながら、本開示のインデックスは、ディスク上とメモリ内の
両方でカラム型ストレージとして機能する。インデックスの固有構成が原因で、高速カラ
ム型アクセスの利益は、比較的小さな不利益を伴って得られ得る。
【０２１９】
ストレージクラウド１１６は、本開示によれば、データはインデックス内に格納され、
具体化表内には格納されないので、インデックスデータのために使用されるストレージ配
列１２０を含む。サーバ１１２のストレージリソースが使用されるとき、ストレージ配列
１２０は、各クエリに応答するためではなく、バックアップおよびニアラインストレージ
のために使用され得る。
【０２２０】
種々の実装において、ストレージ配列１２４は、分析フレームワークがデータについて
動作することになる当該データを含み得る。単なる例として、ストレージ配列１２４は、
ユーザが分析フレームワークを使用してクエリすることを望み得る、ログデータなどの関
連したデータを保持し得る。ストレージ配列１２０およびストレージ配列１２４が同じス
トレージクラウド１１６内に示されるが、それらは、プライベートの外部にホストされた
クラウド、パブリッククラウド、および組織に特定の内部にホストされた仮想環境を含む
、異なるクラウド内に位置し得る。
【０２２１】
単なる例として、ストレージクラウド１１６は、Ａｍａｚｏｎ  Ｗｅｂ  Ｓｅｒｖｉｃ
ｅｓ（ＡＷＳ）Ｓ３クラウドであり得、それは、ビジネスがストレージ配列１２４内にデ
ータを記憶するために既に使用している。結果として、データをストレージ配列１２０に
移すことは、高スループットおよび低費用で実現され得る。計算クラウド１０８は、ＡＷ
Ｓ  ＥＣ２によって提供され得、その場合において、計算クラウド１０８およびストレー
ジクラウド１１６は、共通プロバイダによってホストされる。ユーザ１３０は、標準ＳＱ
Ｌツールを使用してクエリを構築し、そのクエリは計算クラウド１０８において動作し、
応答はユーザ１３０に戻される。ＳＱＬツールは、ユーザ１３０のコンピュータ１３４上
に既にインストールされたツールであり得、本分析フレームワークで動作するために修正
される必要が無い。
【０２２２】
図１Ｂでは、別のデプロイメントアプローチ例が示される。この場合において、物理サ
ーバアプライアンス１８０はビジネスのＬＡＮ／ＷＡＮ１００に接続される。サーバアプ
ライアンス１８０は、オンサイトでホストされ得るかオフサイトでホストされ得、仮想プ
ライベートネットワークなどを用いて、ＬＡＮ／ＷＡＮ１００に接続され得る。サーバア
プライアンス１８０は、ストレージのみならず計算能力を含み、ソースから入力データを
受信し、そのソースは、ＬＡＮ／ＷＡＮ１００に対して局所的であり得る。単なる例とし
て、コンピュータもしくはサーバ１８４は、ウェブトラフィックログまたは侵入検出ログ
などのログを記憶し得る。
【０２２３】
サーバアプライアンス１８０は、ユーザ１３０のクエリに応答するためにインデックス
データを取り出し記憶する。ストレージクラウド１１６は、追加データソース１８８を含
み得、それは、更に他のデータを保持し得るおよび／またはより古いデータのためのニア
ラインデータストレージ設備であり得る。サーバアプライアンス１８０は、ユーザクエリ
を満たすために、追加データソース１８８から追加データを取り出し得る。サーバアプラ
イアンス１８０はまた、バックアップ目的などのために、ストレージクラウド１１６内に
データを記憶し得る。種々の他の実装では、追加データソース１８８は、クラウドにおけ
るＨａｄｏｏｐ実装の一部であり得る。
【０２２４】
本開示の分析フレームワークは、多くの他のデプロイメントシナリオが可能であるよう
に柔軟である。単なる例として、ソフトウェアがビジネスに提供され得、そのソフトウェ
アは、所有されたまたはホストされたサーバ上にインストールされ得る。別の実装では、
仮想マシンインスタンスが提供され得、それは、仮想化環境を通してインスタンス化され
得る。なお更に、ユーザは、ブラウザにおいてユーザインターフェースが提供され得、Ｓ
ＱＬ部分は、Ｎｏｕ  Ｄａｔａなどのサービスプロバイダによってホストされ得、それら
のシステム上またはクラウドにおいて実装され得る。
【０２２５】
図１Ｃには、サーバ２００のハードウェア構成要素が示される。プロセッサ２０４は、
メモリ２０８からの命令を実行し、メモリ２０８内に記憶された（読み書き）データ上で
動作し得る。一般に、速さのために、メモリ２０８は揮発性メモリである。プロセッサ２
０４は、潜在的にチップセット２１２経由で、不揮発性ストレージ２１６と通信する。種
々の実装において、不揮発性ストレージ２１６は、キャッシュとして機能するフラッシュ
メモリを含み得る。より大容量および低費用のストレージが、２次不揮発性ストレージ２
２０のために使用され得る。例えば、ハードドライブなどの磁気ストレージ媒体は、２次
不揮発性ストレージ２２０内に基礎的データを記憶するために使用され得、それのアクテ
ィブな部分は、不揮発性ストレージ２１６内にキャッシュされる。
【０２２６】
入出力機能２２４は、キーボードやマウスなどの入力と、グラフィックディスプレイや
音声出力などの出力とを含み得る。サーバ２００は、ネットワーキングカード２２８を使
用して他のコンピューティングデバイスと通信する。種々の実装において、または種々の
時間に、入出力機能２２４が休止し、サーバ２００と外部アクターとの間の全ての相互作
用がネットワーキングカード２２８経由で行われてもよい。例示のし易さのために、例え
ば、単なる例として、不揮発性ストレージ２１６とメモリ２０８との間またはネットワー
キングカード２２８とメモリ２０８との間のダイレクトメモリアクセス（ＤＭＡ）機能な
どの、追加のよく知られた特徴および変形は示されない。
【０２２７】
図２Ａにおいて、処理図は、どのようにデータが、それがユーザ１３０によってクエリ
され得るように、分析的なフレームワークに採集されたかの一例を示す。データソース３
００はデータを提供し、そのデータについて分析フレームワークが動作する。その生デー
タが自己記述ではない場合、オプションのユーザが定義したラッパー関数３０４は、生デ
ータをＪＳＯＮオブジェクトなどの自己記述の半構造データに変換し得る。
【０２２８】
異なる容量を操作するユーザ１３０であり得るアドミニストレータ３０８は、これらの
ラッパー関数を実装するためのガイドラインを指定することができる。アドミニストレー
タ３０８はまた、データソース３００のどれを使用し、どのデータをそれらのデータソー
スから取り出すかを指定することができる。種々の実装において、データを取り出すこと
は、サブセッティング操作および／または他の計算を含み得る。単なる例として、データ
ソース３００の１つがＨａｄｏｏｐであるとき、ＭａｐＲｅｄｕｃｅジョブが、分析フレ
ームワークのためにデータを取り出す前に要求され得る。
【０２２９】
取り出されたデータは、受信されたデータの観察された構造に基づいてスキーマを動的
に構築するスキーマ推論モジュール３１２によって処理される。アドミニストレータ３０
８は、種々の実装において、スキーマ推論モジュール３１２に型付けヒント（ｈｉｎｔ）
を提供する能力を有し得る。例えば、型付けヒントは、例えば正規表現によって指定され
得る、日付、時間、または他のアドミニストレータが定義した型などの特定形式を認識す
るための要求を含み得る。
【０２３０】
スキーマ推論モジュール３１２によって生成されたデータオブジェクトおよびスキーマ
は、装飾モジュール３１６のみならずインデックス生成モジュール３２０に提供される。
入力オブジェクトは、ソースデータのみならずソースデータを記述するメタデータを含む
。ソースデータは、インデックス生成モジュール３２０によってインデックスストレージ
３２４内に記憶される。
【０２３１】
装飾モジュール３１６は、スキーマモジュール３１２によって生成されたスキーマにお
いてマップを識別する。マップ識別が所望されない実装では、装飾モジュール３１６は省
略され得る。アドミニストレータ３０８は、マップを識別する際に使用される装飾モジュ
ール３１６によって実行される発見的問題解決法を調整するために、マップ基準を指定す
ることができる。
【０２３２】
マップが識別された後、関係スキーマ生成モジュール３２８は、ＳＱＬに準拠したスキ
ーマなどの関係スキーマを生成する。加えて、識別されたマップは、補助インデックス生
成モジュール３３２に提供され、そのモジュール３３２は、上記したような、ＭａｐＩｎ
ｄｅｘなどの追加インデックス、およびＶａｌｕｅＩｎｄｅｘにおけるマップエントリを
生成することができる。補助インデックスはまた、インデックスストレージ３２４内に記
憶され得る。
【０２３３】
アドミニストレータ３０８は、マップインデックスが生成されることを要求する能力を
有し得、どのカラムが値インデックスに追加されるかを指定し得る。加えて、アドミニス
トレータは、どのオブジェクトがマップとして処理されるべきであるかを指定することが
でき、オブジェクトがマップとして処理されるか否かを動的に変更することができる。そ
のような変更は、関係スキーマの変更を結果としてもたらすことになる。
【０２３４】
関係最適化モジュール３３６は、ユーザ１３０により簡潔なスキーマを提示するように
、関係スキーマを最適化する。例えば、関係最適化モジュール３３６は、上記したように
、表間の１対１関係を識別し得、それらの表を単一の表に平坦化し得る。結果として生じ
る関係スキーマは、メタデータサービス３４０に提供される。
【０２３５】
クエリエクゼキュータ３４４は、プロキシ３４８からのクエリを実行するためにメタデ
ータサービス３４０とインターフェースを取る。プロキシ３４８は、特殊構成無しに、プ
ロキシ３４８と相互作用することができるＯＤＢＣクライアント３５２などのＳＱＬに準
拠したクライアントと相互作用する。ユーザ１３０は、クエリをクエリエクゼキュータ３
４４に送信し、それらのクエリに対する応答を受信するために、ＯＤＢＣクライアント３
５２を使用する。
【０２３６】
ＯＤＢＣクライアント３５２経由で、ユーザ１３０はまた、メタデータサービス３４０
によって記憶された関係スキーマを見ることができ、関係スキーマ上でクエリを構築する
ことができる。ユーザ１３０もアドミニストレータ３０８も、予測されたスキーマを知る
こと、またはスキーマの生成を助けることを要求されない。代わりに、スキーマは、取り
出されたデータに基づいて動的に生成され、次いで、提示される。ＯＤＢＣクライアント
３５２が示されるが、ＪＤＢＣを含むＯＤＢＣ以外の機構が利用可能であり、ｐｏｓｔｇ
ｒｅｓクエリを導く。種々の実装において、グラフィカルユーザインターフェースアプリ
ケーションは、ユーザによるＯＤＢＣクライアント３５２の使用をし易くし得る。
【０２３７】
クエリエクゼキュータ３４４は、インデックスストレージ３２４を含むストレージサー
ビス３５６からのデータ上で動作する。ストレージサービス３５６は、それ自体の局所的
ストレージ処理モジュール３６０を含み得、そのモジュール３６０に対してクエリエクゼ
キュータ３４４は、種々の処理タスクを委任することができる。処理されたデータは、次
いで、受信されたクエリへの応答を構築するために、ストレージ処理モジュール３６０に
よってクエリエクゼキュータ３４４に提供される。クラウドをベースとした実装では、ス
トレージサービス３５６およびクエリエクゼキュータ３４４は共に、計算クラウド内に実
装され得、インデックスストレージ３２４は、計算インスタンス内に記憶され得る。イン
デックスストレージ３２４は、図１Ａに示されるようなストレージクラウド１１６内など
の、ニアラインストレージに反映され得る。
【０２３８】
図２Ｂでは、高レベル機能的図が、複数ノード４０２‐１、４０２‐２、および４０２
‐３（集合的に、ノード４０２）を有するストレージサービス３５６を示す。３つのノー
ド４０２が示されるが、より多いかより少ないものが使用され得、使用される数は、分析
フレームワークの必要性に基づいて動的に変動され得る。ノード４０２の数は、より多く
のデータが記憶される必要性があるにつれて、ならびに、クエリを実行するためにおよび
／または冗長性を提供するために要求される追加処理に応答して、増加され得る。クエリ
エクゼキュータ３４４が、ノード４０６‐１、４０６‐２、および４０６‐３（集合的に
、ノード４０６）と共に示される。ノード４０６の数はまた、クエリロードに基づいて動
的に変動され得、ノード４０２の数と独立している。
【０２３９】
プロキシ３４８は、ＯＤＢＣクライアント３５２とクエリエクゼキュータ３４４との間
のインターフェースを提供する。クエリエクゼキュータ３４４は、ストレージサービス３
５６内にあるデータについてのスキーマを記憶するメタデータサービス３４０と相互作用
する。
【０２４０】
図３は、データ採集のための処理例を示す。制御は５０４で始まり、ここで、データの
ソースは、ユーザまたはアドミニストレータなどによって、指定され得る。加えて、デー
タのソースからの一定のデータセットが選択され得、一定のサブセッティングおよび低減
操作がデータソースに要求され得る。制御は５０８に続き、ここで、指定されたデータソ
ースは、新たなデータのために監視される。
【０２４１】
５１２では、新たなデータオブジェクトがデータソースに追加された場合、制御は５１
６に移り、そうではない場合、制御は、所望された場合にデータのソースが修正されるこ
とを可能にするために、５０４に戻る。５１６では、新たなオブジェクトのスキーマが推
論され、それは、図４に示されるような型関数に従って実行され得る。５２０では、５１
６から推論されたスキーマが、既に存在しているスキーマと併合される。併合は、図５に
示されるような併合関数に従って実行され得る。
【０２４２】
５２４では、装飾が所望される場合、制御は５２８に移り、そうではない場合、制御は
５３２に移る。５２８では、マップが、図８に示されるように、データ内で識別される。
５３６では、新たなマップが識別されない場合、制御は５３２に続き、そうではない場合
、新たなマップが識別された場合、制御は５４０に移る。５４０では、マップインデック
スが所望される場合、制御は５４４に移り、そうではない場合、制御は５３２に続く。５
４４では、新たなマップ属性と関連付けられたＢｉｇＩｎｄｅｘまたはＡｒｒａｙＩｎｄ
ｅｘにおける各値について、その値が、マップインデックスに追加される。更に、ユーザ
および／またはアドミニストレータによって所望される場合、特定の属性について、値が
値インデックスに追加される。制御は次いで５３２に続く。
【０２４３】
種々の実装において、５２４における装飾は、オブジェクトの第１のラウンドが処理さ
れるまで待機し得る。例えば、初期採集上で、装飾は、初期オブジェクトの全てが採集さ
れるまで遅延され得る。このようにして、十分な統計が、マップの発見的問題解決法によ
る使用のために収集されていることになる。追加オブジェクトの増分採集のために、装飾
は追加オブジェクトの新たなグループのそれぞれの後に実行され得る。
【０２４４】
５３２では、ＪＳＯＮスキーマが新たなオブジェクトの結果として変更された場合、制
御は５４８に移り、ここで、スキーマは関係スキーマに変換される。制御は５５２に続き
、ここで、１対１関係を平坦化することなどによって、関係ビューが最適化される。制御
は次いで５５６に続く。スキーマが５３２で変更されていない場合、制御は直接的に５５
６に移ることになる。５５６では、インデックスは、図７に示されるように実行され得る
新たなオブジェクトのデータをポピュレートされる。制御は次いで５０４に戻る。
【０２４５】
５４８で推論されたスキーマを関係スキーマに変換した後に実行されるものとして、イ
ンデックスのポピュレーションが５５６に示されるが、種々の実装において、インデック
スは、関係スキーマが要求されないので、関係スキーマを生成する前にポピュレートされ
得る。手順は、パスおよび結合キーを生成するために推論されたＪＳＯＮスキーマを使用
することができる。関係スキーマは、基礎的半構造データの関係ビューとして機能する。
【０２４６】
図４は、再帰に頼る型関数の実装例を示す。制御は６０４で始まり、ここで、型付けさ
れることになるオブジェクトがスカラである場合、制御は６０８に移る。６０８では、ス
カラの型が決定され、そのスカラ型は、６１２で関数の出力として戻される。スカラ型は
、受信されたオブジェクトにおける自己記述に基づいて決定され得る。加えて、一定の文
字列が日付または時間などのデータを表現するものであることを認識し得る更なる型付け
規則が使用され得る。
【０２４７】
６０４では、オブジェクトがスカラではない場合、制御は６１６に移る。６１６では、
オブジェクトが配列である場合、制御は６２０に移り、ここで、型関数（図４）は、配列
の各要素上で再帰的に呼び出される。これらの型関数の結果が受信されたとき、制御は６
２４に続き、ここで、図６に示されるような折り畳み関数が、６２０で決定されたような
要素型の配列上で呼び出される。折り畳まれた配列が折り畳み関数によって戻されると、
その折り畳まれた配列が、６２８で型関数によって戻される。
【０２４８】
６１６で、オブジェクトが配列ではない場合、制御は６３２に移る。６３２では、型関
数（図４）は、オブジェクトの各フィールド上で再帰的に呼び出される。制御は６３６に
続き、ここで、折り畳み関数は、６３２で決定されたフィールド型の連結上で呼び出され
る。折り畳み関数によって戻された折り畳まれたオブジェクトは、次いで、６４０で型関
数によって戻される。
【０２４９】
図５は、２つのスキーマ要素を単一のスキーマ要素に併合する併合関数の実装例を示す
。併合関数はまた、再帰的であり、最初に呼び出されるとき、２つのスキーマ要素は、既
存のスキーマおよび新たに受信されたオブジェクトから推論された新たなスキーマである
。併合関数の更なる再帰的呼び出しでは、スキーマ要素は、これらのスキーマのサブ要素
であることになる。制御は７０４で始まり、ここで、併合されることになるスキーマ要素
が等価である場合、制御は７０８に移り、等価スキーマ要素のいずれか１つを戻す。そう
ではない場合、制御は７１２に移り、ここで、併合されることになるスキーマ要素が両方
とも配列である場合、制御は７１６に移り、そうではない場合、制御は７２０に移る。
【０２５０】
７１６では、併合されることになる配列の１つが空である場合、他の配列は７２４に戻
される。そうではない場合、制御は７２８に続き、ここで、図６に示されるような折り畳
み関数が、併合されることになる両方の配列の要素を含有する配列上で呼び出される。折
り畳み関数によって戻された折り畳まれた配列は、次いで、７３２で併合関数によって戻
される。
【０２５１】
７２０では、併合されることになるスキーマ要素の１つが空である場合には、他のスキ
ーマ要素は、７３６で併合関数によって戻される。併合されることになるスキーマ要素の
いずれもが空ではない場合、制御は７４０に続き、ここで、折り畳み関数が、併合される
ことになる両方のスキーマ要素のキーと値のペアを含有するオブジェクト上で呼び出され
る。折り畳み関数によって戻された折り畳まれたオブジェクトは、次いで、７４４で併合
関数によって戻される。
【０２５２】
図６は、折り畳み関数の実装例を示す。制御は８０４で始まり、ここで、折り畳まれる
ことになるオブジェクトが配列である場合、制御は８０８に移り、そうではない場合、制
御は８１２に移る。８０８では、配列が、両方とも配列である値のペアを含有する場合、
制御は８１６に移り、そうではない場合、制御は８２０に続く。８２０では、配列が、両
方ともオブジェクトである値のペアを含有する場合、制御は８１６に移り、そうではない
場合、制御は８２４に続く。８２４では、配列が、等しいスカラ型である値のペアを含有
する場合、制御は８１６に移り、そうではない場合、折り畳みが完了し、配列が折り畳み
関数から戻される。８１６では、図５に示されるような併合関数が、８０８、８２０、ま
たは８２４によって識別された値のペア上で呼び出される。制御は８２８に続き、ここで
、値のペアは、併合関数によって戻される単一値で置換される。
【０２５３】
８１２では、オブジェクト内の任意のキーが同じである場合、制御は８３２に移り、そ
うではない場合、折り畳みが完了し、オブジェクトは戻される。８３２では、制御は、同
じであるキーのペアを選択し、８３６に続く。キーのペアについての値が両方とも配列で
あるか、両方ともオブジェクトである場合、制御は８４０に移り、そうではない場合、制
御は８４４に移る。８４０では、キーのペアについての値上で併合関数が呼び出される。
制御は８４８に続き、ここで、キーのペアが、併合関数によって戻される値を有する単一
キーで置換される。制御は、次いで８５２に続き、ここで、任意の追加キーが同じである
場合、制御は８３２に移り、そうではない場合、折り畳みが行われ、修正される際にオブ
ジェクトは戻される。８４４では、キーのペアについての値が両方ともスカラである場合
、制御は８５６に移り、そうではない場合、制御は８５２に移る。８５６では、キーのペ
アについての値のスカラ型が等しい場合、制御はキーのそれらのペアを併合するために８
４０に移り、そうではない場合、制御は８５２に移る。
【０２５４】
図７は、新たに取り出されたオブジェクトからのデータをインデックスにポピュレート
するための処理例を示す。制御は９０４で始まり、ここで、ＲｏｗＩｎｄｅｘが所望され
る場合、制御は９０８に移り、そうではない場合、制御は９１２に移る。９０８では、オ
ブジェクトが、上記のようにＲｏｗＩｎｄｅｘに追加され、制御は９１２に続く。９１２
では、オブジェクトは、現在の関係スキーマについて関係タプルに平坦化され、結合キー
が必要に応じて生成される。制御は９１６に続き、ここで、制御は、インデックスに追加
されることになる更なるタプルが存在するかどうかを決定する。そうである場合、制御は
９２０に移り、そうではない場合、インデックスはポピュレートされており、従って、制
御は終了する。
【０２５５】
９２０では、制御は、タプルが配列表についてのものであるかどうかを決定する。そう
である場合、制御は９２４に移り、そうではない場合、制御は９２８に移る。９２４では
、配列表内に更なる値カラムがある場合、制御は９３２に移る。９３２では、カラム値が
元の取り出されたオブジェクト内に存在する場合、値が、９３６でＡｒｒａｙＩｎｄｅｘ
に追加される。制御は、次いで、９４０に続く。ＶａｌｕｅＩｎｄｅｘがカラムについて
所望される場合、制御は９４４に移り、そうではない場合、制御は９２４に戻る。カラム
値が、９３２で元の取り出されたオブジェクト内に存在しない場合、制御は９２４に戻る
。
【０２５６】
９２８では、タプルがマップ表についてのものである場合、制御は９４８に移り、そう
ではない場合、制御は９５２に移る。９４８では、制御は、更なる値カラムがマップ表内
に残っているかどうかを決定する。そうである場合、制御は９５６に移り、そうではない
場合、制御は９１６に戻る。９５６では、制御は、カラム値が元の取り出されたオブジェ
クト内に存在するかどうかを決定する。そうである場合、制御は９６０に移り、そうでは
ない場合、制御は９４８に戻る。９６０では、値が、ＭａｐＩｎｄｅｘに追加され、制御
は９６４に移る。９６４では、ＶａｌｕｅＩｎｄｅｘがカラムについて所望される場合、
値が、９６８においてＶａｌｕｅＩｎｄｅｘに追加され、いずれの場合においても、制御
は次いで９４８に戻る。
【０２５７】
９５２において、制御は、表内に存在する更なるカラムがあるかどうかを決定する。そ
うである場合、制御は９７２に移り、そうではない場合、制御は９１６に戻る。９７２で
は、制御は、カラム値が元の取り出されたオブジェクト内に存在するかどうかを決定する
。そうである場合、制御は９７６に移り、そうではない場合、制御は９５２に戻る。９７
６では、値がＢｉｇＩｎｄｅｘに追加され、制御は９８０に続く。９８０では、Ｖａｌｕ
ｅＩｎｄｅｘがカラムについて所望される場合、制御は９８４に移り、ここで、値がＶａ
ｌｕｅＩｎｄｅｘに追加され、いずれの場合においても、制御は次いで９５２に戻る。
【０２５８】
図８は、マップを識別するための処理例を示す。制御は、１００４で始まり、ここで、
第１のオブジェクトが選択される。制御は１００８に続き、ここで、オブジェクトが空で
ある場合、１０１２で含有オブジェクトがマップとして指定され、そうではない場合、制
御は１０１６に移る。１０１６では、制御は、上記のような含有オブジェクトの頻度に対
する平均フィールド頻度の割合を決定する。制御は１０２０に続き、ここで、割合が閾値
より下である場合、制御は、マップとして含有オブジェクトを指定するために１０１２に
移り、そうではない場合、制御は１０２４に移る。単なる例として、閾値は、ユーザが調
整可能であり得、および／または観察されたデータに基づいて動的であり得る。種々の実
装において、発見的問題解決法は、関係スキーマが大きくなるにつれて、マップとしてフ
ィールドをより容易に識別するように調整され得る。１０１２では、含有オブジェクトが
マップとして指定され、制御は１０２４に続く。評価するための更なるオブジェクトがあ
る場合、制御は１０２８に移り、ここで、次のオブジェクトが選択され、制御は１００８
に続き、そうではない場合、制御は終了する。
【０２５９】
図９は、関係スキーマを生成するために再帰に頼るｃｒｅａｔｅ＿ｓｃｈｅｍａ関数の
実装例を示す。ｃｒｅａｔｅ＿ｓｃｈｅｍａ関数が呼び出されると、制御は、スキーマ要
素（Ｓｃｈｅｍａ＿Ｅｌｅｍｅｎｔ）を表（Ｃｕｒｒｅｎｔ＿Ｔａｂｌｅ）に組み込む。
この目的のために、制御は１１０４で始まり、ここで、Ｓｃｈｅｍａ＿Ｅｌｅｍｅｎｔが
オブジェクトである場合、制御は１１０８に移り、そうではない場合、制御は１１１２に
移る。１１０８では、オブジェクトが空のオブジェクトである場合、オブジェクトはマッ
プとして処理され、制御は１１１６に移り、そうではない場合、制御は１１２０に続く。
１１２０では、新たな表（Ｎｅｗ＿Ｔａｂｌｅ）がネストされたオブジェクトのために生
成される。１１２４では、結合キー（Ｊｏｉｎ＿Ｋｅｙ）が、Ｃｕｒｒｅｎｔ＿Ｔａｂｌ
ｅに追加され、１１２８では、対応するＪｏｉｎ＿Ｋｅｙが、Ｎｅｗ＿Ｔａｂｌｅに追加
される。制御は次いで１１３２に続き、ここで、ネストされたオブジェクトにおける各フ
ィールドについて、ｃｒｅａｔｅ＿ｓｃｈｅｍａ関数が、フィールドを表に追加するため
に再帰的に呼び出される。制御は、次いで１１３６でｃｒｅａｔｅ＿ｓｃｈｅｍａ関数の
本呼び出しから戻る。
【０２６０】
１１１２では、Ｓｃｈｅｍａ＿Ｅｌｅｍｅｎｔがマップである場合、制御は１１１６に
移り、そうではない場合、制御は１１３８に移る。１１１６では、新たな表（Ｎｅｗ＿Ｔ
ａｂｌｅ）がマップのために生成される。制御は１１４０に続き、ここで、Ｊｏｉｎ＿Ｋ
ｅｙが、Ｃｕｒｒｅｎｔ＿Ｔａｂｌｅに追加され、１１４４では、対応するＪｏｉｎ＿Ｋ
ｅｙが、Ｎｅｗ＿Ｔａｂｌｅに追加される。１１４８では、文字列型を有するキーフィー
ルドが、Ｎｅｗ＿Ｔａｂｌｅに追加される。制御は１１５２に続き、ここで、マップにお
ける各値型について、ｃｒｅａｔｅ＿ｓｃｈｅｍａ関数は、値型をＮｅｗ＿Ｔａｂｌｅに
追加するために再帰的に呼び出される。制御は次いで１１３６に戻る。
【０２６１】
１１３８では、制御は、Ｓｃｈｅｍａ＿Ｅｌｅｍｅｎｔが配列であるかどうかを決定す
る。そうである場合、制御は１１５６に移り、そうではない場合、制御は１１６０に移る
。１１５６では、新たな表（Ｎｅｗ＿Ｔａｂｌｅ）が配列のために生成され、Ｊｏｉｎ＿
Ｋｅｙが、１１６４でＣｕｒｒｅｎｔ＿Ｔａｂｌｅに追加され、対応するＪｏｉｎ＿Ｋｅ
ｙが、１１６８でＮｅｗ＿Ｔａｂｌｅに追加される。１１７２では、整数型を有するイン
デックスフィールドが、Ｎｅｗ＿Ｔａｂｌｅに追加される。制御は１１７６に続き、ここ
で、配列における各アイテム型について、アイテム型をＮｅｗ＿Ｔａｂｌｅに追加するた
めにｃｒｅａｔｅ＿ｓｃｈｅｍａ関数が呼び出される。次いで、制御は１１３６に戻る。
【０２６２】
１１６０では、削除の処理によるＳｃｈｅｍａ＿Ｅｌｅｍｅｎｔは、プリミティブであ
る。プリミティブと同じ名前を有するＣｕｒｒｅｎｔ＿Ｔａｂｌｅに既にフィールドがあ
る場合、制御は１１８０に移り、そうではない場合、制御は１１８４に移る。１１８４で
は、名前フィールドがＣｕｒｒｅｎｔ＿Ｔａｂｌｅに単純に加えられ、制御は１１３６に
戻る。１１８０では、型多様性が存在し、従って、プリミティブと同じ名前を有するＣｕ
ｒｒｅｎｔ＿Ｔａｂｌｅにおける既存のフィールドが、それらの型をフィールド名に添え
るために再び名前を付けられる。制御は１１８８に続き、ここで、新たなフィールドが現
在のプリミティブに基づいて追加され、型はフィールド名に添えられる。次いで、制御は
１１３６に戻る。
【０２６３】
結論
上記は、事実上単なる例示にすぎず、開示、それの用途、または使用に限定されること
を決して意図されない。開示の広範な教示は、様々な形態で実装され得る。従って、この
開示は特定の例を含むが、他の修正が、図面、明細書、および以下の特許請求の範囲の検
討から明らかになるであろうから、開示の真の範囲は、そのように限定されるべきではな
い。本明細書において使用される際、Ａ、Ｂ、およびＣの少なくとも１つという文言は、
非排他的論理ＯＲを使用する、論理（ＡまたはＢまたはＣ）を意味することが解釈される
べきである。方法内の１つ以上のステップは、本開示の原理を変えること無く、異なる順
序で（または同時に）実行され得ることが理解されるべきである。
【０２６４】
以下の定義を含むこの適用において、モジュールという用語は、回路という用語と置換
され得る。モジュールという用語は、特定用途向け集積回路（ＡＳＩＣ）、デジタル、ア
ナログ、もしくはアナログ／デジタル混合ディスクリート回路、デジタル、アナログ、も
しくはアナログ／デジタル混合集積回路、組み合わせ論理回路、フィールドプログラマブ
ルゲートアレイ（ＦＰＧＡ）、コードを実行する（共有、専用、もしくはグループ）プロ
セッサ、プロセッサによって実行されるコードを記憶する（共有、専用、もしくはグルー
プ）メモリ、記載した機能性を提供する他の適切なハードウェア構成要素、またはシステ
ムオンチップにおけるものなどの上記のいくつかもしくは全ての組み合わせの一部である
か、あるいはそれを含むことを言い得る。
【０２６５】
コードという用語は、上記で使用される際、ソフトウェア、ファームウェア、および／
またはマイクロコードを含み得、プログラム、ルーチン、関数、クラス、および／または
オブジェクトのことを言う。共有プロセッサという用語は、多数のモジュールからいくつ
かのまたは全てのコードを実行する単一プロセッサを包含する。グループプロセッサとい
う用語は、追加プロセッサと組み合わせて、１つ以上のモジュールからいくつかのまたは
全てのコードを実行するプロセッサを包含する。共有メモリという用語は、多数のモジュ
ールからいくつかのまたは全てのコードを記憶する単一メモリを包含する。グループメモ
リという用語は、追加メモリと組み合わせて、１つ以上のモジュールからいくつかのまた
は全てのコードを記憶するメモリを包含する。メモリという用語は、コンピュータで読み
取り可能な媒体という用語のサブセットであり得る。コンピュータで読み取り可能な媒体
という用語は、媒体を通って伝搬する一時的な電気および電磁信号を包含せず、従って、
有形および非一時的であると考えられ得る。非一時的な有形のコンピュータで読み取り可
能な媒体の非限定例は、不揮発性メモリ、揮発性メモリ、磁気ストレージ、および光スト
レージを含む。
【０２６６】
この出願に記載された装置および方法は、１つ以上のプロセッサによって実行される１
つ以上のコンピュータプログラムによって部分的にまたは完全に実装され得る。コンピュ
ータプログラムは、少なくとも１つの非一時的な有形のコンピュータで読み取り可能な媒
体上に記憶されるプロセッサで実行可能な命令を含む。コンピュータプログラムはまた、
記憶されたデータを含み得るおよび／または記憶されたデータに頼り得る。
【図１Ａ】
0006617117.tif 000089
【図１Ｂ】
0006617117.tif 000090
【図１Ｃ】
0006617117.tif 000091
【図２Ａ】
0006617117.tif 000092
【図２Ｂ】
0006617117.tif 000093
【図３】
0006617117.tif 000094
【図４】
0006617117.tif 000095
【図５】
0006617117.tif 000096
【図６】
0006617117.tif 000097
【図７】
0006617117.tif 000098
【図８】
0006617117.tif 000099
【図９】
0006617117.tif 000100