wiki_research

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

conjunctive_query_acyclic (759B)

      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 
     11 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])
     12 
     13 Special case: [conjunctive_query_hierarchical]
     14 
     15 See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic]
     16 
     17 Up: [conjunctive_query]
     18 
     19 Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic