mr $01 : reification
Table of Contents
1 Introduction
Last time around, we created a tiny database file with a single table, or relation, and manually populated it, displayed it, and then filtered it by row and column – all in plain old pascal.
There's nothing inherently wrong with this approach, but it's tedious. One of the main benefits of the relational database model is that it's universal: you use can use one data structure (the relation) for all of your data, so everything works the same way, and you don't have to keep rewriting the same code over and over by hand.
In order to do this, we're going to have to lift the description of a relation's structure up out of the pascal compiler and into a concrete data structure that we can interact with and inspect at runtime. For example, instead of manually printing and justifying each column name, we will use an array of records that map the keys to string labels, display widths, and specific routines for rendering the data.
This process of replacing code with data is called reification, and we will come back to it again and again as we transfer more and more of our hand-coded logic into the relational database itself.
We'll start by examining what the pascal compiler already does when we use the record keyword to declare a structured data type.
2 The Binary Record Format
2.1 Recap
In lesson 0, we defined the TUrlRec type:
type TUrlRec = record id : cardinal; url : string[ 36 ]; title : string[ 24 ]; end;
We then created a file of TUrlRec, and populated it with some records:
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;
Since pascal handled the file for us, we didn't spend much time looking at what it was actually doing. Let address that now, by creating a hex dump of the generated urldb0.db file.
2.2 Hex Dump
$ hexdump -C urldb0.db 00000000 07 00 00 00 24 68 74 74 70 3a 2f 2f 72 65 64 64 |....$http://redd| 00000010 69 74 2e 63 6f 6d 2f 72 2f 6c 65 61 72 6e 70 72 |it.com/r/learnpr| 00000020 6f 67 72 61 6d 6d 69 6e 67 11 6c 65 61 72 6e 20 |ogramming.learn | 00000030 70 72 6f 67 72 61 6d 6d 69 6e 67 00 00 00 00 00 |programming.....| 00000040 00 00 00 00 04 00 00 00 17 68 74 74 70 3a 2f 2f |.........http://| 00000050 73 6f 75 72 63 65 66 6f 72 67 65 2e 6e 65 74 2f |sourceforge.net/| 00000060 72 6e 70 72 6f 67 72 61 6d 6d 69 6e 67 0b 53 6f |rnprogramming.So| 00000070 75 72 63 65 46 6f 72 67 65 61 6d 6d 69 6e 67 00 |urceForgeamming.| 00000080 00 00 00 00 00 00 00 00 08 00 00 00 19 68 74 74 |.............htt| 00000090 70 3a 2f 2f 73 74 61 63 6b 6f 76 65 72 66 6c 6f |p://stackoverflo| 000000a0 77 2e 63 6f 6d 2f 70 72 6f 67 72 61 6d 6d 69 6e |w.com/programmin| 000000b0 67 0e 53 74 61 63 6b 20 4f 76 65 72 66 6c 6f 77 |g.Stack Overflow| 000000c0 69 6e 67 00 00 00 00 00 00 00 00 00 02 00 00 00 |ing.............| 000000d0 13 68 74 74 70 73 3a 2f 2f 67 69 74 68 75 62 2e |.https://github.| 000000e0 63 6f 6d 2f 77 2e 63 6f 6d 2f 70 72 6f 67 72 61 |com/w.com/progra| 000000f0 6d 6d 69 6e 67 06 47 69 74 48 75 62 4f 76 65 72 |mming.GitHubOver| 00000100 66 6c 6f 77 69 6e 67 00 00 00 00 00 00 00 00 00 |flowing.........| 00000110 0d 00 00 00 22 68 74 74 70 3a 2f 2f 63 32 2e 63 |...."http://c2.c| 00000120 6f 6d 2f 63 67 69 2f 77 69 6b 69 3f 57 69 6b 69 |om/cgi/wiki?Wiki| 00000130 57 69 6b 69 57 65 62 6e 67 0d 57 69 6b 69 20 57 |WikiWebng.Wiki W| 00000140 69 6b 69 20 57 65 62 77 69 6e 67 00 00 00 00 00 |iki Webwing.....| 00000150 00 00 00 00 06 00 00 00 1f 68 74 74 70 3a 2f 2f |.........http://| 00000160 72 65 64 64 69 74 2e 63 6f 6d 2f 72 2f 70 72 6f |reddit.com/r/pro| 00000170 67 72 61 6d 6d 69 6e 67 57 65 62 6e 67 0b 70 72 |grammingWebng.pr| 00000180 6f 67 72 61 6d 6d 69 6e 67 65 62 77 69 6e 67 00 |ogrammingebwing.| 00000190 00 00 00 00 00 00 00 00 |........| 00000198 $ du -b *.db # size in bytes 408 urldb0.db
2.3 Interpretation
Examining the hex dump gives some clues to how the data is laid out in ram.
| column | type | bytes |
|---|---|---|
| id | cardinal |
4 |
| url | string[36] |
37 |
| title | string[24] |
25 |
| (padding) | 2 | |
| total: | 68 | |
| × 6 rows: | 408 |
It might be surprising that a string of 36 1-byte characters takes up 37 bytes, but that's because a ShortString uses an extra byte at the beginning to store the length. The longest ShortString is therefore string[255], which takes up 256 bytes: enough room for 255 characters, plus the extra byte to store the length.
You can see this in action in the hex dump. If you look at the link for the c2 wiki, you'll see how the URL and title fields contain leftover characters 'n' and 'g' from the /r/learnprogramming link. This indicates that the same area in ram was reused each for pass through the loop, and then copied to disk each time. The double-quote character at the start is ascii character number 34 ($22 in hex). This indicates that the uses 34 of the 36 alloted characters. The extra two characters stick around in ram (and get copied to the disk), but pascal ignores them.
Why the extra 2 bytes at the end? Basically, it's because free pascal is a multi-platform compiler, and on some platforms, loading data that doesn't fall cleanly on word boundaries can have unpleasant consequences. By default, fpc aligns records to a multiple of 4 bytes1.
3 Escaping the Type System
Since we know our records are 68 bytes long, we can choose to represent them as a simple array of bytes. We could create another typed file (file of TUrlBuf) but there's no real need to do this, so we'll just use an untyped (file) instead.
The following program shows an example:
program urldb1a; const kRecSize = 68; kLenPos = 4; // position of url length byte (numbering from 0) var f : file; // untyped file a : array of byte; // dynamic array i : byte; // loop counter begin SetLength( a, kRecSize ); // allocate 68 bytes for the array Assign( f, 'urldb0.db' ); // same file from last lesson Reset( f, kRecSize ); // untyped files need to know the size while not eof(f) do begin BlockRead( f, a[0], 1 ); // load 1*kRecSize bytes from f into a for i := 1 to a[kLenPos] do write(chr(a[ kLenPos + i ])); writeln; end; end.
With untyped files, we add an extra parameter to Reset that tells pascal how big to make the "chunks" it reads from the file. Then we call BlockRead instead of Read. This allows us to read an arbitrary number of chunks into ram at a given address. Above, we're reading 1 68-byte chunk, but we could have just as easily read 68 1-byte chunks, or 2 34-byte chunks, etc.
Compiling and running the program produces the following output:
$ fpc urldb1a.pas && ./urldb1a http://reddit.com/r/learnprogramming http://sourceforge.net/ http://stackoverflow.com/ https://github.com/ http://c2.com/cgi/wiki?WikiWikiWeb http://reddit.com/r/programming
4 Refactoring : extract procedure WriteTuple
Let's refactor a bit, and extract a function for the innermost loop:
procedure WriteTuple( a : array of bytes ); begin for i := 1 to a[kLenPos] do write(chr(a[ kLenPos + i ])); writeln; end;
Now our innermost loop becomes:
while not eof(f) do begin BlockRead( f, a[0], 1 ); // load 1*kRecSize bytes from f into a WriteTuple( a ); end;
Now that we've isolated that code, let's generalize it to print arbitrary relations.
5 MetaData
If we want to display arbitrary relations with a single procedure, we need to find a way to describe the structure of the tuples.
The table we made earlier with the label, type, and size in bytes for each field was sufficient to let us figure out where to start reading the url field, so why not give our program a table like that too?
It's easy. First, we create a TKeyDef type:
type TKeyType = ( ktPadding, ktCardinal, ktString ); TKeyDef = record keyName : string[31]; keyType : TKeyType; keySize : cardinal; end;
The syntax for the TKeyType type is new. It's called an enumerated type, which basically means that we're creating a bunch of identifiers that are associated with the numbers 0, 1, 2, 3… These values aren't numbers themselves (Write(ktString) will output 'ktString' rather than '2') but they're associated with numbers: Write(Ord(ktPadding)) produces '0', just as Write(Ord(#0)) or Write(Ord(false)) does, because all of these are the first possible value of their respective type.
We can now translate our table to pascal as literal array of TKeyDef records:
const keys : array [0..3] of TKeyDef = (( keyName: 'id'; keyType : ktCardinal; keySize : 4 ), ( keyName: 'url'; keyType : ktString; keySize: 37 ), ( keyName: 'title'; keyType : ktString; keySize: 25 ), ( keyName: ''; keyType : ktPadding; keySize: 2 ));
We can rewrite our WriteTuple routine, using pascal's case statement to dispatch on the keyType. (Normally we'd write key.keyType, but adding a with statement to our for loop lets us be a little more concise.)
const kSep = #9; // tab character procedure WriteTuple( a : array of byte ); var offs : byte = 0; // current offset into the record key : TKeyDef; begin for key in keys do with key do begin case keyType of ktCardinal : write(cardinal( a[offs]) : 5); ktString : begin for i := 1 to a[offs] do write(chr(a[offs + i])); for i := i to keySize do write(' '); // padding end; // otherwise do nothing end; write( kSep ); inc(offs, keySize); end; writeln; end;
6 Adding a Header
A nicely formatted header is really just more of the same:
procedure WriteHeader; var key : TKeyDef; begin { write the the field names } for key in keys do with key do begin case keyType of ktCardinal : write( PadLeft( keyname, 5 )); ktString : write( PadRight( keyname, keySize )); end; write( kSep ); end; writeln; { show the separator line } for key in keys do with key do begin case keyType of ktCardinal : write( '-----'); ktString : write( AddChar( '-', '', keySize )); end; write( kSep ); end; writeln; end;
The only new addition is strutils.AddChar( s, c, n ):String, which appends n copies of character c to string s.
6.1 Results
Running the program produces the following output:
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
7 Summary and Next Steps
In this lesson, we saw how to reify (make concrete) the structure of our relations, by creating a new record type to hold metadata.
We will use this same concept later to make our database self-describing, but first we need a way to create tables, records without relying on hex editors, pre-existing binary files, or hard-coded pascal syntax. Therefore, in our next lesson, we will look at how to create a simple command interpreter.
Footnotes:
fpc aligns fields to a multiple of 4 bytes: You can change this behavior with the $PACKRECORDS directive. That page actually claims that the default alignment is 2 bytes, but that doesn't appear to be the case. Hopefully #24418 in the FPC bug tracker will lead to some clarification soon.