[논문] 결정 근원: 모호함에서 대수학으로
개요
많은 데이터 시스템은 동일한 입력에 대해 여러 개의 허용 가능한 결과를 가집니다. 예를 들어, 동시 트랜잭션은 여러 순서 중 하나로 직렬화될 수 있고, 논리 프로그램은 여러 안정 모델을 가질 수 있습니다. 고전적인 데이터 출처(provenance)는 이러한 상황에서 질문 자체를 제기할 수 없습니다—결과가 어떻게 도출되었는지는 설명하지만, 어떤 결과를 선택했는지 결정된 뒤에야 말이죠. 우리는 결정성 출처(determination provenance) 를 도입하여 이 모호성을 해소하는 약속(commitments)을 추적합니다. 튜플의 지원(support) 은 해당 튜플이 성립하는 모든 해결(resolution)의 집합이며, 지원들은 교환법칙을 만족하는 반(半)링(semiring)을 형성합니다. 그리고 계층화된 약속들은 필터레이션(filtration) 을 유도하여 각 튜플의 쿼리 상대 깊이(query‑relative depth) 를 측정합니다—즉, 그 튜플이 의존하는 의미적 해결의 레이어 수를 의미합니다. 양의 관계 대수(positive relational algebra)는 이 필터레이션을 보존하므로, 합성적 견고성 분석과 해결 비용의 정량적 진단이 가능해집니다. 우리는 이 프레임워크를 트랜잭션 격리와 $\mbox{Datalog}^\neg$에 적용했으며, 두 경우 모두 고전적인 의미론적 변형(격리 수준; 부정 의미론)이 하나의 공유된 필터레이션에 대한 서로 다른 시각에 해당함을 보여줍니다.
주요 기여
이 논문은 다음 분야의 연구를 제시합니다:
- cs.DB
- cs.DC
- cs.LO
방법론
자세한 방법론은 전체 논문을 참고하십시오.
실용적 함의
본 연구는 cs.DB 분야의 발전에 기여합니다.
저자
- Joseph M. Hellerstein
논문 정보
- arXiv ID: 2606.10270v1
- 분류: cs.DB, cs.DC, cs.LO
- 발표일: 2026년 6월 9일
- PDF: PDF 다운로드