BCNF, 4NF, 5NF আর decomposition-এর গুণ

১ · 3NF-এর পরেও যে ফাঁক থাকে — শিক্ষার্থী, কোর্স আর শিক্ষক

পর্ব ৩৫-এ দেখেছেন functional dependency (FD) X → Y মানে “X-এর মান জানলে Y-এর মান নির্ধারিত”, আর attribute closure X⁺ দিয়ে বের করা যায় X থেকে কী কী নির্ধারিত হয়। পর্ব ৩৬-এ 1NF, 2NF আর 3NF দিয়ে টেবিল ভেঙে partial আর transitive dependency সরিয়েছেন। মনে হতে পারে কাজ শেষ। কিন্তু একটি ছোট, বিখ্যাত টেবিল দেখায়, 3NF-এ থেকেও anomaly থাকতে পারে।

একটি বিশ্ববিদ্যালয়ের নিয়ম ভাবুন। একটি কোর্স (যেমন DBMS) একাধিক শিক্ষক পড়ান, প্রত্যেকে নিজের section. কিন্তু প্রত্যেক শিক্ষক ঠিক একটি কোর্স পড়ান। আর একজন শিক্ষার্থী একটি কোর্স একজন শিক্ষকের কাছেই নেন। রেজিস্টারে সব এক টেবিলে লেখা: sci(student, course, instructor). সংক্ষেপে S, C, I.

নিচের এডিটরের টেবিলে ৫টি সারি: Arif আর Chayon DBMS পড়েন Karim-এর কাছে, Bithi DBMS পড়েন Nasrin-এর কাছে, আর Arif ও Bithi Networks পড়েন Rafiq-এর কাছে। primary key (student, course). এবার দুটি সাধারণ ভুল ঘটান:

-- Karim এখন থেকে AI পড়াবেন; ভুল করে শুধু Arif-এর সারিটি বদলানো হলো
UPDATE sci SET course = 'AI' WHERE student = 'Arif' AND instructor = 'Karim';
SELECT instructor, GROUP_CONCAT(DISTINCT course) AS courses
FROM sci GROUP BY instructor HAVING COUNT(DISTINCT course) > 1;

-- Bithi DBMS ছেড়ে দিলেন: Nasrin যে DBMS পড়ান, সেই তথ্যও গেল
DELETE FROM sci WHERE student = 'Bithi' AND course = 'DBMS';
SELECT * FROM sci WHERE instructor = 'Nasrin';

অথচ এই টেবিল 3NF-এ আছে, অংশ ২-এ তা প্রমাণ করব। সমস্যার মূল হলো I → C: বাঁ দিকের I একটি superkey নয়, তাই একই (I, C) জোড়া বহু সারিতে ফিরে আসে। 3NF এই FD-কে ছাড় দেয়, কারণ C একটি candidate key-র অংশ। BCNF সেই ছাড় তুলে দেয়।

২ · BCNF — প্রতিটি নির্ধারক একটি superkey

দুই সংজ্ঞা পাশাপাশি রাখলেই একটি উপপাদ্য চোখে পড়ে। BCNF ⇒ 3NF: BCNF-এ প্রতিটি FD (ক) বা (খ) মানে। 3NF চায় (ক), (খ) বা (গ)। যে (ক) বা (খ) মানে, সে নিশ্চয়ই “(ক) বা (খ) বা (গ)” মানে। ∎ উল্টোটা সত্য নয়। পার্থক্য শুধু বিকল্প (গ)-তে: বাঁ দিক superkey নয়, কিন্তু ডান দিক prime — এমন FD 3NF মেনে নেয়, BCNF নয়।

পরীক্ষার কাজে একটি সুবিধা আছে: BCNF যাচাইয়ে F⁺-এর সব FD দেখতে হয় না। R-এর ওপর দেওয়া F-এর প্রতিটি FD X → Y দেখলেই চলে। কোনোটিতে X⁺ ≠ R হলে লঙ্ঘন, না হলে R BCNF-এ (প্রমাণ: F-এর সব বাঁ দিক superkey হলে, Armstrong-এর নিয়মে উৎপন্ন প্রতিটি non-trivial FD-র বাঁ দিকও superkey হয়)। তবে সাবধান, এই shortcut শুধু মূল R-এর জন্য। ভাঙার পর টুকরোর জন্য খাটে না, অংশ ৩-এ দেখবেন।

