semantic_acyclicity (358B)
1 # Semantic acyclicity 2 3 The [computational_problem] of deciding if [query] is [query_equivalent] to [query_acyclic], within a specific [query_class] 4 - for [UC2RPQ], cf [morvan2025homomorphism] Chapter V 5 - for [CQs], it is [NP_complete], cf [barcelo2016semantic] 6 7 Up: [computational_problem], [database_theory] 8 9 See also: [semantic_treewidth], [formula_width]