SIGMOD2009 強会.pptxVIP

Session 7 : Testing and Security 担当：小林　大（NEC） 1 【SIGMOD2009勉強会】 I. Generating Example Data for Dataflow Programs C. Olston, S. Chopra, U. Srivastava (Yahoo! Research) データフロープログラム プログラムをデータのフローとoperator（filter, join等)で定義 Aurora, Dryad, Map-Reduce, Pig,… よいExampleデータが必要 扱うデータが巨大 → 短時間でプログラムチェックするには簡潔で特徴的なExampleが必要 プログラム理解や，新言語の習得にも有用 ナイーブなアプローチでは自動生成困難 （filterでexampleデータが空になる, operatorの特徴をうまく表現できない，など） 定式化 Exampleの良さを, 「Realism」(現実性),「Completeness」(完全性), 「Conciseness」(簡潔性）で定義し，定量化 Exampleデータ生成アルゴリズム データフローを用いたレコードLineageの作成による現実性向上と，完全性基準を利用した冗長レコードの削除 Session 7 : Testing and Security 担当：小林大（NEC） 2 概要: データフロープログラムにおいて，よいExampleデータを生成する問題の定式化とアルゴリズム提案，Apache Pigにおいて実現 I. Generating Example Data for Dataflow Programs問題の概要と定式化 Session 7 : Testing and Security 担当：小林大（NEC） 3 前準備 Equivalence class （同値類） ε0 ={ E1, E2, E3,…, Em} の導入 オペレータを特徴づけるレコード集合Ei の集合 例えばfilterであれば， E1=(フィルタを通る全レコード)， E2=(フィルタを通らない全レコード) 現実性，完全性，簡潔性の３つがExampleデータの目標 現実性 定義：Exampleデータ中のレコードは本物のデータのサブセット，あるいは本物のデータのみから生成可能である必要がある 定量化：Exampleデータ中の本物に含まれるデータの割合 ∈ [0,1] 完全性 定義：オペレータの主要な特徴を表している （例えばfilterであれば，通るレコードと落とすレコードが両方含まれている） 定量化： オペレータごとに満たされている同値類の割合の平均 ∈ [0,1] 簡潔性 定義：Exampleデータは十分少ない必要がある 定量化： 全同値類数 / 全Exampleデータ合計 ∈ [0, 1] (特徴を表すのに多数のexampleが必要なオペレータへの配慮） I. Generating Example Data for Dataflow Programs Exampleデータ生成アルゴリズム Session 7 : Testing and Security 担当：小林大（NEC） 4 x x x x x x x x アルゴリズムのGeneralな説明 → Section 4 Pig Latinにおけるアルゴリズム → Appendix A udf(x): user-defined function（非可逆） PASS 1 PASS 2 PASS 3 PASS 4 INPUT: P={O1, O2, …,On}(オペレータ集合),  D(inputデータ集合) OUTPUT: Example Table {T1, T2,…, Tn} (各オペレータごとのoutput集合） 手順 PASS 1: Downstream Pass（フロー正方向） inputデータから任意のデータをサンプリングし，各オペレータで処理し通してExampleデータ生成 各オペレータの出力レコードと関係する入力レコードは同じLineage Liに属するとする PASS 2: 現実性と完全性を基準に冗長レコード除去 各オペレータごとに全ての同値類を満たす範囲(for 完全性)でExampleデータをLineage単位で削減 PASS 3: Upstream Pass (フロー逆方向） 最終オペレータから逆順に，完全性を満たすようにExampleデータを追加し，可能な範囲でリーフまで伝播． PASS 4: 冗長レコード除去 再び冗長なExampleデータ削除（PASS 3のデータ生成で冗長化したデータの削除） I. Generating Example D