এবার শিক্ষার্থী–কোর্স–শিক্ষকের টেবিলে দুটি পরীক্ষা ধাপে ধাপে চালান:

একটি দরকারি তথ্য মনে রাখুন: দুই attribute-এর যেকোনো relation BCNF-এ থাকে। R(A, B)-তে non-trivial FD হতে পারে শুধু A → B বা B → A. A → B থাকলে A⁺ = {A, B} = R, তাই A superkey. B → A-র বেলাতেও একই কথা। এজন্যই BCNF ভাঙনের শেষে প্রায়ই দুই-কলামের টেবিল দেখা যায়।

৩ · BCNF-এ ভাঙার অ্যালগরিদম

BCNF-এ নেই এমন টেবিলকে decomposition বা ভাঙনের মাধ্যমে ছোট টেবিলে আনা হয়। ভাঙন মানে R-এর attribute-গুলোকে কয়েকটি উপসেট R₁, …, Rₙ-এ ভাগ করা, যাদের মিলন R, আর প্রতিটি টুকরোর ডেটা হলো মূল ডেটার projection. অ্যালগরিদম সহজ: লঙ্ঘনকারী একটি FD খুঁজুন, তার বাঁ দিক ধরে দুই ভাগ করুন, প্রতিটি ভাগে আবার একই কাজ।

BCNF-DECOMPOSE(R, F):
  result = { R }
  while result-এ এমন Ri আছে, যা BCNF-এ নেই:
      Ri-তে লঙ্ঘনকারী X → Y খুঁজুন   // X ∩ Y = ∅, X⁺ ⊉ Ri
      Y = (X⁺ ∩ Ri) − X              // ডান দিক যতটা সম্ভব বড়
      Ri-এর জায়গায় বসান:
          (X ∪ Y)                    // X এখানে key
          (Ri − Y)                   // X দুই টুকরোতেই থাকে
  return result

প্রতিবার টুকরো ছোট হয়, আর দুই কলামের টুকরো সবসময় BCNF-এ। তাই অ্যালগরিদম থামবেই। ডান দিক X⁺ পর্যন্ত বড় নেওয়ার কারণ: একসাথে যত বেশি attribute সরানো যায়, ভাঙনের ধাপ তত কম লাগে। এখন একটি বাস্তবধর্মী উদাহরণে চালাই। একটি ফলাফল-রেজিস্টার: R(roll, name, dept, head, course, grade), যেখানে head মানে বিভাগীয় প্রধান।

এবার শিক্ষার্থী–কোর্স–শিক্ষকে অ্যালগরিদম চালান। লঙ্ঘনকারী FD একটিই: I → C, যেখানে I⁺ = {I, C}. তাই R₁ = (I, C) আর R₂ = R − {C} = (S, I). SQL-এ এরা হলো teaches(instructor, course), যার key instructor, আর takes(student, instructor), যার key (student, instructor). দুটিই দুই-কলামের, তাই BCNF-এ। Karim-এর কোর্স এখন এক ঘরেই লেখা — update anomaly গেল। কিন্তু একটি নিয়ম কোথায় গেল, দেখুন:

-- BCNF-এ update anomaly নেই: Karim-এর কোর্স এক ঘরেই
UPDATE teaches SET course = 'AI' WHERE instructor = 'Karim';
UPDATE teaches SET course = 'DBMS' WHERE instructor = 'Karim';

-- Arif DBMS পড়ছেন Karim-এর কাছে; এবার Nasrin-এর কাছেও (একই কোর্স!)
INSERT INTO takes VALUES ('Arif', 'Nasrin');

