The Database of Infinity

Copyright Dr Alan Solomon (1986-1995)

The Boss thumped the table and called the Board to order.  "We can't go
on like this", he said.  "We're losing souls hand over fist, just
because we can't keep proper tabs on them.  Something Must Be Done." So
they set up a Subcommittee to look into the problem.  The Subcommittee
deliberated for several millenia, and eventually came back with a
proposal based on the use of 3 by 5 cards.  "We'll sort alphabetically
by name", they said, "and we'll be able to pull out someone's details in
no time." The Boss thought for a while, and asked "Will we be able to
sort according to sins?" The Subcommittee went back to have another
think, and several more centuries passed.

By this time, Babbage had invented the Analytical Engine, and the
Subcommittee could see that this would solve the sorting problem, so
they reported back to the Boss.  He looked at the proposal, and asked
how long this mechanical monstrosity would take to do a sort.  Somebody
did a few sums and came up with a figure of 23 years.  Someone else
pointed out that most of the data subjects would be dead by then, and so
the Subcommittee went back to the drawing board, and several more
decades went by.

The first valve-based computers were appearing by then.  The heat
obviously ruled these out, but the Subcommittee could see the trend, and
waited patiently.  Eventually, computers that could handle the job
appeared, and the Subcommittee reported back to the Boss.  "There's
quite a lot of choice", they pointed out, as they recommended getting in
a consultant to advise on all this technology.  "Get the best person -
cost is no object", said the Boss.

I was sitting quietly at home, trying to raise my "Marble Madness" score
above what my daughters (aged 5 and 4) were getting, when the Visitation
appeared.  There was a flash of light, and a thunderclap, and a vision
of loveliness appeared, wearing a halo and wings (and a sort of robe).
She explained the problem, and asked if I could help.

"No problem", I said, "Turbo Database Toolbox".  "What's that?", she
said.  So I explained why there was no point in reinventing the wheel,
and how for a silly amount of money you could write a really
sophisticated data base management system in Turbo Pascal.  "What's
Turbo Pascal?", she asked.  So I showed her my favourite compiler, and
she was very interested in it, and in what you could do with it, and she
smelt of hyacinths, and when she asked if we could pop over to her place
so I could show the Boss, I didn't even think twice about it.

So that was why I found myself sweating profusely and trying to get used
to the smell of sulphur dioxide.  I'd fallen for the oldest trick in the
book (come to think of it, it is indeed the oldest trick in the Book).
I've often thought that the best way to tempt people is to pretend that
you represent the forces of Good.  I was brought before the Boss, and
felt quite nervous as I watched him toying with a razor sharp trident,
cleaning his claws.  "So you're the ultimate expert, eh?", he asked.
His piercing red eyes made me feel transparent, and I nodded, and
gulped.  "Solve this problem, and you can have whatever you want." Well,
I've read the books, and I know that you can trust the Prince of Light
about as much as you can trust a dealer who smells a sale.  So I gulped
again, and nodded, and said that I needed to think about the design.

Ashtrial found me a place where the wailing of tortured souls wasn't too
distracting;  she'd dropped her angel disguise by now, and although she
wasn't exactly a vision, she wasn't a bad old stick.  She told me she'd
been a witch, and was now a succubus.  "What's a succubus?", I asked,
and she gave me a very funny look.  She said that she didn't understand
all this modern magic.  I tried to explain that it wasn't actually
magic, but she didn't believe me, and told me not to be silly.  Anyhow,
she apologised nicely for getting me into this hole, but she was only
doing her job, and we got on OK after that.

It's a cardinal mistake to sit down in front of a computer and start to
code;  it much quicker in the long run if you actually design your
project.  I find a computer too tempting, so I can't use a word
processor or outliner - I use good old paper and pencil, preferably 2B.
That was the first problem.  We got some paper, but as soon as Ashtrial
took off the preserve spell, it started to char, and then burst into
flame.  "Fahrenheit 451", I said.  Ashtrial explained that it was only
the preserve spell on me that made it possible for me to survive in that
environment, so I suggested leaving the spell on the paper.  Of course,
that was a daft idea, as everything I wrote on the paper just fell off
the page as soon as I picked it up.

