タプルID伝播（Tuple ID Propagation）とは？マルチリレーショナル分類における仮想結合の仕組みを解説

タプルID伝播の基本概念

タプルID伝播（Tuple ID Propagation）は、仮想結合を実現するための手法であり、マルチリレーショナル分類の効率を大幅に向上させます。リレーション同士を物理的に結合する代わりに、対象リレーションのタプルIDを非対象リレーションのタプルに接続することで、複数のリレーションを仮想的に組み合わせるのが特徴です。

タプルID伝播の利点

この手法では、実際に物理結合を実行した場合と同じように述語を計算できます。IDは2つのリレーション間で容易に伝播できるため、必要なデータ転送量とストレージ容量がわずかで済み、柔軟性と効率性に優れています。その結果、複数のリレーションにまたがる述語を、最小限の冗長計算で算出することが可能になります。

伝播に制約が必要な理由

タプルID伝播は、特定の制約のもとで適用しなければなりません。以下のようなケースでは、伝播がかえって逆効果になる可能性があります。

• 大きなファンアウト（fan-out）を経由した伝播
• 長く弱いリンクを経由した伝播

大きなファンアウトによる伝播

IDをあるリレーションRへ伝播した後、R内のすべてのタプルが何らかの対象タプルと結合しており、かつすべての対象タプルもR内のいくつかのタプルと結合していることが判明するケースです。この結合には選択性がないため、Rと対象リレーションとの間の意味的な関連性は非常に弱くなります。例えば、「出生国」リンクを介した人同士のID伝播は、有益な結果をもたらしません。

長い弱いリンクによる伝播

伝播が長い接続を通じて行われる場合も問題となります。例えば、学生と「その学生の車を購入した販売店のペット」を結ぶような接続では、有用な情報は得られません。効率性と確実性の観点から、この種の接続を経由する伝播は避けるべきとされています。

CrossMineにおけるタプルID伝播の活用

CrossMineは、マルチリレーショナル分類においてタプルID伝播を利用する代表的な手法です。ID伝播によるデータを効果的に統合するため、CrossMineは複合述語をルールの構成要素として採用しています。複合述語pは、次の2つの部分から構成されます。

prop-path（伝播パス）

IDの伝播方法を表します。例えば、「Loan.account_ID → Account.account_ID」というパスは、account_IDを使ってLoanからAccountへIDを伝播することを意味します。ID伝播が含まれない場合は、prop-pathはnullになります。

制約（Constraint）

IDが伝播される先のリレーションに対する条件を表す述語です。カテゴリ型・数値型のどちらでも指定できます。

CrossMineの分類器構築プロセス

CrossMineは、複数のルールからなる分類器を構築します。各ルールは、複合述語のリストとクラスラベルを含みます。CrossMineはFOILと同様の逐次被覆（sequential covering）アルゴリズムを採用しており、ルールを1つずつ構築していきます。ルールrが生成されると、rを満たすすべての陽性の対象タプルがデータセットから削除されます。

CrossMineは最良の複合述語を繰り返し探索し、停止基準が満たされるまで現在のルールに追加し続けます。現在のルールに出現するリレーションは「アクティブ」と呼ばれます。次の最良述語を探索する前に、各アクティブリレーションは、そのタプルごとに伝播済みIDの集合（IDset）を保持している必要があります。