Algorithmically evaluates conjunctive queries' runtimes and optimality for database querying, suggesting improvements.
One of the most celebrated results for evaluating conjunctive queries (CQs) is the Yannakakis algorithm [24] proposed in 1981. It is known that free-connex CQs can be evaluated in O(N + OUT) time, where N is the input size of the database and OUT is the output size of the query result. This is already output-optimal. However, only an upper bound O(N ·OUT) on the runtime is known for the remaining acyclic but non-freeconnex CQs. Alternatively, one can convert a non-freeconnex CQ into a free-connex one using tree decomposition techniques, and then run the Yannakakis algorithm. However, none of them is known to be output-optimal.
No takes yet. Share an insight, caveat, or question.
Hu et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: