Functional dependency — closure, key আর canonical cover

১ · খারাপ টেবিলের তিনটি রোগ — insert, update আর delete anomaly

একটি বিশ্ববিদ্যালয়ের পুরোনো অফিসের কথা ভাবুন। সেখানে একটিই মোটা রেজিস্টার খাতা। প্রতিটি লাইনে লেখা: শিক্ষার্থীর রোল, নাম, কোর্স কোড, কোর্সের নাম, শিক্ষকের নাম, শিক্ষকের বিভাগ আর গ্রেড। খাতাটি দেখতে সুবিধাজনক — এক লাইনেই সব। কিন্তু কয়েক মাস চালালেই সমস্যা শুরু হয়।

“Database Systems” কোর্সে ৬০ জন থাকলে কোর্সের নাম আর শিক্ষকের নাম ৬০ বার লেখা হয়। একে বলে data redundancy. শুধু কালি আর জায়গার অপচয় নয়, এটি তিনটি গুরুতর রোগের জন্ম দেয়। ডেটাবেস তত্ত্বে এদের বলে anomaly — অস্বাভাবিক আচরণ। নিচের ডায়াগ্রামে একটি ছোট নমুনায় তিনটিই দেখুন।

এবার তিনটি রোগ — update anomaly, delete anomaly আর insert anomaly — আসল SQL-এ দেখুন। নিচের এডিটরগুলো একটি বিশেষ টেবিল enrol_wide নিজে বানিয়ে নেয়। এর কলাম: student_id, student_name, course_id, course_title, instructor_id, instructor_name, inst_dept (শিক্ষকের বিভাগ) আর grade. Primary key (student_id, course_id). এতে ৬টি সারি — Arif আর Bristy দুজনেই CSE201 ও CSE301-এ, Chayon EEE101-এ, Dilruba CSE101-এ। সরলতার জন্য term কলাম রাখা হয়নি। প্রতিবার চালালে টেবিল নতুন করে তৈরি হয়, তাই নির্ভয়ে বদলান।

-- Update anomaly: কোর্সের নাম বদলালাম, কিন্তু একটি সারিতে
UPDATE enrol_wide SET course_title = 'Database Management'
WHERE student_id = 2101 AND course_id = 'CSE301';

SELECT student_id, course_id, course_title
FROM enrol_wide WHERE course_id = 'CSE301';

-- Delete anomaly: Dilruba CSE101 ছেড়ে দিলেন
DELETE FROM enrol_wide WHERE student_id = 2201;

-- CSE101 কোর্সটির নাম আর শিক্ষক এখন কোথায়?
SELECT course_id, course_title, instructor_name
FROM enrol_wide WHERE course_id = 'CSE101';

SELECT COUNT(*) AS rows_left FROM enrol_wide;

-- নতুন ভর্তি: শিক্ষার্থী আছে বলে ঢোকে
INSERT INTO enrol_wide VALUES (2102, 'Bristy Saha', 'CSE302',
  'Database Systems Lab', 6, 'Tasnim Chowdhury', 'CSE', NULL);

-- Insert anomaly: নতুন কোর্স, এখনো কোনো শিক্ষার্থী নেই
INSERT INTO enrol_wide (student_id, course_id, course_title,
  instructor_id, instructor_name, inst_dept)
VALUES (NULL, 'CSE401', 'Machine Learning', 2, 'Shahana Parvin', 'CSE');

তিনটি রোগেরই মূল এক: টেবিলে এমন একটি নির্ভরতা আছে — “course_id জানলে course_title জানা যায়” — যার বাম দিক পুরো key নয়। এই নির্ভরতাগুলোকে গাণিতিকভাবে লেখার ভাষাই functional dependency (সংক্ষেপে FD).

২ · Functional dependency — সংজ্ঞা আর ডেটা দিয়ে যাচাই

সহজ ভাষায়: X-এর মান জানলে Y-এর মান একটিই হতে পারে। NID নম্বর জানলে জন্মতারিখ একটিই — NID → জন্মতারিখ। bKash নম্বর জানলে অ্যাকাউন্টধারী একজনই। কিন্তু উল্টোটা সত্য নয়: একই জন্মতারিখে লাখো মানুষ, তাই জন্মতারিখ → NID নয়। “ফাংশন” শব্দটি গণিত থেকে: X থেকে Y-তে একটি ফাংশন, প্রতিটি ইনপুটের একটিই আউটপুট।

enrol_wide-এর ব্যবসার নিয়ম থেকে FD-গুলো লেখা যায়:

• student_id → student_name — একটি রোল একজনেরই
• course_id → course_title, instructor_id — একটি কোর্সের একটি নাম, একজন শিক্ষক (এই বিশ্ববিদ্যালয়ের নিয়মে)
• instructor_id → instructor_name, inst_dept — একজন শিক্ষক একটি বিভাগের
• student_id, course_id → grade — একটি ভর্তির একটি গ্রেড

লক্ষ করুন, key-র সংজ্ঞাও FD দিয়ে লেখা যায়: K একটি superkey ঠিক তখনই, যখন K → R (K সব attribute নির্ধারণ করে)। আর candidate key হলো এমন minimal K. পর্ব ৬-এর key এভাবে FD-র একটি বিশেষ ঘটনা।

Trivial আর non-trivial FD

কিছু FD সব relation-এ, সব সময় সত্য — কোনো নিয়ম না জেনেই। যেমন student_id, course_id → course_id: দুটি সারি (student_id, course_id)-তে মিললে course_id-তে তো মিলবেই। সাধারণভাবে Y ⊆ X হলে X → Y সবসময় সত্য; একে বলে trivial FD. Y-তে X-এর বাইরের অন্তত একটি attribute থাকলে FD-টি non-trivial — এগুলোই আসল তথ্য বহন করে। আর X ∩ Y = ∅ হলে তাকে কখনো কখনো “completely non-trivial” বলে।

FD আসে নিয়ম থেকে — ডেটা শুধু খণ্ডন করতে পারে

সংজ্ঞার “প্রতিটি বৈধ instance” অংশটি সবচেয়ে গুরুত্বপূর্ণ। FD হলো schema-র ধর্ম, ব্যবসার নিয়মের গাণিতিক রূপ। আজকের ডেটায় একটি FD খাটলেই সেটি নিয়ম হয়ে যায় না। কিন্তু একটি জোড়া সারিও যদি X-এ মেলে আর Y-তে না মেলে, তাহলে নিশ্চিত — এই ডেটার জন্য X → Y সত্য নয় (হয় নিয়মটি নেই, নয়তো ডেটা ভুল)।

GROUP BY একই X-এর সারিগুলো এক দলে আনে, COUNT(DISTINCT Y) গোনে দলে Y-এর কয়টি আলাদা মান, আর HAVING শুধু সেই দলগুলো রাখে যেখানে মান একাধিক — অর্থাৎ লঙ্ঘন। কোনো সারি না এলে এই ডেটায় FD খাটছে। প্রথমে enrol_wide-এ চারটি সম্ভাব্য FD একসাথে পরীক্ষা করুন:

-- প্রতিটি FD-র জন্য লঙ্ঘনকারী দলের সংখ্যা
SELECT 'course_id -> course_title' AS fd, COUNT(*) AS violations FROM
  (SELECT course_id FROM enrol_wide GROUP BY course_id
   HAVING COUNT(DISTINCT course_title) > 1)
UNION ALL
SELECT 'instructor_id -> inst_dept', COUNT(*) FROM
  (SELECT instructor_id FROM enrol_wide GROUP BY instructor_id
   HAVING COUNT(DISTINCT inst_dept) > 1)
UNION ALL
SELECT 'student_id -> student_name', COUNT(*) FROM
  (SELECT student_id FROM enrol_wide GROUP BY student_id
   HAVING COUNT(DISTINCT student_name) > 1)
UNION ALL
SELECT 'course_id -> grade', COUNT(*) FROM
  (SELECT course_id FROM enrol_wide GROUP BY course_id
   HAVING COUNT(DISTINCT grade) > 1);

এবার একটি “খারাপ update”-এর পর লঙ্ঘন ধরা দেখুন। কেউ Bristy-র CSE301 সারিতে শিক্ষকের নাম হাতে টাইপ করে একটু আলাদা লিখেছেন। চোখে পড়ে না, কিন্তু FD-পরীক্ষা ধরে ফেলে, আর GROUP_CONCAT(DISTINCT …) দেখায় কোন কোন মান সংঘাতে:

-- ভুল হাতে-টাইপ: একটি সারিতে শিক্ষকের নাম আলাদা
UPDATE enrol_wide SET instructor_name = 'Tasnim Chowdhury (CSE)'
WHERE student_id = 2102 AND course_id = 'CSE301';

-- instructor_id -> instructor_name এখনো খাটে?
SELECT instructor_id, COUNT(DISTINCT instructor_name) AS names,
       GROUP_CONCAT(DISTINCT instructor_name) AS values_seen
FROM enrol_wide GROUP BY instructor_id
HAVING COUNT(DISTINCT instructor_name) > 1;

আসল ডেটাবেসে — “খাটছে” মানেই নিয়ম নয়

এবার কোর্সের সাধারণ বিশ্ববিদ্যালয় ডেটাবেস (db-uni) নিই। এতে আছে departments (dept_id, name, building), instructors (instructor_id, name, dept_id, salary, mentor_id), students (student_id, name, dept_id, batch, cgpa), courses (course_id, title, dept_id, credits, instructor_id) আর enrollments (student_id, course_id, term, grade), যার key (student_id, course_id, term). তিনটি সম্ভাব্য FD পরীক্ষা করুন:

-- ১) একটি বিভাগের সব কোর্সের credit কি সমান? (dept_id -> credits)
SELECT dept_id, COUNT(DISTINCT credits) AS n, GROUP_CONCAT(DISTINCT credits) AS vals
FROM courses GROUP BY dept_id HAVING COUNT(DISTINCT credits) > 1;

-- ২) একজন শিক্ষক কি শুধু এক বিভাগের কোর্স পড়ান? (instructor_id -> dept_id)
SELECT instructor_id, COUNT(DISTINCT dept_id) AS n
FROM courses GROUP BY instructor_id HAVING COUNT(DISTINCT dept_id) > 1;

-- ৩) একজন একটি কোর্স কি একবারই নেন? (student_id, course_id -> term)
SELECT student_id, course_id, COUNT(DISTINCT term) AS n
FROM enrollments GROUP BY student_id, course_id HAVING COUNT(DISTINCT term) > 1;

দোকানের ডেটাবেসেও (db-shop: customers, categories, products, orders, আর order_items — order_id, product_id, quantity, unit_price) একটি শিক্ষণীয় উদাহরণ আছে। মনে হতে পারে product_id জানলেই দাম জানা যায়। পরীক্ষা করুন:

-- order_items-এ product_id -> unit_price খাটে?
SELECT product_id, COUNT(DISTINCT unit_price) AS prices,
       GROUP_CONCAT(DISTINCT unit_price) AS vals
FROM order_items GROUP BY product_id
HAVING COUNT(DISTINCT unit_price) > 1;

-- (order_id, product_id) -> unit_price খাটে?
SELECT order_id, product_id, COUNT(DISTINCT unit_price) AS n
FROM order_items GROUP BY order_id, product_id
HAVING COUNT(DISTINCT unit_price) > 1;

-- একটি সারিতে শিক্ষকের বিভাগ মুছে গেল (NULL)
UPDATE enrol_wide SET inst_dept = NULL
WHERE student_id = 2102 AND course_id = 'CSE201';

-- পদ্ধতি ১: COUNT(DISTINCT) — NULL বাদ পড়ে
SELECT instructor_id, COUNT(DISTINCT inst_dept) AS n
FROM enrol_wide GROUP BY instructor_id HAVING COUNT(DISTINCT inst_dept) > 1;

-- পদ্ধতি ২: আগে আলাদা জোড়া, তারপর গোনা
SELECT instructor_id, COUNT(*) AS n
FROM (SELECT DISTINCT instructor_id, inst_dept FROM enrol_wide)
GROUP BY instructor_id HAVING COUNT(*) > 1;

৩ · Armstrong-এর axiom — তিনটি নিয়ম, প্রমাণ আর তিনটি উপ-নিয়ম

