CS376: Operating Systems - Mini Database (100 Points)

Assignment Goals

The goals of this assignment are:
  1. Synthesize a functional mini-database program in C, demonstrating creativity in choosing and implementing a file format (e.g., flat file, XML, JSON, CSV, binary, or custom format).
  2. Analyze standard library file operations (or CSAPP file I/O libraries) and apply these concepts effectively to handle data storage and retrieval.
  3. Develop a mechanism that allows the selection of a database through a command-line parameter, incorporating the functionality to create a new database if it does not exist.
  4. Create and modify files using the C standard I/O interface

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

Core Concepts — why this matters. This assignment reinforces the essential OS topics of persistent storage, file-based data structures, and serialization/deserialization across the file-system interface. A database is ultimately just structured bytes on disk plus code that seeks, reads, and writes them — the same file abstraction explored in the File I/O assignment and, on the kernel side, in the Kernel Data Structures reference.

In this assignment, you will write a mini-database program in the C language that uses basic file I/O. You may choose any file format you like, including flat file, XML, JSON, comma separated values, binary files, or a format of your own choosing, but you must support the following:

  • Some SQL-like operations, namely:
    • SELECT * FROM TableName WHERE field1=value1
    • DELETE FROM TableName WHERE field1=value1
    • INSERT INTO TableName (value1,value2,value3)
  • Creation and deletion of multiple tables per database:
    • CREATE TABLE TableName FIELDS [Field1,Field2,...]
    • DROP TABLE TableName

You must use only the standard library file operations (no CSV or json libraries, etc.). You may use the CSAPP file I/O libraries. To read a string from the console, you can use the line fgets(buf, 1024, stdin); from stdio.h, assuming that buf is malloc‘ed to 1024 bytes.

Getting Started

Begin by defining a database structure in memory. You will write functions to read text from a file into this data structure (using malloc), and to loop over and write the contents of this data structure to a file. It’s ok to delete the file using remove(filename) and re-create the file each time.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Field {
    char* name;
    char* value;
    struct Field* next;
} Field;

typedef struct Record {
    Field* fields;
    struct Record* next;
} Record;

typedef struct Table {
    char* name;
    Record* records;
    struct Table* next;
} Table;

You can use this code to manipulate the data structure using the CREATE TABLE, SELECT, DELETE, and INSERT commands. To DROP a table, simply free the data in the structure.

void createTable(Table** head, char* name, char** fields, int numFields) {
    Table* table = (Table*)malloc(sizeof(Table));
    table->name = strdup(name);
    table->records = NULL;
    table->next = *head;
    *head = table;
}

void insertIntoTable(Table* head, char* tableName, char** values, int numValues) {
    // Find the table
    Table* table = head;
    while (table != NULL && strcmp(table->name, tableName) != 0) {
        table = table->next;
    }
    if (table == NULL) return; // Table not found

    // Create a new record
    Record* newRecord = (Record*)malloc(sizeof(Record));
    newRecord->fields = NULL;
    newRecord->next = table->records;
    table->records = newRecord;

    // Add fields to the record
    for (int i = 0; i < numValues; i++) {
        Field* newField = (Field*)malloc(sizeof(Field));
        newField->name = NULL; // In this simplified version, field names are not stored
        newField->value = strdup(values[i]);
        newField->next = newRecord->fields;
        newRecord->fields = newField;
    }
}

You can call these functions as follows:

Table* head = NULL;

// Example usage
char* fields[] = {"Field1", "Field2", "Field3"};
createTable(&head, "TableName", fields, 3);

char* values[] = {"Value1", "Value2", "Value3"};
insertIntoTable(head, "TableName", values, 3);

What to Do

  1. Read the input command from the user using the fgets function.
  2. Tokenize this char* to determine the command (which will be the first token in the list).
  3. Compare it to the different commands (i.e., CREATE, SELECT), and call the appropriate function.
  4. These functions take parameters that you will be able to produce from the rest of the tokens. For example, for a CREATE, you will have the list of fields at the end of the statement. You can malloc an array of strings and populate that array with each string in the list.
  5. Create a file named the database name (which you got from argv[1]; being careful to check that argc is at least 2 at the beginning of main, and printing and error message and returning a non-zero value if it is not). It’s ok to replace this file each time you run the program. Write the contents of the file from the linked list.

Makefile

Be sure to include a Makefile with your submission that builds and tests your program. If you prefer, you can include a shell script of test cases that you execute via the Makefile.

Makefile Requirements

Your submission must include a Makefile supporting the following standard targets:

Target What it must do
make Compile your program with no errors.
make run Build if needed and run your program against a representative sample query.
make test Build if needed and run your test cases (e.g., a scripted set of SQL-like commands), printing observable pass/fail output.
make clean Remove all executables, object files, generated data files, and core dumps.

Helpful Utility Functions

Tokenizing a String

