ASP와 Datalog: 논리 프로그래밍의 두 가지 시선

논리 프로그래밍(Logic Programming)이라는 거대한 숲에 들어서면, 우리는 종종 유사한 형태를 지닌 두 가지 거목을 마주하게 됩니다. 바로 Datalog와 ASP(Answer Set Programming)입니다.

둘은 모두 Prolog라는 공통된 조상에서 파생되었고, 겉보기에는 문법도 매우 유사합니다. 사실상 Datalog 프로그램은 유효한 ASP 프로그램이기도 하기 때문입니다. 이 때문에 처음 접하는 사람들은 “과연 무엇이 다른가?” 혹은 “ASP가 Datalog의 상위 호환인가?”라는 혼동을 겪기 쉽습니다.

하지만 이 둘을 단순히 비교나 경쟁 관계(vs)로 보는 것은 타당하지 않습니다. 그보다는 같은 뿌리에서 시작되었지만, 서로 다른 문제를 해결하기 위해 진화한 두 가지 시선으로 바라보는 것이 더 정확합니다. 하나는 ‘데이터로부터 확실한 사실을 이끌어내는 도구’로, 다른 하나는 ‘복잡한 제약 조건 속에서 가능한 해답을 찾아내는 도구’로 발전했기 때문입니다.

Datalog: 데이터 중심의 확실성 (Deductive Database)

Datalog는 그 이름에서 알 수 있듯이 Data와 Logic의 결합입니다. 태생적으로 데이터베이스 진영에서 “SQL만으로는 부족하다”는 요구와 함께 등장했습니다. SQL은 강력하지만, 트리 구조를 탐색하거나 그래프의 도달 가능성(reachability)을 따지는 재귀(recursion)적인 질의를 처리하는 데에는 한계가 존재했습니다.

Datalog는 바로 이 지점에서 SQL의 한계를 보완하며 등장했습니다.

• 본질: 단순히 저장된 데이터를 조회하는 것을 넘어, 명시된 규칙을 바탕으로 새로운 정보를 논리적으로 추론(Inference)해내는 도구입니다. 이는 흔히 연역(Deduction)이라 합니다.
• 목표: “주어진 사실(Facts)과 규칙(Rules)이 있을 때, 여기서 논리적으로 도출될 수 있는 모든 새로운 사실은 무엇인가?”
• 특징:
  • 재귀(Recursion): Datalog의 가장 큰 강점입니다. “내 친구의 친구는 내 친구다” 같은 규칙을 재귀적으로 적용하여 소셜 네트워크의 연결 관계를 규명하거나, 프로그램의 호출 그래프를 분석하는 데 탁월합니다.
  • 확실성(Determinism): Datalog 프로그램의 실행 결과는 언제나 유일합니다. 입력 데이터가 같다면, 도출되는 결과(Minimal Model)도 항상 동일합니다. 여러 가지 가능성을 고려할 필요가 없습니다. 정답은 정해져 있습니다.
  • 효율성: 다항 시간(Polynomial Time) 내에 결과를 도출할 수 있도록 언어적인 제약을 둡니다. 함수 기호(function symbol)를 제한하거나 부정을 신중하게 다루는 이유도 연산을 효율적으로 수행하기 위함입니다.

ASP: 탐색과 해결의 가능성 (Constraint Solving)

반면, ASP(Answer Set Programming)는 “이 데이터에서 어떤 결론이 도출되는가?”보다는 “주어진 제약 조건을 모두 만족하는 시나리오는 무엇인가?”라는 질문에 답하기 위해 고안되었습니다.

ASP는 인공지능(AI)과 지식 표현(Knowledge Representation) 분야에서 어려운 조합 최적화 문제(Combinatorial Search Problems)를 해결하기 위해 진화했습니다.

• 본질: “어떻게” 풀지 단계별로 지시하는 대신, 정답이 갖춰야 할 “조건”만 정의하면 컴퓨터가 해답을 찾아내는 선언적 문제 해결(Declarative Problem Solving) 방식입니다. 이를 통칭하여 선언적 프로그래밍(Declarative Programming)이라 합니다.
• 목표: “이 규칙들을 위배하지 않으면서 가능한 세계(Stable Models/Answer Sets)를 찾아라.”
• 특징:
  • 비결정성(Non-determinism): ASP의 핵심은 ‘선택’입니다. “$a$일 수도 있고 $b$일 수도 있다”는 상황을 모델링할 수 있습니다. 그래서 ASP 프로그램의 실행 결과는 하나가 아닌 여러 개의 ‘해답 집합(Answer Sets)’이 될 수 있습니다. (해답이 존재하지 않을 수도 있습니다.)
  • 제약 조건(Constraints): “특정 상황은 결코 발생해서는 안 된다”라는 제약 조건을 둡니다. 스케줄링 문제를 풀 때 “동시에 두 장소에 있을 수 없다”는 조건을 부여하는 것과 같습니다.
  • 복잡한 문제 해결: ASP는 NP-hard 문제를 다룹니다. 외판원 순회 문제(TSP), 시간표 작성, 하드웨어 설정 구성 등 방대한 경우의 수를 탐색해야 하는 복잡한 문제 해결에 최적화되어 있습니다.

두 시선의 관계: 포함 관계 그 이상

문법적으로만 보면 ASP는 Datalog를 포함하는 상위 집합(Superset)처럼 보입니다. 모든 Datalog 프로그램은 ASP 솔버(Clingo, DLV 등)에서 문제없이 실행됩니다.

하지만 이 둘을 구분 짓는 결정적인 차이는 ‘문제를 대하는 접근 방식’에 있습니다.

마치며

우리가 망치를 들면 모든 게 못으로 보인다고 하지만, 도구 상자에 망치와 드라이버가 모두 있다면 상황에 맞춰 선별하여 사용하는 지혜가 필요합니다.

• Datalog는 거대한 데이터의 바다에서 흩어진 사실들을 논리로 엮어 보이지 않는 관계를 찾아내는 그물과 같습니다.
• ASP는 복잡하게 뒤엉킨 제약 조건의 실타래 속에서 올바른 해답을 찾아내는 실마리와 같습니다.

두 기술은 ‘논리(Logic)’라는 같은 언어를 쓰지만, 바라보는 곳은 다릅니다. 이 차이를 이해한다면, 우리는 문제를 만났을 때 더 명쾌한 해법을 선택할 수 있을 것입니다.

SPARQL의 SQL 유사성이 주는 함정, 그리고 Datalog

요즘 온톨로지와 시맨틱 웹 관련 세미나나 강연을 진행하면서 자주 느끼는 점이 하나 있습니다. 바로 SPARQL을 소개할 때 청중들의 반응입니다.

SQL과 닮은 친구, SPARQL

SPARQL은 문법적으로 SQL과 매우 유사합니다. SELECT, WHERE, ORDER BY 같은 키워드를 사용하기 때문에, 개발 경험이 있는 분들은 처음에 굉장히 반가워하십니다. “아, 그냥 조인(Join) 많은 SQL이구나!”라고 받아들이는 경우가 많기 때문입니다.

하지만 강연을 계속 진행하다 보면, 바로 그 ‘익숙함’이 오히려 독이 되는 순간이 찾아옵니다.

유사함이 주는 오해

SQL은 닫힌 세계 가설(Closed World Assumption, CWA)을 전제로 합니다. 데이터베이스에 명시되지 않은 정보는 ‘거짓’이라고 간주하는 방식입니다. 예를 들어 수강생 목록에 ‘홍길동’이 없다면, 시스템은 “홍길동은 수강생이 아니다”라고 확신합니다.

반면, SPARQL과 온톨로지 세계관은 열린 세계 가설(Open World Assumption, OWA)을 따릅니다. 데이터에 정보가 없다고 해서 그것이 틀린 것이 아니라, 단지 ‘아직 모르는 상태’라고 판단합니다. “홍길동이 수강생이라는 데이터가 없다”는 사실이 “홍길동은 수강생이 아니다”라는 결론을 보장하지 않습니다. 어딘가 다른 데이터셋에 그 정보가 있을 수도 있고, 단지 아직 기록되지 않았을 뿐이라고 가정하기 때문입니다.

사실 테이블이냐 그래프냐 하는 구조적 차이보다, 이러한 철학적 전제의 차이가 쿼리 결과와 추론의 방향을 결정짓는 훨씬 더 본질적인 지점입니다.

SQL과 유사한 구문은 사용자로 하여금 관계형 데이터베이스(RDB)의 멘탈 모델을 온톨로지에 투영하게 만듭니다. 그러나 RDF 그래프 패턴 매칭은 관계 대수(Relational Algebra)를 기반으로 하는 SQL의 조인 연산과는 그 수학적 토대와 의미론적 해석이 근본적으로 다릅니다. 특히 OPTIONAL 연산의 비단조성(Non-monotonicity)이나 추론 규칙(Entailment Regimes)이 개입되는 지점에서 이러한 간극은 극대화됩니다. “왜 SQL과 동일하게 결과가 나오지 않는가?”라는 의문이 드는 순간, 역설적으로 그 익숙한 문법은 학습자가 시맨틱 웹의 고유한 논리 구조를 이해하는 데 방해가 되는 인지적 장벽으로 작용합니다.

차라리 완전히 다른 문법이라면?

그래서 최근에는 이런 고민을 하게 되었습니다. “차라리 온톨로지를 다루는 언어는 SQL과 완전히 다르게 생겼다고 처음부터 못 박는 게 낫지 않을까?”

RDB와는 아예 다른 사고방식이 필요하다는 것을 강조하기 위해, 문법적 유사성이 없는 언어로 접근하는 것이 ‘사고의 전환’을 유도하는 데 더 유리할 수 있다는 생각입니다.

여기서 소개하고 싶은 것이 바로 Datalog입니다.

Datalog: 논리 기반의 질의 언어

Datalog는 Prolog의 부분집합으로 시작된 선언형 논리 프로그래밍 언어입니다. 이름에서 알 수 있듯이 데이터(Data)와 논리(Logic)를 다루는 데 특화되어 있습니다.

SPARQL이 데이터베이스로부터 명시적인 데이터를 조회(Querying)하는 데 중점을 둔다면, Datalog는 주어진 사실(Facts)과 규칙(Rules)으로부터 새로운 지식을 도출(Inference)하는 패러다임을 따릅니다. 이는 온톨로지의 핵심인 추론(Reasoning) 메커니즘과 논리적으로 일관된 구조를 가집니다.

Datalog의 맛보기

예를 들어, “조상의 조상은 조상이다”라는 재귀적인 관계를 SPARQL로 표현하려면 (SPARQL 1.1의 Property Path가 있긴 하지만) 꽤나 설명이 길어질 수 있습니다. 하지만 Datalog에서는 매우 직관적인 논리 규칙으로 표현됩니다.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

• X가 Y의 부모라면, X는 Y의 조상입니다.
• X가 Z의 부모이고, Z가 Y의 조상이라면, X는 Y의 조상입니다.

이 문법은 SQL과는 전혀 다릅니다. 그렇기 때문에 학습자는 RDB의 사고방식을 내려놓고, 논리적 관계와 사실의 도출이라는 새로운 관점에서 데이터를 바라보게 됩니다.

결론

물론 현실의 시맨틱 웹 생태계 표준은 SPARQL입니다. 하지만 온톨로지의 본질인 ‘지식의 표현과 추론’을 이해하기 위한 입문 도구로서, 혹은 SPARQL이 주는 RDB의 환상을 깨기 위한 충격 요법으로서 Datalog를 먼저 접해보는 것은 꽤나 매력적인 시도가 될 것 같습니다.

마지막으로, 앞서 이야기한 세 가지 언어의 기술적 특성을 간단히 비교해보면 다음과 같습니다.

SQL의 그늘에서 벗어나, 데이터 그 자체의 논리적 연결에 집중하게 해주는 Datalog. 온톨로지를 공부하다가 SPARQL의 문법적 함정에 빠져 허우적거린 경험이 있으시다면, 한 번쯤 눈길을 돌려볼 만한 가치가 있습니다.

RDF 처리에 CPU와 메모리가 중요한 이유

딥러닝과 대규모 언어 모델(LLM)의 확산으로 인해 고성능 컴퓨팅의 중심이 GPU로 이동하고 있지만, RDF(Resource Description Framework) 데이터 처리와 SPARQL 쿼리 실행 영역에서는 여전히 CPU의 성능과 대규모 메모리 아키텍처가 시스템의 효율성을 결정짓는 핵심 요소입니다.

1. RDF 처리의 특성: 랜덤 액세스 패턴

GPU가 빛을 발하는 영역은 대규모 병렬 연산입니다. 정형화된 데이터를 대상으로 동일한 연산을 수천 개의 데이터에 동시에 적용하는 작업에서는 GPU가 압도적입니다. 그러나 RDF와 그래프 데이터베이스는 데이터 간의 연결을 따라가는 비정형적인 탐색이 주를 이루므로 성격이 근본적으로 다릅니다.

그래프 탐색의 본질

RDF 데이터는 트리플(Subject-Predicate-Object) 형태로 저장되어 거대한 그래프를 형성합니다. SPARQL 쿼리를 실행한다는 것은 이 그래프를 탐색(Traversal)하는 것입니다.

