Relational Algebra

Set-theoretic operations

Def: Let r1, r2 be relations. r1, r2 are union compatible if r1∪r2 is a relation.

Note: The elegance and generality of this should be compared to typed versions of the RM which have to deal with the awkward case of the empty relation, how headers fit into the picture, the MSTs of relations, the notion of the types forming a lattice (to ensure the MST of the union is defined), etc.

Def: The union, intersection and difference of union compatible relations are exactly the corresponding set-theoretic operators on the sets of tuples.

Projection

Note: We don't define projection on individual tuples, since we have already defined restriction on set of ordered pairs, and it means the same thing.

Def: Let r be a relation. Let p be any set. Then the projection of r on p is defined by
project(r,p) = { restrict(t,p) | t∈r }

Note: p should be regarded as a set of attributes.

Note: ∀relation r, ∀p, project(r,p) is a relation

Note: ∀relation r, ∀p, |project(r,p)| ≤ |r|

Note: We didn't need to deal with the empty relation specially even though the attributes on the empty relation is ill-defined.

Note: ∀p, project(∅,p) = ∅ and ∀r, project(r,∅) = ∅

Restriction

This is just restricted comprehension on the set of tuples.

Join

Def:Let r₁,r₂ be relations. r₁⋈r₂ is defined by
r₁⋈r₂ = { t₁∪t₂ | t₁∈r1 ∧ t₂∈r₂ ∧ t₁∪t₂ is a function }

Note: The requirement that t₁∪t₂ be a function neatly takes care of the requirement that t₁,t₂ agree on the values of the common attributes A=dom(t₁)∩dom(t₂). i.e. that restrict(t₁,A)=restrict(t₂,A).

Note: ⋈ is commutative and associative

Note: ∀r, r⋈∅ = ∅⋈r = ∅

Note: ∀r, r⋈{∅} = {∅}⋈r = r. (dee is identity for join).

Rename

Def: Let b be a boolean value. Then (b?x:y) evaluates to x if b is true and y otherwise.

Def: The rename of attribute a1 as a2 on tuple t is defined as:
rename(t,a1,a2) = {((a=a1)?a2:a, v) | (a,v)∈t}

Def: The rename of attribute a1 as a2 on relation r is defined as:
rename(r,a1,a2) = { rename(t,a1,a2) | t∈r }

todo

It would be worthwhile covering extension, aggregation, grouping, packing, recursion etc.

It would be good to provide a proof of the correspondence between the algebra and the calculus.