—

Database Design and Applications

Minimal Covers, 3NF Synthesis, and Relational Algebra

Published: 2026-08-06

Level: postgraduate

Audience: Postgraduate students in database systems

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Attribute closure (X+) — covered in Lecture 5 (The Closure of a Functional Dependency Set)
Minimal covers of functional dependency sets — covered in Lecture 5 (The Minimal Cover of a Functional Dependency Set)
The 3NF synthesis algorithm — covered in Lecture 5 (The 3NF Synthesis Algorithm)

6.1 The Course Promise: Storing, Retrieving, and Serving Data

6.1.1 Why This Course Exists

The course starts from a big promise: data is the new oil. In the last century, the countries that owned oil went from nobody to everybody — think of the Gulf region — and we are now in a transition where everyone recognizes that data plays that role. The reason is human: people whose basic needs are covered want personal experiences, more wants, more desires satisfied, and whoever can satisfy those wants and desires — a person, a company, a country — prospers. This course makes three specific promises about working with data in any organization: (a) you will be able to store the data well, (b) you will be able to retrieve the data well, and (c) you will be able to retrieve it in a concurrent fashion, with many users accessing it at once.

Consider any organization or application — social media, airline bookings, supply chains, online banking. Every one of them runs on data, and most only scratch the surface of what could be exploited from it; what can be exploited is exponential. The entire science of data science and AI rests on the foundations built by database system engineers. Unless data is stored well, and unless there is confidence that the stored data is correct, no prediction can be trusted — anomalies keep appearing.

The hostel room analogy. A simple picture makes the point: a hostel room. Books, bedsheets, shoes, keys, pens, pencils, notebooks, even a mobile phone — a handful of things — and still it is hard to find your database book, your notebook, your keys. If there is a system — a fixed place for books, a fixed place for bedsheets, a fixed place for clothes — then one person, or many people, can go and fetch things correctly. This is exactly what a database does at larger scale.

Mapping: the hostel room is the organization's data; the fixed places are the tables (relations) and the rules that say which value lives where; a person fetching an item is a query; many people fetching at once is concurrency. Where the analogy breaks: in a hostel the objects are physical, so two people cannot take the same book at the same time without notice. In a database, many users can read the same record at the same time, and the difficulty moves to keeping the writes consistent — which is why promise (c) is a separate promise rather than a footnote.

Building such a storage system is one task; maintaining it is another. Both take effort and energy, and you always trade cost against performance. That is what the fundamentals of this course teach.

6.1.2 Awareness, Education, and Skill

Three things must happen for the promise to be kept, and each has a different owner. Awareness means knowing that something can be done — "this is possible." Education means knowing how it is done — "this is the way." The teaching role carries the session up to the point of education, and then the student's role begins: practice, until the knowledge becomes skill. From that point the teaching role changes into an accountable partner — someone who checks whether the commitments you made ("I will apply this in my life and work") are actually kept. A person who completes this course well becomes an indispensable asset to any organization, whether working standalone or inside a team.

Practice matters even in the theoretical sense. Unless you know the theory portion, you cannot apply the knowledge, you cannot understand the realistic constraints of where it applies, and you cannot explain to yourself or to others why it works and what you are doing. Projects, labs, quizzes, and a written examination are the practice vehicles for this course.

Exam note: the three-stage ladder — awareness → education → skill — is the course's own framing of how learning works. The lecture's answer to "why does theory matter?" is: theory is what lets you apply knowledge, understand its limits, and explain it to others. The practice vehicles are projects, labs, quizzes, and a written examination.

6.1.3 The Hypothesis Behind the Course

The course is built on a hypothesis — and you, as the receiver of the claim, should always stay alert to whether the hypothesis still holds. Consider "water boils at 100 degrees Celsius." It sounds absolute, but it assumes a particular pressure. In the same spirit, "third normal form is more good than second normal form" is a hypothesis. The word "good" has its own significance and relevance, and it must be tested: practice it, apply it across scenarios, and you may come back and say, "my organization performs worse in third normal form than in second normal form — what do you mean by good, and why is it not applicable in my case?"

The honest answer is that the hypothesis holds under implicit assumptions: network communication is dependable, availability is almost guaranteed, there are no petabytes of data arriving every second, and there are not billions or trillions of users hitting the system — a very confined environment where many things are implicit. Real life moves toward data that arrives in all velocity, volume, and variety. Sometimes it is acceptable for data to be heuristically correct rather than exactly correct. Sometimes the network is not always there, so you must worry about replication. In those scenarios the tools, techniques, and tactics change. Today we discuss relational database systems; later we may discuss non-relational systems like MongoDB, Cassandra, and Neo4j. Even so, the fundamentals you learn here hold their elements inside that box, with different constraints and environments. When the situation changes, you adapt more easily because you already learned one language and the basics; a second tool is easier after the first.

The harmonium and the synthesizer. The professor's own analogy: today you learn the harmonium, tomorrow the synthesizer; today Indian classical, tomorrow Western music. The notes, the beats, the basics remain the same. Old knowledge does not lose its relevance when you change instruments — you practice, you become skillful, and you adapt.

Mapping: the harmonium is the relational model, the synthesizer is a non-relational system; the notes and beats are functional dependencies, keys, and normalization; changing instruments is moving to MongoDB, Cassandra, or Neo4j. Where the analogy breaks: music theory transfers almost unchanged between instruments, while database fundamentals transfer with real changes in the rules — NoSQL systems relax strict consistency guarantees and may accept heuristic correctness, so the "notes" are the same but some "beats" differ.

6.1.4 The End-to-End Picture: Where Databases Sit

Q: We would like an end-to-end integration with a working system — experience the full stack, and see how an application reaches the data. API design and UI design are not the purpose of this course, but can we have projects or assignments in that angle? Also, the lab sheet could be great: if we use Node.js or Python with some framework, install it, and connect to the MySQL that is already advised in the lab sheet, that is good enough for us to start.

A: The request is fair, and here is how a computer science education answers "how does a computer work, end to end?" Microprocessor programming starts from switches — from switches we form gates, from gates we form circuits, and from circuits we build adders, multipliers, and finally a microprocessor that replicates any equation in hardware through simple on-off switches. The compiler course takes a language, parses it using its grammar, forms trees, and translates it gradually to assembly, which those gates and circuits can act on. The operating system is a resource manager — it manages the processor, memory, and input-output devices, and decides who goes where. The algorithms course teaches how to process a thought and communicate it efficiently: given constraints, how to solve a problem in the best manner, identifying resources and making them useful. Computer networks explain how one system communicates with another, and database systems explain how to manage the data component — how to make it, how to build it, how to use it, not just for now but for a long time. Software engineering covers the lifecycle, and DevOps and API building complete the picture. The data component is fundamental to every application, and this course makes you skillful in exactly that part.

The commitments: practical scenarios will be shared — real applications, the code in Python, how it is deployed, how it works, and how the database is managed. Separate practice sessions can be recorded and shared, since the discussion here is limited in time. The lab sheets will use Python with a framework or Node.js, connected to the MySQL you already have in the lab sheet. Students coming from a non-computing background are looked after — for them "Python" may literally mean the real snake at first — and the instructor will be an accountable partner who can be reminded and held to these commitments.

The full-stack question places this course in the map of a computer science degree. The point that makes databases special in that map: every layer above — the application, the API, the UI — eventually needs to read or write data, and the quality of the data layer decides whether the layers above can be trusted. That is why the course cares about storage, retrieval, and concurrency as three separate promises: an application that writes well but reads slowly, or reads fast but loses writes under many simultaneous users, is not a finished application.

