Time Complexity: Why the relational model dominates databases
O(n)
0
0
Why the relational model dominates databases in DBMS Theory - Performance Analysis
Understanding Time Complexity
We want to understand how the relational model handles data operations as the amount of data grows.
How does the time to perform common tasks change when the database gets bigger?
Scenario Under Consideration
Analyze the time complexity of a simple SQL query on a relational database.
SELECT * FROM Employees WHERE Department = 'Sales';
This query retrieves all employees who work in the Sales department from a table.
Identify Repeating Operations
Look at what the database does to find matching rows.
- Primary operation: Scanning rows to check the Department value.
- How many times: Once for each row in the Employees table.
How Execution Grows With Input
As the number of employees grows, the database checks more rows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The work grows directly with the number of rows.
Final Time Complexity
Time Complexity: O(n)
This means the time to find matching rows grows in a straight line as the table gets bigger.
Common Mistake
[X] Wrong: "The database instantly finds the rows no matter how big the table is."
[OK] Correct: Without special help like indexes, the database must check each row one by one, so bigger tables take more time.
Interview Connect
Understanding how queries scale with data size shows you know what affects database speed and helps you design better systems.
Self-Check
"What if we added an index on the Department column? How would the time complexity change?"