Understanding Dataframe Operations Through Category Theory

Dataframe libraries like pandas offer a plethora of operations, often leading to confusion about their fundamental differences. My journey to build a new dataframe library led me to explore which operations are truly essential. This quest introduced me to Petersohn et al.'s work, which analyzed pandas usage across 1 million Jupyter notebooks and proposed a dataframe algebra comprising about 15 operators. This algebra compresses over 200 pandas operations into a more manageable set.

## Petersohn's Dataframe Algebra

Petersohn et al. formally defined a dataframe as a tuple (A, R, C, D), distinguishing it from a simple table by its ordered and labeled rows and columns. They identified operators like SELECTION, PROJECTION, and UNION, many of which have roots in relational algebra, while others like TRANSPOSE and MAP are unique to dataframes. Their analysis revealed that most pandas operations could be expressed as compositions of these operators.

## Schema Changes and Patterns

I noticed a pattern among the operators: some change the dataframe schema, while others affect only the rows. Schema-changing operations fall into three categories: restructuring (e.g., PROJECTION, RENAME), merging (e.g., GROUPBY, UNION), and pairing (e.g., JOIN). These patterns align with category theory concepts.

## Category Theory and Dataframes

Category theory, particularly as explained in Fong and Spivak's work, provides a framework for understanding dataframe operations. They describe three fundamental operations: Delta (Δ) for restructuring, Sigma (Σ) for merging, and Pi (Π) for pairing. These operations arise naturally from the relationships between schemas and are connected by an adjoint triple: Σ ⊣ Δ ⊣ Π.

## Beyond the Adjoint Triple

While the adjoint triple covers many operations, DIFFERENCE and DROP DUPLICATES require a different approach. These operations deal with subsets of rows within a schema and are better understood through the concept of a topos, which provides the necessary set-theoretic structure.

## Designing an API

The categorical decomposition informs the design of a dataframe API. Each operation should have a clear rule for computing its output schema. Migration functors handle schema changes, while topos-theoretic operations manage row-level changes. This structured approach allows for safe optimization and reordering of operations.

## Future Directions

The goal is to establish a canonical definition of the dataframe, grounded in theory. While this post focuses on relational operators, dataframe-specific operations like TRANSPOSE and the symmetry between rows and columns warrant further exploration. For those interested, Fong and Spivak's book and Petersohn et al.'s paper provide valuable insights.