Module 4 ended with a promise: to put the BiblioRed schema through a formal examination. So far we have designed by understanding the domain, guided by two intuitive principles —"one thing, one place" and "one fact, one row"— that work surprisingly well but that cannot be proved. When two people disagree about whether a table is well designed, intuition does not settle it. Normalization does: it is a body of theory, published by Edgar Codd between 1970 and 1974 and extended afterwards, that turns those principles into definitions you can reason with and, if it comes to that, argue with.

This lesson is the preparation. It does not define a single normal form yet: it builds the vocabulary and the tools you need in order to understand them. Specifically, it answers three questions. First: what harm does redundancy actually do, beyond "it takes up space"? Second: how do you formally write a rule of the kind "the ISBN determines the title"? Third: how do you work out, with a mechanical procedure rather than by eye, what the key of a table is? Without those three things, the normal forms in the next lesson are memorized formulas; with them, they are obvious consequences.

We will spend nearly all our time on material we already know: BiblioRed's old loans spreadsheet, the one we diagnosed in lesson 01-01 and that we have been using ever since as an example of everything you should not do. The time has come to take it apart formally.

1. What normalizing is and what it is not
2. Why redundancy is the problem (and not disk space)
3. The loans sheet as a single relation: loans_sheet
4. The three anomalies, demonstrated one by one
5. Functional dependencies: definition and notation
6. Where dependencies come from: business rules, not sample data
7. Kinds of dependency: full, partial and transitive
8. Trivial dependencies
9. The dependency graph of loans_sheet
10. Armstrong's axioms
11. The derived rules: union, decomposition, pseudotransitivity
12. The closure of a set of attributes (X⁺)
13. Finding the candidate keys with the closure
14. Prime and non-prime attributes
15. What comes next: the normal forms

Normalizing means reorganizing the attributes of a database into tables so that every fact is stored exactly once, and doing it by following a procedure that can be justified.

That definition has two halves and both matter. The first half ("every fact once") is the goal. The second ("a justifiable procedure") is what separates normalization from the intuition of module 4. By the end of this module you will be able to say of a table not just "this is wrong" but "this violates second normal form because copy_code → isbn is a partial dependency on the key (copy_code, loan_date)", which is a sentence that can be verified or refuted.

It is worth being explicit about what normalizing is not, because the following three confusions are very common:

It is not "splitting tables for the sake of splitting them". Some people believe that normalizing means having lots of small tables and that the more the better. That is false. A decomposition is only justified if it removes a specific problematic dependency. Splitting members into members_basic_data and members_contact_data with no dependency motivating it normalizes nothing: it adds a JOIN to every query and removes no redundancy. If you cannot name the dependency you are removing, you are not normalizing.

It is not an end in itself. The goal of the BiblioRed system is to lend books, not to show off a schema in fifth normal form. Normalization is a means to keep the data from contradicting itself. When it stops serving that end —when the cost of the JOINs outweighs the benefit of consistency— you deliberately do the opposite, and that has a name and a method: it is lesson 05-04.

It is not data cleaning. This point is subtle and worth nailing down from the start. In the BiblioRed sheet, "Ken Follet" and "Ken Follett" live side by side, along with an ISBN that is missing a digit. Normalizing the schema does not fix those errors: if you put dirty data into a perfectly normalized schema, you get well-organized dirty data. What normalization does is remove the possibility of the error happening again: when the author's name is written down once and only once in authors, there is no physical way for two different spellings to exist. Cleaning up the history is a separate job done during migration, and we will see it in lesson 05-03.

The second goal is as important as the first and is forgotten more often. A decomposition that removes all redundancy but loses information is a disaster, not an achievement.

Normalization is often justified by saying it "saves space". It is true that it does, and in 1970, with disks measured in extremely expensive megabytes, that was a weighty argument. Today it is not: disk costs almost nothing, and repeating a branch's name forty thousand times costs a few megabytes that nobody worries about.

The real problem with redundancy is that it creates the physical possibility of contradiction.

Think about what it means for a piece of data to be written down twice. It means there are two places on disk asserting something about the world, and the system has no guarantee whatsoever that they assert the same thing. As long as nobody touches them, they agree. The moment an operation updates one and not the other —because the program had a bug, because the connection dropped halfway, because the person at the front desk corrected what they saw on screen without knowing there were more copies— the database comes to contain two incompatible truths. And there is no automatic way of knowing which one is right.

