DSA, Database System & Operating System — Data Models, Normalization, and SQL, NEC licence examination syllabus (Nepal Engineering Council).
Functional Dependencies
X → Y means "X determines Y" — the formal tool that turns normalization from guesswork into computation.
🌍 Where this lives: functional dependencies are what a query optimiser reasons about when it decides it can skip a sort or eliminate a join. If the planner knows roll → name, then GROUP BY roll, name costs the same as GROUP BY roll — PostgreSQL implements exactly this optimisation for columns functionally dependent on a grouped primary key, which is why GROUP BY id lets you select any column of that table without listing it. FDs are also what data-profiling tools infer automatically to reverse-engineer a schema nobody documented. Search "functional dependency discovery algorithms"; finding all FDs in a table is a genuinely hard computational problem.
Definition
In a relation R, a functional dependency
X → Y ("X functionally determines Y",
"Y is functionally dependent on X")
holds if and only if:
for ANY two tuples t1 and t2 in ANY legal instance of R,
t1[X] = t2[X] implies t1[Y] = t2[Y]
In words: if two rows agree on X, they MUST agree on Y.
Equivalently: each X value maps to exactly ONE Y value.
X is the DETERMINANT. Y is the DEPENDENT.
CRITICAL POINT: an FD is a statement about the SCHEMA — it
must hold for every possible legal instance, not just the
rows you happen to see. You cannot prove an FD from data;
you can only DISPROVE it by finding a counterexample.
roll name marks
────────────────────────────
101 Ram 87
102 Sita 91
103 Ram 76
From this data: roll → name is NOT contradicted ✔
name → roll IS contradicted:
'Ram' appears with roll 101 and 103
→ name → roll is FALSE
name → marks IS contradicted:
'Ram' has 87 and 76
So data can only ever REFUTE an FD. Asserting one requires
knowing the business rule.
TRIVIAL vs NON-TRIVIAL
trivial X → Y where Y ⊆ X (roll → roll)
always true, carries no information
non-trivial X → Y where Y ⊄ X
completely X → Y where X ∩ Y = ∅
non-trivial
FULL vs PARTIAL dependency (needed for 2NF)
full X → Y and NO proper subset of X determines Y
partial some proper subset of X already determines Y
(roll, course) → grade FULL — need both
(roll, course) → student_name PARTIAL — roll alone
suffices
Armstrong's axioms
Three inference rules that are SOUND (never derive a false
FD) and COMPLETE (can derive every FD that logically
follows).
A1 REFLEXIVITY if Y ⊆ X then X → Y
(trivially, X determines its own parts)
A2 AUGMENTATION if X → Y then XZ → YZ
(adding the same attributes to both
sides preserves the dependency)
A3 TRANSITIVITY if X → Y and Y → Z then X → Z
DERIVED RULES — provable from A1–A3, and far more useful in
practice:
UNION if X → Y and X → Z then X → YZ
DECOMPOSITION if X → YZ then X → Y and X → Z
PSEUDOTRANSITIVITY
if X → Y and WY → Z then WX → Z
COMPOSITION if X → Y and Z → W then XZ → YW
PROVING UNION from the axioms — a standard exam question:
1. X → Y given
2. X → Z given
3. X → XY from 1 by augmentation
(add X to both sides)
4. XY → YZ from 2 by augmentation
(add Y to both sides)
5. X → YZ from 3 and 4 by
transitivity ∎
PROVING DECOMPOSITION:
1. X → YZ given
2. YZ → Y reflexivity (Y ⊆ YZ)
3. X → Y transitivity of 1, 2
4. YZ → Z reflexivity
5. X → Z transitivity of 1, 4 ∎
WHAT IS **NOT** VALID — the two classic traps:
✗ if X → Y then Y → X (FDs are DIRECTIONAL)
✗ if XY → Z then X → Z or Y → Z (you may NOT decompose
the LEFT side)
Counterexample for the second:
(roll, course) → grade is true
roll → grade is FALSE — a student has many
grades, one per course
That left-side rule is where most exam mistakes happen.
Decomposition applies to the RIGHT side only.
Attribute closure — the central algorithm
The CLOSURE of an attribute set X under a set of FDs F,
written X⁺, is every attribute determined by X.
ALGORITHM (iterative, guaranteed to terminate):
X⁺ := X
repeat
for each FD A → B in F:
if A ⊆ X⁺ then X⁺ := X⁺ ∪ B
until X⁺ stops changing
return X⁺
WHY IT MATTERS — closure answers all three key questions:
1. Does X → Y hold? → yes iff Y ⊆ X⁺
2. Is X a superkey? → yes iff X⁺ = all attributes
3. Is X a candidate key? → yes iff X⁺ = all attributes
AND no proper subset of X
has that property
WORKED EXAMPLE — R(A, B, C, D, E, F) with
F = { A → BC, CD → E, B → D, E → A }
Compute {A}⁺ :
start {A}
A → BC {A,B,C}
B → D {A,B,C,D}
CD → E (CD ⊆ {A,B,C,D} ✔)
{A,B,C,D,E}
E → A already have A
no change {A,B,C,D,E}
→ {A}⁺ = ABCDE. F is MISSING, so A is not a superkey.
Compute {AF}⁺ :
start {A,F}
A → BC {A,B,C,F}
B → D {A,B,C,D,F}
CD → E {A,B,C,D,E,F}
→ {AF}⁺ = ABCDEF = all attributes. AF IS a superkey.
Minimal? {A}⁺ = ABCDE ≠ all; {F}⁺ = F ≠ all.
Neither subset works → AF is a CANDIDATE KEY. ✔
Compute {E}⁺ :
E → A {A,E}
A → BC {A,B,C,E}
B → D {A,B,C,D,E}
→ {E}⁺ = ABCDE, so {EF}⁺ = ABCDEF → EF is a CANDIDATE KEY.
BUT DO NOT STOP THERE. Two more exist, and missing them is
the commonest error in this question type:
Compute {BC}⁺ :
start {B,C}
B → D {B,C,D}
CD → E {B,C,D,E}
E → A {A,B,C,D,E}
→ {BC}⁺ = ABCDE, so {BCF}⁺ = ABCDEF
Minimal? {BF}⁺ = BDF ✗, {CF}⁺ = CF ✗
→ BCF is a CANDIDATE KEY.
Compute {CD}⁺ :
CD → E {C,D,E}
E → A {A,C,D,E}
A → BC {A,B,C,D,E}
→ {CD}⁺ = ABCDE, so {CDF}⁺ = ABCDEF
Minimal? {CF}⁺ = CF ✗, {DF}⁺ = DF ✗
→ CDF is a CANDIDATE KEY.
ALL FOUR CANDIDATE KEYS: AF, EF, BCF, CDF
prime attributes : A, B, C, D, E, F (all of them)
non-prime attributes : none
THE LESSON: finding one or two candidate keys is not the
answer — you must find them ALL, because 2NF/3NF/BCNF are
defined in terms of EVERY candidate key. Here every attribute
turns out to be prime, which (as the next topic shows) means
this relation is automatically in 3NF.
BE SYSTEMATIC. F is mandatory (never on a right side), so
test F with each subset of {A,B,C,D,E} in increasing size,
skipping any superset of a key already found:
size 1: AF ✔ BF ✗ CF ✗ DF ✗ EF ✔
size 2: BCF ✔ BDF ✗ CDF ✔ ...
(skip anything containing A or E — already keys)
stop when no smaller candidates remain.
THE SHORTCUT worth memorising:
· an attribute appearing on NO right-hand side must be in
every candidate key
· an attribute appearing on NO left-hand side is in no
candidate key
Here F is on no right side → F is in every candidate key.
That immediately tells you where to start.
The "attribute on no right-hand side must be in every candidate key" rule turns a search over 2ⁿ subsets into a handful of closure computations. Start with the mandatory attributes, compute their closure, and add only what is still missing. For a six-attribute relation that is the difference between checking 63 subsets and checking three.
Worked example — finding all candidate keys
R(A, B, C, D, E) with F = { AB → C, C → D, D → B, A → E }
STEP 1 — classify every attribute:
on LEFT only : A (appears left, never right)
on BOTH : B, C, D
on RIGHT only : E
on NEITHER : none
→ A must be in EVERY candidate key (never determined)
→ E can be in NO candidate key (never determines anything)
STEP 2 — compute {A}⁺ :
{A} →(A→E) {A,E}
nothing else applies (AB → C needs B)
{A}⁺ = AE. Not a superkey — missing B, C, D.
STEP 3 — A alone is insufficient, so try A + one more:
{AB}⁺ : {A,B}
AB → C {A,B,C}
C → D {A,B,C,D}
A → E {A,B,C,D,E} = ALL ✔ superkey
minimal? {A}⁺=AE ✗, {B}⁺=B ✗ → CANDIDATE KEY
{AC}⁺ : {A,C}
C → D {A,C,D}
D → B {A,B,C,D}
A → E {A,B,C,D,E} = ALL ✔ superkey
minimal? {A}⁺=AE ✗, {C}⁺=CDB ✗ → CANDIDATE KEY
{AD}⁺ : {A,D}
D → B {A,B,D}
AB → C {A,B,C,D}
A → E {A,B,C,D,E} = ALL ✔ superkey
minimal? {A}⁺=AE ✗, {D}⁺=DB ✗ → CANDIDATE KEY
{AE}⁺ : {A,E} — nothing fires. Not a superkey.
STEP 4 — RESULT: three candidate keys
AB, AC, AD
PRIME attributes (in some candidate key): A, B, C, D
NON-PRIME attribute (in no candidate key) : E
That prime/non-prime split is exactly what 2NF and 3NF are
stated in terms of, which is why closure comes before
normalization.
closure_check.sql
-- FDs are schema-level claims, so SQL cannot declare them
-- directly — but you can TEST whether data violates one.
-- The test: does any determinant value map to more than one
-- dependent value?
CREATE TABLE enrolment_flat (
roll INTEGER,
course CHAR(8),
sname VARCHAR(60),
ctitle VARCHAR(60),
grade CHAR(2),
PRIMARY KEY (roll, course)
);
INSERT INTO enrolment_flat VALUES
(101, 'ACtE0703', 'Ram Bahadur', 'Database Systems', 'B'),
(101, 'AExE0101', 'Ram Bahadur', 'Circuit Theory', 'A'),
(102, 'ACtE0703', 'Sita Devi', 'Database Systems', 'A'),
(103, 'ACtE0703', 'Ram Bahadur', 'Database Systems', 'C');
-- note: roll 103 is ALSO named 'Ram Bahadur' — a different
-- person who happens to share a name.-- ===== TEST 1: does roll -> sname hold? =====
-- Look for a roll with more than one distinct sname.SELECT roll, COUNT(DISTINCT sname) AS distinct_names
FROM enrolment_flat
GROUP BY roll
HAVING COUNT(DISTINCT sname) > 1;-- (0 rows) -> NOT VIOLATED by this data, so roll -> sname
-- is consistent with what we have.-- ===== TEST 2: does sname -> roll hold? =====
SELECT sname, COUNT(DISTINCT roll) AS distinct_rolls
FROM enrolment_flat
GROUP BY sname
HAVING COUNT(DISTINCT roll) > 1;
-- sname | distinct_rolls
-- -------------+----------------
-- Ram Bahadur | 2
-- -> VIOLATED. sname -> roll is FALSE.-- ===== TEST 3: does course -> ctitle hold? =====
SELECT course, COUNT(DISTINCT ctitle) AS distinct_titles
FROM enrolment_flat
GROUP BY course
HAVING COUNT(DISTINCT ctitle) > 1;
-- (0 rows) -> consistent. course -> ctitle holds.-- ===== A REUSABLE GENERIC TEST =====
-- Any FD X -> Y is violated iff this returns rows:
-- SELECT X FROM t GROUP BY X HAVING COUNT(DISTINCT Y) > 1;
-- Data can only REFUTE an FD. Zero rows means "not
-- contradicted yet", never "proved".-- ===== enforcing an FD once you know it holds =====
-- roll -> sname means sname belongs in a student table, not
-- repeated here. That is the 2NF decomposition:
CREATE TABLE student (roll INTEGER PRIMARY KEY,
sname VARCHAR(60) NOT NULL);
CREATE TABLE course (code CHAR(8) PRIMARY KEY,
ctitle VARCHAR(60) NOT NULL);
CREATE TABLE enrolment (
roll INTEGER REFERENCES student(roll),
course CHAR(8) REFERENCES course(code),
grade CHAR(2),
PRIMARY KEY (roll, course)
);
-- Now roll -> sname is enforced STRUCTURALLY: sname is
-- stored once, so it CANNOT disagree with itself.
Closure of a set of FDs, and minimal cover
F⁺ — the closure of the FD SET F — is every FD derivable
from F. It is usually huge and never computed in full.
EQUIVALENCE: two FD sets F and G are equivalent if
F⁺ = G⁺. Test it by checking that every FD in G is derivable
from F (using closures) and vice versa.
MINIMAL COVER (canonical cover, Fc) — the smallest FD set
equivalent to F. Three conditions:
1. every right-hand side is a SINGLE attribute
2. no FD is redundant (removing it changes F⁺)
3. no determinant has a redundant attribute
ALGORITHM:
Step 1 split right sides: X → YZ becomes X → Y, X → Z
Step 2 remove redundant attributes from left sides:
for each FD A → b and each attribute a ∈ A,
if b ∈ (A − a)⁺ computed under F, drop a
Step 3 remove redundant FDs:
for each FD X → Y, if Y ⊆ X⁺ computed WITHOUT
that FD, delete it
WORKED EXAMPLE
F = { A → BC, B → C, AB → D, AC → D }
Step 1 — single right sides:
A → B, A → C, B → C, AB → D, AC → D
Step 2 — redundant LEFT attributes:
AB → D : is B redundant? {A}⁺ under F = ABCD ∋ D ✔
→ drop B, giving A → D
AC → D : now A → D exists, so AC → D is redundant in
step 3 anyway
Result: A → B, A → C, B → C, A → D, AC → D
Step 3 — redundant FDs:
A → C : remove it; {A}⁺ using {A→B, B→C, A→D}
= A,B,C,D ∋ C ✔ still derivable → DELETE
AC → D: remove it; {AC}⁺ using the rest ∋ D ✔ → DELETE
A → B : remove it; {A}⁺ = A,D — B not derivable → KEEP
B → C : remove it; {B}⁺ = B — C not derivable → KEEP
A → D : remove it; {A}⁺ = A,B,C — D not derivable → KEEP
MINIMAL COVER: Fc = { A → B, B → C, A → D }
Check: {A}⁺ under Fc = A,B,C,D — same as under F. ✔
Reduced from 4 FDs (with multi-attribute sides) to 3 simple
ones, with identical logical content.
WHY IT MATTERS: 3NF synthesis (the next topic) builds one
relation per FD in the minimal cover. A non-minimal cover
produces redundant tables, so this computation directly
determines the schema you get.
🌍 Go further: functional dependencies are the simplest of a family. Multivalued dependencies (X ↠ Y) capture independence between two multivalued facts about the same entity and give rise to 4NF; join dependencies give 5NF. There is also an inclusion dependency, which is exactly what a foreign key declares. And the modern twist: real-world data is dirty, so research now focuses on approximate and conditional functional dependencies — "zip → city holds for 99.7% of rows" — which is how data-cleaning tools spot errors. Search "conditional functional dependencies data cleaning".
💡 Exam angle: state the FD definition precisely — if two tuples agree on X they must agree on Y — and stress that an FD is a schema constraint that data can refute but never prove. Know Armstrong's axioms (reflexivity, augmentation, transitivity) and be able to derive union and decomposition from them. The two guaranteed computational questions are attribute closure (X⁺) to find candidate keys, and minimal cover. Remember the trap: you may decompose the right side of an FD but never the left.
Syllabus points
FD, closure of attributes
Armstrong's axioms
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Data Models, Normalization, and SQL