6.1.5 Quiz 1: Format and Rules

Exam note: Quiz 1 opens on the 19th and closes on the 28th. It runs on the e-learn platform (you may know it as Takshila). The quiz has 25 questions, all multiple choice, and you attempt the most correct answer. There is no negative marking. It carries 5% weightage. You may attempt in one sitting or in several sittings — no fixed time limit is set — but you can submit only once, and you should submit at least once before the deadline, otherwise you cannot be marked. The quiz is open book: you may refer to books and your notes while attempting it. Coverage is everything discussed so far — normalization. Relational algebra is not part of Quiz 1.

Q: This is our first quiz in this program. What is the format — is it constant across all subjects, or does it depend on the instructor?

A: The quiz is on the e-learn platform (you may call it Takshila). For this course: 25 multiple-choice questions, attempt the most correct answer, no negative marking, 5% weightage. You can take your time — one sitting of five minutes or ten sittings over five hours is up to you — but you can submit only once. Submit at least once before the deadline. Open book: books and notes are allowed while you attempt. Different courses have different quizzes, and their formats depend on the instructor, but this is what this one looks like.

The practical meaning of "coverage is normalization": the quiz questions expect you to find candidate keys and prime attributes, compute closures of attribute sets, and find minimal covers — exactly the machinery of Sections 6.2, 6.3, and 6.4. Relational algebra, which starts in Section 6.5, is not examinable in this quiz.

6.2 Closure, Redundancy, and Minimal Covers

6.2.1 The Closure of an Attribute Set

A functional dependency (FD) $X \to Y$ says: the values of the attribute set $X$ determine the values of the attribute set $Y$ . The closure of an attribute set $X$ , written $X^{+}$ , is the set of every attribute that is functionally determined by $X$ — everything you can reach from $X$ by following the FDs, directly or through chains. You compute it by starting with $X$ and repeatedly adding whatever the FDs let you reach.

Formal definition. For a relation $R$ with attribute set $U$ and a set of functional dependencies $F$ , the closure of $X \subseteq U$ under $F$ is

$X^{+} = {A \in U ∣ the FD X \to A is derivable from F} .$

The step-by-step procedure (the same idea used by hand in the lecture):

Start with $X^{+} := X$ — an attribute always determines itself, no dependency needed.
For every FD $Y \to Z$ in $F$ : if $Y \subseteq X^{+}$ , then add every attribute of $Z$ to $X^{+}$ .
Repeat step 2 until a complete pass adds nothing new.

Every symbol: $X$ is the starting attribute set, $X^{+}$ (read "X plus") is the growing answer set, $Y \to Z$ is any functional dependency in the given set $F$ , and $U$ is the set of all attributes of the relation. The loop must keep going until a full pass changes nothing, because a newly added attribute can unlock further dependencies. This is exactly what makes the result a closure: it is everything reachable, and it stops growing only when no rule fires anymore.

Q: What is the closure of an attribute?

A: The set of all attributes functionally determined by that attribute. From $A$ , for example, you reach $A$ itself and $B$ , because the dependency $A \to B$ is there, so $A^{+} = {A, B}$ . The starting attribute always appears in its own closure — that part needs no dependency at all.

The closure is the single tool behind three exam-style tasks: finding candidate keys (an attribute set $X$ is a key exactly when $X^{+}$ covers every attribute of the relation, and no smaller set does), testing whether an FD is redundant (Section 6.2.2), and testing whether a left-side attribute is redundant (Section 6.2.3).

6.2.2 When a Whole Functional Dependency Is Redundant

A minimal cover (also called a canonical cover) is a set of FDs that is equivalent to the original set — meaning the closures are the same, so both sets derive exactly the same dependencies — and that contains no redundancy. To test whether one FD $X \to Y$ is redundant, hide it: remove it from the set, recompute $X^{+}$ , and compare with the closure you got before hiding. If before and after are the same, the dependency carries no new information, and it can be dropped.

Why only the left side's closure matters. Hiding $X \to Y$ can change only the closure of attribute sets that contain $X$ — and in fact you do not even need to re-check all of those. The dependency $X \to Y$ is redundant exactly when $Y$ is still reachable without it:

$X \to Y is redundant in F ⟺ Y \subseteq X^{+} computed under F - {X \to Y} .$

So the whole test is: remove the dependency, recompute $X^{+}$ , and ask whether $Y$ is still inside. If yes, the FD added nothing new and can be removed; if no, it is the only source of some attribute, so it must stay. Every other closure in the set is irrelevant to this single question — that is the professor's "hide it and compare" trick, and it is what keeps the method fast enough to do by hand.

6.2.3 When an Attribute on the Left Side Is Redundant

A dependency can also have redundancy on its left side. For $A C \to D$ , ask: is $A$ redundant? Replace the dependency with $C \to D$ — everything else stays — and compare $C^{+}$ before and after the replacement. If the closures are the same, $A$ was redundant; if they differ, $A$ is needed. The same test applies to $C$ : replace $A C \to D$ with $A \to D$ and compare $A^{+}$ . Once you find a minimal set of FDs — no whole dependency redundant, no left-side attribute redundant — you have the canonical cover.

Scope: the redundancy tests assume you are comparing like with like. "Before" means with the original dependency intact (or the original left side intact); "after" means with it hidden or replaced. The two closures must match exactly — both as sets of attributes. Any change counts, an addition or a reduction: if $C^{+}$ grows from ${C, B}$ to ${C, B, D}$ , the closures are not the same, and the attribute you hid is not redundant. The lecture stated this rule explicitly after a student asked whether only a reduction matters.

6.2.4 Canonical Covers Are Not Unique

Because the order of the checks is your choice, the result is not unique. Someone who starts from a different dependency in the list may find a different dependency redundant and end with a different — but still equivalent — minimal set. Both answers are correct. This is an explicit rule of the method: a canonical cover found by one person can legitimately differ from one found by another person, and both are valid as long as each is equivalent to the original set.

The method is recursive in a strict way. Whenever the set of FDs changes — a dependency is removed, or a new one appears — you start again from the top of the list and check everything once more, because a dependency you kept earlier may become redundant later, and one you removed earlier may be needed again in a different pass.

Q: At one step we decide a dependency is redundant and that part needs no more closure work — but in a later step it might be needed, right?

A: Exactly right. Suppose the set changes — say a new dependency $A \to D$ appears. Then you start again from the first step onward and run the whole pass once more. The recursive rule applies every time the set changes. In practice this is why the reference books also give a fixed order — first shrink left sides, then drop redundant dependencies — because with the wrong order you can stop early and miss a redundancy. The lecture's restart rule achieves the same safety: every change forces a fresh full pass.

6.2.5 From a Minimal Cover to Third Normal Form

The synthesis algorithm turns a minimal cover into a third normal form (3NF) schema, and it is short: first, find the minimal set of FDs (the canonical cover). Second, for every FD in that minimal set, create a new relation containing all the attributes of that FD — dependencies that share the same left side are grouped into one relation. Third, if no relation among the ones you created contains a candidate key, create one more relation containing just the candidate key. That is the entire algorithm, and the resulting schema is in 3NF, dependency preserving, and lossless.

The synthesis algorithm, step by step.

Minimal cover. Find a set $G$ of FDs equivalent to the given set $F$ , with no redundant dependency and no redundant left-side attribute (Sections 6.2.2–6.2.3).
One relation per left side. For each left side $X$ appearing in $G$ , create one relation with attributes ${X} \cup {all right sides of FDs with left side X}$ . The left side $X$ becomes the key of that relation.
Key check. If none of the relations created contains a candidate key of the original relation, add one more relation holding exactly a candidate key.
(Implicit cleanup.) If two created relations have the same attribute set, they collapse into one.

