ECE 356: Database Systems

Sources and References

Equivalent UW courses — CS 348 (Intro to Database Management), CS 448 (Database Systems Implementation), MSCI 346 (Database)

Primary textbook — Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019.

Supplementary references — Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom, Database Systems: The Complete Book, 2nd ed., Pearson, 2008; Raghu Ramakrishnan and Johannes Gehrke, Database Management Systems, 3rd ed., McGraw-Hill, 2002.

Equivalent UW Courses

CS 348 is the closest Math-faculty analogue and covers the same core territory: the relational model, ER diagrams, SQL, normalization, and an overview of storage, indexing, transactions, and concurrency control. CS 448 goes deeper into the implementation side and is the better match for the query-processing, buffer-management, and recovery segments of ECE 356. MSCI 346 targets a more applied audience and covers SQL, schema design, and transactions but typically without the implementation-level depth. Together CS 348 and CS 448 cover essentially all of ECE 356 and somewhat more.

What This Course Adds Beyond the Equivalents

Relative to CS 348 alone, ECE 356 spends more time on the mechanics of query evaluation and optimization, on B+ tree indexing, and on transaction isolation levels and deadlock handling, material that normally spills into CS 448. It also adds a short module on database security (SQL injection, password hashing and salting) and a brief introduction to data warehousing, data mining, parallel and distributed databases, and NoSQL. Compared with CS 448 the implementation treatment is lighter and more survey-style; ECE 356 does not cover the advanced query-optimization theory, cost models, or crash-recovery algorithms at the same depth.

Topic Summary

Entity-Relationship Modelling and the Relational Model

ER diagrams with entities, attributes, relationships, cardinality, and participation constraints. Translation of ER designs into relation schemas, keys (primary, candidate, foreign), and referential integrity.

Relational Algebra and SQL

Selection \(\sigma\), projection \(\pi\), join \(\bowtie\), union, difference, and aggregation as the algebra underlying SQL. SQL syntax for data definition, queries, inserts and updates, views, grouping, nested subqueries, and outer joins.

Normalization and Functional Dependencies

Functional dependencies, Armstrong’s axioms, closures, and minimal covers. Decomposition into 3NF and BCNF with the lossless-join and dependency-preservation conditions, and the trade-offs between normalization and query performance.

Physical Storage and File Organization

Disk layout, records in blocks, heap and sorted files, buffer management and replacement policies, and the impact of I/O costs on query performance.

Indexing and B+ Trees

Dense vs sparse primary indexes, secondary indexes, and the B+ tree as the standard disk-resident balanced index. Insertion, deletion, and lookup are analyzed in terms of tree height, which for a tree of order \(b\) on \(N\) keys is

\[ h = O(\log_b N). \]

Query Processing and Optimization

Algorithms for selection, projection, and the major join strategies (nested-loop, block nested-loop, sort-merge, hash join). Query plans as algebra trees; heuristic rewriting (push selections, combine projections) and basic cost-based optimization using catalog statistics.

Transactions and Concurrency Control

ACID properties; serializability as the correctness criterion; conflict-serializable and view-serializable schedules. Two-phase locking, deadlock detection and prevention, timestamp-ordering protocols, and SQL isolation levels (read uncommitted through serializable).

Recovery, Data Warehousing, and Beyond

Log-based recovery with undo and redo records and checkpointing. Survey treatment of data warehousing and OLAP, simple data-mining operations on real datasets, parallel and distributed databases, and key-value, document, and wide-column NoSQL systems as alternatives to the relational model.

Database Security

SQL injection attack patterns and parameterized-query defenses, together with password hashing and salting as the baseline for safe credential storage.