범주론이 DataFrame에 대해 가르쳐주는 것 – Michael Chavinda – 내가 흥미를 느끼는 여러 주제에 대한 생각 모음.

Michael Chavinda

내가 흥미를 느끼는 여러 주제에 대한 생각 모음.

BlogAbout

범주론이 DataFrame에 대해 가르쳐주는 것

모든 dataframe 라이브러리는 수백 개의 연산을 함께 제공한다. pandas만 해도 DataFrame에 대한 메서드가 200개가 넘는다.

pivot

는

melt

와 다른가?

apply

는

map

와 다른가? 그렇다면

transform

,

agg

,

applymap

,

pipe

는 어떤가? 이들 중 일부는 서로 다른 모자를 쓴 같은 연산처럼 보인다. 다른 것들은 정말로 구별되는 것처럼 보인다. 이것들을 구분해 주는 틀이 없으면, 구조를 이해하는 대신 API를 외우게 된다.

나는 직접 dataframe 라이브러리를 만들면서 이 질문과 마주쳤다. 어떤 연산이 정말로 근본적인지, 어떤 것은 표면적인 변형에 불과한지 결정해야 했다. 그 탐색 끝에 Petersohn 등은 _Towards Scalable Dataframe Systems_에 이르렀다. 그들은 pandas를 대체할 수 있는 확장 가능한 drop-in 대체재인 Modin을 만들었고, 그러기 위해서는 API 아래에 있는 실제 구조를 이해해야 했다. 그들은 100만 개의 Jupyter 노트북을 분석하고, 사람들이 pandas를 어떻게 사용하는지 목록화한 뒤, _dataframe algebra_를 제안했다. 이는 pandas의 200개가 넘는 연산이 하는 일을 표현할 수 있는 약 15개의 연산자로 이루어진 형식적 집합이다.

그 대수는 엄청난 압축이었지만, 나는 그 아래에 또 다른 층이 있는지 계속 궁금했다. 그 15개를 구성하는 더 작고 진짜 원시적인 연산 집합이 있는지 말이다. 그런 것이 있다면 그것이야말로 진짜 토대일 것이다. 자명하게 옳다고 볼 수 있을 만큼 작고, 나머지 모든 것을 구성할 수 있을 만큼 표현력이 있는 연산들 말이다.

Petersohn의 dataframe algebra

이후의 모든 내용을 틀 지우기 때문에, Petersohn 등이 실제로 무엇을 했는지 잠시 살펴볼 필요가 있다.

그들은 먼저 dataframe이 무엇인지 정의하는 것부터 시작했다. 놀랍게도 그전까지 아무도 이것을 형식적으로 정의한 적이 없었다. 그들의 정의 4.1에 따르면 dataframe은 튜플 _(A, R, C, D)_이다. 여기서 _A_는 데이터 배열, _R_은 행 레이블, _C_는 열 레이블, _D_는 열 도메인의 벡터다. 이것은 “테이블”이라는 말보다 더 정확하다. 왜냐하면 relational table과 dataframe을 구별하는 점들을 포착하기 때문이다. 행과 열은 둘 다 순서가 있고, 둘 다 레이블이 있으며, 대칭적으로 다뤄진다. dataframe은 전치할 수 있다. 데이터 값을 열 레이블로 승격시킬 수도 있다. 이런 것은 SQL 테이블로는 할 수 없다.

그다음 그들은 연산자들을 식별했다. 그들의 표 1을 요약하면 다음과 같다.

“Origin” 열은 중요하다. 처음 아홉 개 연산자는 relational algebra에서 왔고 SQL에 직접 대응물이 있다. WINDOW는 SQL 확장에서 왔다. 마지막 네 개(TRANSPOSE, MAP, TOLABELS, FROMLABELS)는 dataframe에만 고유하다. dataframe은 행과 열을 대칭적으로 다루고, 값과 메타데이터 사이를 데이터가 오갈 수 있게 하기 때문에 이런 연산이 존재한다. relational database는 그렇게 할 수 없다.

Petersohn은 pandas API의 85% 이상이 이 연산자들의 합성으로 다시 쓸 수 있음을 보였다.

fillna

,

isnull

,

str.upper

,

cummax

같은 연산은 모두 MAP의 특수한 경우다.

sort_values

,

set_index

,

reset_index

,

merge

,

groupby

,

pivot

