Relational Databases and Indexed Categories

Robert Rosebrugh and R. J. Wood

ABSTRACT. A description of relational databases in categorical terminology given here has as intended application the study of database dynamics, in particular we view (i) updates as database objects in a suitable category indexed by a topos; (ii) L-fuzzy databases as database objects in sheaves. Indexed categories are constructed to model the databases on a fixed family of domains and also all databases for a varying family of domains. Further, we show that the process of constructing the relational completion of a relational database is a monad in a 2-category of functors.

Introduction

We use the term relation for a subobject of a finite product of objects in a category. Following the relational database literature, we use the term domain for an object of the ambient category (and warn readers that these are not the ordered objects which go by the name “domain” elsewhere in theoretical Computer Science.) A relational database, as defined by E. F. Codd [3], is first of all a family of relations (or tables) on a family of domains. A heavily used example of domain is the set of character strings over an alphabet. Thus domains should be logically permitted to be infinite, though in practice they are always finite sets, e.g. character strings up to a fixed maximum length. The theory of databases as families of relations views domains simply as discrete objects. We adopt that point of view for this paper though the domains of practice usually have at least an order structure.

A very brief example will serve to illustrate the concepts mentioned so far. We introduce three domains, name, address, phone, which can each be viewed as sets of character strings satisfying appropriate constraints. An example of a database on this family of domains is the family of two relations,

address-book, phone-book, where address-book is a subobject of name ×

address, and phone-book is a subobject of name × phone. Clearly, the storage and manipulation of databases is an important part of computing practise.

The theory of relational databases is well-developed, and the relational model for databases is now the most widely implemented. Earlier database paradigms (“network” and “hierarchical”) are still found in many older systems. They are not as amenable to theoretical treatment, do not provide a portable conceptual structure and are of decreasing interest. Moreover, there is active current research on enhancements and extensions of the relational model. Current editions of the texts by Date [4] or Ullman [18] contain pointers to this work.

Research partially supported by grants from NSERC Canada. Diagrams typeset using Catmac.

This paper is in final form and no verison of it will be submitted for publication elsewhere.

The theory of families we use is the theory of indexed categories as studied by Paré and Schumacher [13]. Indexed categories are a widely used categorical tool, but have only begun to be explicitly used in theoretical computer science relatively recently [6,7,12,16]. The “relational algebra” of relational database theory involves operations which are set-theoretic and other operations which can be defined by a language involving only constants, variables of domain or relation type and equality. An objective of this article is to construct the relational completion of a database as the action of a monad, so that relationally complete databases are algebras for this monad. Section 1 gives some examples, and then the construction of a required family. In Section 2 we describe databases as families of relations in an S-indexed category A and construct an indexed category of databases for a fixed family of domains. We then return to examples, including updates and fuzzy databases. Section 3 considers the effect of varying domains and attributes and finds an indexed category of all databases in an indexed category. In Section 4 we construct the relational completion monad. We find that the endo-functor part of the monad is an endo-functor on the fibration which arises from the indexed category of databases. Finally, we observe that relationally complete databases are 2-categories of relations.

1. The Setting

We will freely use the notion of indexed category, so we first describe the basic language of indexed categories. We begin with a base category, S, which is required to have finite limits. Moreover, for our description of database objects, S must allow construction of free monoids. It suffices to assume that S is an elementary topos with natural numbers object N. Appropriate examples of S include the category of sets and functions, set, any topos of diagrams (or presheaves), or any Grothendieck topos. A topos which will interest us below is set2, the topos whose objects are functions in set and whose arrows are commutative squares.

An S-indexed category A is given by a category A^{I} for each object I in S and a functor α^{∗} : A^{I} ⟶ A^{J} for each arrow α : J ⟶ I in S. These substitution functors α^{∗} are subject to isomorphisms making them compatible with identities and composition in S, and coherent with associativity. For example, if β : K ⟶ J is also in S, then there is a canonical isomorphism (αβ)^{∗} ≅ β^{∗}α^{∗}. For a complete description see [13].

We will often want A to be just S with a canonical indexed structure. We denote it by S with S^{I} defined to be the slice category S/I, and the required substitutions defined by pullbacks. We detail two examples of S now.

Example 1. When we take S to be the category set, we find that the set-indexed category set has, for any set I, ordinary I-indexed families of sets as its I-indexed families. This follows since set/I has functions with codomain I as objects. Such a function, x : X ⟶ I say, may be identified with a family of sets < X_{i} >_{i∈I} defined by X_{i} = x^{−1}(i), and conversely. In fact any category is set-indexed, again taking I-indexed families to be just ordinary families of objects.

Example 2. When S is set2 we get a more interesting indexing. The indexing objects are now functions in set, e.g. I : I_{0} ⟶ I_{1}, and an I-indexed family X, being an arrow of set2, is a pair of functions x_{0} : X_{0} ⟶ I_{0}, x_{1} : X_{1} ⟶ I_{1} making a commutative square in set, x_{1}X = Ix_{0}. Substitutions are defined by pullback which are computed point-wise.

Example 3. Another example of a set2-indexed category arises when we allow the object X above to be replaced by a partial function, which we will denote X : X_{0} [figure]X_{d} ⟶^{X} X_{1}. Thus, when I = 1 we obtain the category whose objects are partial functions and whose morphisms, from X to Y say, are pairs of functions f_{0} : X_{0} ⟶ Y_{0} and f_{1} : X_{1} ⟶ Y_{1} such that the restriction of f_{0} to X_{d} factors through Y_{d} by f_{d} and Y f_{d} = f_{1}X. An I-indexed family is a pair X_{0} ⟶^{x_{0}} I_{0}, X_{1} ⟶^{x_{1}} I_{1} so that x_{1}X = Ix_{d} — with x_{d} the restriction of x_{0} to X_{d}. A morphism in I-indexed families is a pair (f_{0}, f_{1}) of functions so that in

