Derived Property Dependency DAG: The Engine Behind Cascade Computation

“

Series: S4 Ontology Modeling · Article 8 | Level: Intermediate | Reading Time: 18 min

#TL;DR

Derived properties can form dependency chains — property A depends on B, B depends on C. When C changes, recomputation must follow the order C then B then A. This dependency structure is expressed as a Directed Acyclic Graph (DAG).
Topological sorting guarantees correct computation order — no matter how complex the dependency chain, the DAG's topological sort produces the uniquely correct recomputation order, preventing "computing with stale values."
Circular dependency detection happens at registration time — coomia-dip performs DAG cycle detection when derived properties are defined, rejecting any definition that would cause infinite recursion, catching problems at design time.

#1. Why a Dependency DAG Is Needed

#1.1 Limitations of Simple Derived Properties

Code

Scenario: Single-layer derived property (covered in S4-07)

ObjectType: Order
  totalAmount = SUM(LineItem.lineTotal)

This is straightforward: lineTotal changes → totalAmount recomputes.
Only one layer of dependency, no ordering concerns.

#1.2 When Multi-Layer Dependencies Appear

Code

Scenario: E-commerce platform multi-layer computation

Level 0 (source properties):
  LineItem.unitPrice = 29.99
  LineItem.quantity = 3

Level 1 (first-layer derived):
  LineItem.lineTotal = unitPrice × quantity
  → 29.99 × 3 = 89.97

Level 2 (second-layer derived):
  Order.subtotal = SUM(LineItem.lineTotal)
  → 89.97 + 149.99 + ... = 539.94

Level 3 (third-layer derived):
  Order.taxAmount = subtotal × taxRate
  → 539.94 × 0.13 = 70.19
  Order.totalAmount = subtotal + taxAmount
  → 539.94 + 70.19 = 610.13

Level 4 (fourth-layer derived):
  Customer.lifetimeValue = SUM(Order.totalAmount)
  → 610.13 + 1230.50 + ... = 15892.40

Problem: If unitPrice changes, all 4 levels need recomputation.
If the order is wrong (computing totalAmount before subtotal),
the result is incorrect!

#1.3 Natural Mapping to Graph Theory

Code

Graph representation of dependencies:

unitPrice ─────┐
               ├──→ lineTotal ──→ subtotal ──┬──→ taxAmount ──┐
quantity ──────┘                              │                │
                                             └──→ totalAmount ←┘
                                                      │
                                                      ↓
                                              lifetimeValue

Key observations:
├── Each node is a property (source or derived)
├── Each edge means "A is depended on by B" (A changes → B recomputes)
├── The graph is directed (dependency direction is explicit)
├── The graph must be acyclic (otherwise infinite recursion)
└── This is a DAG (Directed Acyclic Graph)

#2. DAG Data Structure

#2.1 Node Definition

Code

DAG Node (DagNode):

┌─────────────────────────────────────────────────┐
│  DagNode                                        │
├─────────────────────────────────────────────────┤
│  nodeId: STRING          # Globally unique ID    │
│  objectTypeId: STRING    # Owning ObjectType     │
│  propertyId: STRING      # Property identifier   │
│  nodeType: ENUM          # SOURCE / DERIVED      │
│  level: INT              # Topological level     │
│  expression: STRING      # Compute expression    │
│  reducer: ENUM           # Aggregation function  │
│  evaluationMode: ENUM    # REALTIME / DEFERRED   │
│  dependencies: LIST      # Dependency node IDs   │
│  dependents: LIST        # Dependent node IDs    │
│  lastComputedAt: TIMESTAMP                      │
│  computeTimeMs: LONG     # Last compute duration │
└─────────────────────────────────────────────────┘

Example:

nodeId: "Order::totalAmount"
objectTypeId: "Order"
propertyId: "totalAmount"
nodeType: DERIVED
level: 3
expression: "subtotal + taxAmount"
reducer: null (expression-based, not aggregation-based)
evaluationMode: DEFERRED
dependencies: ["Order::subtotal", "Order::taxAmount"]
dependents: ["Customer::lifetimeValue"]

#2.2 Edge Definition

Code

DAG Edge (DagEdge):

