🚀 go-pugleaf

  The secret to having multiple keys in a dbm database is to use the
first byte as the key type. It's that easy, and works very nicely
thanks.

  I did some limited testing of dbm and gdbm, and found that while gdbm
kept the file size way down, the build time was a lot longer.
-- 
bill davidsen - davidsen@sixhub.uucp (uunet!crdgw1!sixhub!davidsen)
    sysop *IX BBS and Public Access UNIX
    moderator of comp.binaries.ibm.pc and 80386 mailing list
"Stupidity, like virtue, is its own reward" -me

In article <2300@sixhub.UUCP> davidsen@sixhub.UUCP (Wm E. Davidsen Jr) writes:
>  The secret to having multiple keys in a dbm database is to use the
>first byte as the key type. It's that easy, and works very nicely
>thanks.

  Actually, I thought the original poster meant 'multiple keys' in the
sense of one record having several access paths to it.  (For instance,
being able to retrieve employees by either last name or SSN.)  I don't
know of any *dbm package which does this; it's not designed for it.

  Dbm/ndbm/gdbm works fine if you only have one key per record and
don't need the records to be ordered; for slightly more complicated
things, there's probably public-domain code floating around.  For a
real relational DB, unless one can use University INGRES, I suspect
one would need to go the commercial route.

	Anton
   
+---------------------------+------------------+-------------+
| Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison |
+---------------------------+------------------+-------------+

In article <RANG.90Nov15214357@nexus.cs.wisc.edu> rang@cs.wisc.edu (Anton Rang) writes:
>In article <2300@sixhub.UUCP> davidsen@sixhub.UUCP (Wm E. Davidsen Jr) writes:
>>  The secret to having multiple keys in a dbm database is to use the
>>first byte as the key type. It's that easy, and works very nicely thanks.
>
>  Actually, I thought the original poster meant 'multiple keys' in the
>sense of one record having several access paths to it.

You can fake it by making one key the primary key and storing the actual data
in its record.  The secondary keys point to the primary key.  To keep sizes
down you might want to make the primary key something small and boring like a
three or four byte serial number. 

Logically each key type is in a separate file, but you can combine them into
one big dbm file using the prefix byte trick.  It's gross, but no grosser
than what real data bases do every day.

You may need to keep copies of the secondary keys in the primary record if
you want to be able to delete the record or change the primary key.  A
perfectly workable alternative is to delete the primary key record when you
delete the record, be prepared for secondary keys to be left dangling, and
delete them in a batch run when you scan the file and pick out the dead wood.

If you do anything like this, the first thing you should do is a consistency
checker that reports secondary keys with no primary keys and (if it's an
error) vice versa.

-- 
John R. Levine, IECC, POB 349, Cambridge MA 02238, +1 617 864 9650
johnl@iecc.cambridge.ma.us, {ima|spdcc|world}!iecc!johnl
"Typically supercomputers use a single microprocessor." -Boston Globe

rang@cs.wisc.edu (Anton Rang) wrote in "ndbm won't cut it, what now?":

>  Dbm/ndbm/gdbm works fine if you only have one key per record and
>don't need the records to be ordered; for slightly more complicated
>things, there's probably public-domain code floating around.  For a
>real relational DB, unless one can use University INGRES, I suspect
>one would need to go the commercial route.
>
>	Anton

O good People of the Net -

We here at Langley Research Center (NASA) are searching
for a robust, (fairly) well-tested
and documented relational db system to assist in the integration of a
large number of applications 'extracting' data from a common db.
We have a package that sits on top of 'any' database, providing a
nice interface to whatever package we choose.  It needs to be PD
because we share our code with a number of universitites and research
facilities, and cannot expect them to invest in ORACLE or INGRES or
what-have you.

We don't need a WHOLE lot of functionality - sorts are not critical.
Just has to handle character, integer, float, double, and variable
length arrays of each.  Desired is the ability to specify a "WHERE"
clause (ie all the records whose 3rd field is less than 50).

I have the ftp-list, but many of the names are cryptic... perhaps
indicating a db package???

