Department of Mathematics
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.
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.
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
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
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
Table manipulation in simplicial databases. This short note exemplifies
the fact that the geometric structure of simplicial databases has concrete
meaning. On the arXiv.
theoretical databases. Simplicial databases from the perspective of
type theory. Joint with H. Forssell and H.R. Gylterud.
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
Database queries and constraints via lifting problems.
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
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
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.
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.
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
This work by David I. Spivak is licensed under a Creative Commons
Attribution-Share Alike 3.0 Unported License.