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]