-- দুই টেবিল জুড়ে দেখি: {student, course} → instructor কি টিকে আছে?
SELECT t.student, c.course, COUNT(*) AS instructors
FROM takes t JOIN teaches c ON c.instructor = t.instructor
GROUP BY t.student, c.course HAVING COUNT(*) > 1;

৪ · Lossless join — ভেঙে জোড়া দিলে ঠিক আগের টেবিল

যেকোনোভাবে ভাঙলেই চলবে না। ভাঙার পর দরকার হলে টুকরোগুলো natural join দিয়ে জুড়ে মূল তথ্য ফেরত পেতে হবে। ধরুন একটি বড় বই ছিঁড়ে দুই খণ্ড করলেন। পৃষ্ঠা নম্বর না থাকলে আবার সাজাতে গিয়ে ভুল ক্রমের অনেক “বই” তৈরি হবে। Join-এ সেই পৃষ্ঠা নম্বরের কাজ করে দুই টুকরোর সাধারণ attribute.

একটি সূক্ষ্ম কথা: r ⊆ π_R1(r) ⋈ π_R2(r) সবসময় সত্য। r-এর প্রতিটি সারি t-এর দুই টুকরো t[R₁] আর t[R₂] সাধারণ attribute-এ মেলে, তাই join-এ t আবার তৈরি হয়। অর্থাৎ join কখনো মূল সারি হারায় না। Lossy ভাঙন সারি হারায় না, বরং বাড়তি spurious tuple যোগ করে। “Loss” মানে হারায় তথ্য: কোন সারিগুলো সত্যি ছিল, তা আর আলাদা করা যায় না।

নিচের এডিটরে students(roll, name, dept) — ৪ জন: 101 Rahim CSE, 102 Karima EEE, 103 Rahim EEE, 104 Nusrat CSE. একজন ডিজাইনার ভাঙলেন (roll, dept) আর (name, dept)-এ। সাধারণ attribute শুধু dept.

-- খারাপ ভাঙন: (roll, dept) আর (name, dept) — মিল শুধু dept-এ
CREATE TABLE r1 AS SELECT roll, dept FROM students;
CREATE TABLE r2 AS SELECT DISTINCT name, dept FROM students;

SELECT COUNT(*) AS original FROM students;
SELECT r1.roll, r2.name, r1.dept
FROM r1 JOIN r2 ON r1.dept = r2.dept ORDER BY r1.roll, r2.name;

একই টেবিল এবার (roll, name) আর (roll, dept)-এ ভাঙুন। সাধারণ attribute roll, যা দুই টুকরোরই key:

-- ভালো ভাঙন: (roll, name) আর (roll, dept) — মিল roll-এ, যা key
CREATE TABLE r1 AS SELECT roll, name FROM students;
CREATE TABLE r2 AS SELECT roll, dept FROM students;

SELECT COUNT(*) AS joined FROM r1 JOIN r2 ON r1.roll = r2.roll;
-- join-এ এমন কোনো সারি কি আছে, যা মূল টেবিলে নেই?
SELECT r1.roll, r1.name, r2.dept FROM r1 JOIN r2 ON r1.roll = r2.roll
EXCEPT
SELECT roll, name, dept FROM students;

Binary test আর তার প্রমাণ

অর্থাৎ সাধারণ অংশটি অন্তত একটি টুকরোর superkey হতে হবে। ভালো ভাঙনে roll → (roll, name), তাই lossless. খারাপ ভাঙনে dept → roll নয়, dept → name-ও নয়, তাই lossy. এই শর্ত যে যথেষ্ট, তার প্রমাণ ছোট:

প্রমাণ (যথেষ্টতা): ধরুন X = R₁ ∩ R₂ আর X → R₁. Join-এর যেকোনো সারি t নিন। Join-এর সংজ্ঞায় r-এ একটি সারি t₁ আছে যার t₁[R₁] = t[R₁], আর একটি t₂ আছে যার t₂[R₂] = t[R₂]. দুটিই X-এ t-এর সাথে মেলে, তাই t₁[X] = t₂[X]. r মানে X → R₁, তাই t₁[R₁] = t₂[R₁]. তাহলে t₂[R₁] = t[R₁] আর t₂[R₂] = t[R₂], অর্থাৎ t₂ = t. তাই t ∈ r — join-এ নতুন কিছু নেই। আগেই দেখেছি r ⊆ join, তাই সমান। ∎