In the BiblioRed sheet this has already happened, and that is why it is such a useful example:

• The branch appears as North in three rows and as north in one. A GROUP BY branch returns two branches where there is one.
• The author appears as Ken Follet in one row and Ken Follett in another. Searching for Follett's loans returns half of them.
• Marta Alsina's email appears as [email protected] in two rows and [email protected] in one. Which is the right one? Nobody knows without phoning her.

None of these three problems is a space problem. All three are the same problem: the data is in several places, somebody touched one, and now the database is lying.

There is a formulation worth memorizing: redundancy does not cause inconsistency, it makes it possible; and everything that is possible, given enough rows and enough time, happens. A database with forty thousand loans and eight years of history accumulates an amount of contradiction proportional to the amount of redundancy you allow it.

To work formally we need the spreadsheet to be a table with reasonable column names. We are going to call it loans_sheet and give it this structure, which is the one from the original file with the columns renamed and nothing added:

And this is the data, already with the spellings unified so that we can reason about the structure without the typos distracting us (we will get them back in 05-03, where they really do have to be cleaned up):

Five rows. Count how many times the string Félix J. Palma appears: three. How many times Vallmar: five. How many times Marta's phone number: three. With five rows it is a curiosity; with the 84,000 loans BiblioRed has recorded since 2018, it is a structural problem.

One clarification about the primary key before we go on. I have used (copy_code, loan_date) because BiblioRed's business rule says that a physical copy cannot be on loan twice on the same day: there is only one copy, and if somebody took it away, nobody else can take it until it comes back. In section 13 we will formally verify that this pair really is a key, instead of taking it on trust.

Lesson 04-01 named the three anomalies in a three-line table and promised to explain them here. Here we go, and this time with SQL that really does provoke them.

An anomaly is undesirable behavior that shows up when you insert, modify or delete rows of a badly designed table. It is not a programmer error or a DBMS failure: it is an unavoidable consequence of the table's structure. With loans_sheet you cannot avoid them however careful you are, because they are in the design.

You cannot record one fact because another, unrelated fact is missing.

BiblioRed has just added Ken Follett to its author catalog with his correct nationality, and it also wants to record that a new branch, East, exists in postal code 08140. Let's try:

You can't. To store a fact about an author you have to invent a loan: a copy, a date, a member, an ISBN. Information about authors has nowhere to live unless it hangs off a loan.

The same with the new branch:

The only way out would be to insert a row with made-up values or NULL in everything else —a "ghost row"— and that poisons every query: loan counts come out wrong, average days come out wrong, and sooner or later somebody will ask why there is a loan with no member.

Translation of the problem: the table mixes facts about loans with facts about authors and branches, and it only has a key for the first. The facts belonging to the other entities are trapped.

Changing one fact forces you to modify many rows; if one escapes, the database contradicts itself.

The Vallmar city council renames the North branch as "Vallmar Nord". In a normalized schema this is a single-row UPDATE. Here:

Four rows in the sample; some 31,000 in the real file. And that UPDATE worked because every row said exactly North. In the original file one said north in lowercase, and so it did not match the WHERE:

There is the anomaly in its purest form: a branch that now exists under two different names because one row was left out of the update. It is exactly defect number 7 from the diagnosis in 01-01, and now we know it was not bad luck or carelessness at the front desk: it is the mathematical consequence of having the branch name repeated across 31,000 rows.

The same happens with Marta Alsina's phone number. If she changes it, the three rows where it appears have to be touched; if only two get updated, BiblioRed has two phone numbers for the same person and no way of knowing which to dial.

Translation of the problem: the branch name is a fact about the branch, not about the loan, but it is stored once per loan.

Deleting a row destroys information that had nothing to do with it.

Iván Pereda asks for his loan history to be deleted, and BiblioRed is obliged to comply. His loan of "The Pillars of the Earth" is, let's say, the only one left for that copy:

By deleting that row we have unintentionally lost:

• That a copy called EJ-3090 exists.
• That ISBN 9788401337208 corresponds to "The Pillars of the Earth".
• That its author is Ken Follett.
• That Ken Follett is British.

