Approximate Summaries for Why and Why-not Provenance (Extended Version)

Seokki Lee, Bertram Ludäscher, Boris Glavic

TL;DR

This paper introduces a novel approach to summarize "why" and "why-not" provenance, which explains how query results are derived or why they are missing. By using pattern-based summarization and integrating sampling techniques, the authors achieve scalability for large datasets while providing comprehensive and meaningful explanations, overcoming the limitations of existing methods that are either too slow or incomplete.

What Problem Does This Paper Address?

When analyzing data, it's crucial to understand not just how a result was obtained (why provenance) but also why a particular result is missing (why-not provenance). While these provenance techniques have been studied, they often generate massive amounts of data, making them computationally expensive and difficult for users to interpret. Existing solutions either provide complete but overwhelming explanations (all-derivations) or concise but potentially incomplete ones (single-derivation). This paper tackles the challenge of creating provenance summaries that are both scalable and informative, offering a middle ground that balances conciseness, completeness, and informativeness.

Methods

The core of the paper's contribution lies in its approximate summarization technique for provenance. Instead of materializing the entire provenance graph, the authors propose using pattern nodes to represent sets of derivations concisely. These patterns act as generalized explanations with placeholders.

Key methodological components include:

  • Sampling Provenance: To handle the massive scale of why-not provenance, the authors integrate sampling directly into the provenance capture process. This allows them to generate a representative sample of derivations without materializing the full provenance.
  • Pattern Candidate Generation: They employ a Lowest Common Ancestor (LCA)-based approach to generate candidate patterns from the sampled derivations. This method efficiently produces patterns that can match at least two derivations, significantly reducing the number of patterns compared to enumerating all possibilities.
  • Quality Metrics: The authors define metrics for completeness (fraction of provenance covered by a summary) and informativeness (new information provided by a pattern beyond the user's query). They then define a score based on the harmonic mean of these metrics.
  • Top-k Summarization: A best-first search algorithm is used to find the top-k patterns that maximize the defined score, balancing conciseness and informativeness. This process leverages lower and upper bounds on completeness to prune the search space efficiently.

Datasets

The paper evaluates their approach using a combination of real-world and synthetic datasets:

  • TPC-H: A standard benchmark for database systems.
  • New York State (NYS) license dataset: Approximately 16 million tuples.
  • Movie dataset: Approximately 26 million tuples.
  • Chicago crime dataset: Approximately 6 million tuples.
  • DBLP co-author graph: Extracted from DBLP.
  • Synthetic queries: Generated to test various complexities (e.g., chain and star query structures, varying numbers of joins and unbound variables).

Key Insights and Ideas

  • Provenance Summarization is Crucial for Usability: The sheer volume of provenance data makes it impractical for human analysis. Summarization is not just a performance optimization but a necessity for making provenance useful.
  • Sampling is Key to Scalability: Directly integrating sampling into provenance capture is essential for handling the exponential blow-up of why-not provenance, making it feasible to process large datasets.
  • Pattern-Based Summaries Offer a Sweet Spot: Using patterns with placeholders allows for concise representation of large sets of derivations, striking a balance between the completeness of all-derivations and the conciseness of single-derivation approaches.
  • LCA for Efficient Pattern Generation: The LCA method provides a practical way to generate a manageable set of relevant patterns from sampled data, avoiding the combinatorial explosion of generating all possible patterns.
  • Quality Metrics Guide Summary Selection: Defining clear metrics for completeness and informativeness allows for a principled way to select the "best" summaries, ensuring they are both representative and insightful.

Key Results

  • Performance: The proposed summarization approach significantly outperforms existing all-derivations methods (like Artemis) by orders of magnitude, especially on larger datasets. It also shows competitive performance against single-derivation approaches, often providing more comprehensive explanations.
  • Scalability: The system scales well with increasing dataset sizes and provenance sizes, handling up to 10^80 derivations in some cases. The runtime is generally linear with respect to the sample size and the number of patterns.
  • Quality: The generated summaries are shown to be comprehensive, achieving high completeness scores (up to 100% for why provenance and ~75% for why-not provenance in many cases). The quality metric error due to sampling is low (typically below 2%).
  • Meaningful Summaries: The system produces summaries that are more informative than those from Artemis, often identifying patterns that cover a significant portion of the provenance with more specific details.

Limitations and Future Work

  • Completeness of Sampling: While the sampling is designed to be unbiased with high probability, it's still an approximation. The paper acknowledges that for some complex queries with very large domains and many unbound variables, achieving perfect completeness might be challenging.
  • Pattern Generation Heuristics: The LCA method is a heuristic for pattern generation, meaning it might not find all possible optimal patterns.
  • Future Work: The authors suggest investigating how to incorporate additional information, such as integrity constraints, into the summarization process to further enhance the quality and informativeness of the generated summaries. They also mention the potential for further optimization of the summarization algorithm.

Summary updated

Abstract

Why and why-not provenance have been studied extensively in recent years. However, why-not provenance, and to a lesser degree why provenance, can be very large resulting in severe scalability and usability challenges. In this paper, we introduce a novel approximate summarization technique for provenance which overcomes these challenges. Our approach uses patterns to encode (why-not) provenance concisely. We develop techniques for efficiently computing provenance summaries balancing informativeness, conciseness, and completeness. To achieve scalability, we integrate sampling techniques into provenance capture and summarization. Our approach is the first to scale to large datasets and to generate comprehensive and meaningful summaries.
BibTeX
@article{lee2020approximate,
  author = {Seokki Lee and Bertram Ludäscher and Boris Glavic},
  title = {{Approximate Summaries for Why and Why-not Provenance (Extended Version)}},
  journal = {Proc. VLDB Endow.},
  year = {2020},
  doi = {10.14778/3380750.3380760},
}
Figure