Skip to main content

Database Systems Implementation:  2017-2018



Schedule C1Computer Science

Schedule C1Mathematics and Computer Science

Schedule CMSc in Advanced Computer Science



This course examines the data structures and algorithms underlying database management systems such as Oracle or PostgreSQL. It covers techniques from both research literature and commercial systems.

Learning outcomes

At the end of this course, students should

  • have a good insight into how DBMSs function internally
  • understand how to analyse the performance of data-intensive systems
  • be familiar with a variety of programming techniques for large-scale data manipulation
  • apply the insights achieved to build the major components of a mini-DBMS


This course assumes a reasonable understanding of the following topics:

  • developing applications on relational DBMSs (SQL, relational algebra - completed an introductory course on Databases)
  • sorting/searching techniques (quick/merge sorts, binary trees, hash tables - course on Design and Analysis of Algorithms)

This course will use C and C++. The practicals will have increasing difficulty, to allow students to learn the languages.


  • Hardware: Secondary-storage devices; disk access time; Input/Output model of computation; optimized disk access;
  • File and System Structure: page layout and access; buffer management; file organizations (heap, sorted, clustered); row stores versus column stores;
  • Indexes: Tree-structured (ISAM, B+tree); hash-based (static, extendible, linear); multi-dimensional (UB-tree, k-d-b tree, R-tree)
  • External Sorting: external n-way merge sort; sorting based on B+trees;
  • Query Evaluation: Selection (index-based, hash-based, arbitrary selection predicates); projection (duplicate elimination; hash-based, sorting-based); joins (nested-loops, index nested, block nested, sort-merge, hash joins); set operations; aggregation; impact of buffering, pipelining, blocking; evaluation techniques in existing systems;
  • Query Optimization: cardinality estimation for all query operators, histograms ; equivalences of relational algebra; query plans; cost estimation; nested queries; join optimization algorithms (dynamic programming and greedy join enumeration approaches); optimization techniques in existing systems;
  • Transaction Management: ACID properties; concurrency control (serializability criteria); locking (two-phase locking, index locking, multiple granularity locks, intention locks); deadlock detection; isolation levels; concurrency control in existing systems;


The internals of a relational database management system; data storage; buffer management; indexes; sorting; query evaluation and optimization; transaction management; concurrency control; comparisons of existing commercial systems; use cases: PostgreSQL and IBM DB2.

Reading list

We will follow closely chapters from these two books

  • Ramakrishan and Gehrke. Database Management Systems, McGraw-Hill, 2002 (3rd ed).
  • Garcia-Molina, Ullman, Widom. Database Systems: The Complete Book. Prentice Hall, 2002 (or 2008, 2nd ed).

We will also discuss (or refer to) relevant research papers published in recent years in top conferences and journals in database systems and data management.


Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.