기술 요약: 데이터 흐름 제어 (Data Flow Control, DFC)

1. 문제 정의

본 논문은 데이터베이스 시스템과 상호작용하는 AI 에이전트 및 데이터 분석가의 안전성 측면에서 발생하는 결정적인 공백을 다룹니다. 최근의 연구들은 생성된 SQL의 정확성(즉, 쿼리가 사용자의 의도를 반영하는가?)을 개선하는 데 집중하고 있지만, 안전성에 대해서는 간과하는 경우가 많습니다. 쿼리는 의미론적으로는 정확할 수 있으나, 데이터가 어떻게 결합되고, 변형되며, 공개되는지에 관한 규제, 개인정보 보호 또는 비즈니스 제약 조건을 위반할 수 있습니다.

현재의 안전 메커니즘은 다음과 같은 세 가지 주요 이유로 인해 불충분합니다:

1. 액세스 제어 vs. 데이터 흐름: 전통적인 액세스 제어는 누가 데이터를 읽을 수 있는지를 규제하지만, 쿼리 실행 중에 데이터가 어떻게 흐르고 결합되는지는 규제하지 못합니다.
2. 무결성 제약 조건: 이는 데이터베이스의 정적 상태를 규제할 뿐, 중간 쿼리 상태나 유도된 값에 대해서는 규제하지 않습니다.
3. 프로비넌스(Provenance) 오버헤드: 프로비넌스 시스템은 유도 과정을 사후에 감사할 수는 있지만, 전체 프로비넌스 다항식(polynomials)을 구체화하는 것은 막대한 성능 저하(20배에서 10,000배에 이르는 속도 저하)를 초래하여 실시간 강제 적용에는 부적합합니다.
4. 확률적 접근 방식: 프롬프트나 사후 검증을 통해 LLM이 안전성을 확인하도록 하는 방식은 본질적으로 확률적이며, 공식적인 보장을 제공하지 못하고, 정책의 복잡성과 데이터 규모가 증가함에 따라 성능이 저하됩니다.

저자들은 데이터 안전성이 근본적으로 DBMS 내부에서 튜플 수준의 데이터 흐름에 대해 선언적 정책을 강제할 수 있는 결정론적 메커니즘을 요구하는 인프라 문제라고 주장합니다.

2. 방법론

본 논문은 데이터 흐름에 대한 정책 강제를 선언적으로 명시하고 보장하기 위한 프레임워크인 **데이터 흐름 제어(DFC)**를 소개합니다. 이 방법론은 세 가지 핵심 구성 요소로 이루어져 있습니다.

2.1 데이터 안전성의 정형화

저자들은 데이터 안전성을 **프로비넌스 모노미얼(provenance monomials)에 대한 집계 술어(aggregate predicates)**로 정형화합니다.

• 옵티마이저 불변성(Optimizer Invariance): 주요 과제는 물리적 쿼리 계획이 프로비넌스 다항식의 구조에 영향을 미친다는 점입니다. 정책이 옵티마이저에 대해 불변하도록 하기 위해, DFC는 다항식 구조 자체가 아니라 각 출력 튜플 $o$에 대한 **프로비넌스 모노미얼의 집합(bag of provenance monomials, $M(o)$)**이라는 정규화된 표현에 대해 정책을 정의합니다.
• 세미링 집계(Semiring Aggregation): 시스템은 이러한 모노미얼들에 대해 집계를 효율적으로 계산하기 위해 세미링 성질(예: 자연수, 집합)을 활용하며, 이 과정에서 전체 다항식을 구체화하지 않습니다.

2.2 PGN 정책 언어

저자들은 DFC 정책을 표현하기 위한 선언적 언어인 **PGN (Provenance Guard Notation)**을 제안합니다. PGN을 통해 사용자는 다음을 정의할 수 있습니다:

• 소스 ($S$): 정책이 적용되는 관계(relations).
• 제약 조건 ($B$): 소스 관계의 속성과 프로비넌스 모노미얼에 대한 불리언 표현식 (예: "최대 비용 < 100" 또는 "고유 사용자 수 > 1").
• 해결 ($F$): 위반 시 취할 조치로, REMOVE(튜플 삭제), KILL(쿼리 중단), 또는 데이터를 변형하거나 의미론적 결정을 위해 LLM을 호출할 수 있는 사용자 정의 함수(U-DF) 등이 있습니다.
• 확장 기능: PGN은 외부 차원(시스템 카탈로그 또는 다른 테이블 참조), 싱크(insert/update를 위한 대상 테이블), 필수 소스(grounding), 그리고 관계 수준의 해결 방식을 지원합니다.

2.3 Passant 강제 엔진

Passant는 전체 프로비넌스를 구체화하지 않고 PGN 정책을 강제하는 휴대 가능한 쿼리 재작성 계층입니다. 이는 두 가지 주요 재작성 전략을 사용합니다:

