conjunctive_query_acyclic (1099B)
1 # Acyclic CQs 2 3 Can be evaluated by [yannakakis_algorithm] following a [join_tree] 4 5 - [acyclic_free_connex] 6 7 the evaluation problem is in the complexity class [logcfl], and the the complexity is in O(databaseĆquery + output) 8 9 We can test in linear time if a [hypergraph] is acyclic and if so build the [join_tree]: [GYO_algorithm] 10 - not so obvious to understand where the [linear_time] claim comes from... 11 12 For Boolean queries, even with [self_joins], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection]) 13 14 Special case: [conjunctive_query_hierarchical] 15 16 Testing if a CQ is acyclic ([elimination_order]): 17 18 - while there is a vertex v whose [closed_neighborhood] (includes v itself) is included in some edge, then delete the vertex 19 20 Special case: 21 22 - [acyclic_SJFCQ] 23 24 See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic] 25 26 Up: [conjunctive_query], [query_acyclic] 27 28 Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query