@inproceedings{d1789a042af340b48685dd0e88fb6e0b,
title = "Joins via Geometric Resolutions: Worst-case and beyond",
abstract = "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.",
keywords = "Beyond worst-case analysis, Bounded-width join queries, Indices, Relational join, Resolution",
author = "Khamis, \{Mahmoud Abo\} and Ngo, \{Hung Q.\} and Christopher R{\'e} and Atri Rudra",
note = "Publisher Copyright: {\textcopyright} 2015 ACM.; 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2015 ; Conference date: 31-05-2015 Through 04-06-2015",
year = "2015",
month = may,
day = "20",
doi = "10.1145/2745754.2745776",
language = "English",
series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
publisher = "Association for Computing Machinery ",
pages = "213--228",
booktitle = "PODS 2015 - Proceedings of the 34th ACM Symposium on Principles of Database Systems",
address = "United States",
}