DP-Counter Analytics

In the literature mainly two variants of dynamic programming for constructing join trees are described. We show analytically and experimentally that the runtime behaviors of those two variants differ vastly for different query graphs. The query graphs we consider are chain, cycle, star, and clique. More specifically, one of the variants is highly superior for chain and cycle queries whereas the other is highly superior for star and cliques queries. This motivates us to derive an optimal algorithm which is --- apart from a small overhead --- superior to all algorithms in all cases