문제는 그래프 탐색이 랜덤 액세스 패턴을 따른다는 점입니다. A 노드에서 B 노드로, B에서 또 다른 C 노드로 점프하는 과정에서 메모리 접근이 예측 불가능하게 분산됩니다. GPU는 순차적이고 예측 가능한 메모리 접근에 최적화되어 있어, 이러한 랜덤 패턴에서는 오히려 비효율적입니다 [1].

2. 메모리 용량의 결정적 차이

GPU 메모리의 한계

RDF 트리플 스토어는 효율적인 쿼리를 위해 다중 인덱스를 유지합니다. 기본 트리플 구조(S, P, O)에서는 6가지 순열(SPO, SOP, PSO, POS, OSP, OPS)이 가능하지만, 네임드 그래프(Named Graph)를 포함하는 쿼드(Quad) 구조(G, S, P, O)로 확장되면 상황은 훨씬 복잡해집니다.

이론적으로 4개의 요소는 총 24가지(4!)의 순열을 가질 수 있으며, 실무적인 성능을 위해 GSPO, GPOS, GOSP, SPOG, GSOP 등 주요 접근 패턴에 대한 인덱스를 중복해서 생성합니다 [2]. 여기에 문자열을 ID로 변환하는 딕셔너리 인코딩 구조까지 포함하면, 전체 인덱스 크기는 원본 데이터 대비 5~10배 이상으로 증폭됩니다.

NVIDIA H100도 80GB 정도의 메모리를 가지고 있습니다. 반면, 서버급 CPU 시스템은 수백 GB에서 TB 단위의 메모리를 장착할 수 있습니다. 수십억 개의 트리플을 처리할 때 이 거대한 데이터를 80GB 내외의 GPU 메모리에 담는 것은 구조적으로 한계가 있습니다.

대규모 Knowledge Graph(예: Wikidata, DBpedia)를 다룬다면, GPU 메모리에 전체 그래프를 올리는 것 자체가 불가능합니다. “필요한 부분만 디스크에서 읽어오면 되지 않느냐”고 생각할 수 있지만, 앞서 언급한 랜덤 액세스 특성 때문에 인덱스의 일부만 메모리에 올리는 방식은 I/O 병목 현상을 극심하게 유발합니다. 결국 고성능 SPARQL 엔진은 전체 인덱스를 메모리에 상주시키는 ‘In-memory’ 방식을 선호하게 되는데, GPU는 이 지점에서 메모리 용량이라는 물리적 한계에 부딪히게 됩니다.

CPU-GPU 데이터 전송 오버헤드

GPU를 사용하더라도 데이터는 CPU 메모리에서 GPU 메모리로 PCIe 버스를 통해 전송되어야 합니다. 이 전송 오버헤드가 실제 연산 시간보다 길어지는 경우가 많습니다 [3].

특히 SPARQL 쿼리가 그래프의 다양한 영역을 탐색해야 할 때, 필요한 데이터를 GPU로 계속 옮겨야 하므로 GPU 연산의 이점이 상쇄됩니다.

3. SPARQL 쿼리 처리의 CPU 친화적 특성

조인 연산과 쿼리 최적화

SPARQL 쿼리의 핵심은 트리플 패턴 매칭과 이를 연결하는 조인(Join) 연산입니다. 일반적인 SQL 조인이 미리 정의된 외래 키(Foreign Key)를 따라 테이블을 결합하는 방식이라면, SPARQL의 조인은 쿼리 실행 시점에 공유 변수(Variable)를 매개로 그래프 패턴을 확장해 나가는 과정입니다. 복잡한 쿼리는 수십 개의 트리플 패턴을 조인해야 하며, 이때 데이터의 카디널리티(Cardinality, 특정 패턴에 매칭되는 결과의 수)를 예측하여 최적의 조인 순서를 결정하는 것이 성능에 결정적입니다 [4].

쿼리 최적화(Query Optimization)는 본질적으로 순차적이고 복잡한 의사결정 과정입니다. 각 단계의 결과가 다음 단계의 입력이 되므로, GPU의 병렬 처리 능력을 활용하기 어렵습니다. 현대의 고성능 CPU가 제공하는 브랜치 예측(Branch Prediction)과 캐시 최적화가 훨씬 효과적입니다.

추론(Reasoning)의 복잡성

RDF의 강점 중 하나는 온톨로지 기반 추론(Reasoning)입니다. OWL이나 RDFS 시맨틱스에 따라 암시적 지식을 도출하는 과정은 논리적 규칙의 반복 적용을 필요로 합니다 [5].

