Database Management Systems
The ER model, the relational model, relational algebra, SQL, normalization and indexing.
Textbook: A. Silberschatz, H. F. Korth, S. Sudarshan, “Database System Concepts”, 6th edition, McGraw Hill
- Week 1Introduction to Database Management Systems
- Introduction to database management systemsWhy a DBMS is used instead of a file system, schema vs instance, the three-schema architecture, data independence, DDL/DML and the idea of a transaction. The university database we use all semester is introduced here too.
- Week 2Entity-Relationship Model
- Entity-relationship (ER) modelEntities, attribute types, relationships, cardinality and participation, weak entities and specialization. The basis for reading and drawing ER diagram questions on the midterm.
- Week 3Introduction to Relational Data Model
- The relational model, keys and ER-to-table mappingRelation, schema, instance, domain; super/candidate/primary/foreign key; referential integrity and the rules for turning an ER diagram into tables. Both the algebra and the SQL questions rely on these tables.
- Week 4Relational Algebra
- Relational algebra: basic operatorsWriting queries with selection, projection, set operations, the Cartesian product and rename; the basis of the “write the relational algebra expression” and “give the result” exam questions.
- Week 5Relational Algebra
- Relational algebra: joins, division and groupingWriting multi-table queries with theta, natural and outer joins, division, assignment and grouping (γ); solution patterns for “for every” and “for each” questions.
- Week 6Structured Query Language (SQL)
- SQL basics: DDL, constraints, SELECT and joinsCreating tables (CREATE TABLE and constraints), querying a single table and joining tables (inner, natural, outer, self join). The basis of the "write the SQL" questions on the midterm.
- Week 7Structured Query Language (SQL)
- Advanced SQL: GROUP BY, NULL, subqueries, DML and viewsAggregate functions, GROUP BY/HAVING, the three-valued logic of NULL, IN/EXISTS/correlated subqueries, set operations, INSERT/UPDATE/DELETE and views. The hardest SQL questions on the midterm come from here.
- Week 8Midterm Exam
- Midterm review: DBMS, ER, relational model, algebra and SQLA one-page summary of the first seven weeks and mixed midterm questions. Start here the evening before the exam, and go back to the week of any topic where you feel weak.
- Week 9Relational Database Design
- Bad design, functional dependencies and closureYou learn why putting everything into one table produces anomalies, and then functional dependencies, Armstrong's axioms and finding keys with closure. All normalization questions rely on these calculations.
- Week 10Relational Database Design
- Canonical cover and normal forms: 1NF, 2NF, 3NF, BCNFYou learn to drop extraneous attributes to find the canonical cover, and to determine step by step which normal form a schema is in. The recipe for the 'What is the highest normal form?' question is on this page.
- Week 11Relational Database Design
- Decomposition: lossless join, dependency preservation, BCNF and 3NF algorithmsYou learn to split a schema into pieces without losing data (lossless join), to test dependency preservation, and to apply the BCNF decomposition and 3NF synthesis algorithms step by step.
- Week 12Indexing and Query Processing
- Indexing: dense/sparse indexes, B+ trees, hashing and selection costHow records are laid out on disk, how an index speeds up search, how insertion into a B+ tree works and how the cost of a selection is calculated.
- Week 13Query Processing and Query Optimization
- Query processing and optimization: join algorithms, equivalence rules, estimationThe steps a query goes through, how the costs of nested-loop/block/indexed/merge/hash joins are calculated, and how the optimizer rewrites the query tree.
- Week 14Introduction to Data Analysis and Data Mining Concepts
- Data analysis and data mining: OLAP, star schema, association rulesOLTP vs OLAP, the data warehouse and star schema, cube operations and ROLLUP/CUBE, then data mining: support/confidence/lift, Apriori, information gain in decision trees and k-means. Concept and small calculation questions in the final come from here.