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

Practice

1. In converting an ER diagram to a relational schema, how is a one-to-many relationship typically represented?

easy

A. Add a foreign key in the table on the 'many' side referencing the 'one' side

B. Create a new table for the relationship

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

D. Merge both entities into a single table

Solution

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

   In a one-to-many relationship, one entity instance relates to many instances of another entity.

2. Step 2: Represent relationship in relational schema

   The foreign key is placed in the table representing the 'many' side, pointing to the 'one' side's primary key.

3. Final Answer:

   Add a foreign key in the table on the 'many' side referencing the 'one' side -> Option A

4. Quick Check:

   One-to-many = foreign key on many side [OK]

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

Common Mistakes:

• Placing foreign key on the 'one' side
• Creating unnecessary new tables for one-to-many
• Merging entities incorrectly

2. Which of the following is the correct way to represent a many-to-many relationship in a relational schema?

easy

A. Add foreign keys in both entity tables referencing each other

B. Merge both entities into a single table

C. Create a new table with foreign keys referencing both entities

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

Solution

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

   Many-to-many means multiple instances of one entity relate to multiple instances of another.

2. Step 2: Represent many-to-many in relational schema

   Create a new table (junction table) with foreign keys referencing the primary keys of both entities.

3. Final Answer:

   Create a new table with foreign keys referencing both entities -> Option C

4. Quick Check:

   Many-to-many = new junction table [OK]

Hint: Use a new table for many-to-many relationships [OK]

Common Mistakes:

• Adding foreign keys directly in entity tables
• Merging entities incorrectly
• Ignoring the need for a junction table

3. Given an ER diagram with entities Student(SID, Name) and Course(CID, Title) connected by a many-to-many relationship Enrolls, which relational schema correctly represents this?

medium

A. Student(SID, Name), Course(CID, Title, SID), Enrolls(SID, CID)

B. Student(SID, Name), Course(CID, Title), Enrolls(SID, CID)

C. Student(SID, Name, CID), Course(CID, Title)

D. Student(SID, Name), Course(CID, Title)

Solution

1. Step 1: Identify entities and relationship type

   Student and Course are entities; Enrolls is many-to-many between them.

2. Step 2: Convert entities and relationship to tables

   Student and Course become tables with their attributes. Enrolls becomes a new table with foreign keys SID and CID.

3. Final Answer:

   Student(SID, Name), Course(CID, Title), Enrolls(SID, CID) -> Option B

4. Quick Check:

   Many-to-many needs separate table [OK]

Hint: Many-to-many always needs a separate table [OK]

Common Mistakes:

• Adding foreign key in Course for Student
• Adding foreign key in Student for Course
• Omitting the Enrolls table

4. You converted an ER diagram with a one-to-one relationship between Person and Passport by adding a foreign key PersonID in Passport. However, the database allows multiple passports for one person. What is the likely mistake?

medium

A. Foreign key in Passport lacks a UNIQUE constraint

B. Foreign key should be in Person table, not Passport

C. Passport table should be merged with Person table

D. PersonID should be primary key in Passport table

Solution

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

   One-to-one means each person has at most one passport and vice versa.

2. Step 2: Check foreign key constraints

   Foreign key alone allows many passports per person unless a UNIQUE constraint is added to enforce one-to-one.

3. Final Answer:

   Foreign key in Passport lacks a UNIQUE constraint -> Option A

4. Quick Check:

   One-to-one needs UNIQUE foreign key [OK]

Hint: Add UNIQUE to foreign key for one-to-one [OK]

Common Mistakes:

• Assuming foreign key alone enforces one-to-one
• Placing foreign key in wrong table
• Merging tables unnecessarily

5. An ER diagram has entities Author(AID, Name), Book(BID, Title), and a many-to-many relationship Writes with an attribute RoyaltyPercentage. How should you convert this to a relational schema?

hard

A. Create Author(AID, Name), Book(BID, Title), Writes(AID, BID)

B. Create Author(AID, Name), Book(BID, Title, RoyaltyPercentage), Writes(AID, BID)

C. Create Author(AID, Name, RoyaltyPercentage), Book(BID, Title), Writes(AID, BID)

D. Create Author(AID, Name), Book(BID, Title), Writes(AID, BID, RoyaltyPercentage)

Solution

1. Step 1: Identify entities and relationship with attribute

   Author and Book are entities; Writes is many-to-many with attribute RoyaltyPercentage.

2. Step 2: Convert entities and relationship with attribute

   Entities become tables with their attributes. The many-to-many relationship becomes a new table including foreign keys and the attribute RoyaltyPercentage.

3. Final Answer:

   Create Author(AID, Name), Book(BID, Title), Writes(AID, BID, RoyaltyPercentage) -> Option D

4. Quick Check:

   Relationship attributes go in junction table [OK]

Hint: Put relationship attributes in the new junction table [OK]

Common Mistakes:

• Adding relationship attribute to entity tables
• Omitting the junction table
• Placing attribute in wrong table