Data modelling: tables, relationships, normal forms

After the requirements, interviewers ask: "What data will you store? Draw the tables." This is often called the entities step. A wrong table design is hard to fix once the app is built, because every part of the app reads and writes those tables.

A weak answer is one wide table with every column, or a list of table names with no links. A strong answer names the main things the app keeps. It says how many of one thing can link to another, and it shows where each fact lives. It also says what the design costs.

At SDE-1 level you should find the tables and the keys. At SDE-2 level you should also handle many-to-many links and explain why a fact is stored once. At SDE-3 level you should also say what the design costs when you read the data back.

Think about a school office with one big register. Each line is one fee payment. Every line repeats the student name, the class teacher name and the teacher phone number. Now the teacher changes the phone number. The clerk must fix every line of that class. If the clerk misses one line, the register disagrees with itself: two phone numbers for one teacher.

The fix is simple. Keep a short second list of teachers, once. On each payment line, write only the teacher number. Now the phone number lives in one place.

Data modelling is this fix, done for a whole app. First a few words. In lesson 17 you met tables, rows, columns, primary keys, foreign keys and joins. Here we use them to design.

Entities and attributes

An entity is a kind of thing that the app keeps data about, such as a customer, an order or a dish. Each entity becomes one table. An attribute is one fact about an entity, such as a name or a price. Each attribute becomes one column.

To find entities, read the requirements and mark the nouns. Keep a noun as an entity if it has its own facts and many of them exist. Keep a noun as a plain column if it is only one fact about another thing. An "address" is a column if each customer has one address. It is an entity if one customer can have many addresses.

Relationships

A relationship is a link between two entities. Ask two questions for each pair:

1. Can one A have many B?
2. Can one B have many A?

Here is how each kind is stored:

• One-to-many. One customer has many orders, but each order has one customer. Put a foreign key on the "many" side: the orders table has a customer_id column.
• One-to-one. One customer has one wallet, and each wallet belongs to one customer. Put the foreign key in either table, or keep both sets of columns in one table. A separate table is useful when the data is rarely read or is private.
• Many-to-many. One order has many dishes, and one dish is in many orders. A foreign key on either side is not enough. You add a link table. It has one row for each pair, with two foreign keys. Its primary key is the pair. It can also hold facts about the pair, such as the quantity.

The ER diagram

An entity-relationship (ER) diagram is a drawing of the entities and their links. Each box is one table. Each line is one relationship. A line has a "1" at the one end and a "*" at the many end. In an interview you can draw boxes on the board, or write the lines as text.

Normalisation

A normal form is a rule about how to arrange the columns. Normalisation means arranging them so that each fact is stored in one place. The big register above breaks this rule, and it causes three problems called anomalies:

• Update anomaly. A fact is repeated, so a change must be made in many rows. If one row is missed, the data disagrees with itself.
• Insert anomaly. You cannot save a fact until another fact exists. You cannot save a new dish until somebody orders it.
• Delete anomaly. Deleting one thing deletes a fact you wanted to keep. Cancel the only order with a dish, and the dish is gone.

To say "A depends on B", we mean: if you know B, you can find exactly one A. A composite key is a key that uses two or more columns together. A non-key column is any column that is not part of the key.

There are three normal forms to know. Each one includes the one before it.

1. First normal form. Each cell holds one value. No list in a cell, and no repeating columns such as dish1, dish2, dish3. Fix: one row for each item.
2. Second normal form. This matters when the key has two or more columns. Every other column must depend on the whole key, not on a part of it. Fix: move a column that depends on only one part into its own table.
3. Third normal form. A column must depend on the key and not on another non-key column. Fix: move such columns to their own table, with their own key.

In short: each column depends on the key, on the whole key, and on nothing else. Higher forms exist, but interviews rarely ask beyond the third.

This lesson designs for a relational database. In a document database (lesson 17), related data is often put inside one document, so the rules are used differently.

SwadKart is the food-delivery app of lesson 17. We design its tables.

Assumptions (made up to teach with, not real data):

• 1,000,000 orders per day, 3 dishes in an order on average. So 3,000,000 order lines per day.
• Text sizes: a customer's name, phone and address take 100 bytes. A restaurant's name and area take 50 bytes. A dish name takes 30 bytes. An id takes 8 bytes.
• 5,000,000 customers. 100,000 restaurants with 80 dishes each (the menu size of lesson 17).

Step 1: the nouns. The app needs customers, restaurants, dishes and orders. An order has dishes in it. These four are entities.

Step 2: the big table, and why it hurts. Suppose we start with one table. One row is one dish in one order:

• Columns: order_id, order_time, customer_name, customer_phone, customer_address, restaurant_name, restaurant_area, dish_id, dish_name, price, quantity.
• The key is the pair order_id and dish_id.

