现实世界中实体间的关系可以图数据来表示。图算法用来对图数据进行数据挖掘。数据图处理系统提供了接口给用户实现图算法。数据图处理系统执行算法时普遍采用确定性的并行执行模型,这会导致算法执行并行度低和系统可扩展性差的问题。非确定性的并行执行模型没有这些缺点并能提升系统性能,但是由于当前研究没有说明非确定性并行执行模型的正确性和适用范围,使得它很少被使用。本文针对非确定性并行执行模型因为缺少理论支持而应用不足的问题,给出并论证了非确定性并行执行模型的正确性、适用范围和性能的相关理论。数据图处理系统中非确定性并行执行模型的研究,首先对图处理系统的一般运行过程进行建模,并对算法执行提出保证数据读写原子性和保证数据访问一致性两个限制条件。在系统模型和限制条件的基础上分析不同算法发生数据竞争后可能的执行过程和结果,证明图路径遍历算法能修正读写竞争和写写竞争,图固定点遍历算法能修正读写竞争,然后以外部确定性调度和SSSP算法为典型,通过计算算法在外部确定性调度执行模型和非确定性执行模型下收敛速度的期望,说明算法在不同执行模型下迭代次数大致相同。实验在一个典型的数据图处理系统GraphChi上实现了非确定性并行执行模型,并用标准的图算法和图数据进行了测试,通过将非确定性并行执行模型与确定性并行执行模型下的实验结果进行比较,证明在非确定性并行执行模型下算法迭代次数变化不大,运行时间大幅减少(利用体系结构保证原子性的实现方案性能最好,最多能减少70%的运行时间)。算法运行时间随着处理单元增加而递减,说明非确定性并行执行模型具有良好的可扩展性。实验还对不同执行模型下图固定点遍历算法的输出结果进行对比和分析,说明非确定性并行执行模型下图固定点遍历算法结果的正确性。