Candidate Keys, ER-to-Relational Mapping, and Normalization Revision

This session is a full revision pass driven by quiz questions and an old question paper. It covers how a primary key is actually chosen, how to read the "one" and "many" sides of an ER diagram, how to map a one-to-many relationship with total participation into relations, why we normalize at all, the exact definitions of 1NF, 2NF, 3NF and BCNF, how to find candidate keys using closure, how to check FD-set equivalence, and how to answer relational-algebra and SQL questions. Everything is interleaved with extended student Q&A, because the biggest confusions of the course live here.

The session moves in the professor's order: the three quiz questions open the discussion, the old paper's questions drive the rest, and the exam guidance at the end collects what is being fixed in the answer keys and what is expected of you in the exam hall.

9.1 Choosing a Primary Key from Candidate Keys

9.1.1 The Quiz Question and Its Four Options

Both questions ask the same thing — "why is option 1 also right?" — so they collapse into one canonical Q&A: any criterion, including none at all, is legitimate, because the choice belongs to the administrator.

9.1.2 What This Tells You About Keys

Two definitional facts make the discussion sharp. A candidate key (a minimal set of attributes that uniquely identifies every tuple; there can be many in a relation) and a primary key (the one candidate key the database administrator picks out of that set) differ only in the act of picking. Because every candidate key already satisfies the job of unique identification, any of them can be chosen as the primary key — the "ability to uniquely identify tuples without redundancy" is not a distinguishing criterion among candidate keys; it is the property they all share. Similarly, the number of attributes, the alphabetical order of names, and the data type are all acceptable tie-breaking preferences, but none of them is a rule.

The deep point the professor wants preserved: picking a primary key is an administrative decision, and it may be one that no third party can justify. In real databases, the choice is guided by practical needs — smallest key, stable values, fastest lookups — but formally, anything in the candidate-key set works.

Visual intuition: picture a shelf of candidate keys — A alone, CD, E, BC — each with a tag saying "uniquely identifies every row." The primary key is just the one the administrator lifts off the shelf. The remaining candidates do not stop being keys; they remain usable for indexing, joins, and unique constraints.

Real-world & domain connection: Primary-key selection is a daily decision in database administration. When a schema offers several natural keys (employee ID, email, Aadhaar-style national ID, phone), a DBA picks one — often the smallest, most stable, and fastest to index — and design tools and textbooks treat the candidates as equal alternatives precisely because the choice is administrative. A poorly chosen primary key (a mutable phone number, a huge string) creates real costs: slower indexes, cascade-update chains, and brittle foreign keys. The professor ties this to the rest of the course: candidate keys, super keys, and prime attributes return in every normalization definition from 2NF to BCNF.

9.2 Reading a "One-to-Many" Relationship

9.2.1 The Diagram-Reading Rule

The rule, stated simply: the entity on the side marked "one" can be related to at most one entity on the other side; the entity on the side marked "many" can be related to many entities on the other side. The "one" is an "at most one" — an entity on the one side may even be related to zero entities on the other side. The "many" side means "at most many," so zero is allowed there too.

The professor draws two "bags" (entity sets) X and Y connected by a relationship. If the diagram is read as "X to Y is one-to-many," then X is the one side: any entity in the X bag has a relationship with at most one entity in the Y bag (possibly none). Meanwhile, any entity in the Y bag can have a relationship with many entities in the X bag. In the ER diagram, the "one" label goes on one side of the relationship diamond and the "many" label on the other — one on this side, many on the other side.

Total participation changes the minimum, not the maximum: when X has total participation in a relationship, every entity of X must participate — it is impossible for an X entity to sit out of the relationship. In the diagrams used here, total participation is shown with a double line next to the entity.

9.2.2 The Bag Example: Students and Mentors

The example that made this concrete: a bag of 85 students and a bag of 20 mentors, with a relationship "student is mentored by mentor." Reading the one-to-many side:

• Each student can have at most one mentor. A student with no mentor is fine — "at most one" allows zero.
• Each mentor can have many students — say, several of the 85 students.

So "student to mentor is one-to-many" means a student has at most one mentor, and a mentor has many students. The same example with different roles: in a student–advisor relationship, one student can have at most one advisor, while an advisor can advise many students.

9.2.3 The Great "One-to-Many vs Many-to-One" Debate

This is the largest and most instructive Q&A of the session, because the students pushed back repeatedly and the professor re-explained from several angles. The full arc matters: question → initial explanation → student disagreement → correction → re-explanation → final agreed reading.

The student spotted that the professor's first drawing was reversed — many X's were mapping to a single Y, which makes the X side the many side. The professor accepted the correction on the spot and re-explained with the student–advisor example.

Here the professor reaches for the school-mathematics picture — a function from a domain bag to a co-domain bag — to explain why the direction matters: read each bag's own constraint, then name the relationship from the pair of constraints.

Note the professor's move at this point: separate the concept (which everyone now agrees on) from the name. When a second student reported that the recorded material also reads "one-to-many" as "at most one," the professor deferred checking the textbook screenshot but committed to the concept: the label "1" means "at most one."

The settled reading: "X to Y" means X is related to Y at most one-to-many — read the pair of constraints on each side, never just the first word.

