- Details
- Parent Category: Programming Assignments' Solutions
We Helped With This C Programming Homework: Have A Similar One?
Short Assignment Requirements
Assignment Description
Assignment 1 - Storage Manager
The goal of this assignment is to implement a simple storage manager - a module that is capable of reading blocks from a file on disk into memory and writing blocks from memory to a file on disk. The storage manager deals with pages (blocks) of fixed size (PAGE_SIZE). In addition to reading and writing pages from a file, it provides methods for creating, opening, and closing files. The storage manager has to maintain several types of information for an open file: The number of total pages in the file, the current page position (for reading and writing), the file name, and a POSIX file descriptor or FILE pointer. In your implementation you should implement the interface described below. Please commit a text file README.txt that (shortly) describes the ideas behind your solution and the code structure. Comment your code!
Interface
The interface your storage manager should implement is given as a header file storage_mgr.h. The content of this header is shown below. Two additional headers dberror.h and test_helpers.h define error codes and constants and macros used in the test cases.
#ifndef STORAGE_MGR_H
#define STORAGE_MGR_H
#include "dberror.h"
/************************************************************
* handle data structures *
************************************************************/
typedef struct SM_FileHandle {
char *fileName;
int totalNumPages;
int curPagePos;
void *mgmtInfo;
} SM_FileHandle;
typedef char* SM_PageHandle;
/************************************************************
* interface *
************************************************************/
/* manipulating page files */
extern void initStorageManager (void);
extern RC createPageFile (char *fileName);
extern RC openPageFile (char *fileName, SM_FileHandle *fHandle);
extern RC closePageFile (SM_FileHandle *fHandle);
extern RC destroyPageFile (char *fileName);
/* reading blocks from disc */
extern RC readBlock (int pageNum, SM_FileHandle *fHandle, SM_PageHandle memPage);
extern int getBlockPos (SM_FileHandle *fHandle);
extern RC readFirstBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC readPreviousBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC readCurrentBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC readNextBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC readLastBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
/* writing blocks to a page file */
extern RC writeBlock (int pageNum, SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC writeCurrentBlock (SM_FileHandle *fHandle, SM_PageHandle memPage);
extern RC appendEmptyBlock (SM_FileHandle *fHandle);
extern RC ensureCapacity (int numberOfPages, SM_FileHandle *fHandle);
#endif
Data structures
The page size is hard-coded in the header file dberror.h (PAGE_SIZE). Each of the methods defined in the storage manager interface returns an integer return code also defined in dberror.h (RC). For details see return codes below.
The methods in the interface use the following two data structures to store information about files and pages:
File Handle SM_FileHandle
A file handle SM_FileHandle represents an open page file. Besides the file name, the handle store the total number of pages in the file and the current page position. The current page position is used by some of the read and write methods of the storage manager. For example, readCurrentBlock reads the curPagePosth page counted from the beginning of the file. When opening a file, the current page should be the first page in the file (curPagePos=0) and the totalNumPages has to be initialized based on the file size. Use the mgmtInfo to store additional information about the file needed by your implementation, e.g., a POSIX file descriptor.
Hint: You should reserve some space in the beginning of a file to store information such as the total number of pages.
Hint: Use mgmtInfo to store any bookkeeping info about a file your storage manager needs.
typedef struct SM_FileHandle {
char *fileName;
int totalNumPages;
int curPagePos;
void *mgmtInfo;
} SM_FileHandle;
Page Handle SM_PageHandle
A page handle is an pointer to an area in memory storing the data of a page. Methods that write the data pointed to by a page handle to disk or read a page from disk into the area of memory pointed to by the page handle require that the handle is pointing to an previously allocated block of memory that is at least PAGE_SIZE number of bytes long.
typedef char* SM_PageHandle;
File Related Methods
createPageFile
Create a new page file fileName. The initial file size should be one page. This method should fill this single page with ' ' bytes.
openPageFile
Opens an existing page file. Should return RC_FILE_NOT_FOUND if the file does not exist. The second parameter is an existing file handle. If opening the file is successful, then the fields of this file handle should be initialized with the information about the opened file. For instance, you would have to read the total number of pages that are stored in the file from disk.
closePageFile, destroyPageFile
Close an open page file or destroy (delete) a page file.
Read and Write Methods
There are two types of read and write methods that have to be implemented: Methods with absolute addressing (e.g., readBlock) and methods that address relative to the current page of a file (e.g., readNextBlock).
readBlock
The method reads the pageNumth block from a file and stores its content in the memory pointed to by the memPage page handle. If the file has less than pageNum pages, the method should return RC_READ_NON_EXISTING_PAGE.
getBlockPos
Return the current page position in a file
readFirstBlock, readLastBlock
Read the first respective last page in a file
readPreviousBlock, readCurrentBlock, readNextBlock
Read the current, previous, or next page relative to the curPagePos of the file. The curPagePos should be moved to the page that was read. If the user tries to read a block before the first page of after the last page of the file, the method should return RC_READ_NON_EXISTING_PAGE.
writeBlock, writeCurrentBlock
Write a page to disk using either the current position or an absolute position.
appendEmptyBlock
Increase the number of pages in the file by one. The new last page should be filled with zero bytes.
ensureCapacity
If the file has less than numberOfPages pages then increase the size to numberOfPages.
Return codes
The header file dberror.h defines several error codes as macros. As you may have noticed the storage manager functions all return an RC value. This value should indicate whether an operation was successful and if not what type of error occurred. If a method call is successful, the function should return RC_OK. The printError function can be used to output an error message based on a return code and the message stored in global variable RC_message (implemented in dberror.c).
Source Code Structure
You source code directories should be structured as follows.
· Put all source files in a folder assign1 in your git repository
· This folder should contain at least ...
o the provided header and C files
o a make file for building your code Makefile. This makefile should create a binary from test_assign1 from test_assign1_1.c which requires dberror.c and all your C files implementing the storage_mgr.h interface
o a bunch of *.c and *.h files implementing the storage manager
o README.txt: A text file that shortly describes your solution
E.g., the structure may look like that:
git
assign1
README.txt
dberror.c
dberror.h
storage_mgr.c
storage_mgr.h
test_assign1_1.c
test_helper.h
Makefile
Test cases
We have provided a few test case in test_assign1_1.c. You makefile should create an executable test_assign1 from this C file. You are encouraged to write additional tests. Make use of existing debugging and memory checking tools. However, usually at some point you will have to debug an error. See the main assignment page for information about debugging.
....
Assignment Description
Assignment 2 - Buffer Manager
You should implement a buffer manager in this assignment. The buffer manager manages a fixed number of pages in memory that represent pages from a page file managed by the storage manager implemented in assignment 1. The memory pages managed by the buffer manager are called page frames or frames for short. We call the combination of a page file and the page frames storing pages from that file a Buffer Pool. The Buffer manager should be able to handle more than one open buffer pool at the same time. However, there can only be one buffer pool for each page file. Each buffer pool uses one page replacement strategy that is determined when the buffer pool is initialized. You should at least implement two replacement strategies FIFO and LRU. Your solution should implement all the methods defined in the buffer_mgr.h header explained below.
Make use of existing debugging and memory checking tools. At some point you will have to debug an error. See the main assignment page for information about debugging. Memory leaks are errors!
Buffer Pool Functionality and Concepts
A buffer pool consists of a fixed amount of page frames (pages in memory) that are used to store disk pages from a page file in memory. Clients of the buffer manager can request pages identified by their position in the page file (page number) to be loaded in a page frame. This is called pinning a page. Internally, the buffer manager has to check whether the page requested by the client is already cached in a page frame. If this is the case, then the buffer simply returns a pointer to this page frame to the client. Otherwise, the buffer manager has to read this page from disk and decide in which page frame it should be stored (this is what the replacement strategy is for). Once an appropriate frame is found and the page has been loaded, the buffer manager returns a pointer to this frame to the client. The client can then start to read and/or modify that page. Once the client is done with reading or writing a page, he needs to inform the buffer manager that he no longer needs that page. This is called unpinning. Furthermore, the buffer manager needs to know whether the page was modified by the client. This is realized by requiring the client to call a function to tell the buffer manager that the page is dirty. The buffer needs this information for replacing pages in the buffer pool. If a dirty page is evicted from the buffer pool, then the buffer manager needs to write the content of this page back to disk. Otherwise, the modifications done by the client would be lost. Since buffer pools are used concurrently by several components of a DBMS, the same page can be pinned by more than one client. Making the functions of the buffer manager thread-safe is not part of the assignment. The number of clients having pinned a page is called the fix count of that page. The buffer manager can only evict pages with fix count 0 from the pool, because a non-zero fix count indicates that at least one client is still using the page. Pinning a page increases its fix count by 1, unpinning the page reduces its fix count.
Some hints and reminders:
- Independent of the page replacement strategy, the buffer manager is only allowed to evict pages with fix count zero. This has to be taken into account when implementing page replacement strategies.
- Dirty pages can be evicted from the pool if they have a fix count 0, but have to be written back to disk before the eviction
- If a dirty page is written back to disk and has fix count 0, then it is no longer considered dirty.
- You buffer manager needs to maintain a mapping between page numbers and page frames to enable fast look-ups from page number to page frame and vice versa.
Optional Extensions
Realize these optional extensions for extra credit and extra fun. ;-)
- Make the buffer pool functions thread safe. This extension would result in your buffer manager being closer to real life buffer manager implementations.
- Implement additional page replacement strategies such as CLOCK or LRU-k.
Interface
The header for the buffer manager interface is shown below. Your solution should implement all functions defined in this header.
Data Structures
The header defines two important data structures. The BM_BufferPool and the BM_PageHandle.
The BM_BufferPool stores information about a buffer pool: the name of the page file associated with the buffer pool (pageFile), the size of the buffer pool, i.e., the number of page frames (numPages), the page replacement strategy (strategy), and a pointer to bookkeeping data (mgmtData). Similar to the first assignment, you can use the mgmtData to store any necessary information about a buffer pool that you need to implement the interface. For example, this could include a pointer to the area in memory that stores the page frames or data structures needed by the page replacement strategy to make replacement decisions.
typedef struct BM_BufferPool {
char *pageFile;
int numPages;
ReplacementStrategy strategy;
void *mgmtData;
} BM_BufferPool;
The BM_PageHandle stores information about a page. The page number (position of the page in the page file) is stored in pageNum. The page number of the first data page in a page file is 0. The data field points to the area in memory storing the content of the page. This will usually be a page frame from your buffer pool.
typedef struct BM_PageHandle {
PageNumber pageNum;
char *data;
} BM_PageHandle;
Buffer Pool Functions
These functions are used to create a buffer pool for an existing page file (initBufferPool), shutdown a buffer pool and free up all associated resources (shutdownBufferPool), and to force the buffer manager to write all dirty pages to disk (forceFlushPool).
initBufferPool creates a new buffer pool with numPages page frames using the page replacement strategy strategy. The pool is used to cache pages from the page file with name pageFileName. Initially, all page frames should be empty. The page file should already exist, i.e., this method should not generate a new page file. stratData can be used to pass parameters for the page replacement strategy. For example, for LRU-k this could be the parameter k.
shutdownBufferPool destroys a buffer pool. This method should free up all resources associated with buffer pool. For example, it should free the memory allocated for page frames. If the buffer pool contains any dirty pages, then these pages should be written back to disk before destroying the pool. It is an error to shutdown a buffer pool that has pinned pages.
forceFlushPool causes all dirty pages (with fix count 0) from the buffer pool to be written to disk.
Page Management Functions
These functions are used pin pages, unpin pages, mark pages as dirty, and force a page back to disk.
pinPage pins the page with page number pageNum. The buffer manager is responsible to set the pageNum field of the page handle passed to the method. Similarly, the data field should point to the page frame the page is stored in (the area in memory storing the content of the page).
unpinPage unpins the page page. The pageNum field of page should be used to figure out which page to unpin.
markDirty marks a page as dirty.
forcePage should write the current content of the page back to the page file on disk.
Statistics Functions
These functions return statistics about a buffer pool and its contents. The print debug functions explained below internally use these functions to gather information about a pool.
The getFrameContents function returns an array of PageNumbers (of size numPages) where the ith element is the number of the page stored in the ith page frame. An empty page frame is represented using the constant NO_PAGE.
The getDirtyFlags function returns an array of bools (of size numPages) where the ith element is TRUE if the page stored in the ith page frame is dirty. Empty page frames are considered as clean.
The getFixCounts function returns an array of ints (of size numPages) where the ith element is the fix count of the page stored in the ith page frame. Return 0 for empty page frames.
The getNumReadIO function returns the number of pages that have been read from disk since a buffer pool has been initialized. You code is responsible to initializing this statistic at pool creating time and update whenever a page is read from the page file into a page frame.
getNumWriteIO returns the number of pages written to the page file since the buffer pool has been initialized.
buffer_mgr.h
#ifndef BUFFER_MANAGER_H
#define BUFFER_MANAGER_H
// Include return codes and methods for logging errors
#include "dberror.h"
// Include bool DT
#include "dt.h"
// Replacement Strategies
typedef enum ReplacementStrategy {
RS_FIFO = 0,
RS_LRU = 1,
RS_CLOCK = 2,
RS_LFU = 3,
RS_LRU_K = 4
} ReplacementStrategy;
// Data Types and Structures
typedef int PageNumber;
#define NO_PAGE -1
typedef struct BM_BufferPool {
char *pageFile;
int numPages;
ReplacementStrategy strategy;
void *mgmtData; // use this one to store the bookkeeping info your buffer
// manager needs for a buffer pool
} BM_BufferPool;
typedef struct BM_PageHandle {
PageNumber pageNum;
char *data;
} BM_PageHandle;
// convenience macros
#define MAKE_POOL()
((BM_BufferPool *) malloc (sizeof(BM_BufferPool)))
#define MAKE_PAGE_HANDLE()
((BM_PageHandle *) malloc (sizeof(BM_PageHandle)))
// Buffer Manager Interface Pool Handling
RC initBufferPool(BM_BufferPool *const bm, const char *const pageFileName,
const int numPages, ReplacementStrategy strategy,
void *stratData);
RC shutdownBufferPool(BM_BufferPool *const bm);
RC forceFlushPool(BM_BufferPool *const bm);
// Buffer Manager Interface Access Pages
RC markDirty (BM_BufferPool *const bm, BM_PageHandle *const page);
RC unpinPage (BM_BufferPool *const bm, BM_PageHandle *const page);
RC forcePage (BM_BufferPool *const bm, BM_PageHandle *const page);
RC pinPage (BM_BufferPool *const bm, BM_PageHandle *const page,
const PageNumber pageNum);
// Statistics Interface
PageNumber *getFrameContents (BM_BufferPool *const bm);
bool *getDirtyFlags (BM_BufferPool *const bm);
int *getFixCounts (BM_BufferPool *const bm);
int getNumReadIO (BM_BufferPool *const bm);
int getNumWriteIO (BM_BufferPool *const bm);
#endif
Error handling and Printing buffer and page content
The initial assign2 folder contains code implementing several helper functions.
buffer_mgr_stat.h and buffer_mgr_stat.c
buffer_mgr_stat.h provides several functions for outputting buffer or page content to stdout or into a string. The implementation of these functions is provided so you do not have to implement them yourself. printPageContent prints the byte content of a memory page. printPoolContent prints a summary of the current content of a buffer pool. The format looks like that:
{FIFO 3}: [0 0],[3x5],[2 1]
FIFO is the page replacement strategy. The number following the strategy is the size of the buffer pool (number of page frames). Each part enclosed in [] represents one buffer frame. The first number is the page number for the page that is currently stored in this buffer frame. The "x" indicates that the page is dirty, i.e., it has to be written back to disk before it can be replaced with another page. The last number is the fix count. For example, in the buffer shown above the first frame stores the disk page 0 with a fix count of 0. The second page frame stores the disk page 3 with a fix count of 5 and this page is dirty.
dberror.h and dberror.c
The dberror.h header defines error codes and provides a function to print an error message to stdout.
Source Code Structure
You source code directories should be structured as follows. You should reuse your existing storage manager implementation. So before you start to develop, please copy your storage manager implementation from assign1 to assign2.
- Put all source files in a folder assign2 in your git repository
- This folder should contain at least ...
- the provided header and C files
- a make file for building your code Makefile
- a bunch of *.c and *.h files implementing the buffer manager
- README.txt: A text file that shortly describes your solution
E.g., the structure may look like that:
git
assign2
Makefile
buffer_mgr.h
buffer_mgr_stat.c
buffer_mgr_stat.h
dberror.c
dberror.h
dt.h
storage_mgr.h
test_assign2_1.c
test_assign2_2.c
test_helper.h
Test Cases
test_assign2_1.c
This file implements several test cases using the buffer_mgr.h interface using the FIFO strategy. Please let your make file generate a test_assign2_1 binary for this code. You are encouraged to extend it with new test cases or use it as a template to develop your own test files.
test_assign2_2.c
This file implements several test cases using the buffer_mgr.h interface. Please let your make file generate a test_assign2_2 binary for this code. This test also tests the LRU strategy. You are encouraged to extend it with new test cases or use it as a template to develop your own test files.
Assignment Description
Assignment 3 - Record Manager
In this assignment you are creating a record manager. The record manager handles tables with a fixed schema. Clients can insert records, delete records, update records, and scan through the records in a table. A scan is associated with a search condition and only returns records that match the search condition. Each table should be stored in a separate page file and your record manager should access the pages of the file through the buffer manager implemented in the last assignment.
Hints: This assignment is much more complex than the previous assignments and it is easy to get stuck if you are unclear about how to structure your solution and what data structures to use. Sit down with a piece of paper first and design the data structures and architecture for your implementation.
· Record Representation: The data types we consider for this assignment are all fixed length. Thus, for a given schema, the size of a record is fixed too.
· Page Layout: You will have to define how to layout records on pages. Also you need to reserve some space on each page for managing the entries on the page. Refresh your memory on the page layouts discussed in class! For example, how would you represent slots for records on pages and manage free space.
· Table information pages: You probably will have to reserve one or more pages of a page file to store, e.g., the schema of the table.
· Record IDs: The assignment requires you to use record IDs that are a combination of page and slot number.
· Free Space Management: Since your record manager has to support deleting records you need to track available free space on pages. An easy solution is to link pages with free space by reserving space for a pointer to the next free space on each page. One of the table information pages can then have a pointer to the first page with free space. One alternative is to use several pages to store a directory recording how much free space you have for each page.
tables.h
This header defines basic data structures for schemas, tables, records, record ids (RIDs), and values. Furthermore, this header defines functions for serializing these data structures as strings. The serialization functions are provided (rm_serializer.c). There are four datatypes that can be used for records of a table: integer (DT_INT), float (DT_FLOAT), strings of a fixed length (DT_STRING), and boolean (DT_BOOL). All records in a table conform to a common schema defined for this table. A record is simply a record id (rid consisting of a page number and slot number) and the concatenation of the binary representation of its attributes according to the schema (data).
Schema
A schema consists of a number of attributes (numAttr). For each attribute we record the name (attrNames) and data type (dataTypes). For attributes of type DT_STRING we record the size of the strings in typeLength. Furthermore, a schema can have a key defined. The key is represented as an array of integers that are the positions of the attributes of the key (keyAttrs). For example, consider a relation R(a,b,c) where a then keyAttrs would be [0].
Data Types and Binary Representation
Values of a data type are represented using the Value struct. The value struct represents the values of a data type using standard C data types. For example, a string is a char * and an integer using a C int. Note that values are only used for expressions and for returning data to the client of the record manager. Attribute values in records are stored slightly different if the data type is string. Recall that in C a string is an array of characters ended by a 0 byte. In a record, strings are stored without the additional 0 byte in the end. For example, for strings of length 4 should occupy 4 bytes in the data field of the record.
Interface
#ifndef TABLES_H
#define TABLES_H
#include "dt.h"
// Data Types, Records, and Schemas
typedef enum DataType {
DT_INT = 0,
DT_STRING = 1,
DT_FLOAT = 2,
DT_BOOL = 3
} DataType;
typedef struct Value {
DataType dt;
union v {
int intV;
char *stringV;
float floatV;
bool boolV;
} v;
} Value;
typedef struct RID {
int page;
int slot;
} RID;
typedef struct Record
{
RID id;
char *data;
} Record;
// information of a table schema: its attributes, datatypes,
typedef struct Schema
{
int numAttr;
char **attrNames;
DataType *dataTypes;
int *typeLength;
int *keyAttrs;
int keySize;
} Schema;
// TableData: Management Structure for a Record Manager to handle one relation
typedef struct RM_TableData
{
char *name;
Schema *schema;
void *mgmtData;
} RM_TableData;
#define MAKE_STRING_VALUE(result, value)
do {
(result) = (Value *) malloc(sizeof(Value));
(result)->dt = DT_STRING;
(result)->v.stringV = (char *) malloc(strlen(value) + 1);
strcpy((result)->v.stringV, value);
} while(0)
#define MAKE_VALUE(result, datatype, value)
do {
(result) = (Value *) malloc(sizeof(Value));
(result)->dt = datatype;
switch(datatype)
{
case DT_INT:
(result)->v.intV = value;
break;
case DT_FLOAT:
(result)->v.floatV = value;
break;
case DT_BOOL:
(result)->v.boolV = value;
break;
}
} while(0)
// debug and read methods
extern Value *stringToValue (char *value);
extern char *serializeTableInfo(RM_TableData *rel);
extern char *serializeTableContent(RM_TableData *rel);
extern char *serializeSchema(Schema *schema);
extern char *serializeRecord(Record *record, Schema *schema);
extern char *serializeAttr(Record *record, Schema *schema, int attrNum);
extern char *serializeValue(Value *val);
#endif
expr.h
This header defines data structures and functions to deal with expressions for scans. These functions are implemented in expr.c. Expressions can either be constants (stored as a Value struct), references to attribute values (represented as the position of an attribute in the schema), and operator invocations. Operators are either comparison operators (equals and smaller) that are defined for all data types and boolean operators AND, OR, and NOT. Operators have one or more expressions as input. The expression framework allows for arbitrary nesting of operators as long as their input types are correct. For example, you cannot use an integer constant as an input to a boolean AND operator. As explained below, one of the parameters of the scan operation of the record manager is an expression representing the scan condition.
Interface
#ifndef EXPR_H
#define EXPR_H
#include "dberror.h"
#include "tables.h"
// datatype for arguments of expressions used in conditions
typedef enum ExprType {
EXPR_OP,
EXPR_CONST,
EXPR_ATTRREF
} ExprType;
typedef struct Expr {
ExprType type;
union expr {
Value *cons;
int attrRef;
struct Operator *op;
} expr;
} Expr;
// comparison operators
typedef enum OpType {
OP_BOOL_AND,
OP_BOOL_OR,
OP_BOOL_NOT,
OP_COMP_EQUAL,
OP_COMP_SMALLER
} OpType;
typedef struct Operator {
OpType type;
Expr **args;
} Operator;
// expression evaluation methods
extern RC valueEquals (Value *left, Value *right, Value *result);
extern RC valueSmaller (Value *left, Value *right, Value *result);
extern RC boolNot (Value *input, Value *result);
extern RC boolAnd (Value *left, Value *right, Value *result);
extern RC boolOr (Value *left, Value *right, Value *result);
extern RC evalExpr (Record *record, Schema *schema, Expr *expr, Value **result);
extern RC freeExpr (Expr *expr);
extern void freeVal(Value *val);
#define CPVAL(_result,_input)
do {
(_result)->dt = _input->dt;
switch(_input->dt)
{
case DT_INT:
(_result)->v.intV = _input->v.intV;
break;
case DT_STRING:
(_result)->v.stringV = (char *) malloc(strlen(_input->v.stringV));
strcpy((_result)->v.stringV, _input->v.stringV);
break;
case DT_FLOAT:
(_result)->v.floatV = _input->v.floatV;
break;
case DT_BOOL:
(_result)->v.boolV = _input->v.boolV;
break;
}
} while(0)
#define MAKE_BINOP_EXPR(_result,_left,_right,_optype)
do {
Operator *_op = (Operator *) malloc(sizeof(Operator));
_result = (Expr *) malloc(sizeof(Expr));
_result->type = EXPR_OP;
_result->expr.op = _op;
_op->type = _optype;
_op->args = (Expr **) malloc(2 * sizeof(Expr*));
_op->args[0] = _left;
_op->args[1] = _right;
} while (0)
#define MAKE_UNOP_EXPR(_result,_input,_optype)
do {
Operator *_op = (Operator *) malloc(sizeof(Operator));
_result = (Expr *) malloc(sizeof(Expr));
_result->type = EXPR_OP;
_result->expr.op = _op;
_op->type = _optype;
_op->args = (Expr **) malloc(sizeof(Expr*));
_op->args[0] = _input;
} while (0)
#define MAKE_ATTRREF(_result,_attr)
do {
_result = (Expr *) malloc(sizeof(Expr));
_result->type = EXPR_ATTRREF;
_result->expr.attrRef = _attr;
} while(0)
#define MAKE_CONS(_result,_value)
do {
_result = (Expr *) malloc(sizeof(Expr));
_result->type = EXPR_CONST;
_result->expr.cons = _value;
} while(0)
#endif // EXPR
record_mgr.h
We now discuss the interface of the record manager as defined in record_mgr.h. There are five types of functions in the record manager: functions for table and record manager management, functions for handling the records in a table, functions related to scans, functions for dealing with schemas, and function for dealing with attribute values and creating records. We now discuss each of these function types.
Table and Record Manager Functions
Similar to previous assignments, there are functions to initialize and shutdown a record manager. Furthermore, there are functions to create, open, and close a table. Creating a table should create the underlying page file and store information about the schema, free-space, ... and so on in the Table Information pages. All operations on a table such as scanning or inserting records require the table to be opened first. Afterwards, clients can use the RM_TableData struct to interact with the table. Closing a table should cause all outstanding changes to the table to be written to the page file. The getNumTuples function returns the number of tuples in the table.
Record Functions
These functions are used to retrieve a record with a certain RID, to delete a record with a certain RID, to insert a new record, and to update an existing record with new values. When a new record is inserted the record manager should assign an RID to this record and update the record parameter passed to insertRecord.
Scan Functions
A client can initiate a scan to retrieve all tuples from a table that fulfill a certain condition (represented as an Expr). Starting a scan initializes the RM_ScanHandle data structure passed as an argument to startScan. Afterwards, calls to the next method should return the next tuple that fulfills the scan condition. If NULL is passed as a scan condition, then all tuples of the table should be returned. next should return RC_RM_NO_MORE_TUPLES once the scan is completed and RC_OKotherwise (unless an error occurs of course). Below is an example of how a client can use a scan.
RM_TableData *rel = (RM_TableData *) malloc(sizeof(RM_TableData));
RM_ScanHandle *sc = (RM_ScanHandle *) malloc(sizeof(RM_ScanHandle));
Record *r = (Record *) malloc(sizeof(Record));
int rc;
openTable(rel, "R");
startScan(rel, sc, NULL);
while((rc = next(sc, r)) == RC_OK)
{
// do something with r
}
if (rc != RC_RM_NO_MORE_TUPLES)
// handle the error
closeScan(sc);
Closing a scan indicates to the record manager that all associated resources can be cleaned up.
Schema Functions
These helper functions are used to return the size in bytes of records for a given schema and create a new schema.
Attribute Functions
These functions are used to get or set the attribute values of a record and create a new record for a given schema. Creating a new record should allocate enough memory to the data field to hold the binary representations for all attributes of this record as determined by the schema.
Interface
#ifndef RECORD_MGR_H
#define RECORD_MGR_H
#include "dberror.h"
#include "expr.h"
#include "tables.h"
// Bookkeeping for scans
typedef struct RM_ScanHandle
{
RM_TableData *rel;
void *mgmtData;
} RM_ScanHandle;
// table and manager
extern RC initRecordManager (void *mgmtData);
extern RC shutdownRecordManager ();
extern RC createTable (char *name, Schema *schema);
extern RC openTable (RM_TableData *rel, char *name);
extern RC closeTable (RM_TableData *rel);
extern RC deleteTable (char *name);
extern int getNumTuples (RM_TableData *rel);
// handling records in a table
extern RC insertRecord (RM_TableData *rel, Record *record);
extern RC deleteRecord (RM_TableData *rel, RID id);
extern RC updateRecord (RM_TableData *rel, Record *record);
extern RC getRecord (RM_TableData *rel, RID id, Record *record);
// scans
extern RC startScan (RM_TableData *rel, RM_ScanHandle *scan, Expr *cond);
extern RC next (RM_ScanHandle *scan, Record *record);
extern RC closeScan (RM_ScanHandle *scan);
// dealing with schemas
extern int getRecordSize (Schema *schema);
extern Schema *createSchema (int numAttr, char **attrNames, DataType *dataTypes, int *typeLength, int keySize, int *keys);
extern RC freeSchema (Schema *schema);
// dealing with records and attribute values
extern RC createRecord (Record **record, Schema *schema);
extern RC freeRecord (Record *record);
extern RC getAttr (Record *record, Schema *schema, int attrNum, Value **value);
extern RC setAttr (Record *record, Schema *schema, int attrNum, Value *value);
#endif // RECORD_MGR_H
Optional Extensions
You can earn up to 20 bonus points for implementing optional extensions. A good implementation of one or two extensions will give you the maximum of 20 points. So rather then implementing 5 incomplete extensions, I suggest you to focus on one extension first and if there is enough time, then add additional ones.
· TIDs and tombstones: Implement the TID and Tombstone concepts introduced in class. Even though your implementation does not need to move around records, because they are fixed size, TIDs and Tombstones are important for real systems.
· Null values: Add support for SQL style NULL values to the data types and expressions. This requires changes to the expression code, values, and binary record representation (e.g., you can use the NULL bitmaps introduced in class).
· Check primary key constraints: On inserting and updating tupes, check that the primary key constraint for the table holds. That is you need to check that no record with the same key attribute values as the new record already exists in the table.
· Ordered scans: Add an parameter to the scan that determines a sort order of results, i.e., you should pass a list of attributes to sort on. For dare-devils: Implement this using external sorting, so you can sort arbitrarily large data.
· Interactive interface: Implement a simple user interface. You should be able to define new tables, insert, update, and delete tuples, and execute scans. This can either be a shell or menu-based interface.
· Conditional updates using scans: Extend the scan code to support updates. Add a new method updateScan that takes a condition (expression) which is used to determine which tuples to update and a pointer to a function which takes a record as input and returns the updated version of the record. That is the user of the updateScan method should implement a method that updates the record values and then pass this function to updateScan. Alternatively, extend the expression model with new expression types (e.g., adding two integers) and let updateScan take a list of expressions as a parameter. In this case the new values of an updated tuple are produced by applying the expressions to the old values of the tuple. This would closer to real SQL updates.
Source Code Structure
You source code directories should be structured as follows. You should reuse your existing storage manager and buffer manager implementations. So before you start to develop, please copy your storage manager and buffer manager implementations.
· Put all source files in a folder assign3 in your git repository
· This folder should contain at least ...
o the provided header and C files
o a make file for building your code Makefile
o a bunch of *.c and *.h files implementing the record manager
o README.txt: A text file that shortly describes your solution
E.g., the structure may look like that:
git
assign3
Makefile
buffer_mgr.h
buffer_mgr_stat.c
buffer_mgr_stat.h
dberror.c
dberror.h
expr.c
expr.h
record_mgr.h
rm_serializer.c
storage_mgr.h
tables.h
test_assign3_1.c
test_expr.c
test_helper.h
Test Cases
test_helper.h
Defines several helper methods for implementing test cases such as ASSERT_TRUE.
test_expr.c
This file implements several test cases using the expr.h interface. Please let your make file generate a test_expr binary for this code. You are encouraged to extend it with new test cases or use it as a template to develop your own test files.
test_assign3_1.c
This file implements several test cases using the record_mgr.h interface. Please let your make file generate a test_assign3 binary for this code. You are encouraged to extend it with new test cases or use it as a template to develop your own test files.
....
Frequently Asked Questions
Yes. No hidden fees. You pay for the solution only, and all the explanations about how to run it are included in the price. It takes up to 24 hours to get a quote from an expert. In some cases, we can help you faster if an expert is available, but you should always order in advance to avoid the risks. You can place a new order here.
The cost depends on many factors: how far away the deadline is, how hard/big the task is, if it is code only or a report, etc. We try to give rough estimates here, but it is just for orientation (in USD):
| Regular homework | $20 - $150 |
| Advanced homework | $100 - $300 |
| Group project or a report | $200 - $500 |
| Mid-term or final project | $200 - $800 |
| Live exam help | $100 - $300 |
| Full thesis | $1000 - $3000 |
Credit card or PayPal. You don't need to create/have a Payal account in order to pay by a credit card. Paypal offers you "buyer's protection" in case of any issues.
We have no way to request money after we send you the solution. PayPal works as a middleman, which protects you in case of any disputes, so you should feel safe paying using PayPal.
No, unless it is a data analysis essay or report. This is because essays are very personal and it is easy to see when they are written by another person. This is not the case with math and programming.
It is because we don't want to lie - in such services no discount can be set in advance because we set the price knowing that there is a discount. For example, if we wanted to ask for $100, we could tell that the price is $200 and because you are special, we can do a 50% discount. It is the way all scam websites operate. We set honest prices instead, so there is no need for fake discounts.
No, it is simply not how we operate. How often do you meet a great programmer who is also a great speaker? Rarely. It is why we encourage our experts to write down explanations instead of having a live call. It is often enough to get you started - analyzing and running the solutions is a big part of learning.
Another expert will review the task, and if your claim is reasonable - we refund the payment and often block the freelancer from our platform. Because we are so harsh with our experts - the ones working with us are very trustworthy to deliver high-quality assignment solutions on time.