The properties are guaranteed by the construction, not by luck: every dependency of $G$ lives inside some relation (dependency preservation), and the key relation (when needed) makes the join non-lossy. If the third step is skipped, the design can be lossless in name only — some information about which keys went together is silently destroyed.

This is the whole reason the normalization machinery exists. When we formed an ER diagram and converted it into a relational schema, we could not prove with mathematical certainty that the result was a good relation. Functional dependencies, first and second normal form, third normal form, BCNF, closure, and minimal covers give us that certainty. Lossless join matters because of spurious tuples: when two relations are decomposed and later joined, if the common attribute is not a candidate key in at least one of the relations, the join manufactures extra, wrong tuples. Up to third normal form we keep both dependency preservation and lossless join. When we move to BCNF, it may become impossible to preserve every dependency — and then we still insist on a lossless join.

The spurious tuple trap. Suppose a relation is decomposed into two relations whose only common attribute is not a key of either side. Joining them back can produce combinations of values that never existed together in the original data — fabricated rows. The lecture's rule of thumb: for a two-way split, the common attribute must be a candidate key in at least one of the two relations. This is the same condition the reference books state as Property NJB — the join is non-lossy exactly when the common attribute determines one of the two halves. Up to 3NF the synthesis algorithm buys this condition for free; from BCNF onward, dependency preservation may have to be sacrificed, but losslessness never is.

6.3 Worked Example 1: A Minimal Cover over {A, B, C, D}

6.3.1 The Setup

A relation is given, and the functional dependencies are given, with nobody telling you what the candidate keys are. You must find the candidate keys and the prime attributes, find the minimal cover, decompose into 3NF, and decompose into BCNF — verifying that the decomposition is lossless, and checking dependency preservation. For BCNF, losing dependencies is possible, so you check; for the lossless property, the rule is: when decomposing, the common attribute must be a candidate key in at least one relation, otherwise joining creates spurious tuples.

The dependencies for this exercise:

$F = {A \to B, D \to A B C, C \to B, A C \to D}$

over the attribute set ${A, B, C, D}$ . Every closure check performed in the discussion is consistent with exactly this set, so this is the intended list. A prime attribute is an attribute that belongs to at least one candidate key; a non-prime attribute belongs to none.

Two splitting rules are worth keeping straight. A right side can be split attribute by attribute: $D \to A B C$ is the same as $D \to A$ , $D \to B$ , $D \to C$ . A left side cannot be split: $A C \to D$ does not mean $A \to D$ , and it does not mean $C \to D$ .

6.3.2 Finding a Candidate Key

Compute the closure of each left side. $D^{+} = {A, B, C, D}$ : from $D$ we reach $D$ , then $A$ , $B$ , and $C$ through $D \to A$ , $D \to B$ , $D \to C$ . Since the relation has exactly four attributes and $D$ determines all of them, $D$ is a candidate key. The problem says "find the candidate keys and the prime attributes" — with one candidate key $D$ , the prime attribute is $D$ itself.

A completeness check the lecture's shortcut can miss. $D$ is a candidate key, but it is not the only one. Check $A C$ : from $A C$ we reach $A$ and $C$ , then $B$ through $A \to B$ , then $D$ through $A C \to D$ , so $A C^{+} = {A, B, C, D}$ — all four attributes. Is $A C$ minimal? Its proper subsets $A$ and $C$ give $A^{+} = {A, B}$ and $C^{+} = {C, B}$ , and no single one of them covers the relation. So $A C$ is a candidate key too.

Corrected answer for the exam: candidate keys are $D$ and $A C$ ; prime attributes are $A, C, D$ ; the only non-prime attribute is $B$ . The habit of stopping at the first superkey found is the classic way to drop marks on "find the candidate keys and prime attributes" questions: the closure test proves superkey status, and minimality needs a second look at the subsets.

6.3.3 Checking Each Functional Dependency

Go through the set one dependency at a time, hiding each and comparing closures. Remember the rule: an FD is redundant exactly when its own left-side closure is unchanged after hiding it (Section 6.2.2).

$A \to B$ : before hiding, $A^{+} = {A, B}$ . Hiding $A \to B$ leaves $A^{+} = {A}$ . Different, so $A \to B$ is not redundant; it stays.
$D \to A$ : before hiding, $D^{+} = {A, B, C, D}$ . Hiding $D \to A$ leaves $D^{+} = {B, C, D}$ (from $D \to B$ and $D \to C$ , with $C \to B$ adding nothing new). Different, so $D \to A$ is not redundant.
$D \to C$ : hiding it leaves $D^{+} = {A, B, D}$ (from $D \to A$ , and $A \to B$ ). Different, so $D \to C$ is not redundant. A question came up here — why is $D^{+}$ not ${A, C, D}$ at this point? Because the dependency being hidden is exactly $D \to C$ ; we compare before and after, one dependency at a time, and while it is hidden, $C$ is unreachable from $D$ .
$D \to B$ : hiding it leaves $D^{+} = {A, C, D}$ , and from $A \to B$ we still reach $B$ . So $D^{+}$ is again ${A, B, C, D}$ — the same as before. So $D \to B$ is redundant and is removed from the set, playing no further role.
$C \to B$ : before hiding, $C^{+} = {C, B}$ . Hiding $C \to B$ leaves $C^{+} = {C}$ . Different, so $C \to B$ is not redundant.
$A C \to D$ : before hiding, $A C^{+} = {A, C, B, D}$ — $A$ , $C$ , then $B$ through $A \to B$ , then $D$ through $A C \to D$ . Hiding $A C \to D$ leaves $A C^{+} = {A, B, C}$ . Different, so the whole dependency is not redundant — although it is still possible that one of $A$ or $C$ on the left side is redundant.

6.3.4 Checking the Left Side of AC → D

Is $A$ redundant in $A C \to D$ ? Hide $A$ by replacing $A C \to D$ with $C \to D$ . Before the replacement, $C^{+} = {C, B}$ . After, $C^{+} = {C, B, D}$ — $D$ comes from the new $C \to D$ . The closures differ, so $A$ is not redundant.

Is $C$ redundant? Replace $A C \to D$ with $A \to D$ . Before, $A^{+} = {A, B}$ . After, $A^{+} = {A, B, D}$ . The closures differ, so $C$ is not redundant either.

Q: When $A C \to D$ is hidden, how does $A C^{+}$ still include $B$ ?

A: Because $A C$ contains $A$ , and $A \to B$ is still active. From $A C$ we reach $A$ and $C$ , then $B$ through $A \to B$ . The hidden dependency only removes the $D$ that $A C \to D$ used to provide.

Q: Explain the $C$ closure check for the redundancy of $A$ once more. And does only a reduction matter, or also an addition?

A: Normally $C^{+} = {C, B}$ . To test whether $A$ is redundant in $A C \to D$ , we hide $A$ by adding $C \to D$ in its place. Now $C^{+} = {C, B, D}$ , which is more than before — not the same. So $A$ is not redundant. Any change counts, addition or reduction: the before and after closures must match exactly.

6.3.5 The Minimal Cover and Questions

The final minimal cover is ${A \to B, D \to A, D \to C, C \to B, A C \to D}$ , with candidate keys $D$ and $A C$ . Only $D \to B$ was removed. The discussion moved on to a second example before the 3NF decomposition of this relation was written out; the synthesis algorithm from the previous section applies unchanged to this cover — completed here in full.

Completing the promised 3NF decomposition (synthesis).

Minimal cover: $G = {A \to B, D \to A, D \to C, C \to B, A C \to D}$ .

Step 2 — one relation per left side:

$D \to A, D \to C$ share left side $D$ → $S_{1} (D, A, C)$ with key $D$
$A \to B$ → $S_{2} (A, B)$ with key $A$
$C \to B$ → $S_{3} (C, B)$ with key $C$
$A C \to D$ → $S_{4} (A, C, D)$ with key $A C$

Step 3 — key check: the candidate keys are $D$ and $A C$ , and $S_{1} = (D, A, C)$ and $S_{4} = (A, C, D)$ are the same attribute set, so one of them collapses. Keep $(A, C, D)$ : it contains both candidate keys, so no extra key relation is needed.

Final 3NF schema: $R_{1} (A, C, D)$ , $R_{2} (A, B)$ , $R_{3} (C, B)$ .

Verification: every FD of the minimal cover sits inside one relation ( $A \to B$ in $R_{2}$ , $C \to B$ in $R_{3}$ , $A C \to D$ , $D \to A$ , $D \to C$ in $R_{1}$ ) — dependency preserving. $R_{1}$ contains candidate keys $D$ and $A C$ — lossless. $R_{2}$ and $R_{3}$ are 3NF by inspection: their only dependencies have a single-attribute key on the left. In $R_{1}$ every attribute is prime (its keys are $D$ and $A C$ ), so no 3NF violation is possible.

Sense-check: the two "twin" relations $(D, A, C)$ and $(A, C, D)$ differing only in column order are one relation, and the key check needed nothing extra because the key lives inside it already.

The BCNF part of the problem, and the dependency that is lost. The lecture's setup asks for a BCNF decomposition as well, and it is worth seeing because it shows why the lecture says "at BCNF, dependency preservation may fail."

The violating FD is $A \to B$ : $A$ is not a superkey (it is not a candidate key). Split the relation on this violation into $(A, B)$ and $(A, C, D)$ . The second relation is already in BCNF: its dependencies $A C \to D$ , $D \to A$ , $D \to C$ all have superkey left sides within $(A, C, D)$ — indeed $D^{+}$ and $A C^{+}$ both cover all of $(A, C, D)$ .

But check $C \to B$ : $C$ lives in $(A, C, D)$ , $B$ lives in $(A, B)$ , and nothing connects them anymore — no FD with left side $C$ survives in either relation, so $C \to B$ is lost. This is exactly the lecture's point: BCNF buys a stronger normal form and pays for it with a lost dependency, while 3NF keeps both losslessness and dependency preservation.

Q: At one step we decide a dependency is redundant and that part needs no more closure work — but in a later step it might be needed, right?

A: Exactly right. Suppose the set changes — say a new dependency $A \to D$ appears. Then we start again from the first step onward and run the whole pass once more. The recursive rule applies every time the set changes.

Exam note: this problem type is exactly what Quiz 1 expects — find the candidate keys and prime attributes, compute closures, find the minimal cover by hiding each dependency and comparing closures, and (for the written exam) synthesize the 3NF schema. Write the before-and-after closures down; partial marks live in the closure work, not just in the final set.

6.4 Worked Example 2: Minimal Cover and 3NF Decomposition

6.4.1 The Setup

The second exercise repeats the whole method on a relation over ${W, X, Y, Z}$ . The dependencies, read aloud:

$F = {X \to W, W \to X Y, W Z \to Y, Y \to X Z}$

This set matches every closure computed in the discussion, so it is the intended list. Notice the shapes: $W \to X Y$ has two attributes on the right (split into $W \to X$ and $W \to Y$ when needed), and $W Z \to Y$ has two attributes on the left (never split: $W Z \to Y$ does not mean $W \to Y$ ).

6.4.2 The Candidate Key and the First Checks

$X \to W$ : $X^{+} = {X, W}$ . Hiding $X \to W$ leaves $X^{+} = {X}$ . Not redundant; it stays.
$W Z \to Y$ : before hiding, $W Z^{+} = {W, Z, X, Y}$ — $W Z \to Y$ brings $Y$ , $Y \to X Z$ brings $X$ and $Z$ , $X \to W$ brings $W$ . Since $W Z^{+}$ covers all four attributes, $W Z$ is a superkey. Hiding $W Z \to Y$ : $W Z^{+} = {W, Z, X, Y}$ again — $W \to X Y$ brings $X$ and $Y$ , $Y \to X Z$ brings $X$ and $Z$ . Before and after are the same, so $W Z \to Y$ is redundant and is removed completely from the set from this point onward.
$W \to X Y$ : hiding it leaves $W Z^{+} = {W, Z}$ — nothing else applies. Before, it was ${W, Z, X, Y}$ . Different, so $W \to X Y$ is not redundant; it stays.
$Y^{+} = {Y, X, Z, W}$ : $Y \to X Z$ brings $X$ and $Z$ , and $X \to W$ brings $W$ . A slip was caught here: the first pass through this check missed $W$ , because the $X \to W$ path was overlooked. Once included, $Y^{+}$ covers every attribute.
$Y \to X$ : hiding it leaves $Y^{+} = {Y, Z}$ . Not redundant; it stays.
$Y \to Z$ : hiding it leaves $Y^{+} = {Y, X, W}$ . Not redundant; it stays.

After this pass the set is ${X \to W, W \to X Y, Y \to X Z}$ .

Which attributes are really the keys? The lecture's wording here says "WZ is a candidate key for sure." The closure test proves WZ is a superkey (it determines everything), but a candidate key must also be minimal — and WZ is not. Look again: $W^{+}$ under the full set is ${W, X, Y, Z}$ — $W \to X Y$ brings $X$ and $Y$ , then $Y \to X Z$ brings $Z$ — so $W$ alone already determines the whole relation. Likewise $Y^{+} = {Y, X, Z, W}$ , so $Y$ is a key too. Proper subsets check out: $X^{+} = {X, W}$ and $Z^{+} = {Z}$ , so neither $X$ nor $Z$ is a key.

Corrected answer for the exam: the candidate keys of this relation are $W$ and $Y$ ; the prime attributes are $W$ and $Y$ ; $X$ and $Z$ are non-prime. $W Z$ is a superkey but not a candidate key. The same trap as Example 1: the first superkey found is not automatically the (only) key.

6.4.3 Checking the Left Side of WZ → Y

The technique was then shown on the left side of $W Z \to Y$ . To test whether $Z$ is redundant: replace $W Z \to Y$ with $W \to Y$ , and compare $W^{+}$ . Before the replacement, $W^{+} = {W}$ — with the dependency intact, $W$ alone implies nothing. After, $W^{+} = {W, Y, X, Z}$ : $W \to Y$ gives $Y$ , $Y \to X Z$ gives $X$ and $Z$ , $X \to W$ gives $W$ . Not the same, so $Z$ is not redundant.

To test whether $W$ is redundant: replace $W Z \to Y$ with $Z \to Y$ . Before, $Z^{+} = {Z}$ . After, $Z^{+} = {Z, Y, X, W}$ — $Z \to Y$ , then $Y \to X Z$ , then $X \to W$ . Not the same, so $W$ is not redundant either.

Reconciling this demonstration with the original dependencies. The "before" closure in this walkthrough assumes $W$ alone implies nothing — and that is only true if $W \to X Y$ is absent. But $W \to X Y$ is still in the set. Under the original dependencies, $W^{+}$ is already ${W, X, Y, Z}$ before any replacement, because $W \to X Y$ supplies $X$ and $Y$ and $Y \to X Z$ supplies $Z$ . Redone with the correct closures:

