Functional Dependencies

An FD X → Y is trivial if Y ⊆ X — if Y is a subset of X. In other words, the right-hand side is already contained within the left-hand side.

These FDs are always true for every relation, by definition of functional dependency — if two tuples agree on all attributes in X, they trivially agree on any subset of X. They add zero information about the data model.

An FD X → Y is non-trivial if Y ⊄ X — if at least one attribute in Y is NOT in X. Non-trivial FDs carry real information about the domain — they tell us something meaningful about how the data is related.

An FD is completely non-trivial if X ∩ Y = ∅ — the left and right sides share no attributes at all.

If X determines Y separately and Z separately, then X determines their union YZ together. You can always combine separately determined attributes onto one right-hand side.

Proof using axioms: Given X → Y and X → Z. By Augmentation of X → Y with Z: XZ → YZ. By Augmentation of X → Z with X: X → XZ. By Transitivity of X → XZ and XZ → YZ: X → YZ. □

// Application:
// employee_id → dept_id   (given)
// employee_id → salary    (given)
// By Union: employee_id → {dept_id, salary}

// This is useful when computing closures:
// Instead of tracking dept_id and salary as separate derived FDs,
// Union lets us combine them immediately.

The reverse of Union. If X determines a combined set YZ, you can split the right-hand side into its individual components. X determines each part separately.

Proof: Given X → YZ. By Reflexivity: YZ → Y (since Y ⊆ YZ). By Transitivity of X → YZ and YZ → Y: X → Y. Similarly, YZ → Z by Reflexivity, giving X → Z by Transitivity. □

// Application:
// dept_id → {dept_name, dept_location, dept_budget}   (given)
// By Decomposition:
// dept_id → dept_name      (individual FD)
// dept_id → dept_location  (individual FD)
// dept_id → dept_budget    (individual FD)

// This is useful when testing whether a specific attribute is determined:
// "Is dept_location determined by dept_id?" 
// Given dept_id → {dept_name, dept_location, dept_budget},
// Decomposition immediately gives us dept_id → dept_location.

A generalisation of Transitivity. If X determines Y, and the combination of W and Y determines Z, then the combination of W and X determines Z (because WX can produce Y from X, then WY → Z gives us Z).

Proof: Given X → Y and WY → Z. By Augmentation of X → Y with W: WX → WY. By Transitivity of WX → WY and WY → Z: WX → Z. □

// Application:
// student_id → advisor_id        (given: each student has one advisor)
// {advisor_id, course_id} → grade  (given: advisor grades students in courses)
// By Pseudotransitivity:
// {student_id, course_id} → grade  (replace advisor_id with student_id on LHS)

// This is the most practically useful derived rule for situations
// where you need to "substitute" one determining attribute for another.

// COMPUTE {AB}⁺ under F = {AB→C, C→D, D→E, E→B}

// Step 1 — Initialise:
closure = {A, B}

// Step 2 — Iteration 1: Scan all FDs
// FD: AB → C  ← Is {A,B} ⊆ closure = {A,B}? YES
//   Add C: closure = {A, B, C}
// FD: C → D   ← Is {C} ⊆ closure = {A,B,C}? YES
//   Add D: closure = {A, B, C, D}
// FD: D → E   ← Is {D} ⊆ closure = {A,B,C,D}? YES
//   Add E: closure = {A, B, C, D, E}
// FD: E → B   ← Is {E} ⊆ closure = {A,B,C,D,E}? YES
//   Add B (already in closure — no change)

// End of Iteration 1: closure = {A, B, C, D, E}
// Did anything change? YES — added C, D, E.

// Step 2 — Iteration 2: Scan all FDs again
// FD: AB → C  ← C already in closure
// FD: C → D   ← D already in closure
// FD: D → E   ← E already in closure
// FD: E → B   ← B already in closure
// No new attributes added in this iteration → TERMINATE

// RESULT: {AB}⁺ = {A, B, C, D, E} = all attributes of R

// CONCLUSION:
// {AB}⁺ = all attributes → AB is a SUPERKEY
// Can we remove A? {B}⁺: start {B}, E→B not helpful, no FD has {B} alone as LHS
//   {B}⁺ = {B} ≠ all → cannot remove A
// Can we remove B? {A}⁺: start {A}, no FD has just {A} on LHS
//   {A}⁺ = {A} ≠ all → cannot remove B
// AB is MINIMAL → AB is a CANDIDATE KEY ✓

