튜플 ID 전파의 기본 개념
튜플 ID 전파(Tuple ID Propagation)는 가상 조인(virtual join)을 구현하는 방식으로, 다중 관계 분류(multirelational classification)의 효율성을 크게 향상시키는 핵심 기술입니다. 물리적으로 관계(relation)를 직접 조인하지 않고도, 대상 튜플(target tuple)의 ID를 비대상 관계(non-target relation)의 튜플과 연결함으로써 두 관계를 가상으로 결합할 수 있습니다.
이 방식에서는 마치 실제 물리적 조인을 수행한 것처럼 술어(predicate)를 계산할 수 있습니다. 튜플 ID 전파가 유연하고 효율적인 이유는, 두 관계 사이에서 단순히 ID만 전파하면 되기 때문에 필요한 데이터 전송량이 적고 추가 저장 공간도 크게 요구되지 않기 때문입니다. 이를 통해 여러 관계에 걸친 술어를 최소한의 중복 연산만으로 계산할 수 있습니다.
튜플 ID 전파가 역효과를 낼 수 있는 두 가지 경우
튜플 ID 전파는 반드시 특정 제약 조건을 적용해야 합니다. 무분별하게 전파를 수행하면 오히려 성능이 저하될 수 있는데, 대표적으로 다음 두 가지 경우가 해당됩니다.
- 큰 팬아웃(fan-out)을 통한 전파
- 길고 약한 링크(long, weak links)를 통한 전파
첫 번째 경우는 ID를 관계 R로 전파한 후, R의 모든 튜플이 어떤 대상 튜플과 조인되고, 동시에 모든 대상 튜플도 R의 어떤 튜플과 조인되는 상황에서 발생합니다. 이런 연결은 선택적(selective)이지 않기 때문에 R과 대상 관계 사이의 의미적 연결이 매우 약합니다. 예를 들어 출생 국가(birth-country) 링크를 통해 사람들 간에 ID를 전파하는 것은 생산적이지 못합니다.
두 번째 경우는 전파가 지나치게 긴 연결 경로를 거치는 상황입니다. 예컨대 학생과 그 학생의 자동차 딜러가 키우는 애완동물을 연결하는 것처럼 의미 없는 긴 경로는 생산적이지 않습니다. 효율성과 신뢰성 측면에서 이러한 경로를 통한 전파는 권장되지 않습니다.
CrossMine과 복합 술어(Complex Predicate)
CrossMine은 다중 관계 분류를 위해 튜플 ID 전파를 활용하는 대표적인 방법입니다. CrossMine은 ID 전파의 데이터를 더 효과적으로 결합하기 위해 복합 술어(complex predicate)를 규칙(rule)의 구성 요소로 사용합니다. 하나의 복합 술어 p는 다음 두 부분으로 구성됩니다.
prop-path(전파 경로)
ID를 어떻게 전파할지 나타냅니다. 예를 들어 "Loan.account_ID → Account.account_ID"라는 경로는 account_ID를 사용하여 Loan 관계에서 Account 관계로 ID를 전파한다는 의미입니다. ID 전파가 포함되지 않는 경우 prop-path는 null이 됩니다.
제약 조건(Constraint)
ID가 전파되는 대상 관계에 대한 제약을 나타내는 술어입니다. 범주형(categorical)일 수도 있고 수치형(numerical)일 수도 있습니다.
CrossMine의 분류기 구축 과정
CrossMine은 일련의 규칙들로 구성된 분류기를 생성합니다. 각 규칙은 복합 술어 목록과 클래스 레이블(class label)을 포함합니다. CrossMine은 FOIL과 같은 순차적 커버링(sequential covering) 알고리즘으로, 한 번에 하나씩 규칙을 만들어 나갑니다. 규칙 r이 생성되면 r을 만족하는 모든 양성(positive) 대상 튜플이 데이터 집합에서 제거됩니다.
CrossMine은 최선의 복합 술어를 탐색하여 현재 규칙에 추가하는 과정을 반복하다가, 중단 기준(stop criterion)이 충족되면 종료합니다. 현재 규칙에 등장하는 관계를 활성 관계(active relation)라고 하며, 다음 최적 술어를 검색하기 전에 각 활성 관계는 자신의 모든 튜플에 대해 전파된 ID들의 집합(IDset)을 보유하고 있어야 합니다.