Holes in Joins
Jarek Gryz and Dongming Liang
Technical Report CS-2001-03
York University
June 18, 2001
Abstract
A join of two relations in real databases is usually much smaller than their cartesian product. This means that most of the combinations of tuples in the crossproduct of the respective relations do not appear together in the join result. We characterize these combinations as ranges of attributes that do not appear together. We sketch an algorithm for finding such combinations and present experimental results from two real data sets. We then explore potential applications of this knowledge to query optimization. By modeling empty joins as materialized views, we show how knowledge of these regions can be used to improve query performance.
Download paper in PDF format.
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.