query_resilience (1662B)
1 # Resilience 2 3 The *resilience* of a [query] Q on a [database] D is the minimal number of [tuples] to be deleted from D so that Q is not satisfied: 4 - can be 0 if Q is false on D 5 - can be infinity if Q is true on every [subdatabase] of D 6 7 Can be posed in [set_semantics] or [bag_semantics] 8 - There is a difference between the two 9 - cf [makhija2022unified] Table 1 10 - even for [SJFCQs] 11 12 [Academic_papers]: 13 - ideas of [network_flow] in [meliou2010complexity] 14 - introduced in [freire2015complexity] 15 - gives a [dichotomy] for [SJFCQs] 16 - their notion of [triads] is called [active_triads] in [makhija2022unified] 17 - [freire2019new] for [CQs] with [self_joins] 18 - [qin2022resilience]: for [SJFCQs] with [query_inequalities] 19 - [makhija2022unified] with [neha] 20 - also talks about [causal_responsibility] 21 - results on [SJFCQs] in [bag_semantics]: 22 - resilience is [PTIME] for [linear_queries] 23 - resilience is [NP_complete] for all other [SJFCQs], i.e., queries with [triads] 24 - for [SJFCQs] in [set_semantics] 25 - resilience is [NP_complete] for [SJFCQs] with an [active_triad] 26 - resilience is [PTIME] otherwise 27 - [bodirsky2023complexity]: connections to [CSPs] ([resilience_csp]) 28 - only in [bag_semantics] 29 - gives a [dichotomy] for [2RPQs] 30 - [amarilli2025resilience], for [RPQs] 31 32 Notions: 33 - [triad], [active_triad] 34 - [join_path] 35 - linearizable query 36 37 Tools: 38 - [integer_linear_programming] 39 - [vertex_cover] 40 41 Research directions: 42 - [query_resilience_provenance] 43 - [reliability_rpq] 44 - [reliability_rpq_vertices] 45 46 Up: [database_theory] 47 48 See also: [pqe], [minimal_witness] 49 50 Aliases: database resilience, resilience databases, resilience database