이 과정은 GPU가 잘하는 “같은 연산의 대량 반복”이 아니라, “조건에 따른 분기가 빈번한 복잡한 로직”입니다. CPU의 복잡한 명령 파이프라인과 분기 예측이 이런 워크로드에 훨씬 적합합니다.

4. 실무적 권장사항

메모리: 다다익선

인메모리 트리플 스토어(예: Apache Jena, GraphDB)를 사용한다면, 메모리야말로 성능의 핵심입니다. 전체 그래프와 인덱스를 메모리에 올릴 수 있다면 쿼리 응답 시간이 극적으로 개선됩니다.

권장사항:

• 중소 규모(수천만 트리플): 64GB 이상
• 대규모(수억 트리플): 256GB 이상
• 엔터프라이즈급(십억 트리플 이상): 1TB 이상 또는 분산 클러스터

CPU: 코어 수보다 단일 코어 성능

많은 분들이 코어 수가 많은 CPU를 선택하지만, SPARQL 쿼리 대부분은 단일 쿼리 단위로 처리됩니다. 동시에 수십 개의 쿼리를 처리해야 하는 경우가 아니라면, 높은 클럭 속도와 큰 L3 캐시를 가진 CPU가 더 효과적입니다.

권장사항:

• 대형 L3 캐시(64MB 이상)를 가진 서버급 CPU
• 메모리 대역폭이 높은 DDR5 지원 플랫폼
• 단일 코어 성능이 중요하므로 무조건적인 코어 수 늘리기는 비효율적

GPU는 특수한 경우에만

물론 GPU가 유리한 RDF 관련 작업도 있습니다:

• 그래프 임베딩 학습 (Knowledge Graph Embedding)
• 대규모 유사도 계산 (Entity Matching)
• 대규모 병렬 조인: 일반적인 SPARQL 조인과 달리, 데이터가 정형화되어 있고 수백만 개의 트리플을 동시에 결합해야 하는 특정 분석용 쿼리(예: 대규모 해시 조인)에서는 GPU의 SIMD(Single Instruction, Multiple Data) 연산이 성능을 높일 수 있습니다 [6].

하지만 다시 강조하지만, 일반적인 SPARQL 쿼리 서빙과 추론에서는 CPU와 메모리 투자가 훨씬 효율적입니다.

5. 결론

RDF 처리 시스템을 구축할 때, GPU 카드를 구매하기 전에 먼저 질문해야 합니다:

“메모리는 충분한가? CPU는 적절한가?”

그래프 데이터의 랜덤 액세스 패턴, 메모리 집약적 인덱싱, 복잡한 추론 로직이라는 세 가지 특성이 CPU와 메모리를 핵심 병목으로 만듭니다. 예산이 한정되어 있다면, 고성능 GPU보다 더 많은 메모리와 캐시가 큰 CPU에 투자하는 것이 현명한 선택입니다.

딥러닝 시대에 GPU가 만능처럼 느껴지지만, 모든 문제가 행렬 연산은 아닙니다. 문제의 본질을 이해하고 그에 맞는 하드웨어를 선택하는 것이야말로 엔지니어의 역할입니다.

참고문헌

1. [1]S. Beamer, K. Asanovic, and D. Patterson, “Direction-Optimizing Breadth-First Search,” in 2012 International Conference on High Performance Computing, Networking, Storage and Analysis (SC), IEEE, 2012, pp. 1–10.
2. [2]M. Atre, V. Chaoji, M. J. Zaki, and J. A. Hendler, “Matrix ‘Bit’ loaded: a scalable lightweight join query processor for RDF data,” Proceedings of the 19th International Conference on World Wide Web (WWW), pp. 41–50, 2010.
3. [3]C. Chantrapornchai and C. Choksuchat, “GPU-based SPARQL Query Processing,” Walailak Journal of Science and Technology, vol. 15, no. 7, pp. 521–537, 2018.
4. [4]A. Hogan and others, “Knowledge Graphs,” ACM Computing Surveys, vol. 54, no. 4, pp. 1–37, 2021.
5. [5]Ontotext, “What is RDF Reasoning?” 2024. Available at: https://www.ontotext.com/knowledgehub/fundamentals/what-is-rdf-reasoning/
6. [6]P. Yuan, P. Liu, J. Zhai, L. Wu, H. Liu, and H. Jin, “TripleBit: A Fast and Compact System for Large Scale RDF Data,” in Proceedings of the VLDB Endowment, 2013, pp. 517–528.