역확률 가중치는 모든 답을 열거하지 않고 질의의 답 수를 추정한다. 결과를 표본으로 뽑아 선택 확률의 역수를 가중치로 준다. 정확성은 그 결과가 무엇을 나타내는지에 달려 있다. 유도, 투영한 답, 고유 답은 서로 다른 모집단이다.
집합과 다중집합
고정된 유한 데이터베이스 \(I\)의 질의 \(Q\)에서 바인딩 \(\mu\)의 다중도를 \(m_Q(\mu)\)라 하자. 집합 카디널리티는 \(\vert \{\mu:m_Q(\mu)>0\}\vert\), 다중집합 카디널리티는
\[N_Q=\sum_\mu m_Q(\mu).\]이다. 투영과 합집합을 거치면 둘이 달라진다. Hu와 Motik은 논리곱 무작위 보행을 넘어 합성적인 평가와 가중 표본 추출로 복잡한 그래프 질의를 다룬다. 추출 구성은 각 연산자의 의미론을 구현해야 한다. Hu와 Motik, TODS 2024.
역확률
유한 집합 \(A\)에서 \(a\)를 뽑으며, 모든 \(a\in A\)의 확률 \(q(a)>0\)을 안다고 하자. 다음과 같이 정의하면
\[X=\frac1{q(a)}.\]기댓값은
\[\mathbb E[X]=\sum_{a\in A}q(a)\frac1{q(a)}=\vert A\vert .\]이다. 이 복원 추정기는 Hansen–Hurwitz 추출과 연결된다. Horvitz–Thompson은 부분집합 \(S\)를 추출하고 각 원소의 포함 확률 \(\pi_a=\Pr(a\in S)\)을 사용한다.
\[\widehat N_{\mathrm{HT}}=\sum_{a\in S}\frac1{\pi_a}.\]독립 복원 추출 \(n\)회 뒤에는 \(\pi_a=1-(1-q(a))^n\)이다. 중복을 없애면서 \(1/q(a)\)를 계속 쓰면 일반적으로 편향된다. 포함 확률과 회차별 추출 확률이 다르기 때문이다.
분할 \(A=A_1\uplus\cdots\uplus A_k\)에서 \(i\)를 균등하게 고르면 \(X=k\vert A_i\vert\)의 기댓값은 \(\vert A\vert\)다. 부분집합이 겹치면 보정 없이는 같은 답을 여러 번 센다.
무작위 보행 조인
\(R(x,y)\Join S(y,z)\)에서 먼저 \(R\)의 튜플을 균등하게 뽑고, 그 \(y\)에 매칭되는 \(S\)의 튜플을 균등하게 뽑는다. 차수가 \(d(y)>0\)이면 경로 확률은
\[q(r,s)=\frac1{\vert R\vert }\frac1{d(y)}.\]이다. 성공한 바인딩에는 \(X=\vert R\vert d(y)\), 실패한 보행에는 0을 준다. 성공 경로마다 기댓값에 1을 기여한다. 실패를 남겨야 무조건부 기댓값을 보존하며, 성공할 때까지 재시도하면 분포가 바뀌어 재정규화가 필요하다.
시작 튜플 두 개
\(R\)의 두 튜플이 각각 \(S\)의 한 튜플과 세 튜플에 조인한다고 하자. 완전한 바인딩 네 개에서 확률 \(1/2\)로 \(X=2\), 확률 \(1/2\)로 \(X=6\)를 얻는다.
\[\mathbb E[X]=4,\qquad\operatorname{Var}(X)=4.\]독립 보행 \(n\)회의 평균 분산은 \(4/n\)다. 이 작은 계산이 모든 질의의 분산을 제한하지는 않는다. 드문 고차수 경로가 가중치를 지배할 수 있다.
긴 보행은 조건부 확률을 곱한다. 이미 바인딩된 사이클을 닫는 단계는 새 무작위 선택이 아니라 존재 검사일 수 있다. 한 투영 답에 여러 경로가 닿으면 별도로 계산해야 한다.
DISTINCT와 UNION
다음 질의를 보자.
PREFIX : <urn:example:>
SELECT DISTINCT ?x WHERE { ?x :knows ?y }
이웃이 100명이면 유도는 100개지만 고유 답은 하나다. 이웃이 한 명이면 유도는 하나여도 고유 기여는 같다. 유도 수의 불편 추정이 고유 주어 수의 불편 추정까지 보장하지는 않는다.
답 \(x\)의 유도를 \(W_x\)라 하자. 경로 확률 \(q(w)\)에서 답 \(x\)의 확률은
\[q_A(x)=\sum_{w\in W_x}q(w).\]이다. 이를 알고 양수일 때 가중치 \(1/q_A(x)\)으로 고유 답을 올바르게 센다. 다만 그 합을 계산하는 데 상당한 질의 작업이 필요할 수 있다. 나중에 set()을 적용해도 이 확률을 얻지는 못한다.
다중집합 UNION은 \(m_{A\cup B}(x)=m_A(x)+m_B(x)\)로 다중도를 더한다. 고유 합집합은 \(\vert A\cup B\vert =\vert A\vert +\vert B\vert -\vert A\cap B\vert\)를 따른다. 분기 확률과 겹침을 고려해야 하며 분기별 개수의 평균은 합집합 크기가 아니다.
필터와 맥락
거부된 바인딩도 확률 계산이 과정과 맞으면 기여도 0으로 남길 수 있다. 숨은 재시도는 받아들인 분포를 바꾼다.
SPARQL MINUS는 공유 변수 영역에 따라 호환되는 부분 매핑을 제거하며, 서로소 영역을 특별히 처리한다. 완전한 튜플의 일반 차집합과 항상 같지는 않다. SPARQL 1.1.
측면 정보 전달은 다른 곳에서 얻은 바인딩으로 부분 질의를 평가한다. 모집단을 줄이고 선택 확률도 바꿀 수 있다. 메모이제이션 키에는 결과에 영향을 주는 모든 바인딩과 의미론적 맥락이 들어가야 한다.
강일치성
독립이고 같은 분포를 따르는(iid) \(X_1,X_2,\ldots\)이 \(\mathbb E\vert X_1\vert <\infty\)와 \(\mathbb E X_1=N\)을 만족하면 강한 대수의 법칙으로
\[\overline X_n=\frac1n\sum_{i=1}^{n}X_i \xrightarrow[n\to\infty]{\mathrm{a.s.}}N.\]를 얻는다. 표본이 한없이 늘 때 확률 1로 수렴한다는 뜻이며, 천 개면 충분하다는 보장은 아니다. 유한 실행은 0을 반환할 수 있고 심하게 치우친 분포는 신뢰구간을 불안정하게 한다.
고정된 유한 표본 공간의 양의 확률은 역확률 가중치를 유계로 만들어 적분 가능성을 보장한다. 그 상한이 너무 크면 유한 예산의 집중 결과는 쓸모없을 수 있다. 이전 표본으로 확률을 바꾸면 iid 증명을 그대로 쓰지 않고 적응형 논증이 필요하다.
불확실성과 중단
분산이 유한한 iid 추출에서는
\[s_n^2=\frac1{n-1}\sum_i(X_i-\overline X_n)^2, \qquad\widehat{\operatorname{SE}}(\overline X_n)=\frac{s_n}{\sqrt n}.\]이다. 표본이 충분하고 분포가 적절하면 정규 근사가 유용하다. 대부분의 보행이 실패하고 드문 가중치가 지배하면 취약하다. 표본과 관측 분산이 모두 0이어도 답이 비었다는 증명은 아니다.
고정 표본 구간이 처음 좁아지는 순간 중단하면 명목 포함 확률을 잃을 수 있다. 정당화된 순차 절차나 독립 평가 예산이 필요하다. 지지집합, 실패, 실제 예산, 두꺼운 꼬리도 해석에 영향을 준다.
같은 부분식의 계획들이 다른 추정값을 내면 분산·확률 오류·의미론 변경을 구별해야 한다. 캐시에는 논리 부분식, 맥락 바인딩, 데이터베이스 리비전, 시드가 필요하다.
계획 비용
옵티마이저는 수백 개의 부분 질의 추정을 요청할 수 있다. 전체 지연 시간은
\[T_{\mathrm{total}}=T_{\mathrm{statistics}}+T_{\mathrm{planning}}+T_{\mathrm{execution}}.\]이다. 더 정확한 추정은 실행 시간 절감이 추가 계획 비용을 정당화할 때 유익하다. 재사용, 인덱스 제한 스캔, 예비 표본, 순서 선택은 올바른 확률 계산을 유지하면서 비용을 줄일 수 있다.
요약 및 단순 추출과 비교할 때 q-error, 거짓 0 비율, 계획 시간, 최종 질의 시간, 최악의 저하는 다른 절충을 보여 준다. 질의 모양·답 수·분포의 치우침을 나누면 평균에 가린 치명적인 일부를 드러낼 수 있다.
분산과 제안 분포
크기 \(N\)의 유한 답 집합 \(A\)과 양의 확률 \(q(a)\)에 대해
\[\mathbb E[X^2]=\sum_{a\in A}\frac1{q(a)}, \qquad \operatorname{Var}(X)=\sum_{a\in A}\frac1{q(a)}-N^2.\]이다. \(\sqrt{q(a)}\)와 \(1/\sqrt{q(a)}\)에 코시–슈바르츠를 적용하면
\[N^2\le\left(\sum_aq(a)\right)\left(\sum_a\frac1{q(a)}\right).\]이다. \(q(a)=1/N\)에서 등호가 성립하며, 매번 \(X=N\)이어서 분산이 사라진다. 그러나 균등 추출과 \(1/N\)을 아는 데 질의만큼 비용이 들 수 있다.
두 튜플 예에서 시작 튜플을 조인 차수에 비례해 뽑고 이웃을 균등하게 뽑으면 네 경로의 확률과 가중치 4가 같아진다. 차수와 총합을 먼저 계산해야 하므로 분산 감소에는 구축 비용이 따른다.
실패 확률 질량이 있으면 성공 경로 확률을 \(q(a)\), 실패 가중치를 0으로 둔다. 2차 모멘트는 \(\sum_a1/q(a)\)지만 \(\sum_aq(a)\le1\)여서 드문 성공이 분산을 키운다. 확률이 0인 답은 표본을 늘려도 기댓값에 들어오지 않는다.
유한 오차 상한
성공 확률이 \(q_{\min}>0\) 이상이고 실패 가중치가 0이면 \(0\le X\le M=1/q_{\min}\)이다. 독립 추출은 Hoeffding 상한
\[\Pr(\vert \overline X_n-N\vert \ge\epsilon) \le2\exp\left(-\frac{2n\epsilon^2}{M^2}\right).\]을 만족한다. 오차 상한을 넘을 확률을 \(\delta\) 이하로 만드는 충분조건은
\[n\ge\frac{M^2}{2\epsilon^2}\log\frac2\delta.\]이다. 절대 오차를 제한하는 식이다. 상대 오차의 \(\epsilon=\eta N\)에는 미지의 \(N\)이나 그 하한이 필요하다. 유한한 \(M\)도 매우 크면 예산이 비현실적이므로 강일치성만으로 실용적인 지연 시간을 보장하지 못한다.
과거 정보의 적응형 제안 \(q_t\)도 정확한 확률 계산과 전체 지지를 유지하면 \(\mathbb E[X_t\mid\mathcal F_{t-1}]=N\)를 만족할 수 있다. 독립성이 아니라 마팅게일 성질이다. 집중과 거의 확실한 수렴에는 모멘트나 유계성 가정을 만족하는 마팅게일 정리가 필요하다.
고유 답의 가중치
A의 이웃은 100명, B는 한 명이다. 간선 101개를 균등하게 뽑으면 \(q_A(A)=100/101\)와 \(q_A(B)=1/101\)이다. 고유 답 가중치 \(101/100\)과 \(101\)의 기댓값은
\[\frac{100}{101}\frac{101}{100}+\frac1{101}101=2.\]이다. 간선 경로 가중치 101은 기댓값 101로 유도를 센다. 유한 묶음의 중복 제거는 관측 주어 수를 세며, 최대 둘이고 기댓값은 표본 수에 달려 있다. 서로 다른 세 통계량이다.
부분집합 기반 Horvitz–Thompson에서 쌍별 포함 확률 \(\pi_{ab}=\Pr(a,b\in S)\)은
\[\operatorname{Var}(\widehat N_{\mathrm{HT}}) =\sum_{a,b}\frac{\pi_{ab}-\pi_a\pi_b}{\pi_a\pi_b}, \qquad\pi_{aa}=\pi_a.\]을 준다. \(\sum_a\mathbf1\{a\in S\}/\pi_a\)의 분산을 전개한 식이다. 비복원 포함 지시변수는 의존하므로, 독립 가정은 기댓값이 불편해도 불확실성을 잘못 계산할 수 있다.
복잡한 질의의 추출기는 결과, 유도-답 사상, 실패, 확률을 명시해야 한다. 이 원리만으로 2024년 논문의 모든 연산자를 구현한 것은 아니며, 그 보장에는 해당 구성과 가정이 필요하다.