┌─────────────────────────────────────────────────┐
│  DagEdge                                        │
├─────────────────────────────────────────────────┤
│  sourceNodeId: STRING    # Depended-on node      │
│  targetNodeId: STRING    # Dependent node         │
│  edgeType: ENUM          # SAME_OBJECT /          │
│                          # CROSS_OBJECT /          │
│                          # CROSS_RELATION          │
│  relationPath: STRING    # Relation path           │
│  weight: DOUBLE          # Compute weight          │
└─────────────────────────────────────────────────┘

Edge types explained:

SAME_OBJECT — dependency within the same object
  Example: Order.totalAmount depends on Order.subtotal
  No cross-relation lookup needed, fastest computation

CROSS_OBJECT — dependency across ObjectTypes
  Example: Order.subtotal depends on LineItem.lineTotal
  Requires relation path to locate associated objects

CROSS_RELATION — dependency through multiple relation levels
  Example: Customer.lifetimeValue depends on Order.totalAmount
  Requires traversing Customer → Order relation

#2.3 Complete DAG Example

Code

E-commerce scenario complete DAG:

Level 0 (source properties):
  [LineItem::unitPrice] [LineItem::quantity] [LineItem::discount]
  [Order::taxRate] [Product::cost]

Level 1:
  [LineItem::lineTotal]
    = unitPrice × quantity × (1 - discount)
    depends on: unitPrice, quantity, discount

Level 2:
  [Order::subtotal]
    = SUM(LineItem.lineTotal)
    depends on: LineItem::lineTotal
  [Order::itemCount]
    = COUNT(LineItem)
    depends on: LineItem (existence)
  [Product::totalSold]
    = SUM(LineItem.quantity)
    depends on: LineItem::quantity

Level 3:
  [Order::taxAmount]
    = subtotal × taxRate
    depends on: Order::subtotal, Order::taxRate
  [Order::averageItemPrice]
    = subtotal / itemCount
    depends on: Order::subtotal, Order::itemCount

Level 4:
  [Order::totalAmount]
    = subtotal + taxAmount
    depends on: Order::subtotal, Order::taxAmount

Level 5:
  [Customer::lifetimeValue]
    = SUM(Order.totalAmount)
    depends on: Order::totalAmount
  [Customer::orderCount]
    = COUNT(Order)
    depends on: Order (existence)

Level 6:
  [Customer::averageOrderValue]
    = lifetimeValue / orderCount
    depends on: Customer::lifetimeValue, Customer::orderCount

#3. Topological Sorting and Computation Order

#3.1 Why Order Matters

Code

Incorrect computation order:

Suppose LineItem.unitPrice changes from 29.99 to 39.99

Wrong order (computing higher levels first):
  1. Compute Order.totalAmount
     → uses old subtotal = 539.94
     → totalAmount = 539.94 + 70.19 = 610.13  ← WRONG!
  2. Compute Order.subtotal
     → uses new lineTotal
     → subtotal = 569.94
  3. totalAmount was already computed, won't recompute
     → final totalAmount = 610.13 (should be 643.64)

Correct order (by topological level, low to high):
  1. Compute LineItem.lineTotal = 39.99 × 3 = 119.97
  2. Compute Order.subtotal = 119.97 + 149.99 + ... = 569.94
  3. Compute Order.taxAmount = 569.94 × 0.13 = 74.09
  4. Compute Order.totalAmount = 569.94 + 74.09 = 644.03  ✓
  5. Compute Customer.lifetimeValue = 644.03 + ...         ✓

#3.2 Kahn's Algorithm (BFS Topological Sort)

Code

coomia-dip uses Kahn's algorithm for topological sorting:

Input: set of changed source properties (changedSources)

Algorithm steps:
  1. Find all affected nodes
     affected = BFS from changedSources along dependents edges

  2. Compute in-degrees for subgraph
     For each node in affected subgraph, count in-degree from within affected

  3. BFS topological sort
     queue = nodes with in-degree 0 (the changedSources themselves)
     result = []
     while queue is not empty:
       node = queue.dequeue()
       result.append(node)
       for dependent in node.dependents:
         if dependent in affected:
           dependent.inDegree -= 1
           if dependent.inDegree == 0:
             queue.enqueue(dependent)

  4. Verify
     if len(result) < len(affected):
       → circular dependency exists! (should not happen, detected at registration)
     else:
       → result is the correct computation order

Example execution:

changedSources = {LineItem::unitPrice}

Step 1 - affected nodes:
  LineItem::lineTotal, Order::subtotal, Order::taxAmount,
  Order::totalAmount, Customer::lifetimeValue,
  Order::averageItemPrice, Customer::averageOrderValue

Step 2 - in-degree computation:
  lineTotal: 0 (source is in changedSources)
  subtotal: 1 (depends on lineTotal)
  taxAmount: 1 (depends on subtotal)
  totalAmount: 2 (depends on subtotal and taxAmount)
  averageItemPrice: 1 (depends on subtotal)
  lifetimeValue: 1 (depends on totalAmount)
  averageOrderValue: 1 (depends on lifetimeValue)

Step 3 - BFS:
  Round 1: [lineTotal]       → subtotal.inDegree = 0
  Round 2: [subtotal]        → taxAmount = 0, totalAmount = 1, avgItem = 0
  Round 3: [taxAmount, avgItemPrice] → totalAmount = 0
  Round 4: [totalAmount]     → lifetimeValue = 0
  Round 5: [lifetimeValue]   → averageOrderValue = 0
  Round 6: [averageOrderValue]

Final order:
  lineTotal → subtotal → taxAmount → avgItemPrice
  → totalAmount → lifetimeValue → averageOrderValue

#3.3 Parallelization Opportunities

Code

Nodes at the same level can be computed in parallel:

Parallel execution plan:

Batch 1 (parallel): [lineTotal]
    ↓
Batch 2 (parallel): [subtotal]
    ↓
Batch 3 (parallel): [taxAmount, averageItemPrice]  ← these two in parallel!
    ↓
Batch 4 (parallel): [totalAmount]
    ↓
Batch 5 (parallel): [lifetimeValue]
    ↓
Batch 6 (parallel): [averageOrderValue]

Parallelism analysis:
  Sequential execution: 7 computation steps
  Parallel execution: 6 batches (Batch 3 parallelized 2 nodes)
  Theoretical speedup: 7/6 = 1.17x

More complex scenarios (wide DAGs) achieve higher parallelism:
  10 independent Level-2 properties → 1 batch in parallel
  Sequential needs 10 steps, parallel needs 1 → 10x speedup

#4. Circular Dependency Detection

#4.1 Why Circular Dependencies Are Fatal

Code

Suppose circular dependencies are allowed:

  A.x = B.y + 1
  B.y = A.x + 1

When A.x = 10:
  B.y = 10 + 1 = 11
  A.x = 11 + 1 = 12  ← A.x changed!
  B.y = 12 + 1 = 13  ← B.y changed again!
  A.x = 13 + 1 = 14  ← infinite loop!

Result:
├── System enters infinite computation loop
├── CPU 100%, memory continuously growing
├── Eventually OOM crash
└── Data in indeterminate state (which step was last computed?)

#4.2 Registration-Time Detection (DFS Coloring)

Code

coomia-dip performs cycle detection at derived property registration:

Algorithm: DFS three-color marking

Color meanings:
  WHITE (unvisited) — initial state
  GRAY  (visiting)  — on the DFS stack, ancestor node
  BLACK (finished)  — all descendants visited

Detection logic:
  function hasCycle(node):
    node.color = GRAY
    for dep in node.dependencies:
      if dep.color == GRAY:
        → Cycle found! dep is an ancestor of current node
        → Record cycle path: dep → ... → node → dep
        return true
      if dep.color == WHITE:
        if hasCycle(dep):
          return true
    node.color = BLACK
    return false

Example 1 — No cycle (normal registration):

  Adding derived property: Order.totalAmount = subtotal + taxAmount

  Detection process:
    DFS(totalAmount) → GRAY
      DFS(subtotal) → GRAY
        DFS(lineTotal) → GRAY → BLACK  ✓
      subtotal → BLACK  ✓
      DFS(taxAmount) → GRAY
        DFS(subtotal) → already BLACK, skip  ✓
        DFS(taxRate) → GRAY → BLACK  ✓
      taxAmount → BLACK  ✓
    totalAmount → BLACK  ✓

  Result: No cycle, registration succeeds