같은 연산은 모두 대수의 연산자와 일대일로 대응한다. 이는 거대한 압축이다. 200개가 넘는 임시방편적 메서드가 15개의 조합 가능한 원시 연산으로 바뀌는 것이다.

하지만 나는 그 표에 있는 relational 연산자들(PROJECTION, RENAME, GROUPBY, JOIN)을 계속 들여다보며 이렇게 생각했다. 이것들은 서로 관련되어 보인다. 모두 dataframe의 스키마를 바꾸기 때문이다. 더 깊은 관계가 있는 것 아닐까?

스키마 변화의 형태

Petersohn의 표를 충분히 오래 바라보고 있으면 패턴 하나가 드러나기 시작한다. 어떤 연산자는 스키마를 바꾼다. 즉, 어떤 열이 존재하고 그 타입이 무엇인지 바꾼다. 다른 연산자는 스키마는 그대로 두고 행에만 영향을 준다. 그리고 스키마를 바꾸는 연산자들에 집중해 보면, 그것들은 세 부류로 나뉜다.

재구성. 열을 재배열하거나 부분집합을 취하거나 이름을 바꾼다. 데이터는 그대로이고 형태만 바뀐다. SQL로 말하면

SELECT name, salary FROM employees

는 세 열짜리 테이블에서 두 열 결과를 만든다. dataframe 라이브러리에서는 다음과 같다.

select ["name", "salary"] df
-- 3-column schema → 2-column schema

rename "salary" "pay" df
-- Column name changes, data untouched

exclude ["department"] df
-- Drop a column

이것은 Petersohn의 PROJECTION과 RENAME을 포괄한다. 출력 스키마는 입력 스키마의 함수다. 어떤 데이터도 보지 않고 계산할 수 있다.

병합. 같은 키를 공유하는 행들을 하나의 요약이나 하나의 컬렉션으로 붕괴시킨다. SQL로는

SELECT department, AVG(salary) FROM employees GROUP BY department

이다. 라이브러리에서는 다음과 같다.

aggregate
    [ mean (col @Double "salary") `as` "avg_salary"
    , count (col @Text "name") `as` "headcount"
    ]
    (groupBy ["department"] df)
-- Schema: name, department, salary
--       → department, avg_salary, headcount

-- Or keep all values without reducing:
aggregate
    [ collect (col @Double "salary") `as` "all_salaries" ]
    (groupBy ["department"] df)
-- Each department gets a list of all its salaries

여러 행이 같은 키로 사상되어 결합된다. 이것은 Petersohn의 GROUPBY와 UNION을 포괄한다.

짝짓기. 두 테이블에서 공유된 키에 대해 일치하는 행을 찾아 더 넓은 행으로 꿰맨다. SQL로는

SELECT * FROM employees INNER JOIN departments USING (department)

이다. 라이브러리에서는 다음과 같다.

innerJoin ["department"] employees departments
-- Schema: (name, department, salary) + (department, budget)
--       → name, department, salary, budget

공유 키는 한 번만 나타나고, 각 쪽의 고유한 열은 이어 붙여진다. left join과 outer join도 같은 아이디어지만, 일치가 없을 수 있는 곳에 nullable 열이 들어간다는 점만 다르다. 이것은 Petersohn의 CROSS PRODUCT / JOIN을 포괄한다.

맞지 않는 것들. 두 relational 연산자는 이 묶음에 잘 들어맞지 않는다. SQL에서

SELECT * FROM employees EXCEPT SELECT * FROM contractors

는 한 테이블에는 있지만 다른 테이블에는 없는 행을 돌려준다. 그리고

SELECT DISTINCT * FROM employees

는 중복 행을 붕괴시킨다. 라이브러리에서는 다음과 같다.

distinct df
-- Same schema, fewer rows: removes duplicates

-- DIFFERENCE is not yet implemented, but the idea is:
-- difference employees contractors
-- Same schema, fewer rows: removes rows present in both

DIFFERENCE와 DROP DUPLICATES는 둘 다 어떤 행이 존재하는지를 바꾸지만, 열을 재구성하지도 않고, 키로 붕괴시키지도 않으며, 테이블 사이를 짝짓지도 않는다. 이들은 집합론적 느낌을 준다. 하나는 여집합을 계산하고, 다른 하나는 상을 계산한다. 우선은 이 둘을 제쳐두겠지만, 범주론적 그림이 더 선명해질 때 다시 등장할 것이다.

