Database Schema

definition example

A database is a system of interlocking tables; each table has an ID column of unique row labels, and the other columns are references: foreign keys (internal references to rows of another table, e.g. WorksIn, Mngr, Secr) or external references to strings/integers (FName, DName). Foreign-key labels can be renamed consistently ($1\mapsto 1001$) without changing the meaning; external labels cannot (Ruth $\ne$ Bruce).

A database schema is the reference structure drawn as a “Hasse diagram for a database”: one (black) vertex per table, one (white) vertex per external type, one arrow per non-ID column pointing in the direction of reference (7S Exercise 3.3: as many arrows as non-ID columns), together with business rules — path equations. That is, a schema is a Presentation of a Category; the data is a C-Set $\mathcal{C}\to \mathbf{Set}$.

Sources: 7 Sketches §3.1 (Eqs. 3.1–3.5), Remark 3.20, §3.4, §3.6; Kittenlab Lecture 6 (“you can think of $\mathsf{C}=\mathrm{Path}(G)$ as a database schema”; graphs as two-table databases); FQL, the functorial query language; CTfS §3.5 (Examples 3.5.1.1, 3.5.1.3, 3.5.2.1, Definitions 3.5.2.3, 3.5.2.6, Rules 3.5.2.8, Examples 3.5.2.9–3.5.2.15), §4.2.2 (“a database schema is a category presentation”), §4.4 ($\mathbf{Sch}\simeq \mathbf{Cat}$)

Example (mySchema). Tables Employee (FName, WorksIn, Mngr) and Department (DName, Secr), with rules

$$Department.Secr.WorksIn=\mathsf{Department},Employee.Mngr.WorksIn=Employee.WorksIn$$

(“every department’s secretary works in that department; every employee’s manager works in the employee’s department”): easySchema + constraints = mySchema.

Category Theory for Scientists’ formalization. A schema is a pair $(G,\simeq )$ of a Graph and a categorical path equivalence relation (CPER) on its paths: an equivalence relation relating only paths with the same endpoints and closed under pre- and post-composition with arrows (CTfS Definition 3.5.2.3). It is generated by finitely many path equivalence declarations (PEDs) such as $Employee.manager.worksIn\simeq Employee.worksIn$. Tables come from the schema by the rules of good practice: one table per vertex, a leftmost ID column, one foreign-key column per arrow (Rules 3.5.2.8). Data columns are foreign keys into leaf tables with no further columns (Example 3.5.1.6). Schemas and categories are equivalent (Categories and Schemas are Equivalent), and an Olog is a schema whose boxes and arrows are labelled by readable English. Scientific example (CTfS Example 3.5.1.1): graphene samples with columns Source (a foreign key into a Supplier table with full name and phone), Stress and Strain:

Graphene sample	Source	Stress	Strain
A118-1	C Smkt	0	0
A118-2	C Smkt	0.02	20
A118-4	AC	0.04	37
A118-6	C Plat	0.1	82

Other small schemas with big consequences: the one-loop schema $\mathrm{Loop}$ (a Discrete Dynamical System), $\mathrm{Loop}$ with ${\mathsf{mgr}}^8\simeq {\mathsf{mgr}}^7$ (a finite hierarchy: at Ben & Jerry’s there were only seven levels of management, CTfS Example 3.5.2.11), and “a father has as first child a child, which has a father” with the PED $firstChild.father\simeq \mathrm{id}$ (CTfS Exercise 3.5.2.18).

Data integration accounted for 40% of IT budgets in 2008 and over half of migration projects fail; category theory lets one prove up front that a migration along a functor $F:\mathcal{A}\to \mathcal{B}$ between schemas (e.g. Economy/First-Class seats $\mapsto$ Airline Seat, Eq. 3.5) yields data satisfying the target’s constraints. The four ingredients: schemas are categories, instances are functors to $\mathbf{Set}$, schema mappings are functors, migration is by adjoints. Schemas are “ad hoc — formed for a particular purpose — and there is nothing wrong with that” (§2.2.3). Further reading: [Spi12; SW15b; Sch+17] (algebraic databases with an attached programming language).

JuliaHaskell

Docs: ACSets API · Theories & presentations — Kittenlab Lecture 6

using Catlab
@present SchMySchema(FreeSchema) begin
  (Employee, Department)::Ob
  Mngr::Hom(Employee, Employee)
  WorksIn::Hom(Employee, Department)
  Secr::Hom(Department, Employee)
  Str::AttrType
  FName::Attr(Employee, Str); DName::Attr(Department, Str)
  compose(Secr, WorksIn) == id(Department)
  compose(Mngr, WorksIn) == WorksIn
end
@acset_type MySchema(SchMySchema)
db = @acset MySchema{String} begin
  Employee = 3; Department = 2
  FName = ["Alan", "Ruth", "Kris"]; WorksIn = [1, 1, 2]; Mngr = [2, 2, 3]
  DName = ["Sales", "IT"]; Secr = [1, 3]
end
db[:Secr], db[:WorksIn]      # ([1, 3], [1, 1, 2]): Secr ⋅ WorksIn == id holds

-- a schema as data: tables, foreign keys, attributes, and path equations
data Schema = Schema
  { tables     :: [String]
  , foreignKey :: [(String, String, String)]   -- (column, from table, to table)
  , attribute  :: [(String, String, String)]   -- (column, table, external type)
  , rules      :: [([String], [String])]       -- equal paths of column names
  }
mySchema :: Schema
mySchema = Schema ["Employee", "Department"]
  [("Mngr","Employee","Employee"), ("WorksIn","Employee","Department"), ("Secr","Department","Employee")]
  [("FName","Employee","string"), ("DName","Department","string")]
  [(["Secr","WorksIn"], []), (["Mngr","WorksIn"], ["WorksIn"])]