[figure: y_{0}; Y_{0}; f_{0}; X_{0}; I_{0}; x_{0}; y_{1}; Y_{1}; f_{1}; X_{1}; I_{1}; I; X_{d}; Y_{d}; X; Y]

f_{0} restricts to f_{d} : X_{d} ⟶ Y_{d} and f_{1}X = Y f_{d}. Substitution is still accomplished by pointwise pullback, including on the domain of full definition, X_{d}. We denote the resulting indexed category by set^{pf}.

We want to define a relational database to be a J-indexed family of relations in A on some I-indexed family of domains, say A. A central feature of indexed category theory is that it identifies a J-indexed family of structures as a structure in the category of J-families, e.g. a J-indexed family of groups is a group in J-families. Similarly, a J-indexed family of relations is a single relation in the category A^{J} of J-indexed families. To define relational database in A we need to be able to say when a J-indexed family of relations is a family of subobjects of finite products of domains in A. In order to make this requirement precise, we will need some notation and some hypotheses on A. The remainder of this section provides this background.

For an object I of S we denote the free monoid on I by M(I). Henceforth we assume that M(I) exists in S. It is well known that M(I) exists in any topos with a natural numbers object [10,13]. We also need to assume, and do so for the remainder of this paper that A has finite products. This requires that each A^{I} has finite products preserved by the α^{∗}. If A is an object of A^{I}, we will need the M(I)-indexed family of “finite products of members of A”, denoted P_{0}(A). When S is set the family desired has as fibre over a word w = i_{1}i_{2} … i_{k} ∈ M(I), the (finite) product whose description is A^{w} = A_{i_{1}} ×A_{i_{2}} ×…×A_{i_{k}}. We conclude this section by finding sufficient conditions for the existence of P_{0}(A).

Under suitable hypotheses, the required family of finite products can be constructed as a solution to a “recursion problem” [15] for the indexed functor “crossing with A”. We recall that, for S-indexed categories A and B, an indexed functor F : A ⟶ B is a family of functors F^{I} : A^{I} ⟶ B^{I}, one for each I in S. Further, for any arrow α : J ⟶ I in S, we must have the squares

[figure: A^{J}; B^{J}; F^{J}; A^{I}; B^{I}; F^{I}; α^{∗}; α^{∗}]

commuting up to coherent isomorphism. A recursion problem on A is a pair (Φ, C_{0}) with Φ an indexed endofunctor of A and C_{0} in A^{1}. The recursion problem (Φ, C_{0}) has a solution if there is an object C in A^{N} such that 0^{∗}C = C_{0} and s^{∗}C = Φ^{N}C.

An hypothesis we shall need on A is that it has an indexed functor E : A ⟶ S with small fibres. An indexed functor E has small fibres, when the objects of A^{I} whose image under E^{I} is a given object of S^{I} form a family indexed by an object of S/I. An indexed functor with codomain S and small fibres was called an “e-functor” in [15]. The name refers to “elements” since the idea is that E^{I} gives a (very rough) idea of the cardinality of an object in A^{I}. Examples include the identity functor on S and forgetful functors from (the S-indexed) category of groups (in S.) More interesting, any category of sheaves has an e-functor to set given by taking the union of all sections.

In the proposition which follows, we use a basic technique of indexed category theory “localizing” at M(I). That is, we use the S/M(I)-indexed category A^{M(I)}, whose σ-indexed families, for σ : J ⟶ M(I), are defined by (A^{M(I)})^{σ} = A^{J}. The hypotheses on the indexed category A remain true for A^{M(I)}, and allow us to construct the required object there. We denote the inclusion of generators I in the monoid M(I) by η. The internal sum of A in A^{I} along η is denoted Σ_{η}A. When S is set, Σ_{η}A is the M(I) family with fibre A_{i} over i and empty elsewhere.

Proposition 1. Let S be a topos with NNO and A an S-indexed category with an e-functor E : A ⟶ S. Suppose that A has finite products and that the canonical arrows E^{I}(A × B) ⟶ E^{I}(A) × E^{I}(B) are all monic. Suppose that A is in A^{I} and Σ_{η}A exists. Then the recursion problem (Φ, 1), where Φ : A^{M(I)} ⟶ A^{M(I)} is defined by Φ(C) = C × Σ_{η}A, has a solution.

Proof. We first localize E to E^{M(I)} : A^{M(I)} ⟶ S^{M(I)}, and note that the canonical arrows are still monic. Now we can invoke Proposition 2.2 of [15] as soon as we show that Φ is mono-bounded, i. e. for all C in A^{M(I)} there is a B in S/M(I) such that (i) E^{M(I)}(C)[figure] B;

(ii) for all C′ in (A^{M(I)})^{σ}, if E^{σ}(C′)[figure] B then E^{σ}(Φ^{σ}C′)[figure] σ^{∗}B.

We let B = Ω^{(E(C)+E(Σ_{η}A)+2)}^{N} where Ω is the subobject classifier in S/M(I). Then using the coproduct injection and singleton, E(C)[figure] B is clear and

E(ΦC′) = E(C′ × Σ_{η}A)[figure] E(C′) × E(Σ_{η}A)[figure] B × B[figure] B.

The last monomorphism, whose existence is guaranteed by Lemma 2.2.3, Chapter 5 of [13], localizes to (S/M(I))^{σ} giving (ii).

2. A Categorical Model for Databases

For this section we assume that S is a topos with NNO and A is S-indexed and has finite products and an e-functor to S. The scheme of a relation in a database is the list of attributes ( = names of domains) appearing in the relation, that is, if A in A^{I} is an I-indexed family viewed as a family of domains, the scheme of a relation is in M(I). A database with J relations and (database) signature σ : J ⟶ M(I) is as follows:

