Database Exploration Using Join Paths

Complex database schemas are challenging to explore and query, due to the exponentially many sequences of join edges in the schema graph, not all of which result in valid join paths. The problem becomes even more difficult when tables exhibit structural heterogeneity, i.e., different join paths are meaningful for different subsets of tuples in the same table. In this paper, we propose effective ways to identify meaningful join paths in complex schemas, and to compute the probability with which different destination tables are reached via join paths from a given source table.