wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

query_resilience (1850B)

      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 By [query_class]:
     13 - [query_resilience_sjfcq]
     14 - [query_resilience_cq]
     15 - [query_resilience_ucq]
     16 - [query_resilience_rpq]
     17 
     18 [Academic_papers]:
     19 - ideas of [network_flow] in [meliou2010complexity]
     20 - introduced in [freire2015complexity]
     21   - gives a [dichotomy] for [SJFCQs]
     22   - their notion of [triads] is called [active_triads] in [makhija2022unified]
     23 - [freire2019new] for [CQs] with [self_joins]
     24 - [qin2022resilience]: for [SJFCQs] with [query_inequalities]
     25 - [makhija2022unified] with [neha]
     26   - also talks about [causal_responsibility]
     27   - results on [SJFCQs] in [bag_semantics]:
     28     - resilience is [PTIME] for [linear_queries]
     29     - resilience is [NP_complete] for all other [SJFCQs], i.e., queries with [triads]
     30   - for [SJFCQs] in [set_semantics]
     31     - resilience is [NP_complete] for [SJFCQs] with an [active_triad]
     32     - resilience is [PTIME] otherwise
     33 - [bodirsky2023complexity]: connections to [CSPs] ([resilience_csp])
     34   - only in [bag_semantics]
     35   - gives a [dichotomy] for [2RPQs]
     36 - [amarilli2025resilience], for [RPQs]
     37 
     38 Notions:
     39 - [triad], [active_triad]
     40 - [join_path]
     41 - linearizable query
     42 
     43 Tools:
     44 - [integer_linear_programming]
     45 - [vertex_cover]
     46 
     47 Research directions:
     48 - [query_resilience_provenance]
     49 - [reliability_rpq]
     50   - [reliability_rpq_vertices]
     51 
     52 Generalization:
     53 
     54 - [deletion_propagation_with_source_side_effects]
     55 
     56 Up: [database_theory]
     57 
     58 See also: [pqe], [minimal_witness]
     59 
     60 Aliases: database resilience, resilience databases, resilience database