"How do the demons keep records?", I asked.  "Oh, infallible memory",
she said.  My memory is about four bytes, so that wasn't on.  But I make
up for it with ideas, and I asked for a slate and chalk.  That worked
fine, so I could get to work.

The problem, as always, was the sheer size of the problem.  We had to
keep tabs on everyone who had ever been born, and also on everyone who
would be born.  I asked how many people this was, but Ashtrial couldn't
say.  But every time I named a figure, she said it wasn't big enough.

Now fortunately, I'm a mathematician, and it didn't take me long to
realise that there is only one number that is bigger than any number you
care to mention - infinity.  And it was then that the full implication
hit me;  I had to design a database to handle an infinite number of
records.  Gulp.  I boggled a bit.  After I'd finished explaining to
Ashtrial why it was totally impossible, I had a think.  The tortured
shrieking had died down a bit, and if I closed my eyes against the dull
red light and didn't breath, things felt quite normal.  Unfortunately, I
have this terrible tendency to fall asleep when I close my eyes, and
sure enough, off I went.

I woke up with a start.  The shrieking had suddenly got much louder, and
I sat up.  Ashtrial was a bit closer than I would have expected;  in
fact much closer.  I asked her what the racket was, and she explained
that it was just the demon shift changing, "When they come on-shift
they're a bit more enthusiastic with the pitchforks", she said.  I
jumped out of bed, full of optimism and keenness to tackle what appeared
to be an impossible problem.

The trick was to design something that was completely open ended, but
which could be sorted and searched.  The trouble is, most the sort
algorithms I know take a time that is proportional to the square of N,
the number of records.  The better algorithms are proportional to
N.log(N), and even the spaghetti algorithm is proportional to N.  You
didn't know the spaghetti algorithm?  OK, a short digression - you cut
lengths of spaghetti so that the lengths of the spaghetti is
proportional to the thing you're sorting;  this takes a length of time
that is proportional to N.  Then you pick up the spaghetti in an
unsorted bundle, and bang one end of the bundle against the table - the
bundle is now sorted.

So every time the database was sorted, it would take Eternity to
complete;  clearly not on.  But the database HAD to be sorted, as
otherwise it would take an infinite time to search.

I explained all this to Ashtrial, but her idea was that computers were
so fast, it wouldn't matter if things took a long time.  I thought about
various sorting algorithms, and how they could be adapted, and Ashtrial
practised her tempting, which I found a bit distracting.  It was while
she was doing something with a rather complicated set of chains that I
suddenly had an idea, and I was so pleased with it that I called
Ashtrial over to explain it.  It was the chains that had inspired me.

Suppose you have a large number of records, and suppose they are sorted,
by name, perhaps.  Suppose the records are chained together in a
linked-list (if you don't know what that is, see my article on
pointers).  To add a record, all you have to do is traverse the
linked-list down to where the record should go, then add it using the
usual method of adjusting the pointers.  So no matter how large the
database becomes, you can always add a record, and it is always sorted,
and this is therefore an infinite, sorted database.

But you also need to search the database by some criterion other than by
name - by sin, for example.  Very simple - suppose that you have a
second linked-list of pointers that is sorted by sins.  When you put the
new record in, you also update this linked-list.  So you have a database
which is infinite, and can be searched by name or by sin.  And you can
see how you can search on any number of fields in the record, just by
using more and more linked-lists, each of which is kept permanently
sorted.

Since the records are sorted already according to every possible
criterion, you never need to sort the infinite database;  all you ever
have to do is update each linked-list whenever you add a record.  And
you can prepare a report according to any criterion or combination of
criteria, just by traversing the appropriate linked-list.

I even designed in some short cuts - a fast-retrieve system keyed to the
data subject's name, using a set of pointers into the chain.  So if you
were looking for Smedley, there was a pointer to the start of the chain
of records of people beginning with SME, and you could start traversing
from there.  Similarly, there was a list of pointers into each of the
other chains, so that you could go straight to the adulterers, for
example (Ashtrial said that this was the most common type of sin).

