Semantically Acyclic Conjunctive Queries under Functional Dependencies
Diego Figueira · 2016
The evaluation problem for Conjunctive Queries (CQ) is known to be NP-complete in combined complexity and W[1]-hard in parameterized complexity. However, acyclic CQs and CQs of bounded tree-width can be evaluated in polynomial time in combined complexity and they are fixed-parameter tractable.