Definition 1. Let A in A^{I} be a family of domains. An A-database with database signature σ, where σ : J ⟶ M(I), is a relation R : R_{0} [figure] σ^{∗}P_{0}(A) in A^{J}.

Remarks. The signature σ of a database should not be confused with the scheme of a relation in the database. When A = S = set, the schemes of the relations in the database, R_{j} for j ∈ J, are elements of M(I) given by the signature, σ : J ⟶ M(I).

As J and σ vary we obtain databases with varying families of relations. From this variation we will find a category of databases below.

The category S/M(I) is the base for indexing below, but we wish to also note that the full subcategory of set/M(I) whose objects are those J ⟶ M(I) with J finite is of important practical interest, for these objects are signatures of databases in set with finitely many relations. However, this subcategory fails to have a terminal object. (In fact the terminal object in S/M(I) is 1_{M(I)} : M(I) ⟶ M(I), whose domain is essentially never finite.) The subcategory is thus unsuitable as a base category for indexing as arguments by localization become impossible.

For any object σ : J ⟶ M(I) of S/M(I), we define D(A)^{σ} to be the partial order, hence category, of subobjects of σ^{∗}P_{0}(A). If α : σ′ ⟶ σ is an arrow of S/M(I), i.e. σα = σ′ : J′ ⟶ M(I), define α^{∗} : D(A)^{σ} ⟶ D(A)^{σ′} using substitution in A.

Proposition 2. Assume that all the functors α^{∗} preserve monomorphisms. The D(A)^{σ} determine an S/M(I)-indexed category denoted D(A).

Proof. We merely note that to R : R_{0} [figure] σ^{∗}P_{0}(A), we have α^{∗}R defined by

α^{∗}R_{0} [figure] α^{∗}σ^{∗}P_{0}(A) ≅ σ^{′∗}P_{0}(A).

Checking functorality of α^{∗} and the equations is routine.

Remarks. The indexed category of databases which we denote D(A) above is locally a poset; in fact, it is the indexed category sub(P_{0}(A)) described in [13], and when A = S it is internally complete and cocomplete. Below we will consider subcategories arising by restricting the morphisms of D(A).

Except for Example 3, where we will comment in more detail, we may take the identity functor as e-functor in the examples below. Thus all conditions of Proposition 1 are easily met. The substitution functors below are all defined by pulling back, so the conditions of Proposition 2 are met in all of the examples.

Example 1 - continued. Once again, let S = set and A = set. We note that for any family < A_{i} >_{i∈I} of sets, P_{0}(A) is the family of finite products of the A_{i}. When I, all of the A_{i} and J are finite, a database according to Definition 1 coincides exactly with the usual definition of a relational database with I domains < A_{i} >_{i∈I} and J relations. That is, we have not lost anything by considering the setting proposed. We have gained a definition of morphism of databases — here just an inclusion, and further a definition of substitution along a function ϕ : K ⟶ J, say. This substitution with ϕ monomorphic, for example, defines a database from a subset of the current relations. It might define an authorization class for example.

Example 2 - continued. For an object A in (set2)^{I}, the object P_{0}(A) is constructed “pointwise” i.e.

[figure: M(I_{0}); M(I_{1}); M(I); P_{0}(A_{0}); P_{0}(A_{1}); P_{0}(A); p_{0}; p_{1}]

where to (a_{i_{1}},…, a_{i_{k}}) ∈ p_{0}^{−1}(i_{1} … i_{k}) we have

P_{0}(A)(a_{i_{1}},…, a_{i_{k}}) = (A(a_{i_{1}}),…, A(a_{i_{k}})) ∈ p_{1}^{−1}(M(I)(i_{1} … i_{k}))

Thus a database object with J : J_{0} ⟶ J_{1} relations arises from a diagram such as the following:

[figure: J_{0}; J_{1}; σ^{∗}P_{0}(A_{0}); σ^{∗}P_{1}(A_{1}); M(I_{0}); M(I_{1}); M(I); P_{0}(A_{0}); P_{1}(A_{1}); R_{0}; R_{1}; R_{0}; R_{1}; R]

That is, it consists of an A_{0} database, R_{0}, in set with J_{0} relations, an A_{1} database, R_{1}, in set with J_{1} relations and a function R : R_{0} ⟶ R_{1} so that a tuple a = (a_{l_{1}},…, a_{l_{k}}) in the j’th relation of R_{0} has R(a) in the J(j)’th relation of R_{1}. Thus R itself is a rather general morphism of databases in that the domains, relations and attributes are allowed to be fully variable. This notion of database morphism will be encountered again in the next section. Restricting A and I to be identity functions, and similarly J, provides a simpler notion of database morphism. We exploit such restrictions in the next example.

Example 3 - continued. Again letting S = set2, but now with A = set^{pf}, we obtain rather complicated objects similar to those in Example 2 as databases, but restricting attention to special cases will provide a description of the notion of “update”. First, in order to guarantee that P_{0}(A) exists we define an e-functor E : A ⟶ S as in Proposition 1. If a_{0} : A_{0} ⟶ I_{0}, a_{1} : A_{1} ⟶ I_{1} is an object of A^{I} with domain A_{0} [figure]A_{d} ⟶ A_{1}, we define E^{I}(a_{0}, a_{1}) by

[figure: I_{0}; I_{1}; I; A_{0}; A_{1} + I_{1}; A^{+}; a_{0}; a_{1}^{+}]

where A^{+} is the canonical extension of A : A_{d} ⟶ A_{1} given by viewing A as an I_{1}-indexed family of functions in set viz,

⟨Σ_{I(i_{0})=i_{1}}(A_{d})_{i_{0}} ⟶ (A_{1})_{i_{1}}⟩_{i_{1}∈I_{1}}

and since (A_{d})_{i_{0}} [figure] (A_{0})_{i_{0}} we may extend the I_{1}-family canonically to

⟨Σ_{I(i_{0})=i_{1}}(A_{0})_{i_{0}} ⟶ (A_{1})_{i_{1}} + 1⟩_{i_{1}∈I_{1}}.

Then a_{1}^{+} is defined on A_{1} + I_{1} using a_{1} and the identity on I_{1}. The E^{I} define an indexed functor E : A ⟶ S with small fibres. We omit the technicalities of proving this. With this definition of E it is easy to see that E^{I}(A × B)[figure] E^{I}(A) × E^{I}(B). Moreover, Σ_{η}A exists as internal sums are inherited from set2. So the requirements of Proposition 1 are met. The experienced reader will have noted that P_{0}(A) could have been constructed directly in the case at hand. The point of the construction given is that it can be carried out for S^{pf} for any topos S with NNO. In that case, a_{1}^{+} : A_{1} + I_{1} ⟶ I_{1} above is replaced with the partial morphism classifier [8] for a_{1} in S/I_{1}.

An update of a database which does not change the current family of relations is one or several of three possible actions on elements ( called “tuples”) of the current relations:

(i) delete a tuple from a relation (ii) add a tuple to a relation (iii) change the values of some components of a tuple. In fact, the third action can clearly be accomplished by a combination of the first two actions, namely delete the tuple in its current state and add it in the new state. Thus, an update can be accomplished by specifying a subset of current tuples which will be unchanged by the update (i.e. deleting the tuples to be changed or deleted) and specifying tuples to be added. In short, it is specified by a partial monomorphism whose domain is the current set of tuples, whose subset of total definition is the set of unchanged tuples, and whose function part is a monomorphism on that subset. Now let us describe the database objects in set^{pf} which express updates. For simplicity, we assume that the family of domains and the database signature are constant. That is, we assume that I and J in set2 are identity functions, and A in (set^{pf})^{I} has a fully defined identity function as its domain. In this special case, consider the diagram below for a database r with signature σ : J ⟶ M(I). In the diagram following we denote the domain of σ^{∗}P_{0}(A) by P.

[figure: P; r_{0}; R_{0}; J; P; r_{1}; R_{1}; J; =; R_{d}; i_{R}; R; P; =; =; r_{d}]

We see that since r_{0} and i_{R} are monic, r_{d} is monic and then R is too as r_{1}R = r_{d}. The conclusion is:

a database object in set^{pf} is an update of a database object in set.

It follows from this conclusion that we can reason about updates by reasoning about mere database objects in set^{pf}.

Example 4. Let us denote by ω the category freely generated by the graph

0 ⟶ 1 ⟶ 2 ⟶ . . ..

set^{ω} is a topos whose objects are diagrams

X : X_{0} ⟶^{x_{0}} X_{1} ⟶^{x_{1}} X_{2} ⟶^{x_{2}} …

with X_{i} sets and x_{i} functions, and which can be thought of as X varying in discrete time steps encoded in the x_{i}. An analysis similar to that in Example 2 shows that a database object in set^{ω} is a sequence R_{0}, R_{1},… of databases in set, and the general morphisms of them discussed in Example 2. Restrictions to constant attribute families and relation signatures (the σ’s of Definition 1) again provide a description of a database’s variation through discrete time steps.

An important class of elementary topos is the categories of sheaves on a topological space, or more generally a locale. All base categories S above are of this form. Categories of fuzzy sets, after appropriate completion for fuzzy equality, are categories of sheaves on a locale, as Barr [1] has explained.

Example 5. Let L be a locale. Following Barr, we will denote by L^{+} the locale L with a new bottom element adjoined. Then ( the completion for fuzzy equality of ) L-fuzzy sets is the category of sheaves on L^{+}, sh(L^{+}). It is thus appropriate to define an L-fuzzy database to be a database object in sh(L^{+}). With this definition, we note that Examples 1 and 2 above are special cases; Example 4 can be modified to set^{ω+1}, where ω + 1 is 0 ⟶ 1 ⟶ … ω.The topos set^{(ω+1)^{+}} is of the form sh(L^{+}). It is worth emphasizing that, with the definition we give here, an L-fuzzy database has not only fuzzy relations, but also fuzzy domains and fuzzy index objects for its family of relations. Compare [14].

3. More indexed categories of databases

We have concentrated on a fixed (I-indexed) object A in the discussion above. It is clear that variation of A within A^{I}, and further, variation of I, will define more indexed categories of databases. We have already seen such morphisms for the case S = set. They appeared as objects with variable attribute families and indexes for them, together with their associated databases in set2. We indicate a few definitions:

Let f : B ⟶ A be a morphism of A^{I}. The arrow f determines an arrow of A^{M(I)} which we denote P_{0}(f) : P_{0}(B) ⟶ P_{0}(A). For signatures σ : J ⟶ M(I) and τ : K ⟶ M(I) we have a morphism between them in S/M(I) when there is ν : J ⟶ K satisfying τν = σ. Now we define a category D(A)^{I} as follows. Objects are triples (A, σ, R) with R an A-database with signature σ. An arrow from (A, σ, R) to (B, τ, R′) is a pair (f : A ⟶ B, ν : σ ⟶ τ) such that σ^{∗}P_{0}(f) restricted to R factors through ν^{∗}R′ as in the following (recall that we assume substitution preserves monics):

[figure: R; ν^{∗}R′; ϕ; σ^{∗}P_{0}(A); ν^{∗}τ^{∗}P_{0}(B); σ^{∗}P_{0}(f); = σ^{∗}P_{0}(B); .]

Thus, when S = set for example, we are requiring that for any r ∈ R,ϕ_{j}(r) = (σ^{∗}P_{0}(f))_{j}(r) lies in (ν^{∗}R′)_{j} = R′_{ν(j)}. Since f determines ϕ, our description of arrows is appropriate.

