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