数据库中不等式查询语句的resilience计算

Resilience computation for queries with inequalities in databases

针对数据库中不等式连接查询的因果关系问题,引入并实现了resilience计算,并且为了降低其在路径类型不等式连接查询中计算的时间复杂度,提出了求解resilience的动态规划(DPResi)算法。首先,根据路径类型不等式连接查询的特点及最大流最小割原理,实现了多项式时间复杂度的Min-Cut算法;然后通过将带有不等式布尔连接查询语句的溯源表达式编辑为溯源图,进而将resilience求解问题转换为溯源图中最短距离的计算问题,并结合溯源图的包含关系与最优子结构性质,运用动态规划的思想实现了线性时间复杂度的DPResi算法。在TPC-H数据集上进行了大量实验,实验结果表明,与Min-Cut算法相比,DPResi算法极大地提高了resilience计算的效率,并具有较好的扩展性。

Focusing on the causality problem of conjunctive queries with inequalities in databases, the resilience computation was introduced and implemented. In order to reduce the computational time complexity in path conjunctive queries with inequalities, a Dynamic Programming for Resilience （DPResi） algorithm was proposed. Firstly, according to the properties of path conjunctive queries with inequalities and the max-flow Min-Cut theorem, the Min-Cut algorithm with polynomial time complexity was implemented. Then by compiling the lineage expression of a Boolean conjunctive query with inequality into a lineage graph, the problem of resilience was transformed into the computation of the shortest distance in lineage graph. Combining inclusion property with optimal substructure of the lineage graph, DPResi algorithm with linear time complexity was implemented by applying the idea of dynamic programming. Extensive experiments were carried out on the TPC-H datasets. The experimental results show that DPResi algorithm greatly improves the efficiency of resilience computation and has good scalability compared with Min-Cut algorithm.