Converting ER diagrams to relational schema in DBMS Theory - Time & Space Complexity

Time Complexity: Converting ER diagrams to relational schema

O(n + m + a)

Understanding Time Complexity

When converting an ER diagram to a relational schema, we want to understand how the work grows as the diagram gets bigger.

We ask: How does the time to create tables and relationships change with more entities and connections?

Scenario Under Consideration

Analyze the time complexity of the following process.

-- For each entity in the ER diagram
FOR EACH entity IN ER_diagram.entities LOOP
  CREATE TABLE for entity;
  FOR EACH attribute IN entity.attributes LOOP
    ADD attribute as column to table;
  END LOOP;
END LOOP;

-- For each relationship in the ER diagram
FOR EACH relationship IN ER_diagram.relationships LOOP
  CREATE foreign keys or join tables as needed;
END LOOP;
    

This process creates tables for entities and sets up relationships by adding keys or join tables.

Identify Repeating Operations

Look at what repeats in this process.

• Primary operation: Looping over entities and their attributes, then looping over relationships.
• How many times: Once for each entity and its attributes, and once for each relationship.

How Execution Grows With Input

As the number of entities and relationships grows, the work grows too.

Input Size (n)	Approx. Operations
10 entities, 15 relationships	About 10 loops for entities plus their attributes, plus 15 loops for relationships
100 entities, 150 relationships	About 100 loops for entities plus their attributes, plus 150 loops for relationships
1000 entities, 1500 relationships	About 1000 loops for entities plus their attributes, plus 1500 loops for relationships

Pattern observation: The total work grows roughly in direct proportion to the number of entities and relationships.

Final Time Complexity

Time Complexity: O(n + m + a)

This means the time to convert grows linearly with the number of entities (n), relationships (m), and attributes (a).

Common Mistake

[X] Wrong: "The time grows much faster because each relationship connects multiple entities, so it's exponential."

[OK] Correct: Each relationship is handled once, so the work adds up linearly, not exponentially.

Interview Connect

Understanding how the conversion scales helps you explain database design steps clearly and shows you can think about efficiency in real projects.

Self-Check

"What if we had to handle many-to-many relationships by creating extra join tables? How would that affect the time complexity?"