Outline & Objectives
| Course Outline | Query processing is a central database research area. It deals with how to find correct result fast from large database given a query. With the advanced of the computer technology, the amount of data gets bigger and bigger in the many application domains. This requires more efficient query processing. - This course starts with the basic review of the disk storage. Then it also briefly reviews the basic file structures: record files, index structures (including B-tree), hash tables, etc. Advanced index structures such as multidimensional files and bitmap indexes are presented too. - After reviewing frequently used access methods, this course discuss query processing. It first discusses how to execute queries by examining one-pass and two-pass algorithms for database operations. Then it discusses how to compile queries. Query parsing and query optimization issues will be examined. |
| Learning Objectives | Query processing is a central database research area. It deals with how to find correct result fast from large database given a query. With the advanced of the computer technology, the amount of data gets bigger and bigger in the many application domains. This requires more efficient query processing. - This course starts with the basic review of the disk storage. Then it also briefly reviews the basic file structures: record files, index structures (including B-tree), hash tables, etc. Advanced index structures such as multidimensional files and bitmap indexes are presented too. - After reviewing frequently used access methods, this course discuss query processing. It first discusses how to execute queries by examining one-pass and two-pass algorithms for database operations. Then it discusses how to compile queries. Query parsing and query optimization issues will be examined. |
Textbooks & References
| Title | Author(s) | Publisher | Year | ISBN |
|---|---|---|---|---|
| Database Systems: The Complete Book | Hector Garcia Molina, Jeffrey D. Ullman, and Jennifer Widom | Prentice Hall | 2002 | |
| Principles of Database Query Processing for Advanced Applications | Clement T. Yu and Weiyi Meng | Morgan Kaufmann | 1997 | |
| Query Processing for Advanced Database Systems | Christoph Freytag, David Maier, and Gottfried Vossen | Morgan Kaufmann | 1993 |
Evaluation Criteria
| Mid Term | 30% |
| Final Term | 30% |
| Assignments | 30% |
| Presentation | 0% |
| Attendance | 10% |
Lecture Schedule
| Week | Lecture Topics and Contents |
|---|---|
| Week 1 | Data Storage |
| Week 2 | Representing Data Elements |
| Week 3 | Index Structures |
| Week 4 | Multidimensional Indexes and Bitmap Indexes 1 |
| Week 5 | Multidimensional Indexes and Bitmap Indexes 2 |
| Week 6 | Query Execution: Introduction to Physical-Query-Plan Operators |
| Week 7 | Query Execution: One-Pass Algorithms for Database Operations |
| Week 8 | Midterm Exam |
| Week 9 | Query Execution: Two-Pass Algorithms Based on Sorting and Hashing |
| Week 10 | Query Execution: Indexed-Based Algorithms, Buffer Management |
| Week 11 | Query Execution: Algorithms Using More Than Two Passes, Parallel Algorithms for Relational Operators |
| Week 12 | Query Compiler: Parsing, Algebraic Laws for Improving Query Plans |
| Week 13 | Query Compiler: From Parse Trees to Logical Query Plans, Estimating the Cost of Operations |
| Week 14 | Query Compiler: Introduction to Cost-Based Plan Selection, Choosing an Order for Joins |
| Week 15 | Query Compiler: Completing the Physical-Query-Plan |
| Week 16 | Final Exam |