Database Management Systems

A Database Management System (DBMS) is software that manages structured data. It provides mechanisms to store, retrieve, update, and delete data while ensuring data integrity, security, concurrency control, and durability. A DBMS separates how data is stored from how it's accessed — the physical storage is hidden behind a query interface.

DBMS vs flat files: A flat file stores records in plain text (CSV, JSON lines). You'd need to write custom code for every access pattern, handle concurrent writes manually, implement your own indexing, and risk data corruption on crashes. A DBMS handles all of this: declarative queries (SQL), concurrent access by thousands of clients, automatic indexing, crash recovery via write-ahead logs, and role-based access control.

Types of databases:

• Relational (RDBMS) — data in tables with rows and columns, relationships via foreign keys, queried with SQL. ACID guarantees. Examples: PostgreSQL, MySQL, Oracle, SQL Server, SQLite. Best for: structured data with complex relationships, transactions, reporting.
• Document — stores semi-structured documents (JSON/BSON). Flexible schema. Examples: MongoDB, CouchDB, Firestore. Best for: catalogs, user profiles, content management, heterogeneous data.
• Key-Value — simplest model: key maps to value (any blob). Ultra-fast lookups. Examples: Redis, DynamoDB, Riak. Best for: caching, sessions, leaderboards, shopping carts.
• Wide-Column — rows with dynamic columns, grouped into column families. Examples: Apache Cassandra, HBase, Google Bigtable. Best for: time-series, IoT, write-heavy workloads at massive scale.
• Graph — nodes and edges with properties. Optimized for traversal queries. Examples: Neo4j, Amazon Neptune, JanusGraph. Best for: social networks, fraud detection, recommendation engines, knowledge graphs.
• Search engines — inverted indexes for full-text search. Examples: Elasticsearch, Apache Solr, Meilisearch. Best for: autocomplete, log analytics, e-commerce search.
• Time-Series — optimized for time-stamped data, efficient aggregation over time windows. Examples: InfluxDB, TimescaleDB, Prometheus. Best for: metrics, monitoring, financial data.
• NewSQL — relational model + horizontal scalability. Examples: CockroachDB, TiDB, Google Spanner. Best for: globally distributed transactional workloads.

The relational model (E.F. Codd, 1970) organizes data into tables (relations) consisting of rows (tuples) and columns (attributes). Each column has a defined data type. A table has no inherent order of rows — order is specified at query time with ORDER BY.

Keys:

• Primary Key (PK) — uniquely identifies each row. Cannot be NULL. Each table has exactly one PK. Can be a single column (user_id) or composite (order_id, product_id).
• Foreign Key (FK) — a column (or set) that references the PK of another table. Enforces referential integrity: you can't insert a row with a FK value that doesn't exist in the referenced table (unless deferred). ON DELETE CASCADE / SET NULL / RESTRICT control what happens when the referenced row is deleted.
• Candidate Key — any minimal set of columns that could serve as a PK. A table can have multiple candidate keys; one is chosen as the PK, others become unique keys.
• Composite Key — PK or unique key made of multiple columns. Common in junction tables (user_id + role_id).
• Surrogate Key — system-generated identifier (auto-increment integer, UUID). Has no business meaning. Preferred over natural keys for stability.
• Natural Key — a key derived from real-world data (email, SSN, ISBN). Can change, which cascades to all FKs.

Constraints: NOT NULL (column must have a value), UNIQUE (all values in a column must differ), CHECK (column value must satisfy an expression, e.g. age > 0), DEFAULT (value if none provided), FOREIGN KEY (referential integrity).

Relational algebra operations: SELECT (σ, filter rows), PROJECT (π, select columns), JOIN (combine tables on condition), UNION (combine rows from two queries), INTERSECTION, DIFFERENCE, CARTESIAN PRODUCT. SQL is a declarative language built on these operations — the query optimizer decides how to execute them.

SQL (Structured Query Language) is the standard language for relational databases. It's declarative — you describe what you want, not how to get it.

SQL categories:

• DDL (Data Definition Language) — CREATE TABLE, ALTER TABLE, DROP TABLE, CREATE INDEX, TRUNCATE
• DML (Data Manipulation Language) — SELECT, INSERT, UPDATE, DELETE
• DCL (Data Control Language) — GRANT, REVOKE
• TCL (Transaction Control Language) — BEGIN, COMMIT, ROLLBACK, SAVEPOINT

