Further Reading | Computer Science

• Silberschatz, Korth, Sudarshan: Database System Concepts (7th ed.).
• Ramakrishnan, Gehrke: Database Management Systems (3rd ed.).
• Elmasri, Navathe: Fundamentals of Database Systems (7th ed.).
• Kleppmann: Designing Data-Intensive Applications (2017).

Database systems are built on a tension between correctness and speed. Transactions are the promise that your money will not vanish mid-transfer — ACID properties guarantee that. Indexes are like the index at the back of a textbook — they let you find a topic without reading every page, but they take up space and slow down updates. Normalisation is the art of organising data so that each fact is stored in exactly one place, preventing the chaos of contradictory copies. Query optimisation is the database’s way of finding the fastest route through a maze of joins and filters, like a GPS that recalculates when traffic changes.

• Confusing 2NF and 3NF. 2NF removes partial dependencies; 3NF removes transitive dependencies. Fix: A relation in 3NF is also in 2NF; check for non-prime attributes depending on other non-prime attributes.
• Wrong isolation level. Read uncommitted: dirty reads possible. Serializable: no anomalies but lowest concurrency. Fix: Balance consistency and performance; most applications use Read Committed or Repeatable Read.
• Confusing the CAP theorem trade-offs. A distributed system can guarantee at most 2 of: Consistency, Availability, Partition tolerance. Fix: Network partitions are inevitable; choose between CP (consistent but unavailable) and AP (available but eventually consistent).
• Assuming ACID always guarantees correctness. ACID isolation levels have different anomaly protections. Snapshot isolation prevents dirty reads and non-repeatable reads but allows write skew.
• Denormalising without understanding the read/write ratio. Denormalisation improves read performance at the cost of write complexity. Fix: Profile the workload first; normalise by default, denormalise only when read-heavy.

Problem. Relation R(A, B, C, D) with FDs: AB → C, C → D. Is R in 3NF?

Solution. Key: AB. C depends on AB (partial dependency on non-prime B? No — C depends on the full key AB). C → D: D depends on C, which is non-prime. This is a transitive dependency, violating 3NF.

Decompose: R1(A, B, C), R2(C, D). Both are in 3NF.

$\blacksquare$

Problem. Students(ID, Name, DeptID) and Departments(DeptID, DeptName). Write SQL to list all students with their department names.

Solution. SELECT s.Name, d.DeptName FROM Students s INNER JOIN Departments d ON s.DeptID = d.DeptID;

$\blacksquare$

Problem. R(A, B, C) with FDs: AB → C, C → B. Is R in BCNF?

Solution. Candidate keys: AB and AC. Check each FD: AB → C: AB is a superkey (OK). C → B: C is not a superkey (since C alone does not determine A). Thus R is not in BCNF.

Decompose: R1(C, B), R2(A, C). R1 has FD C → B (C is key, OK). R2 has no non-trivial FDs (OK).

$\blacksquare$

Problem. Two transactions: T1 transfers $100 from A to B, T2 reads balances. At isolation level Read Committed, can T2 see an inconsistent state?

Solution. Yes: T2 could read A after T1 debits it but before T1 credits B. The total appears reduced by $100. This is a non-repeatable read. At Repeatable Read, T2 would see consistent snapshot but may still see phantoms (rows appearing/disappearing in range queries).$\blacksquare$

flowchart TD
    A[11_Further Reading] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

• Normalisation: 1NF (atomic), 2NF (no partial dependencies), 3NF (no transitive dependencies), BCNF.
• ACID properties: Atomicity, Consistency, Isolation, Durability.
• SQL: DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE), DCL (GRANT, REVOKE).
• CAP theorem: distributed systems trade off consistency, availability, and partition tolerance.
• Indexing: B+ trees for range queries, hash indexes for equality lookups, bitmap indexes for low-cardinality columns.
• Query optimisation: cost-based selection of join algorithms (nested-loop, sort-merge, hash), predicate pushdown, and query plan caching.

• Bernstein et al.: “The Asilomar Report on Database Research” — landmark ACM report on database research directions.
• Stonebraker et al.: “The End of an Architectural Era (It’s Time for a Complete Rewrite)” — argues for specialised database engines over one-size-fits-all.
• DeWitt & Gray: “Parallel Database Systems: The Future of High Performance Database Processing” — survey of shared-nothing, shared-memory, and shared-disk architectures.
• Abiteboul, Hull, Vianu: Foundations of Databases — rigorous treatment of database theory, query languages, and complexity.
• Gray et al.: “Transaction Processing: Concepts and Techniques” — encyclopedic reference on transaction processing, recovery, and concurrency control.

• Use The Index, Luke (use-the-index-luke.com) — practical guide to SQL indexing strategies with visual explainers.
• SQL Performance Explained by Markus Winand — focused on index usage and query optimisation.
• CMU Database Group lectures (YouTube) — Andy Pavlo’s database course covering architecture, storage, and modern systems.
• VLDB Summer School — annual summer school on database research topics.
• DB-Engines Ranking (db-engines.com) — popularity ranking of database systems with comparison features.

• Discrete Mathematics
• Algorithm Implementation

• SQL & Relational Theory: Date: SQL and Relational Theory (3rd ed.) — deep treatment of relational model fundamentals.
• Transactions & Concurrency: Weikum, Vossen: Transactional Information Systems — complete coverage of serialisability theory and recovery.
• Distributed Databases: Özsu, Valduriez: Principles of Distributed Database Systems — standard reference for distributed query processing and transaction management.
• Performance Tuning: Tow: SQL Tuning — practical guide to indexing strategies, query plan analysis, and schema design for performance.
• NoSQL: Sadalage, Fowler: NoSQL Distilled — overview of when to use document, graph, column, and key-value stores over relational databases.

• Database Systems
• Introduction to Database Systems
• Problem Set