PadhaikoAll subjects

Database Constraints and Normalization

Database Management System (ENCT 301)

Open in the Padhaiko app

4.1 Integrity constraints and domain constraints

Integrity constraints guard a database against accidental damage by ensuring that authorized changes (INSERT, UPDATE, DELETE) never violate semantic consistency rules.

Definition

Categories of Relational Integrity Constraints

  1. Domain Constraints: Restrict the set of permissible values for each attribute (e.g., data type INT, VARCHAR(40), DATE, NOT NULL, DEFAULT, and user-defined domain checks via CREATE DOMAIN or column CHECK clauses). Every value must be atomic and belong to the declared domain.
  2. Entity Integrity Constraint: States that no primary key attribute may take a NULL value, because primary key values uniquely identify individual tuples in a relation.
  3. Key / Uniqueness Constraints (UNIQUE, PRIMARY KEY): Ensure that no two distinct tuples in a relation share the same value(s) on a candidate key.
  4. Referential Integrity Constraint (FOREIGN KEY): Ensures that a value appearing in one relation (the referencing relation) for a given set of attributes also appears for a certain set of attributes in another relation (the referenced relation), or is NULL.
  5. Tuple-Level CHECK Constraints: Arbitrary Boolean predicates evaluated on each individual row during insertion or modification (e.g., CHECK (EndDate >= StartDate)).
Domain, Check, and Referential Integrity ActionsSQL
CREATE DOMAIN GradePoint AS NUMERIC(3, 2)
    CONSTRAINT ValidGPA CHECK (VALUE >= 0.00 AND VALUE <= 4.00);

CREATE TABLE Department (
    DeptID   INT PRIMARY KEY,
    DeptName VARCHAR(40) NOT NULL UNIQUE
);

CREATE TABLE Enrollment (
    RollNo   INT NOT NULL,
    DeptID   INT,
    Credits  INT CHECK (Credits BETWEEN 1 AND 6),
    GPA      GradePoint,
    PRIMARY KEY (RollNo),
    FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
        ON DELETE CASCADE
        ON UPDATE CASCADE
);

Referential Integrity Violation Actions

When deleting or updating a referenced parent tuple, the DBMS enforces one of four configured actions:


4.2 Assertions

A table-level CHECK constraint can only inspect columns of the single row being inserted or updated; it cannot reliably enforce constraints spanning multiple tables or involving aggregate summaries across rows (especially on DELETE).

Definition

SQL Assertions

An assertion is a database-wide predicate expressing a condition that the database must always satisfy across one or more relations:

When an assertion is created, the system tests it immediately for validity. Thereafter, every modification to any referenced relation is rejected if it would cause the assertion predicate to evaluate to FALSE.

Assertion Examples Across Tables and AggregatesSQL
-- 1. Every loan must have at least one borrower in the Borrower table
CREATE ASSERTION Loan_Must_Have_Borrower
CHECK (NOT EXISTS (
    SELECT * FROM Loan L
    WHERE NOT EXISTS (
        SELECT * FROM Borrower B WHERE B.LoanNo = L.LoanNo
    )
));

-- 2. Total loan amount per branch must remain under 50,000,000
CREATE ASSERTION Branch_Loan_Cap
CHECK (NOT EXISTS (
    SELECT BranchName FROM Loan
    GROUP BY BranchName
    HAVING SUM(Amount) >= 50000000
));

4.3 Functional dependencies

A functional dependency (FD) is a formal constraint between two sets of attributes in a relation schema , generalizing the concept of a key.

Definition

Functional Dependency and Armstrong's Axioms

Let be a relation schema and let and . The functional dependency (" functionally determines ") holds on if, in every legal instance , whenever two tuples agree on all attributes of , they must also agree on all attributes of :

Attribute Closure (), Candidate Keys, and Canonical Cover ()

Properties of Relational Decompositions

When splitting a relation into sub-relations to remove redundancy, two properties are critical:

  1. Lossless-Join Decomposition: Joining the decomposed tables back must never generate spurious extra tuples (). For a binary decomposition of , it is lossless if and only if at least one of the following holds in :

