CS 334: Exam 3 topics

Table of Contents

Notes sheet

You are permitted one 8.5 x 11 handwritten notes sheet (both sides) for use as a reference during the exam.

How to study

Lots of research has shown that purely reading over material isn't a very good way to prepare for exams. Practice is also important. Reading how to swing a baseball bat or how to cross-country ski might be important for giving you some good ideas on how to get better the next time you try it, but it's doesn't substitute for actually getting out there and trying those ideas by swinging a bat or skiing in the Arb.

How can you practice? Go back to look at the homework problems. Can you do them from scratch on paper? Furthermore, the textbook has a strong set of practice problems, with solutions online. Make sure to do all of your practicing on paper, not at a keyboard, so as to simulate the exam conditions.

Remember that you have a textbook. Its content is much better than what you'll find with random web searches, and I'm basing my notation and content on it. It is a much more effective use of your time to use the textbook as a reference rather than trying to find random web pages that may or may match what we've covered.

Exam content

Listed below is the material that I have in mind that you should know for the exam. It's what's in my head when creating it. That said, this isn't a contract. I may have inadvertently left something off this list that ends up on an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

There's more in the textbook than what we've covered; I will only be asking exam questions about content that has either been discussed in class or has appeared on homework assignments.

Indexing (chapter 11)

Be able to show detailed examples of how inserting and deleting works in B+ trees and extendable hashing when sufficient assumptions on implementation are provided. Be able to explain advantages and disadvantages of each of the above techniques, and why each might be chosen. Be able to work out approximate I/O costs for retrieving data using a particular indexing technique.

Query Evaluation (chapter 12)

Be able to explain and/or demonstrate…

  • algorithms used for selection, projection, join
  • how approximate costs for such operations are calculated
  • various join algorithms such as simple nested loops, block nested loops, multi-block nested loops, index nested loops, sort merge join, and hash join, and I/O costs associated with these techniques
  • external sort and associated costs

Query Optimization (chapter 13)

Be able to evaluate alternative query evaluation strategies to determine which is more likely to be chosen. Be able to generate query evaluations strategies for a particular query, and indicate how to decide amongst them. Be able to describe how query optimizer approaches above problems, and show specific examples.