Example 2 — Cycle detected (registration rejected):

  Adding derived property: Order.subtotal = totalAmount - taxAmount
  (But totalAmount already depends on subtotal!)

  Detection process:
    DFS(subtotal) → GRAY
      DFS(totalAmount) → GRAY
        DFS(subtotal) → Found GRAY! → Cycle path!

  Cycle path: subtotal → totalAmount → subtotal
  Result: Registration rejected with error message

Error message example:
┌─────────────────────────────────────────────────────┐
│  CIRCULAR_DEPENDENCY_DETECTED                        │
│                                                      │
│  Cannot register derived property:                   │
│    Order.subtotal = totalAmount - taxAmount           │
│                                                      │
│  Circular dependency path:                           │
│    Order.subtotal                                    │
│      → Order.totalAmount (depends on subtotal)       │
│      → Order.subtotal (CYCLE!)                       │
│                                                      │
│  Suggestion:                                         │
│    Break the cycle by using source properties        │
│    instead of derived properties in the expression.  │
└─────────────────────────────────────────────────────┘

#4.3 Cross-ObjectType Cycle Detection

Code

Cross-ObjectType circular dependencies are more subtle:

  Customer.riskScore = AVG(Order.riskLevel)
  Order.riskLevel = CASE WHEN customer.riskScore > 80 THEN ...

The cycle path spans two ObjectTypes:
  Customer::riskScore → Order::riskLevel → Customer::riskScore

coomia-dip DAG is global, not limited to a single ObjectType:

Global DAG = all ObjectTypes' derived properties merged

Cycle detection runs on the global DAG:
├── Registering Customer.riskScore, depends on Order.riskLevel → no cycle
├── Registering Order.riskLevel, depends on Customer.riskScore
│   → DFS finds Customer.riskScore → Order.riskLevel → Customer.riskScore
│   → Registration rejected
└── No matter how many ObjectTypes are crossed, cycles are detected

#5. Change Propagation Strategies

#5.1 Precise Impact Analysis

Code

Not all derived properties need recomputation when a source changes:

Scenario: LineItem#1001's unitPrice is modified

Complete DAG has 50 derived property nodes
But actually affected are only:

  LineItem#1001.lineTotal    ← direct dependency
  Order#2001.subtotal        ← #1001 belongs to Order#2001
  Order#2001.taxAmount       ← depends on subtotal
  Order#2001.totalAmount     ← depends on subtotal and taxAmount
  Order#2001.averageItemPrice ← depends on subtotal
  Customer#3001.lifetimeValue ← #2001 belongs to Customer#3001
  Customer#3001.averageOrderValue ← depends on lifetimeValue

Impact analysis has two dimensions:
  1. Schema dimension: which property definitions are affected (DAG paths)
  2. Instance dimension: which specific object instances are affected
     (located through relation chains)