그래서 Petersohn의 relational 연산자 다섯 개(PROJECTION, RENAME, GROUPBY, UNION, JOIN)는 재구성, 병합, 짝짓기라는 세 패턴으로 깔끔하게 대응된다. 스키마를 보존하는 연산자(SELECTION, SORT, WINDOW)는 이에 직교한다. 그것들은 어떤 행을 볼지, 혹은 어떤 순서로 볼지를 바꾸지만 열 구조는 바꾸지 않는다. 그리고 dataframe 고유 연산자(TRANSPOSE, MAP, TOLABELS, FROMLABELS)는 relational 모델 바깥에 있다.

내게는 세 패턴과 두 개의 예외가 있었다. 하지만 왜 하필 이 세 패턴이어야 하는지에 대한 이유는 없었다. 재구성, 병합, 짝짓기가 정말로 근본적인가, 아니면 내가 우연히 그렇게 묶은 것뿐인가? DIFFERENCE와 DROP DUPLICATES는 어디에 속하는가? 이 모든 것을 예측하는 이론이 있는가?

내 멘토 Sam Stites는 Fong과 Spivak의 _Seven Sketches in Compositionality_를 읽어보라고 권하면서 나를 이 질문으로 이끌었다. 답은 범주론에서 나온다. 그 책 3장의 범주론은 구체적이고 데이터베이스에 가까운 버전이다. 추상 수학을 알 필요는 없다. 스키마가 무엇인지, 그리고 스키마를 바꾼다는 것이 무엇을 뜻하는지 신중하게 생각하면 된다.

왜 세 가지 migration functor가 있는가

구체적인 예시로 시작해 보자. 다음 두 스키마가 있다고 상상하자.

Employees: name, department, salary
Departments: department, budget

둘 사이에는 자연스러운 관계가 있다.

department

열은

Employees

에서

Departments

의

department

열을 참조한다. 이것이 foreign key다. 한 스키마에서 다른 스키마로 가는 사상이다. 각 직원 행은 어떤 부서 행 하나를 가리킨다.

그렇다면 이 사상으로 무엇을 할 수 있을까? Fong과 Spivak의 3장은 세 가지 근본 연산을 식별한다.

데이터를 다른 스키마에 맞게 제한할 수 있다.

{name, salary}

스키마는

Employees

의 부분집합이다.

select ["name", "salary"]

를 호출할 때 당신은 이렇게 말하는 셈이다. 전체 스키마 모양의 데이터는 있지만, 이 더 작은 스키마에 맞는 부분만 원한다. 데이터 자체는 바뀌지 않는다. 부분집합에 없는 열을 버릴 뿐이다.

이것을 일반화해 주는 것은 _스키마 사이의 사상_이라는 개념이다.

select

의 경우 그 사상은 “작은 스키마의

name

열은 큰 스키마의

name

에 대응하고,

salary

는 큰 스키마의

salary

에 대응한다”라고 말한다. 이것은 포함이다.

rename "salary" "pay"

의 경우 그 사상은 “새 스키마의

pay

는 옛 스키마의

salary

에 대응한다”라고 말한다. 이것은 재레이블링이다. 두 경우 모두, 스키마를 어떻게 번역할지 알려주는 사상이 있고 데이터는 그것을 따른다.

Fong과 Spivak은 이것을 **Delta (Δ)**라고 부른다. 스키마들 사이의 사상이 주어지면 Delta는 그것을 이용해 데이터를 재형성한다. 새로운 데이터를 만들어내거나 행을 결합하지는 않는다. 이미 있는 것을 재구성할 뿐이다.

병합을 통해 그 사상을 따라 데이터를 붕괴시킬 수 있다. 여러 직원이 같은 부서를 공유한다.

Departments

스키마 모양의 데이터, 즉 부서당 한 행의 데이터를 원한다면, 같은 부서를 가리키는 모든 직원을 어떻게 다룰지 결정해야 한다. 목록으로 모을 수도 있고, 급여를 합할 수도 있고, 인원을 셀 수도 있다. 이것이

groupBy ["department"]

뒤에 aggregation이 오는 경우다.

Fong과 Spivak은 이것을 **Sigma (Σ)**라고 부른다. 많은 원천 행이 같은 대상 행을 가리키는 사상이 주어지면 Sigma는 각 대상에 모이는 모든 것을 수집한다.

