wiki_research

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

maximal_under_approximation (568B)

      1 # Maximal under approximation
      2 
      3 A *maximal under approximation* with property P is an [under_approximation] Q' of Q having property P such that any query [query_contained] in Q having property P is also [query_contained] in Q'
      4 
      5 For [CQs], for P being "having treewidth at most k", maximal under approximations exist, cf [barcelo2014efficient]. Connection to [semantic_treewidth]: a [CQ] has semantic treewidth at most k iff it is [query_equivalent] to its maximal under approximation for [treewidth] k
      6 
      7 Up: [under_approximation]
      8 
      9 See also: [minimal_over_approximation]