If that row had been the last one with Follett in the whole table, Ken Follett would have ceased to exist in BiblioRed's database. A permanent catalog fact, deleted by an operation on a loan. No audit would catch it: the row was deleted correctly, the operation succeeded, and yet information was lost.

Translation of the problem: the author's existence is conditional on the existence of at least one loan of his work, when in the real world those are independent things.

All three have the same cause: the table stores facts about several different entities (loan, member, book, author, branch) in a single row, and only one of those entities rules the key. Everything else is there on sufferance.

And here is the great conceptual leap of this lesson: that cause can be written down precisely. The tool for doing so is functional dependencies.

A functional dependency is a rule saying that, once the value of some attributes is known, the value of others is determined unambiguously.

Definition. Let X and Y be two sets of attributes of a relation R. We say that X functionally determines Y, written X → Y, if for any pair of rows of R that agree on all the attributes of X, they necessarily agree on all the attributes of Y as well.

Let's go through the vocabulary, because every symbol counts and no mathematical background is assumed here:

• Attribute: a column. isbn is an attribute.
• Set of attributes: a group of columns, written between braces: {copy_code, loan_date}. When the set has a single element, the braces are usually dropped: isbn instead of {isbn}.
• The arrow →: read as "determines". isbn → title is read "the ISBN determines the title". It is not an assignment, nor a logical implication, nor an arrow in a diagram: it is a symbol specific to this theory.
• The left-hand side (X) is called the determinant. The right-hand side (Y) is the determined or dependent side.
• Juxtaposition means union: XY is shorthand for "the set formed by all the attributes of X plus all those of Y". The operation is called union and its formal symbol is ∪, so XY and X ∪ Y are the same thing. You will see both notations in the literature.

isbn → title says: "if two rows have the same ISBN, they necessarily have the same title". Or, put the other way round and more usefully: "there cannot be an ISBN with two different titles". This second formulation —as a prohibition— is usually the easiest one to validate with the person who knows the business.

Notice that the dependency says nothing in the other direction. isbn → title does not imply title → isbn: two different editions of "The Map of Time" can share a title and have different ISBNs. Dependencies have a direction, and mixing it up is beginner mistake number one.

The left-hand side can have several attributes:

Read as: "given the copy and the date it was lent on, the return date is determined". And it makes sense: that pair identifies one specific loan, and one specific loan was returned on one specific day (or not yet, in which case it is NULL, but it is the same NULL for the two rows that agree).

Neither attribute on its own would be enough. copy_code → return_date is false: copy EJ-3081 appears in two rows with different return dates (2026-03-16 and NULL). Finding two rows that break it is enough to refute the dependency.

The right-hand side can have several too:

"The member's email determines their name and their phone number". As we will see in section 11, a dependency like this can always be split into several with a single attribute on the right, and vice versa. It is a matter of writing convenience.

Gathered together, this is the set of functional dependencies that govern our table. We will call this set F (for functional dependencies), and we will use it throughout the lesson:

Read them one by one out loud, in their prohibition form:

This section is short and is probably the most important one in the lesson.

Functional dependencies are discovered by asking the person who knows the business, not by looking at the data.

The reason is elementary logic. A dependency X → Y asserts something about every row that could ever exist, including those not yet inserted. Sample data can only do two things:

• Refute a dependency: if you find two rows with the same X and different Y, the dependency is false. This is conclusive.
• Fail to refute it: if you find no counterexamples, the dependency might be true. This proves nothing.

An example with our table. Look at the five rows and you will see that member_phone → member_email holds: each phone number always appears with the same email. Is it a functional dependency? Let's ask BiblioRed: "can two members share a phone number?" Answer: "Of course, a married couple giving the home landline, or two teenage siblings giving their mother's number." It is not a dependency. It was a coincidence in the sample.

Another example, in the opposite direction. In the five rows, branch_city is always Vallmar, so apparently title → branch_city holds (everything determines it, because there is only one value). It is obviously absurd. With a small enough sample, preposterous dependencies "hold".

If you have to normalize an existing database and there is nobody to ask, data analysis can be used as a starting point for formulating hypotheses, and there are tools that look for candidates automatically. But every candidate has to be validated against the business before it becomes a design decision. A dependency adopted by mistake makes you decompose where you should not have, and makes the database reject legitimate data on the day it turns up.

