This is one of my Computer Related Projects. It is work in progress.

Personal Relational Database

Table of Contents

• Introduction
• Requirements
• Design
• File Formats
• Protocol
• Command Line Interface
• To Do List

Introduction

A number of my projects need to store structured data. A relational database is an obvious location to store such structured data. Unfortunately, most relational databases come with onerous prices, licenses, and installation issues. I just want something really simple.

Requirements

A real database needs to meet the ACID criteria -- Atomic, Consistent, Isolated, and Durable:

Atomic

All table updates for a transaction take place or none do.

Consistent

With each transaction, the database remains in a valid state. (Basically, this means that there are no foreign keys that point to deleted records.)

Isolated

The results of other concurrent transactions are not visble, until the current transaction completes.

Durable

Once a transaction commits, all the table updates are permanent even in the face of system crashes.

In addition the ACID requirements, PDB has the following additional requirements:

• It must be kept simple.
• It must work on top of a standard hierarchical file system.

PDB has the following explicit non-requirements:

• It does not need to be massively parallel; it can be completely single threaded.
• It need not be particularly fast.
• It does not need to support SQL.
• It does not need to support 24 by 7 operation; shutting down the database for maintenance is perfectly acceptable.

Design

The only reason why PDB has a chance of being simple is because it is intended for relatively small databases that can easily fit into main memory. When it is done it will simply write out the entire contents of tables that have changed. This is not particularly fast or efficient, but it is quite simple.

PDB is not designed for 24 by 7 operation. It is expected to shut down for maintenance. All table creation, deletion, and modification (adding, removing, and changing columns) occurs when the database is shut down. All table updates occur as the result of transactions that occur when the database is up.

Each time the database is brought up, any previous incomplete transactions are aborted and all committed transactions are finalized. All table update files (discussed below) are merged into there corresponding table file. There is a global tranasaction counter that is initialized to zero. The database is now ready for connections and the start of transactions.

The database goes through a sequence of transitions, where each transition corresponds to a committed transaction. Each time a transaction commits, the global committed transaction counter is incremented and the transaction gets assigned a global transaction number. There can be no more than 2³² transactions before the database must be shut down.

PDB uses a standard two phase commit protocol for its transactions. First, all of the information about the transaction is written into a temporary transaction file. After the transaction file is committed to disk, the PDB serializer process decides whether it is able to commit or abort the transaction. An abort occurs because some of the data that the transaction has read, has been changed by another transaction that got its updates in beforehand. In addition, sometimes row deletions will fail because they will result in dangling foreign keys. When the serializer decides to commit the transaction, it assigns the transaction a global transaction number and commits the transaction by renaming the file.

Once a transaction has been committed, the transaction goes through a process called finalization. Finalization involves generating and update file for each table that is modified (i.e. row insertions, deletions, or modifications) by the transaction. Once all of the table update files have been written, the transaction file can be safely deleted. Since PDB is not designed to be fast, the next transaction is not considered until after all of the update files for the currently committed transaction have been written to disk. There is room for performance improvement here.

All table accesses are versioned. A table access uses the global transaction number to determine the table view. When accessing a table using global transaction number N, all subsequent changes from N+1 forward are not visible. The in memory table manager is responsible for keeping track of all table insertions, deletions, and modifications. In addition, it is responsible for keeping the various sort indices up to date.

When a transaction is started, it uses the highest finalized transaction number to provide transaction isolation. The database process keeps track of all open transactions. The minimum open transaction number, M, is kept track of by the database process. All table update files that are less than M can be folded into the flat database file and then safely deleted.

The entire database consists of a bunch of tables reside in a single directory. Each table is partitioned into several files:

table.data.gid

This file consists of a one line header followed by the table records.

table.delta.gid

This contains a list of insertions, modifications, and deletions for the global transaction numbered gid for table. This file remains as long as gid is greater than M.

table..sort.sortname

{More thought needed here}
This conatains a list of 's that establishes a sorting order for .data table. There can be more than one of these for each table.

The format of a table.data consists of a lists or row records where each record is terminated by a new-line character. Each record consists of a sequence of fields, is separated by a single space. The first field is always a unique identifier represented as a decimal number. Non-printable data is stored in the records using `%xx', where xx is the hexadecimal value of the character. Thus, the space character is represented as `%20'. A percent character `%' is represented as `%25'.

The supported datatypes are:

Integer32

32-bit integer represented a decimal string

Integer64

64-bit integer represented a decimal string

Float32

32-bit floating point number represented as a string in `E' format.

Float64

