wiki_research

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

query_minimization (634B)


      1 # Query minimization
      2 
      3 The [function_problem], given a [query] Q in a [query_language], of computing a [query] Q' (usually in the same language) which is [query_equivalent] to Q but is "smaller"
      4 - usually smaller number of [atoms]
      5 - but can be another measure, e.g., the [treewidth]
      6 
      7 This problem can be turned into a [decision_problem] by asking, given a [query] Q and integer k, whether there exists a query which is [query_equivalent] to Q but has at most k atoms
      8 
      9 For various [query_languages]:
     10 - [CQ_minimization]
     11   - cf [homomorphism] / [core]
     12 - [CRPQ_minimization]
     13 - [UCRPQ_minimization]
     14 
     15 Up: [query_problems]
     16 
     17 See also: [core]