Top 50 - Part 2

1. What is the purpose of the Data Dictionary (or System Catalog) in a DBMS?

The Data Dictionary, also called the System Catalog, stores metadata — information about the database and its objects.

It typically contains information about:

• Tables and columns
• Data types
• Primary and foreign keys
• Constraints
• Indexes
• Views
• Users, roles, and privileges
• Other database objects

The DBMS uses this metadata to understand the database structure and decide how to execute queries.

Example: When you create a table using CREATE TABLE, information about that table is recorded in the system catalog.

Easy way to remember: Data Dictionary = data about the data.

---

2. What is the difference between a Physical View and a Logical View of data?

They describe data at different levels of abstraction.

• Physical view — describes how data is actually stored, such as files, pages, blocks, indexes, and storage structures.
• Logical view — describes what data exists and how it is related, such as tables, columns, relationships, and constraints.

User/Application
       ↓
Logical View
(tables, columns, relationships)
       ↓
Physical View
(files, pages, indexes, storage)
       ↓
Disk

Users normally work with the logical view and do not need to know how the DBMS physically stores the data.

---

3. What is Cardinality in database design?

Cardinality describes how many instances of one entity can be associated with instances of another entity.

The common relationship types are:

• One-to-One (1:1) — one person has one passport.
• One-to-Many (1:N) — one customer can have many orders.
• Many-to-Many (M:N) — one student can take many courses, and one course can have many students.

For a many-to-many relationship, a junction (associative) table is normally required.

Students ───< Enrollments >─── Courses

Cardinality is an important part of database design because it determines how relationships and foreign keys are structured.

Note: In some DBMS contexts, “cardinality” can also mean the number of distinct values in a column. In ER/database-design questions, however, it commonly refers to relationship cardinality.

---

4. What is a ‘Phantom Read’ anomaly in a database?

A phantom read occurs when a transaction executes the same query twice and gets a different set of rows because another transaction inserted, deleted, or modified rows that satisfy the query condition.

Example:

1. T1 queries all pending orders → 3 rows.
2. T2 inserts another pending order and commits.
3. T1 runs the same query again → 4 rows.

The newly appearing row is called a phantom row.

T1: SELECT pending orders → 3 rows
T2: INSERT pending order → COMMIT
T1: SELECT pending orders → 4 rows
                         ↑
                    Phantom row

The SERIALIZABLE isolation level prevents phantom reads by providing the strongest transaction isolation. The exact mechanism used to achieve this depends on the DBMS; it may involve predicate/range locking or other serialization techniques.

---

5. What is an Anti-Join conceptually in relational algebra?

An anti-join returns rows from one relation that have no matching row in another relation.

In SQL, it is commonly implemented using NOT EXISTS or sometimes NOT IN.

SELECT *
FROM customers c
WHERE NOT EXISTS (
    SELECT 1
    FROM orders o
    WHERE o.customer_id = c.id
);

This returns customers who have never placed an order.

Remember:

JOIN      → rows that HAVE a match
ANTI-JOIN → rows that DO NOT have a match

NOT EXISTS is generally safer than NOT IN when NULLs may be present in the subquery.

---

6. What is Database Partitioning? Explain its types.

Database partitioning divides a large table or index into smaller logical pieces called partitions. The partitions are managed by the same database system.

Common types include:

• Range Partitioning — rows are divided according to ranges.

  2023 → Partition 1
  2024 → Partition 2
  2025 → Partition 3

• List Partitioning — rows are divided according to specific values.

  North → Partition 1
  South → Partition 2
  East  → Partition 3

• Hash Partitioning — a hash function distributes rows across partitions.

• Composite Partitioning — combines multiple partitioning strategies, such as range + hash.

A major benefit is partition pruning: if a query only needs one partition, the DBMS may avoid scanning the others.

Partitioning ≠ Sharding: partitioning can occur within one database system, whereas sharding distributes data across multiple database servers/nodes.

---

7. Why are B-Trees or B+ Trees preferred over Binary Search Trees for database indexing?

The main reason is reduced disk I/O.

A traditional binary search tree has only a small number of children per node, while a B-tree/B+ tree has a high branching factor. Therefore, it can store many keys in each node and remain relatively shallow.

Binary Search Tree:
          50
        /    \
      25      75
     /  \    /  \
   ...  ... ...  ...

B+ Tree:
       [30 | 60 | 90]
      /    |    |    \
   many  many  many  many
   keys  keys  keys  keys

Fewer levels mean fewer page accesses when searching.

B+ trees have another major advantage: their leaf nodes are typically linked, making range queries and sequential scans efficient.

SELECT *
FROM employees
WHERE salary BETWEEN 50000 AND 70000;

A B+ tree can efficiently locate the starting point and then scan the linked leaf nodes.

---

8. What is a Livelock? How is it different from a Deadlock?

Both are concurrency problems, but the processes behave differently.

• Deadlock — processes are blocked and waiting for resources held by each other.
• Livelock — processes remain active and keep changing/retrying, but make no useful progress.

Analogy:

Two people in a hallway:

• Deadlock: both stand still, each waiting for the other to move.
• Livelock: both repeatedly move left and right trying to avoid each other, but neither gets through.

