owl:sameAs는 서로 다른 이름이 한 개체를 가리킨다고 선언한다. 동등한 이름을 모든 사실에 대입하면 결과가 크게 늘어난다. 재작성은 동등성 폐포를 대표로 압축하면서 규칙의 귀결과 질의 답의 다중도를 보존하는 방법이다.
대표
RDF 그래프는 트리플 \((s,p,o)\)을 담는다. 동등성 사실이 만드는 동치 관계를 \(a\sim b\)라 하면, 반사성·대칭성·추이성 폐포로 동치류를 정의한다.
\[[a]=\{b:b\sim a\}.\]대표 사상 \(\rho\)는 다음을 만족한다.
\[a\sim b\iff\rho(a)=\rho(b),\qquad\rho(\rho(a))=\rho(a).\]두 번째 조건은 멱등성이다. \(\rho\)를 트리플 성분과 규칙 상수에 적용하면 동등한 이름을 대표 하나로 바꿀 수 있다. :US, :USA, :America가 같다면 (:person, :livesIn, :US)를 한 번만 저장한다.
대표는 저장 방식의 선택이다. 외부 어휘에는 모든 이름이 남아 있다. 몫 표현은 저장할 트리플을 바꾸지만, 펼친 그래프에서 드러나는 이름을 없애지 않는다.
owl:sameAs는 유사성과 달리 동등한 개체의 치환을 허용한다. 술어 위치의 치환은 선택한 RDF 기반 규칙에 달려 있다. 여기서는 재작성 논문과 OWL 2 RL/RDF를 따른다. 구문을 검사하는 RDF 항 연산은 별도로 처리해야 한다. 동등성을 포함한 규칙 구체화에 관한 설명이지, 임의의 OWL 추론을 union–find로 해결한다는 뜻은 아니다.
펼친 결과의 크기
이름 \(k\)개인 동치류에는 자기 쌍을 포함한 순서 있는 동등성 쌍이 \(k^2\)개 있다. 트리플의 주어·술어·목적어 동치류 크기가 \(k_s,k_p,k_o\)이면 치환으로 최대
\[k_s k_p k_o\]개의 구문적 트리플을 얻는다. 규칙 실행 횟수는 중복 억제, 실행 순서, 규칙 집합에도 달려 있다.
:alice와 :a가 한 동치류, 세 나라 이름이 다른 동치류에 있으면 정규화한 livesIn 사실 하나가 \(2\cdot1\cdot3=6\)개 트리플을 나타낸다. 몫 저장소는 그 사실과 구성원 정보를 저장하지만 외부 답에는 여섯 조합이 모두 나타날 수 있다.
경로 압축과 랭크 기준 합치기를 쓰면 원소 \(n\)개에 대한 union/find \(m\)회의 상각 비용은 \(O(m\alpha(n))\)이다. 사실 재작성, 인덱스 갱신, 규칙 재평가는 제외한 비용이며, 이 작업들이 추론 시간을 지배할 수 있다.
규칙 재작성
규칙은 새 동등성을 유도할 수 있다.
sameAs(x, :USA) :- presidentOf(:person, x).
leader(x) :- presidentOf(x, :USA).
presidentOf(:person, :US)는 sameAs(:US, :USA)를 유도한다. :US가 대표가 되면 두 번째 규칙의 :USA도 재작성이나 동적 정규화로 :US가 되어야 한다. 그렇지 않으면 사실 재작성 때문에 유효한 매치가 사라진다.
새 동등성이 매치를 만들고 그 매치가 다시 동등성을 유도하므로, 정규화와 구체화는 함께 진행된다. 필요한 동치 관계를 모두 알고 있고 프로그램으로 바뀌지 않을 때만 일회성 전처리로 충분하다.
정확성 불변식
입력 사실을 \(E\), 선택한 동등성 규칙을 포함하는 유한하고 안전하며 함수 기호 없는 양의 프로그램을 \(P\)라 하자. 구체화는 최소 고정점이다. 압축 엔진은 정규화한 사실 \(T\)와 대표 \(\rho\)를 유지하며 치환을 다음과 같이 펼친다.
\[\operatorname{expand}_\rho(T) =\{(s,p,o): (\rho(s),\rho(p),\rho(o))\in T\}.\]엔진은 명시적 구체화의 관련 귀결을 복원해야 한다. 동등성 사실과 비일관성 처리에는 선택한 엔진의 규약도 적용된다.
합치기 직후에는 사실과 상수에 낡은 대표가 함께 남을 수 있다. 대기 중인 재작성이 끝날 때까지 매칭은 이 버전들과 현재의 정규화한 상태를 구별해야 한다.
합치기 뒤의 유효한 사실, 규칙 상수, 매칭 인덱스는 결국 현재 대표를 사용해야 한다. 바뀐 규칙은 기존 사실에 다시 적용하고, 새로 가능해진 모든 규칙 인스턴스가 결국 실행되어야 한다. 건전성은 정규화한 유도가 원래 귀결로 펼쳐짐을 요구한다. 완전성은 명시적 유도에 대한 귀납으로 보인다. 표현된 전제, 정규화한 상수, 공정한 재평가를 사용한다.
유한 영역은 기초 사실 수를 제한하며, 합치기로 동치류 수가 줄어드는 횟수는 최대 \(n-1\)회다. 유한한 규칙 처리를 공정하게 수행하면 종료한다. 병렬 구현의 경쟁 상태가 없다는 증명은 아니다.
병렬 평가
Motik 등은 사실 처리에 변경된 자원과 재작성된 규칙의 큐를 결합한다. 낡은 사실을 지우지 않고 표시할 수 있으므로 매칭에서 제외해야 한다. 합치기는 대표, 출현 인덱스, 대기 작업을 조율한다. 이 동기화 방식이 모든 동등성 추론기의 락 없는 동작을 보장하지는 않는다. 재작성 알고리즘.
take pending fact or equality update
normalize it with the current representative map
if it merges classes:
enqueue affected facts and affected rule constants
otherwise:
apply matching rules and enqueue new facts
repeat until all work, including rule reindexing, is complete
종료하려면 큐가 비어 있을 뿐 아니라 실행 중인 작업자나 지연 갱신이 새 작업을 추가할 가능성도 없어야 한다. 삭제는 별도 문제다. 기존 동치류를 다시 나눠야 할 수 있다.
SPARQL 다중도
정규화한 livesIn 사실의 주어 이름이 둘, 목적어 이름이 셋이라고 하자.
PREFIX : <urn:example:>
SELECT ?s WHERE { ?s :livesIn ?country }
펼친 그래프는 주어마다 세 번씩, 여섯 행을 반환한다. 정규화한 매치를 먼저 투영하고 주어만 펼치면 두 행이 되어 숨겨진 변수의 다중도를 잃는다.
각 변수가 동치류 구성원을 독립적으로 고른다면 정규화한 바인딩 \(\nu\)의 확장 다중도는
\[\prod_{x\in\operatorname{vars}(Q)}\vert [\nu(x)]\vert .\]이다. 반복 변수, 상수, 필터, 조인, 앞선 확장은 선택을 제한한다. SELECT DISTINCT ?s는 고유 주어 둘만 반환한다.
구문을 검사하는 내장 함수는 펼친 뒤 평가해야 한다.
PREFIX : <urn:example:>
SELECT ?label WHERE {
?s :livesIn :US .
BIND(STR(?s) AS ?label)
}
같은 개체의 이름이어도 STR(:alice)와 STR(:a)는 다르다. 나중에 문자열을 정규화해도 잃은 구별을 복원하지 못한다. SPARQL 의미론.
비일관성
동등성 폐포가 서로 다르다고 선언된 자원을 동일시할 수 있다. 엔진은 고전 논리의 폭발 원리에 따른 모든 귀결 대신 모순을 보고할 수 있으므로, 비일관적 데이터의 질의 동작을 따로 정의해야 한다.
재작성은 치환이 폐포를 크게 늘릴 때 유용하다. 정규화한 사실 수, 펼친 답의 수, 경과 시간, 메모리, 갱신 비용으로 효과를 평가하며 투영과 필터 동작도 포함한다. 동등성이 적은 그래프에서 과거와 같은 속도 향상이 보장되지는 않는다.
최소 고정점
유한한 기초 항의 전체 집합에서 팽창적인 즉시 귀결 연산자는 다음과 같다.
\[T_P(S)=E\cup S\cup\{h\sigma: (h\leftarrow b_1,\ldots,b_m)\in P, \;b_i\sigma\in S\text{ for all }i\}.\]\(\sigma\)는 변수를 영역의 항으로 치환한다. 안전성, 함수 기호가 없다는 조건, 유한 영역이 기초화를 유한하게 만든다. 양의 규칙은 단조적이다. \(S\subseteq S'\)이면 \(S\)에서 적용 가능한 인스턴스가 \(S'\)에서도 적용된다. \(E\)에서 시작한 열 \(S_{k+1}=T_P(S_k)\)는 \(E\)를 포함하는 최소 고정점에서 안정된다.
재작성은 이 과정의 변하는 몫 표현을 저장한다. 두 상수를 합치면 일반 사실을 넣지 않아도 실패하던 조인이 성공할 수 있다. 규칙과 인덱스 재평가는 고정된 정규화 프로그램을 가정하지 않고 합치기를 반영해야 한다.
준순진 평가는 새로 추가한 사실과 조인해 반복 유도를 줄인다. 동등성 재작성은 바뀐 동치류와 규칙 상수도 처리해야 한다. 일반 사실 삽입의 델타만으로는 귀결을 놓칠 수 있다.
구문적 동일성
동등한 이름 :alice와 :a도 서로 다른 RDF IRI다.
PREFIX : <urn:example:>
SELECT ?x ?y WHERE {
?x :relatedTo ?y .
FILTER(!sameTerm(?x, ?y))
}
자기 관계를 펼치면 항이 같은 쌍과 다른 쌍이 모두 생긴다. 대표 쌍부터 필터링하면 유효한 다른 항의 쌍을 잃는다. 엔진은 필터를 늦추거나, 관련 변수를 펼치거나, 동등한 기호 계산을 해야 한다.
반복 변수는 할당 하나를 요구한다. ?x :relatedTo ?x는 ?x의 이름 하나를 고른다. 구성원이 둘이고 펼친 자기 트리플이 모두 있다면 네 할당이 아니라 두 할당이다. 독립 선택의 곱은 이런 제약 뒤에 적용한다.
서로 다른 변수에 쓰는 데카르트 곱을 같은 변수가 차지한 두 위치에 적용할 수는 없다. 저장소가 대표 하나를 쓰더라도 질의는 두 위치의 선택을 연결한다.
구문적 순서, 문자열 변환, 항 표기를 검사하는 확장은 추론기 내부의 몫이 아니라 SPARQL 함수 정의를 따른다.
삭제와 출처
명시적 연결이 \(a=b\)와 \(b=c\)뿐이면 세 이름이 합쳐진다. \(a=b\)를 지우면 다른 유도가 동등성을 증명하지 않는 한 \(a\)는 \(\{b,c\}\)와 분리되어야 한다.
union–find는 간선 하나를 지워 합치기를 되돌리지 못한다. 이전에 유도한 동등성도 독립적인 잔존 사실이 아니다. 삭제에는 출처 추적, 진리 유지, 영향을 받는 폐포의 재계산이 필요하며 비용은 작업 부하에 달려 있다.
남는 동등성에는 현재의 명시 사실이나 유도가 필요하다. 이전 폐포에 있었다는 이유만으로 유지할 수는 없다. 영향을 받는 부분을 재계산하면 이 구별을 다시 구성할 수 있다.
작은 명시적 구체화 정답 프로그램으로 갱신 뒤 펼친 트리플과 질의 결과의 전체 다중집합을 비교할 수 있다. 상수 규칙을 활성화하는 합치기, 투영에 숨은 다중도, 구문 필터는 사실 수만으로 놓치는 오류를 드러낸다. 이 글은 새 벤치마크 결과를 주장하지 않는다.