Query Significance in Databases via Randomizations

Markus Ojala, Gemma C. Garriga, Aristides Gionis, Heikki MannilaarXiv 2009 · arXiv

Abstract

In exploratory data analysis, distinguishing meaningful patterns from random artifacts is a significant challenge, especially in complex multi-relational databases. This paper introduces a framework for assessing query significance using randomization techniques. By selectively shuffling data while preserving key structural properties, the authors provide a method to pinpoint the specific relationships driving observed results.

Introduction

When a data scientist discovers an interesting correlation—such as a specific age group preferring a certain movie genre—the immediate question is whether this pattern is "real" or a fluke of the data's structure. Traditional statistical tests often struggle with the complex joins and interdependencies of relational databases. This paper addresses the need for a robust definition of "significance" in highly structured data environments.

Methodology: Relational Permutation Tests

The authors propose using permutation tests adapted for relational models. Instead of analytical formulas, they generate a "null distribution" by shuffling the data and observing how frequently the query produces the original result by chance.

Randomization Strategies

A key innovation is the use of different randomization strategies to isolate specific effects:

  1. Swap Randomization: This method shuffles entries in a binary matrix while keeping row and column sums constant. This preserves the "popularity" of entities (e.g., a director's total movie count) but changes their specific connections.
  2. Row/Column Permutation: Reassigns labels to rows or columns.
  3. Join Randomization: Randomizes the identity relation between tables to test the significance of specific entity pairings.
Illustration of swap randomization, which preserves row and column sums while shuffling connections.

The process involves randomizing a target table $k$ times, re-running the query, and calculating an empirical p-value based on the distribution of results.

Key Insights: Localization and Structure

The framework reveals that significance is often "localized." A query result might be significant when randomizing Table A but not Table B, indicating that the pattern's source lies within the structure of Table B.

Furthermore, the authors emphasize that preserving structural properties like row/column sums is vital. Failing to do so can lead to misidentifying simple power-law distributions as meaningful correlations. The significance of a query is fundamentally linked to the distribution of paths between entities in the database graph.

A bipartite graph representation showing paths from movie genres to viewer ages, illustrating how connectivity influences query results.

Experimental Results

The approach was validated using both synthetic and real-world datasets (MovieLens).

  • Gender and Genre: The hypothesis that men and women watch different movie types was highly significant ($p < 0.001$). Men favored Action and Sci-Fi, while women preferred Romance and Drama.
  • Age and Genre: Results were more nuanced. While age distributions for "Western" or "Romance" were significant, other genres' age patterns were merely artifacts of the general population's age distribution.
  • Performance: The randomization methods proved efficient, typically taking only seconds per sample, making them suitable for interactive analysis.

Conclusion and Future Work

While the framework provides a powerful tool for data exploration, the authors note that the choice of randomization method can influence the resulting p-value. Future research aims to develop methods for combining p-values from multiple randomizations and scaling the approach to larger, more complex schemas.

Summary updated

Abstract

Many sorts of structured data are commonly stored in a multi-relational format of interrelated tables. Under this relational model, exploratory data analysis can be done by using relational queries. As an example, in the Internet Movie Database (IMDb) a query can be used to check whether the average rank of action movies is higher than the average rank of drama movies. We consider the problem of assessing whether the results returned by such a query are statistically significant or just a random artifact of the structure in the data. Our approach is based on randomizing the tables occurring in the queries and repeating the original query on the randomized tables. It turns out that there is no unique way of randomizing in multi-relational data. We propose several randomization techniques, study their properties, and show how to find out which queries or hypotheses about our data result in statistically significant information. We give results on real and generated data and show how the significance of some queries vary between different randomizations.
BibTeX
@misc{ojala2009query,
  author = {Markus Ojala and Gemma C. Garriga and Aristides Gionis and Heikki Mannila},
  title = {{Query Significance in Databases via Randomizations}},
  year = {2009},
  eprint = {0906.5485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0906.5485},
}
Figure