1. Partial-Push (부분 푸시): 조인(join)을 통해 정책 집계 계산을 아래로 밀어 넣지만, 여전히 입력 속성에 접근하기 위해 프로비넌스 다항식을 계산해야 합니다.
2. Full-Push (전체 푸시): 주요 기여점으로, 세미링 주석(semiring annotations)을 사용하여 기본 쿼리 실행에 정책 집계 계산을 직접 "편승(piggyback)"시키도록 기본 쿼리를 재작성합니다.
   • 리프 주석(Leaf Annotation): 입력 관계에 세미링 요소(예: count를 위한 1, 합계를 위한 속성 값)를 주석으로 달아줍니다.
   • 연산자 규칙(Operator Rules): 조인은 주석을 곱하고, 집계는 주석을 더합니다.
   • 결과: 정책 제약 조건은 일반적인 쿼리 실행 중에 인라인으로 평가되므로, 테이블을 다시 스캔하거나 리니지(lineage) 데이터와 조인하는 "프로비넌스 세금"을 피할 수 있습니다.

시스템은 외부 조인(set annotation을 통해), 유니온(union), 셀프 조인(symmetry 최적화를 통해)을 포함한 SQL-92 구문을 처리합니다.

3. 주요 기여

1. 정형화: 프로비넌스를 단순한 감사 도구에서, 옵티마이저에 불변하는 레코드 수준의 프로비넌스에 대한 제약 조건으로 정의함으로써 데이터 안전성을 능동적인 정책 강제 메커니즘으로 격상시켰습니다.
2. PGN 언어: 시스템 컨텍스트, 사용자 권한 및 관계 메타데이터를 참조할 수 있는 복잡한 제약 조건(개인정보 보호, grounding, 변형 제한 등)을 표현할 수 있는 선언적 언어를 설계했습니다.
3. Passant 엔진 및 알고리즘:
   • 기존 프로비넌스 시스템을 사용하는 나이브한 후처리 베이스라인.
   • 중간 상태를 크게 줄이는 Partial-Push 및 Full-Push 재작성 알고리즘.
   • 템플릿화된 정책(여러 임계값을 하나의 지배적인 제약 조건으로 병합) 및 대칭 셀프 조인(계산 복잡도를 팩토리얼에서 선형으로 감소)을 위한 최적화.
4. 실증적 평가: 다양한 데이터베이스 엔진에서 DFC 강제가 거의 제로에 가까운 오버헤드로 달성될 수 있음을 입증했습니다.

4. 결과

저자들은 다섯 가지 DBMS 엔진(DuckDB, Umbra, PostgreSQL, DataFusion, SQLServer)에서 Passant를 평가했습니다.

• 성능: TPC-H 쿼리에 대해, Full-Push는 대부분의 경우 ≈0%의 오버헤드를 달성했으며, 놀랍게도 Umbra 엔진에서는 기본 쿼리(정책 없음)보다 성능이 더 뛰어났습니다.
• 베이스라인과의 비교:
  • 논리적/물리적 프로비넌스(Logical/Physical Provenance): 이러한 방식은 프로비넌스 데이터를 구체화하고 조인하는 비용 때문에 막대한 속도 저하(Logical의 경우 2,000% ~ 75,000%, Physical의 경우 300% ~ 700%)를 초래했습니다.
  • LLM 체크: 13개의 TPC-H 쿼리와 1~32개의 정책을 대상으로 한 비교에서, DFC는 LLM 기반 체크보다 수 자릿수 더 빨랐으며, LLM은 공식적인 보장도 제공하지 못했습니다.
• 확장성:
  • 정책 개수: 템플릿 최적화(제약 조건 병합)를 사용하여 시스템은 정책 개수에 따라 하위 선형적으로 확장됩니다.
  • 셀프 조인: 대칭 정책 최적화를 통해 많은 셀프 조인이 포함된 쿼리에 대한 강제 복잡도를 팩토리얼($O(n!)$)에서 선형($O(n)$)으로 줄였습니다.
• 응용: 비즈니스 프로세스 상태 머신 강제 작업에서, Full-Push는 결정론적 정확성을 제공하면서 LLM 기반 접근 방식보다 두 자릿수 더 빨랐습니다.

5. 의의 및 주장

본 논문은 **데이터 흐름 제어(DFC)**가 데이터 안전성을 "프롬프트와 사후 검사"에서 데이터 인프라로 이동시키는 첫 걸음이라고 주장합니다.

• 기본 설정으로서의 안전(Safety by Default): 거의 제로에 가까운 오버헤드를 달성함으로써, DFC는 모든 쿼리에 대해 안전 정책을 적용하는 것을 가능하게 하여, 안전성을 선택적이고 비용이 많이 드는 추가 기능이 아닌 자연스러운 선택으로 만듭니다.
• 결정론적 보장: 확률적인 LLM 가드와 달리, DFC는 데이터 흐름이 규제 및 비즈니스 제약 조건을 준수한다는 공식적이고 결정론적인 보장을 제공합니다.
• 인프라의 전환: 이 연구는 안전성이 애플리케이션이나 에이전트에게 위임되어야 하는 것이 아니라, 데이터베이스 엔진 자체에 의해 강제되어야 하며, 단순히 누가 접근하는지가 아니라 데이터가 어떻게 변형되고 결합되는지를 관리해야 한다고 주장합니다.

저자들은 현재 프로토타입이 단조(monotonic) SQL-92 쿼리에 집중하고 있지만, 더 넓은 적용 가능성을 위해 DFC를 비단조(non-monotonic) 구문(부정, 재귀)으로 확장하는 것이 향-후 필요한 단계라고 언급했습니다. 시스템은 오픈 소스로 공개되어 있습니다.