University Homepage School Homepage School Contacts School Search

Advanced Databases

Semester 2, Levels 10/11

Lecturer: Stratis Viglas
Informatics Forum, IF 5.11
Tel: +44 (0) 131 650 5183

Lectures:
Monday, 11:10-12:00, F.21 7 George Square (Psychology building)
Thursday, 11:10-12:00, F.21 7 George Square (Psychology building)

Office hours:
Monday, Thursday, 12:00-13:00, IF 5.11.
(Though you can always send e-mail or drop by if you have questions.)

---

Contents

• Pre-requisites
• Announcements
• Slides
• Schedule
• Syllabus
• Reading List
• Assignments
• Software

---

Pre-requisites

Undergraduate students must have taken the Database Systems course. Postgraduate students must have taken an equivalent course to Database Systems during their undergraduate degree. If you have not taken Database Systems or an equivalent course and still want to enroll in Advanced Databases please contact the instructor to obtain consent.

Finally, Advanced Databases is a co-requisite and not a forbidden combination with Topics in Distributed Databases. This means that you are better off taking ADBS if you plan on taking TDD.

---

Announcements

Watch this space for any announcements concerning the course.

• If you want to subscribe to the Scottish Database Interest Group email list, click here and enter your details. This is a low-volume email list concerning announcements of database-related talks and events in Scotland.
• The mailing list for the course is adbs-students at inf dot ed dot ac dot uk.
• 20 January 2013: The course assignments have been announced.
• 28 January 2013: The lab sessions for the course are to be held on Wednesday 30/1/2013 and Wednesday 6/2/2013. There will be two slots for each session, one running 2pm-4pm and a second one running 4pm-6pm. The material covered in each slot of the same day will be identical, so you only need to attend one slot (but both sessions). The sessions will take place in AT, 4.12.
• 11 March 2013: The solution to the first assignment is available. You will need to either change the class name from ExternalMergeSort to ExternalSort; or the call to the sort algorithm from ExternalSort to ExternalMergeSort if you want to use this.

---

Lecture Slides

The entire set of slides for the course can be found in three versions:

• Online version, suitable for viewing (NB: the file is big!)
• Hand-out version suitable for viewing but without the animations, and printing one slide per page.
• Print-out version suitable for printing four slides per page.

---

Lecture Schedule

After each lecture, the material covered will be added.

Lecture Information	Covered Material	Additional Notes
14/1/13	Overview, introduction to query evaluation
17/1/13	Introduction to relational databases, indexing
21/1/13	B+trees, extendible hashing
24/1/13	Linear hashing
28/1/13	R-trees
31/1/13	External mergesort
4/2/13	External mergesort (cont.), physical plans	Graefe's paper on query evaluation in relational databases.
7/2/13	Execution models
11/2/13	Nested loops join, sort-merge join
14/2/13	Sort-merge join, hash joins	Original System-R paper
18/2/13	No class (Innovative Learning Week)
21/2/13	No class (Innovative Learning Week)
4/3/13	Query optimisation
7/3/13	Histograms and dynamic programming
11/3/13	Dynamic programming (cont.), query optimisation wrap-up
14/3/13	Transaction processing
18/3/13	General locking algorithms, B+-tree locking
21/3/13	ARIES recovery algorithm
25/3/13	Parallel database systems	Last lecture

---

Syllabus

During the course we will be mainly dealing with database implementation issues and database technology in general. The material will cover storage structures, query evaluation and execution, query optimisation, concurrency control, transaction processing, recovery, and parallel databases.

Reading List

Raghu Ramakrishnan and Johannes Gehrke, Database Management Systems. (Third Edition) McGraw-Hill 2003.

Note that this is not required text; it is merely recommended. You should be fine with the slides used during the lectures alone, along with any handouts.

---

Assignments

Both assignments are available.

• The first assignment is an implementation of external mergesort; the deadline is Wednesday 27 February, 4pm (solution).
• The second assignment is an implementation of merge join and is also available; the deadline is Wednesday 27 March, 4pm.

Marks and feedback for both assignments will be returned two weeks after submission.

---

Software

In the context of the course, we will be using an experimental relational database system, written in Java, called attica.

Attica can be found at this location. Visit the page to obtain the software and installation instructions.