wiki_research

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

conjunctive_query_acyclic (1013B)

      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_join], 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 See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic]
     21 
     22 Up: [conjunctive_query]
     23 
     24 Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic