This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
teaching:infoh417 [2015/11/26 14:46] svsummer [COURSE TRAJECTORY] |
teaching:infoh417 [2016/12/09 13:25] svsummer [COURSE TRAJECTORY] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== INFO-H-417 : Database Systems Architecture ====== | ====== INFO-H-417 : Database Systems Architecture ====== | ||
| + | <note tip> The written exam of INFOH417 is planned on monday, 16 january 2017 from 14h00-17h30 in room S.UB5.230. The exam is closed book. | ||
| - | <note important>If you are following this course, it is mandatory that you fill out [[https://docs.google.com/forms/d/1R5gEJiYDUpCyZBzfIvneVmEwJkr3UxCfbn3-j1hl43E/viewform|this form]] by **friday, 25 september at the latest**. This enables the course instructors to contact you in the future, as well as form an idea on your background.</note> | + | To help you in preparing for the exam, two prior exams are now available: {{:teaching:infoh417:ex-2011-s2.pdf|prior exam 1}} and {{:teaching:infoh417:ex-2012-s1.pdf|prior exam 2}}</note> |
| + | <note important>The project gropus are posted (see [[http://cs.ulb.ac.be/public/teaching/infoh417/project|project page]])</note> | ||
| ===== GENERAL INFORMATION ===== | ===== GENERAL INFORMATION ===== | ||
| Line 31: | Line 32: | ||
| * **Lecturer**: [[http://code.ulb.ac.be/code.people.php?id=992|Stijn Vansummeren]] (Campus Solbosh, Building U, 4th floor, room UB4.125) | * **Lecturer**: [[http://code.ulb.ac.be/code.people.php?id=992|Stijn Vansummeren]] (Campus Solbosh, Building U, 4th floor, room UB4.125) | ||
| - | * **Assistant**: [[http://code.ulb.ac.be/smg.people.php?id=907|Stefan Eppe]] (Campus Solbosh, Building U, 4th floor, room UB4.131) | + | |
| ==== Organisation ==== | ==== Organisation ==== | ||
| Line 56: | Line 57: | ||
| * 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). | * 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 25 september. Exercise 2 gives extra exercise possibilities. | + | * You are expected to solve exercise 1 of the {{:teaching:infoh417:01-sql2alg-ex.pdf|translation exercises (pdf)}} by the exercise session of friday 30 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. | + | |
| + | * The {{:teaching:infoh417:01_-_sql2alg-sol-slides.pdf|solutions}} of the translation exercises are available. | ||
| ==== Lecture 2: Optimization of Logical Query Plans ==== | ==== 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 addition, *next week* we will 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. | + | * During lecture 2 ({{:teaching:infoh417:slides-lect2-handout.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 addition, we 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 2. 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. | * 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 2. 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. | ||
| - | |||
| - | * The {{:teaching:infoh417:02_-_logicalopt-sol-slides.pdf|solutions}} of the optimization exercises are online. | ||
| * A summary of [[:teaching:infoh417:logicalopt-additional|common questions and answers, mistakes and questions regarding the optimization of logical query plans]] is also available. | * 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 ==== | ==== 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, which is to be performed instead of the lecture of friday, october 2. | + | * 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 ==== | ==== Lecture 3: Index Structures ==== | ||
| Line 87: | Line 88: | ||
| * 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. | * 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: Multidimensional Index Structures ==== | + | ==== Reading Assignment 2 and lecture 5: Multidimensional Index Structures ==== |
| - | * During lecture 5 ({{:teaching:infoh417:slides-lect5.pdf|slides}}) we will study various index structures that deal gracefully with multidimensional search keys. The details may be found in sections 14.4-14.6, pages 661-688 (in the international edition) or pages 649-676 (in the new international edition) of the book. | + | * There is no class on friday 28 October. Instead you are asked to read sections 14.4-14.6, pages 661-688 (in the international edition) or pages 649-676 (in the new international edition) of the book. This concerns various index structures that deal gracefully with multidimensional search keys ({{:teaching:infoh417:slides-lect5.pdf|slides}}). |
| - | + | ||
| - | ==== Lab 1: The I/O Model of Computation and Physical Layout ==== | + | |
| - | + | ||
| - | * During Lab 1 ({{:teaching:infoh417:btree_lab1.pdf|handouts}},{{:teaching:infoh417:btree_lab1-sol.pdf|solution}}) we look at the architecture of a database prototype, and in particular at how a relation stored on disk can be read one block at a time. The code for this lab is available as a [[http://wit-projects.ulb.ac.be/rhodecode/INFO-H-417/Labs/Lab-1/summary|git repository]]. | + | |
| ==== Lecture 6: Physical Operators ==== | ==== Lecture 6: Physical Operators ==== | ||
| Line 99: | Line 96: | ||
| * In lecture 6 ({{: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). | * In lecture 6 ({{: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}} ({{:teaching:infoh417:03-physicalop-sol-slides.pdf|solutions}}) by the exercise session of November 6. You are strongly advised to also try exercise 2 although that exercises will not be corrected during that response lecture. | + | * You are expected to solve exercise 1 of the {{:teaching:infoh417:03-physicalop-ex.pdf|physical operators exercises}} by the exercise session of November 25. The {{:teaching:infoh417:03-physicalop-sol-slides.pdf|solutions}} are online. |
| - | + | ||
| - | ==== Lab 2: The BTree Index Structure ==== | + | |
| - | + | ||
| - | * During Lab 2 ({{:teaching:infoh417:btree_lab2.pdf|handouts}}/*, {{:teaching:btree_lab2-sol.pdf|solutions}}*/) we instantiate a BTree in the database prototype that we used during Lab 1, and study how it can be used to improve query processing. We also delve into the internals of the BTree implementation to understand its layout on disk. The code for this lab is available as a [[http://wit-projects.ulb.ac.be/rhodecode/INFO-H-417/Labs/Lab-2/summary|git repository]]. | + | |
| ==== Lecture 7: Cost-Based Plan Selection ==== | ==== Lecture 7: Cost-Based Plan Selection ==== | ||
| * During lecture 7 ({{:teaching:infoh417:slides-lect7.pdf|slides}}), we will 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). | * During lecture 7 ({{:teaching:infoh417:slides-lect7.pdf|slides}}), we will 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 27**. | + | * 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 **December 2**. The solutions {{:teaching:infoh417:04-costbasedsel-sol-slides.pdf|are online}}. |
| ==== Lecture 8: Coping with System Failures ==== | ==== Lecture 8: Coping with System Failures ==== | ||
| * During lecture 8 {{:teaching:infoh417:slides-lect8-part1.pdf|slides part 1}} {{:teaching:infoh417:slides-lect8-part2.pdf|slides part 1}} 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. | * During lecture 8 {{:teaching:infoh417:slides-lect8-part1.pdf|slides part 1}} {{:teaching:infoh417:slides-lect8-part2.pdf|slides part 1}} 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, December 4**. **It is strongly suggested that you try doing these exercises, as they are typical exam questions.** | + | * 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, December 9**. **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, December 4**. | + | * 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, December 9**. |
| ==== Lecture 9: Concurrency control ==== | ==== 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 (section 18.7 is excluded). | + | * 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 as is section 18.9 on validation-based schedulers). |
| + | |||
| + | * You are expected to solve exercises 18.2.4(b,c,e), 18.8.1(b,d), 18.8.2 (a,c), and 18.9.1 (c,f) by the response lecture of **Friday, December 16**. | ||
| - | * You are expected to solve exercises 18.2.4(b,c,e), 18.8.1(b,d), 18.8.2 (a,c), and 18.9.1 (c,f) by the response lecture of **Friday, December 4**. | ||
| ==== Revision session ==== | ==== Revision session ==== | ||
| - | Durig the lecture & exercise session of **Friday, december 11** 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 7 at the latest**. | + | Durig the lecture & exercise session of **Friday, december 16** 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 12 at the latest**. |
| + | |||
| + | This last lecture also features a demo that illustrates how the theory on query optimization that we have studied is applied in practical database management systems. | ||