对数据依赖关系的分析要求找出是否存在一些整数满足由等式和不等式组成的约束系统。其中的等式是从数组访问的矩阵向量表示中得到的；不等式是从循环界限中得到的。等式可以用不等式表示：等式z 可以用两个不等式：x≥y和y≥x表示。

因此，数据依赖关系问题可以被表示为寻找满足一组线性不等式的整数解，这个问题就是众所周知的整数线性规划（integer linear programming)。整数线性规划是一个NP完全问题。虽然没有已知的多项式复杂性的算法，但人们研发了多种启发式解法来解决涉及很多变量的线性规划问题。这些解法在很多情况下运行得是相当快的。遗憾的是，这样的标准启发式解法并不适合数据依赖关系分析。在数据依赖分析中，问题的难点在于如何解决很多小且简单的整数线性规划，而不是大型的复杂整数线性规划。