Normalization in DBMS: 1NF, 2NF, 3NF and BCNF | Part 5

DBMS Part 5: normalization ko step-by-step samjho. Part 4 mein relations aur queries dekhe. Ab schema ko aise design karte hain ki student/course details baar-baar copy na karni padhein. Yeh general notes hain; particular university ka official syllabus nahi.

1. Normalization aur anomalies: proper definition

Definition: Database normalization relation schemas ko functional dependencies ke basis par organize/decompose karne ki process hai, taki unwanted redundancy aur update, insertion, deletion anomalies kam hon. Decomposition lossless honi chahiye: decomposed tables ko join karne par original information sahi wapas mile. Dependency preservation bhi desirable hai, lekin BCNF mein kabhi compromise hota hai.

Worked relation: Enroll(student_id,student_name,course_id,course_title,marks). Rows: (101,Asha,10,DBMS,82), (101,Asha,20,OS,74), (102,Ravi,10,DBMS,68). Asha ka naam do baar aur DBMS title do baar hai. Asha ka naam badalne par dono rows update na hui to update anomaly. Naya course bina enrollment row ke store na ho to insertion anomaly. DBMS ke last student ko delete karte hi course info bhi gayab ho to deletion anomaly.

2. Functional dependency aur keys

FD X → Y: relation ke har valid state mein agar do rows ka X same hai, to unka Y bhi same hoga. Yeh business rule hai, sirf current sample mein coincidence nahi. Yahan student_id → student_name; course_id → course_title; (student_id,course_id) → marks. Agar repeat enrollments per term allowed hain to key/FD ko term ke saath revise karna padega.

Candidate key: minimal attribute set jo poori row ko uniquely determine kare. Superkey: koi bhi set jo poori row identify kare, minimal hona zaroori nahi. Prime attribute: koi attribute jo kam se kam ek candidate key ka member ho. Is initial Enroll ka candidate key (student_id,course_id) hai, assuming one enrollment per course per student.

3. 1NF: atomic cells, repeating group nahi

First Normal Form (1NF): har column apne chosen domain ke atomic values rakhe, repeating groups/list-valued field na ho. student_id=101, courses="DBMS, OS" ko ek cell mein rakhna us model mein 1NF nahi. Alag Enrollment rows (101,10) aur (101,20) banao. Atomic ka matlab context-dependent hai: address ko ek string rakhna allowed ho sakta hai jab components par query nahi karni. 1NF alone redundancy solve nahi karta.

4. 2NF: composite key par partial dependency hatao

Second Normal Form (2NF): relation 1NF mein ho aur har non-prime attribute har candidate key par fully functionally dependent ho; kisi candidate key ke proper subset par depend na kare. Simple exam shortcut: composite key ka sirf aadha part kisi non-key column ko determine nahi karna chahiye.

Enroll key (student_id,course_id): student_name sirf student_id par, course_title sirf course_id par dependent hai. Dono partial dependencies hain, isliye 2NF nahi. Split: Students(student_id,student_name), Courses(course_id,course_title), Enrollment(student_id,course_id,marks). Marks dono IDs se milkar decide hote hain. Agar sab candidate keys single-attribute hain, non-empty proper key subset ki partial dependency nahi hogi; phir bhi 3NF issue ho sakta hai. Ek selected primary key ko dekhna enough nahi: doosre candidate keys bhi check karo.

5. 3NF: transitive dependency aur formal rule

Third Normal Form (3NF): 2NF mein ho; formal FD test ke mutabik har nontrivial X → A ke liye ya X superkey ho ya A prime attribute ho. Basic exam intuition: non-key attribute ko kisi doosre non-key attribute se derive karne wali transitive dependency hatao.

Example: Students(student_id,name,dept_id,dept_name), with student_id → dept_id and dept_id → dept_name. dept_name student_id se dept_id ke through milta hai, isliye ek department ka naam kai students mein duplicate hota hai. Split Students(student_id,name,dept_id) aur Departments(dept_id,dept_name). Foreign key dept_id se link. 3NF ka prime-attribute exception yaad rakho; sirf "no transitive dependencies" har formal case ko capture nahi karta.

6. BCNF: determinant must be superkey

Boyce-Codd Normal Form (BCNF): har nontrivial FD X → Y ke liye X superkey hona chahiye. Yeh 3NF se stronger hai; har BCNF relation 3NF hota hai, ulta zaroori nahi.

