wiki_research

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

enumeration_ucqs (946B)


      1 # Enumeration for UCQs
      2 
      3 - Union of tractable [CQs] is tractable ([linear_preprocessing_constant_delay])
      4 - A union where every [CQ] is intractable may be tractable! [carmeli2021enumeration]
      5   - notion of [union_extension]
      6     - covers all known tractable cases
      7     - for union of two intractable [CQs], union extensions are known to (conditionally)
      8     cover all tractable queries for disjunctions of two queries
      9       - assumes hypothesis on finding [4clique]
     10     - case of a union of a tractable CQ and an intractable CQ discussed in [bringmann2022unbalanced]
     11 
     12 for [linear_preprocessing_constant_delay_constant_memory], not well-known, cf [carmeli2021enumeration] Section 6.3
     13 - in particular [cheaters_lemma]
     14 
     15 important: it is necessary to look at [body_homomorphism] because the [free_variables] may not be the same
     16 
     17 open question: [enumeration_ucqs_classifying]
     18 
     19 Up: [enumeration] for [union_of_conjunctive_query]
     20 
     21 See also: [enumeration_cqs]