collect

함수는 모든 값을 목록으로 유지하는데, 이것이 순수한 Sigma다.

sum

이나

mean

을 쓰는 것은 그 수집 위에 fold를 합성하는 것이다.

두 스키마의 데이터를 짝지어 결합할 수 있다.

Employees

와

Departments

양쪽의 데이터가 주어졌다면,

department

에서 일치하는 행을 찾아 더 넓은 행으로 꿰맬 수 있다. 이것이

innerJoin ["department"] employees departments

다. 결과 행 각각은 공유 키를 기준으로 매칭된 두 테이블의 열을 모두 포함한다.

Fong과 Spivak은 이것을 **Pi (Π)**라고 부른다. 그들의 기억법은 “pair and query data”이며, 각주에는 “데이터베이스 프로그래머들은 보통 이것을 ‘join’이라고 부른다”라고 되어 있다. Pi는 공유 키가 부과하는 제약을 만족하는 모든 튜플을 찾는다.

그래서 앞 절의 세 패턴(재구성, 병합, 짝짓기)에는 이름이 있다. Δ, Σ, Π다. 하지만 이름 자체는 가장 흥미로운 부분이 아니다. 더 흥미로운 것은 왜 이 세 가지가 스키마 사상의 구조로부터 자연스럽게 나오는가 하는 점이다.

답은 스키마들이 서로 어떤 관계를 가지는가에 달려 있다. Fong과 Spivak은 스키마를 _categories_로 모델링하는데, 이는 그냥 “사물들(테이블, 열)의 모음과, 그것들 사이의 관계(foreign key), 그리고 관계의 사슬을 따라가는 규칙”을 정확하게 말하는 방식이다.

스키마의 _instance_는 여기에 실제 데이터를 할당했을 때 얻는 것이다. 각 테이블에 행의 집합을 배정하고, 각 foreign key에 대해 한 행을 그것이 참조하는 행으로 보내는 함수를 배정한다. 그래서

Employees

/

Departments

스키마의 instance는

{Alice, Bob, Carol}

라는 행들을

Employees

에,

{Engineering, Sales}

라는 행들을

Departments

에 할당하고, Alice → Engineering, Bob → Sales, Carol → Engineering으로 보내는 함수를 할당한다. 유일한 규칙은 일관성이다. 만약

Employees

가

Departments

를 참조하고,

Departments

가 다시

Location

을 참조한다면, Alice의 위치를 직접 찾는 것과 Alice의 부서를 찾은 뒤 그 부서의 위치를 찾는 것은 같은 답을 줘야 한다. 범주론에서는 이런 일관성 규칙을 만족하는 instance를 _functor_라고 부른다.

두 스키마 사이의 사상(이 또한 functor)이 주어지면, Fong과 Spivak은 그것이 이 세 가지 데이터 이동 연산을 유도함을 보인다. 이 셋은 _adjoint triple_이라는 구조로 연결된다.

Σ ⊣ Δ ⊣ Π

Sigma는 상세한 스키마에서 더 거친 스키마로 데이터를 옮기는 가장 관대한 방법이다. 모든 것을 취해 병합한다. Pi는 가장 보수적이다. 모든 공유 속성에서 일치하는 튜플만 남긴다. Delta는 반대 방향으로 가며, 데이터를 만들어내거나 결합하지 않고 제한만 한다. 이 수반 관계는 이 셋이 합성된다는 형식적 보장을 준다. 어떤 Δ 단계의 출력도 Σ나 Π 단계의 유효한 입력이 되고, 그 반대도 마찬가지다. 이것이 select를 join으로, join을 groupBy로 잇는 연쇄에서 스키마가 자연스럽게 맞아떨어지는 이유다.

adjoint triple이 다루지 않는 것

adjoint triple은 Petersohn의 일곱 relational 연산자 중 다섯 개를 설명한다. 하지만 앞에서 제쳐두었던 두 개, DIFFERENCE와 DROP DUPLICATES는 스키마 사상에서 전혀 나오지 않는다. 이들은 스키마 사이의 이동이 아니라 같은 스키마의 instance들 위에서 작동한다.

DIFFERENCE가 실제로 하는 일을 생각해 보자. 같은 스키마를 가진 두 dataframe이 있다고 하자.

