NoSQL database types (document, key-value, column, graph) in DBMS Theory - Time & Space Complexity

Time Complexity: NoSQL database types (document, key-value, column, graph)

O(1) for Key-Value and Document, O(log n) or O(1) for Column, O(k) for Graph

Understanding Time Complexity

When working with NoSQL databases, it's important to understand how the time to find or store data changes as the amount of data grows.

We want to know how fast different NoSQL types handle data operations as data size increases.

Scenario Under Consideration

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

-- Key-Value: Get value by key
GET key

-- Document: Find document by ID
FIND { _id: "123" }

-- Column: Retrieve column data by key
SELECT column FROM table WHERE key = '123'

-- Graph: Find node by ID
MATCH (n) WHERE n.id = '123' RETURN n
    

These commands show how each NoSQL type retrieves data by a key or ID.

Identify Repeating Operations

Look at what repeats when searching for data:

• Primary operation: Searching for a key or ID in the database.
• How many times: Ideally, once per query, but depends on data structure and indexing.

How Execution Grows With Input

As data grows, the time to find a key or document changes differently for each type.

Input Size (n)	Key-Value & Document	Column	Graph
10	Very fast (1-2 steps)	Fast (1-2 steps)	Fast (1-2 steps)
100	Still fast (few steps)	Still fast	More steps if many connections
1000	Fast (constant time)	Fast (constant or log time)	Slower if complex graph traversal

Pattern observation: Key-Value and Document types usually find data quickly regardless of size. Graph databases may take longer if many connections are checked.

Final Time Complexity

Time Complexity: O(1) for Key-Value and Document lookups, O(log n) or O(1) for Column stores with indexing, and O(k) for Graph traversals where k is number of connected nodes checked.

This means some NoSQL types find data instantly, while others take longer depending on connections.

Common Mistake

[X] Wrong: "All NoSQL databases find data instantly no matter what."

[OK] Correct: Some NoSQL types like graph databases must check many connections, so their search time grows with data complexity.

Interview Connect

Understanding how different NoSQL types handle data helps you explain trade-offs clearly and shows you know how data size affects performance.

Self-Check

"What if we added indexing to a graph database? How would that change the time complexity of searches?"

Practice

1. Which NoSQL database type is best suited for storing data as JSON-like documents with flexible schemas?

easy

A. Graph database

B. Document database

C. Column database

D. Key-value database

Solution

1. Step 1: Understand document database structure

   Document databases store data as documents, often JSON-like, allowing flexible and nested data.

2. Step 2: Compare with other NoSQL types

   Key-value stores use simple key-value pairs, column stores organize data by columns, and graph databases focus on relationships.

3. Final Answer:

   Document database -> Option B

4. Quick Check:

   Flexible JSON-like storage = Document database [OK]

Hint: JSON-like flexible data means document DB [OK]

Common Mistakes:

• Confusing key-value with document stores
• Thinking column stores handle JSON
• Assuming graph DB stores documents

2. Which of the following is the correct way to describe a key-value store?

easy

A. Stores data as nested JSON documents

B. Stores data as interconnected nodes and edges

C. Stores data in tables with rows and columns

D. Stores data as simple pairs of keys and values

Solution

1. Step 1: Define key-value store

   Key-value stores save data as pairs: a unique key and its associated value.

2. Step 2: Eliminate other options

   Nodes and edges describe graph DB, tables describe relational or column DB, nested JSON describes document DB.

3. Final Answer:

   Stores data as simple pairs of keys and values -> Option D

4. Quick Check:

   Key-value = key and value pairs [OK]

Hint: Key-value means simple pairs, not complex structures [OK]

Common Mistakes:

• Mixing graph DB with key-value store
• Confusing column DB with key-value
• Thinking document DB is key-value

3. Given a graph database storing people and their friendships, which query result would you expect from a query asking for all friends of 'Alice'?

medium

A. A set of nodes connected to 'Alice' by edges labeled 'friend'

B. A table with columns for friend names and ages

C. A list of key-value pairs with friend names

D. A JSON document containing Alice's profile

Solution

1. Step 1: Understand graph database query

   Graph DB queries return nodes and edges; friends of Alice are nodes connected by 'friend' edges.

2. Step 2: Compare expected outputs

   Key-value pairs or tables are not typical graph DB outputs; JSON document is for document DB.

3. Final Answer:

   A set of nodes connected to 'Alice' by edges labeled 'friend' -> Option A

4. Quick Check:

   Graph DB returns connected nodes and edges [OK]

Hint: Graph DB queries return nodes and edges, not tables or JSON [OK]

Common Mistakes:

• Expecting tabular output from graph DB
• Confusing document DB JSON with graph DB output
• Thinking key-value pairs represent graph edges

4. You wrote a query to retrieve data from a column-family NoSQL database but got an error. Which mistake likely caused this?

medium

A. Using nested JSON documents in the query

B. Querying nodes and edges instead of tables

C. Trying to access data by key only without specifying column family

D. Using key-value pairs without keys

Solution

1. Step 1: Understand column-family DB query requirements

   Column-family DBs require specifying column families to access data properly.

2. Step 2: Identify error cause

   Accessing data by key alone without column family causes errors; other options relate to different DB types or invalid syntax.

3. Final Answer:

   Trying to access data by key only without specifying column family -> Option C

4. Quick Check:

   Column DB needs column family in queries [OK]

Hint: Column DB queries must specify column family [OK]

Common Mistakes:

• Using document DB JSON syntax in column DB
• Ignoring column family in queries
• Confusing graph DB queries with column DB

5. You need to design a social network app that stores users, their posts, and complex friend relationships with recommendations. Which NoSQL database type should you choose and why?

hard

A. Graph database, because it efficiently manages complex relationships

B. Key-value database, because it is fastest for any data

C. Document database, because it handles nested posts well

D. Column database, because it stores large tables efficiently

Solution

1. Step 1: Analyze app data needs

   The app needs to store users, posts, and complex friend relationships with recommendations.

2. Step 2: Match database type to needs

   Graph DBs excel at managing complex relationships and traversals, ideal for social networks.

3. Step 3: Evaluate other options

   Document DB handles nested data but less efficient for relationships; key-value is simple but not relationship-focused; column DB is for wide tables, not relationships.

4. Final Answer:

   Graph database, because it efficiently manages complex relationships -> Option A

5. Quick Check:

   Complex relationships = Graph DB [OK]

Hint: Complex relationships? Choose graph DB [OK]

Common Mistakes:

• Choosing document DB for relationship-heavy data
• Assuming key-value is best for all speed needs
• Ignoring graph DB strengths in relationships