wiki_research

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

bag_cq_containment (328B)

      1 # Bag cq containment
      2 
      3 [computational_complexity] of [query_containment] for [CQs] under [bag_semantics] is [open_problem]
      4 
      5 - introduced in [chaudhuri1993optimization]
      6 - withdrawn claim of [Pi_2_p]-hardness
      7 - only known [lower_bound] is [NP_hard]
      8 
      9 Recent discussion: [marcinkowski2025bag]
     10 
     11 Up: [containment_bag_semantics], [CQs]