Email me with any info you have, and I'll post a summary!

Thanks for your input!
Your Space Program Thanks You!    <note: this is not an official thankyou>

Steve Dahmen


-- 
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Steve Dahmen, Systems Analyst                         (804) 864-4519 (W)
M/S 365,  NASA Langley Research Center                    
Hampton, Virginia  23665                        smd@rehder.larc.nasa.gov

>In article <RANG.90Nov15214357@nexus.cs.wisc.edu> rang@cs.wisc.edu
>(Anton Rang) writes:
>>... I thought the original poster meant 'multiple keys' in the
>>sense of one record having several access paths to it.

(This was the impression I got as well.)

In article <1990Nov16.145542.22326@iecc.cambridge.ma.us>
johnl@iecc.cambridge.ma.us (John R. Levine) writes:
>You can fake it by making one key the primary key and storing the actual data
>in its record.  The secondary keys point to the primary key.  To keep sizes
>down you might want to make the primary key something small and boring like a
>three or four byte serial number. 
>
>Logically each key type is in a separate file, but you can combine them into
>one big dbm file using the prefix byte trick.  It's gross, but no grosser
>than what real data bases do every day.

You also need to store the `next serial number', so you have to reserve a
key for this as well.  This is indeed rather gross.

A few years ago I thought about this problem for a while, and came up with
a different idea based on the same hashing technique.  To explain it I need
to describe the idea behind dbm.

The way dbm works is to take each `key' string and turn it into a
32-bit number, something like a CRC-32 or a checksum.  This number is
not necessarily unique (two different strings will produce the same
32-bit value) but collisions should be rare, if the string-to-number
algorithm is chosen carefully.  In any case, the same string always
produces the same number.

Now to store a `datum', we turn its `key' into our 32 bit number.  This
number is taken as the block number in a file of blocks (typically 4096
bytes each).  To avoid starting out with 2^32 blocks, we ignore `some'
of the bits in this number.  Initially we ignore *all* the bits,
storing all key/datum pairs in block 0; as the database grows, we
ignore fewer bits.  We can leave a binary decision tree behind as a
record of when we stopped ignoring each bit.  This `tree' is simply a
string of bits, 0 where we are still ignoring, and 1 where we are
not.  Given a key hash `h', we start by saying `ignore all the bits',
then we ignore fewer bits as long as bit (h&mask)+mask is set:

	/*
	 * NB: the following is `off the top of my head'.
	 * It may contain errors.
	 */
	hash = calchash(key);
	for (hmask = 0; bit(map, (hash & hmask) + hmask) != 0;
	     hmask = (hmask << 1) | 1)
		/* void */;

Now if the key is anywhere in the database, it is in the block whose
number is (hash & hmask).  The datum for that key is stored immediately
after the key, so all we have to do is read that block and march
through every even-numbered entry, comparing against the key.  If there
is a match, return the corresponding odd-numbered entry.

Under this implementation, storing key=value pairs such as

	mimsy=128.8.128.8 mimsy.umd.edu
	mimsy.umd.edu=128.8.128.8 mimsy.umd.edu
	mimsy.cs.umd.edu=128.8.128.8 mimsy.umd.edu

(a name to number-and-official-name mapping as might be found in a host
number database) requires storing `128.8.128.8 mimsy.umd.edu' three
times---51 bytes, at 17 bytes each, counting the host number as 4 bytes.
Using John Levine's technique we might instead say

	Nmimsy=17
	Nmimsy.umd.edu=17
	Nmimsy.cs.umd.edu=17
	#17=128.8.128.8 mimsy.umd.edu

so that we can store `128.8.128.8 mimsy.umd.edu' only once, saving 34
bytes (and costing 1+4 per key plus 5 for the intermediate key; we wind
up with a net savings of 14 bytes---minus 2 more hidden inside the dbm
implementation, used when storing that intermediate key).  But this
means that to look up a name we have to say:

	*buf = 'N';
	strcpy(buf + 1, name);
	key.dptr = buf;
	key.dsize = strlen(buf);
	datum = fetch(key);
	if (datum.dptr != NULL) {
		*buf = '#';
		bcopy(datum.dptr, buf + 1, sizeof(int));
		key.dsize = 1 + sizeof(int);
		datum = fetch(key);
		if (datum.dptr == NULL)
			panic("lost target");
		printf("officially, %s = %.*s\n",
		    name, datum.dsize, datum.dptr);
	} else
		printf("%s does not exist\n", name);

