Finalized:Sunday, December 4, 2016
Author(s):Khamis, M. A., H. Q. Ngo, C. Re, and A. Rudra
We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes classical and recent worst-case algorithmic results on computing joins. In addition, we use our framework and the same algorithm to show a series of what are colloquially known as beyond worst-case results. The framework allows us to prove results for data stored in BTrees, multidimensional data structures, and even multiple indices per table. A key idea in our framework is formalizing the inference one does with an index as a type of geometric resolution, transforming the algorithmic problem of computing joins to a geometric problem. Our notion of geometric resolution can be viewed as a geometric analog of logical resolution. In addition to the geometry and logic connections, our algorithm can also be thought of as backtracking search with memoization.
Khamis, M. A., H. Q. Ngo, C. Re, and A. Rudra, 2016: Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems, 41, 22, doi:10.1145/2967101.This material is based upon work supported by the National Science Foundation under Grant No. 1343760. Opinions, findings, conclusions or recommendations expressed are those of the authors and do not reflect the views of the NSF.