Page 27 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes Relation Universe: A relation universe U over a header H is a non-empty set of relations with
header H.
Relation Schema: 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. A relation satisfies a 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.

1. Superkey: A superkey is written as a finite set of attribute names.
A superkey K holds in a relation (H, B) if:
K H and

there exist no two distinct tuples t ,t 2 B such that t [K] = t [K].
1
2
1
A superkey holds in a relation universe U if it holds in all relations in U.
Theorem: A superkey K holds in a relation universe U over H if and only if K H and
K H holds in U.
2. Candidate Key: A superkey K holds as a candidate key for a relation universe U if it holds
as a superkey for U and there is no proper subset of K that also holds as a superkey for U.
3. Functional Dependency: A functional dependency (FD for short) is written as X Y for
X, Y finite sets of attribute names.
A functional dependency X Y holds in a relation (H,B) if:

X,Y H and

tuples t ,t 2 B, t X t X t Y t Y
1
1
2
1
2
A functional dependency X Y holds in a relation universe U if it holds in all relations
in U.
4. Trivial Functional Dependency: A functional dependency is trivial under a header H if it
holds in all relation universes over H.
Theorem: An FD X Y is trivial under a header H if and only if Y X H .
5. Closure: Armstrong’s axioms: The closure of a set of FDs S under a header H, written as
+
S , is the smallest superset of S such that:
(a) Y X H X Y S (reflexivity)

(b) X Y S Y Z S X Z S (transitivity) and

(c) X Y S Y H X Z Y Z S (augmentation)
Theorem: Armstrong’s axioms are sound and complete; given a header H and a set S of FDs
that only contain subsets of H, X Y S if and only if X Y holds in all relation
universes over H in which all FDs in S hold.

20 LOVELY PROFESSIONAL UNIVERSITY