Integrity constraints, normal forms

Integrity constraints

Definition. Integrity constraints restrict legal database states. Domain constraints restrict values; key constraints require uniqueness; entity integrity requires primary-key attributes non-NULL; referential integrity requires foreign-key values to match referenced keys or be NULL when allowed.

Example. Enrollment.Sid references Student.Sid; deleting a student may be rejected, cascaded, or set null according to policy.

Exam point. A foreign key must reference a candidate key under standard relational semantics.

Solved examples

Example — foreign-key check. Student IDs are {1,2}; Enrollment contains Sid values 1,3.

1. Sid=1 references an existing Student.
2. Sid=3 has no matching parent row.
3. The instance violates referential integrity unless null/other policy applies; value 3 is not null.

Functional dependencies

Definition. A functional dependency X→Y on relation R holds if any two tuples agreeing on X also agree on Y. It expresses a constraint on all legal instances, not just observed rows. X and Y are attribute sets; trivial dependencies have Y⊆X.

Example. StudentID→Name,Dept if each ID identifies exactly one student profile.

Exam point. A sample table cannot prove a dependency; it can only exhibit a violation.

Solved examples

Example 1 — test a relation instance. Rows are (A,B,C): (1,x,p),(1,x,q),(2,y,r). Does A→B hold? Does A→C hold?

1. The two rows with A=1 have B=x in both, so no counterexample to A→B.
2. Those rows have C=p and C=q, which differ.
3. This instance satisfies A→B but violates A→C.

Example 2 — trivial FD. Is AB→A trivial?

1. Right side {A} is a subset of left side {A,B}.
2. Yes, it follows by reflexivity for every relation.

Attribute closure and candidate keys

Definition. The closure X⁺ under FD set F is all attributes functionally determined by X. To compute it, start with X and repeatedly add Y when an FD U→Y has U contained in the current closure. X is a superkey if X⁺ contains all attributes; a candidate key is a minimal superkey.

Example. For F={A→B,B→C}, A⁺={A,B,C}.

Exam point. Minimality must be checked by removing attributes; a superkey is not necessarily a candidate key.

Solved examples

Example 1 — closure. R(A,B,C,D), F={A→B,B→C,AC→D}. Compute A⁺.

1. Start A⁺={A}.
2. A→B adds B: {A,B}.
3. B→C adds C: {A,B,C}.
4. AC→D applies, adding D.
5. A⁺={A,B,C,D}; A is a candidate key because it is a singleton superkey.

Example 2 — candidate keys. R(A,B,C), F={A→B,C→A}. Find a candidate key.

1. C⁺ starts {C}; C→A adds A; A→B adds B.
2. C⁺=ABC, so C is a superkey.
3. C is a singleton and therefore has no nonempty proper subset that is a key.
4. Candidate key is {C}. A alone yields AB but not C.

Armstrong axioms and FD reasoning

Definition. Armstrong's axioms are reflexivity, augmentation, and transitivity. They are sound and complete for reasoning about functional dependencies. Derived rules include union, decomposition, and pseudotransitivity.

Example. From A→B and B→C, infer A→C by transitivity.

Exam point. Attribute closure is usually the most direct way to test whether F implies a dependency.

Solved example

Example — implication test. F={A→BC, C→D}. Does F imply A→D?

1. A→BC gives A→B and A→C by decomposition.
2. C→D and A→C imply A→D by transitivity/pseudotransitivity.
3. Equivalently, A⁺={A,B,C,D}.
4. Yes, F implies A→D.

Minimal or canonical cover

Definition. A minimal cover is an equivalent FD set with singleton right sides, no extraneous left attributes, and no redundant dependencies. To compute it, split RHSs, minimize each LHS, then remove dependencies implied by the others.

Example. A→BC splits into A→B and A→C.

Exam point. Test extraneousness by closure under the appropriate FD set; a minimal cover need not be unique in exact presentation.

Solved example

Example — reduce a cover. F={A→BC, B→C, A→B}.

1. Split: A→B, A→C, B→C, A→B.
2. A→C is redundant because A→B and B→C imply it.
3. Remove duplicate A→B.
4. A minimal equivalent cover is {A→B,B→C}.

First, second, and third normal forms

Definition. 1NF requires atomic attribute values under the chosen domain model. 2NF requires 1NF and no nonprime attribute partially dependent on a proper subset of any candidate key. 3NF requires for each nontrivial X→A either X is a superkey or A is prime (belongs to some candidate key).

Example. If key is (StudentID,CourseID) and StudentID→StudentName, StudentName is partially dependent, violating 2NF when nonprime.

Exam point. 2NF is relevant only when a candidate key is composite; a single-attribute key has no proper nonempty subset.

Solved examples

Example 1 — 2NF violation. R(StudentID,CourseID,StudentName,Grade), key (StudentID,CourseID), FDs StudentID→StudentName and (StudentID,CourseID)→Grade.

1. StudentName is nonprime because it is not part of any candidate key.
2. It depends on StudentID, a proper subset of the composite key.
3. R violates 2NF. Decompose Student(StudentID,StudentName) and Enrollment(StudentID,CourseID,Grade).

Example 2 — 3NF test. R(A,B,C), key AB, FDs AB→C and C→B.

1. Candidate key AB; prime attributes A and B; C is nonprime.
2. C→B is nontrivial and C is not a superkey because C⁺={B,C}.
3. RHS B is prime.
4. The dependency satisfies 3NF via the prime-attribute alternative, but violates BCNF.

BCNF

Definition. A relation is in BCNF if for every nontrivial FD X→Y that holds, X is a superkey. BCNF is stronger than 3NF. Decomposing on a violating FD X→Y uses relations X∪Y and R−(Y−X); decomposition is lossless for that FD, but may not preserve all dependencies.

Example. In R(A,B,C) with A→B and A not a key, the FD violates BCNF.

Exam point. BCNF decomposition can lose dependency preservation; check dependencies after decomposition.

Solved examples

Example 1 — decompose. R(A,B,C), F={A→B,B→C}; candidate key A. Check BCNF.

1. A→B has A as a key, so it is fine.
2. B→C is nontrivial; B⁺={B,C}, not all attributes.
3. It violates BCNF.
4. Decompose on B→C into R1(B,C) and R2(A,B).
5. Both component relations satisfy BCNF under projected dependencies.

Example 2 — dependency preservation. For the decomposition above, can A→B and B→C be checked locally?

1. A→B is contained in R2(A,B).
2. B→C is contained in R1(B,C).
3. Both dependencies are preserved in this example. Other BCNF decompositions need not preserve all FDs.