ER diagram to table mapping in SQL - Time & Space Complexity

Time Complexity: ER diagram to table mapping

O(n * m)

Understanding Time Complexity

When we convert an ER diagram into tables, we want to know how the time to create or query these tables changes as the data grows.

We ask: How does the work increase when we add more entities or relationships?

Scenario Under Consideration

Analyze the time complexity of creating tables from an ER diagram with entities and relationships.

-- Create table for Entity: Student
CREATE TABLE Student (
  StudentID INT PRIMARY KEY,
  Name VARCHAR(100)
);

-- Create table for Entity: Course
CREATE TABLE Course (
  CourseID INT PRIMARY KEY,
  Title VARCHAR(100)
);

-- Create table for Relationship: Enrollment
CREATE TABLE Enrollment (
  StudentID INT,
  CourseID INT,
  PRIMARY KEY (StudentID, CourseID),
  FOREIGN KEY (StudentID) REFERENCES Student(StudentID),
  FOREIGN KEY (CourseID) REFERENCES Course(CourseID)
);

This code creates tables for two entities and a many-to-many relationship between them.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Inserting or querying rows in tables representing entities and relationships.
• How many times: Once per row added; the relationship table grows with pairs of related entities.

How Execution Grows With Input

As you add more students and courses, the number of rows in each table grows.

Input Size (n)	Approx. Operations
10 students, 10 courses	~10 inserts in Student, 10 in Course, up to 100 in Enrollment
100 students, 100 courses	~100 inserts in Student, 100 in Course, up to 10,000 in Enrollment
1000 students, 1000 courses	~1000 inserts in Student, 1000 in Course, up to 1,000,000 in Enrollment

Pattern observation: The relationship table can grow much faster, roughly multiplying the sizes of the two entity tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the work to handle the relationship table grows with the product of the sizes of the two entity tables.

Common Mistake

[X] Wrong: "The relationship table grows linearly with the number of entities."

[OK] Correct: The relationship table can grow much faster because it stores pairs, so its size depends on the combination of entities, not just one side.

Interview Connect

Understanding how tables grow from ER diagrams helps you design efficient databases and predict query performance in real projects.

Self-Check

"What if the relationship was one-to-many instead of many-to-many? How would the time complexity change?"

Practice

1. In an ER diagram, what does an entity typically become when converting to a database schema?

easy

A. A table with columns for each attribute

B. A single column in a table

C. A database index

D. A stored procedure

Solution

1. Step 1: Understand what an entity represents

   An entity in an ER diagram represents a real-world object or concept with attributes.

2. Step 2: Map entity to database structure

   Each entity is converted into a table, where each attribute becomes a column in that table.

3. Final Answer:

   A table with columns for each attribute -> Option A

4. Quick Check:

   Entity = Table [OK]

Hint: Entities become tables with columns for attributes [OK]

Common Mistakes:

• Confusing entities with indexes
• Thinking entities become single columns
• Assuming entities become procedures

2. Which of the following is the correct way to represent a one-to-many relationship in tables derived from an ER diagram?

easy

A. Create a new table with only primary keys from both tables

B. Add a foreign key column in the 'many' side table referencing the 'one' side

C. Add a foreign key column in the 'one' side table referencing the 'many' side

D. Use a trigger to link the two tables

Solution

1. Step 1: Understand one-to-many relationship

   One-to-many means one record in the first table relates to many records in the second table.

2. Step 2: Map relationship to tables

   The 'many' side table gets a foreign key column referencing the 'one' side table's primary key.

3. Final Answer:

   Add a foreign key column in the 'many' side table referencing the 'one' side -> Option B

4. Quick Check:

   Foreign key on 'many' side = Add a foreign key column in the 'many' side table referencing the 'one' side [OK]

Hint: Foreign key goes in the 'many' side table [OK]

Common Mistakes:

• Placing foreign key on the 'one' side
• Creating unnecessary tables for one-to-many
• Using triggers instead of foreign keys

3. Given two entities Author(id, name) and Book(id, title, author_id) with a one-to-many relationship from Author to Book, what will be the result of this SQL query?

SELECT a.name, b.title FROM Author a JOIN Book b ON a.id = b.author_id WHERE a.name = 'Alice';

medium

A. Syntax error due to join condition

B. List of all authors and their books

C. List of books with no authors

D. List of all books written by Alice

Solution

1. Step 1: Analyze the JOIN condition

   The query joins Author and Book on matching author IDs, linking books to their authors.

2. Step 2: Apply the WHERE filter

   It filters authors with name 'Alice', so only books by Alice are selected.

3. Final Answer:

   List of all books written by Alice -> Option D

4. Quick Check:

   Join + filter by author name = books by Alice [OK]

Hint: JOIN on foreign key filters books by author [OK]

Common Mistakes:

• Confusing join condition causing no results
• Ignoring WHERE clause filtering
• Thinking it lists all authors

4. You have two tables from an ER diagram: Student(id, name) and Enrollment(student_id, course_id). You want to add a foreign key constraint to Enrollment.student_id. Which SQL statement is correct?

medium

A. ALTER TABLE Enrollment ADD FOREIGN KEY (student_id) REFERENCES Student(id);

B. ALTER TABLE Student ADD FOREIGN KEY (id) REFERENCES Enrollment(student_id);

C. CREATE FOREIGN KEY Enrollment.student_id REFERENCES Student.id;

D. ALTER Enrollment ADD CONSTRAINT FOREIGN KEY student_id Student(id);

Solution

1. Step 1: Identify the correct syntax for adding foreign key

   The standard syntax is ALTER TABLE [table] ADD FOREIGN KEY (column) REFERENCES [other_table](column).

2. Step 2: Apply to given tables

   Enrollment.student_id references Student.id, so the statement must alter Enrollment table.

3. Final Answer:

   ALTER TABLE Enrollment ADD FOREIGN KEY (student_id) REFERENCES Student(id); -> Option A

4. Quick Check:

   ALTER TABLE + ADD FOREIGN KEY + REFERENCES [OK]

Hint: Foreign key added on referencing table with ALTER TABLE [OK]

Common Mistakes:

• Adding foreign key on referenced table
• Wrong ALTER TABLE syntax
• Using CREATE FOREIGN KEY instead of ALTER TABLE

5. Consider an ER diagram with entities Employee(emp_id, name), Project(proj_id, title), and a many-to-many relationship WorksOn between them. How should you map this relationship into tables?

hard

A. Add proj_id as a foreign key column in Employee table

B. Add emp_id as a foreign key column in Project table

C. Create a new table WorksOn with columns emp_id and proj_id as foreign keys

D. Merge Employee and Project tables into one

Solution

1. Step 1: Understand many-to-many relationships

   Many-to-many means multiple employees can work on multiple projects and vice versa.

2. Step 2: Map many-to-many to tables

   This requires a new table (junction table) that holds foreign keys from both Employee and Project tables.

3. Final Answer:

   Create a new table WorksOn with columns emp_id and proj_id as foreign keys -> Option C

4. Quick Check:

   Many-to-many = junction table with two foreign keys [OK]

Hint: Many-to-many needs a new table with two foreign keys [OK]

Common Mistakes:

• Adding foreign key to only one table
• Merging unrelated tables
• Ignoring the need for a junction table