Now suppose α : J ⟶ I is an arrow of S. We obtain a functor α^{∗} : D(A)^{I} ⟶ D(A)^{J} when we define

α^{∗}(A, σ, R) = (α^{∗}(A), σ′, R′)

where α^{∗}(A) refers to the indexed structure on A, R′ = (M(α)′)^{∗}R, and the following is a pullback:

[figure: M(J); M(I); M(α); J′; J; M(α)′; σ′; σ]

Proposition 3. The categories D(A)^{I} and functors α^{∗} determine an Sindexed category, denoted D(A).

Proof. All that remains after the construction above is to verify that the D(A)^{I} are categories and that the α^{∗} are functorial and compatible with identities and composition. This is a good exercise in the definitions of indexed category.

4. Relational Completion is a Monad

The information obtained by querying a relational database is presented as relations. The relations which present the information derived are obtained by operating on the “base tables” or stored relations. The operations are collectively known as the “relational algebra” and depend on the schemes of stored relations as well as on the constants in the family of domains for the database. Simple examples of the operations are “list tuples in either of two relations” (union), “list the cartesian product of two relations”, “list tuples whose value in one attribute equals their value in another” (selection.) The reader will have noted that combining the latter two sorts of operations allows formation of pullbacks. We will say that a database is relationally complete if it is closed under the operations of relational algebra. Of course, a relationally complete database can never be physically stored, having at least countably many relations. Thus, the ability to present any relation in the relational completion of a physically stored database is an important objective for a database system. Our objective in this section is to show that constructing the relational completion of database objects on a family of domains is a monad in a suitable 2-category, and that relationally complete databases are precisely algebras for this monad. Until further notice, we assume that our databases are in set, though much of what we say holds for databases in indexed categories satisfying the hypotheses of Proposition 1 by having A = S. Various families of binary and unary operations on the relations in a database have been called the “relational algebra”. We describe a simple family of them namely two boolean operations, cartesian product, projection and selection. We remark that the other common operations, with the exception of difference, may be derived from those mentioned below [11]. We are unable to handle the binary difference of relations operation in our setup. Unlike the other operations of relational algebra we use here, it is not monotonic. This spoils functoriality of relational completion and that is too high a price to pay. We make some further remarks about this difficulty below.

The boolean operations are the simplest to describe. To do so, suppose that R : R_{0} [figure] σ^{∗}P_{0}(A) is an A-database with signature σ : J ⟶ M(I) and r, s are relations in R with the same scheme i.e. for some j_{1}, j_{2} : 1 ⟶ J we have r = j_{1}^{∗}(R_{0}), s = j_{2}^{∗}(R_{0}) and σj_{1} = σj_{2} so r, s[figure] (σj_{1})^{∗}P_{0}(A). Then r ∪ s, r ∩ s[figure] (σj_{1})^{∗}P_{0}(A) are relations with scheme σj_{1}. Next we consider cartesian product. If r[figure] (σj_{1})^{∗}P_{0}(A) and s[figure] (σj_{2})^{∗}P_{0}(A) then r × s[figure] (σj_{1} · σj_{2})^{∗}P_{0}(A) where σj_{1} · σj_{2} denotes product in M(I) of σj_{1}, and σj_{2}.

Projection and selection require a little more care. Suppose that j : 1 ⟶ J and that r[figure] (σj)^{∗}P_{0}(A). Since σj is a word of length n : 1 ⟶ N, say, we may view the word as σj : [n] ⟶ I. Now let φ : [n′][figure] [n] be one-one. The projection of r along φ, denoted π_{φ}r is the (n′-ary) relation obtained by “projecting on the n′ columns specified by φ.” Finally, for j and r as above, and viewing σj as σj : [n] ⟶ I, suppose that σj(i_{1}) = σj(i_{2}) ∈ I and c ∈ A_{σj(i_{1})}. The selection operators S_{i_{1}=i_{2}}(r) and S_{i_{1}=c}(r) are defined by equalizers with codomain r as follows:

[figure: S_{i_{1}=i_{2}}(r); r; (σj)^{∗}P_{0}(A); A_{σj(i_{1})}; π_{i_{1}}; π_{i_{2}}]

and

[figure: S_{i_{1}=c}(r); r; (σj)^{∗}P_{0}(A); A_{σj(i_{1})}; π_{i_{1}}; 1; c]

Before proceeding, to establish notation, we give a brief description of 2categories. The standard reference is [9]. A 2-category B consists of a class of objects, denoted B_{0}, and for each pair B, C of objects, a hom category, denoted B(B, C), whose objects are called 1-cells, and whose arrows are called 2-cells. We denote a 2-cell by σ : f ⟹ g in B(B, C). Composition of 2-cells in B(B, C) is called vertical composition. There is also a horizontal composition of 2-cells defined by a functor B(C, D) × B(B, C) ⟶ B(B, D) for each triple B, C, D of objects of B. An identity 1-cell in B(B, B) for each object B completes the necessary data. The data are required to satisfy associativity of horizontal composition, neutrality of identity arrows for horizontal composition and an interchange law linking horizontal and vertical composition. We generally denote vertical composition by juxtaposition or · , and horizontal composition by ∘. The interchange law, for example, states that for

[figure: ⇓; B; C; ⇓; C; D; ⇓; ⇓; σ; σ′; τ; τ′]

we have (τ′ · τ) ∘ (σ′ · σ) = (τ′ ∘ σ′) · (τ ∘ σ). The motivating example of a 2-category is cat, the 2-category with categories as objects, functors as 1-cells and natural transformations as 2-cells. Another important example is rel, the 2-category of relations. The objects of rel are sets. If B and C are sets, then the category rel(B, C) is the partial order, qua category, of relations from B to C, so vertical composition is trivial and horizontal composition is the usual composition of relations. It is defined on 2-cells since if R ⊆ R′ : B ⟶ C and S ⊆ S′ : C ⟶ D are relations then SR ⊆ S′R′. The interchange law follows since all equations among 2-cells in rel are trivial: inclusion either holds or it doesn’t.