Deadlock → waiting, no progress
Livelock  → activity, but no progress

Livelock can often be reduced using techniques such as randomized backoff, retry limits, or better scheduling.

---

9. What is the difference between Sharding and Partitioning?

Both divide data, but they operate at different levels.

• Partitioning — divides a table into smaller partitions within a database system.
• Sharding — distributes portions of the data across multiple database servers or nodes.

Partitioning:

One Database Server
 ├── Partition 1
 ├── Partition 2
 └── Partition 3


Sharding:

Server A → Users 1–1M
Server B → Users 1M–2M
Server C → Users 2M–3M

Partitioning can improve query performance and manageability.

Sharding is primarily used to scale storage and workload across multiple machines.

Sharding introduces additional complexity, such as routing, cross-shard queries, distributed transactions, and rebalancing.

---

10. What does the CAP Theorem state for distributed data stores?

The CAP Theorem states that during a network partition, a distributed system cannot simultaneously guarantee both:

• Consistency (C) — every read sees the appropriate/latest value according to the system’s consistency guarantee.
• Availability (A) — every request to a non-failing node receives a response.
• Partition Tolerance (P) — the system continues operating despite network communication failures between nodes.

Because network partitions cannot simply be ignored in a distributed system, the practical trade-off during a partition is generally:

Network Partition
       ↓
   C  OR  A

• CP — favors consistency and may reject/delay some requests during a partition.
• AP — favors availability and may temporarily return inconsistent/stale data.

Important: CAP is specifically about behavior when a partition occurs. It does not mean a system simply picks any two properties at all times.

---

11. What is the role of a Write-Ahead Log (WAL) in a transaction engine?

A Write-Ahead Log (WAL) records changes in a durable log before the corresponding database data pages are written to their final storage locations.

The fundamental rule is:

The log must be safely persisted before the associated data change is considered durable.

If the system crashes, the DBMS can use the log during recovery to redo committed changes and, depending on the logging/recovery design, undo or otherwise handle incomplete transactions.

Transaction
    ↓
Write log record
    ↓
Persist log
    ↓
Data pages can be written later
    ↓
Crash?
    ↓
Recovery using WAL

WAL improves performance because the system doesn’t need to immediately flush every modified data page to durable storage at commit time.

---

12. What is the difference between Optimistic and Pessimistic Concurrency Control?

The key difference is how they handle conflicts.

• Pessimistic concurrency control assumes conflicts are likely and uses locks to prevent conflicting operations while they are occurring.
• Optimistic concurrency control assumes conflicts are relatively rare, so transactions proceed with fewer locks and conflicts are detected during validation/commit.

	Pessimistic	Optimistic
Basic idea	Prevent conflicts	Detect conflicts
Locking	More locking	Often little/no locking during reads
Best when	High contention	Low contention
Conflict	Wait/block	Retry/rollback

Example:

If two users frequently update the same inventory row, pessimistic locking may be appropriate.

If many users mostly read data and conflicts are rare, optimistic concurrency can avoid unnecessary locking.

---

13. What does the ‘Consistency’ property in ACID mean?

Consistency means that a transaction takes the database from one valid state to another valid state, preserving all defined integrity constraints and business rules enforced by the database.

These may include:

• Primary-key uniqueness
• Foreign-key constraints
• NOT NULL
• CHECK constraints
• Other application/database rules

Example:

Suppose a transaction transfers ₹500 from Account A to Account B.

Before:

A = ₹5000
B = ₹3000
Total = ₹8000

After a successful transfer:

A = ₹4500
B = ₹3500
Total = ₹8000

The database remains in a valid state.

Important distinction: ACID Consistency is not the same thing as consistency in the CAP theorem. ACID consistency concerns database integrity rules; CAP consistency concerns what values distributed nodes return.

---

14. What is a ‘Cascading Rollback’ in transaction execution?

A cascading rollback occurs when one transaction is rolled back and causes other transactions to roll back because they depended on its uncommitted data.

Example:

T1 writes X
     ↓
T2 reads X before T1 commits
     ↓
T1 rolls back
     ↓
T2's result is now based on invalid data
     ↓
T2 must also roll back

If T3 had read data produced by T2, T3 might also need to roll back.

This is why schedules that allow dirty reads can lead to cascading rollbacks.

Avoidance: use a recoverable/strict concurrency-control strategy and isolation levels that prevent transactions from reading uncommitted changes.

---

15. What is a Lossless-Join Decomposition?

A lossless-join decomposition is a decomposition of a relation into smaller relations such that joining those relations reconstructs exactly the original relation, without losing information or creating spurious tuples.

Suppose:

R(A, B, C)

is decomposed into:

R1(A, B)
R2(B, C)

When we join R1 and R2 on B, the result should be exactly the original R.

R1 ⋈ R2 = R

A common sufficient condition for a binary decomposition R → R1, R2 to be lossless is that the common attributes

R1 ∩ R2

functionally determine all attributes of R1 or all attributes of R2.

In other words, the common attributes must function as a superkey of at least one decomposed relation.

Why it matters: normalization should produce decompositions that preserve the original information and do not generate false/spurious rows when the tables are joined back together.