all_employees:           terminated:
name   department        name   department
Alice  Engineering       Carol  Engineering
Bob    Sales
Carol  Engineering

DIFFERENCE는

all_employees

에 있으나

terminated

에는 없는 행, 즉 Alice와 Bob을 돌려준다. 스키마는 바뀌지 않는다. 행들의 집합만 바뀐다. DROP DUPLICATES는 하나의 dataframe 위에서 작동한다.

with_duplicates:         after distinct:
name   department        name   department
Alice  Engineering       Alice  Engineering
Bob    Sales             Bob    Sales
Alice  Engineering

동일한 행들을 하나로 붕괴시킨다. 다시 말해, 스키마는 건드리지 않는다.

이 둘은 어느 열이 존재하는지를 바꾸지 않는다. 고정된 스키마 안에서 어느 행이 존재하는지만 바꾼다. adjoint triple은 여기에 대해 할 말이 없다. Δ, Σ, Π는 스키마 사이에서 데이터를 이동시키는 것에 관한 것이기 때문이다. DIFFERENCE와 DROP DUPLICATES는 하나의 스키마 내부에서 행 부분집합에 대해 추론하는 것에 관한 것이다.

부분집합 위의 연산을 다루려면, 범주가 여집합과 교집합 같은 연산을 갖춘 “부분집합” 개념을 지원해야 한다. 모든 범주가 그런 것은 아니다. 하지만 스키마 위의 instance 범주는 그렇다. 각 테이블에 행의 집합을 할당하고 각 foreign key에 함수를 할당하면, 필요한 모든 집합론적 구조를 얻게 되기 때문이다. 범주론에서는 이런 종류의 구조를 가진 범주를 _topos_라고 부른다. 우리 목적에서 topos의 중요한 점은 부분집합을 다루는 도구를 갖추고 있다는 것이다.

• DIFFERENCE는 부분집합에 대한 여집합 연산이다. 두 행 부분집합 A와 B(같은 스키마를 가진 두 dataframe)가 주어지면, DIFFERENCE는 A에는 있지만 B에는 없는 행을 계산한다. topos는 이 여집합이 잘 정의되고 집합론에서 기대하는 방식으로 동작함을 보장한다.

• DROP DUPLICATES는 상(image) 연산이다. 각 행의 내용을 그 행의 정체성에서 값들로 가는 함수라고 생각해 보자. 여러 행이 같은 값들로 사상될 수 있다. DROP DUPLICATES는 이것들을 붕괴시켜 각 구별되는 값마다 대표 하나만 남긴다. topos는 모든 그런 함수가 자신의 상을 통해 깔끔하게 인수분해된다는 것을 보장하며, 바로 이것이 DROP DUPLICATES를 잘 정의되게 만든다.

그래서 relational 연산의 범주론적 그림은 두 층으로 이루어진다. 하나는 스키마 사이에서 데이터를 옮기는 migration functors(Δ, Σ, Π)이고, 다른 하나는 하나의 스키마 안에서 행 부분집합에 대해 추론하기 위한 topos structure다.

다음은 Petersohn의 연산자를 이 범주론적 틀에 대응시킨 전체 그림이다.

처음 다섯 연산자는 adjoint triple Δ, Σ, Π로 분해된다. 다음 두 개는 instance 범주의 topos 구조를 사용한다. 이 일곱 개가 함께 relational 핵심을 이룬다. 그다음 세 개는 스키마를 보존한다. 이것들은 스키마 사이의 이동이 아니라 같은 스키마 위의 instance들 사이의 사상이다. 마지막 네 개는 relational 모델 바깥에 있다.

이것이 압축이다. pandas 연산자 200개 → 대수적 연산자 15개 → relational 핵심을 덮는 3개의 migration functor와 2개의 topos-이론적 연산. 스키마를 보존하는 연산과 dataframe 고유 연산도 중요하지만, 복잡성이 사는 곳은 거기가 아니다. migration functor는 스키마 변경 연산을 다루고, topos 구조는 스키마 내부의 집합론적 추론을 다루며, 이 두 층은 합성된다.

이 패턴들을 중심으로 API 설계하기