Is $Z$ redundant in $W Z \to Y$ ? Replace $W Z \to Y$ with $W \to Y$ . Before: $W^{+} = {W, X, Y, Z}$ . After: $W^{+} = {W, Y, X, Z}$ — the same set. The closures match, so $Z$ is redundant: $W \to X Y$ already tells us $W \to Y$ , and $W Z$ contains $W$ , so $W Z \to Y$ is derivable without $Z$ .
Is $W$ redundant? Replace $W Z \to Y$ with $Z \to Y$ . Before: $Z^{+} = {Z}$ . After: $Z^{+} = {Z, Y, X, W}$ — different, so $W$ is not redundant.

Shrinking the left side first is exactly the order the reference books recommend (remove extraneous left-side attributes, then remove redundant dependencies): once $W Z \to Y$ becomes $W \to Y$ , the next pass sees $W \to Y$ as redundant because $W \to X Y$ already contains it, and removes it — landing on ${X \to W, W \to X Y, Y \to X Z}$ , the same cover the whole-dependency pass produced in Section 6.4.2. This is the professor's own restart rule doing its job: whenever the set changes, run the whole pass again.

6.4.4 Questions and Answers

Q: At this step, we will not use the removed dependency $W Z \to Y$ any more — is it eliminated completely from this point of the discussion?

A: Yes, completely removed from this point onward; it plays no further role here. And a caution: somebody who starts from a different place may find a different dependency redundant, and that is acceptable. Canonical covers for two different people can differ, and both are still correct as long as each is equivalent to the original set.

Q: When we hide $W Z \to Y$ and compute $W Z^{+}$ , we get $W Z$ and $Y$ easily — but how do we say $W Z^{+}$ contains $X$ ?

A: Through paths that stay in the set. $W \to X Y$ gives $X$ and $Y$ directly, since $W Z$ contains $W$ ; and once $Y$ is there, $Y \to X$ gives $X$ again. Either way it is a kind of transitive reach: $W Z$ reaches $Y$ , and $Y$ reaches $X$ .

Q: If we remove $Z$ from $W Z \to Y$ , then $W \to Y$ , and transitively $Y \to Z$ , $Y \to X$ — so it seems like both attributes together are redundant?

A: Compare like with like. Before the removal, $W^{+} = {W}$ only — $W$ alone implies nothing. After replacing the dependency with $W \to Y$ , $W^{+} = {W, Y, X, Z}$ . The two closures are not the same, so $Z$ is not redundant. The same comparison for $W$ : $Z^{+} = {Z}$ before, ${Z, Y, X, W}$ after, so $W$ is not redundant either. (The reconciliation box in Section 6.4.3 shows what changes when the "before" closure is computed under the original dependencies.)

Q: For an FD with a combination of three attributes on the left side, do we remove them one by one?

A: Yes, one at a time. If the dependency is $W Y Z \to K$ , remove $W$ and write $Y Z \to K$ , then compare $Y Z^{+}$ before and after; then remove $Y$ and write $W Z \to K$ ; then remove $Z$ . And if any removal turns out redundant, you start once again from the top of the list — the whole pass repeats in a recursive manner, because a redundancy found later can invalidate an earlier decision. Two orders of work are both acceptable: first find out whether anything more is redundant and then check everything, or check everything and then find out what is redundant. Both approaches are okay, and your answers may differ in shape while both stay correct.

Q: You said there can be multiple minimal sets of dependencies — some with more dependencies than others. Are all minimal dependencies equivalent? Do all of them produce a 3NF that is dependency preserving and lossless?

A: Yes. All minimal covers are equivalent — in one you may get $X \to Y$ , in another $X \to Z$ , but the sets derive the same dependencies. Each one, when used for synthesis, produces a third normal form that is dependency preserving and lossless. In my experience the number of dependencies does not change; only which ones appear.

6.4.5 The Final Minimal Cover

The final set presented was ${X \to W, W Z \to Y, Y \to X Z}$ .

Reconciliation: this final set conflicts with the pass above, and the restart rule resolves it. The set ${X \to W, W Z \to Y, Y \to X Z}$ is not equivalent to the original dependencies. Check it: under this set, $W^{+} = {W}$ — $W \to X Y$ is gone, so $W$ no longer implies $X$ or $Y$ . The FD $W \to X Y$ (which the pass in Section 6.4.2 explicitly kept) has been lost from the closure. The set that is actually equivalent to the original dependencies — and the one that matches every closure check performed live — is

${X \to W, W \to X Y, Y \to X Z}$

Evidence for equivalence: hiding $W Z \to Y$ changed nothing (Section 6.4.2 showed $W Z^{+}$ is unchanged without it, since $W \to X Y$ already supplies $Y$ ), and hiding $W \to X Y$ changed $W Z^{+}$ from ${W, Z, X, Y}$ to ${W, Z}$ , so it must stay. The professor's stated restart rule catches the slip: whenever the set changes — here, replacing $W \to X Y$ with $W Z \to Y$ — you rerun the whole pass, and the pass would restore $W \to X Y$ . For the exam: the minimal cover is ${X \to W, W \to X Y, Y \to X Z}$ , and the candidate keys are $W$ and $Y$ (Section 6.4.2).

6.4.6 The 3NF Decomposition

Synthesis: one relation per FD in the minimal cover, grouping dependencies with a common left side.

$X \to W$ gives $R_{1} (X, W)$ , where $X$ is the candidate key.
$W Z \to Y$ gives $R_{2} (W, Z, Y)$ , where $W Z$ is the candidate key.
$Y \to X Z$ gives $R_{3} (Y, X, Z)$ , where $Y$ is the candidate key.

Key check: the candidate key $W Z$ is already contained in $R_{2}$ , so no extra relation holding the key is needed. The three relations $R_{1} (X, W)$ , $R_{2} (W, Z, Y)$ , $R_{3} (Y, X, Z)$ are the resulting third normal form schema.

The same synthesis from the reconciled cover. Applying the algorithm to the reconciled minimal cover ${X \to W, W \to X Y, Y \to X Z}$ :

$X \to W$ gives $R_{1} (X, W)$
$W \to X Y$ gives $R_{2} (W, X, Y)$
$Y \to X Z$ gives $R_{3} (Y, X, Z)$

Key check with the true keys $W$ and $Y$ : $W$ already sits inside $R_{1}$ , and $Y$ already sits inside $R_{3}$ — so no extra key relation is needed. Final schema: $R_{1} (X, W)$ , $R_{2} (W, X, Y)$ , $R_{3} (Y, X, Z)$ .

Verification: every FD of the cover is inside a relation ( $X \to W$ in $R_{1}$ , $W \to X Y$ in $R_{2}$ , $Y \to X Z$ in $R_{3}$ ) — dependency preserving. A candidate key is present ( $W$ in $R_{1}$ ) — lossless. And $R_{2}$ is actually BCNF, since $W$ , $X$ , and $Y$ each determine the others there. Sense-check: $W \to X Y$ must not be lost, and it is not — it lives whole in $R_{2}$ .

