The hardness of resilience for nested aggregation query
Dongjing Miao, Jiguo Yu, Zhipeng Cai · Theoretical Computer Science · 2019
Resilience problem is defined on a database d, given a boolean query q where q(d) is initially true, and an integer k, it is to find the tuple set d′ of smallest size such that the query result q(d∖d′) becomes false. As a potential explanation of a specified query, resilience plays a fundamental and important role in query explanation, database debugging and error tracing. Complexity results of resilience decision on relational algebraic queries have been studied previously. In this paper, we investigate the resilience decision problem on aggregation queries. New results on the hardness are provided. We show that, this problem is polynomially intractable on nested COUNT and SUM query both under data complexity and parametric complexity, and even it is NP-hard to approximate it within a constant ratio under the active domain constraint.