특성 집합 · Logs. hongjun7

특성 집합은 한 주어에 어떤 술어가 나타나는지 기록한다. 책에 저자와 제목이 함께 있다는 식의 동시 출현을 포착한다. 완전한 통계는 제한된 고유 주어의 별 모양 질의를 정확히 세지만, 다중도·상수·조인·압축에는 추가 정보가 필요하다.

카디널리티와 계획

계획기는 카디널리티로 조인 순서와 연산자를 고른다. 백만 행을 열 행으로 줄이는 필터를 일찍 적용하면 중간 작업을 크게 줄일 수 있다.

RDF 그래프는 트리플의 집합이지만 SPARQL은 보통 해 매핑의 다중집합을 반환한다. 전체 바인딩, 투영한 행, 고유 값의 개수는 다르며 SELECT DISTINCT는 세려는 대상을 바꾼다.

특성 집합에 따른 분할

유한 RDF 그래프 \(R\)와 그 주어 집합 \(U_R\)에 대해 다음과 같이 정의한다.

\[C(s)=\{p:\exists o\;(s,p,o)\in R\},\qquad n_C=\vert \{s\in U_R:C(s)=C\}\vert .\]

각 \(C\)에 대응하는 주어 집합은 서로 겹치지 않는다. 술어 집합이 \(P=\{p_1,\ldots,p_k\}\)인 별 모양 질의의 예는 다음과 같다.

PREFIX : <urn:example:>
SELECT DISTINCT ?s WHERE {
  ?s :author ?a .
  ?s :title  ?t .
}

목적어 변수가 서로 다른 새 변수이고 제한이 없으며 필터나 다른 공유 변수도 없으면, 매칭 조건은 정확히 \(P\subseteq C(s)\)다. 따라서

\[N_{\mathrm{distinct}}(P)=\sum_{C\supseteq P}n_C.\]

요청한 술어마다 나가는 간선이 있어야 한다. 집합 포함이 바로 그 조건이며, 주어는 클래스 하나에 속하므로 합에서 한 번 센다. 목적어 상수, 공유 목적어 변수, 임의의 조인, 합친 클래스에는 이 보장이 그대로 적용되지 않는다. Neumann과 Moerkotte, 2011.

바인딩의 다중도

나가는 간선의 다중도는 다음과 같다.

\[m_p(s)=\vert \{o:(s,p,o)\in R\}\vert .\]

목적어 변수가 독립이고 중복을 제거하지 않으면 전체 바인딩 수는

\[N_{\mathrm{bag}}(P)=\sum_{s:P\subseteq C(s)}\prod_{p\in P}m_p(s).\]

이다. 변수마다 나가는 값 하나를 독립적으로 고르므로 곱이 한 주어의 조합 수를 센다. DISTINCT 없는 투영은 그 반복 행을 남긴다.

작은 요약은 총 출현 횟수 \(o_{C,p}=\sum_{s:C(s)=C}m_p(s)\)와 평균 다중도 \(\bar m_{C,p}=o_{C,p}/n_C\)를 저장해 다음을 추정한다.

\[\widehat N_{\mathrm{bag}}(P)=\sum_{C\supseteq P}n_C\prod_{p\in P}\bar m_{C,p}.\]

곱의 평균을 평균의 곱으로 바꾸므로 클래스 내부의 다중도 상관관계를 무시하는 가정이 들어간다.

술어의 존재 여부가 같아도 나가는 값의 개수는 다를 수 있다. 요약은 전자를 정확히 보존하지만, 평균 기반 근사는 후자의 서로 다른 개수를 술어별 평균 하나로 모은다.

상관관계 예제

특성 집합이 {author, title}인 두 주어의 다중도를 \((1,1)\)과 \((3,3)\)이라 하자. 실제 개수는 \(1\cdot1+3\cdot3=10\)다. 평균은 모두 \(2\)여서 추정값은 \(2\cdot2\cdot2=8\)이다. 클래스에서 주어를 균등하게 고르면

\[\mathbb E[m_p m_q] =\mathbb E[m_p]\mathbb E[m_q]+\operatorname{Cov}(m_p,m_q).\]

이다. 빠진 기여분은 \(n_C\operatorname{Cov}(m_p,m_q)\)다. 쌍을 \((1,3)\)과 \((3,1)\)로 바꾸면 실제 개수 \(6\)에 추정값 \(8\)가 되어 오차 방향도 바뀐다. 술어의 존재 여부에 관한 상관관계만으로 다중도 상관관계가 정해지지는 않는다.

같은 술어에 별도 목적어 변수를 쓰면 \(m_p(s)^2\) 같은 거듭제곱이 생긴다. 목적어 변수를 공유하면 동일성 제약이 생긴다. 둘 다 독립적인 두 술어와 다르다.

상수와 공유 변수

?s :author :Ada는 아무 저자가 아니라 Ada를 요구한다. 지시함수

\[b_{p,o}(s)=\mathbf1\{(s,p,o)\in R\}.\]

의 곱을 합하면 고유 주어 수를 정확히 센다. Ada의 전역 빈도만으로는 클래스, 연도, 다른 상수와의 상관관계를 놓칠 수 있다.

\(\Pr(O=o\mid P=p)\) 같은 확률에는 정의된 표본 공간과 양의 조건 확률이 필요하다. 균등 트리플 추출에는 고차수 주어가 더 자주 나오므로 트리플 빈도가 곧 주어 확률은 아니다.

?s :author ?x . ?s :editor ?x는 별도 다중도로 충분하지 않으며 다음을 사용한다.

\[\sum_s \vert \operatorname{Authors}(s)\cap\operatorname{Editors}(s)\vert .\]

술어 동시 출현을 넘어 목적어 집합의 겹침이 필요하다.

압축

가능한 술어가 \(d\)개면 집합은 최대 \(2^d\)개다. 저장 제약 때문에 드문 클래스를 합칠 수 있다. {author}를 {author, title} 안에서 세면 두 술어를 요구하는 별에 거짓 매치가 생긴다. 실제 공동 클래스를 단일 술어 요약들로 나누면 동시 출현을 잃는다.

어느 오차 방향도 항상 무해하다고 볼 수 없다. 과대 추정은 조인 순서·메모리 예약·연산자를 바꿀 수 있고, 과소 추정은 큰 중간 결과에 중첩 루프를 고르게 할 수 있다. 개수가 정확한지·합쳤는지·표본인지·오래된 값인지 구분해야 한다. 첫 title 간선의 추가나 마지막 간선의 삭제는 주어를 다른 클래스로 옮기므로 술어 총계만으로 분할을 유지할 수 없다.

여러 별의 조인

관계형 입력 \(R_1,\ldots,R_m\)와 조인 조건 \(e\)에 대한 명시적 독립 근사는 다음 형태다.

\[\widehat N=\left(\prod_{i=1}^{m}\vert R_i\vert \right) \left(\prod_{e}\widehat{\operatorname{sel}}(e)\right).\]

선택도는 곱한다. 이 식은 호환되는 표본 공간과 독립성을 가정하며 상관된 조인의 공식은 아니다. 상관된 술어 묶음의 요약은 해당 인자들을 묶어서 대체한다. 겹치는 요약은 상관관계나 모집단을 중복 계산할 위험이 있다.

논리적으로 동등한 질의의 실제 카디널리티는 물리 순서와 무관하다. 같은 논리 부분식의 추정값을 재사용하면 물리 계획 비교 중 별도의 근사 호출이 서로 다른 값을 내는 일을 피한다.

평가

실제 개수와 추정값이 양수일 때

\[q\text{-error}=\max\left(\frac{\widehat N}{N},\frac{N}{\widehat N}\right).\]

이다. 실제 \(100\)에 추정값 \(80\)이면 q-error는 \(1.25\)다. 0을 1로 바꾸면 거짓 빈 결과 예측을 숨기므로 별도 정책이 필요하다. 빈 질의 검출, q-error 중앙값과 꼬리, 구축·저장 비용, 추정 및 최종 질의 지연 시간을 함께 측정한다.

같은 스냅샷에서 완전한 특성 집합, 예산 제한 버전, 표본 추출, 기본 통계를 비교할 수 있다. 별·사이클·상수·반복 술어·편향·갱신에 따른 변화를 포함한다. 복잡한 질의의 표본 추출은 단순한 별 요약 밖의 연산자를 다룬다.

고차 상관관계

한 클래스의 세 다중도 \(X,Y,Z\)를 평균 주변에서 전개하면

\[\begin{aligned} \mathbb E[XYZ] ={}&\mu_X\mu_Y\mu_Z +\mu_X\operatorname{Cov}(Y,Z) +\mu_Y\operatorname{Cov}(X,Z)\\ &+\mu_Z\operatorname{Cov}(X,Y) +\mathbb E[(X-\mu_X)(Y-\mu_Y)(Z-\mu_Z)]. \end{aligned}\]

이다. 평균과 쌍별 공분산만으로는 중심화한 3차 항이 빠진다. 같은 가중치의 네 주어가 다중도 \((1,1,1),(1,2,2),(2,1,2),(2,2,1)\)를 가지면 모두 양수이므로 특성 집합 하나를 공유할 수 있다. 각 쌍은 독립이고 평균은 \(3/2\), 공분산은 0이다.

정확한 개수 \(1+4+4+4=13\)와 평균의 곱 추정 \(4(3/2)^3=13.5\)은 다르다. 곱의 평균 \(13/4\)과 평균의 곱 \(27/8\)의 차이는 \(-1/8\)다. 쌍별 독립은 상호 독립을 보장하지 않으며, 주변 통계를 늘려도 결합분포가 복원되는 것은 아니다.

동등 조인 추정

두 관계에서 키 \(v\)의 빈도를 \(f_R(v)\)와 \(f_S(v)\)라 하자. 실제 다중집합 조인 크기는

\[N_{R\Join S}=\sum_v f_R(v)f_S(v).\]

이다. 크기 \(V_R,V_S\)인 영역 \(D_R,D_S\) 안에서 키가 균등하고 작은 영역이 포함되면 공통 키는 \(\min(V_R,V_S)\)개다. 따라서

\[\widehat N= \min(V_R,V_S)\frac{\vert R\vert }{V_R}\frac{\vert S\vert }{V_S} =\frac{\vert R\vert \vert S\vert }{\max(V_R,V_S)}.\]

이다. 고유 값 수뿐 아니라 균등성과 포함 관계가 필요하다. 일부만 겹치면 공통 키 인자가 달라지고, 편향되면 빈도 곱의 합이 필요하다. 키와 상관된 필터는 추가 조건부 분포를 만든다.

열 행인 두 입력에 공통 키 둘이 같은 빈도로 나오면 \(2\cdot5\cdot5=50\)행으로 조인한다. 빈도가 각각 아홉/하나와 하나/아홉이면 \(9\cdot1+1\cdot9=18\)행이다. 여전히 열 행과 고유 키 둘이므로 균등 추정은 50에 머물며 편향을 놓친다.

유지

전체 구축은 주어별 고유 술어를 모아 같은 집합의 개수를 센다. 기대 선형 작업량에는 적절한 해싱과 비싼 정규형 계산을 반복하지 않는 표현이 필요하다. 정렬의 비용은 다르다. 메모리는 주어 작업 상태, 키, 클래스별 개수, 다중도 통계도 포함한다.

주어별 술어 개수로 첫·마지막 간선과 추가 간선을 구별한다. 두 번째 간선은 다중도만 바꾸고, 마지막 간선의 제거는 집합과 클래스를 바꾼다. 클래스 평균에는 이동과 남은 다중도가 반영되어야 한다. 일회용 데이터의 재구축을 증분 유지의 정답 기준으로 쓸 수 있다.

예산 제한 요약은 어떤 고유 주어의 별 질의에서 개수가 여전히 정확한지 드러낼 수 있다. 증명된 0을 표본의 0이나 오래된 추정과 구별하는 근거다. q-error가 줄어도 작은 오차가 연산자 임계값을 잘못 넘으면 실행 비용이 늘 수 있다. 계획과 지연 시간도 평가해야 하며, 과거 저장·벤치마크 수치는 RDF의 보편적 성질이 아니다.

정확성은 특성 집합이라는 이름만으로 정해지지 않는다. 질의 모양과 유지한 통계에 달려 있으며, 압축하거나 질의 조건을 추가하면 같은 보장을 유지하지 못할 수 있다.