This is one of my Computer Related Projects. It is work in progress.
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.
A real database needs to meet the ACID criteria -- Atomic, Consistent, Isolated, and Durable:
In addition the ACID requirements, PDB has the following additional requirements:
PDB has the following explicit non-requirements:
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 232 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:
.datatable. There can be more than one of these for each table.
The format of a
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 `
where xx is the hexadecimal value of
the character. Thus, the space character is
represented as `
%20'. A percent
%' is represented as
The supported datatypes are:
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 Minorwhere
H PDB_Table 1 0
The supported datatypes are:
sizeare are 8, 16, 32, and 64.
Table_Nameis 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
%25. A space is represented
%N0 is used
to represent NULL.
The first line is a header line of the form:
H PCB_Index Major Minorwhere
The remaining lines in the file are of the form:
RUID Offset Countwhere
The database schema is represented recursively as three tables -- APPLICATIONS, TABLES, and COLUMNS.
The schema for the TABLES table is:
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:
The following commands are supported from the command line interface:
The following items are on the "to-do" list: