DATABASE MIGRATION

Database Migration

[Name of the Institute]

Database Migration

Introduction

This paper has two main goals. The first goal is to present a straightforward category-theoretic model of databases under which every theorem about small categories becomes a theorem about databases. To do so, we will present a category Sch of database schemas, which has three important features:

the category Sch is equivalent to Cat, the category of small categories,

the category Sch is a faithful model for real-life database schemas, and

the category Sch serves as a foundation upon which high-level database concepts rest easily and harmoniously.

The second goal is to apply this category-theoretic formulation to provide new data migration functors, so that for any translation of schemas F : C ? D, one can transport instances on the source schema C to instances on the target schema D and vice versa, with provable “round-trip” properties. For example, homomorphisms of instances are preserved under all migration functors. While these migration functors do not appear to have been discussed in database literature, their analogues are well-known in modern programming languages theory, e.g. the theory of dependent types, and polynomial data types . This is part of a deeper connection between database schemas and kinds (structured collections of types) in programming languages.

An increasing number of researchers in an increasing variety of disciplines are finding that categories and functors offer high-quality models, which simplify and unify their respective fields.1 The quality of a model should be judged by its efficiency as a proxy or interface—that is, by the ease with which an expert can work with only an understanding of the model, and in so doing successfully operate the thing itself. Our goal in this paper is to provide a high-quality model of databases. Other category-theoretic models of databases have been presented in the past.

Almost all of them used the more expressive notion of sketch where we have used categories. The additional expressivity came at a cost that can be cast in terms of our two goals for this paper. First, the previous models were more complex and this may have created a barrier to wide-spread understanding and adoption.

Second, morphisms of sketches do not generally induce the sorts of data migration functors that morphisms of categories do. It is our hope that the present model is simple enough that anyone who has an elementary understanding of categories (i.e. who knows the definition of category, functor, and natural transformation) will, without too much difficulty, be able to understand the basic idea of our formulation: database schemas as categories, database instances as functors.

Categorical normal form

A database schema may contain hundreds of tables and foreign keys. Each foreign key links one table to another, and each sequence of foreign keys T1?T2?· · ·?Tn results in a function f from the set of records in T1 to the set of records in Tn. It is common that two different foreign key paths, both connecting table T1 to table Tn, may exist; and they may or may not define the same mapping on ...