ডিজাইনার সাধারণত কয়েকটি FD জানেন — ধরুন সেটটির নাম F. কিন্তু F থেকে আরও অনেক FD যুক্তি দিয়ে বের হয়। course_id → instructor_id আর instructor_id → inst_dept জানলে course_id → inst_dept-ও সত্য, যদিও কেউ সেটি আলাদা করে লেখেননি। F থেকে যত FD যৌক্তিকভাবে বের হয় (F নিজেসহ), তাদের সেটকে বলে F-এর closure, লেখা হয় F⁺. F⁺ বের করার নিয়মগুলোকে বলে inference rule. ১৯৭৪ সালে William W. Armstrong তিনটি নিয়ম দেন, যা আজ Armstrong-এর axiom নামে পরিচিত।

এখানে XZ মানে X ∪ Z (সেটের সংযোগ) — FD-র বইয়ে এভাবেই সংক্ষেপে লেখা হয়।

প্রমাণ — নিয়মগুলো sound (ভুল কিছু বের করে না)

একটি নিয়ম sound মানে: যে instance F মেনে চলে, সেটি নিয়ম থেকে পাওয়া FD-ও মেনে চলবে। প্রতিটির প্রমাণ সংজ্ঞা থেকে সরাসরি আসে। যেকোনো instance r আর তার দুটি tuple t₁, t₂ নিন।

• Reflexivity: ধরুন t₁[X] = t₂[X]. Y ⊆ X, তাই Y-এর প্রতিটি attribute X-এরও attribute, সেখানে দুটি tuple মেলে। অতএব t₁[Y] = t₂[Y]. ∎
• Augmentation: ধরুন t₁[XZ] = t₂[XZ]. তাহলে আলাদাভাবে t₁[X] = t₂[X] আর t₁[Z] = t₂[Z]. প্রথমটি থেকে X → Y দিয়ে t₁[Y] = t₂[Y]. Y-তে আর Z-এ দুটিতেই মেলে, তাই t₁[YZ] = t₂[YZ]. ∎
• Transitivity: ধরুন t₁[X] = t₂[X]. X → Y দিয়ে t₁[Y] = t₂[Y]; তারপর Y → Z দিয়ে t₁[Z] = t₂[Z]. ∎

উল্টো দিকটি আরও গভীর: নিয়মগুলো complete — F থেকে যে FD-ই সত্যিই বের হয়, তা এই তিনটি নিয়ম বারবার প্রয়োগ করে পাওয়া যাবেই। এর প্রমাণ অংশ ৪-এর closure অ্যালগরিদমের সাথে দেখবেন।

তিনটি উপ-নিয়ম (derived rule) — axiom থেকে প্রমাণ

পরীক্ষায় প্রায়ই বলা হয়: “axiom ব্যবহার করে প্রমাণ করুন”। এই তিনটি নিয়ম বারবার কাজে লাগে, তাই এদের প্রমাণ মুখস্থ নয়, বুঝে রাখুন:

একটি ছোট উদাহরণে axiom দিয়ে ধাপে ধাপে প্রমাণ: R(A, B, C, D, E, F), F = {A → B, A → C, CD → E, CD → F, B → E}. প্রমাণ করুন AD → E.

1. A → C (দেওয়া)। D দিয়ে augment: AD → CD.
2. CD → E (দেওয়া)।
3. ১ আর ২-এ transitivity: AD → E. ∎

অন্য পথেও হয়: A → B, B → E থেকে transitivity-তে A → E, তারপর reflexivity-তে AD → A, আবার transitivity-তে AD → E. একটি FD-র একাধিক প্রমাণ থাকতে পারে; পরীক্ষায় যেকোনো সঠিক শিকলই চলে। কিন্তু প্রতিটি FD-র জন্য এমন শিকল খোঁজা ক্লান্তিকর, আর F⁺ নিজেও বিশাল — n টি attribute-এর relation-এ শুধু trivial FD-ই 3ⁿ টি (প্রতিটি attribute X-এ ও Y-তে, শুধু X-এ, বা কোনোটিতেই না — তিন বিকল্প; খালি সেটসহ গুনলে)। তাই বাস্তবে F⁺ কেউ লেখে না; লেখে ছোট একটি জিনিস — X⁺.

৪ · Attribute closure X⁺ — সব FD-প্রশ্নের চাবি

একটি attribute-সেট X-এর attribute closure X⁺ হলো F-এর অধীনে X যতগুলো attribute নির্ধারণ করে, তাদের সেট: X⁺ = { A : X → A ∈ F⁺ }. আর মূল উপপাদ্য:

