mysqlmysql-5.7transitive-closure-table

Transitive-Closure Table Restructure


How would I be able to retrieve a full-tree from the current structure, or refactor the current table structure to allow for an optimized recursive query?

Issue

Unable to retrieve full-tree of components from base component without iteration.

A single component can have an undefined number of connections (depth).

Components do not have a parent property, as each component can be related to multiple components.

Unable to recursively update affected attribute values of a component. For example if the price of a component changes, the price is updated for all related components_of.

Current Structure

component

primary key (id)
| id | price |
|----|------ |
| A  | 1     |
| B  | 1     |
| C  | 1     |
| D  | 2     |
| E  | 2     |

component_closure

unique index (component, component_of)
index (component_of)
FK (component) References component (id)
FK (component_of) References component (id)
| component | component_of |
|--------------------------|
|     D     |  B           |
|     D     |  C           |
|     B     |  A           |
|     E     |  C           |
|     E     |  A           |

Resulting Graph Model:

graph

Example query:

UPDATE component
SET price = 2
WHERE id = 'A';

Desired Result (* indicates recursively updated values)

| id | price |
|----|------ |
| A  | 2     |
| B  | 2     | *
| C  | 1     |
| D  | 3     | *
| E  | 3     | * 

I am thinking I would need to store the entire tree relationship in the component_closure table, so that I would be able to retrieve the component_of relationships of all components and use a depth column to determine the order of components. Though that seems wasteful when the full-tree is not needed, such as for immediate components_of.

For example:

| component | component_of | depth |
|-----------|--------------|-------|
|  D        | A            | 1     |
|  D        | B            | 2     |
|  D        | C            | 1     |

Solution

  • Yes, if you want to store the transitive closure, you need to store all paths.

    For some operations, it's even helpful to store the path of length 0:

    | component | component_of | depth |
    |-----------|--------------|-------|
    |  D        | D            | 0     |
    |  D        | A            | 1     |
    |  D        | B            | 2     |
    |  C        | C            | 0     |
    |  B        | B            | 0     |
    |  B        | A            | 1     |
    |  A        | A            | 0     |
    

    In MySQL 8.0, none of this will be needed. We'll finally be able to use recursive queries.