You've spotted the problem, I bet.  Turbo only uses 2-byte integers, and
this give you access to a mere 65536 records.  Even 4-byte pointers (as
used by the more serious databases) only allow about 4 billion records.
Clearly, an infinite database needs pointers of infinite size.

The thought of this depressed me, as there was no point in having a
database containing nothing but a single, infinite, pointer.  But then I
remembered some of the more interesting properties of infinity, and
decided that there was probably a way round it.  "Where can I get a cup
of coffee round here?", I asked Ashtrial;  I always think better with
coffee in my hand.  She breathed a bit, and said "You can't".  "What do
you mean, you can't?  Where can you get a drink around here?" "That's
part of the torment", she explained.  "It's hot, and dry, and there's
nothing to drink.  The souls hate it." For the first time, I began to
feel a bit of sympathy for them.  Up till then, the tormented souls had
been nothing but a nuisance, distracting me with their wailing and
screaming.  And I felt sure that they were the cause of the disagreeable
smell that periodically wafted up from their pit, whenever the wind
changed.  But to be denied coffee - how on earth did they manage?

I took my slate and chalk and had a think.  I realized that I couldn't
actually store the pointer in the same place as the actual data, as it
would be so big.  But not all pointers had to be big - early on in the
database, two-byte pointers would be enough, and four-byte pointers when
two byte were insufficient, then six-byte, and so on.  In other words,
the pointers would be of variable size!  I though of having a single
byte in front of the pointer that would contain the pointer's length,
but realised that even that would run out.  So I decided to use the C
method, and I'd put a zero byte at the end of the pointer.  That meant
that a zero byte could not be part of the pointer, but that could be
avoided by using base-255 numbers for pointers, and only allowing 1 to
255 in the pointer bytes.  I toyed with the idea of using prime numbered
blocks for storing these huge pointers, and the other blocks for data,
and where a pointer was needed in the data block, I'd have a
pointer-pointer (a pointer to a pointer) which would point to the actual
pointer, which would be nearby.  But then I realised that at the larger
end of the integer spectrum, the primes became rather rare, and I'd need
a pretty big pointer-pointer.  So I thought of making every
even-numbered block a pointer, but that would waste rather a lot of
space when pointers were only 4 bytes.  So I compromised, and decided to
use a scheme that made every 128th record a potential pointer.  This
still allowed me an infinite amount of space for pointers, but wasted
less than 1% of the disk space, and still guaranteed that you could find
a block for a pointer not too far away from a record. Each block would
be a nice round 1024 bytes.

By now, I was puffing rather from the effort of heaving large amounts of
slate around, and I sat down for a rest.  Ashtrial joined me, and asked
what we were going to do with all that slate.  "Don't touch it", I
warned, "It's got all my designs on it." She muttered something
inaudible about designs, and I started thinking about hardware.  Looking
through my back issues of Infernal Machine, I soon realised that I
wasn't going to find a hard disk with infinite storage at any price.
But that wasn't a real problem, as I'd met a problem very like this
before.  My last big project had been in an environment that was as cold
as this one was hot (see A Computer for Christmas), and I'd developed a
way of networking networks together.  I simply extended this system and
designed a tree of LANs so that no matter how many there were, a
workstation could be removed and replaced with an entire LAN of
workstations.  This meant that hard disk space could be extended
infinitely, and that solved the hardware problem.  That left only one
minor problem - how to get myself home after the project was finished.
We've all read the stories about how Lucifer tricks the poor stupid
human, and I didn't want to spend the rest of my life coffeeless.  But
I've been in this sort of situation before, and I knew exactly how to
deal with it.

"I'm ready to see the Boss", I told Ashtrial.  She insisted on getting
changed into something less informal (although, given the ambient
temperature, I could see why you didn't really want to wear heavy
clothes all the time) and off we went.

We reached the throne room, and Beelzebub stopped playing with something
red and squishy (I couldn't quite see what it was) and said "Well?"
Ashtrial looked distinctly nervous, but to me this was just another
client with just another set of unique requirements, and I soon forgot
who I was talking to, as I launched into my usual pitch.  It's always
difficult knowing how technical to get when you're talking to a client,
but I've found that if you talk about concrete examples, it makes things
much clearer.

I explained that, although he'd heard a lot about dBase III plus, it
simply wasn't designed for such a big job, and I explained about the
special problems posed by the infinitistic nature of the database, and
how I'd solved them.  I explained that he'd be able to request a report
based on whatever criterion he wanted, that the database would never
need sorting or indexing, and about how it would meet all his needs from
now till Eternity.  I could see he was impressed.  "How soon can we have
it", he said.  "Money is no object".

"First we have to reach a binding agreement", I said, "Signed in blood."
"And what is your fee?", he asked.  Go for broke, I thought;  he who
doesn't ask, doesn't get.  I would ask for something plainly outrageous,
and settle for something less.  "I want to be able to program in C", I
said.  "Done", he said.  The speed with which he agreed to such an
outrageous request worried me a bit, but I reasoned that it didn't cost
him anything, so why should he quibble.  And it sure would be nice to be
able to program in C.

Back in the quiet place, I took some fresh slates and started making a
list of hardware.  Ashtrial was clattering around, making even more
noise than the damned souls, and I've been around women enough to know
that this meant I'd upset her somehow.  I asked her what was up.  "You
wasted a perfectly good wish", she said, but when I asked her what I
should have wished for, she just snorted, and went back to tidying up
again.  Eventually I finished my list of hardware, and told her I was
ready to go shopping.

We needed quite a lot of hardware, of course, and the order was one that
any dealer would be willing to sell his soul for.  But we had terrible
trouble finding one that hadn't already sold it, and then he insisted on
cash with order, so he could get the necessary boxes from his supplier.
Fortunately, I'd expected this, and I'd popped in on Mammon before
leaving Hell.  We got him to deliver the lot to Stonehenge, Ashtrial
drew a pentagram round it all, did something unspeakable to a chicken
and we found ourselves back in hell.

The first step was to set up an air-conditioned room.  IBM PC's are
pretty tolerant of difficult conditions, but at temperatures around 451
Fahrenheit, semiconductors don't semiconduct, and insulators don't
always insulate.  And floppy disks get distinctly floppy.  I was
wrestling with the problem of how to make an infinite air-conditioned
room, when Ashtrial came up with a brilliant idea.  "Why don't we use
Eskimo Hell?", she said.  I thought she was referring to an obscene song
I'd once heard, but it was just that you couldn't hear anything properly
with all the caterwauling that the lost souls were making.  It seems
that heat is the Eskimo idea of heaven, so there was a special frigid
area just for them.  We put the computer systems in the boundary between
the normal hell and Eskimo hell, where the temperature was just right.
That also solved the electricity problem - we used the temperature
difference to drive the dynamos.

The day came when everything was ready.  I laid on an impressive
ceremony, full of flashing lights and beeps.  The Horned One pulled the
switch, and everything started booting up.  After the whirring and
flashing had subsided, he turned to me and said "Is that it?".  "Yes", I
said proudly, watching the damned entering infinite amounts of data into
my database.  "Right, then - here's your reward".  Instantly, I could
see how to program in C. "Oh wow", I said. "There is a
pointer-structure that isn't ill-defined into the state-space.
The struct that is mapped onto is an endomorphism of the similarity
matrix. Look, an n++ could self-modify the inversion, and then
the modification remediates the data!"

Lucifer grinned, evilly.  My mind had been warped into C programming,
and I couldn't express myself clearly, or even think straight.  I'd been
swindled!  But I still had a card to play.  Have you ever wondered why
programmers put bugs into programs?  "Unless you unscramble my mind, I
wont be able to remove any of the bugs in this system", I said.
"Bugs?", he said.  "Bugs." I said.

In an infinite database like this, you can expect an infinite number of
bugs.  So I should be safe for eternity, although just to be on the safe
side, I've started praying now and then, just as a hedge, you
understand.