数据库中不等式查询语句的resilience计算
来源：计算机应用杂志2018年第7期北京时间：
作者：林杰, 覃飙, 覃雄派
单位：中国人民大学 信息学院, 北京 100872
摘要：针对数据库中不等式连接查询的因果关系问题，引入并实现了resilience计算，并且为了降低其在路径类型不等式连接查询中计算的时间复杂度，提出了求解resilience的动态规划（DPResi）算法。首先，根据路径类型不等式连接查询的特点及最大流最小割原理，实现了多项式时间复杂度的Min-Cut算法；然后通过将带有不等式布尔连接查询语句的溯源表达式编辑为溯源图，进而将resilience求解问题转换为溯源图中最短距离的计算问题，并结合溯源图的包含关系与最优子结构性质，运用动态规划的思想实现了线性时间复杂度的DPResi算法。在TPC-H数据集上进行了大量实验，实验结果表明，与Min-Cut算法相比，DPResi算法极大地提高了resilience计算的效率，并具有较好的扩展性。
关键词：因果关系,resilience,不等式查询语句,溯源表达式,溯源图
基金资助：国家自然科学基金资助项目（61472425）。
