관계 대수는 관계형 대수가 아닙니다

AI 요약

relational algebra와 relation algebra는 영어 이름에서 글자 두 개만 다르지만, 출발점과 쓰임이 다릅니다. 전자는 관계형 데이터베이스의 이론적 기반이고, 후자는 이항 관계를 다루는 수학적 대수 구조입니다. 두 개념을 혼동하는 사례가 많았으며, 글쓴이는 Wikipedia와 데이터베이스 분야의 Jamie Brandon까지 과거에 이를 구분하지 못했다고 지적합니다.

데이터베이스의 relational algebra

Edgar F. Codd는 1970년 논문 「A Relational Model of Data for Large Shared Data Banks」에서 관계형 데이터 모델을 제시했습니다. 2년 뒤 이 모델의 연산 체계에 relational algebra라는 이름을 붙였습니다. 관계형 데이터베이스에서 질의를 설명하고 분석하는 기반으로 쓰이는 대수입니다.

이 분야에서 잘 알려진 결과가 Codd's theorem입니다. 정리에 따르면 relational algebra는 domain-independent relational calculus와 표현력이 같습니다. domain-independent relational calculus는 1차 논리(first-order logic)로 작성한 질의 가운데 데이터베이스의 실제 도메인과 무관하게 동작하도록 제한한 형태입니다. 따라서 관계형 데이터베이스의 대수적 질의와 특정한 1차 논리 질의를 서로 대응시킬 수 있습니다.

수학과 논리학의 relation algebra

relation algebra는 논리학과 순수수학에서 공리 집합으로 정의하는 추상적 대수 구조입니다. 이 이름은 이항 관계(binary relation)를 대상으로 하는 구체적인 대수를 relation algebra 구조로 편리하게 모델링할 수 있다는 데서 나왔습니다. 데이터베이스용 relational algebra가 Codd의 관계형 모델에서 출발했다면, relation algebra는 관계 자체와 관계 연산을 공리적으로 다룹니다.

표현력에도 대응 관계가 있습니다. relation algebra는 1차 논리에서 서로 다른 변수를 최대 세 개만 쓰도록 제한한 FOL^3와 동등하다고 설명됩니다. 변수 수는 세 개로 제한되지만 양화사는 임의로 깊게 중첩할 수 있습니다. 여기에 fork operator를 추가하면 일반적인 1차 논리(first-order logic)와 같은 표현력에 도달할 수 있습니다.

컴퓨터과학에서도 쓰이는 relation algebra

두 대상을 각각 수학과 데이터베이스에만 속한다고 나누면 충분하지 않습니다. relation algebra는 컴퓨터과학의 형식 기법과 데이터베이스 이론에서도 쓰입니다. 대표적인 사례가 Alloy analyzer입니다. Alloy는 relation algebra를 relational logic이라고 부르며, Z notation의 계보를 잇는 도구입니다. Z notation은 Jean-Raymond Abrial이 만든 형식 명세 언어입니다.

글쓴이는 relation algebra를 데이터베이스 이론과 시스템에 적용해 온 연구자 집단도 소개합니다. Dirk Van Gucht를 중심으로 한 연구자들은 수십 년 동안 이 분야를 발전시켰습니다. 관련 문헌은 Prela query language에 관한 최근 논문에서 확인할 수 있다고 설명합니다. Prela는 relation algebra를 기반으로 만든 질의 언어이며, 글쓴이의 판단으로는 Van Gucht의 IUGQL 이후 처음 등장한 해당 계열의 질의 언어입니다.

TAR라는 새 이름

글쓴이는 relation algebra가 더 널리 알려져야 한다고 주장합니다. Alfred Tarski는 relation algebra를 “관계의 calculus는 그 본질적인 매력과 아름다움 덕분에, 이를 접한 사람에게 지적인 즐거움의 원천이 된다”고 표현했습니다. 다만 Tarski가 relation algebra를 또 다른 이름인 the calculus of relations라고 불렀다는 점도 혼동을 늘립니다. 이 표현은 데이터베이스 이론의 relational calculus와도 다릅니다.

혼동을 줄이기 위해 글쓴이는 앞으로 relation algebra를 Tarski's Algebra of Relations, 줄여서 TAR라고 부르기 시작했다고 말합니다. 이름은 다르지만 relational algebra와 relation algebra는 서로 다른 역사와 형식 체계를 가리키며, Alloy와 Prela 같은 사례를 보면 relation algebra는 순수수학에만 머물지 않습니다.

Lobsters 반응

커뮤니티 점수는 16점이며 댓글은 없습니다.

원문: Remy Wang 블로그 / 번역·요약: Trawling