Relational Data Design

Representing complex data in a computational framework

Data layout and structure is a constant trade-off between performance, readability, maintenance, future-proofing, extendability, and reuse. While more complex tables can achieve higher performance and readability, the cost becomes future proofing, maintainability, and often scalability.

Moving towards a document store type of data storage is incredibly beneficial for their simplicity and flexibility. They are more akin to file systems where documents are accessed by name and have few limitations on how they are structured. This is very good for horizontal scalability since it is easy to add more hardware when data does not need to be consistent across multiple tables/machines.

The relational model is a very good fit for developing non-sparse data layouts. However, for widely scaled systems the relational model can be inappropriate. Larger calculations and process now run via map-reduce. The most valuable high level data processing techniques are often a combination of hardware-focused data manipulation layers being used with functional type algorithms.

Data Normalization

Relational models require atomicity when working with data. For our purposes, this means normalizing data to the level of a noun, or a nameable piece. Consider the following setup code:

const mesh_room: Mesh = loadMesh("room_mesh");
const mesh_room_start: Mesh = loadMesh("room_start_mesh");
const mesh_room_trapped: Mesh = loadMesh("room_trapped_mesh");
const mesh_key: Mesh = loadMesh("key_mesh");
const mesh_potion: Mesh = loadMesh("potion_mesh");
const mesh_armor: Mesh = loadMesh("armor_mesh");

const texture_room: Texture = loadTexture("room_texture");
const texture_room_start: Texture = loadTexture("room_start_texture");
const texture_room_trapped: Texture = loadTexture("room_trapped_texture");
const texture_key: Texture = loadTexture("key_texture");
const texture_potion: Texture = loadTexture("potion_texture");
const texture_armor: Texture = loadTexture("armor_texture");

const animation_key_bob: Animation = loadAnimation("key_bob_animation");

const k1: PickupId = createPickup(
  type_key,
  mesh_key,
  texture_key,
  tint_color_copper,
);
const k2: PickupId = createPickup(
  type_key,
  mesh_key,
  texture_key,
  tint_color_silver,
);
const k3: PickupId = createPickup(
  type_key,
  mesh_key,
  texture_key,
  tint_color_gold,
);
const p1: PickupId = createPickup(
  type_potion,
  mesh_potion,
  texture_potion,
  tint_color_green,
);
const p2: PickupId = createPickup(
  type_potion,
  mesh_potion,
  texture_potion,
  tint_color_purple,
);
const a1: PickupId = createPickup(
  type_armor,
  mesh_armor,
  texture_armor,
  null,
);

const r1: Room = createRoom(
  worldPosition(0, 0),
  mesh_room_start,
  texture_room_start,
  null,
);
const r2: Room = createRoom(
  worldPosition(-20, 0),
  mesh_room_trapped,
  texture_room_trapped,
  hpDamage(10),
);
const r3: Room = createRoom(
  worldPosition(-10, 20),
  mesh_room,
  texture_room,
  null,
);
const r4: Room = createRoom(
  worldPosition(-30, 20),
  mesh_room,
  texture_room,
  null,
);
const r5: Room = createRoom(
  worldPosition(20, 10),
  mesh_room_trapped,
  texture_room_trapped,
  hpDamage(10),
);

addDoor(r1, r2, null);
addDoor(r1, r3, k1);
setRoomAsSpecial(r1, starting_room, worldPosition(1, 1));

addPickup(r2, k1, worldPosition(-18, 2));
addDoor(r2, r1, null);
addDoor(r2, r4, k2);

addPickup(r3, k2, worldPosition(-8, 12));
addPickup(r3, p1, worldPosition(-7, 13));
addPickup(r3, a1, worldPosition(-8, 14));
addDoor(r3, r1, null);
addDoor(r3, r2, null);
addDoor(r3, r5, k3);

addPickup(r4, k3, worldPosition(-28, 14));
addPickup(r4, p2, worldPosition(-27, 13));
addDoor(r4, r2);

setRoomAsSpecial(r5, exit_room, null);

This snippet is fairly complicated, involves multiple objects referencing each other, and needs to orchestrated so that all pieces are created before they can be referenced. This results in staggered phases of setup and linking. In order to make this design more database-like, the data needs to be normalized into tables.

Meshes - 0NF

Textures - 0NF

Animations - 0NF

Pickups - 0NF

Rooms - 0NF

Normalization

There are many stages of normalization, including six normal forms. It is critical to know them and understand why they exist. Opting for a data first approach instead of objects/classes allows for data to be manipulated together. It also allows for changes to the design now require fewer changes to the data.

First Normal Form

Ever cell contains one and only one atomic value. There should exist no array of values, no null entries, and every row should be distinct. All tables should have a unique primary key to assist with sorting and optimizing data access. The key should also be as small as possible and because of the uniqueness rule, every row has an implicit key. This can include using the whole row as a key, but this is to be avoided if possible.

On the topic of treating a row in a database as a key, think of the table as a set and an insert is checking if a combination exists. This can be useful if the number of possible values is small enough to be represented with a bit set. Bit sets take up significantly less memory and can be accessing in $O(1)$ time.

To normalize to first normal form, we need to first remove null values and treat them as new tables.

Pickups - 1NF

PickupTints - 1NF

PickupAnimations - 1NF

First normal form will create more tables with fewer columns in those tables and will only create rows for things that matter. This means more memory usage, but it also means that we no longer need to check for null values in our code, removing unnecessary state.

Rooms - 1NF

PickupInstances - 1NF

Doors - 1NF

LockedDoors - 1NF

Traps - 1NF

Laying out data like this takes up less space in larger projects as the number of null entries or arrays would have only increased with the increased complexity. Now we can add new features without having to revisit the original objects.

Second Normal Form

Second normal form is about trying to pull out columns that don’t depend on only a part of the primary key. This can happen when the table requires a compound primary key. Consider the following alternative representation of pickups

Pickups - 0NF

Pickups - 1NF

TintedPickups - 1NF

Pickups - 2NF

PickupTints - 2NF

PickupAssets - 2NF

PickupAnimations - 2NF

Third Normal Form

Third Normal Form removes transitive dependencies on the primary key via another column in the table. For example, any room that has a mesh will also have a matching texture.

Rooms - 1NF

Rooms - 3NF

TexturesAndMeshes - 3NF

Boyce-Codd Normal Form

Boyce-Codd Normal Form, BCNF, is normalizing the functional dependencies.

Rooms - BCNF

Rooms - BCNF

Domain Key Normal Form

Domain key normal form considered to be the last normal forms, but for developing efficient data structures, it should be considered early and often. Domain knowledge is preferable when writing code as it makes immediate sense. Domain knowledge is the idea that data depends on other data, but only given information about the domain in which it resides. It can also be presenting a human interpretation of the data, but this is not always the case. Consider the following transformation:

TexturesAndMeshes - 3NF

Assets - DKNF

Operations

Manipulating data will always be handled with either an insert, delete, or update. It’s considered best practice to only modify data using actions that would be commonly found in a database to avoid unexpected state complexity. Even though the data is now laid out like a database, we are not required to use a query language to access it.

Stream Processing

All data can be implemented as streams. Tables can be thought of as sets of all possible permutations of the attributes. Processing a set can be thought of as traversing the set and producing an output set. Given that sets are unordered, this means we can trivially introduce parallel processing.

Stream processing, instead of random access processing, means that we can process data without the need write to variables outside of the process. This means no side-effects and easy parallelization because the order of operations is irrelevant. This makes it easier to think about the system, inspect, debug, extend, and interrupt it.

References

• Data-Oriented Design