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?"