64-bit floating point number representad as a string in `E' format. String

A string of 0 or more characters. There is no limit on length.

Date

A data is represented as year-month-date, year, month, and date are decimal numbers.

Time

A time is represented in 24 hour format as HH:MM:SS, where HH, MM, and SS are 2 digit decimal numbers.

Currency

A currency is represented as...

Foreign Key

A foreign key is represented as a decimal number

File Formats

...

Table File

A table data file consists of a bunch of lines, where each line is terminated by a new-line character.

The first line is the header line and has the following format:

    H PDB_Table Major Minor
								

Major

is the major version number (currently 1), and

Minor

is the minor version number (currently 0).

	
    H PDB_Table 1 0
								

The supported datatypes are:

Integer:size

A signed integer that can be fit into a Size bit container. The number is stored as a decimal string with a preceeding minus (`-') for negative numbers. The currently acceptable values for size are are 8, 16, 32, and 64.

Float:size

32-bit floating point number represented as a string in `E' format.

String

A string of 0 or more characters. There is no limit on length.

Date

A data is represented as year-month-date, year, month, and date are decimal numbers.

Time

A time is represented in 24 hour format as HH:MM:SS, where HH, MM, and SS are 2 digit decimal numbers.

Currency

A currency is represented as...

Foreign_Key:Table_Name

A foreign key is a pointer to another row in another table. Table_Name is the name of the other table.

Finally, the rows of data are present with with each row represented on a single line where each column value is separated by a single space and the entire line is terminated by a new-line character. The first column is always the row unique identifier. The rows are always stored in ascending row unique identifier order. Any spaces or non-printing characters are embedded into a column value using %HH, where HH is a two-digit hexadecimal value. The percent sign (`%') is represented as %25. A space is represented as %20. %N0 is used to represent NULL.

Index File

The first line is a header line of the form:

    H PCB_Index Major Minor
								

Major

is the major version number, and

Minor

is the minor version number.

The remaining lines in the file are of the form:

    RUID Offset Count
								

RUID

is the row unique identifier,

Offset

is the byte offset to the first byte of that row, and

Count

is the number of rows until the next entry in the file.

Schema Tables

The database schema is represented recursively as three tables -- APPLICATIONS, TABLES, and COLUMNS.

The schema for the TABLES table is:

Row_Id:RUID

Row Unique identifier.

Name:String

The table name.

Row_Id:RUID

Unique Identifer

Table:Foreign_Key:Tables

The foreign key for the table that the column is part of.

Column:Integer:16

The column number

Name:string

The table name.

Type:String

xxx

Null_OK:Logical

xxx

Protocol

Upon opening a connection to the server, the following commands can be sent. Many commands will return a number; any numbers less than 100 are errors, 100 means success, and numbers greater than 100 are handles:

A[ccess] account password

This command obtains database access priviledges. The returned number is the access handle that is used by other commands.

O[pen] access mode

This command opens a transaction with access priviledges to the database. Mode is one of the following:

R[ead]O[nly]

This provides isolated reading of the database. Nothing is journaled since read only access does not change anything.

R[ead]W[rite]

This is a fully isolated transaction. Reads are tracked and writes are stored for eventual transaction committal.

C[urrent]

There is no isolation, the data that is read is always the most current.

The returned number is the transaction handle that is used in other commands.

C[lose] transaction

This command will attempt to commit the transaction (if appropriate). The returned number is either 100 for success or an error number.

L[ookup] transaction table_name ...

Each table name is located and and a table handle is returned. The table handle is bound to transaction. 0 is returned if the lookup fails.

S[how] transaction table [from [to]]

Show the contents of the rows from from to to in table using transaction. A single line is returned, with rows separate by semi-colons.

R[ead transaction table [from [to]]

Show the contents of the rows from from to to in table using transaction. A single line is returned, with rows separate by semi-colons.

D[elete] transaction table row

The row in table with a unique identifier of row is deleted using transaction. 0 is returned if the delete succeeds and an error number otherwise.

I[nsert] transaction table data ...

This command inserts data ... into table using transaction. The row unique identifier row is returned returned for success and an error number for failure.

U[pdate] tranasaction table row data ...

This command will update the contents of row in table with data ... using transaction. 0 is returned for success and an error number otherwise.

Command Line Interface

The following commands are supported from the command line interface:

pdb create

Create an empty database containing only the Schema_Tables and Schema_Columns tables.

pdb table create table_name

Create a new table named table_name with only a single column named Row_Id for starters.

pdb table column_append table_name column_name type null_ok [default_value]

Append a new column named column_name to the table named table_name. The column will have a type of type, and a null-ok value of null_ok. If there are any preexisting rows in the table, default_value is used to fill in the values.

pdb insert table_name column₀ ...

Insert a new row of data into the table named table_name with column values of column₀...

pdb delete table_name row_id

Delete the column with row identifier of row_id in the table named table_name.

pdb update table_name row_id column₀ ...

Replace the contents of the row with a row identifier of row_id in the table named table_name.

To Do List

The following items are on the "to-do" list:

1. Make the database more durable by writing out the new contents to a different directory.
2. Add type checking.
3. Provide better support for NULL and empty strings.
4. Get a network interface up and running.
5. Get transactions working.