Database design best practices in SQL - Time & Space Complexity

Time Complexity: Database design best practices

O(log n)

Understanding Time Complexity

When designing a database, it is important to understand how the structure affects the speed of queries.

We want to know how the design choices impact the time it takes to get data as the database grows.

Scenario Under Consideration

Analyze the time complexity of this simple query on a well-designed table.

SELECT customer_name, order_date
FROM orders
WHERE customer_id = 12345;

This query fetches orders for one customer using an indexed column.

Identify Repeating Operations

Look for repeated steps in the query process.

• Primary operation: Searching the index for matching customer_id.
• How many times: Depends on the number of matching orders for that customer.

How Execution Grows With Input

As the total number of orders grows, the index helps keep search fast.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find data
100	About 5-7 steps
1000	About 7-10 steps

Pattern observation: The search steps grow slowly even if the data grows a lot, thanks to indexing.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly as the database gets bigger, making queries efficient.

Common Mistake

[X] Wrong: "Adding more data always makes queries take much longer."

[OK] Correct: Proper design with indexes keeps search time growing slowly, not linearly.

Interview Connect

Understanding how design affects query speed shows you know how to build databases that work well as they grow.

Self-Check

"What if we removed the index on customer_id? How would the time complexity change?"

Practice

1. Which of the following is a key reason to use primary keys in database tables?

easy

A. To store large amounts of text data

B. To create duplicate records easily

C. To speed up the database server hardware

D. To uniquely identify each record in the table

Solution

1. Step 1: Understand the role of primary keys

   Primary keys uniquely identify each row in a table, preventing duplicates.

2. Step 2: Compare options with primary key purpose

   Only To uniquely identify each record in the table describes uniqueness, which is the main purpose of primary keys.

3. Final Answer:

   To uniquely identify each record in the table -> Option D

4. Quick Check:

   Primary key = unique record ID [OK]

Hint: Primary keys always ensure unique records [OK]

Common Mistakes:

• Thinking primary keys store large text
• Confusing primary keys with performance hardware
• Believing primary keys allow duplicates

2. Which SQL statement correctly creates a table with a primary key on the id column?

easy

A. CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50));

B. CREATE TABLE users (id INT, name VARCHAR(50) PRIMARY KEY);

C. CREATE TABLE users (id INT, name VARCHAR(50), PRIMARY id);

D. CREATE TABLE users (id INT UNIQUE, name VARCHAR(50));

Solution

1. Step 1: Review correct primary key syntax

   The primary key is declared as id INT PRIMARY KEY inside the column definition.

2. Step 2: Check each option's syntax

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); uses correct syntax; A has invalid syntax; B places PRIMARY KEY on wrong column; D uses UNIQUE but not PRIMARY KEY.

3. Final Answer:

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); -> Option A

4. Quick Check:

   Primary key syntax = column_name TYPE PRIMARY KEY [OK]

Hint: Primary key goes right after the column type [OK]

Common Mistakes:

• Placing PRIMARY KEY on wrong column
• Using UNIQUE instead of PRIMARY KEY
• Incorrect syntax for primary key declaration

3. Given these two tables:
CREATE TABLE authors (author_id INT PRIMARY KEY, name VARCHAR(100));
CREATE TABLE books (book_id INT PRIMARY KEY, title VARCHAR(100), author_id INT, FOREIGN KEY (author_id) REFERENCES authors(author_id));
What will happen if you try to insert a book with author_id = 5, but no author with author_id = 5 exists?

medium

A. The insert will succeed and create a new author automatically

B. The insert will fail due to foreign key constraint violation

C. The insert will succeed but author_id will be set to NULL

D. The insert will succeed but cause duplicate author records

Solution

1. Step 1: Understand foreign key constraints

   Foreign keys require the referenced value to exist in the parent table to maintain data integrity.

2. Step 2: Apply constraint to the insert operation

   Inserting a book with author_id = 5 fails if no author with id 5 exists, causing a constraint violation.

3. Final Answer:

   The insert will fail due to foreign key constraint violation -> Option B

4. Quick Check:

   Foreign key enforces existing parent record [OK]

Hint: Foreign keys block inserts without matching parent [OK]

Common Mistakes:

• Assuming foreign keys auto-create missing parents
• Thinking foreign keys allow NULL by default
• Ignoring constraint errors on insert

4. You have a table orders with columns order_id (primary key), customer_id, and order_date. You want to add a foreign key constraint on customer_id referencing customers(customer_id). Which of these statements has an error?

medium

A. ALTER TABLE orders ADD FOREIGN KEY (customer_id) REFERENCES customers(customer_id);

B. ALTER TABLE orders ADD CONSTRAINT fk_customer FOREIGN KEY (customer_id) REFERENCES customers(customer_id);

C. ALTER TABLE orders ADD FOREIGN KEY customer_id REFERENCES customers(customer_id);

D. ALTER TABLE orders ADD CONSTRAINT fk_customer FOREIGN KEY (customer_id) REFERENCES customers(customer_id) ON DELETE CASCADE;

Solution

1. Step 1: Review correct syntax for adding foreign keys

   The correct syntax requires parentheses around the column name after FOREIGN KEY.

2. Step 2: Identify the incorrect statement

   ALTER TABLE orders ADD FOREIGN KEY customer_id REFERENCES customers(customer_id); misses parentheses around customer_id, causing syntax error.

3. Final Answer:

   ALTER TABLE orders ADD FOREIGN KEY customer_id REFERENCES customers(customer_id); -> Option C

4. Quick Check:

   Foreign key column must be in parentheses [OK]

Hint: Always use parentheses around foreign key columns [OK]

Common Mistakes:

• Omitting parentheses around column names
• Forgetting to name the constraint (optional but recommended)
• Misplacing ON DELETE options

5. You are designing a database for a library. You want to track books, authors, and the categories each book belongs to. Which design best follows database design best practices?

hard

A. Separate tables for books, authors, and categories with primary keys and foreign keys linking them

B. Separate tables for books and categories only, storing author names as text in books

C. One table for books and authors combined, and a separate table for categories

D. One table with columns: book_id, book_title, author_name, category_name

Solution

1. Step 1: Analyze normalization and relationships

   Best practice is to separate entities into tables and link them with keys to avoid duplication.

2. Step 2: Evaluate each option's design

   Separate tables for books, authors, and categories with primary keys and foreign keys linking them uses separate tables with keys, which supports clear organization and data consistency.

3. Final Answer:

   Separate tables for books, authors, and categories with primary keys and foreign keys linking them -> Option A

4. Quick Check:

   Separate tables + keys = best design [OK]

Hint: Use separate tables and keys for related data [OK]

Common Mistakes:

• Putting all data in one table causing duplicates
• Mixing unrelated data in same table
• Storing related entity names as plain text