Types of databases (relational, NoSQL, object-oriented) in DBMS Theory - Time & Space Complexity

Time Complexity: Types of databases (relational, NoSQL, object-oriented)

O(log n)

Understanding Time Complexity

We want to understand how the time it takes to work with different types of databases changes as the amount of data grows.

How does the database type affect the speed of finding or saving data?

Scenario Under Consideration

Analyze the time complexity of basic data retrieval in different database types.

-- Relational database query example
SELECT * FROM users WHERE id = 123;

-- NoSQL document lookup example
db.users.find({"id": 123});

-- Object-oriented database object retrieval
user = db.getObjectById("User", 123);

These commands get a user record by ID from three database types.

Identify Repeating Operations

Look at what happens when the database searches for the user.

• Primary operation: Searching through data entries to find a match.
• How many times: Depends on data size; the database may check many records.

How Execution Grows With Input

As the number of users grows, the search work changes differently for each database type.

Input Size (n)	Approx. Operations
10	Few checks, very fast
100	More checks, still quick
1000	Many checks, time grows

Relational databases often use indexes to keep search fast even as data grows. NoSQL may vary by type; some are very fast for certain queries. Object-oriented databases depend on how objects are linked.

Final Time Complexity

Time Complexity: O(log n)

This means that as data grows, the time to find a record grows slowly, usually doubling data size adds only a little more time.

Common Mistake

[X] Wrong: "All databases take the same time to find data regardless of type."

[OK] Correct: Different database types organize data differently, so their search speeds change differently as data grows.

Interview Connect

Knowing how database types affect search speed helps you explain your choices clearly and shows you understand how data size impacts performance.

Self-Check

"What if we added an index to the NoSQL database? How would the time complexity change?"

Practice

1. Which type of database stores data in tables and uses SQL for queries?

easy

A. Object-oriented database

B. NoSQL database

C. Graph database

D. Relational database

Solution

1. Step 1: Understand database types

   Relational databases organize data in tables with rows and columns.

2. Step 2: Identify query language

   They use SQL (Structured Query Language) to manage and query data.

3. Final Answer:

   Relational database -> Option D

4. Quick Check:

   Tables + SQL = Relational database [OK]

Hint: Tables and SQL mean relational database [OK]

Common Mistakes:

• Confusing NoSQL with relational because both store data
• Thinking object-oriented databases use SQL
• Assuming graph databases are relational

2. Which of the following is the correct way to describe a NoSQL database?

easy

A. Stores flexible data like documents or key-value pairs

B. Stores data only in tables with fixed schema

C. Stores data as objects matching programming languages

D. Uses only SQL for data queries

Solution

1. Step 1: Recall NoSQL database features

   NoSQL databases store data flexibly, often as documents or key-value pairs.

2. Step 2: Eliminate incorrect options

   They do not require fixed schemas or only tables, and do not rely solely on SQL.

3. Final Answer:

   Stores flexible data like documents or key-value pairs -> Option A

4. Quick Check:

   No fixed schema + flexible data = NoSQL [OK]

Hint: Flexible data storage means NoSQL [OK]

Common Mistakes:

• Thinking NoSQL uses only tables
• Confusing object-oriented with NoSQL
• Assuming NoSQL requires SQL queries

3. Given the following description, which database type fits best?
Data is stored as objects with properties and methods, similar to programming languages.

medium

A. Relational database

B. NoSQL database

C. Object-oriented database

D. Hierarchical database

Solution

1. Step 1: Analyze data storage style

   The data is stored as objects with properties and methods, matching programming language objects.

2. Step 2: Match to database type

   Object-oriented databases store data as objects, unlike relational or NoSQL databases.

3. Final Answer:

   Object-oriented database -> Option C

4. Quick Check:

   Objects with methods = Object-oriented database [OK]

Hint: Objects with methods mean object-oriented DB [OK]

Common Mistakes:

• Confusing object-oriented with NoSQL
• Thinking relational databases store objects
• Assuming hierarchical is object-oriented

4. Identify the error in this statement:
NoSQL databases always use SQL queries to retrieve data.

medium

A. No error, statement is correct

B. NoSQL databases do not use SQL queries

C. NoSQL databases only store data in tables

D. NoSQL databases are a type of relational database

Solution

1. Step 1: Understand NoSQL query methods

   NoSQL databases typically use query methods other than SQL, like JSON queries or key-value lookups.

2. Step 2: Identify the error

   The statement wrongly claims NoSQL always uses SQL, which is false.

3. Final Answer:

   NoSQL databases do not use SQL queries -> Option B

4. Quick Check:

   NoSQL ≠ SQL queries [OK]

Hint: NoSQL means no SQL queries [OK]

Common Mistakes:

• Believing NoSQL uses SQL
• Confusing NoSQL with relational
• Thinking NoSQL stores only tables

5. A company wants to store user profiles with flexible fields that can change often, and also wants to store some complex objects with methods for processing. Which combination of databases should they use?

hard

A. A NoSQL database for flexible data and an object-oriented database for complex objects

B. Only a relational database

C. Only a NoSQL database

D. Only an object-oriented database

Solution

1. Step 1: Analyze data needs

   Flexible fields suggest NoSQL for schema flexibility; complex objects with methods suggest object-oriented database.

2. Step 2: Choose suitable combination

   Using both NoSQL and object-oriented databases fits the requirements best.

3. Final Answer:

   A NoSQL database for flexible data and an object-oriented database for complex objects -> Option A

4. Quick Check:

   Flexible + complex objects = NoSQL + object-oriented [OK]

Hint: Use NoSQL for flexible, object-oriented for complex objects [OK]

Common Mistakes:

• Choosing only relational database ignoring flexibility
• Using only NoSQL and ignoring object methods
• Assuming object-oriented alone handles flexible fields