SELECT query anatomy (execution order): FROM (which tables) → JOIN (combine rows) → WHERE (filter rows) → GROUP BY (aggregate groups) → HAVING (filter groups) → SELECT (choose columns) → DISTINCT → ORDER BY → LIMIT/OFFSET.

JOIN types:

• INNER JOIN — returns rows where the join condition matches in both tables. Missing matches excluded from both sides.
• LEFT JOIN — returns all rows from left table, matched rows from right. Right side is NULL where no match.
• RIGHT JOIN — opposite of LEFT JOIN.
• FULL OUTER JOIN — returns all rows from both tables. NULL where no match on either side.
• CROSS JOIN — Cartesian product. Every row from left × every row from right. No join condition.
• SELF JOIN — join a table to itself (e.g., finding employees and their managers in the same employees table).

Aggregate functions: COUNT(*), COUNT(col) (ignores NULLs), SUM, AVG, MIN, MAX. Used with GROUP BY. HAVING filters on aggregate results (WHERE filters before aggregation).

Window functions: Perform calculations across a set of rows related to the current row without collapsing them into one row (unlike GROUP BY). ROW_NUMBER(), RANK(), DENSE_RANK(), NTILE(), LAG(), LEAD(), SUM() OVER (PARTITION BY … ORDER BY …). Extremely useful for running totals, moving averages, percentile rank.

Subqueries: A query nested inside another. Correlated subquery references the outer query — executes once per outer row (can be slow). EXISTS checks if a subquery returns any rows. CTEs (WITH clause) name subqueries for readability and reuse. Recursive CTEs traverse hierarchical data (org charts, graph traversal).

NULL handling: NULL ≠ NULL in SQL. Use IS NULL / IS NOT NULL. Any arithmetic with NULL returns NULL. Use COALESCE(col, default) to substitute a default. COUNT(*) counts all rows; COUNT(col) skips NULLs.

Normalization is the process of organizing a database schema to reduce data redundancy and improve data integrity. Each normal form builds on the previous. Higher normal forms reduce anomalies at the cost of more joins.

1NF (First Normal Form): Each column contains atomic (indivisible) values. No repeating groups. Each row is uniquely identifiable by a primary key. Violation: storing "phone1, phone2" in one column, or having columns phone_1, phone_2, phone_3.

2NF (Second Normal Form): Must be in 1NF. Every non-key attribute is fully functionally dependent on the entire primary key (no partial dependencies). Applies only when the PK is composite. Violation: table (order_id, product_id, quantity, product_name) — product_name depends only on product_id, not the full PK. Fix: separate products table.

3NF (Third Normal Form): Must be in 2NF. No transitive dependencies — non-key attributes must not depend on other non-key attributes. Violation: table (employee_id, department_id, department_name) — department_name depends on department_id, not employee_id. Fix: separate departments table.

BCNF (Boyce-Codd Normal Form): Stricter version of 3NF. For every functional dependency X → Y, X must be a superkey. BCNF eliminates anomalies 3NF misses in tables with multiple overlapping candidate keys.

4NF and 5NF deal with multi-valued dependencies and join dependencies — rarely needed in practice.

Denormalization: Intentionally introducing redundancy to improve read performance. Add a redundant column to avoid a JOIN. Maintain aggregated counts in a separate column. Pre-compute derived values. Trade-off: faster reads, slower writes, risk of inconsistency. Common in data warehouses (star schema) and high-read systems (caching aggregates in Redis).

