David Spivak

Research Scientist
Department of Mathematics

Email: dspivak--math/mit/edu

Algebraic databases. Joint with Patrick Schultz, Christina Vasilakopoulou, Ryan Wisnesky. Here we understand attributes and null values in a database, using algebraic theories. The theoretical contributions include a notion of algebraic profunctor, a development of the collage construction, and a new proarrow equipment of "variable algebras" of a theory.

Functorial Data Migration. This was published in the journal Information and Computation in 2012. In this paper I show some of the power of the database=category idea: a morphism of schemas induces data migration functors that transmit states on one schema to states on the other. This creates such functionality as views, unions, joins, projects, selects, etc. An older version is here, and both are available on the arXiv. A 5-part video series (totalling ~1 hour) on roughly this subject can be found here.

On The Relational Foundations Of Functorial Data Migration. Joint with Ryan Wisnesky. A syntactic version of the above Functorial Data Migration paper, with more details about query composition, equivalences, and containment. On the arXiv.

Simplicial databases. A geometric model of databases. In this model, a "schema" for a database is a labeled simplicial set, whose n-simplicies correspond to tables with n+1 columns. We form a simplicial set by taking the union of such simplices, and doing so reflects the links between objects of differing types. The data itself is then a sheaf on the corresponding site. This category of databases is closed under limits and colimits and these functors correspond to common operations on databases, such as joins, selects, and unions. On the arXiv.
I gave a talk on this subject at the 2008 ATMCS meeting in Paris, and wrote a more brief survey of the ideas here. written out as a .pdf document.
A primitive version of this talk in which I only discuss the category of tables, was given as a colloquium in the University of Oregon computer science department. It can be found here.

Table manipulation in simplicial databases. This short note exemplifies the fact that the geometric structure of simplicial databases has concrete meaning. On the arXiv.

Type theoretical databases. Simplicial databases from the perspective of type theory. Joint with H. Forssell and H.R. Gylterud.

Higher-dimensional models of networks. In this paper, I make a case that many networks involve interactions between more than two entities, and as such should not be modeled by graphs but by simplicial sets. I give a variety of other models and suggest ways to determine which model is most applicable for a given situation, and how to transform models from one type into another. The paper is written mainly for a CS audience familiar with the basics of category theory. It can also be found on the arXiv. A more mathematical paper on networks and information processing is in the works.

Database queries and constraints via lifting problems. (Published by Mathematical structures in computer science.) In this paper I show that database queries and constraints, especially so-called "graph pattern queries", are nicely modeled in terms of the algebro-topological notion of lifting problems (which one encounters, for example, in Quillen's theory of model categories). The lifting problem is the query and the lifts are the solutions. Also available on the arXiv.

Kleisli database instances. Here we use monads to allow non-atomic values in database fields. For example depending on the choice of monad, a column may contain lists, probability distributions, or vectors of entries in some foreign table. As an interesting aside, we show that there is a schema Loop, whose Kleisli T-instances for different monads T completely capture classical structures of interest, such as directed graphs, discrete dynamical systems, Markov chains, multi-graphs, finite state automata, Turing Machines, and square matrices. Also available on the arXiv.

The operad of wiring diagrams. Here I discuss a symmetric colored operad S of wiring diagrams, which can be used as a graphical language for database queries. I also show that the same formalism fits the classical theory of digital circuits, as well as the notion of plug-and-play and recursion. Also available on the arXiv.

The operad of temporal wiring diagrams. Joint with Dylan Rupel. We discuss an operad of wiring diagrams, whose purpose is to formalize the hierarchical nature of processes. We prove that there is an algebra of stream processors. This may have applications to computer hardware design and neuroscience. Also available on the arXiv.

Algebras of open dynamical systems on the operad of wiring diagrams. Joint with Dmitry Vagner and Eugene Lerman. We show that open multivariable dynamical systems form an algebra on an operad of wiring diagrams. Also available on the arXiv.

Nesting of dynamic systems and mode-dependent networks. I show that you can build networks of dynamic systems, in which the dynamics can change the network architecture in real time. Also available on the arXiv.

Creative Commons License
This work by David I. Spivak is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.