(optimal) Database delete/insert sequence

dependency-relationship.dot

digraph deps {
  A -> B;
  B -> C;
  A -> D;
  E -> D;
}

fk.lp

Minimize
  a_i + b_i + c_i + d_i + e_i
Subject To
  c01: a_d - b_d <= -1
  c02: b_d - c_d <= -1
  c03: a_d - d_d <= -1
  c04: e_d - d_d <= -1
  c05: c_d - c_i <= -1
  c06: b_d - b_i <= -1
  c07: c_i - b_i <= -1
  c08: b_i - a_i <= -1
  c09: d_d - d_i <= -1
  c10: d_i - a_i <= -1
  c11: e_d - e_i <= -1
  c12: d_i - e_i <= -1
Bounds
  1 <= a_d <= 10
  1 <= b_d <= 10
  1 <= c_d <= 10
  1 <= d_d <= 10
  1 <= e_d <= 10
  1 <= a_i <= 10
  1 <= b_i <= 10
  1 <= c_i <= 10
  1 <= d_i <= 10
  1 <= e_i <= 10
Integer
  a_d
  b_d
  c_d
  d_d
  e_d
  c_i
  b_i
  a_i
  d_i
  e_i
End

output.txt

Problem:
Rows:       12
Columns:    10 (10 integer, 0 binary)
Non-zeros:  24
Status:     INTEGER OPTIMAL
Objective:  obj = 22 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 c01                        -1                          -1
     2 c02                        -1                          -1
     3 c03                        -1                          -1
     4 c04                        -1                          -1
     5 c05                        -1                          -1
     6 c06                        -3                          -1
     7 c07                        -1                          -1
     8 c08                        -1                          -1
     9 c09                        -1                          -1
    10 c10                        -3                          -1
    11 c11                        -3                          -1
    12 c12                        -1                          -1

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 a_i          *              6             1            10
     2 b_i          *              5             1            10
     3 c_i          *              4             1            10
     4 d_i          *              3             1            10
     5 e_i          *              4             1            10
     6 a_d          *              1             1            10
     7 b_d          *              2             1            10
     8 c_d          *              3             1            10
     9 d_d          *              2             1            10
    10 e_d          *              1             1            10

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

run.sh

#/bin/bash

# dot -Tpng dependency-relationship.dot | display -
glpsol --cpxlp fk.lp -o output.txt