Practical rule: turn every dependency into a sentence starting with "it cannot happen that…" and take it to the meeting. isbn → title becomes "it cannot happen that the same ISBN has two different titles". If the business person hesitates or says "well, except when…", you do not have a dependency: you have to keep digging.

With the definition in hand we can classify. These three kinds are exactly the ones we will need in the next lesson to define second and third normal form, so it is worth having them clear.

First we need a term: a superkey is a set of attributes that determines all the other attributes of the relation. A candidate key is a minimal superkey: if you remove any attribute from it, it stops determining everything. We will come back to this in section 13 with a procedure for computing them; for now it is enough to know that in loans_sheet the candidate key is {copy_code, loan_date}.

X → Y is full if Y depends on the whole of X: removing any attribute from X makes the dependency stop holding.

Example in BiblioRed:

It is full because neither half is enough:

• copy_code → return_date is false: EJ-3081 has two different return dates in the sample.
• loan_date → return_date is false: two loans made the same day are returned on different days.

Both attributes are needed, and that is why the dependency is full. Full dependencies on the key are the good ones: they are exactly the ones we want to survive normalization.

X → Y is partial if X is a composite key (of two or more attributes) and Y is already determined by part of X.

Example in BiblioRed:

isbn is an attribute of the table that depends on the key {copy_code, loan_date} —as does everything else— but half the key is superfluous: copy_code alone already determines it. A copy's code says which work it is, regardless of when it was lent.

What harm it does: the ISBN, the title and the author are repeated in every loan of that copy. They are a fact about the copy, not about the loan, and they are stored once per loan. It is the direct source of the anomalies in section 4.

The same goes for copy_code → branch_name: the branch where the copy lives does not depend on when it was lent.

Notice a detail: a table with a single-attribute key cannot have partial dependencies, because there are no "parts" of the key. That is a useful fact when second normal form arrives.

X → Z is transitive if there is an intermediate set Y such that X → Y and Y → Z, where Y is not a superkey and Z is an attribute that is not part of any key.

In plain terms: the attribute does not depend on the key directly, but "through" another attribute that is not a key either.

Example in BiblioRed:

The member's name does depend on the loan's key, yes, but only because the key determines the email and the email determines the name. member_email is not a key of the table; it is just another attribute that happens to determine others. The real dependency is member_email → member_name, and the loan has nothing to do with it.

Another example, in a chain of three hops:

To know the nationality of the author of a loan you have to go through the copy, the ISBN and the author. Four steps, none of them a key except the first, and the result repeated in every row.

And the cleanest one of all, which will come back in the next lesson:

The city is not a fact about the branch: it is a fact about the postal code. That the North branch is in Vallmar is a consequence of it being in 08110 and of 08110 being in Vallmar.

What harm it does: exactly the same as the partial one. A fact belonging to another entity is repeated in every row of this one.

A dependency is trivial when the right-hand side is already contained in the left-hand side:

They are called trivial because they always hold, in any table, without anybody having to decide it: if two rows agree on {copy_code, loan_date}, they obviously agree on copy_code, which is one of those two columns. They tell you nothing about the design.

The symbol used to express this is ⊆, read "is contained in" or "is a subset of". Y ⊆ X means that every element of Y is also in X. With that notation:

X → Y is trivial if Y ⊆ X. Otherwise it is non-trivial. If in addition X and Y share no attributes, it is said to be completely non-trivial.

So what are they good for? Two things. First, because they are the basis of Armstrong's first axiom (section 10) and they make the theory complete and free of special cases. Second, because the formal definitions of the normal forms explicitly exclude the trivial ones, and if you did not know what they were, those definitions would look incomprehensible. When you read "for every non-trivial dependency X → Y…" in 05-02, you will already know what is being ruled out and why.

Dependencies are much easier to see drawn out. Every arrow in the diagram is a functional dependency from the set F:

The graph tells the whole story at a glance, and it is worth looking at slowly:

• The two thick arrows come out of the complete key. Those are the healthy dependencies: member_email and return_date are genuine facts about the loan.
• The arrows coming out of copy_code alone (f2) are the partial dependencies. Half a key determines things: there is a hidden table there.
• The long chains (isbn → author → author_nat, branch_name → branch_postal_code → branch_city, member_email → member_name) are the transitive dependencies. Every intermediate link that is not a key gives away another hidden table.
• Every node that has at least one arrow coming out of it and that is not the key —copy_code, isbn, author, member_email, branch_name, branch_postal_code— is an entity disguised as a column. Count them: six. In lesson 05-03 that count will turn into six tables.