You can use the strtok function to tokenize a string. Here is a function that dynamically allocates (and re-allocates) an array of tokens given an input string, a string of possible delimiters, and an integer representing the number of tokens found (passed as a pointer so that updates are seen in the main function).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** tokenize(char* input, const char* delimiter, int* tokenCount) {
    char** tokens = NULL;
    int capacity = 10; // Initial capacity for the array of tokens
    *tokenCount = 0; // Initialize the token count

    // Allocate initial memory for tokens
    tokens = (char**)malloc(capacity * sizeof(char*));
    if (tokens == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }

    // Duplicate the input string to avoid modifying the original string
    char* inputDup = strdup(input);
    if (inputDup == NULL) {
        free(tokens);
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }

    // Tokenize the input string
    char* token = strtok(inputDup, delimiter);
    while (token != NULL) {
        if (*tokenCount >= capacity) {
            // Increase capacity
            capacity *= 2;
            char** temp = (char**)realloc(tokens, capacity * sizeof(char*));
            if (temp == NULL) {
                // Cleanup and error handling
                for (int i = 0; i < *tokenCount; ++i) {
                    free(tokens[i]);
                }
                free(tokens);
                free(inputDup);
                fprintf(stderr, "Memory allocation failed\n");
                return NULL;
            }
            tokens = temp;
        }

        // Duplicate token and add to the array
        tokens[*tokenCount] = strdup(token);
        if (tokens[*tokenCount] == NULL) {
            // Cleanup and error handling
            for (int i = 0; i < *tokenCount; ++i) {
                free(tokens[i]);
            }
            free(tokens);
            free(inputDup);
            fprintf(stderr, "Memory allocation failed\n");
            return NULL;
        }

        (*tokenCount)++;
        token = strtok(NULL, delimiter);
    }

    free(inputDup); // Cleanup the duplicated string
    return tokens;
}

int main() {
    char input[] = "This is a test string, with several delimiters.";
    const char* delimiter = " ,."; // Tokenize based on space, comma, and period
    int tokenCount = 0;

    char** tokens = tokenize(input, delimiter, &tokenCount);
    if (tokens != NULL) {
        for (int i = 0; i < tokenCount; i++) {
            printf("%d: %s\n", i + 1, tokens[i]);
            free(tokens[i]); // Free each token
        }
        free(tokens); // Free the array of tokens
    }

    return 0;
}

Comparing Two Strings

You can compare two strings using the strcmp function, which returns 0 when the strings are equal. Here is an example:

#include <stdio.h>
#include <string.h>

int main() {
    // Define pairs of strings to compare
    char* pairs[][2] = {
        {"apple", "apple"}, // Equal strings
        {"apple", "banana"}, // Lexicographically less
        {"banana", "apple"}, // Lexicographically greater
        {"apple", "Apple"}, // Case sensitivity, 'a' > 'A' in ASCII
        {"", ""}, // Both strings are empty
        {"apple", ""}, // Non-empty string compared with an empty string
        {"apple", "apple"} // The strings are equal
    };

    // Calculate the number of pairs
    int numPairs = sizeof(pairs) / sizeof(pairs[0]);

    for (int i = 0; i < numPairs; i++) {
        // Compare the strings
        int result = strcmp(pairs[i][0], pairs[i][1]);

        // Print the result of the comparison
        printf("Comparing \"%s\" and \"%s\": ", pairs[i][0], pairs[i][1]);
        if (result < 0) {
            printf("The first string is less than the second string.\n");
        } else if (result > 0) {
            printf("The first string is greater than the second string.\n");
        } else {
            printf("The strings are equal; result == 0.\n");
        }
    }

    return 0;
}

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague. In your README, please include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
Implementation of SQL-like Operations (30%) No implementation of SQL-like operations. Basic implementation of one or two SQL-like operations with significant issues. Partial implementation of most SQL-like operations with minor issues. Full implementation of all specified SQL-like operations functioning correctly.
Design and Construction of File I/O System (20%) Ineffective or non-existent file I/O system. Basic file I/O functionality with significant limitations or errors. Functional file I/O system with some limitations or minor errors. Robust and efficient file I/O system with no significant issues.
Database Table Management (Create and Drop Table) (20%) No functionality for creating or dropping tables. Basic functionality for table creation or deletion with major issues. Good functionality for managing tables, minor issues in creation or deletion processes. Fully functional and efficient table management system, including creation and deletion.
Makefile and Compilation (15%) No Makefile provided or compilation issues. Basic Makefile provided but with errors or missing targets. Functional Makefile, minor issues with targets or dependencies. Well-structured Makefile, enabling seamless compilation without errors.
Documentation (README) (15%) No README or severely lacking in information. Basic README provided but lacking essential information or clarity. Good README, covers most essential aspects with minor omissions or clarity issues. Comprehensive, clear, and detailed README, providing complete instructions on program usage.

Please refer to the Style Guide for code quality examples and guidelines.