Datalog의 증분 계산

Datalog는 사실(Facts)과 규칙(Rules)으로부터 새로운 지식을 연역해내는 논리 프로그래밍 언어입니다. 간결한 재귀 규칙 몇 줄로 소셜 네트워크의 도달가능성을 분석하거나, 지식 그래프 위에서 복잡한 추론을 수행할 수 있습니다.

하지만 Datalog를 실제 시스템에 적용하려면, “데이터가 변하면 어떻게 하는가”라는 문제를 피할 수 없습니다.

쇼핑몰의 추천 시스템을 예로 들면, 고객이 새 상품을 하나 구매할 때마다 모든 고객의 추천 목록을 처음부터 다시 계산하는 것은 현실적이지 않습니다. 영향받는 추천만 갱신하면 됩니다. 그런데 전통적인 Datalog 엔진은 사실 하나가 바뀌면 전체 추론을 처음부터 다시 수행합니다.

정적 Datalog의 한계

쇼핑몰에서 “함께 구매되는 상품” 데이터를 기반으로 연관 제품을 추천하는 시나리오로 이 문제를 살펴봅니다. 노트북을 산 사람은 마우스, 파우치, 가방을 함께 사는 경향이 있고, 마우스를 산 사람은 마우스패드를, 파우치를 산 사람은 가방을 새로 구매하는 경향이 있습니다. 이 연쇄를 따라가면, 노트북 구매자에게 마우스패드까지 추천할 수 있습니다. Datalog로 표현하면 다음과 같습니다.

bought_together("노트북", "마우스").
bought_together("노트북", "파우치").
bought_together("노트북", "가방").
bought_together("마우스", "마우스패드").
bought_together("파우치", "가방").

% 연관 추천 (재귀)
recommends(X, Y) :- bought_together(X, Y).
recommends(X, Y) :- bought_together(X, Z), recommends(Z, Y).

이 규칙을 평가하면 직접 연관뿐 아니라, recommends("노트북", "마우스패드")처럼 재귀적으로 도출하는 추천까지 만들어냅니다. 특히 recommends("노트북", "가방")은 직접 구매 경로와 파우치를 경유하는 경로, 두 가지로 도출됩니다.

여기에 새로운 구매 패턴을 발견하여 사실 하나를 추가하는 상황을 살펴봅니다.

bought_together("가방", "보조배터리").   % 새로운 사실 추가!

나이브(Naive)한 Datalog 엔진은 기존에 도출된 모든 recommends 관계를 버리고, 처음부터 전체 추론을 다시 실행합니다. 상품이 네 개일 때는 문제가 되지 않지만, 수백만 개의 상품과 수억 건의 구매 이력을 가진 대형 쇼핑몰에서는 치명적인 비용이 됩니다.

이에 대한 고전적인 해법으로 세미나이브 평가(Semi-naive Evaluation)가 있습니다. 이전 반복에서 새로 도출된 사실만을 다음 반복의 입력으로 사용하여 중복 계산을 줄이는 기법입니다. 하지만 세미나이브 평가에도 한계가 있습니다. 사실의 추가에는 비교적 잘 대응하지만, 삭제에는 취약합니다. 마우스가 단종되어 bought_together("노트북", "마우스")를 삭제하면, 마우스를 경유해서 도출했던 recommends("노트북", "마우스패드") 같은 추천도 무효화해야 합니다. 어떤 추천이 영향받는지를 추적하려면, 결국 상당 부분을 다시 계산해야 합니다.

Differential Dataflow: 차이만 계산하는 발상

2013년, Frank McSherry 등은 이 문제에 대한 근본적으로 다른 접근법인 Differential Dataflow를 제안했습니다[1].

핵심 아이디어는 단순합니다. 컬렉션을 정적인 집합으로 보지 않고, 시간에 따른 차이(Difference)의 축적으로 표현하는 것입니다.

\[\text{Collection}[t] = \sum_{s \leq t} \Delta[s]\]