(In words: the common attributes must form a superkey of at least one of or .)

  1. Dependency Preservation: Every FD in can be checked within a single decomposed table (or inferred from ), without performing expensive joins across tables.

4.4 Different normal forms (1NF, 2NF, 3NF, BCNF)

Normalization is a systematic schema-refinement process that decomposes poorly designed tables to eliminate data redundancy and the three update anomalies:

Definition

Hierarchy of Normal Forms (1NF, 2NF, 3NF, BCNF)

Let be a relation schema. An attribute is prime if it belongs to at least one candidate key of ; otherwise it is non-prime.

  1. First Normal Form (1NF): Every attribute domain contains only atomic (indivisible) values—no repeating groups, arrays, or nested tables inside a single cell.
  2. Second Normal Form (2NF): is in 2NF if it is in 1NF and has no partial functional dependency—that is, no non-prime attribute depends on a proper subset of any candidate key of . (Note: Every relation in 1NF whose candidate keys are all single-attribute is automatically in 2NF.)
  3. Third Normal Form (3NF): is in 3NF if it is in 2NF and has no transitive functional dependency of a non-prime attribute on a candidate key. Formally, is in 3NF under if for every FD , at least one of the following three conditions holds:
    • is trivial (), OR
    • is a superkey for , OR
    • Every attribute is a prime attribute (contained in some candidate key of ).
  4. Boyce–Codd Normal Form (BCNF): A strictly stronger form of 3NF: is in BCNF under if for every FD , at least one of the following holds:
    • is trivial (), OR
    • is a superkey for . (BCNF drops the prime-attribute exception of 3NF: every determinant of a non-trivial FD must be a superkey.)
AspectThird Normal Form (3NF)Boyce–Codd Normal Form (BCNF)
Permitted Non-Trivial FDs is a superkey OR is a prime attribute. must be a superkey (no prime-attribute exception).
RedundancyEliminates transitive dependencies of non-prime attributes; tiny redundancy can remain if a prime attribute depends on a non-superkey.Eliminates all redundancy discoverable from functional dependencies.
Lossless-Join DecompositionAlways achievable.Always achievable.
Dependency PreservationAlways achievable (via canonical-cover synthesis).Not always achievable (some schemas lose an FD when forced into BCNF).

Worked Out Examples

Example 4.1

4.1

Consider a relation schema with functional dependencies:

  1. Compute the attribute closures , , and .
  2. Find all candidate keys of and the total number of superkeys containing .
  3. Compute a canonical cover for .

Computing Attribute Closures:

  • Starting with : .
  • Starting with : . No other LHS is contained in , so:
  • Starting with : .
  • Check : .

Finding All Candidate Keys:

  • Single-attribute closures: and , whereas do not reach (, , , ).
  • Two-attribute closures without or : since and , we need a set reaching or . Only reaches (without already using or ). Neither nor alone reaches , so is minimal!
  • Any set containing , , or is a superkey; no other minimal subset exists.
    • Candidate keys: , , .
    • Superkeys containing : Since is already a superkey, any subset of the remaining attributes can be added, giving superkeys containing .

Computing the Canonical Cover :

Answer:
  1. , , .
  2. Candidate keys: , , ; number of superkeys containing .
  3. Canonical cover: .
Example 4.2

4.2

Consider the relation schema ProjectAssign(EmpID, ProjID, EmpName, ProjTitle, Hours, Dept) with functional dependencies:

  1. Identify the candidate key(s) and determine the current normal form of ProjectAssign.
  2. Normalize the schema step by step up to BCNF, verifying lossless join and dependency preservation.

Finding Candidate Keys and Checking 2NF:

  • Computing yields all attributes . Neither EmpID nor ProjID appears on any RHS, so is the sole candidate key.
  • Prime attributes: EmpID, ProjID. Non-prime attributes: EmpName, ProjTitle, Hours, Dept.
  • Check for partial dependencies:
    • (proper subset of candidate key determines non-prime attributes violates 2NF!).
    • (also violates 2NF!).
  • Hence ProjectAssign is currently in 1NF only (not 2NF).

