Efficient Relational Joins with Arithmetic Constraints on Multiple Attributes

We introduce and study a new class of queries that we refer to as ACMA (arithmetic constraints on multiple attributes) queries. Such combinatorial queries require the simultaneous satisfaction of arithmetic constraints on three or more attributes from different relations, and thus often involve expensive multi-join operations. Building on techniques from constraint programming, we develop preprocessing methods, algorithms, and a new constrained join operator that allow ACMA queries to be evaluated efficiently within a conventional relational database engine. We present the results of a careful performance evaluation of both our new approach and the conventional nested-loop join algorithm. Measurements of tuples read, intermediate tuples generated, and execution time shows that our approach achieves superior performance for ACMA joins. 1