시점 $t$에서의 컬렉션은, 그 시점 이전에 발생한 모든 변경분($\Delta$)의 합산입니다. 삽입은 $+1$, 삭제는 $-1$로 기록합니다. 이 방식은 메모리 관리에서의 레퍼런스 카운팅(Reference Counting)과 구조적으로 닮아 있습니다. 레퍼런스 카운팅에서 객체의 참조가 생기면 카운트를 $+1$, 참조가 사라지면 $-1$하여 카운트가 $0$이 되면 객체를 해제하듯, Differential Dataflow에서도 각 튜플의 가중치가 $0$이 되면 해당 사실이 컬렉션에서 사라집니다. 다만 Differential Dataflow는 이를 단순한 생존 여부를 넘어 가중 집합(weighted set, 혹은 Z-set)으로 일반화합니다. 가중 집합이란 각 원소에 정수 가중치를 부여한 집합으로, 일반 집합이 “있다/없다”만 표현할 수 있는 반면, 가중 집합은 “몇 번 도출되었는가”까지 표현합니다. 앞의 예에서 recommends("노트북", "가방")은 직접 구매 경로와 파우치를 경유하는 경로, 두 가지로 도출되므로 가중치가 $2$입니다. 이때 파우치와 가방의 연관이 사라져 한 경로가 무효화($-1$)되더라도 가중치가 $1$로 남아 있으므로 해당 추천은 여전히 유효합니다. 레퍼런스 카운팅이 참조 수로 객체의 생존을 결정하듯, 가중 집합은 도출 경로의 수로 사실의 유효성을 결정하는 것입니다.

가중 집합 비교: 가중치 2 vs 1

추천 시스템의 예에 적용하면, 추천 목록(Collection)은 과거 구매 이력 변화(Difference)의 누적이며, 새 구매 패턴을 발견하면 영향받는 추천만 갱신하면 됩니다.

이 접근이 강력한 이유는 ‘시간’의 개념을 단순한 일련번호가 아니라 부분 순서(Partial Order)로 일반화하기 때문입니다. 예를 들어 Datalog의 재귀 규칙을 평가할 때, 시간은 (외부 시점, 내부 반복 횟수)라는 2차원 좌표가 됩니다. Differential Dataflow는 뫼비우스 역변환(Möbius Inversion)이라는 수학적 기법을 사용하여 이러한 다차원 시간 축에서도 차이를 정확하게 계산합니다.

이 모든 것은 Timely Dataflow라는 분산 데이터플로우 런타임 위에서 동작합니다. Timely Dataflow가 데이터의 흐름과 병렬 실행을 관리하고, Differential Dataflow가 그 위에서 증분 계산의 논리를 담당하는 구조입니다.

일괄 처리, 스트림 처리, 그리고 Differential Dataflow

기존의 데이터 처리 패러다임과 비교하면 Differential Dataflow의 위치가 명확해집니다.

구분	일괄 처리 (Batch)	스트림 처리 (Stream)	Differential Dataflow
데이터 모델	정적 데이터셋	무한 이벤트 흐름	차이(Difference)의 축적
변경 대응	전체 재계산	개별 이벤트 처리	변경분만 전파
재귀 지원	매 반복 전체 재실행	제한적 (윈도우 기반)	네이티브 (중첩된 반복 추적)
지연 시간	높음	낮음	낮음 (변경 크기에 비례)
처리량	높음	중간	높음
대표 시스템	Hadoop, Spark (batch)	Kafka Streams, Flink	differential-dataflow, Materialize

일괄 처리는 전체를 다시 계산하므로 정확하지만 느리고, 스트림 처리는 빠르지만 재귀적 추론을 표현하기 어렵습니다. Differential Dataflow는 변경의 크기에 비례하는 비용으로 재귀를 포함한 복잡한 연산을 증분적으로 유지합니다.

DDlog: Datalog를 증분으로 만들다

Differential Dataflow의 개념을 Datalog에 직접 적용한 것이 Differential Datalog(DDlog)입니다.

DDlog의 핵심은 다음과 같습니다.

프로그래머는 평범한 Datalog 규칙을 작성하고, DDlog 컴파일러가 이를 자동으로 증분 실행 가능한 Differential Dataflow 파이프라인으로 변환한다.

// DDlog 규칙
input relation BoughtTogether(item: string, related: string)
output relation Recommends(item: string, recommended: string)

Recommends(x, y) :- BoughtTogether(x, y).
Recommends(x, y) :- BoughtTogether(x, z), Recommends(z, y).

// 런타임 동작:
// BoughtTogether("가방", "보조배터리") 삽입 →
// Recommends에서 변경된 튜플만 자동으로 전파
// BoughtTogether("파우치", "가방") 삭제 →
// Recommends("노트북", "가방")의 가중치가 2→1로 갱신 (직접 구매 경로 유지)

프로그래머 입장에서는 일반적인 Datalog를 작성하는 것과 동일합니다. 하지만 런타임의 동작은 근본적으로 다릅니다. 입력 관계(relation)에 삽입이나 삭제가 스트리밍으로 들어오면, 출력 관계에서 변경된 부분만 자동으로 갱신합니다. 세미나이브 평가가 해결하지 못했던 삭제 문제까지 처리합니다.

