Constant Complements, Reversibility and Universal View Updates

Michael Johnson

(joint work with Bob Rosebrugh)

CT - 2006

What is …

What is a database? — sets of tuples (tables)

(eg address book) algebra (multi-sorted)

a database specification? — table structure

theory

a constraint? — extra software (triggers)

commutative diagram

Entities are “things in the world” Attributes are “values possessed by entities”

(names, addresses, phone numbers …)

Example theory (and algebra)

[figure: In-patient operation; at; under; by; Oper’n type; GP; is a; Specialist; is a; has; Medical pract’ner; is a; memb; Practice agreem’t; Hospital; Spec’n; is a; College; Person]

Fragment of a hospital database

Attributes not shown (people have names…) Triangles and square commute Square is pb; monos by unshown pb squares

Issues

Implementation — well handled commercially Efficiency — eg query optimization

… Specification Security Views Interoperation

Specification

ERA models vs Theories

(communication) Commutative diagrams as constraints

(business rules) Categorical logic

(constraints inherent in theory) Leverage

Categorical Specification

An EA-sketch 𝔼 = (G, D, L, C) is a finite limit, finite coproduct sketch with

• a specified empty base cone in L (vertex is called 1); domain 1 arrows called elements.

• attributes are vertices of cocones with injections only elements (assume attribute not the domain of arrow); non-attributes called entities.

• the graph of G is finite.

An EA sketch is keyed if each entity E has a specified monic arrow k_{E} : E [figure] A_{E} to a chosen attribute A_{E}.

Another example

[figure: ShipperID; RedOrders; isa; Orders; Quantity; RedStock; isa; WineStock; WhiteStock; isa; Bin; Year]

Graph fragment for a Winery data model

Triangles and square commute Square is pb; monos from pb Winestock is a sum Quantity, ShipperID are attributes

DB state (model, algebra)

• Sketch morphism 𝔼 [figure] Set_{0} (finite sets)

• Equivalently: finite limit, finite coproduct preserving functor Q𝔼 [figure] Set_{0}

• More generally, a database state D for an EA sketch 𝔼 is a a model of 𝔼 in a lextensive S (finite lims and disjoint universal sums)

• Category of database states of 𝔼 is Mod (𝔼, S) – morphisms are natural transformations.

• Update changes state by deletion and/or insertion

• If 𝔼 is keyed then arrows of Mod (𝔼, S) are monic

Views

A view is …

DB theorists function: states [figure]states (often surjective)

Category theorists V : 𝕍 [figure] Q𝔼 a sketch morphism, hence V^{∗} : Mod 𝔼 [figure] Mod 𝕍 a functor

Too abstract? Too far from reality? No! And what’s hard anyway?

View updating

Constant complements

Let 𝔼, 𝕍 and ℂ be EA sketches and 𝕍 [figure: V] Q(𝔼) and ℂ [figure: C] Q𝔼 be views. We say C is a complement of V if the functor

Mod (𝔼) [figure: ⟨V^{∗},C^{∗}⟩] Mod (𝕍) × Mod (ℂ)

is full, faithful and one-one on objects.

Let 𝕍 [figure: V] Q(𝔼) and ℂ [figure: C] Q𝔼 be views with C a complement of V and α : R [figure]V^{∗}D be an arrow in Mod (𝕍). We say that α has a C-constant update if there is α̂ in Mod (𝔼) with α = V^{∗}α̂ and C^{∗}(α̂) an isomorphism. (Note α̂ is not necessarily cartesian)

Universal view updates

Asking that for a view state delete there should exist a universal lifting to the underlying database state leads to...

Let V be a view schema for 𝔼, D be a state of 𝔼, T = V^{∗}D and t : T′ [figure] T. The delete update t is propagatable if there exists a delete m : D′ [figure] D with: for any state D′′ and delete m′′ : D′′ [figure] D such that V^{∗}m′′ factors as tt′ there is a unique delete m′ : D′′ [figure] D′ such that V^{∗}m′ = t′. (propagatable insert is dual)

That is, t is a propagatable delete if it has a cartesian arrow m:

[figure: D′′; m′′; m′; D′; m; D; V^{∗}D′′; V^{∗}m′′; t′; T′; t; V^{∗}D]

all insert updates for V are propagatable exactly when V^{∗} is a fibration. (remember that for keyed sketches all morphisms are monic)

.

Reversibility

Let 𝕍 [figure: V] Q(𝔼) be a view and α : R [figure]V^{∗}M a propagatable deletion in Mod (𝕍). We say that α is reversible if its cartesian arrow αM [figure: α̂] M is also opcartesian. Similarly, a propagatable insertion is reversible if its opcartesian arrow is also cartesian.

Results

- Constant complement updates are universal - But there exist universal view updates which

are not constant compliment

- Constant complement updates are reversible - Reversible updates are universal (defn)

- But there exist universal view updates which are not reversible For related articles see:

www.cs.mq.edu.au/~mike
www.mta.ca/~rrosebru

Remarks on abstraction

“Give me something concrete like a function from states to states, not something abstract like V^{∗} for finite-limit, finite-coproduct preserving functors V … ”

Categorical study of databases

Dampney-Johnson-Monro 1992: An illustrated mathematical foundation for ERA Rosebrugh-Wood 1992: Relational databases and indexed categories Baclawski-Simovici-White 1994: A categorical approach to database semantics Diskin-Cadish 1995–: Algebraic graph-based approach… Piessens 1995–: Categorical data specifications… Benson 1996: Stone duality between queries and data Tuijn-Gyssens 1996: A categorical graph-oriented object data model Johnson-Rosebrugh-Dampney-Wood 1997–: the Sketch Data Model Pierce 2006: Lenses and view update translation