TupleRank and implicit relationship discovery in relational databases

Google's successful PageRank brings to the Web an order that well reflects the relative importance of Web pages. Inspired by PageRank, we propose a similar scheme called TupleRank for ranking tuples in a relational database. Database tuples naturally relate to each other through referential integrity constraints declared in the schema. However, such constraints cannot capture more general relationships such as similarity. Furthermore, relationships determined statically from the database schema do not reflect actual query patterns that arise at runtime. To address these deficiencies of static TupleRank, we introduce the notion of query-driven TupleRank. We develop techniques to compute query-driven TupleRank accurately and efficiently with low space requirement. We further augment query-driven TupleRank so that it can better utilize the access frequency information collected from the workload. Preliminary experiment results demonstrate that TupleRank is both informative and intuitive, and they confirm the advantages of query-driven TupleRank over static TupleRank. © Springer-Verlag Berlin Heidelberg 2003.

Duke Scholars

Author Jun Yang Computer Science