This is the moment where the theory and the intuition of module 4 meet. When we said back there that "a row of loans must talk only about the loan", what we were saying without knowing it was: "in the dependency graph, every arrow must come out of the complete key".

We have a set F of seven dependencies given to us by the business. But others that nobody wrote down follow from them. For example, from isbn → author and author → author_nat it obviously follows that isbn → author_nat, even though it is not on the list.

In 1974, William Armstrong published three rules that let you derive all the dependencies that follow from a given set, and only those. They are called Armstrong's axioms. An axiom is a rule accepted as a starting point from which everything else is proved; that these three are enough to derive everything is a proven theorem, not an opinion.

The set of all dependencies derivable from F is called the closure of F and is written F⁺ (with a superscript +, which in this theory always means "everything that follows from this").

If Y ⊆ X, then X → Y.

In plain language: a set of columns determines any subset of itself.

It is the formalization of the trivial dependencies from section 8. It looks like a triviality, and in a way it is, but without it the theory does not close.

Example: {isbn, title} → title. If two rows agree on ISBN and title, they agree on title.

If X → Y, then XZ → YZ for any set Z.

In plain language: if some columns determine others, adding the same extra columns to both sides breaks nothing. Knowing more can never determine less.

Example: we know that isbn → title. By augmentation with Z = {loan_date}:

Which reads: "given the ISBN and the loan date, the title and the loan date are determined". It is true, though not much use on its own. Its value lies in combining it with the other axioms.

If X → Y and Y → Z, then X → Z.

In plain language: dependencies chain together.

This is the axiom that does the real work. Example in BiblioRed, with two applications in a row:

We have proved that a copy's code determines the author's nationality. Nobody wrote that rule; it follows. And that is exactly why Ken Follett's nationality appears repeated in every loan of every one of his copies.

From the three axioms other rules follow that add no power —anything proved with them could be proved with the three axioms— but that shorten hand work enormously.

If X → Y and X → Z, then X → YZ.

Plainly: if the same determinant determines two things separately, it determines them together.

Example: from member_email → member_name and member_email → member_phone you get member_email → {member_name, member_phone}. That is exactly what we wrote as f5.

If X → YZ, then X → Y and X → Z.

Plainly: it is the previous rule backwards. A dependency with several columns on the right can be split into several with just one.

Example: from f2, copy_code → {isbn, branch_name}, you get copy_code → isbn and copy_code → branch_name.

Union and decomposition together say something practical: the right-hand side of a dependency can be grouped or ungrouped freely. That is why, when you have to work by hand, you usually start by decomposing every dependency so that they all have a single attribute on the right. Our set F would look like this:

Careful: the left-hand side cannot be split like that. From {copy_code, loan_date} → member_email it does not follow that copy_code → member_email. This is a classic mistake and it produces disastrous decompositions.

If X → Y and YW → Z, then XW → Z.

Plainly: a transitivity in which the second step needs extra help. If X gives me Y, and Y plus W gets me to Z, then X plus W gets me to Z too.

Example: suppose BiblioRed computes the late-return surcharge with a rate that depends on the branch and on the number of days: {branch_name, days_late} → surcharge. Since copy_code → branch_name, by pseudotransitivity:

Given the copy and the days late, the surcharge is determined: the copy supplies the branch.

Applying the axioms by hand to answer "does X → Y follow from F?" is slow and error-prone. There is a mechanical algorithm that solves it, and it is the most useful tool in the whole of normalization theory.

Definition. The closure of a set of attributes X with respect to a set of dependencies F, written X⁺, is the set of all attributes that are determined by X using the dependencies in F.

Put another way: X⁺ answers the question "if I know the values of X, what else can I work out?".

The idea is that of a snowball: you start from what you know, apply every rule you can, and with the new things you have worked out you try again, until a complete pass adds nothing.

There is only one thing to watch out for, and it is the same trap as before: to fire a dependency A → B you need all the attributes of A in RESULT, not just some of them.

Question: knowing only the copy's code, what do I know about a loan?