Rust로 만져보는 Differential Dataflow

Differential Dataflow의 정식 구현체(canonical implementation)는 Rust로 작성한 라이브러리입니다. differential-dataflow 크레이트(crate)를 사용하면, 앞서 살펴본 연관 추천 계산을 다음과 같이 표현할 수 있습니다.

use differential_dataflow::input::Input;
use differential_dataflow::operators::Iterate;
use differential_dataflow::operators::Join;
use differential_dataflow::operators::Consolidate;

timely::execute_directly(move |worker| {
    let (mut input, probe) = worker.dataflow(|scope| {
        let (input, edges) = scope.new_collection::<(String, String), isize>();

        // Datalog의 recommends 규칙과 동일한 연관 추천 계산
        let recommendations = edges.iterate(|reach| {
            let edges = edges.enter(&reach.scope());
            reach
                .join_map(&edges, |_mid, src, dst| (dst.clone(), src.clone()))
                .concat(&edges)
                .distinct()
        });

        let probe = recommendations.consolidate().probe();
        (input, probe)
    });

    // 시점 0: 초기 구매 패턴 입력
    input.insert(("노트북".into(), "마우스".into()));
    input.insert(("노트북".into(), "파우치".into()));
    input.insert(("노트북".into(), "가방".into()));
    input.insert(("마우스".into(), "마우스패드".into()));
    input.insert(("파우치".into(), "가방".into()));
    input.advance_to(1);
    input.flush();
    worker.step_while(|| probe.less_than(input.time()));

    // 시점 1: 새로운 구매 패턴 추가 — 변경분만 재계산
    input.insert(("가방".into(), "보조배터리".into()));
    input.advance_to(2);
    input.flush();
    worker.step_while(|| probe.less_than(input.time()));
});

advance_to(1)에서 advance_to(2)로 진행할 때, 시스템은 ("가방", "보조배터리") 추가로 인해 영향받는 추천 관계만 증분적으로 계산합니다. 기존의 ("노트북", "마우스"), ("마우스", "마우스패드") 등 기존 추천 추론은 그대로 유지됩니다.

진화하는 지식 그래프를 위하여

현실 세계의 지식 그래프는 정적이지 않습니다. 새로운 논문이 나오면 인용 관계가 바뀌고, 조직 개편이 일어나면 보고 체계가 변하며, 쇼핑몰에서는 매 시간 새로운 구매 패턴이 생깁니다. 대화형 AI 에이전트의 경우에도, 사용자가 요구사항을 추가하거나 수정할 때마다 지식 그래프의 상태는 계속 변합니다. 이런 상황에서 매번 전체 추론을 다시 수행하는 것은 비현실적입니다.

Differential Dataflow는 지식 그래프의 변경을 차이(Difference)로 표현하고, 추론 결과를 증분적으로 유지함으로써, 변화하는 데이터 위에서 실시간으로 추론할 수 있게 합니다.

최근에는 이 핵심 아이디어를 데이터베이스와 스트림 처리에 특화시킨 DBSP(Database Stream Processing)도 등장했습니다. Materialize와 같은 시스템이 이를 기반으로 SQL 뷰의 증분 유지(Incremental View Maintenance)를 구현하고 있으며, 증분 계산의 영향력은 논리 프로그래밍을 넘어 더 넓은 데이터 생태계로 확장되고 있습니다.

마치며

전통적인 Datalog는 “변하지 않는 사실”을 전제로 합니다. 모든 데이터를 확정한 뒤에야 추론을 시작할 수 있는 구조입니다. 하지만 현실의 데이터는 계속 변합니다. 신상품이 들어오고, 인기 상품이 사라지며, 구매 패턴은 시시각각 달라집니다.

Differential Dataflow는 데이터의 변화 자체를 계산의 일급 시민(first-class citizen)으로 다룹니다. 변경분만을 추적하고 전파함으로써, 전체 재계산 없이도 정확한 추론 결과를 유지할 수 있게 합니다. 이것이 Differential Dataflow가 논리 프로그래밍에 가져다 준 가장 본질적인 전환입니다.

참고 문헌

[1]F. McSherry, D. G. Murray, R. Isaacs, and M. Isard, “Differential Dataflow,” in Proceedings of the 6th Biennial Conference on Innovative Data Systems Research (CIDR ’13), CIDR, Jan. 2013. [Link]