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, Sigma_F : S-inst -> T-inst, Pi_F : S-inst -> T-inst, and Delta_F : T-inst -> 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.

Previous work has demonstrated that categories are useful and expressive models for databases. In the current paper we build on that model, showing that certain queries and constraints correspond to lifting problems, as found in modern approaches to algebraic topology. In our formulation, each SPARQL graph pattern query corresponds to a category-theoretic lifting problem, whereby the set of solutions to the query is precisely the set of lifts. We interpret constraints within the same formalism, and then investigate some basic properties of queries and constraints. In particular, to any database π, we can associate a certain derived databaseQry(π) of queries on π. As an application, we explain how giving users access to certain parts ofQry(π), rather than direct access to π, improves the ability to manage the impact of schema evolution.

We show that the category of decomposition spaces and CULF maps is locally a topos. Precisely, the slice category over any decomposition space $\mathcal {D}$ is a presheaf topos, namely $\mathsf {Decomp}_{/\mathcal {D}}\simeq \mathsf {Psh}(\operatorname {tw} \mathcal {D})$ .

Automata are machines, which receive inputs, accordingly update their internal state, and produce output, and are a common abstraction for the basic building blocks used in engineering and science to describe and design complex systems. These arbitrarily simple machines can be wired together—so that the output of one is passed to another as its input—to form more complex machines. Indeed, both modern computers and biological systems can be described in this way, as assemblies of transistors or assemblies of simple cells. The complexity is in the network, i.e., the connection patterns between simple machines. The main result of this paper is to show that the range of simplicity for parts as compared to the complexity for wholes is in some sense complete: the most complex automaton can be obtained by wiring together direct-output memoryless components. The model we use—discrete-time automata sending each other messages from a fixed set of possibilities—is certainly more appropriate for computer systems than for biological systems. However, the result leads one to wonder what might be the simplest sort of machines, broadly construed, that can be assembled to produce the behaviour found in biological systems, including the brain.