Madhavan Mukund

Teaching

Database Managment Systems
Sai University
Aug–Nov 2023

Database Managment Systems

Sai University, Aug–Nov 2023

Administrative details

  • Instructor: Madhavan Mukund

  • Teaching Assistants: Vinodh Chincholi, Deepmalya Dutta, Praveen Kumar

  • Evaluation:

    • Assignments (both pen-and-paper and coding), 50%
    • Midsemester exam (week of Oct 3–6), 20%
    • Final exam, 30%

  • Text and reference books:

    • Abraham Silberschatz, Henry F. Korth and S. Sudarshan: Database System Concepts (7th ed), McGraw-Hill (2021)
    • Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom: Database Systems: The Complete Book (2nd ed), Pearson (2013)

Course plan

  • The relational model for data
  • Query languages — relational algebra, SQL
  • Designing databases, Functional dependencies, normal forms
  • Data storage and indexing schemes
  • Query processing and optimization
  • Transaction management — ACID properties, serializability
  • Concurrency control
  • Miscellaneous topics (if time permits) — semistructured and unstructured data

Assignments

  • Assignment 1, 13 Sep 2023, due 20 Sep 2023 23 Sep 2023 (submit on Moodle).
  • Assignment 2, 28 Sep 2023, due 8 Oct 2023 (submit on Moodle).
  • Assignment 3, 30 Oct 2023, due 8 Nov 11 Nov 2023 (submit on Moodle).
  • Assignment 4, 12 Nov 2023, due 20 Nov 2023 (submit on Moodle).
  • Assignment 5, 25 Nov 2023, due 3 Dec 2023 (submit on Moodle).

Lectures

  • Lecture 1: 16 Aug 2023
    (Class Notes (pdf))

    Why DBMS? Overview of concepts to be discussed in the course

    Reference: Silberschatz et al, Ch 1.1, 1.2, 1.6

  • Lecture 2: 18 Aug 2023
    (Class Notes (pdf))

    The relational model — mathematical relations, relations and tables, schema, representing graphs using relations, keys, integrity constraints

    Reference: Silberschatz et al, Ch 2.1, 2.2, 2.3

  • Lecture 3: 23 Aug 2023
    (Class Notes (pdf))

    Foreign keys, referential integrity, schema diagrams, relational algebra – select, project, join

    Reference: Silberschatz et al, Ch 2.3, 2.4, 2.5, 2.6

  • Lecture 4: 25 Aug 2023
    (Class Notes (pdf))

    Relational algebra – select, project, join, set operations, assignment, renaming, sets vs lists – duplicates and ordering, query optimization, declarative programming

    Reference: Silberschatz et al, Ch 2.6

  • Lecture 5: 26 Aug 2023
    (Class Notes (pdf))

    Introduction to SQL – table creation, updating tables, select command, cartesian product and join, renaming, set operations

    Reference: Silberschatz et al, Ch 3.1, 3.2, 3.3, 3.4 (part), 3.5

  • Lecture 6: 1 Sep 2023

    Problem Sheet (pdf)

    Solutions (pdf)

  • Lecture 7: 6 Sep 2023
    (Class Notes (pdf))

    Introduction to SQL – string matching, sorting, aggregate operations, grouping

    Reference: Silberschatz et al, Ch 3.4, 3.7

  • Lecture 8: 8 Sep 2023
    (Class Notes (pdf))

    Introduction to SQL – nested queries, null values, set membership and comparison, testing for empty relations and duplicates

    Reference: Silberschatz et al, Ch 3.6, 3.8

  • Lecture 9: 13 Sep 2023
    (Class Notes (pdf))

    Introduction to SQL – joins (natural, outer, inner), views, constraints, cascading deletes/updates, built-in datatypes, interfacing with SQL

    Reference: Silberschatz et al, Ch 4.1, 4.2, 4.4

  • Lecture 10: 20 Sep 2023
    (Class Notes (pdf))

    Relational database design – redundancy, lossless decomposition, functional dependences, normalization, BCNF, 3NF

    Reference: Silberschatz et al, Ch 7.1, 7.2, 7.3

  • Lecture 11: 22 Sep 2023
    (Class Notes (pdf))

    Relational database design – BCNF, 3NF, computing dependency closure, extraneous attributes, canonical basis, dependency preservation

    Reference: Silberschatz et al, Ch 7.4, Garcia-Molina et al, Ch 2.4, 2.5

  • Lecture 12: 27 Sep 2023
    (Class Notes (pdf))

    Relational database design – computing dependency closure, extraneous attributes, canonical basis, dependency preservation, multivalued dependencies

    Reference: Silberschatz et al, Ch 7.4, 7.6

  • Lecture 13: 29 Sep 2023

    Problem Sheet (pdf)

    Solutions (pdf)

  • Lecture 14: 13 Oct 2023
    (Class Notes (pdf))

    Storage – RAM, disk, SSD; fixed and variable length records; heap and sequential organization of files; primary and secondary indices; multilevel indices; introduction to hashing

    Reference: Silberschatz et al, Ch 12.1-12.4, 13.1-13.3

  • Lecture 15: 18 Oct 2023
    (Class Notes (pdf))

    Indexing: motivation, clustering index, dense and sparse indices, secondary indices, multilevel indices, B+-trees, hashing, indices on multiple attributes

    Reference: Silberschatz et al, Ch 14.1-14.3, 14.5-14.7, 14.9

  • Lecture 16: 20 Oct 2023
    (Class Notes (pdf))

    Indexing: B+-tree insertion and deletion

    Query processing: query plans, assessing and optimizing cost, algorithms for selection operation

    Reference: Silberschatz et al, Ch 14.3, 15.1-15.3

  • Lecture 17: 25 Oct 2023
    (Class Notes (pdf))

    Sorting: External merge sort

    Query processing: nested-loop join, block nested-loop join, indexed nested-loop join, merge-join, hash-join, outer joins, aggregation, set operations

    Reference: Silberschatz et al, Ch 15.4-15.6

  • Lecture 18: 1 Nov 2023
    (Class Notes (pdf))

    Query processing: materialization and pipelining

    Query optimization: transforming relational algebra expressions, estimating outputs, choosing between evaluation plans

    Reference: Silberschatz et al, Ch 15.7, 16.1-16.4

  • Lecture 19: 3 Nov 2023
    (Class Notes (pdf))

    Transactions: ACID properties, transaction state diagram, logs, concurrent schedules

    Reference: Silberschatz et al, Ch 17.1-17.5

  • Lecture 20: 8 Nov 2023
    (Class Notes (pdf))

    Transactions: serializability, conflict serializability, testing for conflict serializability

    Reference: Silberschatz et al, Ch 17.6

  • Lecture 21: 10 Nov 2023
    (Class Notes (pdf))

    Transactions: recoverable schedules, cascading rollbacks, transactions in SQL

    Reference: Silberschatz et al, Ch 17.7, 17.8

  • Lecture 22: 17 Nov 2023
    (Class Notes (pdf))

    Transactions: concurrency control, locks, two phase locking, deadlock handling

    Reference: Silberschatz et al, Ch 18.1, 18.2

  • Lecture 23: 22 Nov 2023
    (Class Notes (pdf))

    Transactions: concurrency control, locks, timestamp based protocols, validation based protocols

    Reference: Silberschatz et al, Ch 18.1, 18.2, 18.5, 18.6

    Beyond RDBMS: semi-structured data, CAP theorem, weak consistency

  • Lecture 24: 24 Nov 2023
    (Class Notes (pdf))

    Clarifications and doubts

Last modified: Sat 25 Nov 2023