Cross of both dimensions = precise recomputation task list
Avoids unnecessary computation (other Orders' subtotal unaffected)

#5.2 Batch Change Merging

Code

When multiple source properties change simultaneously, merge recomputation:

Scenario: Batch import updates 1000 LineItems' unitPrice

Inefficient approach (one by one):
  Change #1 → recompute lineTotal → recompute subtotal → ...
  Change #2 → recompute lineTotal → recompute subtotal → ...
  ...
  Change #1000 → recompute lineTotal → recompute subtotal → ...

  If 1000 LineItems belong to 100 Orders:
  subtotal recomputed 1000 times (but only needs 100!)

Efficient approach (merged):
  Collect all changes → group by DAG level → batch recompute

  Level 1: Batch recompute 1000 lineTotals
  Level 2: Batch recompute 100 subtotals (deduplicated)
  Level 3: Batch recompute 100 taxAmounts
  Level 4: Batch recompute 100 totalAmounts
  Level 5: Batch recompute 50 lifetimeValues (deduplicated)

  90% reduction in redundant computation!

Merge window strategies:
├── Time window: collect all changes within 100ms
├── Count window: collect 1000 changes
├── Hybrid: whichever triggers first
└── Configurable: each derived property can set independently

#5.3 Priority Scheduling

Code

Different derived properties have different recomputation priorities:

Priority matrix:

┌──────────┬───────────────────┬──────────────────────────┐
│ Priority │ Characteristics   │ Examples                  │
├──────────┼───────────────────┼──────────────────────────┤
│ P0 (now) │ Affects user UI   │ Cart total, stock count   │
│ P1 (fast)│ Affects decisions │ Risk score, credit limit  │
│ P2 (norm)│ Affects reports   │ Monthly revenue, LTV      │
│ P3 (lazy)│ Analytics only    │ Historical trends, stats  │
└──────────┴───────────────────┴──────────────────────────┘

Scheduling logic:
  1. P0: Synchronous, computed within the source write transaction
  2. P1: Asynchronous, completed within 100ms
  3. P2: Asynchronous, queued, completed in seconds
  4. P3: Asynchronous, low-priority queue, completed in minutes

Priority propagation rule:
  Child node's priority <= highest priority among its parents
  Example: subtotal is depended on by P0 totalAmount and P2 monthlyRevenue
      → subtotal's priority is automatically elevated to P0

#6. Performance Optimization for Large-Scale DAGs

#6.1 DAG Partitioning

Code

Partitioning strategy for very large DAGs:

Scenario: Global DAG has 10,000 nodes

Problems:
├── Traverse the entire DAG for every change?
├── Topological sort processing 10,000 nodes?
└── Too slow!

Solution: DAG partitioning

Partition by ObjectType boundaries:
  Partition 1: LineItem-related derived properties
  Partition 2: Order-related derived properties
  Partition 3: Customer-related derived properties
  ...

Cross-partition edges:
  Order::subtotal → SUM(LineItem::lineTotal)
  This edge connects Partition 1 and Partition 2

Partitioned computation strategy:
  1. Change occurs in Partition 1
  2. First do topological sort and compute within Partition 1
  3. After completion, notify Partition 2 via cross-partition edge
  4. Partition 2 does its internal topological sort and compute
  5. Cross-partition notification via message queue

Benefits:
├── Each partition's node count << global node count
├── Intra-partition computation can be highly optimized
├── Cross-partition parallel processing (independent partitions)
└── Fault isolation (one partition's error doesn't affect others)

#6.2 Incremental Topological Sort

Code

When DAG structure changes (add/remove derived properties),
no need for full global re-sort:

Incremental update algorithm:

Add node:
  1. Determine new node's dependencies
  2. New node's level = max(dependency levels) + 1
  3. Update dependency nodes' dependents lists
  4. Cycle detection only checks new edges
  Time complexity: O(E_new), E_new = number of new edges

Remove node:
  1. Check if other nodes depend on this node
  2. If yes → reject deletion (or cascade delete)
  3. If no → directly remove node and related edges
  4. No re-sorting needed (other nodes' levels unchanged)
  Time complexity: O(D), D = number of dependent nodes

Modify dependencies:
  1. Remove old edges, add new edges
  2. Recompute affected nodes' levels
  3. Cycle detection only checks new edges
  Time complexity: O(E_old + E_new + V_affected)

#6.3 Computation Caching and Invalidation

Code

Caching strategy:

┌─────────────────────────────────────────────────────┐
│              DAG Computation Cache Architecture      │
│                                                     │
│  ┌──────────┐    ┌──────────┐    ┌──────────┐      │
│  │ L1 Cache │    │ L2 Cache │    │ Persistent│      │
│  │ (in-proc)│ ←→ │ (Redis)  │ ←→ │ (DB)     │      │
│  └──────────┘    └──────────┘    └──────────┘      │
│                                                     │
│  Hit rate targets: L1 > 90%, L2 > 99%              │
│  Invalidation: precise (only affected nodes)        │
└─────────────────────────────────────────────────────┘

Precise cache invalidation:
  Source property changes → traverse along DAG dependents edges
  → only invalidate caches of nodes on the path
  → other nodes' caches remain valid

Example:
  LineItem#1001.unitPrice changes
  Invalidated:
    ✗ LineItem#1001.lineTotal (cache invalidated)
    ✗ Order#2001.subtotal (cache invalidated)
    ✗ Order#2001.totalAmount (cache invalidated)
  Retained:
    ✓ LineItem#1002.lineTotal (unaffected)
    ✓ Order#2002.subtotal (unaffected)
    ✓ Product#4001.totalSold (unaffected)

#7. DAG Visualization and Debugging

#7.1 DAG Visualization API

Code

API: GET /api/v1/ontology/dag/visualize

Request parameters:
  objectTypeId: "Order"         # Optional, limit to ObjectType
  depth: 3                      # Optional, display depth
  format: "mermaid"             # Optional, output format

Response (Mermaid format):

graph TD
  LP[LineItem.unitPrice] --> LT[LineItem.lineTotal]
  LQ[LineItem.quantity] --> LT
  LD[LineItem.discount] --> LT
  LT --> OS[Order.subtotal]
  OS --> OT[Order.taxAmount]
  OS --> OA[Order.totalAmount]
  OT --> OA
  OA --> CL[Customer.lifetimeValue]

  style LP fill:#e8f5e9
  style LQ fill:#e8f5e9
  style LD fill:#e8f5e9
  style LT fill:#fff3e0
  style OS fill:#fff3e0
  style OT fill:#fff3e0
  style OA fill:#fff3e0
  style CL fill:#fce4ec

  Green = source properties
  Orange = derived properties
  Pink = cross-ObjectType derived properties

#7.2 Impact Analysis API

Code

API: POST /api/v1/ontology/dag/impact-analysis

Request:
{
  "sourceProperty": "LineItem.unitPrice",
  "changeType": "VALUE_CHANGE",
  "affectedInstances": ["LineItem#1001", "LineItem#1002"]
}

Response:
{
  "affectedNodes": [
    {
      "property": "LineItem.lineTotal",
      "level": 1,
      "affectedInstances": 2,
      "estimatedComputeTimeMs": 5,
      "evaluationMode": "REALTIME"
    },
    {
      "property": "Order.subtotal",
      "level": 2,
      "affectedInstances": 1,
      "estimatedComputeTimeMs": 10,
      "evaluationMode": "DEFERRED"
    },
    {
      "property": "Order.totalAmount",
      "level": 4,
      "affectedInstances": 1,
      "estimatedComputeTimeMs": 5,
      "evaluationMode": "DEFERRED"
    },
    {
      "property": "Customer.lifetimeValue",
      "level": 5,
      "affectedInstances": 1,
      "estimatedComputeTimeMs": 50,
      "evaluationMode": "DEFERRED"
    }
  ],
  "totalAffectedInstances": 5,
  "totalEstimatedComputeTimeMs": 70,
  "maxDepth": 5,
  "parallelBatches": 5
}

#7.3 Recomputation Tracing

Code

Every recomputation has a complete trace chain:

RecomputeTrace:
├── traceId: "tr-20250115-001"
├── trigger: "VALUE_CHANGE"
├── sourceProperty: "LineItem.unitPrice"
├── sourceInstance: "LineItem#1001"
├── timestamp: "2025-01-15T10:30:00Z"
├── steps:
│   ├── Step 1:
│   │   ├── property: "LineItem.lineTotal"
│   │   ├── instance: "LineItem#1001"
│   │   ├── oldValue: 89.97
│   │   ├── newValue: 119.97
│   │   ├── computeTimeMs: 2
│   │   └── status: SUCCESS
│   ├── Step 2:
│   │   ├── property: "Order.subtotal"
│   │   ├── instance: "Order#2001"
│   │   ├── oldValue: 539.94
│   │   ├── newValue: 569.94
│   │   ├── computeTimeMs: 8
│   │   └── status: SUCCESS
│   └── ...
├── totalSteps: 6
├── totalComputeTimeMs: 45
└── status: COMPLETED

Uses:
├── Debugging: Why did Customer.lifetimeValue suddenly change?
├── Audit: Whose action triggered the cascade recomputation?
├── Performance: Which step was slowest?
└── Rollback: If recomputation errored, restore old values

#8. Failure Handling and Consistency

#8.1 Recomputation Failure Handling

Code

Scenario: Cascade recomputation fails at step 3

  Step 1: lineTotal recomputed successfully   ← persisted
  Step 2: subtotal recomputed successfully    ← persisted
  Step 3: taxAmount recomputation FAILED      ← division by zero!
  Step 4: totalAmount not executed
  Step 5: lifetimeValue not executed

Problem: Data is in a partially updated state
  lineTotal and subtotal have new values
  taxAmount still has old value
  totalAmount still has old value
  → Inconsistent!

Handling strategies:

Strategy A — Full Rollback (strong consistency):
  All completed steps rolled back to old values
  ├── lineTotal restored to 89.97
  ├── subtotal restored to 539.94
  └── Data remains consistent but at old state
  Use case: Financial scenarios, partial updates not allowed

Strategy B — Mark Stale Data (eventual consistency):
  Completed steps keep new values
  Failed and unexecuted steps marked as STALE
  ├── taxAmount marked STALE
  ├── totalAmount marked STALE
  ├── lifetimeValue marked STALE
  └── Background retry task will continue attempting recomputation
  Use case: Most scenarios, brief inconsistency acceptable

Strategy C — Partial Commit + Compensation (hybrid):
  Completed steps committed
  Failed steps enter retry queue
  After retry success, continue subsequent steps
  ├── Maximum 3 retries
  ├── Retry interval exponential backoff: 1s, 5s, 30s
  └── All 3 fail → alert + manual intervention
  Use case: E-commerce scenarios

#8.2 Concurrent Change Conflicts

Code

Scenario: Two changes simultaneously trigger recomputation
of the same derived property

  Transaction 1: LineItem#1001.unitPrice → 39.99
  Transaction 2: LineItem#1002.unitPrice → 19.99

  Both need to recompute Order#2001.subtotal

Conflict resolution strategies:

Strategy 1 — Optimistic Locking:
  Each derived property value has a version number
  During recomputation:
    Read subtotal(version=5, value=539.94)
    Compute new value
    CAS update: UPDATE ... SET value=569.94, version=6 WHERE version=5
    If fails (version already changed) → re-read + recompute

  Pros: Lock-free, high concurrency
  Cons: Many retries under high contention

Strategy 2 — Merge Window:
  Multiple changes within 100ms merged into one recomputation
  Transaction 1 and 2's changes collected in the same window
  Single recomputation of subtotal (using all latest values)

  Pros: Avoids redundant computation
  Cons: Adds latency (up to 100ms)

coomia-dip defaults to Strategy 2 (merge window).
P0 priority properties use Strategy 1 (optimistic locking).

#9. Practical Example: Building a Complete DAG

#9.1 Requirements Analysis

Code

Scenario: SaaS subscription platform

Business requirements:
  1. Subscription MRR (Monthly Recurring Revenue)
  2. Customer total MRR
  3. Customer health score (composite of multiple metrics)
  4. Product total MRR and utilization rate
  5. Company-level total MRR and customer health distribution

#9.2 Property Definition and DAG Construction

Code

ObjectType definitions:

Subscription:
  Source properties:
    unitPrice, quantity, discount, status, startDate, endDate
  Derived properties (Level 1):
    mrr = unitPrice × quantity × (1 - discount) × IF(status == "ACTIVE", 1, 0)
    isActive = status == "ACTIVE"
    daysToExpiry = endDate - today()

Customer:
  Source properties:
    name, segment, lastLoginAt
  Derived properties (Level 2):
    totalMrr = SUM(Subscription.mrr)
    activeSubscriptions = COUNT(Subscription WHERE isActive == true)
    daysSinceLogin = today() - lastLoginAt
  Derived properties (Level 3):
    healthScore = CUSTOM(
      score = 0
      IF totalMrr > 1000: score += 30
      IF activeSubscriptions >= 2: score += 20
      IF daysSinceLogin < 7: score += 30
      IF daysSinceLogin < 30: score += 20
      RETURN score
    )

Product:
  Source properties:
    name, category
  Derived properties (Level 2):
    totalMrr = SUM(Subscription.mrr)
    subscriberCount = COUNT(DISTINCT Subscription.customerId)
  Derived properties (Level 3):
    averageMrrPerSubscriber = totalMrr / subscriberCount

Company (singleton object):
  Derived properties (Level 3):
    totalMrr = SUM(Customer.totalMrr)
    totalCustomers = COUNT(Customer)
    healthyCustomers = COUNT(Customer WHERE healthScore >= 80)
  Derived properties (Level 4):
    healthyCustomerRatio = healthyCustomers / totalCustomers
    averageMrrPerCustomer = totalMrr / totalCustomers

Generated DAG structure:

Level 0: unitPrice, quantity, discount, status, startDate, endDate,
         lastLoginAt, name, segment

Level 1: Subscription.mrr, Subscription.isActive,
         Subscription.daysToExpiry

Level 2: Customer.totalMrr, Customer.activeSubscriptions,
         Customer.daysSinceLogin,
         Product.totalMrr, Product.subscriberCount

Level 3: Customer.healthScore,
         Product.averageMrrPerSubscriber,
         Company.totalMrr, Company.totalCustomers,
         Company.healthyCustomers

Level 4: Company.healthyCustomerRatio,
         Company.averageMrrPerCustomer

Total: 24 nodes, 28 edges, max depth 4

#9.3 Change Propagation Verification

Code

Test case: Modify Subscription#S001's unitPrice

Before:
  Subscription#S001.unitPrice = 99
  Subscription#S001.mrr = 99 × 2 × (1 - 0.1) = 178.20
  Customer#C001.totalMrr = 178.20 + 299.00 = 477.20
  Customer#C001.healthScore = 60 (totalMrr < 1000)
  Company.totalMrr = 477.20 + 1230.50 + ... = 8500.00

After (unitPrice → 199):
  Step 1: Subscription#S001.mrr = 199 × 2 × 0.9 = 358.20
  Step 2: Customer#C001.totalMrr = 358.20 + 299.00 = 657.20
          Product#P001.totalMrr += (358.20 - 178.20) = +180.00
  Step 3: Customer#C001.healthScore = 60 (totalMrr still < 1000)
          Company.totalMrr = 8500 + 180 = 8680.00
  Step 4: Company.averageMrrPerCustomer = 8680 / 50 = 173.60

Verification: All values consistent, no stale data used ✓

#10. Comparison with Other Systems

Code

Derived property DAG design comparison:

┌──────────────┬──────────────────┬──────────────────┐
│ Feature      │ coomia-dip        │ Traditional ETL  │
├──────────────┼──────────────────┼──────────────────┤
│ Trigger      │ Auto on change   │ Scheduled        │
│ Granularity  │ Per instance     │ Full table/batch │
│ Dependencies │ Explicit DAG     │ Implicit (docs)  │
│ Cycle detect │ At registration  │ None (runtime)   │
│ Impact scope │ Per instance     │ Full table       │
│ Latency      │ ms to seconds    │ minutes to hours │
│ Visualization│ Built-in         │ External tools   │
│ Tracing      │ Built-in         │ External logs    │
└──────────────┴──────────────────┴──────────────────┘

┌──────────────┬──────────────────┬──────────────────┐
│ Feature      │ coomia-dip        │ Spreadsheets     │
├──────────────┼──────────────────┼──────────────────┤
│ Scale        │ Millions objects │ Thousands cells  │
│ Concurrency  │ Supported        │ Not supported    │
│ Persistence  │ Automatic        │ Manual save      │
│ Access ctrl  │ Property-level   │ File-level       │
│ Versioning   │ Schema versioned │ None             │
│ API access   │ Native           │ Requires export  │
└──────────────┴──────────────────┴──────────────────┘

coomia-dip derived property DAG is essentially:
  "Enterprise-grade spreadsheet formula engine"
  + million-scale objects
  + multi-user concurrency
  + complete audit and tracing

#Key Takeaways

The DAG is the core data structure for cascade computation — it precisely expresses dependencies between properties, guarantees correct computation order, and is the critical upgrade from "individual computed properties" to "computed property networks."
Topological sort + parallelization = correct and efficient — Kahn's algorithm provides the correct order, same-level node parallelization provides linear speedup, and together they solve both correctness and performance requirements.
Circular dependencies must be caught at registration time — discovering cycles at runtime means system crash. DFS three-color marking detects cycles globally in O(V+E) time, catching problems at design time.
Precise impact analysis avoids wasteful computation — by crossing the schema dimension (DAG paths) with the instance dimension (relation chains), exactly the right properties and objects are targeted for recomputation.
Failure handling determines consistency guarantees — full rollback (strong consistency), stale marking (eventual consistency), partial commit + compensation (hybrid) suit different business scenarios.

#Next Article

The next article S4-09 Schema Change Management discusses Ontology Schema version control — how to safely migrate when ObjectTypes need new properties, type changes, or field deletions without downtime, how to handle backward compatibility, and how to auto-generate data migration scripts.

#ontology #derived-property #dag #topological-sort #cycle-detection #cascade-recomputation #impact-analysis #graph-algorithm