Storing Decision Trees in a Database: A Deep Dive

Introduction

When dealing with sequences of actions, such as in game development or decision-making algorithms, it’s essential to store and query the data efficiently. In this article, we’ll explore different approaches to representing a sequence of actions in a database while keeping detailed information about each action.

The Problem

We have multiple actions players can take in a game, and we need to track each action taken by a player. We care about the action’s size (if applicable), other action possibilities that weren’t taken, the player who took the action, the action that player faced before their move, and whether some action happened or did not happen before the action we’re looking at.

Database Models

We’ll examine three potential database models: relational, document-based, and graph databases. Each model has its strengths and weaknesses, and we’ll discuss the trade-offs for each approach.

Relational Model

The relational model presents a simple but inefficient way to store actions:

game  |  player  |  seq_n  |  action  |  time  |  deal_opp  | discard_opp
123   |  Player1  |   1     |   deals  |  0.28  |     1      |     1

However, to see the previous actions taken in the same game requires multiple inner joins, which becomes inefficient for large tables (e.g., billions of rows).

Document-Based Model

Storing actions in a document-based database can simplify aggregates:

game: 123
actions: [
    {
        player: Player1,
        action: deals,
        time: 0.69,
        deal_opp: 1
        discard_opp: 1
    },
    {
        player: Player2,
        action: discards,
        time: 1.21
        deal_opp: 0,
        discard_opp: 1,
    }
    ...
]

However, this approach doesn’t allow for easy identification of the player who took each action.

Graph Database

Graph databases can represent actions as a linked list or a decision tree:

(id, player, action, time)
(1, Player1, deals, 0.69)
(2, Player1, call, 1.21)
(3, Player2, discards, 1.51)

(id, action, prev_action, next_action)
(4, deal, 1, 5)
(5, discard, 4, null)

However, graph databases might be overkill for this use case.

Closure Tables

A closure table is a technique to efficiently query previous actions in a relational database. It works by creating a separate table with foreign keys referencing the original table:

closure_table (id, game_id, action_id, prev_action_id)

This approach allows you to quickly find previous actions for each action in a game.

Modified Preorder Tree Traversal

For storing decision trees in a relational database, one efficient approach is using modified preorder tree traversal. This technique involves creating a new table with the child nodes of each node as separate rows:

decision_tree (id, parent_id, action)
(1, null, deals)
(2, 1, call)
(3, 1, discard)

This allows for efficient querying of previous actions in the decision tree.

Conclusion

When dealing with sequences of actions, it’s essential to choose an approach that balances data storage efficiency and query complexity. Relational databases can be optimized using techniques like closure tables or modified preorder tree traversal. Document-based models simplify aggregates but don’t allow for easy identification of player actions. Graph databases offer flexibility but might be overkill for this use case.

Example Use Case: Game Development

In a game development scenario, we can store the sequence of actions as follows:

decision_tree (id, parent_id, action)
(1, null, deals)

closure_table (id, game_id, action_id, prev_action_id)
(1, 123, 1, 5)

modified_preorder_tree_traversal (id, child_node_id, new_child_node_id)
(1, 2, 6)

This allows us to efficiently query previous actions and navigate the decision tree.

Last modified on 2024-06-21