Update anomalies that normalization prevents: Insertion anomaly (can't insert data without unrelated data), Update anomaly (updating one fact requires updating multiple rows), Deletion anomaly (deleting a row deletes unintended information).

ACID properties guarantee that database transactions are processed reliably, especially in the face of errors, crashes, and concurrent access.

Atomicity: A transaction is treated as a single unit — either all operations succeed and commit, or all fail and roll back. No partial state is left in the database. Implementation: write-ahead log (WAL) records all intended changes before applying them. On crash, incomplete transactions are rolled back during recovery.

Example: Bank transfer of $100 from Account A to Account B. Two operations: debit A, credit B. Atomicity ensures you can't debit A without crediting B (or vice versa). Without atomicity, a crash between the two operations leaves $100 missing.

Consistency: A transaction brings the database from one valid state to another. All defined constraints (NOT NULL, UNIQUE, FK, CHECK) and business rules are satisfied before and after the transaction. Consistency is partially enforced by the database (constraints) and partially by the application (business logic).

Example: A constraint says account balance ≥ 0. A transaction attempting to overdraw is rejected — the database remains consistent.

Isolation: Concurrent transactions execute as if they were serial — one transaction cannot see uncommitted changes from another (at default isolation levels). Prevents dirty reads, non-repeatable reads, and phantom reads. Implementation: locks (two-phase locking), MVCC (Multi-Version Concurrency Control — readers don't block writers, each transaction sees a snapshot).

Example: Two users simultaneously booking the last ticket. Isolation ensures only one succeeds — neither sees the other's uncommitted state.

Durability: Once a transaction commits, its changes are permanent — even if the system crashes immediately after. Implementation: write-ahead logging (WAL). Changes are first written to the log (a sequential append — fast), then checkpointed to the actual data files. On crash, the log is replayed. fsync() ensures the log is on durable storage before acknowledging the commit.

Concurrency anomalies:

• Dirty Read — Transaction T2 reads data written by T1 before T1 commits. If T1 rolls back, T2 has read data that never existed.
• Non-Repeatable Read — T1 reads a row. T2 updates and commits that row. T1 reads the same row again and gets a different value. The row changed mid-transaction.
• Phantom Read — T1 runs a query returning N rows. T2 inserts rows matching T1's query and commits. T1 runs the same query and gets N+K rows. New "phantom" rows appeared.
• Lost Update — Two transactions read the same value, both modify it, and one's update is overwritten by the other.
• Dirty Write — T1 and T2 both write to the same row before either commits. One's write overwrites the other's uncommitted write.

Isolation levels (SQL standard, weakest to strongest):

Two-Phase Locking (2PL): A transaction acquires all locks it needs (growing phase) before releasing any (shrinking phase). Prevents dirty reads and lost updates. Strict 2PL: hold all write locks until commit — prevents cascading aborts. Deadlocks are possible; detected with a wait-for graph and resolved by aborting one transaction.

MVCC (Multi-Version Concurrency Control): Each write creates a new version of the row; old versions are kept. Readers see a consistent snapshot of the database at the time their transaction started — they never block on writers. Writers don't block readers. PostgreSQL, MySQL InnoDB, and Oracle all use MVCC. Old versions are cleaned up by a vacuum/garbage collection process.

Optimistic vs Pessimistic Concurrency: Pessimistic locking acquires locks upfront, assuming conflict is likely. Optimistic concurrency control (OCC) makes changes without locking, then validates at commit time — if another transaction modified the same data, abort and retry. OCC works well for low-contention workloads. SELECT … FOR UPDATE is pessimistic; version/timestamp checks are optimistic.

An index is a data structure that improves the speed of data retrieval. Without an index, a query that filters on a column requires a full table scan — O(N) rows read. With an appropriate index, the same lookup is O(log N) or O(1).

B+Tree index: The default in PostgreSQL, MySQL, SQL Server, Oracle. A balanced tree where all data pointers are in leaf nodes, and leaf nodes are linked for range scans. Supports: equality (=), range (<, >, BETWEEN), prefix (LIKE 'abc%'), ORDER BY, GROUP BY. O(log N) for all operations. Works well for both sequential writes (inserts are amortized) and reads.

Hash index: A hash table mapping key → row location. O(1) average lookup. Only supports equality (=). Cannot support range queries or sorting. MySQL MEMORY engine supports hash indexes; PostgreSQL has hash indexes but B+Tree is usually preferred. Useful for: exact lookups in memory (hash join in query execution).

Clustered vs Non-Clustered index:

• Clustered — the table data rows are physically stored in index order. There can only be one clustered index per table (there's only one physical order). In MySQL InnoDB, the primary key is always the clustered index. Excellent for range scans on the clustered key — rows are stored contiguously.
• Non-Clustered (Secondary) — a separate data structure containing the indexed columns plus a pointer to the full row (the clustered key in InnoDB, or a physical row ID in PostgreSQL heap). A table can have many secondary indexes. Lookups require: find the secondary index entry → follow pointer → fetch actual row (two lookups unless covering index).

Covering index: An index that contains all columns needed by a query — the query is satisfied entirely from the index without reading the actual row. Example: index on (user_id, status, created_at) covers SELECT status, created_at FROM orders WHERE user_id = 42. Eliminates the "double lookup" for secondary indexes.

Composite index: An index on multiple columns (col1, col2, col3). The leftmost prefix rule: the index can be used for queries on (col1), (col1, col2), or (col1, col2, col3), but NOT on (col2) alone or (col2, col3). The order of columns matters enormously. Put the most selective column first, or the column that appears in the most WHERE clauses.

Index selectivity: How many distinct values exist in a column relative to total rows. High selectivity (many distinct values, like user_id) = good index candidate. Low selectivity (few distinct values, like boolean is_active) = poor index candidate — the optimizer may prefer a full table scan. Partial indexes (PostgreSQL: WHERE is_active = true) index only a subset of rows, reducing size and improving selectivity.

Index overhead: Indexes speed up reads but slow down writes — every INSERT, UPDATE, DELETE must update all relevant indexes. A table with 10 indexes has 10x more write work per row change. Don't over-index. Remove unused indexes.

Full-text index: Inverted index mapping words to the documents that contain them. Used for LIKE '%keyword%' queries (which can't use B+Tree). PostgreSQL has built-in full-text search. For production search, dedicated engines (Elasticsearch) are preferred.

The query optimizer transforms SQL into an efficient execution plan. It's a cost-based optimizer (CBO) — it estimates the cost of various plans using statistics (row counts, column cardinality, data distribution) and picks the cheapest one.

Execution plan: A tree of operators — Table Scan, Index Scan, Index Seek, Hash Join, Nested Loop Join, Merge Join, Sort, Aggregate. Use EXPLAIN (PostgreSQL/MySQL) or EXPLAIN ANALYZE (actually runs the query) to see the plan. Key things to look for: sequential scans on large tables (often means missing index), hash joins on very large inputs (memory spill), huge row count estimates (stale statistics).

Join algorithms:

• Nested Loop Join — for each row in the outer table, scan the inner table for matches. O(N×M). Efficient only if inner table is small or has an index on the join key. The default for small result sets.
• Hash Join — build a hash table from the smaller table on the join key, then probe it with the larger table. O(N+M) average. Efficient for large unsorted inputs. Requires memory for the hash table — if it spills to disk, performance degrades. Used when no useful index exists.
• Merge Join (Sort-Merge Join) — sort both tables on the join key, then merge them (like merge sort). O(N log N + M log M + N + M). Very efficient when both inputs are already sorted (sorted index, or ORDER BY). Good for large range joins.

Common causes of slow queries:

• Missing index on WHERE clause, JOIN condition, or ORDER BY column
• Implicitly casting a column in a WHERE clause (WHERE CAST(user_id AS VARCHAR) = '123') — prevents index use
• Leading wildcard in LIKE ('%keyword%') — can't use B+Tree index
• Function on indexed column (WHERE LOWER(email) = 'abc') — use functional index or store lowercase
• SELECT * — fetching unnecessary columns prevents covering indexes, increases I/O
• N+1 query problem — selecting N rows then running one query per row; fix with a JOIN or eager loading
• Stale statistics — ANALYZE (PostgreSQL) or ANALYZE TABLE (MySQL) updates optimizer statistics
• Joins on unindexed foreign keys — always index FK columns

NoSQL (Not only SQL) databases sacrifice some relational features (JOINs, full ACID, strict schema) in exchange for horizontal scalability, flexible schema, and optimized data models for specific access patterns.

Document Databases — MongoDB: Stores JSON-like documents (BSON). Documents in the same collection can have different fields. Query language supports embedded document queries, array operators, aggregation pipeline (map-reduce equivalent). No JOIN — embed related data or use application-level joins. Scales horizontally via sharding on a shard key. Supports multi-document ACID transactions since v4.0. Best for: product catalogs, user profiles, CMSs, any data that maps naturally to a document.

Key-Value — Redis: In-memory data structure store. Supports strings, hashes, lists, sets, sorted sets (ZSETs), streams, HyperLogLog. O(1) for most operations. Persistence options: RDB (periodic snapshots) and AOF (append-only file — WAL). Pub/Sub messaging. Lua scripting for atomic multi-step operations. Cluster mode for horizontal scaling. Best for: caching (most common use), sessions, rate limiting, real-time leaderboards (sorted sets), job queues.

Wide-Column — Apache Cassandra: Rows identified by a partition key (determines node placement via consistent hashing). Within a partition, rows are ordered by clustering columns. Optimized for time-series and write-heavy workloads. Writes go to a commit log + memtable, then flushed to SSTables. No single point of failure — masterless, every node is equal. Tunable consistency: ONE, QUORUM, ALL. Best for: IoT sensor data, messaging, activity tracking, anything with a natural time-series access pattern at scale.

Graph — Neo4j: Data stored as nodes (entities) and edges (relationships), each with properties. Cypher query language. Graph traversal is O(1) per hop (follows pointers) vs relational JOIN which requires scanning rows. Optimized for: social networks (friends-of-friends), fraud detection (follow money trails), recommendation engines, knowledge graphs. Poor fit for: flat tabular data, massive write throughput.

When to choose NoSQL:

• Need to scale writes horizontally across many nodes (Cassandra, MongoDB sharding)
• Data has variable or evolving schema (document DB)
• Access pattern is always by a single key (key-value store, Redis)
• Data is naturally hierarchical and never queried across documents (embed in document DB)
• Graph traversal is the primary access pattern (graph DB)
• Need ultra-low latency (sub-millisecond) with simple access patterns (Redis)

CAP Theorem (Brewer, 2000): A distributed data store can guarantee at most two of three properties simultaneously:

• Consistency (C) — every read receives the most recent write or an error. All nodes see the same data at the same time. (Note: CAP "consistency" ≠ ACID consistency.)
• Availability (A) — every request receives a response (not necessarily the most recent data). The system is always available, even if some nodes are down.
• Partition Tolerance (P) — the system continues operating despite network partitions (nodes can't communicate with each other).

Network partitions are inevitable in any distributed system (cables fail, switches drop packets). Therefore, every distributed system must be partition tolerant — the real choice is between CP and AP:

• CP systems — choose consistency over availability during a partition. If nodes can't synchronize, they refuse to respond (or return an error). Examples: HBase, Zookeeper, Redis Cluster (when quorum can't be reached), etcd, CockroachDB.
• AP systems — choose availability over consistency during a partition. All nodes respond with potentially stale data. Examples: Cassandra (with ONE consistency), DynamoDB (eventually consistent reads), CouchDB, Riak.

CAP limitations: CAP is binary and doesn't capture the nuance of real systems. PACELC (Abadi) extends it: even without partitions, there's a latency vs consistency trade-off. Systems like Spanner (Google) use synchronized clocks (TrueTime) to provide external consistency with global distribution — challenging the strict CAP framing.

BASE (Basically Available, Soft state, Eventually consistent): The alternative to ACID for distributed systems. Basically Available: the system always responds, even if data is stale or partial. Soft state: the system's state may change over time, even without new input, as updates propagate. Eventually consistent: given no new updates, all replicas converge to the same state eventually. BASE is the model behind Cassandra, DynamoDB, and most AP systems.

Eventual consistency in practice: DNS is eventually consistent (updates propagate in minutes to hours). Amazon shopping cart famously uses eventual consistency — it's ok for two sessions to temporarily show different cart states. Financial ledgers are NOT eventually consistent — strong consistency is required.

Replication copies the same data to multiple nodes for fault tolerance and read scaling. Sharding partitions different data across different nodes for write scaling and handling datasets larger than one node.

Replication topologies:

• Single-leader (Master-Slave) — one primary accepts all writes; replicas receive changes asynchronously (or synchronously). Reads can go to replicas (eventual consistency) or primary (strong consistency). Simple, most common. Failover: promote a replica if primary fails. Used by: MySQL primary-replica, PostgreSQL streaming replication.
• Multi-leader (Multi-Master) — multiple primaries accept writes. Changes replicated between primaries. Enables geo-distributed writes. Conflicts arise when two primaries modify the same row simultaneously — conflict resolution needed (last-write-wins, CRDTs, application logic). Used by: MySQL Group Replication, Galera Cluster, CouchDB.
• Leaderless (Quorum-based) — any node accepts reads and writes. Write succeeds if W nodes acknowledge. Read succeeds if R nodes respond. Strong consistency if W + R > N (replication factor). Used by: Cassandra (W=QUORUM, R=QUORUM is common), DynamoDB, Riak. Cassandra's read repair and anti-entropy ensure eventual convergence.

Replication lag: Asynchronous replication means replicas may be seconds behind the primary. Reading from a replica may return stale data. Critical operations (after a write, immediately read your own write) should read from primary. Monitoring replication lag is essential.

Sharding strategies:

• Range sharding — shard by range of key values. Users A–M → shard 1, N–Z → shard 2. Easy range queries within a shard. Risk: hotspots if data is skewed (all requests go to one shard).
• Hash sharding — shard = hash(key) % N. Even distribution. Eliminates hotspots. Range queries require hitting all shards. Hash(user_id) → shard.
• Consistent hashing — arrange nodes and keys on a ring. A key belongs to the first node clockwise from its hash position. Adding/removing a node only reassigns a fraction of keys (1/N), avoiding full reshuffling. Used by Cassandra, Amazon DynomoDB, Memcached. Virtual nodes (vnodes) improve distribution.
• Directory-based sharding — a lookup table maps keys to shards. Flexible — any key can be assigned to any shard. The directory itself is a bottleneck and single point of failure.

Vertical vs Horizontal scaling: Vertical (scale up): larger machines with more RAM/CPU/disk. Simple, no distribution complexity. Hard ceiling. Horizontal (scale out): add more machines. Complex: data distribution, consistency, distributed transactions. Theoretically unlimited scale. Most NoSQL databases are designed for horizontal scaling.

Hot shard problem: A shard receiving disproportionate traffic (a viral user, a popular product). Solutions: split the hot shard, use caching (Redis) in front, shard more granularly, or introduce a per-entity rate limiter.

SQL Injection: One of the most dangerous vulnerabilities. An attacker injects SQL code through user input, manipulating the query logic.

Vulnerable: SELECT * FROM users WHERE username = '" + username + "'

With input admin' -- the query becomes: SELECT * FROM users WHERE username = 'admin' -- ' — commenting out the password check.

Prevention:

• Parameterized queries / Prepared Statements — the query structure is fixed; user input is always treated as data, never as SQL code. The gold standard. Use in all cases.
• ORM frameworks — Hibernate, SQLAlchemy, Prisma use parameterized queries internally. Still vulnerable if you use raw query methods incorrectly.
• Input validation — whitelist expected formats (numeric IDs, email patterns). Not sufficient alone.
• Least privilege — the application database user should only have SELECT/INSERT/UPDATE on needed tables, not DROP TABLE or access to other schemas.
• WAF (Web Application Firewall) — detects and blocks common SQLi patterns. Defense in depth, not a replacement for parameterized queries.

Role-Based Access Control (RBAC): Grant permissions to roles, assign roles to users. Examples: GRANT SELECT ON public.users TO readonly_role; GRANT INSERT, UPDATE ON public.orders TO app_user; REVOKE ALL ON public.payments FROM app_user. Never use the database superuser (root/postgres/sa) from application code.

Row-Level Security (RLS): PostgreSQL supports RLS — policies that restrict which rows a user can see or modify. For multi-tenant databases, RLS can enforce tenant isolation at the database level: CREATE POLICY tenant_isolation ON orders USING (tenant_id = current_setting('app.tenant_id')).

Encryption:

• Encryption at rest — database files on disk are encrypted. Transparent Data Encryption (TDE) in SQL Server and Oracle. PostgreSQL relies on filesystem encryption (LUKS, FileVault). Protects against physical disk theft.
• Encryption in transit — require TLS for all client-server connections. In PostgreSQL: ssl=on in postgresql.conf; hostssl in pg_hba.conf. In MySQL: require_secure_transport=ON.
• Column-level encryption — encrypt specific sensitive columns (SSN, credit card) with application-layer encryption before storing. The database never sees plaintext. Allows compliance with PCI-DSS and GDPR requirements even if the database is compromised.
• Key management — encryption keys must be stored separately from encrypted data (AWS KMS, HashiCorp Vault). Rotating keys without downtime requires re-encryption of existing data.

Audit logging: Record every query, especially writes, with user identity and timestamp. PostgreSQL pg_audit extension. Essential for compliance (SOC 2, HIPAA, GDPR) and incident forensics.

These are the database and DBMS questions most frequently asked in technical interviews at Google, Amazon, Meta, Microsoft, and other top tech companies. Each answer is written at interview depth — enough to demonstrate solid understanding without over-explaining.

Q1: What are the ACID properties? Give a concrete example of each.

Atomicity: A transaction is all-or-nothing. Example: a bank transfer debits Account A and credits Account B. If the system crashes after the debit but before the credit, the transaction rolls back — both operations undo. Implemented via write-ahead log (WAL). Consistency: A transaction brings the DB from one valid state to another, honoring all constraints. Example: a NOT NULL constraint on email prevents inserting a user without an email address. Isolation: Concurrent transactions don't interfere. Example: two users simultaneously booking the last concert ticket — only one succeeds; neither sees the other's uncommitted reservation. Implemented via MVCC or locking. Durability: Committed data survives crashes. Example: after a successful order placement, a server crash before the next checkpoint still preserves the order. Implemented via WAL fsync to disk before acknowledging the commit.

Q2: What is the difference between a clustered and non-clustered index?

A clustered index determines the physical order of rows on disk — the data is stored sorted by the index key. Each table can have only one clustered index (because you can't physically sort the same data in two ways). In PostgreSQL it's called a heap + explicit CLUSTER command; in MySQL InnoDB, the primary key IS the clustered index and the row data lives in the B+Tree leaf nodes. A non-clustered index is a separate data structure containing the index key + a pointer (row ID or clustered index key) to the actual row. A table can have many non-clustered indexes. Lookup via non-clustered index requires two lookups: find the pointer in the index, then fetch the actual row ("table lookup" or "key lookup"). A covering index includes all columns needed by a query in the index itself, eliminating the second lookup.

Q3: How does a B+Tree index work? Why is it preferred over a hash index?

A B+Tree is a self-balancing tree where all data lives in leaf nodes (linked in sorted order) and internal nodes contain only keys for routing. Operations: search O(log N), insert O(log N) with rebalancing, range scan O(log N + K) where K is the number of matching rows. Preferred over hash indexes for range queries: B+Tree supports WHERE salary BETWEEN 50000 AND 80000 and ORDER BY by traversing sorted leaf nodes. Hash indexes only support exact equality (WHERE user_id = 42) in O(1) but cannot do range scans. Hash indexes are used in Redis (in-memory), and PostgreSQL offers hash indexes but they're rarely the right choice for persistent data. B+Tree's O(log N) worst case and excellent cache performance (high fanout = few levels = few disk seeks) make it the default for relational databases.

Q4: What are the SQL isolation levels and what anomalies does each prevent?

From weakest to strongest: READ UNCOMMITTED — allows dirty reads (reading uncommitted data from another transaction). READ COMMITTED (default in PostgreSQL, Oracle) — prevents dirty reads; allows non-repeatable reads (same row can return different values if re-read within a transaction). REPEATABLE READ (default in MySQL InnoDB) — prevents dirty and non-repeatable reads; allows phantom reads (new rows can appear in a range query if re-executed within a transaction). SERIALIZABLE — prevents all anomalies; transactions appear to execute one at a time. Higher isolation = fewer anomalies = more locking overhead = lower throughput. In practice: READ COMMITTED for most OLTP, SERIALIZABLE for financial transactions or distributed coordination.

Q5: What is the CAP theorem? Where does Cassandra fall? PostgreSQL?

CAP theorem (Brewer, 2000): a distributed system can guarantee at most two of three properties during a network partition: Consistency (every read receives the most recent write or an error), Availability (every request receives a response, though it might not be the latest data), Partition Tolerance (the system continues operating despite network partitions). Network partitions are unavoidable in distributed systems, so the real choice is between C and A during a partition. Cassandra is AP — it stays available during partitions but may return stale data (tunable consistency via quorum reads). PostgreSQL (single node) doesn't face partition tolerance concerns; as a distributed extension (Citus, Patroni), it leans CP — it may become unavailable during partition to maintain consistency. Note: PACELC refines CAP by considering the latency/consistency tradeoff even without partitions.

Q6: What is the N+1 query problem and how do you fix it?

The N+1 problem occurs when code executes 1 query to fetch N records and then N additional queries to fetch related data for each record. Example: fetch 100 orders (1 query), then for each order fetch the customer name (100 queries) = 101 queries total. As N grows, performance collapses. Fix: (1) JOIN in the original query to fetch orders and customer names together in one query, (2) eager loading — ORMs like Django's select_related() or Hibernate's JOIN FETCH pre-fetch associations, (3) batched loading — fetch all 100 customer IDs in one IN clause (SELECT * FROM customers WHERE id IN (...)). N+1 is a classic ORM pitfall — always check the generated SQL in production using query logging or EXPLAIN ANALYZE.

Q7: How does MVCC work?

Multi-Version Concurrency Control (MVCC) maintains multiple versions of each row, stamped with transaction IDs (xmin for creation, xmax for deletion). Readers see a consistent snapshot of the database as of their transaction's start time — they never block on writers. Writers create new row versions rather than overwriting; old versions are garbage-collected by VACUUM (PostgreSQL) or purge threads (MySQL). Result: reads never block writes, writes never block reads — only write-write conflicts cause contention. PostgreSQL and MySQL InnoDB both use MVCC. Trade-off: table bloat from accumulating old row versions (requires periodic vacuuming), and "read-your-own-write" consistency requires care in distributed settings where readers might hit a replica.

Q8: When would you choose NoSQL over SQL?

Choose NoSQL when: (1) Schema flexibility — data shape varies per record (product catalog with different attributes per product type → document DB). (2) Massive write scale — millions of writes/second with wide distribution (IoT sensor data → Cassandra, time-series DB). (3) Simple access patterns — always fetch by a single key, no joins needed (session cache, shopping cart → Redis). (4) Horizontal scaling requirement — relational databases scale vertically; NoSQL databases are designed to shard horizontally. Choose SQL when: you need ACID transactions across multiple entities, complex queries with JOINs and aggregations, strong data integrity via constraints, or a mature ecosystem with decades of tooling. In practice, most production systems use both — SQL for transactional data, Redis for caching, Elasticsearch for search, Cassandra for write-heavy event streams.

Q9: How does consistent hashing work and why is it used for sharding?

Consistent hashing maps both keys and servers onto a ring (0 to 2³²). Each key is assigned to the next server clockwise on the ring. When a server is added or removed, only K/N keys need to be remapped (K = number of keys, N = number of servers) — compared to modulo hashing which remaps nearly all keys. This minimizes cache invalidation and data movement during scaling. Used by: Amazon DynamoDB, Apache Cassandra, Redis Cluster, CDNs (for cache routing). Virtual nodes (vnodes) improve load distribution: each physical server has multiple positions on the ring, smoothing out hotspots when servers have different capacities or fail. Interview tip: draw the ring, show a server addition, count how many keys move — much more convincing than a verbal description.

Q10: What is replication and what consistency challenges does it introduce?

Replication maintains copies of data across multiple nodes. Synchronous replication: the primary waits for at least one replica to acknowledge the write before confirming to the client. Guarantees no data loss on failover; higher write latency. Asynchronous replication: the primary confirms immediately; replicas catch up later. Lower write latency; risk of data loss if primary fails before replicas catch up. Replication lag is the delay between a write on the primary and its appearance on replicas. Consequences: "read-your-own-write" inconsistency (user writes a post, immediately refreshes, reads from a lagged replica, sees the old state), stale reads in analytics. Solutions: route reads for the same user to the same replica (sticky sessions), use synchronous replication for critical data, use a causal consistency protocol, or always read from the primary for consistency-critical paths.

This guide is aligned with the references used in database courses and production database engineering:

• CMU 15-445 Database Systems (Andy Pavlo), the leading university database systems course covering storage, indexing, and transaction internals.
• PostgreSQL Documentation, the authoritative reference for MVCC, indexing, and query planning in a real production database.
• Use The Index, Luke (Markus Winand), the definitive practical guide to how database indexes actually work.
• Database System Concepts (Silberschatz, Korth & Sudarshan), the standard textbook this guide's topic order follows.