// STRATEGY: First identify which attributes CAN be in a candidate key.
// An attribute that appears ONLY on the right-hand side of FDs (never on LHS)
// CANNOT be a candidate key alone (nothing derives it independently).
// An attribute that appears ONLY on the left-hand side (never on RHS)
// MUST be in every candidate key (no FD produces it, so it cannot be derived).

// Classify attributes:
// A: appears on LHS (A→B, A→C) — can derive things
//    appears on RHS (B→A) — can be derived
// B: appears on LHS (B→A, B→C) — can derive things
//    appears on RHS (A→B) — can be derived
// C: appears on LHS (C→D) — can derive things
//    appears on RHS (B→C, A→C) — can be derived
// D: appears ONLY on RHS (C→D) — NEVER on LHS
//    D is only derivable, never a determiner
//    D CANNOT be in any candidate key (removing it still gives a superkey)
//    D MUST be derived — no candidate key contains D alone OR is reducible by removing D

// Since D never appears on LHS, D cannot help derive anything.
// Every candidate key must be able to derive D → must derive C (C→D) → must derive A or B.

// TEST {A}:
// A⁺: start {A}
//   A → B: add B → {A,B}
//   A → C: add C → {A,B,C}
//   B → A: A already there
//   B → C: C already there
//   C → D: add D → {A,B,C,D}
// A⁺ = {A,B,C,D} = all attributes → A is a superkey
// Can we reduce? A alone → A⁺ = all → already single attribute
// A is a CANDIDATE KEY ✓

// TEST {B}:
// B⁺: start {B}
//   B → A: add A → {A,B}
//   B → C: add C → {A,B,C}
//   A → B: B already there
//   A → C: C already there
//   C → D: add D → {A,B,C,D}
// B⁺ = {A,B,C,D} = all attributes → B is a superkey
// B alone → already single attribute
// B is a CANDIDATE KEY ✓

// TEST {C}:
// C⁺: start {C}
//   C → D: add D → {C,D}
// C⁺ = {C,D} ≠ all attributes → C is NOT a candidate key
// (Cannot derive A or B from C alone)

// TEST {D}:
// D⁺: start {D}
// No FD has D on LHS → D⁺ = {D} ≠ all → NOT a candidate key

// TEST {A,B}: A⁺ = all → AB is a superkey. But A alone is a superkey → {A,B} is NOT minimal
// TEST {A,C}: A⁺ = all → AC superkey. A alone is superkey → NOT minimal
// TEST {B,C}: B⁺ = all → BC superkey. B alone is superkey → NOT minimal
// (Any multi-attribute set containing A or B is a non-minimal superkey)

// FINAL ANSWER: Candidate keys = {A} and {B}
// Both A and B independently determine all attributes of R.
// A↔B (they determine each other) — they are equivalent identifiers.

// STEP 1: Classify attributes
// Appears ONLY on LHS (never on RHS): must be in every candidate key
//   F appears on LHS (CF→B) but NEVER on RHS → F must be in EVERY candidate key
//   A appears on LHS (AB→C), also on RHS (BC→AD) → not required in every key
//   B appears on LHS (AB→C, BC→AD), also on RHS (CF→B) → not required in every key
//   C appears on LHS (BC→AD, CF→B), also on RHS (AB→C) → not required in every key
//   D appears on LHS (D→E), also on RHS (BC→AD) → not required in every key
//   E appears ONLY on RHS (D→E) → CANNOT be in any candidate key (cannot derive others)

// CONCLUSION from classification:
//   F must be in EVERY candidate key (never derived)
//   E cannot be in any candidate key (never derives anything)
//   So every candidate key contains F and does NOT contain E alone

// STEP 2: Test {A, F}
// Closure of {A,F}:
//   Start: {A, F}
//   FD AB→C: need {A,B} — B not in closure yet. Skip.
//   FD BC→AD: need {B,C} — not in closure. Skip.
//   FD D→E: need {D} — not in closure. Skip.
//   FD CF→B: need {C,F} — C not in closure. Skip.
//   No additions in iteration 1.
//   {A,F}⁺ = {A,F} ≠ all → NOT a candidate key

// STEP 3: Test {A, B, F}
// Closure of {A,B,F}:
//   Start: {A, B, F}
//   FD AB→C: {A,B} ⊆ {A,B,F} → add C → {A,B,C,F}
//   FD BC→AD: {B,C} ⊆ {A,B,C,F} → add A,D → {A,B,C,D,F}
//   FD D→E: {D} ⊆ {A,B,C,D,F} → add E → {A,B,C,D,E,F}
//   FD CF→B: {C,F} ⊆ {A,B,C,D,E,F} → add B (already there)
//   End iteration 1: {A,B,C,D,E,F} = all attributes ✓
// {ABF}⁺ = all → ABF is a superkey
// Is it minimal? Can we remove any attribute?
//   Remove A? {BF}⁺: start {B,F}, CF→B needs C, AB→C needs A... 
//     {B,F}: no FD fires → {BF}⁺ = {B,F} ≠ all → Cannot remove A ✓
//   Remove B? {AF}⁺ = {A,F} ≠ all (computed above) → Cannot remove B ✓
//   Remove F? {AB}⁺: AB→C → {A,B,C}, BC→AD → {A,B,C,D}, D→E → {A,B,C,D,E}
//     {AB}⁺ = {A,B,C,D,E} — missing F! ≠ all → Cannot remove F ✓
// ABF is MINIMAL → ABF is a CANDIDATE KEY ✓

// STEP 4: Test {B, C, F}
// Closure of {B,C,F}:
//   Start: {B,C,F}
//   FD AB→C: needs A — not present. Skip.
//   FD BC→AD: {B,C} ⊆ {B,C,F} → add A,D → {A,B,C,D,F}
//   FD D→E: {D} ⊆ {A,B,C,D,F} → add E → {A,B,C,D,E,F}
//   FD CF→B: already have B
// {BCF}⁺ = {A,B,C,D,E,F} = all ✓
// Is it minimal?
//   Remove B? {CF}⁺: CF→B → add B → {B,C,F}, BC→AD → add A,D → {A,B,C,D,F}, D→E → {A,B,C,D,E,F}
//     {CF}⁺ = all → B is redundant in BCF! NOT minimal
// So BCF is NOT a candidate key (CF alone is a superkey)

// STEP 5: Test {C, F}
// {CF}⁺ (computed above) = {A,B,C,D,E,F} = all ✓
// Is it minimal?
//   Remove C? {F}⁺: no FD has just F on LHS → {F}⁺ = {F} ≠ all → cannot remove C ✓
//   Remove F? {C}⁺: C→? no FD has just C on LHS → {C}⁺ = {C} ≠ all → cannot remove F ✓
// CF is MINIMAL → CF is a CANDIDATE KEY ✓

// FINAL ANSWER: Candidate keys = {A,B,F} and {C,F}
// (Check any other combinations systematically to confirm no others)
// Verify: A appears in ABF, F appears in both — consistent with our classification

Does X → Y hold in F⁺? Compute X⁺. If Y ⊆ X⁺ → yes. Else → no.

Compute X⁺. If X⁺ = all attributes of R → X is a superkey.

Test all subsets systematically (start with single attributes, then pairs, etc.). A subset is a candidate key if it is a superkey AND no proper subset is also a superkey.

Decompose R into R1(X,Y) and R2(X,Z). Check if X → Y or X → Z holds (i.e., if Y ⊆ X⁺ or Z ⊆ X⁺). If either holds → lossless decomposition.

An FD X → Y is redundant in F if Y ⊆ X⁺ computed from F − {X→Y}. If removing it from F does not change any closure, it is redundant.

In FD XA → Y, is A extraneous? Compute X⁺ from F. If Y ⊆ X⁺ → A is extraneous in XA → Y (X alone already determines Y).

For every FD X → A in F_c, no attribute in X is extraneous — removing any attribute from X changes the closure. Every LHS attribute genuinely contributes to the dependency.

Each FD in F_c has exactly ONE attribute on its right-hand side. X → AB is not canonical — it must be split into X → A and X → B using Decomposition.

No FD in F_c can be derived from the remaining FDs in F_c. Removing any FD changes the closure of some attribute set — every FD genuinely contributes.

-- The original schema (intuition-designed, never FD-analysed):
CREATE TABLE order_details (
    order_id          INT           NOT NULL,
    product_id        INT           NOT NULL,
    product_name      VARCHAR(200),   -- stored here for "convenience"
    product_category  VARCHAR(100),   -- stored here for "convenience"
    current_price     DECIMAL(10,2),  -- PROBLEM: whose current? when?
    ordered_qty       INT             NOT NULL,
    unit_price        DECIMAL(10,2),  -- price at time of order
    customer_id       INT             NOT NULL,
    customer_name     VARCHAR(100),   -- stored here for "convenience"
    customer_city     VARCHAR(100),   -- stored here for "convenience"
    order_date        DATE            NOT NULL,
    
    PRIMARY KEY (order_id, product_id)
);

// Identify all FDs that should hold on order_details:
// PK = (order_id, product_id)

// product_id → product_name, product_category, current_price
//   (product attributes depend only on product_id — PARTIAL DEPENDENCY on PK)
//   → 2NF VIOLATION → update anomaly root cause!

// customer_id → customer_name, customer_city
//   (customer attributes depend only on customer_id)
//   But customer_id itself depends on order_id → TRANSITIVE DEPENDENCY
//   → 3NF VIOLATION

// order_id → customer_id, order_date
//   (order attributes depend on order_id — PARTIAL DEPENDENCY on PK)
//   → 2NF VIOLATION

// (order_id, product_id) → ordered_qty, unit_price
//   These correctly depend on the full PK

// THE INCIDENT ROOT CAUSE:
// current_price is product_id → current_price (partial dependency).
// When a product's price changes, engineers run:
// UPDATE products SET price = 300 WHERE product_id = 101;
// They update the products table (not order_details).
// But order_details ALSO stores current_price (copied at order insertion).
// The two values diverge → two different prices in two different queries
// depending on which table they source from.

-- After FD analysis: extract each dependency set to its own table

CREATE TABLE products (
    product_id    SERIAL         PRIMARY KEY,
    product_name  VARCHAR(200)   NOT NULL,
    category      VARCHAR(100),
    current_price DECIMAL(10,2)  NOT NULL  -- single source of truth for CURRENT price
);

CREATE TABLE customers (
    customer_id    SERIAL        PRIMARY KEY,
    customer_name  VARCHAR(100)  NOT NULL,
    customer_city  VARCHAR(100)
);

CREATE TABLE orders (
    order_id     SERIAL   PRIMARY KEY,
    customer_id  INT      NOT NULL,
    order_date   DATE     NOT NULL DEFAULT CURRENT_DATE,
    FOREIGN KEY (customer_id) REFERENCES customers(customer_id)
);

CREATE TABLE order_items (
    order_id    INT           NOT NULL,
    product_id  INT           NOT NULL,
    ordered_qty INT           NOT NULL CHECK (ordered_qty > 0),
    unit_price  DECIMAL(10,2) NOT NULL,  -- SNAPSHOT: price at time of order (historical)
    -- unit_price is INTENTIONAL denormalisation for historical accuracy
    -- It is NOT synced with products.current_price — that is correct by design
    
    PRIMARY KEY (order_id, product_id),
    FOREIGN KEY (order_id)   REFERENCES orders(order_id)   ON DELETE CASCADE,
    FOREIGN KEY (product_id) REFERENCES products(product_id) ON DELETE RESTRICT
);

-- NOW: "current price" always comes from products.current_price (single source)
-- "historical price" always comes from order_items.unit_price (snapshot)
-- These are genuinely different data — one current fact, one historical fact
-- They SHOULD be different values when prices change — by design

-- QUERIES:
-- Product catalogue price (always current):
SELECT product_name, current_price FROM products WHERE product_id = 101;

-- Order history price (always historical snapshot):
SELECT oi.unit_price, o.order_date
FROM order_items oi JOIN orders o ON oi.order_id = o.order_id
WHERE oi.product_id = 101;

-- No more inconsistency — two different CORRECT answers for two different questions.