CS 410 Top: Database Internals

Credit Hours:	4
Course Coordinator:	David Archer
Course Description:	Internal design of a relational database management system. Concurrency control; lock managers; crash recovery; query and operator evaluation; query optimization.
Prerequisites:	CS 386, CS 333
Goals:	To develop understanding of the internal structure of relational database systems. To understand how memory and disk storage structures are taken into account by database components. To understand how database internal structure and impact of memory and disk systems affect database design choices. Upon completion of this course, the successful student will be able to explain/describe: Indexing methods used in modern relational databases (RDBMSs), how they work, and what the key trade-offs are in selecting them appropriately How disk and file structures are used in RDBMSs External (out-of-memory) sorting mechanisms How relational operators are evaluated Query optimization, and how to manually optimize query plans Concurrency control systems for RDBMSs Crash recovery mechanisms Basic concepts of parallel and distributed databases, how to distinguish these, and what some of the salient complexities of these systems are.
Textbooks:	Ramakrishnan, R. & Gehrke, J. (2003). Database Management Systems. New York: McGraw-Hill
References:	None
Major Topics:	Database index structures (tree- and hash-based) and their management; disk drive hardware characteristics and implications for disk access performance; file structures on disk; sorting large files using “out-of-memory” techniques; evaluation techniques and implementation algorithms for relational algebra operators; database concurrency control management; query optimization techniques, real-world approaches to optimization, and how to limit the scope of eligible query plans; database crash recovery and transaction abort mechanisms; parallel and distributed database architectures.
Laboratory Exercises:

CAC Category Credits	Core	Advanced
Data Structures	0.5	1.0
Algorithms	0.5	0.5
Software Design		0.5
Computer Architecture		0.5
Programming Languages		0.5

Oral and Written Communications:	None
Social and Ethical Issues:	None
Theoretical Content:	About 35 percent of class time is spent on theoretical aspects of databases: Relational algebra manipulations Index structures and hash-based indexing of data Concurrency and serialization of database transactions Complexity of the space of possible implementations for queries Durability and atomicity of database transactions
Problem Analysis:	About 65 percent of class time is spent on analyzing and solving database design problems: How relational algebra manipulations are used to optimize DBMS queries Algorithms for implementing relational operators External (“out-of-memory”) sorting techniques for data Use of resource locking techniques for achieving safe concurrency in databases Use of dynamic programming techniques and heuristics for limiting searches for near-optimal query plans Write-ahead logging and ARIES recovery mechanisms for achieving durability and atomicity of transactions in the presence of system crashes and transaction aborts. Architectures for parallel and distributed databases
Solution Design:	Through programming problems (activity outside of class time), students gain sophistication in how database internals are constructed and optimized.