Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 1893-1897.DOI: 10.11772/j.issn.1001-9081.2018010078

Previous Articles     Next Articles

Resilience computation for queries with inequalities in databases

LIN Jie, QIN Biao, QIN Xiongpai   

  1. School of Information, Renmin University of China, Beijing 100872, China
  • Received:2018-01-10 Revised:2018-03-28 Online:2018-07-10 Published:2018-07-12
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61472425).

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

林杰, 覃飙, 覃雄派   

  1. 中国人民大学 信息学院, 北京 100872
  • 通讯作者: 覃飙
  • 作者简介:林杰(1991-),男,河北石家庄人,硕士研究生,主要研究方向:机器学习、信息检索;覃飙(1972-),男,湖北江陵人,副教授,博士,CCF会员,主要研究方向:数据库、大数据处理;覃雄派(1971-),男(壮族),广西德保人,讲师,博士,CCF会员,主要研究方向:数据库、大数据处理。
  • 基金资助:
    国家自然科学基金资助项目(61472425)。

Abstract: 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.

Key words: causality, resilience, conjunctive query with inequality, lineage expression, lineage graph

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

关键词: 因果关系, resilience, 不等式查询语句, 溯源表达式, 溯源图

CLC Number: