wiki_research

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

counting_cqs (959B)

      1 # Counting CQ results
      2 
      3 Given a [conjunctive_query] and a [database_instance], count the number of answers.
      4 
      5 Can be studied in [data_complexity], [query_complexity], or [combined_complexity]. Of course in [data_complexity] it is always [ptime].
      6 
      7 Results:
      8 
      9 - Exact counting is [sharpp_complete] in [query_complexity]
     10 - For [acyclic_CQs]: [ptime] with counting variant of [Yannakakis's_algorithm]
     11 - For bounded [generalized_hypertree_width]:
     12   - [arenas2021when]: approximate counting [fpras] for bounded [generalized_hypertree_width]generalized_hypertree_width
     13     - extended by [vanbremen2023probabilistic]
     14   - [self-joins] can be a problem
     15 
     16 Related task: [sampling_cqs]
     17 
     18 [academic_papers]:
     19 - [chen2023counting], journal version of [chen2015trichotomy] and [greco2014counting]
     20 - context explained in https://dbt.zulipchat.com/#narrow/stream/413229-Paper-announcements/topic/Papers.20about.20counting.20CQs
     21 
     22 Up: [counting_query_answers] for [conjunctive_query]