We next describe the 2-category cat2 in which we will work below. The objects of cat2 are functors. If A : A_{0} → A_{1} and B : B_{0} → B_{1} are functors a 1-cell F : A → B is a triple F = (F_{0}, F_{1}, Φ) where F_{0} : A_{0} → B_{0} and F_{1} : A_{1} → B_{1} are functors and Φ : BF_{0} ≅ F_{1}A is a natural isomorphism. A 2-cell τ : F ⟹ G : A → B, with G = (G_{0}, G_{1}, Γ), is a pair of transformations τ_{0} : F_{0} ⟹ G_{0} and τ_{1} : F_{1} ⟹ G_{1} such that Γ·(τ_{1}∘A) = (B∘τ_{0})·Φ. Verification that the obvious compositions of 1- and 2- cells provide a 2-category is left to the reader.

For any S-indexed category A there is a functor with codomain S called the Grothendieck construction for A. We denote this functor G_{A} : gr(A) → S and briefly describe it. The objects of gr(A) are pairs (I, A) with A an object of A^{I}. The hom-sets are defined by the formula gr(A) ((I, A), (J, A′)) = {(α, φ) |I →^{α} J, A →^{φ} α^{∗}A′ } . The functor G_{A} is given on objects and arrows by projecting on I and α. In fact, G_{A} is a fibration [5].

We can now proceed to describe the relational completion monad. We recall that a monad in a 2-category is a 1-cell with a monoid structure given by “unit” and “multiplication” 2-cells [17]. Thus in cat2 a monad is an arrow of cat2 together with unit and multiplication 2-cells. We note that a monad on A : A_{0} ⟶ A_{1} in cat2 is specified by a monad M_{0} in cat on A_{0}, a monad M_{1} in cat on A_{1} and a 2-cell M : M_{1}A ≅ AM_{0}. These must satisfy equations involving the structures of the given monads in cat and M.

The domain of our monad C is the Grothendieck construction for the S/M(I)-indexed category D(A), which is denoted G_{D(A)} : grD(A) ⟶ S/M(I).

Thus, the monad C = (C^{0}, C^{1}, Γ) requires functors C^{0} : grD(A) ⟶ grD(A), C^{1} : S/M(I) ⟶ S/M(I) and a transformation Γ : C^{1}G_{D(A)} ⟹ G_{D(A)}C^{0}.

The second functor C^{1} is inductively defined and we describe it first. Its action on a database signature σ : J ⟶ M(I) produces the database signature we denote C^{1}(σ) : σ^{1} ⟶ M(I). This is generated, beginning from the set of relation names J, by freely adjoining to σ^{1} all expressions of relational algebra as described above for the family of domains A. These expressions have appropriate schemes given by C^{1}(σ). The inductive definition of σ^{1} (and simultaneously C^{1}(σ)) follows: σ^{1} is the smallest set satisfying clauses 1. – 5. below subject to identifications generated by equations 1. – 7.:

1. ∀j ∈ J, j ∈ σ^{1} (with scheme σ(j))

2. if s_{1}, s_{2} ∈ σ^{1} (with scheme C^{1}(σ)(s_{1}) = C^{1}(σ)(s_{2})) then (s_{1} ∪ s_{2}), (s_{1} ∩ s_{2}) ∈ σ^{1} (with scheme C^{1}(σ)(s_{1}))

