CMPUT 391 is a graded undergraduate course at the University of Alberta whose main objective is to study fundamental concepts and advanced technology underlying modern data management systems expected from expert users and database administrators.

Formal Prerequisites: CMPUT201, CMPUT 204 or 275, and CMPUT 291.

Beyond Prerequisites : CMPUT391 was designed for senior undergraduate students with strong programming and problem solving skills, and who are able to seek answers to technical problems independently using the Web (Google and social coding sites such as stackOverflow). Students are expected : (1) to be fluent in (or able to quickly learn) multiple programming languages, including C; (2) to have excellent knowledge of SQL and relational database theory; and (3) to work at least 3 hours per week on coursework beyond lectures and labs.

Learning Objectives

Understanding fundamental algorithms and data structures underlying the storage and manipulation of data by a relational database management system and select topics pertaining to non-traditional data models and applications, including document management, spatial data management, graph data management, and NoSQL (not-only SQL) systems.


  1. SQL and relational algebra: brief review, equivalence, and compiling SQL into algebraic expressions
  2. Recursive SQL and querying graph databases
  3. Hardware/OS: virtual memory, storage, redundancy, the Buffer Manager
  4. Query processing: in memory query execution, external memory query execution, iterators
  5. Speeding up tuple retrieval: flat indexes, multilevel indexes, B+trees, hashing, multidimensional indexes
  6. Transaction processing: ACID transactions, logging and error recovering, locking, timestamping, validation
  7. RDF and SPARQL
  8. XML and XQuery
  9. Spatial indexes, simple spatial queries and nearest neighbor queries
  10. NoSQL and Map-Reduce

Other Suggested Readings