The professor's version $R_{1} (X, W)$ , $R_{2} (W, Z, Y)$ , $R_{3} (Y, X, Z)$ is still a valid 3NF decomposition of the original relation, and worth understanding: $W \to X Y$ survives even though no single relation carries it whole, because $W \to Y$ holds inside $R_{2}$ and $Y \to X$ holds inside $R_{3}$ , so the dependency is re-derivable across the schema. Its key check also passes with the true keys ( $W \in R_{1}$ , $Y \in R_{3}$ ). The difference between the two answers is the cover each was built from; both are dependency preserving and lossless, and $R_{2} (W, Z, Y)$ — unlike $R_{2} (W, X, Y)$ — is 3NF but not BCNF, because $W \to Y$ has a non-superkey left side. In an exam, name the minimal cover you used; both schemas are accepted.

6.5 Relational Algebra: The Mathematical Foundation of SQL

6.5.1 Why Relational Algebra Exists

Relational algebra is the mathematical form that works underneath query languages. Some query languages use relational algebra as their basis; others use relational calculus — mostly tuple relational calculus or domain relational calculus. We learn relational algebra for two reasons: it is mathematical, and it plays a key role in query optimization — the rewriting of queries that we cannot do in SQL. Everything that can be represented in relational algebra can also be represented in SQL, but the reverse is not always true.

The two reasons in detail. (1) It is mathematical: a query is an expression built from a small set of operations, so its meaning is exact and provable — there is no room for the ambiguity of natural language. (2) It enables query optimization: a database system can algebraically rewrite an expression into a cheaper one with the same result — for example, pushing a selection down before a join so that fewer rows are joined. SQL itself cannot be rewritten this way, because the system works on the algebra underneath the SQL. Query optimization is precisely "rewriting queries we cannot do in SQL," and it is a later lecture's topic; here we learn the language that makes it possible.

6.5.2 The Operations

The operations of relational algebra are: select $σ$ , project $π$ , rename $ρ$ , union $\cup$ , cartesian product $\times$ , join $⋈$ , and division $\div$ . Set operations appear as well: union, set difference, and intersection. A relation is a set — rows and columns — and nothing repeats in a relation. We start with a relation, apply operations, and end with a relation; if an operation (projection, for example) would produce a duplicate, the duplicate is removed because the result must still be a relation.

One operation in, one relation out. This property — the result of every operation is itself a relation — is the relational closure property, and it is the reason expressions can be nested: the output of one operation is a legal input to the next, so a query of any length is a single expression. The unary operations (select $σ$ , project $π$ , rename $ρ$ ) take one relation; the binary operations (union $\cup$ , set difference $-_{set}$ , intersection $\cap$ , cartesian product $\times$ , join $⋈$ , division $\div$ ) take two. Because a relation is a set, duplicates never survive any operation — this comes up again in Section 6.5.4.

6.5.3 Select and Project Are Not the SQL Select

The vocabulary contrast matters: select in relational algebra is not the same as select in SQL. In relational algebra, select picks out a limited number of rows — tuples — from a relation, based on a predicate. In SQL, "select first name, middle name, last name from ... where ..." picks out a limited set of attributes — columns — which is what project does in relational algebra. SQL's where clause is the closer cousin of relational algebra's select. A predicate is the mathematical term for a condition written on an operation — for example, "salary is greater than 30,000 dollars."

The vocabulary map. Relational algebra's $σ$ (select) → SQL's WHERE clause. Relational algebra's $π$ (project) → SQL's SELECT clause. This is the professor's key terminology contrast: when SQL says "select", it is projecting; when it says "where", it is selecting. Using the two names interchangeably is the single most common confusion in this chapter.

Select and project are not commutative. Commutative means $a \cdot b = b \cdot a$ : the order of application does not matter. Here the order does matter: if we project first, the attributes we need for the predicate may no longer be in the relation, and the later select cannot use them. If we select first, all attributes are still present, and the projection afterwards keeps only what the user wants.

Q: Isn't select in relational algebra the same as select in SQL?

A: No. Select in relational algebra filters rows — tuples — by a predicate, keeping all attributes. Select in SQL picks columns, which is exactly what project does in relational algebra. SQL's where clause is the closer relative of relational algebra's select.

Q: What does commutative mean here — $a$ dot $b$ equals $b$ dot $a$ ?

A: Yes: two operations are commutative when doing $a$ then $b$ gives the same result as doing $b$ then $a$ . Select and project are not commutative.

Pitfalls for the select–project pair. (1) Project first, select later on the dropped column: the predicate becomes unanswerable — the expression is simply wrong, not slower. (2) Forgetting that select keeps all attributes: $σ_{dno = 4} (EMPLOYEE)$ returns full employee rows, not just department numbers. (3) Confusing the two SQL clauses: SELECT clause projects, WHERE clause selects. (4) Assuming duplicate rows survive: projection removes duplicates, so the result has no repeats. The textbook formal facts behind these: select is commutative with itself ( $σ_{c_{1}} (σ_{c_{2}} (R)) = σ_{c_{2}} (σ_{c_{1}} (R))$ ), a cascade of selects collapses into one conjunctive select, and $π_{L_{1}} (π_{L_{2}} (R)) = π_{L_{1}} (R)$ holds exactly when $L_{2}$ contains $L_{1}$ — otherwise the expression is invalid, which is precisely the order trap.

6.5.4 Worked Examples on the EMPLOYEE Schema

The practice schema is EMPLOYEE with the attributes first name (fname), middle name (minit), last name (lname), SSN (ssn), birth date (bdate), address, sex, salary, department number (dno), and supervisor SSN (superssn). These abbreviations come from the practice sheet; the full names in the reference schema are Fname, Minit, Lname, Ssn, Bdate, Address, Sex, Salary, Super_ssn, Dno — same attributes, and either naming is accepted. The worked numbers below use the standard sample data: eight employees, with the department-5 staff being Smith (123456789), Wong (333445555), Narayan (666884444), and English (453453453).

Example 1 — employees of department 4. Select all employee tuples whose department number is 4: write the select operator with the predicate "department number is equal to 4" and the relation EMPLOYEE inside.

$σ_{dno = 4} (EMPLOYEE)$

Worked with real rows: the predicate is applied to each tuple independently, and every tuple that passes keeps all of its attributes. In the sample data the result contains exactly the tuples for Zelaya (999887777), Wallace (987654321), and Jabbar (987987987) — three full rows, each with all ten attributes. Sense-check: the output is a horizontal slice of the table — the same columns, a subset of the rows.

Example 2 — salaries above 30,000. Select all employee tuples whose salary is greater than 30,000 dollars. The predicate is "salary is greater than 30,000":

$σ_{salary > 30000} (EMPLOYEE)$

Worked with real rows: Wong (40,000), Wallace (43,000), Narayan (38,000), and Borg (55,000) pass; Smith's 30,000 does not, because the comparison is strict. Four full rows out. Sense-check: "greater than" excludes the boundary value — 30,000 is not greater than 30,000.

Example 3 — names of department 5 employees, and the order trap. The user wants first name, middle name, and last name of all employees who work in department 5. Two ways suggest themselves. Select first, then project:

$π_{fname, minit, lname} (σ_{dno = 5} (EMPLOYEE))$

Or project first, then select:

$σ_{dno = 5} (π_{fname, minit, lname} (EMPLOYEE))$

The second is not a correct answer: after projecting fname, minit, lname, the department number is gone from the relation, so the predicate cannot be evaluated. A working alternative: project fname, minit, lname and dno together, then select on dno = 5, then project the three names again. The user does not want dno in the final answer, so a second projection cleans it out.

Worked with real rows (correct version): selecting dno = 5 first leaves the four department-5 tuples — Smith, Wong, Narayan, English — still with all ten attributes; projecting then yields exactly four rows (John B Smith, Franklin T Wong, Ramesh K Narayan, Joyce A English). No duplicates arise here because fname, minit, lname is a key-compatible list, but if the projection had produced repeats, they would be eliminated. Sense-check: the query is a vertical slice of a horizontal slice — filter rows, then trim columns, in that order.