Comparison — the three cardinality ratios at a glance. The same two bags, X and Y, under each ratio:

The reference text uses the same reading with l..h bounds: a 1..1 on an edge means "exactly one," a 0..* means "zero or more." The textbook even warns explicitly that the 0..* on one edge is easy to misread as the reverse — exactly the trap the class hit.

When to pick which: choose the ratio by the maximum on each side: a max of 1 on one side and unlimited on the other gives 1:N; the side with max 1 is the "one" side, whatever you decide to call the pair.

9.2.4 What Was Resolved

The professor first drew the diagram, a student spotted that it was drawn the wrong way around, and the professor accepted the correction on the spot — an honest error-correction moment that is itself worth keeping. The settled reading of a diagram marked "1" on the Y side and "many" on the X side: many X's connect to a single Y; each individual X connects to at most one Y. The label "one-to-many" versus "many-to-one" depends on which entity you start from, and the professor explicitly tells students not to lose marks over the naming — the representation of which side is "1" (at most one) and which side is "many" is the part that must be right.

Two mental models are worth holding together:

• From the one side: the entity has at most one relationship (zero allowed).
• From the many side: the entity may have many relationships, and every entity in a total participation set must have at least one.

Real-world & domain connection: Cardinality reading is the skill behind every real schema. A bank that says "a branch belongs to exactly one bank" is a 1:N with total participation on the branch side; a college's "each student has one advisor" is a 1:N with total participation on the student side. Misreading a side means modeling "advisor advises many students" backwards — an error that surfaces later as wrong foreign keys and wrong queries. Tools that generate diagrams, and the (min, max) notation covered later in this session, both encode exactly these per-side constraints.

9.3 Mapping a Binary One-to-Many Relationship with Total Participation

9.3.1 The Quiz Question

9.3.2 The Two-Step Construction

The professor works the mapping in two steps, and the second step is the teaching point.

Step 1 — the separate association relation. Build the relationship relation, call it X_Y. It holds the key of X and the key of Y — both of them foreign keys pointing back to their own entity relations (assuming the relationship carries no attributes of its own). This is option B: a new association relation whose attributes are the primary keys of X and Y as foreign keys. This relation is always correct as an intermediate step.

Step 2 — the merge. Because X has total participation, every entity of X appears in the relationship X_Y. The set of X-entities and the set of X-entities inside X_Y are the same set. So merging the X relation with the X_Y relation costs nothing and removes a join: the combined relation contains the key of X, the key of Y (as a foreign key), and the other attributes of X. Because each X has at most one Y, the key of X still uniquely identifies every row, so the primary key of the merged relation is X's key and Y's key enters as a foreign key. The Y relation stays as it is: key of Y plus its own attributes.

The key claim, reconciled with the standard mapping: the merged relation's primary key is X's key. The check is dimensional: each X tuple pairs with at most one Y tuple (the "one" side), so X's key alone still tells every row apart — no two rows share an X key. Y's key is a foreign key: it references Y, and the same Y may appear in many rows.

The general rule the professor states: whenever there is a one-to-many relationship and the one side has total participation, join those relations, because whatever entities exist on the one side also exist in the relationship — the merge is lossless and shrinks the schema (three relations become two).

9.3.3 The Null-Value Worry, Resolved

The null worry is real — but only on the other side. Merging the relationship into X is safe precisely because X's total participation means the relationship relation contains every X; the merged table can never hold an X with a blank. Y's key may hold nulls in some rows (a department row for an entity that is not yet tied to any Y — impossible here because of total participation, but possible in general). This is why the general mapping keeps the merge for the total-participation side only.

The last exchange ties the professor's merge to the textbook rule: the standard mapping for 1:N places the primary key of the one side as a foreign key inside the many-side relation. The professor's merged design is the same idea expressed as a merge into the one-side relation — the choice is which relation hosts the foreign key, and total participation decides which hosting is null-free.

Comparison — Design B versus Design C.

When to pick which: use C when the one side has total participation (the professor's exam rule); otherwise use B — unless there is total participation, "there is always a chance of null entries."

9.3.4 The Settled Answer

Both B and C are correct, and C is the most accurate answer for this course's treatment of the ER portion: B is the un-merged intermediate step (always safe, three relations), while C is the final, least-redundant design (two relations), justified specifically because X's total participation guarantees no nulls on the X side and so allows a clean merge. The professor also restates the general principle for exam use: a new relation is created whenever we merge, decompose, or join — the merge is mostly for the total-participation case; otherwise, unless there is total participation, there is always a chance of null entries.

Real-world & domain connection: This mapping decision is made in every database design tool and every hand-drawn schema. A library's "a copy belongs to exactly one book, and every copy must belong to a book" is a total-participation 1:N — merge the copy's book foreign key directly into the copy relation (which is, of course, how it is always drawn in practice). A hospital's "a patient may or may not have a primary doctor" is partial participation — a nullable doctor foreign key, or a separate linking relation, is the honest model. Reading total participation on the diagram and choosing B or C accordingly is the entire skill.

9.4 Why We Normalize: The Goals of a Good Database Design Schema

9.4.1 The Four Characteristics

After building a relational schema from an ER diagram, the next question is whether that schema is good. The professor lists the characteristics of a good database design schema; the point of the entire normalization machinery is to achieve them:

1. Proper semantics. Every relation and every attribute must mean something clear. A relation R with attributes A, B, C, D, E "does not make any sense for anyone else apart from you" — even if you wrote the meaning in the schema description. The application development team and the maintenance team may be different people, so the schema itself must carry meaning: give A its real attribute name, B its real attribute name. This is the first part of a good design.
2. Least amount of redundancy, and no anomalies. Redundancy is not a space problem — "20, 25, 30 years ago people might say okay, the space is the issue" — it is a correctness problem. Whenever an attribute value repeats, an update must propagate everywhere the value repeats, and any missed spot creates discrepancy.
3. No spurious tuples — lossless join. As you move from one normal form to the next, you decompose relations and later join them back. If the join manufactures wrong tuples (spurious tuples), the database again contains wrong information. Whenever a relation is decomposed, the join must be lossless.
4. Scalable, and long lasting. The professor closes the list with the goals a good schema must survive by: it must scale as data and users grow, and it must last — a schema that must be redesigned every few years has failed its primary purpose. The first three characteristics make the schema correct today; these last two make it survive tomorrow.

The first three characteristics are named directly in the session; the professor then adds "scalable, and long lasting" as the goals that round out a good schema.

9.4.2 Redundancy Creates Uncertainty: The Email-ID Example

The concrete argument: suppose there is a functional dependency between email ID and name, and the name value repeats across many tuples. If the name changes at one place, it must change at every place where the email ID appears. If you retrieve the data later and 17 of 20 occurrences say one thing while 3 say another, there is a discrepancy — and a discrepancy creates uncertainty in the database: "which is the correct answer, the one the 17 are saying or the one the 3 are saying?" Redundancy causes uncertainty, and uncertainty does not allow you to take a decision. This is the core reason normalization exists: to remove redundancy so that a single fact is stored in a single place.

The professor's chain is the lecture's core argument: redundancy → discrepancy → uncertainty → inability to decide. Each normal form removes one source of redundancy, so a single fact lives in a single place.

9.4.3 Denormalization in Real Life (and the NoSQL Link)

The professor adds an important real-world caveat: in real life, people denormalize relations. BCNF is a beautiful, near-redundancy-free schema, "an absolutely impeccably nice relational schema" — but maintaining it means many relations, and so many joins. Joins cost storage and retrieval overhead. So some schemas deliberately live with a little redundancy and a few null entries to make retrieval faster. "In few real life cases we denormalize to second normal form as well." This performance-versus-redundancy trade-off is flagged as essential for the later part of the course, when NoSQL is discussed — "just mind you, this discussion ... about NoSQL ... the performance aspect is very important."

Real-world & domain connection: The normalization/denormalization trade-off is an everyday decision in real database design. E-commerce order tables are routinely denormalized (storing the product name alongside the order line) so that product renames don't trigger historical order rewrites; analytics warehouses store wide, duplicated facts on purpose because joins at petabyte scale are unaffordable. The professor explicitly ties the decision to NoSQL: document stores like MongoDB and key-value stores sacrifice normalization for performance by design. Knowing what normalization costs is what makes the trade-off a decision rather than a violation.

9.4.4 First Normal Form: Atomic Cells

First normal form is the base: every cell of every tuple holds a single, unique entry. The professor's argument is practical, not formal. Suppose one cell holds three phone numbers separated by commas: "V has three entries with a comma here." To find a person's phone number you cannot simply read the cell — you must write an algorithm that searches inside the cell, and that takes time and computation power. 1NF says each cell carries exactly one value, so retrieval stays simple. This is the foundation the other normal forms build on.

Real-world & domain connection: Every one of these goals shows up as a real failure mode. Proper semantics: column names like col1 in a production schema force every future query to be reverse-engineered. Redundancy: a customer address stored in five tables drifts apart — the classic data-quality complaint of every CRM team. Spurious tuples: a poorly decomposed schema that joins into phantom rows has caused countless wrong BI reports. And the atomic-cell rule of 1NF is why phone-number, tag, and "multi-value" columns are routinely split into child tables in production designs.

9.5 The Normal-Form Definitions at a Glance

9.5.1 The Key Vocabulary, Revisited

• A super key is a set of attributes that uniquely identifies every tuple.
• A key is a minimal super key — a minimal set of attributes that uniquely identifies every tuple.
• If more than one minimal set exists, they are candidate keys; one of them is chosen as the primary key.
• A prime attribute is an attribute that is part of any candidate key.

The standard reference formulation agrees, and adds the naming: if a relation has more than one candidate key, one is arbitrarily designated the primary key and the rest are called secondary keys. An attribute is prime if it is a member of some candidate key — membership in the primary key alone is not enough.

9.5.2 Second Normal Form: No Partial Dependencies

A functional dependency (FD) $\alpha \to \beta$ says the values of the attribute set $\alpha$ determine the values of the attribute set $\beta$; both sides may be sets, and $\beta$ may be a single attribute. An FD is a full functional dependency when the left side is the complete candidate key — the left side cannot be shrunk. A partial dependency is an FD $\alpha \to \beta$ where $\alpha$ is a proper subset of a candidate key. If, hypothetically, the candidate key is ABC, then an FD from AB (a proper subset of the key) to some non-prime attribute is not allowed — that is exactly what violates 2NF.

The reference text makes the same point with the classic EMP_PROJ example: key $\{Ssn,Pnumber\}$, with $Ssn\to Ename$ — Ename is determined by part of the key, so it is partially dependent and the relation fails 2NF. Note the reference's historical definition is stated against the primary key; the professor's version — every candidate key — is the general definition, and the quiz question below makes that generalization explicit and examinable.

9.5.3 Third Normal Form: No Transitive Dependencies

3NF adds a stricter rule: a transitive dependency $\alpha \to \beta$ — the professor's phrasing: "from alpha to beta is there, if alpha is not a super key and beta is not a prime attribute" — is not allowed. In the informal framing used in the session: a transitive dependency is a non-prime attribute determining a non-prime attribute. If the middle attribute (or the target) happens to be a candidate key or a prime attribute, the chain is not a transitive dependency in the violating sense.

Why transitive dependencies are banned: they carry redundancy. When the non-prime attribute repeats, anything it determines repeats with it, and any change must be propagated everywhere — the same redundancy-uncertainty argument as before. 3NF "is an even stricter form" that refuses this too.

9.5.4 BCNF: The Left Side Must Be a Super Key

BCNF is the sharpest rule: for every FD $\alpha \to \beta$, $\alpha$ must be a super key — no exceptions, no carve-outs for prime attributes on the right. So BCNF is strictly stronger than 3NF: 3NF allows $\alpha \to \beta$ when $\alpha$ is not a super key provided $\beta$ is prime; BCNF forbids it regardless.

Comparison — 2NF, 3NF, BCNF at a glance.

When to pick which: the exam's rule of thumb — check BCNF first via left-side closures (fast), and use 3NF/2NF only when the question asks specifically; a schema in BCNF automatically satisfies the others.

9.5.5 The 2NF Definition Question from the Quiz

A follow-up quiz question tested the wording of the 2NF definition.

Real-world & domain connection: These definitions are not just exam material — they are the acceptance criteria of every schema review. A designer who can name the normal form of a table, and the specific FD that violates it, has found the exact redundancy that will later produce an update anomaly in production. Tools that suggest decompositions (and every textbook algorithm for 3NF and BCNF synthesis) are built on the three conditions above; knowing them by heart means the tool's output is never a black box.

9.6 Worked Example: Finding Candidate Keys and Checking 2NF, 3NF, BCNF

9.6.1 The Given Functional Dependencies

The third quiz question gives a relation and this set of functional dependencies (confirmed in the discussion):

$$A\to B,A\to C,CD\to E,B\to D,E\to A$$

The relation's attributes are exactly $\{A,B,C,D,E\}$. The question asks which statement about normalization is correct. The way to answer: find all candidate keys, then check each normal form's condition FD by FD.

9.6.2 Finding the Candidate Keys with Closure

The professor computes four closures:

$$A^{+}=\{A,B,C,D,E\}$$

Start with A. From $A\to B$ and $A\to C$ add B and C; from $B\to D$ add D; from $CD\to E$ add E. Since $A^{+}$ covers everything, A is a candidate key.

$$C{D}^{+}=\{C,D,E,A,B\}$$

Start with C and D. From $CD\to E$ add E; from $E\to A$ add A; from $A\to B$ and $A\to C$ add B and C. CD is a candidate key.

$$E^{+}=\{E,A,B,C,D\}$$

Start with E. From $E\to A$ add A; from $A\to B$ and $A\to C$ add B and C; from $B\to D$ add D. E is a candidate key.

$$B{C}^{+}=\{B,C,D,E,A\}$$

Start with B and C. From $B\to D$ add D; from $CD\to E$ add E; from $E\to A$ add A. BC is a candidate key.

That is exactly four candidate keys: A, CD, E, BC. The single attributes B, C, D each close to themselves or less (B closes to $\{B,D\}$ and no further), and BD closes only to $\{B,D\}$ because $CD\to E$ needs C — so no other minimal combination exists. Because every attribute appears in at least one candidate key, every attribute of the relation is prime.

9.6.3 Checking 2NF

A partial dependency needs a proper subset of a candidate key on the left and a non-prime attribute on the right. Look at $B\to D$: B is a proper subset of the candidate key BC — the shape of a partial dependency. But D is a prime attribute (D belongs to the candidate key CD). The second condition fails, so $B\to D$ does not violate 2NF. No other FD has a left side that is a proper subset of a candidate key. The relation is in 2NF.

9.6.4 Checking 3NF

For 3NF, each FD $\alpha \to \beta$ must have $\alpha$ as a super key or $\beta$ prime. Check one by one:

• $A\to B$: A is a candidate key, so a super key — fine.
• $A\to C$: same — fine.
• $CD\to E$: CD is a candidate key — fine.
• $B\to D$: B is not a super key, but D is a prime attribute — fine.
• $E\to A$: E is a candidate key — fine.

No FD violates 3NF, so the relation is in 3NF. (For completeness: it is not in BCNF, because BCNF demands the left side be a super key with no exception, and $B\to D$ fails that demand.)

9.6.5 The Quiz Options Were Flawed — and the Answer Key Is Being Fixed

The professor's verdict: every option of this question needs revision; the option that claims 2NF is the most appropriate answer as written, and the answer key will be updated so that no one loses marks over the flawed wording.

The student's proposed chain fails twice. First, there is no FD $C\to E$ — the set has $CD\to E$, and CD is itself a candidate key. Second, even the existing chain $E\to A$ has E as a candidate key, so its left side is a super key — under 3NF, an FD from a super key is always fine. The student's reading is a textbook example of the trap: calling any multi-hop FD chain "transitive" without checking the status of the attributes in the middle.

Real-world & domain connection: This exact exercise — FD set in hand, keys found by closure, normal form verified FD by FD — is the professional's route to deciding whether a schema needs decomposition. Every real schema review starts here: write the FDs, compute the keys, name the violating FD, fix it. The BCNF shortcut shown in section 9.10 is the same skill optimized for exam speed.

9.7 Why Check Every Candidate Key? Closure, Armstrong's Rules, Minimal Cover

9.7.1 The Question That Started It

The idea, unpacked. From the five written FDs, Armstrong's rules derive plenty of FDs that are never written down — and all of them are real constraints. In the worked example: $A\to B$ and $B\to D$ give $A\to D$ by transitivity; $E\to A$ and $A\to C$ give $E\to C$; and the fact that BC closes to the whole relation means $BC\to A,BC\to D,BC\to E$ all hold. None of these appears in the written set, yet every one of them is a constraint the database must respect. If the schema designer only planned around the written five, the schema could silently violate its own data's real structure — which is why "check every candidate key" is the fundamental rule for detecting lost dependencies during decomposition.

9.7.2 The Search Is Finite

The search is finite because of a simple pruning rule: once a set is a candidate key, every superset is only a super key — never a candidate key. In the quiz example: A and E are candidate keys, so all 15 supersets containing A or E are eliminated immediately. Among the remaining singles $\{B,C,D\}$, only pairs matter: BC and CD are keys; BD fails (its closure stops at $\{B,D\}$); any triple containing a pair that failed cannot be minimal... and in fact every triple contains a key or BC/CD anyway. Total sets examined: five singles and three pairs — not "unlimited."

This is the practical algorithm for a small relation: test every single attribute, then every minimal pair, and so on; stop early because any candidate key you find kills all its supersets as candidate-key candidates (they remain super keys only).

Real-world & domain connection: "Lost dependency" is not an abstract phrase — it is the reason decompositions produce schemas that accept data the original constraints forbade. Real design tools compute the closure and minimal cover silently; when a tool warns "FD lost in decomposition," it is running exactly the checks the professor insists students run by hand. The same machinery detects whether two FD sets describe the same constraints — the subject of section 9.11's old-paper question.

9.8 Old Paper Question 1: From an ER Diagram to a Relational Schema

9.8.1 The Setup and the Conversion

The entity relations come first: book is one entity, author is one entity, periodical/paper is a separate relation, user is an entity — each with its attributes. Then the relationships: "has" between book and author is one-to-n (1:N), and there is no total participation, so we keep "has" as a separate relationship schema. The same pattern repeats for each relationship in the diagram. The professor's compact rule: for a 1:N relationship without total participation, keep the relationship as its own relation; the merge into the one-side's relation is reserved for the total-participation case, because without total participation there is always a chance of null entries.

The professor's confidence check: given an ER diagram, you should be able to identify the entities, identify the attributes, identify the relationships, identify the keys, and convert them into a relational schema with the foreign keys. "In the ER diagram portion you must go full marks."

9.8.2 Reading Cardinality on the Bank–Branch Example

To make the reading of cardinality concrete, the professor reads a bank–branch relationship: a bank can be associated with many bank branches, while a bank branch can be related to at most one bank. Both sides have total participation here: every bank must have at least one bank branch, and every bank branch must belong to a bank. Reading each side: "every bank can have at most many bank branches" (the many side, with the minimum forced to one by total participation) and "every bank branch can have at least one and at most one bank" (the one side).

The professor distinguishes the two notations explicitly: the "1 / N" side-label style read here, and the (min, max) style to be covered next — they encode the same facts (per-side minimums and maximums) in different visual forms, and the next section shows how to read the (min, max) form.

9.8.3 Practice and the Standing Offer

The professor pushes hard on practice: "Are you 50, 60, 70 percent confident that you can represent that? Practice still needs to be done." There is no substitute for practice — "I can't practice for you." Students can email their attempts at the three practice questions and get feedback ("is my practice correct or not — do I need something more or less?"). There is also a standing offer for an optional one-on-one practice session: write a mail to reserve half an hour, planned midweek (Monday or Tuesday), organized by a student volunteer, with the professor available to solve and discuss questions live. A commitment from earlier weeks is repeated: to show what a database looks like inside an entire application end to end.

Real-world & domain connection: This conversion is the first step of every database project — the ER diagram is the blueprint, and the relational schema is the build. Design tools automate it, but their output is only as good as the reading of cardinality and participation, which is exactly what this section rehearses. Bank–branch modeling is a canonical real example: banks hold many branches; branches belong to exactly one bank; total participation on both sides is a business rule, not a choice.

9.9 Reading (min, max) Cardinality Notation

9.9.1 The Notation and the Textbook

A different ER notation writes a (min, max) pair on each entity's side of a relationship edge. The textbook — the professor explicitly names it: "what is written in the book is Navathe also" — covers it on page 83 (bottom) and shows a diagram on page 85. The professor's reading rule, as he eventually settled it: the (min, max) written on an entity's side describes how that entity participates in the relationship — the minimum and maximum number of relationship instances that each entity of that set can appear in (equivalently, for a binary relationship, how many entities on the other side it can connect to).

A caution from the reference is worth keeping: some other notations — particularly UML — place the (min, max) pair on the opposite side of the edge from this book's convention. So a screenshot from another source can genuinely look reversed; the rule "the label describes the entity it is written beside" only holds within one notation's convention. This is precisely why the professor's first instinct (reading the labels as describing the other side) must be corrected.

9.9.2 The Department–Employee Example, Including the Professor's Own Confusion

The example on the page is a WORKS_FOR-style relationship between departments and employees, with (1,1) on the department side and (2,30) on the employee side. Reading it strictly from the notation:

• A department participates in the relationship between 1 and 1 times — every department is rated (1,1) in WORKS_FOR.
• An employee participates between 2 and 30 times — "an employee can be related to minimal two and maximal 30 departments, that is how we read it across."

The professor is openly uncertain at first and corrects himself on the fly: he starts by reading the labels as if they described the other side (a department has min 1, max 1 employees; a department has min 2, max 30 employees), then stops: "it should be the opposite one ... if I read the diagram on page 85 as it is, without worrying about real life, a department can have minimal 1 and maximal 1; an employee can be related to 2 and maximal 30."

The (min, max) assignment — (1,1) on the department side and (2,30) on the employee side — and the side-to-side reading rule are confirmed by the reference's definition: the label describes the participation of the entity on whose side it is written, and this is what the professor commits to. The professor's mid-answer self-correction is the lesson in miniature: reading "a department has 1 to 1 employees" describes the employee's participation, not the department's.

Comparison — the two notations, side by side.

The two notations encode the same facts: "(1,1)" = one-side label plus double line; "(0,N)" = many-side label without double line. The professor's point stands: in this notation read from the side the label is written on; in the other, read the side labels similarly — never mix the conventions mid-diagram.

9.9.3 Why It Still Matters, and the Exam Note

The professor is explicit about scope: "you will not get this type of question in your mid-semester or mid-semester makeup — I will not give these questions, so you may not worry about it right now." But: "in case in your real life you come in touch with something like this, you should still be able to read it — that this is related to this side."

Real-world & domain connection: Tools that generate ER diagrams from databases, and standards that exchange schemas between systems, frequently use (min, max) or l..h bounds (the same rule written as a range). Reading them is a transferable skill: a system integrator meeting a schema in (min, max) form must know which side a constraint belongs to, or every cardinality is misread. The professor's framing — "in real life you should still be able to read it" — is the actual reason the notation is taught even though it is not exam-tested.

9.10 Old Paper Question 2: Which Functional Dependencies Violate BCNF?

9.10.1 The Shortcut: Only the Left-Hand Side Matters

For BCNF, there is a shortcut that saves most of the work: you do not need to enumerate all candidate keys. BCNF only worries about whether the left-hand side of each FD is a super key (or candidate key). So for each given FD, compute the closure of its left-hand side; if the closure is not the whole relation, that FD violates BCNF; if the closure is the whole relation, it is fine. "I need not even find out in this question all the candidate keys as well."

9.10.2 The Worked Walk-Through

The paper's BCNF question gives FDs whose left-hand sides include B, BF, C, and CH. The discussion names the left sides B, BF, C, and CH and walks the check for CH in full — that walk is the method. The check for CH:

$$C{H}^{+}=\{C,H,B,D,A\}$$

From $CH\to B$ add B; from $B\to CD$ add C and D; and from there the professor notes A and B, C are reachable as well — but E is not: "from CH I cannot find out E." Since $C{H}^{+}$ misses at least one attribute of the relation, CH is not a candidate key and not a super key — the FD with CH on the left violates BCNF. The other left-hand sides (B, BF, C) are super keys, so their FDs pass.

9.10.3 "Determine All the Keys" — the Companion Question

The same paper also asks the inverse task: determine all the keys of a relation. The professor warns about the standard slip — declaring a single attribute a key when only a combination is a key: "you need to be careful of saying 'A is a key, B is a key.'" In this question, AB is a key, AC is a key, and BC is a key; individually, none of A, B, C is a key. And with these as the keys, none of the FDs violates BCNF — every FD's left side is a super key.

The two sub-questions of the paper use different FD sets: the "B, BF, C, CH" walk belongs to the BCNF-violation part, while the "AB, AC, BC" answer belongs to the determine-all-keys part — keep the two readings distinct.

Real-world & domain connection: The left-side closure check is what schema tools run when they tell you a table "violates BCNF — consider decomposing on FD $CH\to B$." It is also why BCNF is the design target in practice: every redundancy traced to an FD with a non-superkey left side is a redundancy the left-side check would have caught. The "determine all keys" skill is the everyday reverse exercise — naming the keys of a real table before judging its normal form.

9.11 Old Paper Question 2(c): Are Two FD Sets Equivalent?

9.11.1 The Method

The question: given two sets of functional dependencies F1 and F2, are they equivalent? Two FD sets are equivalent when every FD in one set can be derived from the other set, and vice versa — i.e., their closures are the same. The concrete check: take each FD of F2, and test whether its right-hand side is reachable from its left-hand side using only the FDs of F1; then repeat in the other direction.

In the paper's example, F2 contains $A\to CD$, and F1 contains $A\to C$ and $A\to D$. The professor checks: "can we find out A to CD from A to C and A to D? Yes — by the union rule, from $A\to C$ and $A\to D$ we derive $A\to CD$." So that FD of F2 is derivable from F1. The other direction fails: F2 also contains $E\to H$ (along with $E\to A$), and F1 contains no H anywhere.

The student's instinct — "there is no H in F1" — is exactly right, but the exam demands it as a derivation argument, not a glance. The one-line proof: "H is not in $F_1$, so no FD of $F_1$ has H on its right side; $E_{F_1}^{+}$ can then never contain H, and $E\to H\notin F_1^{+}$".

9.11.2 The Lesson on Proofs

The real lesson is how to present the proof, not just the one-word answer. The professor's script for any such question, which he says works "very, very well" in such examinations:

1. Write your understanding of the topic — what is equivalence, what is a functional dependency.
2. Write what the question asks — to check whether the sets are equivalent, you must test each FD of one set against the closure of the other.
3. Perform the check and show the specific FD that fails.
4. Conclude with the reason: "not equivalent because of that reason."

"Just by saying 'no' and nothing else" loses the marks that the reasoning earns. The evaluator can then see that you know what equivalence means, what checking equivalence requires, and that you actually checked it. Even when the answer is "no, they are not equivalent," this structure "would have a very heavy weight." The professor's closing warning: mind the time limit — you have that responsibility as well.

Real-world & domain connection: FD-set equivalence is the theory behind schema validation in real projects: when two designers submit FD lists for the same business rules, equivalence checking tells whether they described the same constraints before any decomposition is built. Database tools verify "does this new constraint change the closure?" with exactly the pairwise test worked here. And the four-step answer script is not exam theatre — it is the standard form of a technical report: context, question, method, conclusion.

9.12 Relational Algebra and SQL: Borrowers with No Books Checked Out

9.12.1 The Question and the Relations

The professor flags the wording "checked out" as ambiguous — it could mean "has borrowed nothing" or "has returned nothing." He states the assumption "checked out means nothing is borrowed" and proceeds, since the point is the query-writing technique, not the reading of the question.

9.12.2 The Relational-Algebra Logic

The professor's logical flow: first find the list of all card numbers present in BOOK_LOANS — these borrowers do have books out. Then the borrowers we want are exactly the ones whose card numbers are not in that list. In relational algebra this is a set difference:

$${\pi }_{\text{name}}\left(\text{BORROWER}\right)-{\pi }_{\text{name}}\left(\text{BORROWER}\bowtie \text{BOOK\_LOANS}\right)$$

The professor describes the subtraction of card numbers in words ("find out all the card numbers which are not there") but does not write the relational algebra on screen; the expression above is the same logic written symbolically. It matches the standard treatment: the join $\text{BORROWER}\bowtie \text{BOOK\_LOANS}$ pairs each borrower with every loan they hold; projecting on name removes duplicates, yielding exactly the set of names that appear in BOOK_LOANS; the difference with all borrower names keeps the rest. It may be possible that some borrowers have no entry at all in BOOK_LOANS — those are exactly the ones the difference keeps.

9.12.3 The SQL Version

In SQL, the "card numbers not in the loans list" idea maps directly to NOT IN:

SELECT name
FROM borrower
WHERE card_number NOT IN (SELECT card_number FROM book_loans);

The professor's spoken version walks through the same shape: join borrower and book loans, collect the card numbers that appear in the loans, then select borrower names whose card numbers are not in that set — "I would have to say 'not in': card numbers not in book loans." The point to take away: SQL provides IN and NOT IN as first-class provisions, and the set-difference question is where they shine. The professor adds the honest disclaimer: "I am not 100% sure this is the exact final query, but this is the logical flow" — and reminds students that these queries "take some effort," so similar ones must be practiced.

name
-----
Chetan
Deepa

SELECT name
FROM borrower b
WHERE NOT EXISTS (SELECT 1 FROM book_loans l WHERE l.card_number = b.card_number);

Real-world & domain connection: The query runs against a library management system — borrowers, book copies, book loans — the classic domain where relational algebra's set operations and SQL's NOT IN are used daily. The same shape answers countless business questions: "customers with no orders," "students with no enrollments," "warehouses with no stock movements." Set difference is one of the most reused patterns in real analytics, which is why the professor insists the "NOT IN / set difference" family be practiced.

9.13 How to Structure an Exam Answer (and Exam Logistics)

9.13.1 The Structure That Earns Marks

Consolidated from the equivalence discussion, the answer-writing recipe: open with your understanding of the topic, restate what the question asks, show the check (closure computations, FD-by-FD validation), and close with the reason-based conclusion. This structure signals mastery to the evaluator and carries "very heavy weight" — even for a question whose final answer is "no." Keep the time limit in view while doing it.

9.13.2 Typed or Scanned? The Open Question

Two students raised the same point from different angles — what format must answers take, and what if diagrams are involved — so they form one canonical Q&A: the format (typing only, or typing plus scanning) is not yet settled, and scanning/upload restrictions are a known possibility for drawing-heavy questions. Confirm with the exam team; do not assume.

The movies question in the paper (a second-part question about movies) was flagged but not discussed: the professor notes it "may take some time" and defers it — the FD-set equivalence question (Q2c) was the one he chose to develop fully.

9.13.3 Say Something: The Cost of Fearing Wrong Answers

Early in the session, when few students were answering, the professor paused the content to make a point about participation that applies directly to exam preparation: our education system mostly works on being correct all the time, and sometimes, fearing that an answer might be wrong, we take no action at all. That fear is the real loss. "Even if you consider it as a gambling game — just pick one of them." Saying something matters more than being right: "whatever be your reasoning, that's secondary — but just say something. It is important, trust me, it is important to say something." The reasoning can be fixed later; a mind that freezes in silence cannot be corrected. In a revision session this plays out visibly — the students who spoke up (even with wrong guesses) were the ones who got the deepest explanations, because their wrong answers surfaced the exact confusion the professor could then resolve.

Real-world & domain connection: The four-part script is the standard shape of technical communication beyond the exam: requirements understanding first, problem restatement, method and computations, evidence-based conclusion — the structure of a good bug report, design doc, or incident postmortem. The professor's "say something" lesson is likewise professional: in reviews, standups, and design meetings, the people who voice tentative ideas get the corrections that turn them into experts.

Exam Guidance Summary

• Quiz answer keys are being revised. Question 1 (primary key choice): all four options are correct — any marked option gets the marks. Question 2 (1:N with total participation mapping): B and C are both correct; C is the most accurate. Question 3 (normalization of $A\to B,A\to C,CD\to E,B\to D,E\to A$): the option claiming "in 2NF" is the most appropriate answer, but the reasoning given in the options was wrong (2NF is about partial dependency / full functional dependency, not transitive dependency); updated keys will be released. The 2NF-definition question: "every non-prime attribute is fully functionally dependent on every candidate key" is the correct statement; both "primary key" and "any candidate key" wordings are marked correct.
• ER-diagram questions: go for full marks. Expected of you: identify entities, attributes, relationships, keys, and foreign keys; convert to a relational schema. The exam question papers follow the same style as the old paper practiced here.
• (min, max) cardinality reading will not appear in the mid-semester or the mid-semester makeup — but you should still know how to read it (Navathe pages 83 and 85).
• BCNF questions have a shortcut: check only whether each FD's left-hand side is a candidate key or super key; you do not need all candidate keys.
• "Determine all keys" questions: be careful not to declare a single attribute a key when only a combination is a key.
• FD-set equivalence: equivalence means each FD of one set derivable from the other; prove non-equivalence by naming a specific FD that cannot be derived (e.g., $E\to H$ when F1 has no H).
• Answer-writing strategy: write your understanding of the topic, what the question asks, the check you perform, and the reason-based conclusion — it carries heavy weight with the evaluator; respect the time limit.
• Answer format (typed vs scanned) is not yet known — confirm with the exam team; scanning/uploading is sometimes restricted for exams requiring drawings.
• Practice list: the three old-paper questions (ER-to-relational conversion; BCNF violation check; FD-set equivalence) plus the SQL/relational-algebra query question. Practice is non-negotiable — "there is no substitute for practice." Email attempts for feedback; optional live half-hour practice session midweek by mail.
• SQL/relational-algebra questions take effort — practice queries of the "NOT IN / set difference" family.

Key Industry Applications

• Primary-key selection is a real DBA decision. In practice a database administrator picks the primary key from the candidate set by preference — smallest key, stability, lookup speed — and the choice need not be justifiable to anyone else. This is exactly why database design tools and textbooks treat candidate keys as equal alternatives.
• Denormalization for performance. Real systems often deliberately keep redundancy (sometimes back to 2NF) to avoid expensive joins — the professor explicitly flags this performance trade-off as the bridge to the course's later NoSQL discussion. E-commerce orders and analytics warehouses are everyday examples: duplicated facts are kept where reads must be fast.
• Redundancy breeds uncertainty. The email-ID-to-name example is a small model of real data-quality failures: duplicated facts drift apart (17 copies say one thing, 3 say another), and the database loses trustworthiness. Every CRM and master-data project exists to fight exactly this.
• Library systems (borrowers, book copies, book loans) are the everyday domain for relational algebra set difference and SQL NOT IN queries — and the same shape answers "customers with no orders," "students with no enrollments," and similar business questions.
• Bank–branch modeling shows how cardinality plus total participation reads in a real domain: every bank has branches, every branch belongs to exactly one bank.
• Reading (min, max) notations is a transferable skill: even though not exam-tested, real-world ER diagrams (and tools that generate them) use this notation, so knowing which side a label describes matters beyond the course.
• The exam answer script is the professional report shape. Understanding, restatement, check, conclusion — the same four parts structure design documents, bug reports, and incident write-ups; and the "say something" lesson applies in every technical review.