Eight attributes out of thirteen. Missing are loan_date, return_date, member_email, member_name and member_phone. Formal conclusion: copy_code is not a superkey of loans_sheet, because its closure does not contain every attribute.

And an important reading: those eight attributes it does determine are precisely the ones that will be repeated in every loan of the same copy. The closure of a non-key attribute measures the redundancy that attribute generates.

Three attributes. Not a superkey either. And once again the closure sketches out a table that is begging to exist: members(email, name, phone).

It contains every attribute. By definition, {copy_code, loan_date} is a superkey.

We now have everything we need to solve the central practical problem: given a relation and its dependencies, what are its keys?

The systematic procedure rests on a very useful observation that saves most of the work. Classify each attribute according to where it appears in F:

The reason for the first rule is intuitive: if an attribute never appears on the right, no dependency can produce it, so the only way to know it is to have it as input. And the reason for the second: if it appears only on the right, it can always be derived from others, so it is never needed in a minimal set.

Step 1. Classify the thirteen attributes.

Step 2. The mandatory core. The "left only" attributes are in every candidate key: {copy_code, loan_date}.

Step 3. Is the core enough? We compute its closure, which we already did in example 3 of the previous section:

Yes, it is enough. It is a superkey.

Step 4. Is it minimal? We have to check that no proper subset is. The proper subsets of a two-element set are three: {copy_code}, {loan_date} and the empty set.

• {copy_code}⁺ = 8 attributes. Not a superkey (computed in 12.1).
• {loan_date}⁺ = {loan_date}. No dependency has loan_date alone on the left, so the closure does not grow. Not a superkey.
• The empty set, obviously, is not either.

Step 5. Conclusion. {copy_code, loan_date} is a superkey and it is minimal, so it is a candidate key. And since every "left only" attribute must be in every candidate key, and these two are already enough on their own, it is the only one.

This proves what we took on trust in section 3. That is the difference between designing by intuition and designing with instruments: now we do not believe it, we know it.

To show you that uniqueness is not guaranteed, let's take the members table from BiblioRed's real schema, with these dependencies:

The second one exists because email is UNIQUE (we declared it that way in 02-02). Let's compute:

• {member_id}⁺ = every attribute → superkey, and minimal (it is a single attribute).
• {email}⁺ = every attribute → superkey, and minimal.

Two candidate keys: {member_id} and {email}. One is chosen as the primary key —member_id, the surrogate one, for the reasons we discussed in 04-01— and the other remains as an alternate key, protected with UNIQUE. This is not a design flaw; it is what normally happens when an entity has both a natural key and a surrogate key.

The last definition of the lesson, and the shortest. We will need it literally in the first sentence of second and third normal form.

An attribute is prime (or a key attribute) if it is part of some candidate key of the relation. If it is part of none, it is non-prime (or a non-key attribute).

Note the "some": if a relation has two candidate keys, being in one of them is enough to be prime.

In loans_sheet, with its single candidate key {copy_code, loan_date}:

Eleven non-prime attributes, every one of them hanging off the key by partial or transitive dependencies. The table is, formally speaking, as bad as it looked.

In members, with candidate keys {member_id} and {email}, both are prime: member_id and email. All the rest are non-prime. This example usually comes as a surprise: email is an entirely ordinary-looking attribute and yet it is prime, because it is a candidate key.

Confusing "normalizing" with "having lots of tables". The number of tables is a consequence, not a goal. If, when decomposing, you cannot name the problematic dependency you are removing, you are not normalizing: you are complicating the schema. When in doubt, write the dependency down on paper before touching the CREATE TABLE.

Deriving dependencies from sample data. This is the most expensive mistake of all, because it is not detected until the system is in production and rejects legitimate data. Every dependency must come from a confirmed business rule. If BiblioRed says "in principle each ISBN has one title", that "in principle" is an alarm: ask about the exceptions before writing it down.

Reversing the arrow. isbn → title is not the same as title → isbn, and the second is false (several editions share a title). When you are unsure about the direction, use the prohibition formulation: "can there be an ISBN with two titles?" (no → the dependency goes from ISBN to title) versus "can there be a title with two ISBNs?" (yes → there is no dependency in that direction).

