wiki_research

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

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