প্রয়োজনীয়তা (সংক্ষেপে): শুধু FD-ই নিয়ম হলে, দুই শর্তের কোনোটি না খাটলে দুই সারির একটি বৈধ instance বানানো যায়, যারা X-এ মেলে কিন্তু R₁ − X আর R₂ − X-এ আলাদা। তাদের join-এ চারটি সারি, যার দুটি ভুয়া। খারাপ ভাঙনের 101 আর 104 ঠিক এমন জোড়া। এই উপপাদ্যের আদি রূপকে Heath-এর উপপাদ্য (১৯৭১) বলা হয়: R(A, B, C)-তে A → B খাটলে (A, B) আর (A, C)-তে ভাঙন lossless.

এ থেকেই আসে একটি বড় ফল: BCNF decomposition সবসময় lossless. অ্যালগরিদমের প্রতিটি ধাপে টুকরো দুটি (X ∪ Y) আর (Ri − Y), তাদের ছেদ ঠিক X, আর X → X ∪ Y. অর্থাৎ binary test প্রতিবার পাস করে। Lossless ভাঙনের কোনো টুকরোকে আবার lossless-ভাবে ভাঙলে পুরোটাও lossless থাকে, তাই শেষ ফলও lossless. ∎

তিন বা বেশি টুকরো — chase (tableau) পদ্ধতি

টুকরো দুইয়ের বেশি হলে binary test সরাসরি খাটে না। তখন ব্যবহার হয় chase test, যা Aho, Beeri আর Ullman ১৯৭৯ সালে আনুষ্ঠানিক রূপ দেন। একটি টেবিল বানান, যাতে প্রতিটি টুকরোর জন্য একটি সারি। টুকরোর নিজের কলামে লিখুন “জানা” প্রতীক aⱼ, বাকি কলামে “অজানা” bᵢⱼ. তারপর FD প্রয়োগ করুন: দুটি সারি X-এ মিললে Y-তেও তাদের সমান করুন (একটি a থাকলে সবাই সেই a). কোনো সারি পুরোটা a হয়ে গেলে ভাঙন lossless; আর কিছু বদলানো না গেলে, অথচ সব-a সারি নেই, তবে lossy.

৫ · Dependency preservation — নিয়মগুলো কি টুকরোয় টিকে থাকে

Lossless হলেই কাজ শেষ নয়। অংশ ৩-এর এডিটরে দেখেছেন, BCNF ভাঙনের পর Arif-কে DBMS-এ দুজন শিক্ষক দেওয়া গেল। ডেটা হারায়নি, কিন্তু একটি নিয়ম পাহারাহীন হয়েছে। ভালো ভাঙনের দ্বিতীয় গুণ তাই: প্রতিটি FD যেন কোনো একটি টুকরোর ভেতরে, শুধু সেই টুকরো দেখে যাচাই করা যায়। তাহলে প্রতিটি INSERT বা UPDATE-এ শুধু সেই টেবিলের key আর constraint দেখলেই চলে, join লাগে না।

F⁺ বের করা ব্যয়বহুল — attribute সংখ্যার সূচকীয় হারে বাড়তে পারে। তাই বাস্তবে F-এর প্রতিটি X → Y আলাদা করে যাচাই করা হয়, F⁺ না বানিয়েই:

PRESERVED(X → Y, {R1..Rn}, F):
  result = X
  repeat
      for each Ri:
          t = ((result ∩ Ri)⁺ ∩ Ri)   // closure মূল F দিয়ে
          result = result ∪ t
  until result আর বদলায় না
  return Y ⊆ result

