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.
[1] PEARL J. Causality:Models, Reasoning, and Inference[M]. New York:Cambridge University Press, 2000:207-214. [2] HALPERN J Y, PEARL J. Causes and explanations:a structural-model approach, part Ⅰ:causes[J]. British Journal for the Philosophy of Science, 2005, 56(4):843-887. [3] DAN O, HUANG J. Using OBDDs for efficient query evaluation on probabilistic databases[C]//SUM 2008:Proceedings of the 2008 International Conference on Scalable Uncertainty Management. Berlin:Springer, 2008:326-340. [4] DAN O, HUANG J. Secondary-storage confidence computation for conjunctive queries with inequalities[C]//SIGMOD 2009:Proceedings of the 2009 International Conference on Management of Data. New York:ACM, 2009:389-402. [5] FREIRE C, GATTERBAUER W, IMMERMAN N, et al. The complexity of resilience and responsibility for self-join-free conjunctive queries[J]. Proceedings of the VLDB Endowment, 2015, 9(3):180-191. [6] MELIOU A, GATTERBAUER W, MOORE K F, et al. The complexity of causality and responsibility for query answers and non-answers[J]. Proceedings of the VLDB Endowment, 2010, 4(1):34-45. [7] SARMA A D, BENJELLOUN O, HALEVY A, et al. Working models for uncertain data[C]//ICDE 2006:Proceedings of the 2006 International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2006:7. [8] DALVI N, SUCIU D. Efficient query evaluation on probabilistic databases[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2007, 16(4):523-544. [9] 余萝,覃飙,刘勇.概率数据库中图类型的不等式查询语句的置信度计算[J].小型微型计算机系统,2015,36(5):996-1001.(YU L, QIN B, LIU Y. Confidence computation for queries with inequality graph in probabilistic databases[J]. Journal of Chinese Computer Systems, 2015, 36(5):996-1001.) [10] GALLES D, PEARL J. Axioms of causal relevance[J]. Artificial Intelligence, 1997, 97(1/2):9-43. [11] HALPERN J Y. Axiomatizing causal reasoning[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. San Francisco:Morgan Kaufmann, 1998:202-210. [12] CHOCKLER H, HALPERN J Y. Responsibility and blame:a structural-model approach[J]. Journal of Artificial Intelligence Research, 2004, 22(1):93-115. [13] FORD L R, FULKERSON D R. Constructing maximal dynamic flows from static flows[J]. Operations Research, 1958, 6(3):419-433. [14] EDMONDS J, KARP R M. Theoretical improvements in algorithmic efficiency for network flow problems[J]. Journal of the ACM, 1972, 19(2):248-264. [15] SKIENA S. Dijkstra's algorithm[M]//Implementing Discrete Mathematics:Combinatorics and Graph Theory with Mathematica. Reading, MA:Addison-Wesley, 1990:225-227.
2018, Vol. 38 
