程序代写代做代考 SQL database cache algorithm CSci 4707: Practice of Database Systems

CSci 4707: Practice of Database Systems
Lab 2
Spring 2017

Due: ​03/21/2017 ​18:30 ​ on Moodle
There will be a 10% penalty off your grade for a 24 hours late submission.
This lab has to be done in a group of two.

A. Introduction

This lab needs to be done in a group of two. You are going to change the buffer replacement
policy that is currently used in PostgreSQL, a major open source DMBS. In particular, the
original replacement policy of PostgreSQL is a clocksweep algorithm with LRU (Least Recently
Used). In this lab, you are asked to implement an MRU (Most Recently Used) replacement
policy without using the clocksweep algorithm.

B. Most Recently Used

The basic idea of MRU can be seen in ​here ​. However, you will need to adapt the algorithm with
the Database buffer management policy concept, e.g., pin count.

C. Setting-Up PostgreSQL (Same as Lab 1)

PostgreSQL is a large software. You will want at least 200 MB of space in your machine.
Download version 9.6.1 of PostgreSQL and create the installation location by executing the
following commands:

// Download the PostgreSQL and extract it.
$wget ​https://ftp.postgresql.org/pub/source/v9.6.1/postgresql-9.6.1.tar.gz
$tar xvzf postgresql-9.6.1.tar.gz

// Create the installation folder, called “install”.
$mkdir install

Then, we retrieve the full path of both source and installation folder by executing the following
command:

// Retrieve the full path of the directory.
$pwd

https://en.wikipedia.org/wiki/Cache_replacement_policies#Most_Recently_Used_.28MRU.29
https://ftp.postgresql.org/pub/source/v9.6.1/postgresql-9.6.1.tar.gz

# This will return a full path of your current directory. Throughout this
documentation, this path is called as $W$. ​So, Don’t forget to replace it with
your actual working directory.

Thus, the path of the PostgreSQL’s source code is located at ​“$W$/postgresql-9.6.1” ​ and the
path where we will install PostgreSQL is located at ​“$W$/install”.

Next, you will configure the installation of PostgreSQL and install PostgreSQL on the given path
by executing the following commands:

// Go to the source directory.
$cd postgresql-9.6.1

// Run the configure command. ​Don’t forget to change $W$ to your actual
directory.
$./configure –prefix=$W$/install

// Run the makefile.
$make
# You should see the following output.
All of PostgreSQL successfully made. Ready to install.

// Run the installation.
$make install
# You should see the following output.
PostgreSQL installation complete.

After the installation has finished, you will need to initialize and create a database to use. In this
example, we will initialize the database at ​“$W$/install/data” ​ folder by executing the
following command:

// Go to the installation folder.
$cd ../install
// Initialize database.
$bin/initdb -D data

Once the database has been initialized, we can start the PostgreSQL backend by executing the
following command:

// Execute the backend.
$bin/postgres -D data

We can then use this terminal to get information on what is happening in our DBMS.

To run the client, open another terminal and use the following command to create a database
to use: (In this example, we call the database as ProjectDB)

// Create the ProjectDB database.
$cd $W$/install
$bin/createdb -h localhost ProjectDB

We interact with our DBMS by using a program called psql. To start psql, use the following
command:

// Run psql
$bin/psql -h localhost ProjectDB

The next time you want to start the database again, you only need to run two consoles where
one is for the backend and one is for the psql console:

// Execute the backend.
$bin/postgres -D data

// Execute the psql console.
$bin/psql -h localhost ProjectDB

Several important commands for the lab are:

// You ​must​ exit psql by typing the following command and do ​not ​use Ctrl+C
ProjectDB=#\q

// To run an sql script located at $W$/script.sql
ProjectDB=#\i $W$/script.sql

D. Modification

Most (if not all) of your changes will be located in the following directory:
“$W$/postgresql-9.6.1/src/backend/storage/buffer/”.
To implement the MRU algorithm, you will want to maintain the timestamp of each buffer when
they are called or used. For simplicity, you will maintain a global integer value which will be
assigned to a buffer whenever a buffer page is requested, then, increment the integer.

For verifying the correctness of your implementation, you need to print out the timestamp of all
candidate (not in use) buffers as: “Candidate buffers: ”