Formal approaches of evaluating join queries over distributed systems with optimality guarantees.

Big data and scalability have been buzzwords in recent years. The trend is to use a set of clusters to
perform a computation over massive amounts of data. These new large-scale systems call for
innovative ways to understand the complexity of its computation in which case we can often ignore
the I/O factor by assuming that the data is available in the local memories of the clusters performing
the computation. At the same time, the complexity of a distributed computation often incurs other
factors that are not relevant to the centralized setting such as the communication cost and the
number of rounds of communication. From a database perspective, it is essential to understand how
to evaluate queries over such large-scale systems efficiently. Out of the classical set of operators,
join is considered the most challenging because of its unique nature that requires data from different
tables; and in a distributed setting, it is more likely to have such data located on different clusters,
so the data needs to be sent from one server to another. Therefore, understanding the complexity of
join in a distributed setting in terms of the communication cost is essential for having efficient largescale systems. In this proposal, we are interested in developing distributed join algorithms that
minimize the communication cost of the evaluation while keeping the number of communication
rounds constant. In particular, we are interested in providing optimality guarantees for our
algorithms