Her address is in every row she appears in. She has 200 x 3 = 600 rows. Update anomaly: she moves, and 600 rows must change. If 599 change, she has two addresses. This answers the predict box: 600 rows, against 1 row when the address is stored once. Insert anomaly: a new dish has no order yet, so it cannot be saved. Delete anomaly: cancel the only order with "Masala dosa", and the dish and its price are gone.

Step 3: first normal form. Suppose a first draft had one row per order, with a cell "Paneer pizza x1, Cola x2". That breaks the first form, because one cell holds a list. You cannot count pizzas, and you cannot join on a dish. The big table of step 2, with one row per dish, already fixes this.

Step 4: second normal form. The key is (order_id, dish_id). Check each column:

• quantity depends on both parts: how many of this dish in this order. It stays.
• order_time and all customer_ and restaurant_ columns depend on order_id only. Move them to an orders table.
• dish_name depends on dish_id only. Move it to a dishes table.
• price is two facts. The current price of the dish depends on dish_id only. The price paid in this order depends on both parts of the key. Suppose the price of a pizza changes from Rs 299 to Rs 329. An old order of 2 pizzas must still show Rs 598, not Rs 658. The total would be wrong by Rs 60. So we keep the price paid in the order line, and the current price in a dishes table.

Step 5: third normal form. In orders, customer_name, customer_phone and customer_address depend on the customer, not on the order. Move them to customers. The same holds for restaurant_name and restaurant_area: they move to restaurants. Each customer and each restaurant gets an id, and orders keeps only customer_id and restaurant_id. Two customers can share a name, so the id, not the name, identifies a customer.

Step 6: the result.

customers 1 ---- * orders
restaurants 1 ---- * orders
restaurants 1 ---- * dishes
orders 1 ---- * order_items
dishes 1 ---- * order_items

• customers: id, name, phone, address
• restaurants: id, name, area
• dishes: id, restaurant_id (foreign key, because one restaurant has many dishes), name, price
• orders: id, customer_id, restaurant_id, order_time
• order_items (the link table): order_id, dish_id, quantity, price_paid. The key is the pair order_id and dish_id.

Orders and dishes are many-to-many, and order_items links them.

Step 7: the size of the repeated text. In the big table, each line repeats three things. They are the customer (100 bytes), the restaurant (50 bytes) and the dish name (30 bytes). That is 180 bytes.

• Big table: 3,000,000 lines x 180 bytes = 540,000,000 bytes = 540 MB a day.
• Normalised: each order stores 2 ids, customer_id and restaurant_id (16 bytes): 1,000,000 x 16 = 16,000,000 bytes = 16 MB a day. Both designs keep dish_id, so it is not counted.
• 540 / 16 = 33.75, so about 34 times less repeated data.
• The text kept once: customers 5,000,000 x 100 = 500 MB. Restaurants 100,000 x 50 = 5 MB. Dishes 100,000 x 80 = 8,000,000, and 8,000,000 x 30 = 240 MB. Total 745 MB, once. The saving of 540 - 16 = 524 MB comes every day.

• Normalising solves facts that disagree, and rows that must all change together. It also saves space here: about 34 times less repeated data. It costs more tables, so reading one whole order needs a join over four tables: orders, customers, order_items and dishes. I would change it when a query that joins many tables misses its speed target in a test, and I would test before I change.
• A link table solves a many-to-many link with no lists in cells. It costs one more table and one more join. I would never replace it with a list of ids in one column.
• Stopping at the third form solves most update problems. Going further costs more tables for little gain. I would go further only if a real update problem remains.

"Normalisation makes the database faster." It protects the data. Reads often get slower, because one screen needs joins. In the example, one order read joins four tables instead of reading one row.

"A many-to-many link can be a column with a list of ids." A column dish_ids with "12, 15, 19" breaks the first normal form. The database cannot check that dish 15 exists, cannot join on it, and cannot count orders of one dish. Removing one id means editing text. Use a link table.

"Storing the price in the order line breaks normalisation." It does not, because it is a different fact. The current price of a dish and the price paid on one day are two facts. If you keep only the current price, a price change rewrites history: the old order of 2 pizzas jumps from Rs 598 to Rs 658.

1. What is an entity? Give one example each of a one-to-one, a one-to-many and a many-to-many link. Say the three normal forms in one line each.
2. A school keeps one table with one row for each fee payment. Each row has the student name, the class teacher name, the teacher phone and the amount. There are 1,200 students, with 40 in each class. Each student pays 12 times a year. (a) A teacher changes the phone. How many rows change? (b) How many rows change if teachers are in their own table? (c) The teacher name and phone take 30 bytes. How many bytes of teacher text does the big table hold for the year, and how many does a teachers table hold?
3. A students table has a column subjects with values such as "Maths, Physics". The school wants to count the students of Physics, and to remove Physics from one student. What is wrong, and what tables do you use?