📘 Relational Design & Normalization

Brief Overview
This note covers relational design and was created from a 48-page PDF. It provides a
detailed walk‑through of functional dependencies, lossless decomposition, BCNF, 3NF,
4NF, multivalued dependencies, and temporal database concepts, giving you the tools to
structure and evaluate database schemas effectively.

Key Points
Overview of functional dependencies and their role in schema design.
Techniques for lossless decomposition and achieving BCNF.
Comparison of 3NF, 4NF, and multivalued dependencies.
Introduction to SQL:2011 temporal extensions and their practical implications.

📚 Features of Good Relational Designs

Entity‑relationship (E‑R) designs provide the initial set of relation schemas.
The quality of the resulting relational schemas depends on the goodness of the
original E‑R design.
A well‑designed schema should avoid redundancy and preserve consistency.

Good Relational Design – A collection of relation schemas that stores information

without unnecessary redundancy and supports easy retrieval.

Example: University Database Schemas

Relation Attributes
in_dep (ID, name, salary, dept name, building,
budget)
classroom (building, room number, capacity)
department (dept name, building, budget)
course (course id, title, dept name, credits)
instructor (ID, name, dept name, salary)
 section (course id, sec id, semester, year, building,
room number, time slot id)
teaches (ID, course id, sec id, semester, year)
student (ID, name, dept name, tot cred)
takes (ID, course id, sec id, semester, year, grade)
advisor (s ID, i ID)
time slot (time slot id, day, start time, end time)
prereq (course id, prereq id)
The in_dep relation is a natural join of instructor and department, which can lead to
redundancy (e.g., repeated budget values).

🔄 Decomposition
Goal: Eliminate repetition of information by splitting a relation into smaller
schemas.
Not every decomposition is useful; lossless decompositions are required.
Bad Decomposition Example
Original schema: employee(ID, name, street, city, salary)
Decomposed into:
employee1(ID, name)
employee2(name, street, city, salary)

Lossy Decomposition – A decomposition where the natural join of the component

relations produces more tuples than the original, causing loss of information about
which values belong together.