3. if s_{1}, s_{2} in σ^{1} (with schemes C^{1}(σ)(s_{1}) and C^{1}(σ)(s_{2}) then (s_{1} × s_{2}) ∈ σ^{1} (with scheme C^{1}(σ)(s_{1}) · C^{1}(σ)(s_{2}))

4. if s ∈ σ^{1} (with scheme C^{1}(σ)(s) : [n] ⟶ I) and φ : [n′] ⟶ [n], then (π_{φ}s) ∈ σ^{1} (with scheme C^{1}(σ)(s) · φ)

5. if s ∈ σ^{1}, C^{1}(σ)(s)(i_{1}) = C^{1}(σ)(s)(i_{2}) and if c ∈ A_{C^{1}(σ)(s)(i_{1})}, then (S_{i_{1}=i_{2}}(s)) and (S_{i_{1}=c}(s)) are in σ^{1} (with schemes C^{1}(σ)(s).)

The following equations (which have no effect on schemes) apply to the “words” generated above. Let s, s_{1}, s_{2}, s_{3} ∈ σ^{1} be such that the operations mentioned below are defined, then

1. (s_{1} × s_{2}) × s_{3} = s_{1} × (s_{2} × s_{3})

2. (s_{1} ∪s_{2})∪s_{3} = s_{1} ∪(s_{2} ∪s_{3})  (s_{1} ∪s_{2}) = (s_{2} ∪s_{1})  (s_{1} ∪s_{1}) = s_{1}

(s_{1} ∪ s_{2}) ∩ s_{3} = (s_{1} ∩ s_{3}) ∪ (s_{2} ∩ s_{3}) (s_{1} ∪ s_{2}) ∩ s_{2} = s_{1}

and the dual equations

3. if φ : [n′][figure] [n] and ψ : [n′′][figure] [n′] then π_{ψ}π_{φ}s = π_{φψ}s

4. S_{i=j}(S_{i=j}s) = S_{i=j}s = S_{j=i}s S_{i=i}s = s S_{i=j}(S_{k=l}s) = S_{k=l}(S_{i=j}s) S_{i=c}(S_{i=j}s) = S_{i=j}(S_{i=c}s) S_{i=c}(S_{i=c}s) = S_{i=c}s

5. s_{1}×(s_{2}∪s_{3}) = (s_{1}×s_{2})∪(s_{1}×s_{3}) s_{1}×(s_{2}∩s_{3}) = (s_{1}×s_{2})∩(s_{1}×s_{3})

6. π_{φ}(s_{1} ∪ s_{2}) = π_{φ}s_{1} ∪ π_{φ}s_{2} π_{φ}(s_{1} ∩ s_{2}) = π_{φ}s_{1} ∩ π_{φ}s_{2}

7. S_{i=j}(s_{1} ∪ s_{2}) = S_{i=j}s_{1} ∪ S_{i=j}s_{2} S_{i=j}(s_{1} ∩ s_{2}) = S_{i=j}s_{1} ∩ S_{i=j}s_{2}

The definition of C^{1} on an arrow τ : σ_{1} ⟶ σ_{2} of S/M(I) is that induced by the action of τ from generators of σ_{1}^{1} to those of σ_{2}^{1}. The transformations making C^{1} a monad on S/M(I) are easily described. The unit is simply inclusion of the generators, while the multiplication simply rewrites a “word of words” in (C^{1}(σ))^{1} as that element of σ^{1} obtained by treating operations on elements of σ^{1} as operations defining an element of σ^{1}.

Next we decribe C^{0}. The image under C^{0} of an object (σ, R) of grD(A) is (C^{1}(σ), R^{0}) where R^{0} is the σ^{1}-indexed family of relations where, for s ∈ σ^{1}, R_{s}^{0} is the relation obtained by applying the relational operations in the construction of s to the corresponding relations of R. Extending C^{0} to arrows of grD(A) presents no difficulties. Once again, the monad unit is inclusion of generators and the multiplication arrow on the family of relations component merely applies the appropriate relational operations.

The non-monotonicity of binary difference of relations would prevent the definition of C^{0} indicated above. One way to get around this problem is to use updates rather than simply inclusions as arrows in a modified D(A). The relationally complete databases are then those algebras for the resulting monad which have fully defined structural arrows. We have chosen to leave out difference in order that a “relationally complete database” is precisely an algebra for the monad C we have described.

Now the definition of Γ is straightforward. For any object (σ, R) of grD(A), the natural isomorphism required has components the identity on C^{1}(σ). The reader will have no trouble verifying that C is a monad on G_{D(A)} in cat2.

The category grD(A)C^{0} of Eilenberg-Moore algebras [17] for the monad C^{0} has objects pairs (σ, R) where σ is the database signature of a relationally complete database with relations R. The Eilenberg-Moore algebras set/M(I)C^{1} for C^{1} has objects database signatures with interpretations for the operations of relational algebra. There is a functor between these categories GC_{D(A)} :

grD(A)^{C^{0}} ⟶ set/M(I)^{C^{1}} which forgets the relations.

Proposition 4. The functor GC_{D(A)} is the Eilenberg-Moore object for the

monad C on G_{D(A)} in cat2.

Proof. This is an instance of a more general result which asserts that Eilenberg-Moore algebras for monads in cat2 are computed, as here, by taking algebras for the domain and codomain monads and the induced functor between these categories of algebras.

For the balance of this section we will assume that the indexing category S is an elementary topos with NNO and that A = S. Before describing the 2-category arising from a relationally complete database, we note that to any word w : 1 ⟶ M(I) of M(I) we can associate a “diagonal” relation δ_{w} : Δ_{w} [figure] (ww)^{∗}P_{0}(A) ≅ w^{∗}P_{0}(A) × w^{∗}P_{0}(A). We take Δ_{w} to be w^{∗}P_{0}(A), and define δ_{w} by projections to w^{∗}P_{0}(A) which are both the identity.

Now let R : R_{0} [figure] σ^{∗}P_{0}(A) be a datbase with database signature σ : J ⟶ M(I). Provided that R is closed under projection, selection and cartesian product, we can construct a 2-category which we will denote R. We define the objects of R to be M(I). Letting v, w : 1 ⟶ M(I) be objects of R, we define 1-cells by the formula

R(v, w) = \{ \begin{matrix}\{(v, R_{j}, w) ∈ R | σ(j) = vw\} & if v ≠ w \\ \{(v, R_{j}, w) ∈ R | σ(j) = vw\} ⋃\{Δ_{w}\} & if v = w \end{matrix}

The two-cells are given by inclusion.

Proposition 5. Let ρ be a database closed under selection, projection and cartesian product. The structure R is a 2-category with composition of 1-cells given by relational composition.

Proof. We need only observe that if r ∈ R(v, w) and s ∈ R(u, v) then their relational composite (with a slight abuse of our notation for projection and selection) is

rs = π_{uw}(s ▷◁ r) := π_{uw}(S_{r.v=s.v}(s × r))

so that rs is in R. Now, with identities given by the Δ’s, we have that R is a sub-2-category of rel(S) and the required equations all follow from the latter’s structure.

Corollary 1. If ρ is a relationally complete database, then R is a 2category of relations.

We end this section with two remarks:

(i) the results raise the question whether a relationally closed database is a “2category of relations” in the sense of Carboni and Walters [2] (= the 2-category rel(E) for a regular category E) – the answer appears to be no; (ii) the setting we have constructed will be useful for the expression of functional dependencies which are important in database design – the statement that there is a functional dependency becomes the categorical statement that a 1-cell in R(v, w) always has a right adjoint.

Conclusion

We conclude this article with some directions for further work. While the theory of indexed categories gives a satisfactory account of the theory of relational databases, viewing databases as 2-categories of relations begs the investigation of databases on a different data structure which appears in a bicategories closely related to 2-categories of relations, namely bicategories of profunctors. A (binary) relation from set A_{1} to set A_{2} is determined by stating whether or not an element of A_{1} is related to an element of A_{2}. A profunctor generalizes this in two ways. First, A_{1} and A_{2} are categories and there is a set (not just a boolean truth value) relating an object of A_{1} to an object of A_{2}. Second, this doubly indexed family of sets is acted on by arrows of the categories A_{1} and A_{2}. Replacing the discrete objects used as domains in the relational theory by categories, and hence considering the profunctor data structure, may provide a suitable theoretical foundation for object-oriented databases. This observation is currently under investigation.

References

1. M. Barr, Fuzzy set theory and topos theory. Bull. Can. Math. Soc. 29 (1986), 501–508.

2. Aurelio Carboni and R. F. C. Walters, Cartesian bicategories 1. Journal of Pure and Applied Algebra 49 (1987), 11–32.

3. E. F. Codd, A relational model for large shared data banks. Comm. ACM 13 (6) (1970), 377–387.

4. C. J. Date, Introduction to Database Systems, Fifth edition. Addison-Wesley, 1990.

5. J. W. Gray, Fibered and Cofibered Categories, Proceedings of the Conference on Categorical Algebra, La Jolla, pages 21–83, Springer, 1966.

6. B. Hilken and D. E. Rydeheard, Indexed categories for program development. Cahiers de topologie et géometrie différentielle catégoriques, XXXII (1991), 165–185.

7. M. Hyland and A. M. Pitts. The Theory of Constructions: Categorical Semantics and Topos-Theoretical Models, Categories in Computer Science and Logic, Contemporary Math No. 92, American Mathematical Society, 1989.

8. Peter T. Johnstone, Topos Theory, Academic Press, 1977.

9. G. M. Kelly and R. Street, Review of the elements of 2-categories, Lecture Notes in Math. 420, pages 75–103. Springer-Verlag, 1974.

10. B. LeSaffre, Structures algebriques dans les topos elementaires. PhD thesis, U. de Paris 7, 1974.

11. D. Maier, The Theory of Relational Databases, Computer Science Press, 1983.

12. Eugenio Moggi, A category-theoretic account of program modules, Mathematical Structures in Computer Science 1 (1991), 103–139.

13. R. Paré and D. Schumacher, Abstract Families and the Adjoint Functor Theorems, Indexed Categories and their Applications, pages 1–125. Volume 661 of Lecture Notes in Math., Springer-Verlag, 1978.

14. K. Raju and A. Majumdar, Fuzzy functional dependencies and losslessjoin decomposition of fuzzy relational database systems. ACM Transactions on Database Systems, 13 (1988), 129–166.

15. Robert Rosebrugh, On defining objects by recursion in a topos, Journal of Pure and Applied Algebra, 20 (1981), 325–335.

16. R. A. G. Seely, Categorical semantics for higher order polymorphic lambda calculus, Journal of Symbolic Logic, 52 (1987), 4.

17. R. Street, The formal theory of monads, Journal of Pure and Applied Algebra, 2 (1972), 149-168.

18. J. D. Ullman, Principles of Database and Knowledge Base Systems, Volumes 1 and 2, Computer Science Press, 1988.

DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE MOUNT ALLISON UNIVERSITY SACKVILLE, N.B. CANADA RROSEBRUGH@MTA.CA and

DEPARTMENT OF MATHEMATICS, STATISTICS AND COMPUTING SCIENCES DALHOUSIE UNIVERSITY HALIFAX, N.S. CANADA RJWOOD@CS.DAL.CA

References

[1] M. Barr. Fuzzy set theory and topos theory. Bull. Can. Math Soc., 29:501– 508, 1986.

[2] Aurelio Carboni and R. F. C. Walters. Cartesian bicategories 1. Journal of Pure and Applied Algebra, 49:11–32, 1987.

[3] E. F. Codd. A relational model for large shared data banks. Comm. ACM, 13(6):377–387, 1970.

[4] C. J. Date. Introduction to Database Systems, Fifth Edition. Addison-Wesley, 1990.

[5] J. W. Gray. Proceedings of the Conference on Categorical Algebra, La Jolla, chapter Fibered and Cofibered Categories, pages 21–83. Springer, 1966.

[6] B. Hilken and D.E. Rydeheard. Indexed categories for program development. Cahiers de topologie et géometrie différentielle catégoriques, XXXII:165–185, 1991.

[7] M. Hyland and A. M. Pitts. Categories in Computer Science and Logic, chapter The Theory of Constructions: Categorical Semantics and Topos-Theoretic Models. Contemporay Math No. 92, American Mathematical Society, 1989.

[8] Peter T. Johnstone. Topos Theory. Academic Press, 1977.

[9] G. M. Kelly and R. Street. Lecture Notes in Math. 420, chapter Review of the elements of 2-categories, pages 75–103. Springer-Verlag, 1974.

[10] B. LeSaffre. Structures algebriques dans les topos elementaires. PhD thesis, U. de Paris 7, 1974.

[11] D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.

[12] Eugenio Moggi. A category-theoretic account of program modules. Mathematical Structures in Computer Science, 1:103–139, 1991.

[13] R. Paré and D. Schumacher. Indexed Categories and their Applications, chapter Abstract Families and the Adjoint Functor Theorems, pages 1–125. Volume 661 of Lecture Notes in Math., Springer-Verlag, 1978.

[14] K. Raju and A. Majumdar. Fuzzy functional dependencies and losslessjoin decomposition of fuzzy relational database systems. ACM Transactions on Database Systems, 13:129–166, 1988.

[15] Robert Rosebrugh. On defining objects by recursion in a topos. Journal of Pure and Applied Algebra, 20:325–335, 1981.

[16] R.A.G. Seely. Categorical semantics for higher order polymorphic lambda calculus. Journal of Symbolic Logic, 52:4, 1987.

[17] R. Street. The formal theory of monads. Journal of Pure and Applied Algebra, 2:149–168, 1972.

[18] J. D. Ullmann. Principles of database and knowledge base systems, Vol. 1 and 2. Computer Science Press, 1988.