Dependent Dimensions (declaration and enforcement)

[mahatoankitkumar]

1st approach

Add the column in Dimensions table ( dependent_dimensions -> Array )
Store the immediate dependents in the array
Say

Store in this way

Dimensions Dependent Dimension ([Text])
A [B]
B [C, D]
C [D]

Retrieval -> O(N), N being the number of nodes in the dependency tree
Update -> O(N) overall
O(N) for cycle detection
O(1) for updating a dependent

2nd approach

Add the column in Dimensions table ( dependent_dimensions -> JSON )
Store the whole dependency tree for all the dimensions

Dimensions Dependent Dimension (JSON)
A store

For B store

Retrieval -> O(1), As we are storing the whole dependency tree for all the dimensions
Update -> O(N) overall
O(N) for cycle detection
O(N) for updating a dependent, As we'll have to update the dependency tree for all the parent dimensions

3rd Approach

Make a new table for storing all the relations

Retrieval -> O(N), As we'll need to go through the all the entries
Update -> O(N) overall
O(1) for cycle detection, As we can directly find the relation between them exists or not
O(N) for updating a dependent, As we'll have to update with new entries showing all the transitive dependency
between the new dimension and all the parent dimensions

4th Approach

Mix of the 2nd approach and 3rd approach
Keep the new table for the relations and store the dependency tree to make the reads faster, but the updation still suffers a bit

Retrieval -> O(1), As we'll find the whole dependency tree in the dimensions table.
Update -> O(N) overall
O(1) for cycle detection, As we can directly find the relation between them exists or not
O(N) for updating a dependent, As we'll have to update with new entries showing all the transitive dependency
between the new dimension and all the parent dimensions

---

---

Api changes (written as per the 2nd approach)

List the dd graph
-> Evaluate the flatten json

Creation a dimension
-> No validation for DAG
-> Add Mandatory dimension as DD

Updating MD
-> Dependent Dimension should exist.
-> validate the dependencies
-> It should be a DAG (No cycles)
-> Update the dependencies
-> update it with MD in workspace.

Updating a dimension
-> Dependent Dimension should exist.
-> Validation
-> It should be a DAG (No cycles)
-> Update the dependencies

Update List Dimensions API

[mahatoankitkumar]

Updated Approach 2

To enable faster reads, we store the entire graph for each dimension using an adjacency list to represent relations. Additionally, we maintain an immediate parent map to facilitate efficient updates.

Graph Representation (Dimension A Example)

A: [B]
B: [C, D]
C: [E]
E: [F]
F: []
D: []

Adding a New Dependency (G → E)
We introduce G as a dependent of E. G has its own dependency graph:

G: [H]
H: []

Cycle Detection
If G’s dependency graph already contains E as a key, a cycle is detected, and we return an error.

Resolving Dependencies
Since no cycle is found, we merge G's dependencies with E’s dependencies:

E: [F]
F: []
G: [H]
H: []

After adding G as a dependency of E, the updated graph becomes:

E: [F, G]
F: []
G: [H]
H: []

Propagating Updates to Immediate Parents
We update all immediate parents of E by resolving their dependencies with E’s updated graph.

Immediate Parent of E: [C]
Updating C with E's dependencies:

C: [E]
E: [F, G]
F: []
G: [H]
H: []

Handling Multiple Immediate Parents
If E had multiple immediate parents, we recursively update all of them using Depth-First Search (DFS) to ensure consistency across the dependency graph.

This approach ensures fast reads and prevents cycles.

[mahatoankitkumar]

Optimization on Approach 2 for faster updates (DISCARDED)

Optimized Approach for Faster Reads and Updates
To enhance both read and update performance, we introduce two additional columns in our storage model:

Dependency Graph – Stores the entire graph structure only at the root node.
Root Node – Indicates the root of the dependency graph for each dimension.

This approach ensures:
Faster Updates – Modifications affect only one graph (stored at the root node).
Optimized Reads – Lookups are efficient as dependencies are centralized at the root.

Storage Structure

Update Process (Example: Adding G as a dependency to E)

1. Fetch G's root's graph i.e. G's graph
   

2. Find If E exists as key in the adjacency list to detect cycle
   

3. If no cycle present, get E's root graph
   

4. Merge the two adjacency list
   

5. Update it with the E's root's graph i.e. A's graph
   

Only A’s Graph is Modified

Read Process (Example: Fetch Dependencies of D)

1. Find Root of D → root(D) = A
   

2. Retrieve Graph from A
   

3. Extract D’s Dependencies graph from A’s Graph
   

This method ensures minimal storage redundancy, efficient updates, and fast lookups.

[knutties]

@mahatoankitkumar - how do we define roots for a graph? roots exists only for trees IIRC. For example: we might have tier and industry as two roots - with merchant/client rolling up to each of them separately.

[mahatoankitkumar]

@knutties Correct, multiple roots can be handled, but will become more complex.
Better to go with this approach then in that case #430 (comment)