Datalog와 함수형 프로그래밍의 만남, Datafun 분석

논문에서는 Datalog의 재귀 쿼리를 최소 고정점 연산자(Least Fixed-Point Operator)로 재해석하는 접근 방식을 제시합니다. 그래프 도달 가능성 예시를 통해, 재귀적 정의를 함수 f에 대한 최소 R (R ⊇ f(R)) 형태로 변환하여 함수형 언어에서 표현 가능함을 보입니다. 이는 술어 논리(Predicate Logic) 기반의 Datalog를 집합론(Set Theory)과 함수(Functions)로 통합하는 핵심 아이디어입니다.

Datafun은 Datalog의 재귀 쿼리에서 발생하는 잘 정의됨(Well-definedness)을 보장하기 위해 단조성(Monotonicity)을 추적하는 타입 시스템을 도입했습니다. 논문에서는 이러한 단조성 추적이 함수 합성(Function Composition) 시에도 구성적으로(Compositionally) 작동함을 설명합니다. 비단조성(Non-monotonicity)은 범주론(Category Theory)의 단조적 코모나드(Monoidal Comonad) 또는 필요성 모달리티(Necessity Modality)로 표현될 수 있다고 언급합니다.

기존의 반복적인 고정점 탐색 방식은 중복 계산(Redundant Computations)으로 인해 비효율적입니다. 논문은 이를 개선하기 위해 '세미나이브(Semi-naïve)' 알고리즘을 적용하여, 이전 반복에서 새롭게 추론된 사실(Newly Deduced Facts)만을 기반으로 다음 단계를 계산한다고 설명합니다. 이는 이산 미분(Discrete Derivative) 개념을 활용하여 증분 계산(Incremental Computation)을 가능하게 하며, 시간 복잡도(Time Complexity)를 크게 향상시킵니다.

커뮤니티에서는 Datalog의 간결한 의미론(Simple Semantics)과 효율적인 구현 전략(Efficient Implementation Strategies)이 여전히 매력적이라는 점에 동의합니다. 특히, 함수형 프로그래밍과의 통합을 통해 코드 추상화(Code Abstraction)의 한계를 극복하려는 시도에 주목하고 있습니다. 다만, 실제 데이터 격리 아키텍처(Data Isolation Architecture) 구현 시 발생할 수 있는 복잡성과 타입 시스템(Type System)의 제약에 대한 논의도 이어지고 있습니다.