Relational model

The relational model for management of a database is a data model based on predicate logic and set theory.

Set Theory Formulation

Basic notions in the relational model are relation names and attribute names. We will represent these as strings such as "Person" and "name" and we will usually use the variables r, s, t, ... and a, b, c to range over them. Another basic notion is the set of atomic values that contains values such as numbers and strings.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Our first definition concerns the notion of tuple, which formalizes the notion of row or record in a table:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A tuple is a partial function from attribute names to atomic values.

Related Topics:
Tuple - Partial function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A header is a finite set of attribute names.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def.- The projection of a tuple t on a finite set of attributes A is t = { (a, v) : (a, v) ∈ t, a ∈ A }.

Related Topics:
Finite - Set

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The next definition defines relation which formalizes the contents of a table as it is defined in the relational model.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A relation is a tuple (H, B) with H, the header, and B, the body, a set of tuples that all have the domain H.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Such a relation closely corresponds to what is usually called the extension of a predicate in first-order logic except that here we identify the places in the predicate with attribute names. Usually in the relational model a database schema is said to consist of a set of relation names, the headers that are associated with these names and the constraints that should hold for every instance of the database schema.

Related Topics:
Relation - First-order logic - Database schema - Constraints

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A relation universe U over a header H is a non-empty set of relations with header H.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A relation schema (H, C) consists of a header H and a predicate C(R) that is defined for all relations R with header H.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A relation satisfies the relation schema (H, C) if it has header H and satisfies C.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Key constraints and functional dependencies

One of the simplest and most important types of relation constraints is the key constraint. It tells us that in every instance of a certain relational schema the tuples can be identified by their values for certain attributes.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A superkey is written as a finite set of attribute names.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A superkey K holds in a relation (H, B) if K ⊆ H and there are no two distinct tuples t1 and t2 in B such that t1 = t2.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A superkey holds in a relation universe U over a header H if it holds in all relations in U.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. - A superkey K holds as a candidate key for a relation universe U over H if it holds as a superkey for U and there is no proper subset of K that also holds as a superkey for U.

Related Topics:
Candidate key - Proper subset

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A functional dependency (or FD for short) is written as X->Y with X and Y finite sets of attribute names.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A functional dependency X->Y holds in a relation (H, B) if X and Y are subsets of H and for all tuples t1 and t2 in B it holds that if t1 = t2 then t1 = t2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A functional dependency X->Y holds in a relation universe U over a header H if it holds in all relations in U.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. A functional dependency is trivial under a header H if it holds in all relation universes over H.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Theorem A FD X->Y is trivial under a header H iff Y ⊆ X ⊆ H.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Theorem A superkey K holds in a relation universe U over H iff K ⊆ H and K->H holds in U.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. (Armstrong's rules) Let S be a set of FDs then the closure of S under a header H, written as S+, is the smallest superset of S such that:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: (reflexivity) if Y ⊆ X ⊆ H then X->Y in S+

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: (transitivity) if X->Y in S+ and Y->Z in S+ then X->Z in S+

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: (augmentation) if X->Y in S+ and Z ⊆ H then X∪Z -> Y∪Z in S+

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Theorem Armstrong's rules are sound and complete, i.e., given a header H and a set S of FDs that only contain subsets of H then the FD X->Y is in S+ iff it holds in all relation universes over H in which all FDs in S hold.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. If X is a finite set of attributes and S a finite set of FDs then the completion of X under S, written as X+, is the smallest superset of X such that:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: if Y->Z in S and Y ⊆ X+ then Z ⊆ X+

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Theorem Given a header H and a set S of FDs that only contain subsets of H it holds that X->Y is in S+ iff Y ⊆ X+.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Algorithm (deriving candidate keys from FDs)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

INPUT: a set S of FDs that contain only subsets of a header H

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

OUTPUT: the set C of superkeys that hold as candidate keys in

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

all relation universes over H in which all FDs in S hold

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

begin

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

C := ∅; // found candidate keys

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Q := { H }; // superkeys that contain candidate keys

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

while Q ∅ do

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

let K be some element from Q;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Q := Q - { K };

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

minimal := true;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for each X->Y in S do

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

K' := (K - Y) ∪ X; // derive new superkey

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

if K' ⊂ K

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

then

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

minimal := false;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Q := Q ∪ { K' };

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

fi

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

od

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

if minimal and there is not a subset of K in C

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

then

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

remove all supersets of K from C;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

C := C ∪ { K };

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

fi

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

od

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Def. Given a header H and a set of FDs S that only contain subsets of H an irreducible cover of S is a set T of FDs such that

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:# S+ = T+

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:# there is no proper subset U of T such that S+ = U+,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:# if X->Y in T then Y is a singleton set and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:# if X->Y in T and Z a proper subset of X then Z->Y is not in S+.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~