schema

database schema or simply schema, $\mathcal{C}$ is a pair $\mathcal{C} := (G, \simeq)$ , where $G$ is a graph $(V, A, src, tgt)$ and $\simeq$ is a congruence on $G$

given a database schema $\mathcal{C} = (G, \simeq)$ $C = (G, ≃)$ , an instance on $\mathcal{C}$ $C$ is a bunch of tables whose data conform to the specified layout
- $G = (V, A, src, tgt)$
denote $(\text{PK}, \text{FK}): \mathcal{C} \to \mathbf{Set}$ $(PK, FK) : C \to Set$
- consituents:
  - A: primary ID part
    - a function $\text{PK}: V \to \mathbf{Set}$ , sending each vertex $v \in V$ to a set $\text{PK}(v)$
  - B: foreign ID part
    - for every arrow $a \in A$ where $v = src(a) \in V$ and $w = tgt(a) \in V$ , a function $\text{FK}(a): \text{PK(v)} \to \text{PK(w)}$
    - each foreign key relation is a function that maps primary key values in one table to the primary key in another table
- laws: preservation of congruence
  - …
  - the congruence (declared on the paths on graph) is preserved