그렇다면 실제로 dataframe 라이브러리를 만들고 있다면 이것이 무엇을 뜻할까? 범주론적 분해는 설계 원리를 하나 준다. 각 연산은 입력 스키마로부터 출력 스키마를 계산하는 명확한 규칙을 가져야 한다. migration functor는 스키마 자체를 바꾼다. topos-이론적 연산은 스키마는 유지하되 어떤 행이 존재하는지만 바꾼다.

먼저 migration functor부터 보자. Delta는 새 데이터를 계산하지 않고 스키마를 재형성하는 연산을 준다. 이는 다음을 뜻한다.

select columns

 → 출력 스키마는 이름 붙인 입력 열들의 부분집합
*   ```plaintext
exclude columns

→ 출력 스키마는 입력 스키마에서 이름 붙인 열들을 뺀 것

rename old new

 → 출력 스키마는 한 열의 레이블만 바뀐 입력 스키마

이 연산들은 공통 성질을 가진다. 입력 스키마와 연산 인자만 주어지면, 어떤 데이터도 보지 않고 출력 스키마를 계산할 수 있다. 그래서 값이 싸고, 예측 가능하며, optimizer에서 안전하게 재배열할 수 있다.

다음은 Sigma다. 키를 기준으로 행을 붕괴시키는 연산이 필요하다. 이는 다음을 뜻한다.

*   ```plaintext
groupBy keys

뒤에

aggregate [sum ..., mean ..., count ...]

→ 출력 스키마는 키 열들과 aggregation마다 하나씩의 새 열

groupBy keys

 뒤에 
```plaintext
collect

→ 출력 스키마는 키 열들과 list 값을 가진 열들

범주론적 그림이 주는 핵심 통찰은

collect

와

aggregate

가 같은 패턴의 변형이라는 점이다. Sigma는 각 키에 모이는 모든 것을 수집하고,

sum

이나

mean

같은 aggregation 함수는 그 위에 선택적으로 얹는 축약이다.

다음은 Pi다. 공유 키를 기준으로 두 스키마를 결합하는 연산이 필요하다. 이는 다음을 뜻한다.

innerJoin keys left right

 → 출력 스키마는 키 열(한 번만)과 양쪽의 비키 열
*   ```plaintext
leftJoin keys left right

→ 동일하지만 오른쪽의 비키 열이 nullable이 됨

fullOuterJoin keys left right

 → 동일하지만 양쪽의 비키 열이 nullable이 됨

각 join 변형은 일치하지 않는 경우를 처리하는 정책만 다를 뿐 Pi다. 스키마 규칙은 같고, 달라지는 것은 nullability 래핑뿐이다.

그다음은 topos 층이다. DIFFERENCE와 DROP DUPLICATES는 스키마를 보존하므로 스키마 규칙이 필요 없다. 이들의 타입 시그니처는 그것을 반영한다.

distinct :: TypedDataFrame cols -> TypedDataFrame cols -- difference :: TypedDataFrame cols -> TypedDataFrame cols -> TypedDataFrame cols

