wiki_research

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

minimal_witness (618B)

      1 # Minimal witness
      2 
      3 #todo "minimum witness"?
      4 
      5 Find the smallest subset of a [relational_database] that satisfies a [query]
      6 - formally, for query Q and database D, find smallest subset D' of D giving the same result
      7 - [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset
      8 
      9 easy for [conjunctive_query_full], so hardness comes from [projection]
     10 
     11 - [miao2019explaining], with [ptime] algorithm for a specific tuple
     12 - [hu2023finding], [best_paper_award] at [icdt_2024]
     13 
     14 Up: [database_theory]
     15 
     16 See also: [query_resilience]