Complexity

• Factors

  • NA = number of attributes
  • NC = number of constraints
  • S = total size of input constraints (?C |lhs|)
  • H = height of lattice
  • B = max. # of immediate predecessors (“branching factor”) in the lattice
  • c = cost of lub operation

• Acyclic: O((S + NCHB)c)

• General: O(NASH2Bc)

Previous slide

Next slide

Back to first slide

View graphic version