3NF but not BCNF example: Teaching(student,course,instructor), assumptions: ek student ek course mein ek instructor se padhta hai, aur har instructor ek hi course padhata hai; ek student course ko ek hi instructor se leta hai. FDs (student,course) → instructor aur instructor → course. Candidate keys (student,course) aur (student,instructor) hain. course prime attribute hai, so instructor → course 3NF pass karta hai; instructor akela superkey nahi, so BCNF fail. Is FD par Teaching ko InstructorCourse(instructor,course) aur StudentInstructor(student,instructor) mein split karna in FDs ke under lossless hai, par original (student,course) → instructor constraint decomposition ke baad direct single-table constraint ke roop mein preserve na ho. Assumptions badalengi to keys bhi badlenge.

Form	Main check	Failure example
1NF	Atomic values, no repeating group	Courses list in one cell
2NF	No partial dependency of non-prime on candidate key	student_id → student_name in Enrollment
3NF	FD left side superkey or right side prime	dept_id → dept_name in Students
BCNF	Every nontrivial FD determinant is superkey	instructor → course in Teaching

7. Lossless join vs dependency preservation

Lossless: decomposed tables ka join original valid rows de, spurious rows na add kare. Dependency preserving: original FDs ko decomposed tables par alag-alag enforce/check kar sakein, join karke validation na karni pade. Sahi 3NF synthesis algorithm se lossless aur dependency-preserving decomposition milti hai; BCNF lossless ho sakta hai par dependency preservation lose kar sakta hai. "Zyada tables = automatically better" nahi; requirements aur query needs matter karti hain.

8. Enrollment ka FD aur decomposition diagram

Original: Enroll
student_id → student_name
course_id → course_title
(student_id, course_id) → marks
↓ partial dependencies remove karo
Students(student_id, student_name)
Courses(course_id, course_title)
Enrollment(student_id, course_id, marks)
Enrollment ke IDs → parent tables ke primary keys

Student name ek student row mein aur course title ek course row mein store hota hai. Enrollment sirf relationship aur marks store karta hai. Neeche SQL ko fresh SQLite database mein run karo.

PRAGMA foreign_keys = ON;
CREATE TABLE Students (student_id INTEGER PRIMARY KEY, student_name TEXT NOT NULL);
CREATE TABLE Courses (course_id INTEGER PRIMARY KEY, course_title TEXT NOT NULL);
CREATE TABLE Enrollment (
    student_id INTEGER REFERENCES Students(student_id),
    course_id INTEGER REFERENCES Courses(course_id),
    marks INTEGER NOT NULL,
    PRIMARY KEY (student_id,course_id)
);
INSERT INTO Students VALUES (101,'Asha'),(102,'Ravi');
INSERT INTO Courses VALUES (10,'DBMS'),(20,'OS');
INSERT INTO Enrollment VALUES (101,10,82),(101,20,74),(102,10,68);
SELECT s.student_id,s.student_name,c.course_id,c.course_title,e.marks
FROM Enrollment e
JOIN Students s ON s.student_id=e.student_id
JOIN Courses c ON c.course_id=e.course_id
ORDER BY s.student_id,c.course_id;

student_id	student_name	course_id	course_title	marks
101	Asha	10	DBMS	82
101	Asha	20	OS	74
102	Ravi	10	DBMS	68

Actual join ne original teen rows exactly wapas di. Yeh sample check hai; har valid database state ki lossless guarantee FD reasoning se aati hai, sirf teen rows se nahi.

9. Lossless join ka binary test

R ko R1 aur R2 mein split karne par, common attributes (R1 ∩ R2) agar F+ ke under R1 ya R2 ko determine karein, decomposition lossless hai. F+ ka matlab given FDs aur unse logically nikli dependencies. Yeh FD-based binary-decomposition criterion hai; multi-table decomposition par blindly ek intersection test mat lagao.

Enroll se Students split karne ka common column student_id hai. student_id → Students ke saare attributes, so first split lossless. Remaining relation se Courses split karne ka common course_id Courses ko determine karta hai. Dono successive lossless steps se final decomposition lossless hai.

10. Spurious rows ka executed counterexample

Assume Original(A,B,C) ke liye B → A aur B → C valid rules nahi hain. Sirf common B hone se join safe nahi hota:

CREATE TABLE Original (A TEXT,B INTEGER,C TEXT);
INSERT INTO Original VALUES ('a1',1,'c1'),('a2',1,'c2');
CREATE TABLE AB AS SELECT DISTINCT A,B FROM Original;
CREATE TABLE BC AS SELECT DISTINCT B,C FROM Original;
SELECT A,B,C FROM AB NATURAL JOIN BC ORDER BY A,C;

A	B	C	Original mein?
a1	1	c1	Yes
a1	1	c2	No: spurious
a2	1	c1	No: spurious
a2	1	c2	Yes

Do original rows se chaar joined rows mile. Extra (a1,1,c2) aur (a2,1,c1) fabricated combinations hain: decomposition lossy hai.

11. Teaching example: keys ko program se check karo

Short names S=student, C=course, I=instructor. Given SC → I and I → C. Candidate keys SC and SI; I+ sirf CI hai, isliye I superkey nahi.

from itertools import combinations
attrs = set("SCI")  # Student, Course, Instructor
fds = [(set("SC"), set("I")), (set("I"), set("C"))]

def closure(seed):
    found = set(seed)
    while True:
        old = found.copy()
        for left, right in fds:
            if left <= found:
                found |= right
        if old == found:
            return found

keys = []
for size in range(1, len(attrs) + 1):
    for parts in combinations(sorted(attrs), size):
        key = set(parts)
        if closure(key) == attrs and not any(k <= key for k in keys):
            keys.append(key)
print("Keys:", ["".join(sorted(k)) for k in keys])
print("I+:", "".join(sorted(closure("I"))))

Keys: ['CS', 'IS']
I+: CI

All three attributes prime hain kyunki candidate keys ka union SCI hai. I → C ka right side prime hai, so 3NF pass; I superkey nahi, so BCNF fail. InstructorCourse(IC) aur StudentInstructor(SI) ka intersection I hai, aur I → IC, so split lossless hai.

12. Lossless hona dependency-preserving hona nahi hai

InstructorCourse	StudentInstructor
(I1,C1)	(S1,I1)
(I2,C1)	(S1,I2)

Dono local tables apne projected FDs satisfy karti hain. Join mein (S1,C1,I1) aur (S1,C1,I2) aate hain, jo SC → I todte hain. Original constraint ko enforce karne ke liye cross-table check chahiye. Isliye yeh decomposition lossless hone ke saath dependency-preserving nahi hai; dono properties alag hain.

13. Exam mein follow karne ka workflow

1. Attributes aur actual business FDs likho, sample coincidence ko rule mat banao.
2. Closure se sab candidate keys nikalo; har key ki minimality check karo.
3. Candidate keys ka union lo: wahi prime attributes hain.
4. Nontrivial FDs par 2NF, 3NF aur BCNF rules apply karo.
5. Violating FD par decomposition likho aur lossless reasoning do.
6. Projected FDs se original dependencies enforce hoti hain ya nahi, alag check karo.

14. More end-topic answers

1. Har superkey candidate key hai? Nahi, candidate key minimal superkey hai.
2. Sample rows unique hone se FD prove ho jati hai? Nahi; FD har valid state ka rule hai.
3. Table ki primary key badalne se normal form badal jata hai? Nahi, formal tests sab candidate keys aur FDs dekhte hain.
4. BCNF split hamesha dependencies preserve karta hai? Nahi, Teaching example counterexample hai.
5. Normalization aur faster queries same thing hain? Nahi. Schema correctness aur measured performance alag concerns hain.
6. Foreign keys alone har FD implement karti hain? Nahi. Foreign keys referenced-row existence enforce karti hain; keys, constraints aur application checks bhi chahiye ho sakte hain.

Verification: enrollment SQL/join, spurious-row SQL and Python closure checker executed. Teaching dependency counterexample also checked by joining both local tables. Formal definitions checked against CMU normal-forms notes.

15. Practice questions: short answers

1. 2NF example mein problem kya? (student_id,course_id) key ka proper part student_id student_name ko determine karta hai; partial dependency.
2. 3NF formal rule? Nontrivial X → A ke liye X superkey ya A prime.
3. BCNF ka rule? Har nontrivial FD ka determinant superkey.
4. 3NF vs BCNF trade-off? BCNF stronger redundancy control de sakta hai, par decomposition kuch FDs preserve na kare; lossless join alag check hai.

Five-minute revision

FD business rule hai. Key minimal identity, superkey nonminimal bhi ho sakti hai. 1NF atomic; 2NF no partial key dependency; 3NF X superkey or A prime; BCNF X superkey. Enrollment ko Students, Courses, Enrollment mein split karke anomalies samjho. Lossless join aur dependency preservation ko kabhi ek hi cheez mat samjho.

Sources: MIT OCW: Schema Design; CMU: Normal Forms lecture notes; CMU: Schema Refinement and Normalization. Next: transactions and ACID.

DBMS Exam Notes series: Previous: Part 4: Relational Algebra | DBMS series and hub | Next: Part 6: Transactions and ACID