CS157b Spring 2023Practice Midterm

Studying for one of my tests does involve some memorization. I believe this is an important skill. Often people waste a lot of time and fail to remember the things they are trying to memorize. Please use a technique that has been shown to work such as the method of loci. Other memorization techniques can be found off the Wiki Page for Moonwalking with Einstein. Given this, to study for the midterm I would suggest you:

• Know how to do (by heart) all the practice problems.
• Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
• Go over the homework problems.
• Try to create your own problems similar to the ones I have given and solve them.
• Skim the relevant sections from the book.
• If you want to study in groups, at this point you are ready to quiz each other.

The practice midterm is below. Here are some facts about the actual midterm: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) One problem (less typos) on the actual test will be from the practice test.

1. Draw a diagram of the memory hierarchy. Briefly describe the different kinds of cache memory.
2. What is the I/O model of computation? How can disk striping help up access to large relations in this model?
3. Suppose the odds that a disk drive fails in a given year is 1/4. Suppose we are using Raid 4 with three drives. What is the mean time till data is lost if it takes 3 hours to replace a broken drive?
4. Give an example of three things that might be stored in a record header and three things that might be stored in a block header.
5. Suppose 100 records for some table T can fit into a 8k block. Suppose an index entry takes 16 bytes and we can completely fill all but 48 bytes of an index block. If T takes 500 million blocks to store, how many blocks would a dense index on T be? How many block would a sparse index take?
6. How are relations stored on disk (file format and its implementation) for Mysql? For Sqlite?
7. Give an example with data and concrete choices for implementation showing a query that a grid file would perform better than a partitioned hash file.
8. Explain and give an example of how two pass hashing can be used to do duplicate elimination.
9. Suppose the block size was 2048, where 48 bytes are used for header info. Suppose had a 4,000,000 tuple relation. Suppose tuple size goes from 100 bytes long to 10 bytes long after a projection. How many block would be needed to store all the tuple before and after doing this projection?
10. What is a left deep join tree? What is branch and bound plan enumeration?