How would you represent a hashtable collection in a database schema?

Question

If you were trying to create a domain object in a database schema, and in your code said domain object has a hashtable/list member, like so:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

A Dictionary is just a hashtable/list mapping object keys to value keys, I've come up with multiple ways to do this, creating various join tables or loading techniques, but they all kind of suck in terms of getting that O(1) access time that you get in a hashtable.

How would you represent the SpaceQuadrant, SpaceCoordinate, and Space Object in a database schema? A simple schema code description would be nice, ie.

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

but any thoughts at all would be nice as well, thanks for reading!

More Information:

Thanks for the great answers, already, I've only skimmed them, and I want to take some time thinking about each before I respond.

If you think there is a better way to define these classes, then by all means show me an example, any language your comfortable with is cool

Answer 1

Relations are not hash tables; they are sets.

I wouldn't organize the database using the coordinates as the key. What if an object changes location? Instead, I would probably treat coordinates as attributes of an object.

Also, I assume there is a fixed number of dimensions, for example, three. If so, then you can store these attributes of an object in fixed columns:

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

In your object-oriented class, it's not clear why your objects are in a dictionary. You mention accessing them in O(1) time, but why do you do that by coordinate?

If you're using that to optimize finding objects that are near a certain point (the player's spaceship, for instance), you could also build into your SQL query that populates this SpaceQuadrant a calculation of every object's distance from that given point, and sort the results by distance.

I don't know enough about your program to know if these suggestions are relevant. But are they at least making you think of different ways of organizing the data?

Answer 2

In the simplest case, the dictionary has a key which would map to the primary key of a table - so that when you specify the values of the key, you can immediately find the matching data via a simple lookup.

In this case, you would need a table SpaceQuadrant with any general (single-valued) attributes that describe or characterize a space quadrant. The SpaceQuadrant table would have a primary key, possibly a generated ID, possibly a natural value. The hashtable would then consist of a table with the primary key value for cross-referencing the SpaceQuadrant, with the position (a SpaceCoordinate) and the attributes of the quadrant and coordinate.

Now, if you have an extensible DBMS, you can define a user-defined type for the SpaceCoordinate; failing that, you can use a trio of columns - x, y, z or r, theta, rho, for example - to represent the position (SpaceCoordinate).

In general terms, the structure I'm describing is quite similar to Bill Karwin's; the key (pun not intended until after I was rereading the message) difference is that it is perfectly OK in my book to have the position as part of the primary key of the sub-ordinate table if you are sure that's the best way to organize it. You might also have an object ID column that is an alternative candidate key. Alternatively, if objects have an existence independent of the space quadrant they happen to be in at the moment (or can exist in multiple positions - because they aren't points but are space stations or something), then you might have the SpaceObject in a separate table. What is best depends on information that we don't have available to us.

You should be aware of the limitations of using a SpaceCoordinate as part of the primary key:

• no two objects can occupy the same position (that's called a collision in a hash table, as well as in 3D space),
• if the position changes, then you have to update the key data, which is more expensive than an update up non-key data,
• proximity lookups will be hard - exact lookups are easy enough.

The same is true of your dictionary in memory; if you change the coordinates, you have to remove the record from the old location and place it in the new location in the dictionary (or the language has to do that for you behind the scenes).

Answer 3

A dictionary is a table. The hash is a question of what kind of index is used. Most RDBMS assume that tables are big and densely packed, making a hashed index not appropriate.

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

Your Space objects have FK references to the Quadrant in which they're located.

Depending on your RDBMS, you might be able to find a hash-based index that gets you the performance you're hoping for. For example MySQL, using the HEAP storage engine supports HASH indexes.

Answer 4

First, dedicated support for geo-located data exists in many databases - different algorithms can be used (a spatial version of a B-Tree exists for instance), and support for proximity searches probably will exist.

Since you have a different hash table for each SpaceQuadrant, you'd need something like (edited from S.Lott's post):

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

This is a (SpaceCoordinate, Quadrant) -> SpaceObjectId dictionary.

=====

Now, about your O(1) performance concern, there is a lot of reasons why it's wrongly addressed.

You can use in many DB's a hash index for memory-based tables, as somebody told you. But if you need persistent storage, you'd need to update two tables (the memory one and the persistent one) instead of one (if there is no built-in support for this). To discover whether that's worth, you'd need to benchmark on the actual data (with actual data sizes).

Also, forcing a table into memory can have worse implications.

If something ever gets swapped, you're dead - if you had used a B-Tree (i.e. normal disk-based index), its algorithms would have minimized the needed I/O. Otherwise, all DBMS's would use hash tables and rely on swapping, instead of B-Trees. You can try to anticipate whether you'll fit in memory, but...

Moreover, B-Trees are not O(1) but they are O(log_512(N)), or stuff like that (I know that collapses to O(log N), but bear me on this). You'd need (2^9)^4 = 2^36 = 64GiB for that to be 4, and if you have so much data you'd need a big iron server anyway for that to fit in memory. So, it's almost O(1), and the constant factors are what actually matters.
Ever heard about low-asymptotic-complexity, big-constant-factor algorithms, that would be faster than simple ones just on unpractical data sizes?

Finally, I think DB authors are smarter than me and you. Especially given the declarative nature of SQL, hand-optimizing it this way isn't gonna pay. If an index fits in memory, I guess they could choose to build and use a hashtable version of the disk index, as needed, if it was worth it. Investigate your docs for that.

But the bottom line is that, premature optimization is evil, especially when it's of this kind (weird optimizations we're thinking on our own, as opposed as standard SQL optimizations), and with a declarative language.