논리 프로그래밍(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 |
|---|---|---|
| 논리적 접근 | 연역(Deduction): 사실을 연쇄적으로 축적하는 Bottom-up 방식 | 만족(Satisfiability): 규칙과 모순되지 않는 ‘가능한 세계’를 탐색 |
| 핵심 목표 | 주어진 데이터로부터 확실한 사실을 이끌어냄 | 복잡한 제약 조건을 만족하는 해답(Model)을 찾음 |
| 적합한 상황 | 대용량 데이터 기반의 규칙 분석 | 데이터는 적지만 규칙이 복잡한 조합 최적화 |
| 주요 사례 | 정적 분석, 보안 정책 검증, 그래프 DB | 로봇 경로 계획, 팀 구성, 시스템 설정 자동화 |
마치며
우리가 망치를 들면 모든 게 못으로 보인다고 하지만, 도구 상자에 망치와 드라이버가 모두 있다면 상황에 맞춰 선별하여 사용하는 지혜가 필요합니다.
- Datalog는 거대한 데이터의 바다에서 흩어진 사실들을 논리로 엮어 보이지 않는 관계를 찾아내는 그물과 같습니다.
- ASP는 복잡하게 뒤엉킨 제약 조건의 실타래 속에서 올바른 해답을 찾아내는 실마리와 같습니다.
두 기술은 ‘논리(Logic)’라는 같은 언어를 쓰지만, 바라보는 곳은 다릅니다. 이 차이를 이해한다면, 우리는 문제를 만났을 때 더 명쾌한 해법을 선택할 수 있을 것입니다.
Comments