Decomposing to 2NF (and Checking 3NF / BCNF): Eliminate partial dependencies by placing attributes determined by each subset into separate tables while retaining the full key + Hours:

  1. Employee(EmpID [PK], EmpName, Dept) — FD: . Here is a superkey BCNF (and 3NF).
  2. Project(ProjID [PK], ProjTitle) — FD: . Here is a superkey BCNF.
  3. WorksOn(EmpID [PK, FK], ProjID [PK, FK], Hours) — FD: . Determinant is the superkey BCNF.

Verifying Lossless Join and Dependency Preservation:

  • Lossless join: Employee WorksOn (key of Employee); Project WorksOn (key of Project). Every split shares a superkey of one side, so the join is lossless.
  • Dependency preservation: Every FD in is completely contained inside one of the three resulting tables, so all FDs are preserved.
Answer:
  1. Candidate key: ; highest current normal form: 1NF (fails 2NF due to partial dependencies on EmpID and ProjID).
  2. BCNF (also 3NF and 2NF) Decomposition:
    • Employee(EmpID [PK], EmpName, Dept)
    • Project(ProjID [PK], ProjTitle)
    • WorksOn(EmpID [PK, FK], ProjID [PK, FK], Hours) The decomposition is both lossless-join and dependency-preserving.
Example 4.3

4.3

Examine the classic relation with functional dependencies:

Determine whether is in 3NF and whether is in BCNF. If not in BCNF, decompose into BCNF and check whether dependency preservation holds.

Finding All Candidate Keys:

  • (neither nor is , so is a candidate key).
  • (, so is also a candidate key!).
  • Candidate keys: and .
  • Prime attributes: (every attribute is prime!).

Testing 3NF vs. BCNF:

  • Test : is a superkey satisfies both 3NF and BCNF.
  • Test :
    • Is a superkey? No () violates BCNF!
    • Is a prime attribute? Yes () satisfies 3NF!

Therefore, is in 3NF, but not in BCNF.

Decomposing into BCNF and Checking Dependency Preservation:

Answer:

is in 3NF (since is prime in ) but not in BCNF (since is not a superkey). Decomposing into and achieves BCNF and is lossless, but loses dependency preservation for .


Exercises

Practice Exercises — Constraints & Normalization

Question 1

Explain domain constraints, entity integrity, and referential integrity in relational databases. What are the four actions an RDBMS can take when a referenced parent tuple is deleted?

Constraint Definitions:

  • Domain Constraints: Require every column value to be atomic and drawn from the attribute's declared type/range (INT, CHECK, NOT NULL).
  • Entity Integrity: Requires that no attribute belonging to a relation's PRIMARY KEY can contain NULL.
  • Referential Integrity: Requires every non-null FOREIGN KEY value in a child table to match an existing candidate/primary key value in the referenced parent table.

Four ON DELETE Referential Actions:

  1. RESTRICT / NO ACTION: Rejects the deletion if referencing child tuples exist.
  2. CASCADE: Deletes all matching child tuples automatically.
  3. SET NULL: Sets the child foreign key attribute(s) to NULL.
  4. SET DEFAULT: Sets the child foreign key attribute(s) to their declared DEFAULT value.
Answer:

Domain constraints enforce valid atomic column values, entity integrity forbids NULL in primary keys, and referential integrity ensures foreign keys match parent keys (or NULL). On parent deletion, the DBMS can apply RESTRICT/NO ACTION, CASCADE, SET NULL, or SET DEFAULT.

Question 2

What is an SQL assertion? Write an SQL assertion enforcing that "no instructor may teach more than courses in the same semester" given Teaches(InstID, CourseID, Semester). Explain why CHECK on a single row cannot enforce this.

Why Row-Level CHECK Fails: A table CHECK constraint inspects only the attributes of one tuple at a time. Counting how many courses an instructor teaches in a given semester requires grouping across multiple rows (GROUP BY InstID, Semester), which requires an assertion (database-wide constraint).

Writing the SQL Assertion:

Assertion Limiting Courses per SemesterSQL
CREATE ASSERTION Max_Three_Courses_Per_Sem
CHECK (NOT EXISTS (
    SELECT InstID, Semester
    FROM Teaches
    GROUP BY InstID, Semester
    HAVING COUNT(*) > 3
));
Answer:

An SQL assertion (CREATE ASSERTION ... CHECK (...)) enforces database-wide invariants involving multiple rows or tables that row-level CHECK constraints cannot express. The assertion uses NOT EXISTS (SELECT InstID, Semester FROM Teaches GROUP BY InstID, Semester HAVING COUNT(*) > 3).

Question 3

State Armstrong's three axioms for functional dependencies and prove the Union Rule () using only those three axioms.

Armstrong's Axioms:

  1. Reflexivity: If , then .
  2. Augmentation: If , then .
  3. Transitivity: If and , then .

Proof of the Union Rule: Given and :

  1. Apply Augmentation to using : , which simplifies to .
  2. Apply Augmentation to using : .
  3. Apply Transitivity to and : .
Answer:

Armstrong's axioms are Reflexivity, Augmentation, and Transitivity. Augmenting by gives ; augmenting by gives ; applying transitivity yields .

Question 4

Given and :

  1. Find all candidate keys of and the number of superkeys of .
  2. Determine the highest normal form (1NF, 2NF, 3NF, or BCNF) of , and give a lossless-join BCNF decomposition of .

Finding Candidate Keys and Superkeys:

  • Attribute does not appear on the RHS of any FD, so must belong to every candidate key.
  • . Therefore is the only candidate key!
  • Total superkeys (any subset containing plus any subset of ): (and superkeys containing is ).

Testing Normal Form and BCNF Decomposition:

  • Every non-trivial FD , , has a non-prime RHS attribute ( are all non-prime) and a non-superkey LHS ().
  • Since is a single-attribute candidate key, there are no partial dependencies, so is in 2NF, but fails 3NF (transitive dependencies ).
  • BCNF decomposition:
    1. Split on : (, BCNF) and ().
    2. In , and violate BCNF (neither nor is a superkey of ). Split on : (BCNF) and (, BCNF).
    • Verify lossless join: (superkey of and ); (superkey of ).
Answer:
  1. Sole candidate key: ( total superkeys).
  2. Highest normal form: 2NF (fails 3NF due to transitive dependencies). Lossless BCNF decomposition: , , and .
Question 5

Why are unnormalized relations vulnerable to insertion, deletion, and update anomalies? Contrast 3NF and BCNF with respect to redundancy, lossless-join decomposition, and dependency preservation.

Anomalies in Unnormalized Relations: Mixing facts about two distinct entities into one table (e.g., Student and Department in one row) duplicates department details across every student row:

  • Update anomaly: Changing a department's office requires updating multiple rows; missing one leaves inconsistent data.
  • Insertion anomaly: Cannot record a newly created department if zero students are enrolled yet (without NULL primary keys).
  • Deletion anomaly: Deleting the last student in a department erases the department's metadata entirely.

3NF vs. BCNF Trade-off:

  • BCNF requires every non-trivial FD determinant to be a superkey, eliminating all FD-driven redundancy and guaranteeing a lossless join, but cannot always preserve all FDs.
  • 3NF relaxes BCNF by allowing non-superkey determinants if the RHS attribute is prime; it always guarantees both lossless join and dependency preservation, at the cost of slight potential redundancy when overlapping candidate keys exist.
Answer:

Unnormalized tables mix entity attributes, causing insertion, deletion, and update anomalies. BCNF removes all FD redundancy with lossless joins but may sacrifice dependency preservation, whereas 3NF always guarantees both lossless joins and dependency preservation.

← Relational Query LanguagesQuery Processing and Optimization →