Example 4 — SSNs of department 5 employees and their direct supervisors. The user wants the social security number of every employee who works in department 5, or who directly supervises an employee who works in department 5. This needs two relations. First, the SSNs of department 5 employees:

$π_{ssn} (σ_{dno = 5} (EMPLOYEE))$

Second, the supervisor SSNs: take the same employees, read off their superssn column instead:

$π_{superssn} (σ_{dno = 5} (EMPLOYEE))$

The user wants one single list, so we union the two:

$π_{ssn} (σ_{dno = 5} (EMPLOYEE)) \cup π_{superssn} (σ_{dno = 5} (EMPLOYEE))$

Worked with real rows: the first projection gives ${123456789, 333445555, 666884444, 453453453}$ . The second gives the supervisor SSNs of exactly those four employees — ${333445555, 888665555}$ after duplicates collapse. The union is ${123456789, 333445555, 666884444, 453453453, 888665555}$ — five values, and 333445555 (Wong, who works in department 5 and supervises three of his colleagues) appears exactly once. Sense-check: the answer is one column, no repeats, and a supervisor who is also a department-5 employee is counted once, not twice.

Why not simply write $π_{ssn, superssn} (σ_{dno = 5} (EMPLOYEE))$ ? That gives two columns, but the user asked for one column — one list of numbers. The union of two relations is allowed only when the relations are compatible: the same number of attributes, and corresponding attributes with the same or similar domains. Both operands here are single-column relations of SSN values, so the union is a single relation of SSNs. If an SSN appears in both (a supervisor who also works in department 5), it appears once in the result, because the result is a relation.

Union compatibility, precisely. Two relations $R (A_{1}, \dots, A_{n})$ and $S (B_{1}, \dots, B_{n})$ are union compatible when they have the same number of attributes (the same degree $n$ ) and each pair of corresponding attributes has the same domain. Union, intersection, and set difference are all defined only on union-compatible operands. The set operations then behave exactly as in set theory, with one relational addition: duplicates are eliminated. This is why the professor's example can join the two single-column lists — both are degree one over the SSN domain — and why merging $π_{ssn, superssn}$ would answer a different question: that expression yields two columns, not one.

6.5.5 Questions and Answers

Q: Project basically returns a set of rows just like select, but only for the listed attributes — everything else is gone?

A: Exactly right. The same rows remain, but only the listed attributes stay in the result.

Q: Between selecting first and then projecting, or projecting first and then selecting — which is better?

A: Select first. If you project only fname, minit, lname, the department number is no longer in the relation and you cannot filter on it afterwards — the second option does not even give a correct answer. Projecting the department number as well, then selecting, then projecting the three names again is also valid, but select-then-project does the job directly.

Q: Can we merge two predicates in the same line — say department number 5 and SSN equal to supervisor SSN?

A: Row-wise predicates combine fine: "department number 5 and salary greater than 30,000" is one valid predicate. But SSN equal to superssn pairs two columns, which is a different kind of condition, and besides, the user wants a single column in the end.

Q: What if the supervisor also works in department 5?

A: Then the first relation already contains that supervisor's SSN, and the union removes the duplicate — the result has it once, because a relation holds no redundancy. And if the supervisor works in a different department, say 7? We do not care where the supervisor works. The second term asks for the superssn of whoever supervises an employee of department 5, wherever that supervisor sits.

Q: So the union operation makes the result unique?

A: Yes — and not just union. Every operation ends with a relation, and a relation is a set, so the final answer of a union, a set difference, even a projection, contains no duplicates. In projection, if the original had four attributes and we keep one, the result is unique on that one attribute.

6.5.6 Exam Notes and Next Steps

Exam note: relational algebra is not part of Quiz 1. There are no questions on it in this quiz, so it can be learned without stress — and the quiz covers normalization, everything discussed up to this point. More relational algebra practice and SQL work (with MySQL) follow next. The practice sheet used here is the same one used in the lab, where Python or Node.js connects to MySQL.

The next step connects the two halves of the course promise: relational algebra is the mathematical language of retrieval, and SQL is the practical language — with MySQL as the engine, and Python or Node.js as the application layer that sends queries and consumes the results.

Exam Guidance Summary

Quiz 1 opens on the 19th and closes on the 28th, on the e-learn platform (also called Takshila).
Format: 25 multiple-choice questions; attempt the most correct answer; no negative marking; 5% weightage.
You may attempt in one sitting or several, with no fixed time limit, but you can submit only once — submit at least once before the deadline to be marked.
Open book: books and notes may be consulted while attempting.
Coverage: everything discussed so far, which means normalization. Expect problems on finding candidate keys and prime attributes, computing closures, and finding minimal covers.
Relational algebra is not part of Quiz 1; it will be practiced next, along with SQL.
Different courses run different quizzes; formats depend on the instructor.

Exam note: the quiz's problem style is the worked-example method itself: compute closures, identify the candidate keys (remember minimality — the first superkey found may not be the key), hide dependencies one at a time and compare before-and-after closures, then write down the minimal cover. For the two examples in this lecture: over ${A, B, C, D}$ the keys are $D$ and $A C$ ; over ${W, X, Y, Z}$ the keys are $W$ and $Y$ . Relational algebra needs no quiz preparation — there are no questions on it.

Key Industry Applications

Real-world: data is described as the new oil — the organizations and countries that manage it well (social media, airlines, supply chains, online banking) will prosper as those that owned oil did in the last century.
Real-world: the entire fields of data science and AI rest on database system engineering — correct storage is the precondition for correct predictions.
Real-world: relational database systems fit confined, predictable environments; as data grows in velocity, volume, and variety — with heuristic correctness acceptable and replication needed for availability — organizations move to non-relational systems such as MongoDB, Cassandra, and Neo4j.
Real-world: the normalization skills in this section — closures, minimal covers, 3NF synthesis — are the mathematical certainty behind relational schema design that ER conversion cannot provide.
Real-world: relational algebra is the mathematical basis underneath SQL, and query optimization relies on rewriting that SQL itself cannot express; the EMPLOYEE practice sheet mirrors the kind of HR table used in real systems.
Real-world: the lab connects Python (with a framework) or Node.js to MySQL, covering the store-retrieve-serve pipeline end to end.

Where this lecture shows up in practice. Every schema design decision in a production system — an airline's booking schema, a bank's ledger, a hospital's patient records — is a decision about functional dependencies and normal forms: which attributes are keys, which dependencies to enforce, and whether a join will fabricate rows. Closure and minimal-cover reasoning is the audit tool for that decision. And every SQL query the lab writes is a relational algebra expression in disguise: the optimizer rewrites it algebraically before execution, which is why the mathematical form in this lecture is not a theory exercise but the engine room of real database performance.

DDA Lecture 6 notes · Minimal Covers, 3NF Synthesis, and Relational Algebra

Database Design and Applications· postgraduate· 2026-08-06

Sections Breakdown

16.1 The Course Promise: Storing, Retrieving, and Serving Data

The three course promises, the hostel-room and harmonium-synthesizer analogies, and the format and rules of Quiz 1.

26.2 Closure, Redundancy, and Minimal Covers

Attribute-set closure, hiding-dependency redundancy tests, canonical covers, and the 3NF synthesis algorithm.

36.3 Worked Example 1: A Minimal Cover over {A, B, C, D}

