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

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

数据依赖关系分析算法由三个部分组成：

1)使用丢番图方程的理论，应用GCD( Greatest Common Divisor,最大公约数）测试来检验是否存在满足问题中所有等式的整数解。如果没有整数解，那么就不存在数据依赖关系，否则就用等式来替换其中的某些变量，从而得到较简单的不等式组。

2)使用一组简单的启发规则来处理大量的典型不等式。

3)在少数情况下，这些启发式规则可能还解决不了问题。此时，我们使用线性整数规划求解程序来解决问题。这个程序基于Fourier-Motzkin消除算法，使用了一种分支并设限的方法来求解。