IIT Database Group

header bar

Approximate Summaries for Why and Why-not Provenance




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. We introduce a novel approximate summarization technique for provenance to address these challenges. Our approach uses patterns to encode why and why-not provenance concisely. We develop techniques for efficiently computing provenance summaries that balance informativeness, conciseness, and completeness. To achieve scalability, we integrate sampling techniques into provenance capture and summarization. Our approach is the first to both scale to large datasets and to generate comprehensive and meaningful summaries.


  author = {Lee, Seokki and Lud\"ascher, Bertram and Glavic, Boris},
  journal = {Proceedings of the VLDB Endowment},
  keywords = {PUGS; Summarization; Sampling; Missing Answers; Datalog},
  longversionurl = {https://arxiv.org/pdf/2002.00084},
  projects = {PUGS},
  number = {6},
  pages = {912 - 924},
  pdfurl = {http://www.vldb.org/pvldb/vol13/p912-lee.pdf},
  title = {{Approximate Summaries for Why and Why-not Provenance}},
  venueshort = {PVLDB},
  volume = {13},
  year = {2020}


Approximate Summaries for Why and Why-not Provenance Seokki Lee, Bertram Ludäscher and Boris Glavic Proceedings of the VLDB Endowment. 13, 6 (2020) , 912–924.