Finding candidate keys, testing every dependency for redundancy, and synthesizing the 3NF schema.

46.4 Worked Example 2: Minimal Cover and 3NF Decomposition

A second full pass over {W, X, Y, Z} with left-side redundancy checks and two valid 3NF decompositions.

56.5 Relational Algebra: The Mathematical Foundation of SQL

Select, project, rename, union, and the set operations, with four worked examples on the EMPLOYEE schema.

6Exam Guidance Summary

Quiz 1 logistics, coverage, and the problem-solving method the quiz expects.

7Key Industry Applications

Where closures, minimal covers, and relational algebra show up in real database systems.

Postgraduate students in database systems

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

The Course Promise: Storing, Retrieving, and Serving Data

Must-know: The course promise: store data well, retrieve data well, retrieve concurrently; normalization hypotheses hold only under implicit assumptions (dependable network, limited scale); awareness -> education -> skill.

Top pitfall: Treating 'third normal form is better than second normal form' as an absolute: it is a hypothesis that depends on implicit assumptions about network, availability, and scale.

Self-check: Quiz 1 carries what weightage, how many questions, and is it open book?

Connects to: closure, redundancy, and minimal covers, the worked example over {A, B, C, D}, the worked example over {W, X, Y, Z}.

Closure, Redundancy, and Minimal Covers

Must-know: Closure X+ is the set of all attributes functionally determined by X, computed by repeatedly firing FDs whose left side is already reached; X->Y is redundant iff Y is still in X+ after hiding it; canonical covers are not unique but all are equivalent.

$X^{+} = {A \in U ∣ X \to A derivable from F}$

Top pitfall: Stopping the closure loop too early: a newly added attribute can unlock further dependencies, so the pass must continue until nothing changes; also, any change (addition or reduction) in the before/after closures means the hidden item is not redundant.

Self-check: Why does hiding one dependency only require recomputing the closure of its own left side?

Connects to: the worked example over {A, B, C, D}, the worked example over {W, X, Y, Z}.

Worked Example 1: A Minimal Cover over {A, B, C, D}

Must-know: For F = {A->B, D->ABC, C->B, AC->D}: candidate keys D and AC, prime attributes A, C, D; minimal cover {A->B, D->A, D->C, C->B, AC->D} (only D->B dropped); 3NF synthesis gives (A,C,D), (A,B), (C,B).

$F = {A \to B, D \to A B C, C \to B, A C \to D}$

Top pitfall: Stopping at the first superkey found: AC is also a candidate key (AC+ = ABCD), so prime attributes include A and C; also, any change in before/after closures (addition or reduction) means the hidden item is not redundant.

Self-check: Why is D->B redundant in this set while D->A is not?

Connects to: closure, redundancy, and minimal covers, the worked example over {W, X, Y, Z}.

Worked Example 2: Minimal Cover and 3NF Decomposition

Must-know: For F = {X->W, W->XY, WZ->Y, Y->XZ}: candidate keys are W and Y (WZ is only a superkey); minimal cover {X->W, W->XY, Y->XZ} (WZ->Y is redundant since W->XY already supplies Y); 3NF synthesis gives (X,W), (W,X,Y), (Y,X,Z) with no extra key relation.

$F = {X \to W, W \to X Y, W Z \to Y, Y \to X Z}$

Top pitfall: Calling the first superkey found the candidate key: W and Y are the keys, WZ is not minimal; also, a cover that drops W->XY loses it from the closure, so always re-run the whole pass after every change (restart rule).

Self-check: Why is WZ->Y redundant in this set?

Connects to: closure, redundancy, and minimal covers, the worked example over {A, B, C, D}.

Relational Algebra: The Mathematical Foundation of SQL

Must-know: Select (sigma) filters rows by predicate and keeps all attributes; project (pi) keeps only listed columns and eliminates duplicates; select-then-project is correct, project-then-select may lose the predicate column; union requires union-compatible relations (same degree, same domains) and the result has no duplicates.

$π_{ssn} (σ_{dno = 5} (EMPLOYEE)) \cup π_{superssn} (σ_{dno = 5} (EMPLOYEE))$

Top pitfall: Projecting first and then selecting on a dropped column makes the predicate unanswerable; writing select and project as commutative; merging two columns into a one-column answer.

Self-check: Why is select-before-project the correct order in the names-of-department-5 query?

Connects to: the course promise and Quiz 1, closure, redundancy, and minimal covers.

Exam Guidance Summary

Must-know: Quiz 1: 25 MCQs, most correct answer, no negative marking, 5% weightage, one submission, open book, covers normalization only; the answer keys D/AC and W/Y summarize the two worked key-finding examples.

Top pitfall: Overlooking key minimality: the first superkey found (WZ, or D alone) may not be the full set of candidate keys.

Self-check: What is the exact submission rule for Quiz 1?

Connects to: the course promise and Quiz 1, the worked example over {A, B, C, D}, the worked example over {W, X, Y, Z}, relational algebra.

Key Industry Applications

Must-know: Real systems (airlines, banking, supply chains) run on data; normalization and closure reasoning are the audit tools of schema design; every SQL query is a relational algebra expression the optimizer rewrites.

Connects to: the course promise and Quiz 1, closure, redundancy, and minimal covers, relational algebra.

Previous LectureLecture 05 · Database Normalization: Closure, Minimal Cover, and the 3NF Synthesis Algorithm

Next LectureLecture 07 · Relational Algebra: Select, Project, and Joins

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

6.1 The Course Promise: Storing, Retrieving, and Serving Data

6.1.1 Why This Course Exists

6.1.2 Awareness, Education, and Skill

6.1.3 The Hypothesis Behind the Course

6.1.4 The End-to-End Picture: Where Databases Sit

6.1.5 Quiz 1: Format and Rules

6.2 Closure, Redundancy, and Minimal Covers

6.2.1 The Closure of an Attribute Set

6.2.2 When a Whole Functional Dependency Is Redundant

6.2.3 When an Attribute on the Left Side Is Redundant

6.2.4 Canonical Covers Are Not Unique

6.2.5 From a Minimal Cover to Third Normal Form

6.3 Worked Example 1: A Minimal Cover over {A, B, C, D}

6.3.1 The Setup

6.3.2 Finding a Candidate Key

6.3.3 Checking Each Functional Dependency

6.3.4 Checking the Left Side of AC → D

6.3.5 The Minimal Cover and Questions

6.4 Worked Example 2: Minimal Cover and 3NF Decomposition

6.4.1 The Setup

6.4.2 The Candidate Key and the First Checks

6.4.3 Checking the Left Side of WZ → Y

6.4.4 Questions and Answers

6.4.5 The Final Minimal Cover

6.4.6 The 3NF Decomposition

6.5 Relational Algebra: The Mathematical Foundation of SQL

6.5.1 Why Relational Algebra Exists

6.5.2 The Operations

6.5.3 Select and Project Are Not the SQL Select

6.5.4 Worked Examples on the EMPLOYEE Schema

6.5.5 Questions and Answers

6.5.6 Exam Notes and Next Steps

Exam Guidance Summary

Key Industry Applications

DDA Lecture 6 notes · Minimal Covers, 3NF Synthesis, and Relational Algebra

Sections Breakdown

Exam Revision Notes

The Course Promise: Storing, Retrieving, and Serving Data

Closure, Redundancy, and Minimal Covers

Worked Example 1: A Minimal Cover over {A, B, C, D}

Worked Example 2: Minimal Cover and 3NF Decomposition

Relational Algebra: The Mathematical Foundation of SQL

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat