Relational Foundations For Functorial Data Migration

We study the data transformation capabilities associated with schemas that are presented by directed multi-graphs and path equations. Unlike most approaches which treat graph-based schemas as abbreviations for relational schemas, we treat graph-based schemas as categories. A schema $S$ is a finitely-presented category, and the collection of all $S$-instances forms a category, $S$-inst. A functor $F$ between schemas $S$ and $T$, which can be generated from a visual mapping between graphs, induces three adjoint data migration functors, ${\mathrm{\Sigma }}_F:S$-inst$\to T$-inst, ${\mathrm{\Pi }}_F:S$-inst $\to T$-inst,and$\Delta_F:T$-inst$\to S$-inst. We present an algebraic query language FQL based on these functors, prove that FQL is closed under composition, prove that FQL can be implemented with the select-project-product-union relational algebra (SPCU) extended with a key-generation operation, and prove that SPCU can be implemented with FQL.