minrel, part 0
Table of Contents
1 Introduction
We're going to write a little relational database here. It's called minrel, both because it's a rather minimalistic relational database, and because it's meant to serve as the relational component for a slightly larger project called minneron.
We're going to start with a very naive implementation, and it's going to be pretty slow compared to things like PostGresQL, MySQL and SQLite – although perhaps not nearly as slow as you might expect.
Once we have it running, we're going to start introducing optimizations, swapping out algorithms, perhaps even dropping down to assembly language, until we have a very fast system, on par with those other databases.
2 Relations
In database terminology, a relation is a table-like data structure.
Relations are un-ordered collections of tuples, which are ordered collections of values. All the tuples in a relation have the same structure, meaning they all have the same slots in the same order.
Generally, when drawing relations, the tuples are depicted as rows, and the columns are given meaningful labels, called keys.
Here's a simple example of a relation that lists a few popular programming-related websites, along with their titles.
| id | URL | title |
|---|---|---|
| 7 | http://reddit.com/r/learnprogramming | learn programming |
| 4 | http://sourceforge.net/ | SourceForge |
| 8 | http://stackoverflow.com/ | Stack Overflow |
| 2 | https://github.com/ | GitHub |
| 13 | http://c2.com/cgi/wiki?WikiWikiWeb | Wiki Wiki Web |
| 6 | http://reddit.com/r/programming | programming |
Notice that each tuple conforms to the same structure, but the tuples themselves aren't in any particular order.
Also note the id column. It's good practice when designing a database to make sure that there's a set of keys that, together, can uniquely identify a particular tuple within the relation. Preferably, only a single key is required, and we call this the primary key.
In this particular case, the URL could serve this purpose, but as we will see, it's generally more convenient to use a number. Generally, we will restrict ourselves to positive integers.
A relational database can contain any number of relations, and produces new relations dynamically as it responds to queries. For example, if you were to request the id and title values from the above table but only where the ID is less than five, then the result would also be a relation:
| id | title |
|---|---|
| 2 | GitHub |
| 4 | SourceForge |
The relational model is rigorously defined in the mathematical sense, and provides a number of convenient operations for combining, filtering, and transforming relations in various ways. Most database provide some non-relational utilities as well, such as sorting and stored procedures.
We will explore these features in depth as we go along, but first we're going to look at how we can implement our one-table database in software.
3 Implementation
3.1 A simple database for bookmarks.
Let's write a program to implement our one-table relational database for bookmarks, and perform the above query. (Scroll down to the Results section at the end of this document if you want to see what it does.)
The example code in these articles is all written in object pascal, using the cross platform, open source compiler from http://freepascal.org/ (version 2.6.2). Pascal is a fun, easy-to-understand language that's been around a long time, and object pascal is a modern dialact with all kinds of nice features like interfaces and generics.
Don't worry if you don't know pascal. I will assume that most people reading this are not already familiar with it (or at least, not with the modern version), and will introduce each new construct as we go along.
3.2 program urldb0
We will start with a simple command line program that lets us create, update, and delete records in our database.
Basically, what our program does is this:
- define
TUrlRec, arecordtype to hold our data. - define a
filevariable to store records of this type. - store our bookmarks in the file (using hard coded values for now)
- show the unfiltered table
- execute our example query and display the results
Here's the rough outline of of the code:
program urldb0; uses strutils; type TUrlRec = record id : cardinal; url : string[ 36 ]; title : string[ 24 ]; end; TUrlFile = file of TUrlRec; <<routines>> var f : TUrlFile; begin MakeDatabase( f ); ShowHeader('All records'); ShowAllRecords( f ); ShowHeader('Query results'); ShowQueryResults( f ); end.
3.3 Walkthrough
Let's walk through that code line by line:
program urldb0;
This line simply gives a name to the program. It's not strictly required, but it's good practice.
uses strutils;
This line imports the strutils unit, so that we have access to the types and routines it provides. Units correspond roughly to modules in python, or to static classes in java. They are just collections of reusable definitions, and this one in particular deals with strings. We're going to use it to output our results.
type
This line introduces a type section, in which we can declare new types.
TUrlRec = record
id : cardinal;
url : string[ 36 ];
title : string[ 24 ];
end;
TUrlRec is the name we will use for the type that holds our url-related tuple. The "T" doesn't mean "tuple" though. It stands for "type" and it's just part of a naming convention that the object pascal community uses.
The = record syntax indicates that TUrlRec is a record type. Records are flat, fixed-size chunks of ram with a particular structure.
The : character indicates a relationship between a set of field names (on the left) with a type (on the right). It means has the type. So for example, the id field has the type cardinal (a 32-bit unsigned integer).
The URLs and titles are both of type string. Pascal has a rich variety of string types. The bracket syntax indicates that we are dealing with the type ShortString. The number inside the brackets indicates the maximum length of the string, in bytes. Since records are flat structures, all of these bytes will be allocated. Unused bytes at the end will be padded with null characters, and one extra byte will be reserved at the start of the string to indicate its length.
TUrlFile = file of TUrlRec;
One of the benefits of records is that, because they are fixed size, they are easily loaded and saved to disk. This line defines a new file type that can store values of type TUrlFile.
Typed files are a feature of pascal that you don't often see in other languages. These are binary files on disk that contain fixed-size records, making them a good match for tabular data. (Probably one reason you don't see typed files in modern languages is the emergence of relational databases.)
Because we will eventually want to let our database users define new relations (and thus new record types) dynamically, we will eventually leave pascal's records and typed files behind, but for now, they're an excellent way to quickly store a table of data.
<<routines>>
This line isn't actually pascal source, but rather a placeholder for code we'll write later. The double angle-bracket syntax is used by the literate programming tool I'm using to edit this code.
var f : TUrlFile;
The word var tells the pascal compiler that we're going to introduce one or more variables. In this case, the variable is called f and its type is TUrlFile.
begin
MakeDatabase( f );
ShowHeader('All Records'); ShowAllRecords( f );
ShowHeader('Query results'); ShowQueryResults( f );
end.
This is the main code of the program. You can always tell you're looking at the end of a pascal program because the end keyword is followed by a period. (Any text that appears in the file after the period is ignored.)
Here, MakeDatabase, ShowHeader, ShowAllRecords, and ShowQueryResults are all procedures that we're about to define.
3.4 Implementation
3.4.1 procedure MakeDatabase
procedure MakeDatabase( var f : TUrlFile ); var rec : TUrlRec; procedure store( id: cardinal; url: string; title : string ); begin rec.id := id; rec.url := url; rec.title := title; Write( f, rec ); end; begin Assign( f, 'urldb0.db' ); ReWrite( f ); store( 7 , 'http://reddit.com/r/learnprogramming' , 'learn programming' ); store( 4 , 'http://sourceforge.net/' , 'SourceForge' ); store( 8 , 'http://stackoverflow.com/' , 'Stack Overflow' ); store( 2 , 'https://github.com/' , 'GitHub' ); store( 13 , 'http://c2.com/cgi/wiki?WikiWikiWeb' , 'Wiki Wiki Web' ); store( 6 , 'http://reddit.com/r/programming' , 'programming' ); end;
3.4.2 procedures ShowHeader
We saw that Write can be used to write records to a typed file.
There is also a special type of file called Text, and for these, pascal provides some syntactic sugar for Write, and also for a related procedure called WriteLn, which adds a newline at the end.
In particular, these special routines can take a variable number of parameters, know how to format numbers as strings and allow using a special syntax for aligning text (provided you're using a monospaced font).
procedure ShowHeader( header : string ); var i : cardinal; begin WriteLn; Write( '##| ', header, ' |' ); for i := length(header) + length('##| '+ ' |') to 64 do write( '#' ); WriteLn; WriteLn; end;
3.4.3 procedure ShowAllRecords
To reopen a file for reading, we use Reset, then loop through and Read records from the file until we reach the end of the file (which we test by calling Eof before each read).
As we print each record with WriteLn you can see the special string justification syntax using the colon character. For example, rec.id : 3 tells WriteLn to use at least 3 characters to display the numbers in that column.
procedure ShowAllRecords( var f : TUrlFile ); var rec : TUrlRec; i : byte; begin Reset( f ); Writeln( 'id' : 3, ' ', PadRight( 'url', 36 ), ' ', PadRight( 'title', 24 )); for i := 1 to 64 do write( '-' ); writeln; while not Eof( f ) do begin Read( f, rec ); WriteLn( rec.id : 3, ' ', PadRight( rec.url, 36 ), ' ', PadRight( rec.title, 24 )); end end;
3.4.4 procedure ShowQueryResults
The only differences between ShowAllRecords and ShowQueryResults are:
- we use an
if ... thenstatement to check the record's.idfield, and only print the record if the id is less than 5 - we don't print the url
procedure ShowQueryResults( var f : TUrlFile ); var rec : TUrlRec; i : byte; begin Reset( f ); Writeln( 'id' : 3, ' ', PadRight( 'title', 24 )); for i := 1 to 64 do write( '-' ); writeln; while not eof( f ) do begin Read( f, rec ); if rec.id < 5 then WriteLn( rec.id : 3, ' ', PadRight( rec.title, 24 )); end; Writeln; end;
4 Results
To compile and run the program, use the following commands:
fpc urldb0.pas ./urldb0
You should see the following output:
##| All records |################################################ id url title ---------------------------------------------------------------- 7 http://reddit.com/r/learnprogramming learn programming 4 http://sourceforge.net/ SourceForge 8 http://stackoverflow.com/ Stack Overflow 2 https://github.com/ GitHub 13 http://c2.com/cgi/wiki?WikiWikiWeb Wiki Wiki Web 6 http://reddit.com/r/programming programming ##| Query results |############################################## id title ---------------------------------------------------------------- 4 SourceForge 2 GitHub
5 Summary
In this article, we explored the concept of a relation and implemented a very simple database with a single hard-coded table. We displayed the relation as-is, and then showed how to filter the keys and tuples to produce a new relation (the query results).
In the next lesson, we will add a second relation and explore the relational algebra in a little more detail.