Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
teaching:infoh417 [2019/12/06 19:43]
svsummer [COURSE TRAJECTORY]
teaching:infoh417 [2020/09/10 08:46]
svsummer
Line 1: Line 1:
 ====== INFO-H-417 : Database Systems Architecture ====== ====== INFO-H-417 : Database Systems Architecture ======
-<note tip>To help you in preparing for the exam, two prior exams and their solution are now available: {{:​teaching:​infoh417:​ex-2016-s1-sol.pdf|prior exam 1}} {{:​teaching:​infoh417:​ex-2014-s1-it4bi-sol.pdf|prior exam 2}}</​note>​ 
- 
- 
-<​note>​The list of approved project groups {{:​teaching:​infoh417:​students_groups.pdf|has been updated}}</​note>​ 
  
 +<note important>​This course has moved to the [[https://​uv.ulb.ac.be/​course/​view.php?​id=92219|Virtual University]]</​note>​
  
 ===== GENERAL INFORMATION ===== ===== GENERAL INFORMATION =====
Line 28: Line 25:
 relational database management systems ensures recovery from errors relational database management systems ensures recovery from errors
 and controls concurrent access to the data. Topics studied in transaction processing include logging, serializability,​ concurrency control, and their combination. and controls concurrent access to the data. Topics studied in transaction processing include logging, serializability,​ concurrency control, and their combination.
- 
-==== Contacts ==== 
- 
-  * **Lecturer**:​ [[http://​code.ulb.ac.be/​code.people.php?​id=992|Stijn Vansummeren]] (Campus Solbosh, Building U, 4th floor, room UB4.125) 
- 
- 
-==== Organisation ==== 
- 
-    * The course is taught during the first semester 
-    * The list of competences that will be taught during the course and interrogated during the exam is available in the {{:​teaching:​infoh417:​course plan.pdf|course plan.}} 
- 
  
 ==== Course Material ==== ==== Course Material ====
  
-The course uses the book [[http://​www.amazon.co.uk/​gp/​product/​129202447X/​ref=s9_simh_gw_p14_d0_i1?​pf_rd_m=A3P5ROKL5A1OLE&​pf_rd_s=center-2&​pf_rd_r=05ETHX35GZHR16YA722M&​pf_rd_t=101&​pf_rd_p=455344027&​pf_rd_i=468294|"​Database Systems: The Complete Book (second, international edition)"​]] by H. Garcia-Molina,​ J. D. Ullman, and J. Widom (ISBN-13: 978-0131354289)complemented by course notes made available on this website. +For the table of contents, course notes, slides, ​exercises ​and solutions, ​as well as recording ​of the lectures, see the [[https://uv.ulb.ac.be/​course/​view.php?id=92219|Virtual University]] page.
- +
-==== Method of Evaluation ==== +
- +
-Students are evaluated on both a project to be developed during the semesterand a written exam. The project work contributes 6/20 points to the overall score, and the written exam contributes the remaining 14/20 points. Participation in both the project work and the written exam are mandatory requirements for passing the course. +
- +
-===== COURSE TRAJECTORY ===== +
- +
-==== Lecture 1: Course Introduction and Translation of SQL into the Relational Algebra ​ ==== +
- +
-  *  During lecture 1 we refresh the basic background knowledge on relational database management systems (relations, relational algebra, SQL). To re-acquaint yourself with the relevant background knowledge, you are expected to read thoroughly chapter 1, chapter 2 (only sections 2.2 and 2.4), chapter 5 (only sections 5.1 and 5.2) and 6 from the handbook TCB. +
- +
-  * During lecture 1 ({{:​teaching:​infoh417:​slides-lect1.pdf|slides}})we present an overview of the architecture of a query compiler (see chapter 16, sections 16.1, 16.3.1 ​and  ​16.3.2 in the book) and study the translation of SQL into the extended relational algebra (see {{:​teaching:​infoh417:​sql2alg_eng.pdf|course notes}} for the full translation algorithm). +
- +
-  * You are expected to solve exercise 1 of the {{:​teaching:​infoh417:​01-sql2alg-ex.pdf|translation exercises (pdf)}} by the exercise session ​ of friday 27 september. Exercise 2 gives extra exercise possibilities,​ but will not be corrected in class. +
- +
-  * The {{:​teaching:​infoh417:​01_-_sql2alg-sol-slides.pdf|solutions}} of the translation exercises are available. +
- +
-==== Lecture 2: Optimization of Logical Query Plans  ==== +
- +
-  * During lecture 2 ({{:​teaching:​infoh417:​slides-lect2.pdf|slides}})we study optimization ​of the select-project-join expressions (see {{:​teaching:​infoh417:​conjunctive_eng.pdf|course notes}} for the full optimization algorithm and its correctness). In additionwe discuss popular heuristics for improving general logical query plans: ​see chapter 16, section 16.3.3 in the book which discusses the simple (but very important) logical optimizations of “pushing” selections and projections;​ and recognizing joins, based on the algebraic equalities from section 16.2. +
- +
-  * You are expected to solve exercises 1.1, 3.1, 4.1, 5, 6, and 8.1 of the {{:​teaching:​infoh417:​02-logicalopt-ex.pdf|optimization exercises}} ​ by the exercise session of friday, october 6. You are strongly advised to also try exercises 2, 3, and 4, although these exercises will not be corrected during that session. The remaining exercises give extra exercise possibilities. +
- +
-  * A summary of [[:teaching:​infoh417:​logicalopt-additional|common questions and answers, mistakes and questions regarding the optimization of logical query plans]] is also available. +
- +
-  * The {{:​teaching:​infoh417:​02_-_logicalopt-sol-slides.pdf|solutions}} of the optimization exercises are online. +
- +
- +
-==== Reading Assignment 1: Physical data organisation ​ ==== +
- +
-   * We take an intermezzo in the compilation of SQL to logical query plans, and consider how a DBMS physically organizes its data on disk.  ({{:​teaching:​infoh417:​slides-ra1.pdf|slides}}). The details may be found in chapter 13 of the book and constitute the first reading assignment. +
- +
-==== Lecture 3: Index Structures ​ ==== +
- +
-  * During Lecture 3 ({{:​teaching:​infoh417:​slides-lect3-part1.pdf|slides part I}},  {{:​teaching:​infoh417:​slides-lect3-part2.pdf|slides part II}}) we study sparse and dense index structures, and BTrees. The details are found in chapter 14, sections 14.1 and 14.2 in the book. +
- +
-==== Lecture 4: More Index Structures ​ ==== +
- +
-  * During Lecture 4 ({{:​teaching:​infoh417:​slides-lect4-part1.pdf|slides}},​ {{:​teaching:​infoh417:​slides-ch13-indexstruc.odp|slides in OpenOffice Impress format}}) we have studied index structures based on hashing. Hash-based indexes are discussed in depth in section 14.3 and 15.7 in the book. +
-   +
-  * In addition, we have also introduced data warehouses {{:​teaching:​infoh417:​slides-lect5.pdf|slides}}) and motivated the need for multidimensional index structures. Subsequently,​ we  and have studied various index structures that deal gracefully with multidimensional search keys. See sections 14.4-14.6, pages 661-688 (in the international edition) or pages 649-676 (in the new international edition) of the book. +
- +
-==== Project Assignment: External Memory Algorithms ==== +
- +
-  * In this assignment you are asked to implement an external-memory merge-sort algorithm, and examine its performance under different parameters. Be sure to visit the [[teaching:​infoh417:​project|project'​s page]] for full details and modalities.  +
- +
-==== Lecture 5: Physical Operators ==== +
- +
-  * In lecture 5 ({{:​teaching:​infoh417:​slides-lect6.pdf|slides}}),​ we study the basic algorithms for physical operators, together with their cost analysis. The details (including some algorithms not discussed during the lecture) can be found in chapter 15 sections 15.1 until 15.6, pages 701-746 (in the international edition) or pages 689-734 (in the new international edition). The interested reader is also advised to read Section 15.7 (although this will not be interrogated during the exam). +
- +
-  * You are expected to solve exercise 1 of the {{:​teaching:​infoh417:​03-physicalop-ex.pdf|physical operators exercises}} by the exercise session of November 8.  The {{:​teaching:​infoh417:​03-physicalop-sol-slides.pdf|solutions}} are online. +
- +
-==== Lecture 6: Cost-Based Plan Selection ==== +
-   * During lecture 6 ({{:​teaching:​infoh417:​slides-lect7.pdf|slides}}),​ we study the problems that occur when translating a logical query plan into an (optimal) physical query plan (i.e., estimating the sizes of subresults and join ordering). The details can be found in Chapter 16 (Sections 16.4 until 16.8, pages 792-839 in the international edition or pages 780-827 in the new international edition). +
- +
-  * You are expected to solve exercise 2 of the {{:​teaching:​infoh417:​04-costbasedsel-ex.pdf|cost-based plan selection exercises}} ​ by the exercises session of **November 15**.   The solutions {{:​teaching:​infoh417:​04-costbasedsel-sol-slides.pdf|are online}}. +
- +
-==== Lecture 7: Coping with System Failures ​ ==== +
- +
-  * During lecture 7 {{:​teaching:​infoh417:​slides-lect8-part1.pdf|slides part 1}} {{:​teaching:​infoh417:​slides-lect8-part2.pdf|slides part 2}} we gave a short introduction to transaction processing in general, and dove into coping with systems failures in particular. The details may be found in chapter 17 of the book. +
- +
-  * You are expected to solve the integrated exercise 8.2 of the {{:​teaching:​infoh417:​02-logicalopt-ex.pdf|optimization exercises}},​ and 3.5 of the {{:​teaching:​infoh417:​04-costbasedsel-ex.pdf|cost-based plan selection exercises}} by the exercise session of **Friday, November 22**. **It is strongly suggested that you try doing these exercises, as they are typical exam questions.** ​  +
- +
-  * You are expected to solve exercises 17.2.2, 17.2.4, 17.2.5, 17.2.7, 17.3.2, 17.3.3, 17.3.4, 17.3.5, 17.4.2, 17.4.3, 17.4.4, and 17.4.5 in the book by exercise session of **Friday, November 29**.  {{:​teaching:​infoh417:​05_-_logging-sol-slides.pdf|The solutions are online.}} +
- +
-==== Lecture 8: Integrated exercises ​ ==== +
- +
-  * During lecture 8 we focused on solving integrated exercises 8.2 of the {{:​teaching:​infoh417:​02-logicalopt-ex.pdf|optimization exercises}},​ and 3.5 of the {{:​teaching:​infoh417:​04-costbasedsel-ex.pdf|cost-based plan selection exercises}}. +
- +
-  * {{:​teaching:​infoh417:​07-integrated-slides.pdf|The solutions are online.}} +
- +
- +
-==== Lecture 9: Concurrency control ==== +
- +
-  * During lecture 9 ({{:​teaching:​infoh417:​slides-lect9.pdf|slides}}),​ we studied the problems that can occur when a database runs many transactions concurrently and the different kinds of scheduling algorithms that can prevent these problems. The details can be found Chapter 18 (sections 18.5, 18.6. 18.7 is excluded). +
- +
-  * You are expected to solve exercises ​ 18.2.4(b,​d,​e),​ 18.8.1(b,​d),​ 18.8.2 (a,c), and 18.9.1 (c,f)  by the response lecture of **Friday, December 6**.  {{:​teaching:​infoh417:​06_-_concurrency.pdf|The solutions are online.}} +
- +
- +
- +
- +
- +
-==== Revision session ==== +
- +
-Durig the lecture & exercise session ​ of **Friday, december 6** you have the opportunity to  ask questions on the theory and exercises. In particular, if you would like to have a certain part of a lecture re-explained,​ or an exercise re-corrected,​ then this is possible **provided that you let prof. Vansummeren know your question by monday, december 2 at the latest**.  +
-  +
-The slides of the revision lecture {{:​teaching:​infoh417:​qa_slides.pdf|are online.}}+
 
teaching/infoh417.txt · Last modified: 2020/09/10 08:46 by svsummer