Illustration
Original Tuple employee1 employee2
(57766, Kim, Main, (57766, Kim) (Kim, Main, Perryridge, 75000
Perryridge, 75000)
 (98776, Kim, North, (98776, Kim) (Kim, North, Hampton, 67000)
Hampton, 67000)
Natural join yields four tuples, mixing attributes of the two Kims, thus losing the
association between each ID and its address/salary.

✅ Lossless Decomposition
Definition: For a relation schema R and a decomposition into R and R 1 ​

2 ​

(where R = R 1 ​ ∪ R2 ), the decomposition is lossless if for every legal instance

​

r(R):

ΠR (r); ⋈; ΠR (r); =; r
​ ​

1 ​

2 ​

If the natural join produces a proper superset, the decomposition is lossy:

r; ⊂; ΠR1 (r); ⋈; ΠR2 (r)
​
​

​
​

Note: The definition assumes attributes on the left side of a functional dependency
cannot be null.

📏 Normalization Theory
Normalization = systematic process of converting schemas into normal forms
that avoid redundancy.
Steps:
1. Test whether a schema is in a desired normal form (e.g., 1NF, 2NF,
3NF, BCNF).
2. If not, decompose it into smaller schemas that satisfy the target
normal form, ensuring the decomposition is lossless.
The primary tool for testing normal forms is the set of functional
dependencies (FDs).

🔧 Decomposition Using Functional Dependencies

Real‑world Constraints (University Example)
1. ID uniquely identifies students and instructors.
2. Each person has only one name.
3. Each person is primarily associated with a single department.
4. Each department has a single budget and building.
 Legal Instance – A relation instance that satisfies all specified real‑world constraints.

Notational Conventions
Symbol Meaning
α, β Sets of attributes (Greek letters)
R Relation schema (uppercase Roman)
r(R) Relation r with schema R
K Superkey for a schema
r Instance of a relation

Keys and Functional Dependencies

Superkey: K ⊆ R such that no two distinct tuples share the same K values.
Functional Dependency (FD): α → β holds if whenever two tuples agree on α,
they also agree on β .

Definition (FD):
“For relation r(R), α → β holds iff for all tuples t 1,
​
t2 ​
in any legal instance, t 1 [α]
​
=

t [α] implies t [β ] = t [β ] .”
2 ​

1 ​

2 ​

Superkey as FD: K → R .
Example FD on in_dep
dept name → budget (each department has a unique budget).
Composite superkey: ID, dept name → name, salary, building, budget.
Trivial vs. Non‑trivial FDs
Trivial FD: β ⊆ α (e.g., A → A, AB → A).
Non‑trivial FDs convey actual constraints.
Sample Instance (Figure 7.4)
A B C D
a1 b1 c1 d1
 a1 b2 c1 d2
a2 b2 c2 d2
a2 b3 c2 d3
a3 b3 c2 d4
Satisfies A → C (all rows with same A share the same C ).
Violates C → A (rows with C = c2 have different A values).
Using FDs for Lossless Decomposition
For schemas R, R , R with R = R ∪ R , the decomposition is lossless if one
1 ​

2 ​

1 ​

2 ​

of the following holds in the FD closure F : +

R1 ∩ R2 → R1
​ ​ ​

R1 ∩ R2 → R2
​ ​ ​

Attribute closure can be used to test whether the intersection forms a

superkey for either side.
Example: in_dep Decomposition
Decompose into:
instructor(ID, name, dept name, salary)
department(dept name, building, budget)
Intersection = dept name. Since dept name → building, budget is in F , the
+

decomposition is lossless.

📐 Normal Forms
Binary decomposition (into two schemas) has a simple lossless test; for
multiple schemas the test is more complex.
Multivalued dependencies (covered later) can also guarantee losslessness
even when no FD is present.
BCNF (Boyce–Codd Normal Form)
Definition: A schema R is in BCNF w.r.t. a set of FDs F if for every non‑trivial
FD α → β in F , α is a superkey of R .
+

BCNF Condition: Either the FD is trivial, or its left‑hand side is a superkey.

BCNF Example
Relation in_dep(ID, name, salary, dept name, building, budget)
FD dept name → budget is non‑trivial, but dept name is not a
superkey → not in BCNF.
Decomposition into instructor and department yields schemas where
every non‑trivial FD has a superkey on the left, so both are in BCNF.
BCNF Decomposition Rule
If a schema R is not in BCNF because of a violating FD α → β (with α not a superkey),
replace R with:
1. (α ∪ β )
2. R − (β − α)
Applying the Rule to in_dep
Violating FD: dept name → building, budget
New schemas:
1. (dept name, building, budget)
2. (ID, name, dept name, salary)
Both resulting schemas satisfy BCNF.

🔄 BCNF and Dependency Preservation

Dependency preservation: After decomposition, it should still be possible to
enforce all original FDs using only the decomposed relations.
In some cases, BCNF decomposition breaks dependency preservation, making
certain constraints harder to enforce efficiently.
Illustrative Scenario
Modified university model adds a ternary relationship dept advisor(s ID, i ID,
dept name) with constraints:
i ID → dept name
s ID, dept name → i ID
The schema dept advisor is not in BCNF because i ID is not a superkey.
BCNF decomposition yields:
(s ID, i ID)
 (i ID, dept name)
Both resulting two‑attribute schemas are automatically in BCNF.

🧩 Third Normal Form (3NF)

Definition (3NF) – A relation schema R is in third normal form with respect to a set of
functional dependencies F iff for every non‑trivial FD α → β in F (where α, β ⊆ R)
+

at least one of the following holds:

1. Trivial FD: β ⊆ α .
2. Superkey: α is a superkey of R .
3. Attribute in a candidate key: Every attribute A in β !−!α appears in some
candidate key of R .

Candidate key – a minimal superkey; no proper subset of it is a superkey.

Observation: Every schema that satisfies BCNF automatically satisfies 3NF, because
BCNF guarantees that any non‑trivial FD has a superkey on the left‑hand side, fulfilling
condition 2.

Example: Dept‑Advisor Relation

Functional dependencies:
i!I D → dept!name

s!I D,; dept!name → i!I D

The FD i!I D → dept!name violates BCNF (left side not a superkey).

However, dept!name is part of the candidate key s!I D,, dept!name, so condition 3 is
satisfied. Hence the relation is in 3NF but not in BCNF.

⚖️ Comparing BCNF and 3NF

Aspect BCNF 3NF
 Strictness More restrictive – every Allows FD where left side
non‑trivial FD must have a is not a superkey, provided
superkey on the left. the right‑hand attributes
appear in some candidate
key.
Dependency preservation May break preservation; Guarantees a
some FDs require joins to dependency‑preserving
enforce. lossless decomposition
exists.
Potential redundancy Less redundancy (stronger May retain some
normalization). redundancy; null values can
appear to represent
optional relationships.
Practical trade‑off Preferred when possible, Chosen when a BCNF
but sometimes impossible design would sacrifice
without losing dependency preservation.
preservation.

Design goals (in order of priority): 1️⃣ Achieve BCNF; 2️⃣ Ensure losslessness; 3️⃣
Preserve dependencies.
When the three cannot be satisfied simultaneously, we must decide between a BCNF
design (possible loss of dependency preservation) and a 3NF design (preserves
dependencies).

🔗 Dependency Preservation
Definition (Dependency‑preserving decomposition) – Given a set of FDs F on
schema R and a decomposition R , … , R , let F be the restriction of F to R (all
1 ​

n ​

i ​
+
i ​

FDs whose attributes lie wholly in R ). Define F = ⋃ F . The decomposition is

i ​
′ n

i=1
​

i ​

dependency preserving iff F = F . ′+ +

General Test (Figure 7.10)

1. Compute F (the closure of all FDs).
+

2. For each relation R , form F (restriction of F ).

i ​

i ​
+

3. Let F = ⋃ F .
′
i ​
 4. If F ′+
= F
+
→ dependency preserving; otherwise, not.
The test is exponential because F
+
can be large.
Sufficient (Easy) Condition
If each FD in the original set F can be verified on one relation of the
decomposition, the decomposition is automatically dependency preserving.
This condition is sufficient but not necessary; some preserving
decompositions fail this simple test.
Efficient Procedural Test (Modified Attribute Closure)
For each FD α → β in F :
1. result ← α
2. Repeat for each relation R in the decomposition: i ​

Compute t = ((result ∩ R ) ) ∩ R (closure of the part of result

i ​
+
i ​

that lies in R , using the original FD set F ).

i ​

result ← result ∪ t
3. Until result stabilizes.
4. If result contains all attributes of β , the FD is preserved.
The decomposition is dependency preserving iff every FD in F passes the above
procedure.

🛠 Algorithms for Decomposition

BCNF Decomposition (Figure 7.11 – summarized)
1. Start with result = {R}.
2. While a schema R in result violates BCNF:
i ​

Choose a violating non‑trivial FD α → β where α does not contain +

all of R . i ​

Replace R by the two schemas (α ∪ β ) and (R − β ) .

i ​

i ​

3. End when all schemas satisfy BCNF.

Only the FDs in the original set need to be examined; computing
F F
+
is not required for
the test.

🧩
🧩 Multivalued Dependencies (MVD)
Definition (MVD) – For a relation schema R, α →!! → β holds iff for any two tuples
t1 , t2
​ ​ with t 1 [α]
​ = t2 [α]
​ , there exist tuples t 3,
​ t4 ​ in R such that

t3 [α] = t4 [α] = t1 [α] = t2 [α],

​ ​ ​ ​

t3 [β ] = t1 [β ],;; t4 [β ] = t2 [β ],
​ ​ ​ ​

t3 [R!−!β ] = t2 [R!−!β ],;; t4 [R!−!β ] = t1 [R!−!β ].

​ ​ ​ ​

Trivial MVD – occurs when β ⊆ α or α ∪ β = R .

Every functional dependency α → β implies the MVD α →!! → β .
Illustration of Redundancy
Relation r2(ID, dept_name, street, city) with the MVD ID →→ street, city:
ID dept_name street city
22222 Physics North Rye
22222 Math Main Manchester
Because the address of an instructor is independent of the department they belong to,
the above table repeats address information for each department—a classic case of
unnecessary redundancy that MVDs help to eliminate.

🏗 Fourth Normal Form (4NF)

Definition (4NF) – A relation schema R is in fourth normal form w.r.t. a set D of
functional and multivalued dependencies iff for every non‑trivial MVD α →!! → β in
D , either:
+

1. The MVD is trivial, or

2. α is a superkey of R .

Every 4NF schema is automatically in BCNF (because a violating FD would also

violate the MVD condition).
4NF Decomposition Example
Original schema: (I D,; dept!name,; street,; city) with MVD I D →!! → street, city .
Since I D is not a superkey, decompose into:
1. (I D,; dept!name)
2. (I D,; street,; city)
Both resulting schemas satisfy 4NF and eliminate the address duplication shown earlier.

4NF Decomposition Algorithm (Figure 7.16 – summarized)

1. result ← {R}; compute D . +

2. While a schema R in result violates 4NF:

i ​

Pick a non‑trivial MVD α →!! → β with α not a superkey.

Replace R by (α ∪ β ) and (R − β ) .
i i

3. End when all schemas are in 4NF.

​ ​

The algorithm guarantees losslessness because every step respects the MVD
condition.

📐 More Normal Forms

Normal Form Governing Constraint Remarks
5NF / Project‑Join Join dependencies Rarely used; reasoning is
Normal Form (PJNF) (generalization of MVDs) complex.
Domain‑Key Normal Form All integrity constraints Theoretically ideal but
(DKNF) (expressible as logical impractical; no complete
formulas) inference system.
2NF Historical; omitted in the Defined but not
main flow (see emphasized.
Exercise 7.19)
1NF Atomic domains (no Discussed next.
composite or multivalued
attributes)

Note: PJNF and DKNF are seldom applied in practice because the associated
constraints are difficult to manage and lack sound‑complete inference rules.

🏷
🏷 First Normal Form (1NF)
Definition (1NF) – A relation schema R is in first normal form iff every attribute
domain is atomic (indivisible).

Non‑Atomic Examples
Non‑Atomic Value Reason
Set of names (e.g., {Alice, Bob}) Contains multiple separate items.
Composite attribute address (street, city) Has internal structure.
Multivalued attribute phone_numbers Holds a collection per tuple.
Encoded ID like "CS001" Can be split into department code and
numeric part.
Atomic domain: Single, indivisible values (e.g., integers, single‑word strings).
When an attribute’s domain can be decomposed (e.g., splitting "CS001" into
dept_code and emp_no), the relation violates 1NF and must be rewritten so
each component becomes its own attribute.

📊 Identification Numbers & Primary Keys

Using identification numbers that embed additional information (e.g.,
department code) couples application logic with the database schema.
When such an identifier is used as a primary key, any change in the encoded
attribute (e.g., employee moves to another department) forces a cascade of
updates across all tables that reference the key.
This creates two problems:
1. Maintenance burden – the programmer must write extra code to
locate and modify every occurrence.
2. Potential inconsistency – if any reference is missed, the database
becomes logically inconsistent.

Key Insight – Prefer surrogate keys (simple, system‑generated identifiers) that carry
no business meaning, keeping the interpretation of attributes separate from the key.
🗂 First Normal Form Revisited
A domain is atomic when each value is indivisible. The earlier course identifier
example (CS‑101) is treated as atomic by the database as long as the
application does not split it into department and number parts.
Set‑valued attributes (e.g., a list of section IDs stored with each instructor)
introduce redundant storage and can lead to inconsistencies when updates
are performed in only one place.

Definition (1NF) – A relation schema R is in first normal form iff every attribute
domain is atomic.

Non‑Atomic Constructs & Their Trade‑offs

Construct Typical Use Advantage Drawback
Composite‑valued Entities with Reduces number of Requires extra code
attribute (e.g., naturally grouped attributes to query individual
address = (street, fields components
city))
Set‑valued Many‑to‑many Simpler schema at a Redundant data;
attribute (e.g., relationships glance updates must be
instructor → captured inside one duplicated; harder
{section₁, section₂}) tuple to enforce
referential integrity
Atomic attribute Normalized designs Straightforward May increase
(e.g., dept_name) queries; easy to number of tables
enforce FDs (requires joins)
Modern DBMSs (e.g., PostgreSQL, Oracle) support non‑atomic types (arrays,
JSON) because converting data back and forth incurs runtime overhead.
While the textbook restricts itself to relations in 1NF for formal analysis,
practical systems often retain non‑atomic values where they simplify
application code.

📈 Database‑Design Process (Section 7.9)

1. Origin of the schema r(R)
 From an E‑R diagram → relational schemas (Section 7.1.1).
Single large relation containing all attributes of interest, later
broken down by normalization.
Ad‑hoc design → test against desired normal forms.
2. Normalization within the process
If the initial schema is not in the target normal form, apply lossless
decomposition (as described earlier) to obtain smaller,
well‑structured schemas.
3. Denormalization for performance
After achieving a normalized design, designers may deliberately
re‑introduce redundancy (e.g., storing a frequently queried attribute
in multiple tables) to improve query speed.
This trade‑off must be weighed against the risk of update
anomalies.
4. Bad designs not caught by normalization
Schemas that satisfy all normal forms can still be semantically poor
(e.g., missing essential relationships, inappropriate use of surrogate
keys).
Such issues are usually identified by domain analysis and business
rule validation, not by formal normalization alone.

🧩 E‑R Model and Normalization (7.9.1)

A well‑crafted E‑R diagram usually yields relation schemas that are already
close to BCNF.
Functional dependencies that appear after conversion often signal poor E‑R
modeling.
Example: dept_name → dept_address on an Instructor entity
indicates that department should be a separate entity with its own
relation.
Multivalued dependencies (MVDs) arise from two main sources:
1. Many‑to‑many relationship sets – each entity gets its own table,
plus a separate table for the relationship.
2. Multivalued attributes – represented by a table containing the
attribute and the primary key of the owning entity (e.g., Instructor(ID,
phone_number)).
 Observation – The universal‑relation approach (single massive table) often masks
the need for MVDs and 4NF because it starts from a non‑normalized baseline.

🌐 Universal‑Relation Approach
Assumes a single relation with all attributes of interest, defining the complete
view of the database.
Limitation:
Difficult to associate dependent data correctly (e.g., a takes record
cannot be tied to the appropriate course title without additional
logic).
Lacks temporal semantics and other advanced constraints unless
explicitly added.
Modern SQL standards (SQL:2011) introduce temporal extensions to
overcome some of these shortcomings.

⏳ Temporal Data in Relational Databases

SQL:2011 Temporal Features
Valid‑time period: period for validtime (start, end) attaches a time interval to
each tuple, indicating when the data is considered true.
Temporal primary key: declared as

primary key (course_id, validtime) without overlaps

ensuring no two rows for the same course_id have overlapping validity periods.
Temporal foreign‑key constraints (theoretically) allow a period to be
specified on both referencing and referenced attributes, but no major DBMS
currently enforces them.
DBMS Support Overview
DBMS Temporal Primary‑Key Temporal Foreign‑Key
Support Support
IBM DB2 ✔︎ ✖︎

Teradata ✔︎ (partial) ✖︎ (not enforced)

PostgreSQL ✖︎ (native) → uses exclude ✖︎

constraint
Others (e.g., MySQL, ✖︎ ✖︎
Oracle)
PostgreSQL workaround:

ALTER TABLE course

ADD CONSTRAINT uniq_course_time
EXCLUDE (course_id WITH =, validtime WITH &&);

validtime is of type tsrange (timestamp range).

The && operator returns true when two ranges overlap; the
EXCLUDE constraint prohibits such overlaps for identical course_id
values.
Temporal Relational Algebra
Selection / Projection – output tuples retain the same valid‑time interval as
the input tuple.
Temporal Join – the resulting tuple’s valid time is the intersection of the input
tuples’ intervals; if the intervals do not intersect, the tuple is omitted.

Note – No commercial DBMS implements temporal joins natively; they must be

expressed via explicit SQL queries that compute the interval intersection.

📌 Key Takeaways
Avoid embedding business semantics in primary keys; use surrogate keys to
keep data and logic separate.
First normal form is a baseline; modern systems may store non‑atomic values
when they simplify application code, but designers must manage the associated
redundancy.
The database‑design process moves from high‑level E‑R models to
normalized relational schemas, with optional denormalization for performance.
Functional and multivalued dependencies guide refinement of E‑R diagrams;
most many‑to‑many relationships naturally lead to 4NF‑compliant designs.
Temporal extensions (SQL:2011) add validity intervals and enable temporal
keys, though full support varies across DBMSs.
Understanding the algebraic semantics of temporal operations (selection,
projection, join) is essential for designing correct temporal queries.