입력과 출력 타입은 동일하다. 바뀌는 것은 어떤 행이 존재하는가뿐이다. 
```plaintext
distinct

는 중복을 붕괴시키고,

difference

는 두 번째 인자에 나타나는 행을 제거한다. 둘 다 dataframe을 받아 같은 열이지만 더 적은 행을 가진 dataframe을 돌려주므로, 구현과 최적화에서 의미가 단순하다.

마지막으로 스키마를 보존하는 연산들(

filter

,

sort

,

take

,

sample

)은 migration 패턴과 topos 패턴 바깥에 놓인다. 이들의 출력 스키마는 항상 입력 스키마와 동일하다. 중요하긴 하지만 스키마 합성과 상호작용하지 않기 때문에 독립적으로 설계할 수 있다.

이 조각들을 갖추고 나면, 하나의 파이프라인은 migration 단계들(Δ, Σ, Π)과 행 수준 단계들(DIFFERENCE, DROP DUPLICATES, filter)의 연쇄가 되고, 각 단계의 출력 스키마는 다음 단계의 유효한 입력이 된다. dataframe 라이브러리에서는 Haskell의 타입 시스템이 이것을 강제한다. 스키마는 타입 수준에 인코딩되고, 컴파일러가 모든 전이를 검사한다.

type Employees =
    '[ Column "name" Text
     , Column "department" Text
     , Column "salary" Double
     ]

type Departments = '[ Column "department" Text, Column "budget" Double ]

result =
    employees
        & T.distinct                                -- topos: drop duplicate rows
        & T.innerJoin @'["department"] departments  -- Π: schema grows
        & T.derive @"cost_ratio"                    -- grows by one
            (T.col @"salary" / T.col @"budget")
        & T.select @'["department", "cost_ratio"]   -- Δ: schema shrinks
        & T.groupBy @'["department"]
        & T.aggregate                               -- Σ: collapse
            ( T.agg @"avg_ratio" (T.mean (T.col @"cost_ratio"))
            $ T.aggNil
            )

select

가

"salary"

를 제거한 뒤에 그것을 참조한다고? 컴파일 에러다. 이미 존재하는 열을 derive한다고? 컴파일 에러다. 한쪽 테이블에 없는 키로 join한다고? 컴파일 에러다. 파이프라인이 컴파일된다면, 모든 스키마 전이는 유효하다. 하지만 이 아이디어는 Haskell에만 해당하는 것이 아니다. 충분히 표현력 있는 타입을 가진 언어라면 같은 규칙을 강제할 수 있다. 범주론적 분해는 그 규칙이 무엇인지 알려주고, 타입 시스템은 단지 그것을 집행하는 수단일 뿐이다.

이 패턴들은 최적화에도 도움이 된다. 각 연산이 스키마에 정확히 어떤 일을 하는지 안다면, 언제 단계를 재배열해도 안전한지 추론할 수 있다. 라이브러리에는 실행 전에 파이프라인을 논리 계획으로 쌓아 올리는 지연 평가 모드가 있다.

optimize :: Int -> LogicalPlan -> PhysicalPlan
optimize batchSz =
    toPhysical batchSz
        . eliminateDeadColumns
        . pushPredicates
        . fuseFilters

연속된 filter는 하나로 합쳐진다. filter는 열 연산을 지나 데이터 소스 쪽으로 밀어 넣어진다. 아래 단계에서 결코 참조되지 않는 파생 열은 실행 전에 제거된다. 이런 재작성은 연산이 범주론적 구조에서 따라오는 대수 법칙을 따르기 때문에 안전하다. 재구성과 filtering은 filter가 재구성된 열을 건드리지 않을 때 교환 가능하다. predicate의 conjunction은 두 번 filtering하는 것과 같다. 한 열을 제거하는 Δ 단계는 그 열을 참조하지 않는 filter에 영향을 줄 수 없다.

이것이 향하는 곳

내가 궁극적으로 향하는 더 큰 그림은 dataframe의 정준적인 정의다. 내가 본 것 중에서는 Petersohn 등이 그들의 데이터 모델과 대수로 가장 좋은 시도를 했다. 범주론은 그 위에 대수적 구조를 더한다. 스키마 변경 연산을 위한 세 가지 migration functor가 수반관계를 통해 합성되고, 스키마 내부의 집합론적 추론을 위한 topos-이론적 장치가 있다. 둘을 합치면 dataframe algebra의 relational 핵심을 포괄한다.

라이브러리를 시작할 때 내가 원했던 것이 바로 이것이다. 이론에 기반한 작은 연산 집합과, 모든 단계를 검증하는 컴파일러. 이 글은 dataframe이 SQL과 공유하는 relational 연산자들을 다룬다. dataframe을 relational table과 다르게 만드는 TRANSPOSE, TOLABELS, FROMLABELS 같은 dataframe 고유 연산자와 행과 열 사이의 대칭성은 그 자체의 대수적 취급을 받을 가치가 있다. 하지만 relational 핵심에 대해서는, migration functor와 topos 구조라는 두 층의 범주론적 그림이 견고하게 느껴진다.

이 중 어떤 것이든 흥미롭게 들린다면, Fong과 Spivak의 Seven Sketches in Compositionality는 비수학자를 위해 쓰였고 가장 기초부터 시작한다. 3장은 데이터베이스와 Δ/Σ/Π migration functor를 다룬다. Petersohn 등의 Towards Scalable Dataframe Systems는 대수, 데이터 모델, 그리고 사람들이 그 100만 개 노트북에서 실제로 무엇을 하는지를 다룬다. 둘 다 읽을 가치가 충분하다.

dataframe 라이브러리는 GitHub에 있다. 타입이 있는 API는

DataFrame.Typed

에 있다. 이것으로 무엇을 만들게 될지 듣고 싶다.

Written on March 28, 2026