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