CS W186 Introduction to Database Systems
Spring 2020 Josh Hug, Michael Ball DIS 4
1 Buffer Management
(a) Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern A B C D A F A D G D G E D F
Red frame outline is where the clock hand points at the end of the access
Yellow frame outline is where the clock hand considered ejecting a page, but the bit was one Red box means the second chance bit is zero
Green box means the second chance bit is one
* means a hit
CS W186, Spring 2020, DIS 4 1
(b) Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F Remember that unpinning does not contribute to the hit count!
(c) Is MRU ever better than LRU?
Yes; MRU prevents sequential flooding during sequential scans
(d) Why would we use a clock replacement policy over LRU?
Efficiency (approximation of LRU; don¡¯t need to maintain entire ordering)
(e) Why would it be useful for a database management system to implement its own buffer re- placement policy? Why shouldn¡¯t we just rely on the operating system?
The database management system knows its data access patterns, which allows it to optimize its buffer replacement policy for each case
CS W186, Spring 2020, DIS 4 2
2 Relational Algebra
Why do we care about relational algebra? Why do you think it might be useful?
Relational algebra are plans to execute queries; the many ways of writing the plans give the system room to design for optimizations. We will learn more about how to estimate the cost of the plan in the future.
Consider the schema:
Write relational algebra expressions for the following queries:
(a) Find the name of the artists who have albums with a genre of either ¡¯pop¡¯ or ¡¯rock¡¯.
(b) Find the name of the artists who have albums of genre ¡¯pop¡¯ and ¡¯rock¡¯.
(c) Find the id of the artists who have albums of genre ¡¯pop¡¯ or have spent over 10 weeks in the top 40.
(d) Find the names of all artists who do not have any albums.
CS W186, Spring 2020, DIS 4 3