Relational Foundations For Functorial Data Migration

MaRDI QIDQ6238207zbMATH OpenFDO

Authors David I. Spivak, Ryan Wisnesky

Publication date 20 December 2012

Mathematics Subject Classification ID

Logic in computer science (03B70) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40) Database theory (68P15)

Abstract: 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, $Sigm{a}_F:S$-inst$oT$-inst, $P{i}_F:S$-inst $oT$-inst, and $Delt{a}_F:T$-inst $oS$-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.

This page was built for publication: Relational Foundations For Functorial Data Migration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6238207)