Unification Algorithm の解説#
graph_unify_loop_0#
初期状態の graph が以下になる。
Fig. 34 graph_unify_loop_0#
graph_unify_loop_0 テーブルの作成方法#
WF 内の +extract_and_merge タスクにて、graph_unify_loop_0 テーブルが作成されるが、どのようにして graph が作成されるのかを見ていこう。
canonical_ids:
- name: person_id
merge_by_keys: [email, td_ssc_id, td_client_id, td_global_id]
merge_iterations: 5
今回、canonical_ids: の設定における merge_by_keys: では、できるだけ普遍な canonical_id が生成されるように、email を最も優先度高くし、その次に td_ssc_id としている。
元のデータに対して、前章と同じのステップで graph_unify_loop_0 テーブルを生成する。
Fig. 35 graph_unify_loop_0 テーブルの作成方法#
前回と異なるのは、1つのテーブルに3つ以上のkeyが存在する site_aaa のペアの作られ方である。この時、1つのレコードに対して leader と follower は
leader:
td_ssc_id
follower:
td_client_id
td_global_id
td_ssc_id
となるため、follower ごとにペアを作るため、3つのレコードに展開されることになる。（上図の緑色の箇所）
follower_ns, leader_ns はそれぞれの id がどの key なのかを特定する。 (今回の例では1なら td_client_id、2なら td_global_id、3なら td_ssc_id, 4なら email となる。) 今回の設定では、ns が [4,3,1,2] の順で優先度が高いことになる。
graph_unify_loop_1#
loop_0 の graph を基に、以下のルールに基づいて leader を更新していく。
Fig. 36 graph_unify_loop_1 における leader の更新方法1#
前回と異なるのは、
ある leader がより優先度の高い leader に接続している場合には、follower に隣接している同じ優先度の leader よりも率先して入れ替わることになる
ところである。
全ての leader に対して、new_leader への置き換え (もちろん自身が最小または最高優先度であれば置き換えられない) を行い、全てをマージしたテーブルが graph_unify_loop_1 テーブルとなる。
Fig. 37 graph_unify_loop_1 における leader の更新方法2#
Fig. 38 graph_unify_loop_1#
以後のループは (前回のループの graph に対して) この繰り返しである。
graph_unify_loop_2#
Fig. 39 graph_unify_loop_2#
graph_unify_loop_3#
3回目のループで収束することになる。
Fig. 40 graph_unify_loop_3#