(যুক্তি: Y ⊆ X⁺ হলে Y-এর প্রতিটি A-র জন্য X → A, union দিয়ে X → Y. উল্টো দিকে X → Y থাকলে decomposition দিয়ে প্রতিটি A ∈ Y-এর জন্য X → A, তাই A ∈ X⁺.) অর্থাৎ 3ⁿ আকারের F⁺ লাগবে না; শুধু X⁺ বের করলেই X → Y সত্য কি না বলা যায়। অ্যালগরিদমটি সহজ, অনেকটা গুজব ছড়ানোর মতো: যাদের জানা আছে তাদের দল দিয়ে শুরু করুন; কোনো FD-র পুরো বাম দিক দলে থাকলে ডান দিককেও দলে নিন; যতক্ষণ দল বাড়ে, চালিয়ে যান।

closure(X, F):
    result := X
    repeat
        changed := false
        for each FD (L -> R) in F:
            if L ⊆ result and R ⊄ result:
                result := result ∪ R
                changed := true
    until changed = false
    return result

এবার ক্লাসিক উদাহরণে চালাই: R(A, B, C, D, E, F), F = {A → B, A → C, CD → E, CD → F, B → E}. বের করি (AD)⁺.

অ্যালগরিদম কেন সঠিক — প্রমাণ (আর Armstrong-এর completeness)

ধরুন অ্যালগরিদম শেষে ফল S. দাবি: A ∈ S ঠিক তখনই, যখন X → A ∈ F⁺.

• S-এর প্রতিটি attribute সত্যিই নির্ধারিত (sound): শুরুতে X → X (reflexivity). ধরুন কোনো মুহূর্তে X → result. একটি FD L → R প্রয়োগ হয় যখন L ⊆ result: decomposition দিয়ে X → L, transitivity দিয়ে X → R, union দিয়ে X → result ∪ R. Induction-এ শেষ পর্যন্ত X → S.
• S-এর বাইরের কিছু নির্ধারিত নয়: দুই সারির একটি instance বানান — t₁-এর সব ঘরে 0; t₂-এর S-এর ঘরে 0, বাকি ঘরে 1. F-এর যেকোনো L → R নিন। L ⊄ S হলে দুটি সারি L-এ মেলে না, FD খাটে। L ⊆ S হলে অ্যালগরিদম থামার সময় R ⊆ S (নইলে আরেকবার বাড়ত), তাই সারি দুটি R-এও মেলে, FD খাটে। অর্থাৎ instance-টি F-এর সব FD মেনে চলে। কিন্তু A ∉ S হলে সারি দুটি X-এ মেলে (X ⊆ S) আর A-তে মেলে না — এই instance-এ X → A ভাঙে। তাই X → A, F থেকে বের হয় না। ∎

প্রথম অংশে শুধু Armstrong-এর নিয়ম ব্যবহার হয়েছে। তাই যে FD সত্যিই বের হয়, তা axiom দিয়েই পাওয়া যায় — এটিই completeness-এর প্রমাণ।

খরচ: ধরুন |R| = n আর F-এ m টি FD. শেষ pass বাদে প্রতিটি pass অন্তত একটি attribute যোগ করে, তাই pass সর্বোচ্চ n − |X| + 1 টি। প্রতি pass-এ m টি FD, প্রতিটির “L ⊆ result?” যাচাই bitset বা boolean array-তে O(n). মোট O(n² · m) — ছোট schema-য় এক নিমেষের কাজ। (আরও দ্রুত, ইনপুটের দৈর্ঘ্যে linear একটি সংস্করণ আছে — “আরও গভীরে” বাক্সে।)

নিজে চালিয়ে দেখুন — closure আর key ক্যালকুলেটর

নিচের ছোট JavaScript প্রোগ্রাম ঠিক উপরের অ্যালগরিদম চালায় আর প্রতিটি যোগ ছাপে। শেষে সব উপসেট ছোট থেকে বড় ক্রমে দেখে সব candidate key বের করে। attrs আর fds বদলে নিজের পরীক্ষার প্রশ্ন মিলিয়ে নিন (প্রতিটি attribute একটি বড় হাতের অক্ষর)।

