SQL Server cycle detection doesn't detect multiple paths correctly

[pimeys]

SQL Server and multiple cascade paths

Our original implementation of cycle detection has a problem: it only detects cycles, never multiple cascading paths correctly. By accident, all tests were green, until our introspection CI catched an issue that should validate and we can safely migrate to the database.

What are multiple cascading paths

A simple example from our current test setup demonstrates a data model that should not pass the validation:

model A {
  id     Int  @id @default(autoincrement())
  bId    Int
  b      B    @relation(fields: [bId], references: [id])
  cs     C[]
}

model B {
  id     Int  @id @default(autoincrement())
  as     A[]
  cs     C[]
}

model C {
  id     Int  @id @default(autoincrement())
  aId    Int
  bId    Int
  a      A    @relation(fields: [aId], references: [id])
  b      B    @relation(fields: [bId], references: [id])
}

Originally, our setup validated this by detecting a cycle: A.b -> B.cs -> C.a and so on. This is wrong. The actual validation error in the data model goes in two paths: C -> A -> B and C -> B.

By accident, our cycle detection algorithm validated this, but by looking into a more complex example, we see what is wrong with the current algorithm:

model order_items {
  order_id   Int
  item_id    Int
  product_id Int
  orders     orders   @relation(fields: [order_id], references: [order_id], onDelete: Cascade)
  products   products @relation(fields: [product_id], references: [product_id], onDelete: Cascade)

  @@id([order_id, item_id])
}

model orders {
  order_id      Int           @id @default(autoincrement())
  store_id      Int
  stores        stores        @relation(fields: [store_id], references: [store_id], onDelete: Cascade)
  order_items   order_items[]
}

model products {
  product_id   Int           @id @default(autoincrement())
  brand_id     Int
  order_items  order_items[]
  stocks       stocks[]
}

model stocks {
  store_id   Int
  product_id Int
  products   products @relation(fields: [product_id], references: [product_id], onDelete: Cascade)
  stores     stores   @relation(fields: [store_id], references: [store_id], onDelete: Cascade)

  @@id([store_id, product_id])
}

model stores {
  store_id   Int      @id @default(autoincrement())
  orders     orders[]
  stocks     stocks[]
}

Our current validation finds a cycle in it, as the algorithm is written:

order_items.orders → orders.stores → stores.stocks → stocks.products → products.order_items

Although when turning off the validation, SQL Server accepts the migration!

The first step is to stop jumping over back-relations and only look for @relation arguments with fields, references and (maybe implicitly) refererential actions defined. From this data model we can find several paths:

• order_items -> orders -> stores
• order_items -> products

From order_items there are no cascading paths.

• stocks -> products
• stocks -> stores

Again, no cascading paths.

From this point on we're done and we don't need to be looking into other paths.