Splitting the left-hand side of a dependency. From {A, B} → C it does not follow that A → C or B → C. The right-hand side can be split (decomposition rule); the left-hand side, never. Applying this false rule when computing a closure produces invented candidate keys and decompositions that lose information.

Forgetting that a single counterexample refutes. To prove a dependency false it is enough to find two rows with the same determinant and a different determined value. It is the cheapest check there is and it is always worth doing before accepting a dependency. In SQL:

Careful: returning zero rows does not prove the dependency (section 6), but returning some does refute it, or else indicates that there is dirty data to clean up. In BiblioRed's original file this query returned rows, precisely because of the truncated ISBN.

Stopping after the first pass when computing a closure. The algorithm repeats until nothing changes. It is very easy to add isbn and forget that now, with isbn inside, isbn → author fires, and with author inside, author → author_nat fires. Mark the dependencies you have already used and go through the whole list again after each addition.

Method tip: to compute closures by hand, write the dependencies in split form (a single attribute on the right) and cross them off as you use them. It is much harder to go wrong.

BiblioRed keeps a flat table events_sheet with this structure, inherited from another spreadsheet:

events_sheet(event_id, event_title, date, room_name, room_capacity, room_floor, speaker_email, speaker_name)

For each of these three situations, say which anomaly it is (insertion, update or deletion) and which functional dependency causes it:

• a) The Multipurpose room at Central is refurbished and its capacity goes from 60 to 90 seats. There are 214 events already held in it.
• b) BiblioRed opens a new room, the Children's Room at East, with capacity 25. No event has been scheduled there yet.
• c) The only event that speaker Clara Ferrán took part in is cancelled and deleted.

For the relation:

R(event_id, member_email, member_name, registration_date, status, companions, occupied_seats)

with the set of dependencies:

You are asked to:

• a) Compute {event_id, member_email}⁺ showing the passes.
• b) Say whether it is a superkey and whether it is a candidate key, justifying it.
• c) Compute {member_email}⁺ and say what the result means.
• d) List the prime and the non-prime attributes.

In the loans_sheet relation from this lesson, classify each of these five dependencies as full, partial, transitive or trivial with respect to the candidate key {copy_code, loan_date}. Justify each one in a sentence.

• a) {copy_code, loan_date} → member_email
• b) copy_code → branch_name
• c) {copy_code, loan_date} → branch_city
• d) {copy_code, isbn} → copy_code
• e) member_email → member_phone

Solution 1

a) Update anomaly. The guilty dependency is room_name → room_capacity: the capacity is a fact about the room, but it is stored once per event. Changing it forces an UPDATE of 214 rows, and if any of them is left out —because of a badly written filter, because of a difference in capitalization in the room name— BiblioRed will have the same room with two capacities. It is exactly the "North"/"north" case moved to rooms.

b) Insertion anomaly. The same dependency, room_name → {room_capacity, room_floor}, seen from the other side. The room's data can only be stored hanging off an event, and this room has none. The only alternative would be to insert a phantom event with made-up event_title and date, which would contaminate any query about events.

c) Deletion anomaly. The dependency is speaker_email → speaker_name. Deleting the event also removes the only record saying that a speaker called Clara Ferrán with that email exists. The information about the speaker had no existence of its own: it lived on sufferance in the event's row.

All three share the same root: there are dependencies whose determinant (room_name, speaker_email) is not a key of the table. They are entities —rooms, speakers— disguised as columns. And not by accident: in the real schema of module 4, BiblioRed already has them as tables of their own.

Solution 2

a) Closure of {event_id, member_email}:

All seven attributes of R. Note the snowball effect: occupied_seats only comes in after companions does, and companions itself came in through g1. Anyone who stops at the first dependency misses it.

b) It is a superkey, because its closure contains every attribute. And it is a candidate key because it is minimal: the two single-element proper subsets have to be checked.

• {event_id}⁺ = {event_id}. event_id does not appear alone on the left of any dependency (in g1 it has company), so the closure does not grow. Not a superkey.
• {member_email}⁺ = see part c). Not a superkey.

Since no proper subset is a superkey, {event_id, member_email} is minimal and therefore a candidate key.

c) Closure of {member_email}:

Only g2 is applicable, and after that nothing else. Two attributes out of seven. It means that member_email is not a superkey, and —more interestingly— that it drags along an attribute, member_name, that will end up repeated in every registration by that member. It is a partial dependency on the composite key, the unmistakable sign that the member's name has no business in this table and must live in members. In BiblioRed's real schema, registrations has no member_name, and now we formally know why.