যুক্তিটি এমন: result হলো “টুকরোগুলোর ভেতরের নিয়ম দিয়েই X থেকে যা যা পাওয়া যায়”। প্রতিটি টুকরোয় আমরা শুধু সেই টুকরোর attribute-গুলো দিয়ে এগোই। শেষে Y পাওয়া গেলে FD-টি টুকরোগুলো মিলিয়েই রক্ষা পায়। শিক্ষক-কোর্সের ভাঙনে পরীক্ষাটি চালান:

বড় উপপাদ্য — BCNF বনাম 3NF

শিক্ষক-কোর্সের উদাহরণে এই দ্বন্দ্ব এড়ানোর উপায় নেই, প্রমাণও ছোট। R থেকে ছোট কোনো টুকরো, অর্থাৎ দুই attribute-এর টুকরো, নিলে সেখানে non-trivial FD পাওয়া যায় কেবল I → C — {S, C}-তে কেউ কাউকে নির্ধারণ করে না, {S, I}-তেও না। তাই যেকোনো ভাঙনের টুকরোগুলো মিলে শুধু I → C জানে, যা দিয়ে SC → I আসে না। SC → I রাখতে হলে একটি টুকরোকে পুরো (S, C, I) হতে হবে — সেটি তো BCNF-এ নেই। ∎ তাই এখানে বেছে নিতে হয়: BCNF (redundancy নেই, একটি নিয়ম পাহারাহীন) অথবা 3NF (নিয়ম পাহারায়, কিছু redundancy).

3NF synthesis অ্যালগরিদম উল্টো দিক থেকে আসে। F-এর canonical cover (পর্ব ৩৫) নিন; প্রতিটি X → Y থেকে একটি টেবিল (X ∪ Y) বানান; কোনো টেবিলে candidate key না থাকলে একটি key-টেবিল যোগ করুন; অন্য টেবিলের ভেতরে পুরোপুরি পড়ে যাওয়া টেবিল বাদ দিন। এখানে cover {SC → I, I → C} থেকে আসে (S, C, I) আর (I, C). দ্বিতীয়টি প্রথমটির ভেতরে পড়ে, তাই ফল মূল R-ই — 3NF-এ, সব নিয়ম রক্ষিত।

হারানো নিয়মের দাম — trigger দিয়ে পাহারা

BCNF বেছে নিলে SC → I রক্ষার দায় নিতে হবে অ্যাপ বা ডেটাবেসের কোডকে। প্রতিটি নতুন takes-সারির আগে join করে দেখতে হবে, এই শিক্ষার্থীর এই কোর্সে আগেই কোনো শিক্ষক আছেন কি না। SQL standard-এর CREATE ASSERTION এমন বহু-টেবিলের নিয়মের জন্যই, কিন্তু প্রচলিত বড় DBMS-গুলো এটি বাস্তবায়ন করেনি। ভরসা তাই trigger (পর্ব ২৯):

CREATE TRIGGER one_instructor_per_course BEFORE INSERT ON takes
WHEN EXISTS (SELECT 1 FROM takes t
  JOIN teaches a ON a.instructor = t.instructor
  JOIN teaches b ON b.instructor = NEW.instructor
  WHERE t.student = NEW.student AND a.course = b.course)
BEGIN
  SELECT RAISE(ABORT, 'student already has an instructor for this course');
END;
-- বৈধ: Chayon Networks নিলেন Rafiq-এর কাছে
INSERT INTO takes VALUES ('Chayon', 'Rafiq');
-- অবৈধ: Arif-এর DBMS-এ আগেই Karim আছেন
INSERT INTO takes VALUES ('Arif', 'Nasrin');

একটি মাঝামাঝি কৌশলও আছে: teaches-এ UNIQUE (instructor, course) রাখুন, আর তিন-কলামের sci টেবিলটি রেখে দিন, যেখানে key (student, course) আর FOREIGN KEY (instructor, course) REFERENCES teaches (instructor, course). তাহলে SC → I রক্ষা করে sci-এর key, আর I → C রক্ষা করে foreign key — কোনো trigger ছাড়াই। দাম: course দুই জায়গায় লেখা, কিন্তু DBMS নিজে দুই কপি মিলিয়ে রাখে। এটি নিয়ন্ত্রিত redundancy, পর্ব ৩৮-এর denormalization-এর এক আত্মীয়।

৬ · Multivalued dependency আর 4NF — দুটি স্বাধীন তালিকা

এবার এমন redundancy, যা কোনো FD দিয়ে ধরা যায় না। একটি কোচিং সেন্টার প্রত্যেক শিক্ষকের দুটি তালিকা রাখে: কোন কোন বিষয় পড়াতে পারেন, আর কোন কোন ভাষায় পড়াতে পারেন। দুটি তালিকা একে অপরের ওপর নির্ভর করে না — Karim যে বিষয়ই পড়ান, তিনি বাংলা আর ইংরেজি দুটিতেই পারেন। এক টেবিলে রাখলে teacher_skills(teacher, subject, language), যার key তিনটি কলাম মিলে। কোনো non-trivial FD নেই, তাই টেবিলটি BCNF-এ। তবু Karim-এর ৩টি বিষয় আর ২টি ভাষা মানে ৩ × ২ = ৬টি সারি — প্রতিটি সংমিশ্রণ আলাদা করে লিখতে হয়।

এখানে teacher →→ subject আর teacher →→ language. কয়েকটি মৌলিক তথ্য: (১) প্রতিটি FD একটি MVD — X → Y হলে X →→ Y. (২) পরিপূরক নিয়ম: X →→ Y হলে X →→ R − X − Y, তাই MVD সাধারণত জোড়ায় লেখা হয়: teacher →→ subject | language. (৩) X →→ Y trivial, যদি Y ⊆ X বা X ∪ Y = R.

-- Karim এখন হিন্দিতেও পড়াতে পারেন — কিন্তু ঢোকানো হলো একটিই সারি
INSERT INTO teacher_skills VALUES ('Karim', 'DBMS', 'Hindi');

-- MVD টিকে থাকলে সারি = (বিষয়ের সংখ্যা) × (ভাষার সংখ্যা)
SELECT teacher, COUNT(*) AS rows_now,
       COUNT(DISTINCT subject) * COUNT(DISTINCT language) AS rows_needed
FROM teacher_skills GROUP BY teacher;

teacher_skills-এ teacher superkey নয়, তাই 4NF ভাঙে। সমাধান BCNF-এর মতোই: লঙ্ঘনকারী X →→ Y ধরে (X ∪ Y) আর (R − Y)-তে ভাঙা — এখানে (teacher, subject) আর (teacher, language). এই ভাঙন lossless, কারণ binary test-এর সাধারণ রূপ (Fagin, ১৯৭৭) বলে: {R₁, R₂} lossless ⇔ (R₁ ∩ R₂) →→ (R₁ − R₂). FD-র শর্তটি এরই বিশেষ রূপ।

-- 4NF: নতুন ভাষা মানে একটিই নতুন সারি
INSERT INTO teacher_language VALUES ('Karim', 'Hindi');

SELECT (SELECT COUNT(*) FROM teacher_subject)
     + (SELECT COUNT(*) FROM teacher_language) AS rows_stored;

-- join করলে পুরোনো টেবিলের সব সংমিশ্রণ ফিরে আসে
SELECT s.teacher, COUNT(*) AS combinations
FROM teacher_subject s JOIN teacher_language l ON l.teacher = s.teacher
GROUP BY s.teacher;

৭ · Join dependency আর 5NF — সরবরাহকারী, যন্ত্রাংশ আর প্রকল্প

MVD হলো দুই টুকরোয় lossless ভাঙনের শর্ত। এর সাধারণ রূপ join dependency: *(R₁, R₂, …, Rₙ) খাটে, যদি প্রতিটি বৈধ r-এ r = π_R1(r) ⋈ … ⋈ π_Rn(r) হয়। X →→ Y আসলে *(XY, XZ). কিছু নিয়ম আছে, যা দুই টুকরোয় ধরা যায় না, কিন্তু তিনটিতে যায়।

একটি নির্মাণ প্রতিষ্ঠানের spj(supplier, part, project): কোন সরবরাহকারী কোন প্রকল্পে কোন যন্ত্রাংশ দেয়। ধরুন ব্যবসার একটি চক্রাকার নিয়ম আছে: যদি S1 যন্ত্রাংশ P1 সরবরাহ করে (কোনো প্রকল্পে), আর P1 লাগে প্রকল্প J1-এ, আর S1 প্রকল্প J1-এ কিছু সরবরাহ করে — তাহলে S1 প্রকল্প J1-এ P1 সরবরাহ করে। নিয়মটি FD নয়, MVD-ও নয়। কিন্তু এর মানে হলো *(SP, PJ, SJ) — তিনটি জোড়া-টেবিল থেকে পুরো তথ্য ফেরত আসে।

এডিটরের টেবিলে ৪টি সারি: (S1, P1, J2), (S1, P2, J1), (S2, P1, J1), (S1, P1, J1). শেষ সারিটি নিয়মের ফল — প্রথম তিনটি থেকে এটি বাধ্যতামূলক। এবার তিনটি জোড়া-projection বানিয়ে জোড়া দিন:

CREATE TABLE sp AS SELECT DISTINCT supplier, part FROM spj;
CREATE TABLE pj AS SELECT DISTINCT part, project FROM spj;
CREATE TABLE sj AS SELECT DISTINCT supplier, project FROM spj;

-- দুটি অংশ জুড়লে: ভুয়া সারি আসে কি?
SELECT sp.supplier, sp.part, pj.project FROM sp JOIN pj ON pj.part = sp.part
EXCEPT SELECT * FROM spj;

-- তিনটি অংশ একসাথে জুড়লে কয়টি সারি?
SELECT COUNT(*) AS three_way FROM sp
JOIN pj ON pj.part = sp.part
JOIN sj ON sj.supplier = sp.supplier AND sj.project = pj.project;

spj-এর একমাত্র key তিনটি কলাম মিলে, আর *(SP, PJ, SJ) সেই key থেকে আসে না। তাই spj 4NF-এ (কোনো non-trivial MVD নেই) থেকেও 5NF-এ নেই। 5NF-এ আনতে তিনটি টেবিল sp, pj, sj রাখুন। চক্রাকার নিয়মটি তখন গঠনের ভেতরেই থাকে, আর “S1 এখন P3 দেয়” জাতীয় তথ্য একবারই লিখতে হয়। তবে মূল্য আছে: প্রশ্নের উত্তর পেতে তিন-টেবিলের join লাগে, আর নিয়মটি সত্যিই ব্যবসায় খাটে কি না, তা নিশ্চিত হতে হয়।

৮ · 6NF, DKNF আর normal form-এর সিঁড়ি — বাস্তবে কতদূর যাবেন

সিঁড়ির আরও দুটি ধাপ নাম হিসেবে জেনে রাখুন। 6NF: টেবিলে কোনো non-trivial join dependency-ই নেই — সাধারণত একটি key আর বড়জোর একটি অন্য কলাম। এর প্রধান ব্যবহার সময়ভিত্তিক ডেটায়: একজন কর্মচারীর বেতন, পদবি আর শাখা আলাদা আলাদা সময়ে বদলায়। এক টেবিলে (emp, salary, designation, from, to) রাখলে শুধু বেতন বদলালেও পুরো সারি নতুন করে লিখতে হয়। 6NF-এ প্রতিটি attribute নিজের টেবিলে, নিজের সময়-সীমা নিয়ে থাকে, যা temporal table-এর আলোচনায় আসে। DKNF (domain-key normal form): সব constraint শুধু domain constraint আর key constraint থেকেই আসে — একটি আদর্শ, যা সাধারণ নিয়মে পৌঁছানোর কোনো অ্যালগরিদম নেই।

বাস্তব অবস্থান

• লক্ষ্য 3NF বা BCNF. এদের মধ্যে পার্থক্য আসে শুধু যখন candidate key একাধিক আর পরস্পর-ঢাকা (overlapping). বেশিরভাগ টেবিলে 3NF আর BCNF একই।
• BCNF ভাঙতে একটি নিয়ম হারালে দুটি পথ: 3NF-এ থেকে key দিয়ে পাহারা, বা BCNF-এ গিয়ে trigger/অ্যাপ-কোড দিয়ে পাহারা। কোন নিয়ম কতবার ভাঙার ঝুঁকি, তা দেখে বেছে নিন।
• 4NF-এর সমস্যা সাধারণত আসে দুটি আলাদা one-to-many তালিকা এক টেবিলে মেশালে — ER মডেল থেকে ঠিকমতো টেবিল বানালে (পর্ব ১০) এমনিতেই এড়ানো যায়।
• 5NF-এর সমস্যা বিরল, আসে শুধু ternary relationship-এ চক্রাকার ব্যবসায়িক নিয়ম থাকলে। কিন্তু ঘটলে নিঃশব্দে ভুল ডেটা তৈরি হয়।
• পড়ার গতির জন্য ইচ্ছে করে নিয়ম ভাঙা — denormalization — পরের পর্বের বিষয়। আগে normalize করে জানুন কী ভাঙছেন।

৯ · পরীক্ষার ধাঁচের সমস্যা — পূর্ণ সমাধানসহ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই অধ্যায় থেকে সাধারণত একটি FD-সেট দিয়ে চার-পাঁচটি প্রশ্ন একসাথে আসে। নিজে আগে চেষ্টা করুন, তারপর সমাধান মেলান।

সমস্যা ১. R(A, B, C, D), F = {AB → C, C → A, C → D}. (ক) সব candidate key বের করুন। (খ) R সর্বোচ্চ কোন normal form-এ? (গ) BCNF-এ ভাঙুন; ভাঙনটি কি dependency preserving? (ঘ) 3NF synthesis করুন।

সমস্যা ২. R(A, B, C), F = {A → B}. ভাঙন (ক) {(A, B), (B, C)} আর (খ) {(A, B), (A, C)} — কোনটি lossless? Lossy হলে একটি প্রতি-উদাহরণ দিন।

সমস্যা ৩. R(course, teacher, book): প্রতিটি কোর্সের একদল শিক্ষক আর একটি নির্দিষ্ট বইয়ের তালিকা আছে; কোর্সের যেকোনো শিক্ষক সব বই ব্যবহার করেন। কোনো FD নেই। R কি BCNF-এ? 4NF-এ? প্রয়োজনে ভাঙুন।

১০ · AI-এর যুগে normalization

AI-কে “এই টেবিলটি BCNF-এ নিয়ে যাও” বললে সে দ্রুত কয়েকটি টেবিল দেয়, প্রায়ই সঠিকও। কিন্তু এই অধ্যায়ের ভুলগুলো চোখে পড়ে না, কারণ ভাঙা টেবিলও চলে, কোয়েরিও চলে। AI সাধারণত যা ভুল করে:

AI-এর দেওয়া ভাঙন হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি FD আমি ব্যবসার একটি নিয়মের সাথে মেলাতে পারি; কোনোটি শুধু কলামের নাম দেখে অনুমান নয়
• প্রতিটি ভাঙনের ধাপে টুকরো দুটির ছেদ অন্তত একটি টুকরোর superkey
• নমুনা ডেটায় টুকরোগুলো join করে সারি গুনেছি আর EXCEPT দিয়ে ভুয়া সারি খুঁজেছি
• প্রতিটি FD-র dependency preservation দেখেছি; হারানো থাকলে trigger বা 3NF-এর সিদ্ধান্ত নিয়েছি
• প্রতিটি নতুন টেবিলে primary key, foreign key আর দরকারি UNIQUE আছে
• নতুন schema-য় আসল কোয়েরিগুলো চালিয়ে ফল পুরোনোটার সাথে মিলিয়েছি, আর দরকারি join-এ index আছে কি না EXPLAIN দিয়ে দেখেছি