// FD = "LHS->RHS", each attribute is one capital letter
const attrs = "ABCDEF";
const fds = ["A->B", "A->C", "CD->E", "CD->F", "B->E"];
function closure(x, list, show) {
  const res = new Set(x);
  let changed = true, pass = 0;
  while (changed) {
    changed = false; pass++;
    for (const fd of list) {
      const [lhs, rhs] = fd.split("->");
      if ([...lhs].every(a => res.has(a)) && [...rhs].some(a => !res.has(a))) {
        for (const a of rhs) res.add(a);
        changed = true;
        if (show) console.log(`  pass ${pass}: ${fd} => {${[...res].sort().join(",")}}`);
      }
    }
  }
  return [...res].sort().join("");
}
for (const x of ["AD", "A", "CD"]) console.log(`(${x})+ = {${closure(x, fds, true)}}`);
const subsets = [];
for (let m = 1; m < 1 << attrs.length; m++)
  subsets.push([...attrs].filter((_, i) => m >> i & 1).join(""));
subsets.sort((p, q) => p.length - q.length);
const keys = [];
for (const s of subsets)
  if (closure(s, fds, false).length === attrs.length && !keys.some(k => [...k].every(a => s.includes(a))))
    keys.push(s);
console.log("candidate keys:", keys.join(", "));

৫ · X⁺ দিয়ে superkey আর candidate key খোঁজা

X⁺ = R হলে X একটি superkey; আর X-এর কোনো প্রকৃত উপসেটের closure R না হলে X একটি candidate key. কিন্তু সব উপসেট পরীক্ষা করা ধীর। পরীক্ষার খাতায় আর বাস্তবে একটি পদ্ধতিগত কৌশল কাজ করে — প্রতিটি attribute কোথায় আসে, তা দেখে শ্রেণিভাগ:

দ্বিতীয় সারির যুক্তি: ধরুন E শুধু ডান দিকে আসে, আর K একটি superkey যাতে E আছে। K-এর closure হিসাবের সময় E কখনো কোনো FD-র বাম দিকে লাগে না, তাই (K − E)⁺-এও E ছাড়া বাকি সব আসে; তারপর যে FD-র ডান দিকে E, তার বাম দিকও (যাতে E নেই) এসে গেছে, তাই E-ও আসে। অর্থাৎ K − E-ও superkey, K minimal নয়। কৌশলটি তাই: আবশ্যিক অংশ (core) দিয়ে শুরু করুন, তার closure দেখুন, না হলে “দুই দিকের” attribute একটি একটি করে যোগ করুন, ছোট থেকে বড়।

Prime আর non-prime attribute

শেষ ধাপের দুটি শব্দ পরের পর্বে বারবার লাগবে। Prime attribute হলো এমন attribute, যা অন্তত একটি candidate key-র সদস্য। Non-prime attribute কোনো candidate key-তেই নেই। 2NF আর 3NF-এর সংজ্ঞা (পর্ব ৩৬) ঠিক এই ভাগের ওপর লেখা — যেমন 2NF বলে “কোনো non-prime attribute কোনো candidate key-র অংশের ওপর নির্ভর করবে না”। তাই সব candidate key খুঁজে না পেলে কোনটি prime, বলা যায় না, আর normal form-ও ঠিক করা যায় না। এখানেই একটি সাধারণ ভুল: শুধু একটি key (যেমন primary key) দেখে বাকি সবাইকে non-prime ধরা। উপরের উদাহরণে কেউ শুধু AB দেখলে C আর D-কে non-prime ভাবতেন — অথচ দুটিই prime.

৬ · FD সেটের সমতা আর canonical cover

দুটি FD-সেট F আর G সমতুল্য (equivalent), যদি F⁺ = G⁺ — অর্থাৎ দুটি থেকে ঠিক একই FD-গুলো বের হয়। যাচাই করতে F⁺ লাগে না: G-এর প্রতিটি FD X → Y-এর জন্য F-এর অধীনে X⁺ বের করে দেখুন Y ⊆ X⁺ কি না (তাহলে “F, G-কে cover করে”), আর উল্টো দিকেও একই কাজ। দুই দিকেই মিললে সমতুল্য।

উদাহরণ: F = {A → B, B → C, A → C}, G = {A → B, B → C}. G-এর দুটি FD তো F-এই আছে। F-এর A → C: G-এর অধীনে A⁺ = {A, B, C}, তাতে C আছে। তাই F ≡ G. কিন্তু G′ = {A → B, A → C} নিলে F-এর B → C: G′-এর অধীনে B⁺ = {B} — C নেই। তাই F আর G′ সমতুল্য নয়।

F ≡ G দেখায়, A → C আসলে বাড়তি: বাকি দুটি থেকেই বের হয়। প্রতিটি FD মানে ডেটাবেসকে প্রতিটি INSERT/UPDATE-এ একটি যাচাই করতে হবে, আর normalization অ্যালগরিদমে একটি করে টেবিল আসতে পারে। তাই আমরা চাই সবচেয়ে ছোট সমতুল্য সেট — canonical cover (Elmasri–Navathe-এর বইয়ে “minimal cover”). একটি সেট minimal, যদি:

1. প্রতিটি FD-র ডান দিকে একটিই attribute;
2. কোনো FD-র বাম দিকে কোনো extraneous (বাড়তি) attribute নেই — অর্থাৎ বাম দিক থেকে একটি attribute ফেললে সেট আর সমতুল্য থাকে না;
3. কোনো redundant FD নেই — অর্থাৎ যেকোনো FD বাদ দিলে সেট আর সমতুল্য থাকে না।

দুটি যাচাই কীভাবে করবেন: বাম দিকের বাড়তি attribute: XA → B-তে A বাড়তি, যদি F-এর অধীনে B ∈ X⁺ (A ছাড়াই X দিয়ে B আসে)। Redundant FD: X → B বাদ দিয়ে বাকি সেটের অধীনে X⁺ বের করুন; তাতে B থাকলে FD-টি redundant. Silberschatz-এর বইয়ের canonical cover শেষে একই বাম দিকের FD-গুলো union দিয়ে জুড়ে দেয় (A → B, A → C-কে A → BC); ধারণা একই।

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

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই অধ্যায় থেকে সাধারণত চার ধরনের প্রশ্ন আসে: closure বের করা, একটি FD বের হয় কি না যাচাই, সব candidate key, আর canonical cover. প্রতিটির একটি করে সম্পূর্ণ সমাধান:

সমস্যা ১ — সব candidate key

R(A, B, C, D, E), F = {A → BC, CD → E, B → D, E → A}. সব candidate key আর prime attribute বের করুন।

সমস্যা ২ — একটি FD বের হয় কি না

একই F-এ (ক) BC → A আর (খ) B → E কি F⁺-এ আছে?

সমস্যা ৩ — দুটি সেট সমতুল্য কি না

F = {A → C, AC → D, E → AD, E → H} আর G = {A → CD, E → AH}. F ≡ G?

সমস্যা ৪ — canonical cover, পুরো হিসাবসহ

R(A, B, C, D, E), F = {AB → CD, A → E, E → C}. Canonical cover বের করুন।

৮ · ইতিহাস আর পরের ধাপ — Codd, Armstrong আর multivalued dependency

৯ · AI-এর যুগে functional dependency

AI-কে “এই টেবিলের FD আর key বের করো” বললে সুন্দর গোছানো উত্তর আসে। কিন্তু এই বিষয়ে AI-এর ভুলগুলো খুব নির্দিষ্ট ধরনের, আর হাতে X⁺ বের করলেই ধরা পড়ে:

AI-এর FD-হিসাব হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি closure-ধাপে FD-র পুরো বাম দিক আগে থেকেই সেটে ছিল
• প্রতিটি candidate key-র প্রকৃত উপসেটগুলোর closure R নয় — minimal নিজে মিলিয়েছি
• শুধু-বামের attribute সব key-তে আছে, শুধু-ডানের attribute কোনো key-তে নেই
• Canonical cover-এর প্রতিটি FD বাদ দিয়ে দেখেছি — বাকিরা সেটি দেয় না
• মূল F-এর প্রতিটি FD canonical cover থেকে বের হয় (সমতা দুই দিকেই)
• আসল ডেটায় GROUP BY X দিয়ে লঙ্ঘন খুঁজেছি, আর NULL-এর জন্য DISTINCT-পদ্ধতি ব্যবহার করেছি