d) The only candidate key is {event_id, member_email}.

• Prime: event_id, member_email.
• Non-prime: registration_date, status, companions, member_name, occupied_seats.

Solution 3

a) Full. The determinant is the complete key and neither of its two halves is enough: copy_code → member_email is false (EJ-3081 was lent to Marta on two different occasions, but it could have gone to somebody else on another date; and in general a copy circulates among members), and loan_date → member_email is obviously false (books are lent to several members on the same day). It is a healthy dependency: member_email is a genuine fact about the loan.

b) Partial. The determinant copy_code is a proper part of the composite key and already determines branch_name on its own. The loan date plays no part: the branch where a copy lives does not change according to when it is lent. It is one of the dependencies that second normal form will remove.

c) Transitive. The key does determine branch_city, yes, but through a chain of three hops: {copy_code, loan_date} → copy_code → branch_name → branch_postal_code → branch_city. None of the intermediate links is a superkey and branch_city is a non-prime attribute, which are the two conditions for transitivity. It is the one that third normal form will remove.

(Note: this dependency is partial at the same time, because copy_code alone already produces it. The categories are not mutually exclusive: one and the same dependency can be problematic for more than one reason, and that is why normalization is applied in stages —first 2NF, then 3NF— instead of all at once.)

d) Trivial. The right-hand side, {copy_code}, is contained in the left-hand side, {copy_code, isbn}. It always holds, in any table, without anybody deciding it. It says nothing about the design and the definitions of the normal forms will explicitly exclude it.

e) Transitive (with respect to the key). On its own, member_email → member_phone is simply a dependency; what makes it transitive is its relationship with the key: {copy_code, loan_date} → member_email → member_phone, with member_email not a superkey and member_phone non-prime. Its practical consequence is that Marta Alsina's phone number is written three times in five rows.

This lesson has built the instruments. Let's recap what is now in your hands and was not when the module began.

You know what normalizing is: reorganizing attributes so that every fact appears exactly once, with a justifiable procedure. And you know what it is not: neither splitting tables for sport, nor an end in itself, nor cleaning up dirty data. You also know that the enemy is not disk space but the physical possibility of contradiction, and that everything that is possible eventually happens.

You know how to name the damage. The three anomalies —insertion, update and deletion— stopped being a three-line table from module 4 and became three concrete failures you have watched being provoked with INSERT, UPDATE and DELETE on the BiblioRed sheet. And you know that all three have a single structural cause.

You know how to write the cause down. X → Y, "X determines Y", with its determinant and its determined side, with its direction that cannot be reversed, and with the capital warning that it comes from business rules and never from sample data. You can tell full dependencies (the healthy ones) from partial ones (half a key determines something) and transitive ones (you get there through a non-key attribute), and you know how to discard the trivial ones.

You know how to compute. Armstrong's three axioms —reflexivity, augmentation, transitivity— and their three derived rules —union, decomposition, pseudotransitivity— let you derive every dependency that follows from the known ones. And the closure X⁺ algorithm turns into something mechanical what used to be intuition: it tells you whether a dependency follows, whether a set is a superkey and, applied together with the classification of attributes by their position in F, it finds the candidate keys. We have used it to prove that the key of loans_sheet is {copy_code, loan_date} and that members has two candidate keys.

And you know how to classify attributes into prime (those that are part of some candidate key) and non-prime (the rest), which is the distinction that the definitions coming next rest on literally.

Because what comes next are the normal forms. They are a scale of increasingly demanding levels: the first asks for little and almost any reasonable table satisfies it; the second adds one condition; the third, another; and so on up to a point where the demands are so fine-grained that they are rarely applied in practice. Each level forbids one specific kind of badly placed dependency —and you have to recognize every one of the kinds we defined in this lesson in order to understand which one each level forbids.

In lesson 05-02, Normal Forms, we will go through them one by one: first, second, third, Boyce-Codd, fourth and fifth, each with its precise definition, a minimal BiblioRed example that violates it, the corresponding fix and the reason it matters. We will not yet apply any methodology to the loans sheet —that is lesson 05-03—: first we need the complete catalog.