There *is* another way.

Instead of storing keys and data in pairs, we can store each
individually.  In other words, we can dissociate them---put each in its
own block.  All we have to do is somehow tie one to the other
(otherwise the database is no good!).  The 32-bit hash value is almost
good enough, but not quite: two different strings can produce the same
hash.  But what if we augment it?

Instead of viewing the database as a series of `key/datum' pairs,
suppose we view it as a collection of `items'.  Each item has three
attributes:

 A. A number that is unique to this item within its block.  (Blocks
    are typically 4096 bytes or so, so there cannot possibly be more
    than 4096 or so items; a 16-bit number suffices.)  I called this
    an `index' for want of a better name; this particular index is
    the item's `in index'.  (`Key' might be a better name in some
    other context :-) .)  This exists so that the item can be a datum.

 B. A `link' record consisting of a 32-bit value and another index.
    This is only used if the item is considered a `key'.  The index
    here is an `out index'; it is zero if the item is not acting as
    a key.  The 32-bit value is an `out hash'.

 C. A `link count' telling how many times this item is a key or datum
    (it can only be a key once).

Now to store an item, whether as key or datum, we compute its hash and
find its block as above.  Then, if the item is a key (has a nonzero
`out index') and we are replacing its current content (link target),
we `unlink' its current target, store the new datum, and `link' this
key to the item produced here.  If the item is not a key and is being
made one, it simply acquires an `out index'.  If the item is a datum,
we just increment its link count.

To find a key's datum, we `follow the link': the out hash is the hash
value for the key's datum.  Just as with a key, this (plus the decision
bit tree) tells us exactly which block will contain the key's datum
(which in this case is certain to exist).  Since the item index values
are unique to each block, once we have the correct block all we need to
do is find the item with the same `in index' number that the key has in
its `out index'.

Thus, instead of

	Nmimsy=#17
	Nmimsy.umd.edu=#17
	Nmimsy.cs.umd.edu=#17
	#17=128.8.128.8 mimsy.umd.edu

we might have a database that looks like this:

	<block 1>:
	   <in=1, out=2, outhash=3ab197c4, links=1, "mimsy">
	<block 3>:
	   <in=3, out=2, outhash=3ab197c4, links=1, "mimsy.umd.edu">
	   <in=4, out=2, outhash=3ab197c4, links=1, "mimsy.cs.umd.edu">
	<block 4>:
	   <in=2, out=0, outhash=0, links=3, "128.8.128.8 mimsy.umd.edu">

More interestingly, if we create a new database and stick

	hello=hello

into it, we get:

	<block 0>:
	   <in=1, out=1, outhash=195e094c, links=2, "hello">

This key points to itself!

There is no problem with circular references, because a key does not
point to another `key', but rather to an `item'.  This item has two
references (itself as a key, and itself as a datum), not infinitely
many.  Storing hello=world causes the count to go to 1 (when the
as-datum link vanishes); removing `hello' as a key then makes the count
go to 0.

The main problem with this scheme is that, as with John Levine's, it
takes two database accesses to locate an item (though this time the
work is hidden from the programmer).  There is also a problem with the
index values.  As each block fills and splits, a new block is created
with some index values `used up', and it can become difficult to decide
on the next `available in index'.  I got around this by recording
minimum and maximum `in use' index numbers in each block header, so
that typically simply taking the next number suffices.  When the min
and max values reach 1 and 65535 (actually USHRT_MAX), however, it is
necessary to scan the block for a free number.  Also, this technique
imposes a fair amount of overhead (12 bytes per item for a size offset,
link count, two index values, and the out hash, versus 2 bytes per item
in dbm/ndbm for the size offset).
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris