Science, Faculty of
Computer Science, Department of
DSpace
UBCV
AlOmeir, Omar
Doctor of Philosophy - PhD
University of British Columbia
Data provenance is any information about the origin of a piece of data and the process that led to its creation. Most database provenance work has focused on creating models and semantics to query and generate this provenance information. While comprehensive, provenance information remains large and overwhelming, which can make it hard for data provenance systems to support data exploration or any meaningful applications. This thesis is focused on facilitating the use of database provenance through visual interfaces, summarization techniques, and curation techniques for real world applications. In the first part, we present visualization techniques for provenance information in relational databases. Our visualizations address every part of provenance information to facilitate user exploration. Through a user experiment, we show that our approach improves the accuracy and efficiency of performing exploration tasks. The next part addresses the challenge of volume of provenance information. Specifically, in the case of aggregation queries. The volume increases with the size of the database and creates a "needle in a haystack problem". We present novel summarization techniques that build on existing summarization literature. Our techniques work to support exploration for users who are not familiar with the data or its provenance. The final part shows our use of our summarization techniques to address the problem of refining aggregate queries. Aggregate queries pose a challenge in that they present ambiguous results to inexperienced users. Query refinement can help users realize their query errors and help them fix them. Through user experiment, we present evidence of the usefulness, and usability of our methods. Overall, the goal of this thesis is to facilitate the use of provenance information in relational databases. Through the use of novel techniques and user-centric evaluation, we present novel solutions and user interaction methods to enable new applications in this domain.
Provenance in Relational Databases: Usabilityand ApplicationsbyOmar AlOmeirA thesis submitted in partial fulfilment of the requirements forthe degree ofDoctor of PhilosophyinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)The University of British Columbia(Vancouver)April 2023© Omar AlOmeir, 2023The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Provenance in relational databases: Usability and applicationssubmitted by Omar AlOmeir in partial fulfillment of the requirements forthe degree of Doctor of Philosophyin Computer ScienceExamining Committee:Rachel Pottinger, Professor, Computer Science, UBCSupervisorRaymond Ng, Professor, Computer Science, UBCSupervisory Committee MemberTerje Haukaas, Professor, Civil Engineering, UBCUniversity ExaminerAlan Wagner, Associate Professor, Computer Science, UBCUniversity ExaminerAdditional Supervisory Committee Members:Joanna McGrenere, Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractData provenance is any information about the origin of a piece of data andthe process that led to its creation. Most database provenance work hasfocused on creating models and semantics to query and generate this prove-nance information. While comprehensive, provenance information remainslarge and overwhelming, which can make it hard for data provenance sys-tems to support data exploration or any meaningful applications. This thesisis focused on facilitating the use of database provenance through visual in-terfaces, summarization techniques, and curation techniques for real worldapplications.In the first part, we present visualization techniques for provenance in-formation in relational databases. Our visualizations address every part ofprovenance information to facilitate user exploration. Through a user exper-iment, we show that our approach improves the accuracy and efficiency ofperforming exploration tasks.The next part addresses the challenge of volume of provenance informa-tion. Specifically, in the case of aggregation queries. The volume increaseswith the size of the database and creates a “needle in a haystack problem”.We present novel summarization techniques that build on existing summa-rization literature. Our techniques work to support exploration for users whoare not familiar with the data or its provenance.The final part shows our use of our summarization techniques to addressthe problem of refining aggregate queries. Aggregate queries pose a chal-iiilenge in that they present ambiguous results to inexperienced users. Queryrefinement can help users realize their query errors and help them fix them.Through user experiment, we present evidence of the usefulness, and usabilityof our methods.Overall, the goal of this thesis is to facilitate the use of provenance in-formation in relational databases. Through the use of novel techniques anduser-centric evaluation, we present novel solutions and user interaction meth-ods to enable new applications in this domain.ivLay summaryUsers of data across all domains require the origin of data in order to gaintrust and understanding of the underlying data. Furthermore, informationabout the origin can improve the process of gaining knowledge from data.Data provenance is the scientific name given to the process of finding theorigin of a piece of data. With data provenance comes a large host of complexmodels and operations. Our goal in this thesis is to facilitate the use of thisprovenance information for relational database users. We do that throughvisualizations, summarization techniques, and through the application of ourtechniques to help users refine their database questions and answers. Weconduct experiments with real users to show the validity of our methods.vPrefaceThis dissertation is the result of multiple collaborations. All work was com-pleted in collaboration with my supervisor Dr. Rachel Pottinger, from heUniversity of British Columbia, Canada. The primary investigator role im-plies: 1) identifying the research question, 2) designing and performing the re-search, 3) analysis of results, as well as 4) writing and preparing manuscriptsand thesis chapters. Any work done by other team members is addressed foreach chapter. Most of the work has been published in peer reviewed venuesor is currently under submission. The break down of published content is asfollows:1. Chapter 3 is based on a publication at ICDE 2020. I was the pri-mary investigator for this work. Eugneie helped with implementingthe summarization method. Mostafa Milani helped with the write upand formalization. The study in this chapter was approved as mini-mal risk by the Behavioural Research Ethics Board at the Universityof British Columbia. UBC BREB number: H16-00797. The paper canfound in [ALMP20b]:(a) Omar AlOmeir, Eugenie Lai, Mostafa Milani, and Rachel Pot-tinger. (2020, April). The Pastwatch: On the usability of prove-nance data in relational databases. In 2020 IEEE 36th Inter-national Conference on Data Engineering (ICDE) (pages. 1882-1885).vi2. Chapter 4 is based on a publication at ICDE 2021. An extended versionof this work has been accepted in the IEEE Transactions on Knowl-edge and Data Engineering journal. I was the primary investigator forthis work. Eugenie Lai worked on implementing the summarizationmethods and experiments. Mostafa Milani helped with formulatingthe problem, writing the manuscript, and came up with the ideas forsummaries with joins. The survey conducted in this chapter was ap-proved as minimal risk by the Behavioural Research Ethics Board atthe University of British Columbia. UBC BREB number: H20-01634.The paper can be found in [ALMP21]:(a) Omar AlOmeir, Eugenie Lai, Mostafa Milani, and Rachel Pot-tinger. (2021, April). Summarizing Provenance of AggregateQuery Results in Relational Databases. In 2021 IEEE 37th Inter-national Conference on Data Engineering (ICDE) (pages. 1955-1960)3. Chapter 5 is being prepared for submission but is currently unpub-lished. It is joint work with Jianhao Cao and Rachel Pottinger. I wasthe lead investigator of this work. Jianhao Cao was in charge of imple-menting and evaluating the baseline methods. The study in this chap-ter was approved as minimal risk by the Behavioural Research EthicsBoard at the University of British Columbia. UBC BREB number:H21-03344.viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . .xvii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3.1 Visualizing provenance . . . . . . . . . . . . . . . . . . 41.3.2 Summarizing provenance . . . . . . . . . . . . . . . . . 41.3.3 Query refinement using provenance and summary rules 51.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8viii2.1 Provenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Data Summarization Rules . . . . . . . . . . . . . . . . . . . . 133 Provenance visualization . . . . . . . . . . . . . . . . . . . . . . 173.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . 183.2 System design principles . . . . . . . . . . . . . . . . . . . . . 193.2.1 Provenance System Principles . . . . . . . . . . . . . . 193.2.2 Visualization principles . . . . . . . . . . . . . . . . . . 213.3 Pastwatch overview . . . . . . . . . . . . . . . . . . . . . . . . 223.3.1 Visualization components . . . . . . . . . . . . . . . . 233.3.2 Summarization of provenance of aggregate query results 253.4 User experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4.1 Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . 293.4.2 Participants and setup . . . . . . . . . . . . . . . . . . 293.4.3 Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 303.4.4 Experimental design and analysis . . . . . . . . . . . . 313.4.5 Results and discussion . . . . . . . . . . . . . . . . . . 323.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 364 Provenance summarization . . . . . . . . . . . . . . . . . . . . 384.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . 434.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.3 Formalizing Provenance Summarization Problems . . . . . . . 474.3.1 Basics and Problem Setting . . . . . . . . . . . . . . . 484.3.2 The Impact Summarization Problem . . . . . . . . . . 494.3.3 Impact Summaries for Queries with Joins . . . . . . . . 544.3.4 The Comparative Summarization Problem . . . . . . . 564.4 Summarization Algorithms . . . . . . . . . . . . . . . . . . . . 58ix4.4.1 Computing Impacts and Contingency Sets . . . . . . . 604.4.2 Analysis of Summarization Algorithms . . . . . . . . . 634.4.3 A note about sampling . . . . . . . . . . . . . . . . . . 644.5 User Interface and visualization . . . . . . . . . . . . . . . . . 654.6 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 684.6.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . 684.6.2 Runtime Performance . . . . . . . . . . . . . . . . . . . 704.6.3 Quality of Provenance Summaries . . . . . . . . . . . . 714.6.4 User Survey . . . . . . . . . . . . . . . . . . . . . . . . 744.6.5 Case Study . . . . . . . . . . . . . . . . . . . . . . . . 764.7 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . 805 Aggregate query refinement using summary rules and prove-nance summaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 865.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865.1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . 915.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 945.3 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . 965.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 975.3.2 The scope of the query refinement solution . . . . . . . 995.3.3 Rule containment . . . . . . . . . . . . . . . . . . . . . 1005.3.4 Continuous Attributes . . . . . . . . . . . . . . . . . . 1015.3.5 Categorical attributes . . . . . . . . . . . . . . . . . . 1015.4 Solution Overview . . . . . . . . . . . . . . . . . . . . . . . . 1035.4.1 Rule generator . . . . . . . . . . . . . . . . . . . . . . 1055.4.2 Provenance summary . . . . . . . . . . . . . . . . . . . 1075.4.3 Candidate rule mining . . . . . . . . . . . . . . . . . . 1075.4.4 Candidate rules embedding, and ranking . . . . . . . . 1095.5 User study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.5.1 Experiment design . . . . . . . . . . . . . . . . . . . . 1115.5.2 User Study results . . . . . . . . . . . . . . . . . . . . 119x5.6 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . 1225.6.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . 1255.6.2 Runtime Performance . . . . . . . . . . . . . . . . . . . 1265.7 Conclusion and future work . . . . . . . . . . . . . . . . . . . 1326 Conclusions and future work . . . . . . . . . . . . . . . . . . . 1336.1 Summary of chapters and future work . . . . . . . . . . . . . . 1346.2 Discussion and reflections . . . . . . . . . . . . . . . . . . . . 136Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138A Provenance visualization . . . . . . . . . . . . . . . . . . . . . . 153A.1 User study materials . . . . . . . . . . . . . . . . . . . . . . . 153A.1.1 Task Questionnaire . . . . . . . . . . . . . . . . . . . 153A.1.2 Exit Questions . . . . . . . . . . . . . . . . . . . . . . 155B Provenance summarization . . . . . . . . . . . . . . . . . . . . 157B.1 Alternative Score Functions . . . . . . . . . . . . . . . . . . . 157B.1.1 Accumulative Impact Summaries . . . . . . . . . . . . 157B.1.2 Entropy-based Comparative Summaries . . . . . . . . . 159B.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161B.3 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165B.4 User survey materials . . . . . . . . . . . . . . . . . . . . . . . 166C Aggregate query refinement . . . . . . . . . . . . . . . . . . . . 171C.1 User study materials . . . . . . . . . . . . . . . . . . . . . . . 171C.1.1 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171C.1.2 Questionnaires and interfaces . . . . . . . . . . . . . . 173C.1.3 Suggestions . . . . . . . . . . . . . . . . . . . . . . . . 173xiList of Tables2.1 Summary of symbols and notations . . . . . . . . . . . . . . . . 92.2 Movies table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Directors table . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Q1’s answer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.1 Movies table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.1 Q1’s result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Q2’s result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.3 IMDB table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.4 A basic summary . . . . . . . . . . . . . . . . . . . . . . . . . 404.5 An impact summary . . . . . . . . . . . . . . . . . . . . . . . 404.6 A comparative summary . . . . . . . . . . . . . . . . . . . . . 404.7 Movies table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.8 Directors table . . . . . . . . . . . . . . . . . . . . . . . . . . 514.9 Summary A . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.10 An impact summary from the IPS algorithm . . . . . . . . . . 784.11 A basic summary from the BRS algorithm . . . . . . . . . . . 785.1 MoviesGenre sample table . . . . . . . . . . . . . . . . . . . . 885.2 Summary of symbols and notations for query refinement . . . . . 975.3 Table shows the average time (in seconds) it took users tofinish tasks using the two methods (ProvSum and PULearn). . 120B.1 Summary A . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168xiiC.1 PULearn suggestions for each task . . . . . . . . . . . . . . . . 176C.2 ProvSum suggestions for each task . . . . . . . . . . . . . . . 177xiiiList of Figures3.1 Pastwatch use case . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Pastwatch interface. (A) Main interface with 1) Schema list, 2)Query input, and 3) Query results. (B) The provenance graphshows the history of data to the most recent results, includingdatabase operations (Union and Select in this case). (C) Theoverview visualization is: a) A linked view of a world mapand bar chart. Showing geographic locations and a numberof companies respectively. b) A treemap visualization is alsoavailable for datasets that do not contain geographic informa-tion. (D) The summarization rules as a horizontal treemap. . . 243.3 A screenshot of a table showing provenance information. Theprov prefix tells the user they are looking at provenance in-formation. The name of the table follows the prefix, and thenthe name of the attribute. . . . . . . . . . . . . . . . . . . . . 313.4 Results for time (in seconds) broken down by task for eachmethod. Error bars correspond to standard error. Case refersto task. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Results for perceived difficulty (1 is very difficult - 5 very easy)broken down by task for each method. Error bars correspondto standard error. Case refers to task. . . . . . . . . . . . . . . 334.1 User interface for impact summaries. . . . . . . . . . . . . . . 664.2 User interface for summaries for queries with join (NA refersto missing data). . . . . . . . . . . . . . . . . . . . . . . . . . 66xiv4.3 User interface for comparative summaries. . . . . . . . . . . . 674.4 Effect of different parameters on Runtime, in seconds, of IPS.CPS experiments used the IMDB dataset. . . . . . . . . . . . 814.5 The quality of summaries w.r.t. coverage, weight, impact, anddiversity for the IMDB data, and the impact of k and mw (themaximum weight) on these quality metrics. . . . . . . . . . . . 824.6 The quality of summaries for five queries in the TPC-H dataset(k = 4 and mw = 3). . . . . . . . . . . . . . . . . . . . . . . . 834.7 a shows sampling performance. b & c show the effect of sam-pling on the quality of summaries. (k = 4, mw = 3) . . . . . . 844.8 Survey results show how users ranked the various metrics (5essential – 1 not important) and summary sizes. . . . . . . . . 855.1 Overview of solution from the query step all the way to therecommended groups of tuples . . . . . . . . . . . . . . . . . . 925.2 Query refinement framework architecture . . . . . . . . . . . . 935.3 t-SNE visualization of TFIDF representation of groups of rulesin example 20 in 2D space . . . . . . . . . . . . . . . . . . . . 1105.4 User interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165.5 Users’ perceived usefulness for both types of refinement method(1: very useful - 5: Very useless). . . . . . . . . . . . . . . . . 1225.6 The time it took users to complete tasks for both groups ofusers (Group A started with the PULearn method, Group Bstarted with the ProvSum method) . . . . . . . . . . . . . . . 1235.7 The time it took users to complete tasks using both methods. 1245.8 Effect of |D| in TPC-H. . . . . . . . . . . . . . . . . . . . . . 1265.9 Method and time in IMDB. . . . . . . . . . . . . . . . . . . . 1275.10 Breakdown of prediction/training for PULearn in IMDB dataset.1275.11 Effect of indexing in IMDB. . . . . . . . . . . . . . . . . . . . 1285.12 Preprocessing steps breakdown in IMDB. . . . . . . . . . . . . 1285.13 Preprocessing steps breakdown in TPC-H. . . . . . . . . . . . 129xvC.1 Demographic questionnaire for the query refinement study . . 173C.2 Tasks interface for the query refinement study . . . . . . . . . 174C.3 Exit questionnaire for the query refinement study . . . . . . . 174C.4 Individual movie suggestions (PULearn) . . . . . . . . . . . . 175C.5 Rules suggestions (ProvSum) . . . . . . . . . . . . . . . . . . 175xviAcknowledgementsFirst of all, all praises go to Allah the most merciful for his guidance.I would like to start by expressing my utmost gratitude to my supervisor,Dr. Rachel Pottinger for not only being an amazing supervisor but also aconstant source of inspiration, and a role model in kindness, patience, anddedication to research. Her encouragement and insightful feedback have beenextremely valuable to me. We have been through a lot in this PhD journeyand she was nothing but supportive and inspirational.I would also like to thank Dr. Mostafa Milani for all his support, inspi-ration, kindness, and guidance. I learned a lot from him.I would also like to thank my Ph.D. committee members, Dr. JoannaMcGrenere for all the meetings, advice, feedback, and support. Dr. RaymondNg for his invaluable advice, kindness, and support. Thank you both for yourtime and effort.I thank my collaborators, in no particular order, Eugenie Y. Lai, JianhaoCao, and Zainab Zolaktaf. Thank you so much for all the excellent workand contributions. Thank you to all members of the db-talks group, and theDMM lab. I will miss both.I thank my friends in the department. Jessica Wong, for being there fromthe beginning to the end. I also thank Laura Cang, Enrique Rosales, andArthur Marques. Thank you for making this a fun experience.I am incredibly grateful to my parents, who always believed in me. Forall the sacrifices they made for me so that I can be who I am today. Thankxviiyou to my father for believing in me and supporting me throughout. Thankyou to my mother, my first teacher, my best teacher, I learned so much fromyou that I cannot possibly repay you. Thank you both.I express my sincere and wholehearted thanks to my wife, my love, Abrarfor believing in me even when I did not believe in myself. Without her bymy side, I would not have been able to complete this work. I am thankfulfor her help, her insight, and her constant love and support. Thank you.To my daughters Serene and Yasmeen, thank you for being there with methroughout all of this. Playing with you has always helped keep this journeyfun, and enjoyable. I couldn’t have done it without you as my guiding light.I am thankful to my siblings, Othman and Nora, for their love and supportthroughout the years I spent away from home.Finally, I would like to thank the Saudi government and Prince SultanUniversity for their funding and financial support.xviiiChapter 1Introduction1.1 MotivationsThe provenance of data refers to the ability to track the origin and evolutionof a piece of data throughout its lifetime. Provenance has been a focus ofresearch in several different areas. In the scientific workflow context, prove-nance is used to show the processes that data went through. This researchon provenance work in workflow management has included work on visualiz-ing and presenting provenance information to users. In contrast, in databaseresearch, most of the focus has been on finding the sources that contributedto the results of a query. This has included a lot of work on developingcomprehensive models and representations of data provenance.However, there is very little work on presenting database provenance in-formation in a way that does not overwhelm users. Using existing prove-nance database systems can be overwhelming without prior knowledge ofdata provenance models or the data itself. Furthermore, provenance infor-mation can increase data size exponentially. This can have serious implica-tions on both storage and usability. We argue that data provenance needsto be visualized and in certain cases summarized to support and facilitatebroad exploration. In our work, we propose and develop techniques as se-1rious steps toward making provenance data widely usable without the needfor deep technical knowledge.A formal definition of provenance in database research is as follows:Definition 1.1. Given a database D, a query Q, and the results of applyingthe query to the database Q(D), the provenance problem in databases is tofind the sources in D that contributed to Q(D).Provenance information is important for a number of applications. Ourfocus is on using provenance to support analysis and exploration tasks. How-ever, to reach its potential, provenance information needs to be presented tothe user in a way they can easily understand and explore.We identify three main challenges:1. Provenance information needs to be visualized in a way that facilitatesexploration. Insightful visualizations of carefully curated provenanceinformation enable users to use provenance information to explore thedata. Visualizations should include query results, the processes that ledto the creation of the query results, and a visual summary of provenanceinformation.2. Provenance of aggregation query results presents a “needle in a haystackproblem”. The volume of provenance information for an aggregationresult can be large and prohibitive for exploration. An aggregationquery that counts the number of tuples in a relation returns a singlenumber. The provenance of this single number can be the whole re-lation or a group of relations. This creates a barrier for users to lookthrough provenance information and find meaningful information.3. Provenance information is too complex to support applications. In cer-tain cases, provenance information is not sufficient to solve a problem.Refinement of aggregate queries is such a problem. When a user issuesan erroneous aggregate query, provenance plays a role in looking at the2origin of the answer but not finding the correct answer. We utilize thetechniques developed to tackle the first two challenges to solve this one.Addressing these challenges should allow the user to freely explore dataand its related provenance without knowledge of the structure of provenanceinformation or the data itself. The last challenge creates a meaningful usecase for the techniques developed to tackle the first two.1.2 GoalsThe aim of this research is to design and implement a provenance explo-ration system for relational databases and utilize and extend the techniquesdeveloped for this system to handle aggregate query refinement. We definea provenance exploration system as a system that presents provenance in-formation without overwhelming size and complexity. The specific sub-goalsinvolved in achieving this are as follows:• Sub-goal 1: Develop visualizations of all aspects of provenance in databasesystems. This includes Query results, the process that led to creatingthose query results, and a visual summary of provenance information.• Sub-goal 2: Develop a new way to summarize provenance data for ag-gregation query results. This method takes into account the uniqueaspects of provenance. Our method integrates the aggregation func-tion used and the impact of provenance tuples on the result into thecalculation of the score function used to evaluate the quality of thesummary. We extend this algorithm to support the following function-alities: 1) The user can compare the provenance of different partitionsin the aggregation. Such comparisons can uncover interesting insightsinto the data. 2) Define different impact functions for multiple aggre-gation functions. 3) Compare the different semantics of the scoringfunction on real-world datasets to see how they perform.3• Sub-goal 3: Develop a query refinement approach using provenance andsummaries. This final task is unrelated to the provenance explorationsystem described previously. It is a related task as we use provenanceinformation and the summarization techniques we have developed. Thegoal is to allow users to get feedback as to why their aggregation queriesare not providing the answer that they expect. We present the user withpossible changes to the query results if they incorporate new suggestedtuples from the base data.1.3 OverviewWe define three main parts for this thesis that we briefly discuss below:1.3.1 Visualizing provenanceProvenance information can be large and overwhelming to users. We presenta set of criteria that any provenance exploration tool must have and in-troduce Pastwatch, a provenance exploration system that adheres to thosecriteria. We also address the issues associated with the provenance of aggre-gation queries, including creating a summarization method that makes theprovenance of aggregation queries manageable for users. Finally, we conducta quantitative user study to show statistically significant results that Past-watch makes provenance information more efficient and easier to use thanstandard approaches.1.3.2 Summarizing provenanceData provenance is any information about the origin of a piece of data and theprocess that led to its creation. Most database provenance work has focusedon creating models and semantics to query and generate this provenanceinformation. While comprehensive, provenance information remains large4and overwhelming, making it hard for data provenance systems to supportdata exploration.We present a new approach to provenance exploration that builds on datasummarization techniques. We contribute novel summarization schemes forthe provenance of aggregation queries, and techniques for the fast generationof these summarization schemes. We present impact summaries that considerthe impact of specific groups of tuples on an aggregate value. We also intro-duce comparative summaries that allow users to compare the provenance oftwo aggregate values. We conduct thorough experiments and a user surveyto show the feasibility and relevance of our approaches.1.3.3 Query refinement using provenance and summaryrulesOur primary motivation for this work is to help users perform aggregationqueries. Users use aggregation queries to perform many tasks: Exploring adataset, deriving summary statistics such as count, sum, and avg, or gen-erating reports. The process is iterative and error-prone. We address theversion of this problem where the user knows the domain well enough toknow that the answer is wrong. In such a case, the user may want to modifythe aggregate query to receive a specific answer. Our technique supports theuser in such a scenario by presenting them with suggestions on how to altertheir query to receive their preferred answer. Our technique is based on theprovenance summaries we describe above. We conduct a user study to showthat our methods outperform comparable machine learning methods. Wealso show that our approach gives meaningful suggestions for a broad classof queries.51.4 ContributionsWe identify 3 main contributions of this thesis:1. We present, to the best of our knowledge, the first system with visu-alization of provenance in a relational database system as part of ourPastwatch system. We identify the criteria for designing this systemand implementing it. We also conduct a user study to evaluate theutility and usability of our system.2. We introduce two novel techniques for summarizing the provenanceof relational data. We based our techniques on the results of a usersurvey we conducted. We evaluate those summarization techniquesbased on criteria for the summary quality we identify in the literatureand through our survey results.3. We introduce a new approach to query refinement based on the use ofprovenance data and summary patterns. We demonstrate the utilityof our approach through a user study. We also perform performanceexperiments to show the minimal cost incurred by our method.Throughout our work, we have used user studies as a means of demon-strating the utility of our solutions. In the provenance visualization solution,we compared the visualization we developed with provenance informationpresented to the user in tables. We showed that the provenance visualiza-tions allowed users to perform the tasks faster and more accurately.In the provenance summarization work, our initial plan was to conducta controlled lab experiment to determine some of the solution’s parameters(summary size, user preferred utility function, and presentation method).We opted for a remote user study instead for circumstances at the time(March 2020) did not allow for an in-person user study. It was also easier toacquire ethics approval for a remote survey than a remote study. The surveypresented users with a scenario of a data table and asked them questions6about multiple proposed short summaries. We designed the survey to findevidence of what users value in such a summary. We used those metrics toevaluate our summaries in performance experiments.In our final project, we conducted an in-person and remote user study tocompare how users perform the outlined tasks using our approach comparedto comparable machine learning techniques.User studies have not historically been a focus in database research, whichhas a tendency to focus exclusively on performance rather than usability.While user studies have become more common over the last decade, they arecertainly still quite rare. This is a promising development, although the useof user studies in database research still lacks maturity. The rigor and detailof such studies are not usually as well reported or as carefully scrutinized byreviewers as in fields such as human computer interaction. It is difficult togive a full picture of the field, but at the time of publication, our papers wereamong a few others with such evaluations. While not the main focus of thisthesis, we hope the user experiments described here can help maintain thestandards of the more rigorous work we found in the literature, and can beup to the standards set in other research fields.1.5 OutlineThis thesis is organized as follows. Chapter 2 presents background informa-tion that is relevant to all other chapters. Chapter 3 presents the problem ofvisualizing provenance information to facilitate user exploration. Chapter 4presents the problem of summarizing provenance information. Chapter 5addresses how to use provenance information and summary rules to refineaggregate queries. Finally, Chapter 6 concludes the thesis and gives direc-tions for future work.7Chapter 2BackgroundIn this chapter, we present some background information that is importantfor understanding the other chapters. We start with important notationand basic definitions to establish consistent terminology throughout the the-sis. In addition, we cover the basics of provenance in database managementsystems, including the different types and semantics, and the different im-plementations, along with some examples. We also discuss summary rules,their definition, and their different representations. Both of those topics areused in the following chapters so we decided to collect the information herebefore the reader gets into the main topics.We begin with some notation: A relation R with a set of attributes (rela-tion schema)R = {A1, ..., Am} is a finite set of m-ary tuples {t1, ..., tn}. Eachrelation is represented as a table, each of which has columns and containsrows. We occasionally abuse notation by saying that tables contain tuples orhave attributes. A database D with database schema S = {R1, ...,RN} is afinite set of relations R1, ..., RN . We denote the value in the i-th position intuple t in D as t[Ai]. Q(D) is the set of answers to a query Q over databaseD. For attribute Ai ∈ R, Dom(Ai) is the domain of values in Ai. Table 2.1summarizes our symbols and notation.8Table 2.1: Summary of symbols and notationsSymbol DescriptionR relationA,B, ..., G relational attributest, r tuplesa, b tuples in query answerQ,Q(D) database, query, query answerD,S database (instance), database schemas, c rules (c for comparative rules)S set or list of rulesDom(A) domain of attribute A? wildcard characterRa provenance of answer a in RQa query that returns aggregate value in amw maximum rule weightmD,mq number of attributes, number of group-by attributes2.1 ProvenanceData provenance is defined as provenance information related to the dataitself. To show what we mean by data provenance in the relational context,we introduce a running example. Consider the following query:Q1: SELECT d.Gender, m.Genre FROM Movies m, Directors dWHERE m.Director = d.NameApplying Q1 to the data in Tables 2.2-2.3 results in Table 2.4.The goal of data provenance is finding the source of a piece of data andthe process it went through to make it into the results of a query. Moreprecisely, given a database D, a query Q, and the result of applying thequery to the database Q(D), the provenance problem in databases is to findthe sources in D that contributed to Q(D) [BKWC01].Different notions of provenance, including lineage, why-provenance, where-provenance, and how-provenance, are proposed and studied for databases9ID Title Year Genre Rating Rev (M$) Directorr1 Lincoln 2012 Drama 8 275.3 Steven Spielbergr2 Sicario 2015 Drama 8 84.9 Denis Villeneuver3 Crimson Peak 2015 Horror 7 74.7 Guillermo del Toror4 Bonjour Anne 2016 Comedy 5 8.9 Eleanor Coppolar5 The Terminal 2004 Drama 7 219.4 Steven SpielbergTable 2.2: Movies tableID Name Gender Countryr6 Steven Spielberg Male USr7 Denis Villeneuve Male Canadar8 Guillermo del Toro Male Mexicor9 Eleanor Coppola Female USTable 2.3: Directors tableID Gender Genreb1 Male Dramab2 Male Horrorb3 Female ComedyTable 2.4: Q1’s answerqueries [CCT09]. We review those provenance types with emphasis on lin-eage and why-provenance, which we use in this work.LineageIn addition to often being used as a synonym for provenance, lineage is one ofthe earliest types of provenance. Lineage lists the tuples that caused a tupleto appear in the answer of a query [CW00]. The lineage of b1, the first tuplein the results, w.r.t. query Q1 is simply the set of tuples that contribute tob1. In this case, the lineage of b1 is {r1, r2, r6, r7}.We give a formal definition of lineage, as it is the provenance type wweuse in our work. This definition is paraphrased from definition 2.1 in [CCT09]to fit our notation:Definition 2.1 (Lineage). Given a queryQ over relationsR1,..,Rn in databaseD, the lineage of a tuple t ∈ Q(D) is a sequence (R′1, ..., R′n) of subsetsR′i ⊆ Ri. Such that:101. Q(R′1, ..., R′n) = {t}.2. For each 1 ≤ i ≤ n and for each ti ∈ R′i, we haveOp(R′1, .., R′i−1, {ti}, ..., R′n) =φ.3. (R1′, ..., Rn′) is maximal among subsets of R1, ..., Rn satisfying (1) and(2).Why-provenanceIntuitively, why-provenance consists of witnesses, i.e. sets of tuples that arenecessary to make a tuple appear in the answer [BKWC01]. To continuewith our running example, the why-provenance of b1 in Table 2.4 consistsof two witnesses {r1, r6} or {r2, r7}, either of which is sufficient to explainthe presence of b1 in the results. In other words, having this tuple in theresults of Q3 does not require the tuples in both witnesses; only one witnessis needed.Where-ProvenanceWhere-provenance answers the question of where in the input that piece ofdata is copied from [BKWC01]. In our example, the where-provenance ofb1[Gender] in Table 2.4 would be r6[Gender], r7[Gender] since data is copiedfrom those attributes in tuples r6 and r7.How-provenanceHow-provenance answers the question of what process the piece of data wentthrough to end up in the output. How-provenance represented by elementsof a semiring of polynomials, as seen in [GKT07], can give a more detailedaccount of the transformation applied to the piece of data. In our example,the how-provenance of b1 in Table 2.4 would be the polynomial r1.r6 + r2.r7.11This represents that r1, r2 was joined with r6, r7, and subsequent results werecombined to get the final result.We do not use why, how, or where provenance in our work and refer thereader to [CCT09] for formal definitions.Provenance for aggregate queriesFor aggregate queries, the notion of lineage is still applicable, e.g. the lineageof an answer (Male, 654.3M$) to the aggregate query,Q4: SELECT d.Gender, SUM(m.Rev) FROMMovies m JOIN Directors d ON m.Director = d.Namecontains r1, r2, r3, r5 from Movies (Table 2.2) and r6, r7, r8 from Directors(Table 2.3), i.e. the male directors and their directed movies.The authors in [ADT11] extend how-provenance to aggregate queries us-ing semimodules instead of semirings, which allows bag and set semanticsin aggregate queries, and enables tracing provenance information for val-ues rather than tuples. For example, the provenance of (Male, 654.3M$) isthe aggregate polynomial expression r1.r6 ⊗ 275.3$⊕ r2.r7 ⊗ 84.9$⊕ r3.r8 ⊗74.7$ ⊕ r5.r6 ⊗ 219.4$. The relation ⊕ in the expression is the operation ofthe monoid. It can be interpreted as sum, average, min, or max, dependingon the aggregate function in the query, e.g., for Q4, ⊕ is interpreted as asum. The tensor product ⊗ in the semimodule maps to a symbolic expres-sion that involves tensors, scalars, polynomials, and the addition operation ofthe semimodule., e.g., ⊗ maps the pair of r5.r6 and 219.4$ to 219.4$ when r5and r6 are respectively present in Movies and Directors. With the semimod-ule in this example, computing the provenance will result in the aggregatequery answer 654.3M$. While this provenance representation is informative,it can easily become a large and unreadable expression even for fairly simplequeries.We use lineage as the notion of provenance in our provenance summaries.Therefore, by the provenance of a query, we refer to the set of tuples in the12query lineage.Compared with the other types of provenance, lineage leaves out someimportant provenance information; however, its simplicity is advantageousin our solution as it makes the provenance summary easy to navigate andunderstand. Our solution can be extended to support other types of prove-nance where the representation is in the form of tables or sets of tuples.We leave such extensions as future work and focus mainly on lineage as wemainly explore usability. We also augment the provenance data with impactand coverage information. Coupled with the simplicity of lineage, this allowsus to present users with the information they need in a concise, clear, andcomprehensible representation.2.2 Data Summarization RulesThe work in [JGMP15, JGP16] introduces summarization rules to summa-rize “interesting” aspects of a table. In Chapters 3 and 4, we use them tosummarize and explore the provenance of aggregate queries. In Chapter 5,we use them to refine aggregate queries. Here we review some key conceptsabout these summarization rules.Definition 2.2 (Summarization rules). A summarization rule s over a rela-tion R with schema R = {A1, ..., Am} is an n-ary tuple in which for everyAi ∈ R, s[Ai] ∈ Dom(Ai) ∪ {?} and ? is a value not in Dom(Ai).The value ? is a wildcard that matches every attribute value and allowsthe rule to summarize multiple tuples.Example 1. The rule s1 = (?, 2015, ?, 7, ?, ?) is a summarization rule overTable 2.2 that matches every movie with rating 7 made in the year 2015.This matches the tuple: r3 For clarity, we include attribute names in the rules, e.g. s1 in Example 1is (Title : ?,Year : 2015,Genre : ?,Rating : 7,Rev : ?,Director : ?).13Definition 2.3 (Sub-rule and super-rule). Consider rules s1 and s2 over arelation R with schemaR = {A1, ..., Am}. Rule s1 is a sub-rule of s2, denotedby s1 v s2, if and only if for every Ai ∈ R, s1[Ai] = s2[Ai] or s1[Ai] = ?. Ifs1 is a sub-rule of s2, s2 is a super-rule of s1, which we denote by s2 w s1.Example 2. Rule s1 is a sub-rule of s′ = (Title : ?,Year : 2015,Genre :Romance,Rating : 7,Rev : ?,Director : ?), and it is a super-rule of s′′ =(Title : ?,Year : ?,Genre : ?,Rating : 7,Rev : ?,Director : ?) Definition 2.4 (Cover and count). Given a relation R, a summarizationrule s covers a tuple r ∈ R denoted by r ∈ s if for every Ai, r[Ai] = s[Ai]or s[Ai] = ?. Cover(s) is the set of tuples in R that are covered by s andCount(s) = |Cover(s)| is the number of tuples covered by s.Example 3. In Example 1, s1 covers r2, r3, Cover(s1) = {r2, r3} and Count(s1) =2. Rule s2 = (Title : ?,Year : ?,Genre : Drama,Rating : ?,Rev : ?,Director :?) covers the drama movies, Cover(s2) = {r1, r2, r5} and Count(s2) = 3. Definition 2.5 (Marginal cover and marginal count). For a list of rulesS = (s1, s2, ...) over relation R, MCover(si, S) is the marginal cover of si andis defined as the tuples that are covered by si and not any sj ∈ S with j < i.MCount(si, S) = |MCover(si, S)| is the marginal count of si.Example 4. Considering S = (s1, s2) that summarizes Table 2.2 with rules:s1 = (Title : ?,Year : ?,Genre : Drama,Rating : ?,Rev : ?,Director : ?),and s2 = (Title : ?,Year : ?,Genre : ?,Rating : 7,Rev : ?,Director : ?),MCover(s1, S) = {r1, r2, r5},MCover(s2, S) = {r3}, MCount(s1, S) = 3,MCount(s2, S) = 1. Definition 2.6 (Score function and marginal score). The score of a list ofrules S = (s1, s2, ...) is defined as follows:Score(S) =∑si∈SMCount(si, S)×Weight(si). (2.1)14Weight is a function that returns a non-negative real number. For si ∈ S,MCount(si, S)×Weight(si) is its marginal score.The weight function conveys how well a rule summarizes the values in atable. We use the common weight function that is introduced in [JGMP15]:the number of non-? values. We prove our results for a general class ofmonotone weight functions as in Definition 2.7.Example 5. For s1 and s2, Weight(s1) = 1 and Weight(s2) = 1. The score ofS = (s1, s2) is 3×1+1×1 = 4 and the score of S ′ = (s2, s1) is 2×1+2×1 = 4.The marginal scores of s1 and s2 are subsequently 3 and 1 in S, and 2 and 2in S ′. Definition 2.7 (Monotone weight functions). A weight function Weight,or W for short, is monotone if for every pair of rules s1, s2 if s1 v s2, thenW (s1) ≤ W (s2).Example 6. The weight function W that returns the number of non-? valuesis monotone. In Example 2, s1 v s′ and W (s1) ≤ W (s′) as W (s1) = 2 andW (s′) = 3. Also s′′ v s1 and W (s′′) ≤ W (s1) as W (s′′) = 1. Definition 2.8 (Summary). A summary over a relation R is a set of summa-rization rules over R. The score of a summary is the maximum score betweenall the possible lists containing the rules in the summary.For the rest of the thesis, we use sets of summarization rules rather thanlists of summarization rules where the score of a set of rules is the maximumscore between all the possible lists containing the rules in the set.Example 7. In Example 5, {s1, s2} is a summary with scoremax(Score((s1, s2)), Score((s2, s1))) = max(4, 4). Definition 2.9 (The summarization problem). Given a relation R and afixed value k, the summarization problem is to find a summary S with |S|=kand maximum Score(S).15The summarization problem is NP-hard [JGP16]. The authors in [JGP16]present a greedy algorithm called Best Rule Set (BRS) that finds a sub-optimal set of rules efficiently. At a high level, BRS has k steps. It starts withan empty ruleset S, and at each step, it adds the best rule that maximizes thescore function. In order to find the rule s to add in each step, the algorithmcomputes the impact of every possible rule on the score function. This is donein several iterations over the tuples in the relation. The algorithm appliesideas from the Apriori Algorithm [AS94] for frequent item-set mining to prunesome of the rules without computing the score function. The authors alsosuggest a data sampling scheme for finding the best rule when only a limitednumber of tuples can be processed in memory. The approximation guaranteein the algorithm is based on the fact that the score function (Definition 2.6)is sub-modular [JGP16, Lemma 3].Definition 2.10 (Sub-modular set functions). A set function f is sub-modular iff for any sets of items S1, S2 and an item s 6∈ S1 ∪ S2, if S1 ⊆ S2then f(S1 ∪ {s})− f(S1) ≥ f(S2 ∪ {s})− f(S2).16Chapter 3Provenance visualization3.1 IntroductionData provenance is any information about the origin of a piece of data andthe process that led to its creation. Provenance has been researched in anumber of different areas. In the scientific workflow context, provenance isused to show the processes that data went through. Thus, provenance workin workflow management has included work on visualizing and presentingprovenance information to users. In contrast, in database research, most ofthe focus has been on finding the sources that contributed to the results ofa query. This has included much work on developing comprehensive mod-els and representations of data provenance. However, there is very littlework on presenting database provenance information in a way that does notoverwhelm users. Using existing database provenance systems can be over-whelming for those who do not have prior knowledge of data provenancemodels or the data itself. Furthermore, provenance information can increasethe data size considerably. This can have serious implications on both stor-age and usability. We argue that data provenance needs to be visualized andsometimes summarized to support and facilitate broad exploration. In thischapter, we present Pastwatch, which is a first step toward making prove-17nance data widely usable without the need for deep technical knowledge.We identify two main challenges:1. Provenance information needs to be visualized in a way that facilitatesexploration. Visualizations should include query results, the processesthat led to the creation of the query results, and the source tables.2. Provenance information for aggregate query results can be large andprohibitive for exploration. An aggregation query that counts the num-ber of tuples in a relation returns a single number. The provenance ofthis single number can be the whole relation. This creates a barrierfor users to look through provenance information and find meaningfulinformation.Pastwatch addresses these two challenges as we describe in the followingsubsection.3.1.1 ContributionsIn this chapter, we review provenance research and use our findings to cre-ate Pastwatch, a first step toward comprehensible database provenance. Inparticular, our contributions are:• We present, to the best of our knowledge, the first system with visual-ization of provenance information in a relational database system.• We survey provenance research and create a concise set of desirablefeatures for a provenance exploration system. We identify the criteriafor designing this system and implementing it.• We validate Pastwatch with a user study that shows how it improvesaccuracy and efficiency.183.2 System design principlesIn this section, we lay out a set of design principles that should be followedby future database provenance exploration systems and are adhered to byour Pastwatch system.In particular, in this chapter, we seek to solve the problem of provenanceexploration, which is to present provenance information without overwhelm-ing size and complexity. Provenance exploration in turn allows non-expertsto understand the provenance of their relational data and query results. In-sightful visualizations of carefully curated provenance information give usersthe ability to use provenance information to explore the data.We define a data provenance exploration system to support data prove-nance exploration through two components: 1) A back-end DBMS with sup-port for provenance, 2) A front-end user interface with visualizations. In thissection, we characterize design principles for these two components which areconsidered in the design of Pastwatch.3.2.1 Provenance System PrinciplesWhat sets an exploration system apart from traditional systems is that thetraditional approaches rely on the user to query and explore the results viadata manipulation languages. In traditional approaches, the models canbe complex and some query languages can be unintuitive, making thingsdifficult.Several data provenance papers have looked at the desirable features ofa data provenance system [GD07, SPG05]. Authors in such surveys list de-sirable features for provenance in data management systems, including userinterfaces and visualizations. In this section, we combine these features andaugment them with new features, based on recent literature, to detail theprinciples for a data provenance exploration system for which Pastwatch is afirst attempt. Based on this background research, our principles for a data19provenance exploration system are as follows:1. Support multiple types of provenance. As argued in [GD07], acomprehensive provenance exploration system should support multipletypes of provenance. The user could need different semantics depend-ing on the scenario, this includes access to different visualizations. Inthis work, we present visualizations that work for why provenance andlineage.2. The back-end system should allow for provenance data to bequeried. [GD07] Without this feature, it would be impossible to showprovenance information to the user, let alone visualize it meaningfully.3. Provenance exploration systems should support provenanceinformation at different granularities. [DF08] Provenance explo-ration systems must support both tuple and table-level granularities inorder to make decisions.4. Store provenance data in a way that lets provenance informa-tion be decoupled from the data. Provenance and its data shouldbe distinct enough so that the user can tell where it comes from and towhich tuple the provenance belongs. Storage is key: The way prove-nance is stored should allow for querying and isolating of provenanceinformation while retaining the link to the data.5. The model should be efficient and simple enough to queryand visualize. A provenance exploration system based on a rela-tional DBMS allows for improved efficiency. This allows it to performprovenance operations with the good performance provided by years ofoptimization of SQL queries. It also supports SQL-like manipulationthat can power visualizations.6. Make provenance simpler to use with different disseminationtechniques. As seen in workflow provenance systems, provenance ex-20ploration needs visualizations that give the user the ability to explorefreely.7. Provenance of large size results of aggregation queries shouldbe summarized. Provenance of aggregation query results can belarge and daunting. A summary of such provenance information canhelp users make the most of this information. This problem is quitechallenging, as we discuss in detail in Section 3.3.2.We designed Pastwatch in accordance with the above design principles.Pastwatch supports multiple types of provenance; the back-end supports bothwhy- and where-provenance. The back end is a relational DBMS, whichmeans it is efficient and simple to query, and provenance information canbe queried separately. Finally, visualization and summarization of data andprovenance are first-class components of Pastwatch.3.2.2 Visualization principlesIn section 3.2.1, we detail what the system can provide to the user of prove-nance information. In this section, we explore what the user can do whenusing this provenance information in the form of visualizations. The designof the visualization and exploration component is guided by the following setof visualization principles:• Overview first, zoom and filter, then details on demand [Shn96].This principle is essential for dealing with large-scale information. Themain goal of our visualizations is to show the user a summarized viewof the data (usually an aggregation). The user can browse through acustom overview by specifying an aggregation or filtering query. Theuser can then zoom in and look at specific tuples and look at theirprovenance information.21• Recognition over recall [Mun14]. Navigating through data tablesand drilling down can confuse the user as to where they are in thesystem or the provenance of query results. Keeping track of where theuser is via visual elements beats having to remember where they are.Hence we create a provenance graph to show a persistent overview thathighlights which level the user is currently browsing.• Appropriate encoding for the underlying data. We use a graphto show the provenance information sources and how they relate to theresults. We use a horizontal treemap to represent the summarizationrules. Using this visualization allows nesting rules within rules. Thescore of a rule is mapped to the area of the rectangle that contains therule.• Multiple views are most effective when explicitly linked [Rob07].The user is given the option to utilize multiple views at once. High-lighting one element in a certain view (the bar chart for example) wouldhighlight the same item on a different view (country on a map for ex-ample).• Aggregation and filtering to reduce the data. Visual idioms havelimitations regarding the number of items they can display [Mun14].Reducing guarantees better scalability for large datasets and more ef-ficient visualizations.3.3 Pastwatch overviewOur goal in implementing Pastwatch was to provide users with all the fa-cilities they need to use provenance information. Pastwatch has two maincomponents:1. A data and provenance visualization component.222. A data summarization component that summarizes the provenance oftuples produced by aggregation queries. In this section, we go intodetail on each component.Provenance SummarizationUser InterfaceProvenance GenerationVisualizationQ Q(D)Database Dt Summary(*,*,Comedy,*)(*,*,2018,*)(*,*,Action,*)...QtQQ Q(D)SPastwatchFigure 3.1: An overview of Pastwatch. The system takes a query and returnsthe query results to the user, including visualization of provenance informa-tion. The user asks for the provenance of a tuple in the query results. Thesummarization component takes the provenance, summarizes it and returnsa ranked list of rules of size k.3.3.1 Visualization componentsAs seen in Figure 3.2, Pastwatch visualizes provenance information that isstored in relational tables side by side with their respective tuples. Thedata alone can be large and overwhelming, and the provenance information23Figure 3.2: Pastwatch interface. (A) Main interface with 1) Schema list,2) Query input, and 3) Query results. (B) The provenance graph showsthe history of data to the most recent results, including database operations(Union and Select in this case). (C) The overview visualization is: a) Alinked view of a world map and bar chart. Showing geographic locationsand a number of companies respectively. b) A treemap visualization is alsoavailable for datasets that do not contain geographic information. (D) Thesummarization rules as a horizontal treemap.24increases the size and complexity. The user needs the information to bedivided into smaller subsets. To maximize comprehensibility, provenanceinformation should be hidden until the user asks for it.We created two components to browse the provenance information: theoverview visualization and the provenance graph. The overview visualizationsummarizes the data and presents the user with a manageable overview. Inthis overview, the user can click on any data item to see its provenance. Theprovenance graph presents an interactive overview of the provenance of apiece of data. Furthermore, users can ask for the provenance informationof a piece of aggregated data to be summarized as a set of summary rules.Summary rules are shown in Figure 3.2 where a horizontal treemap embedsthe score of a rule as height and color.3.3.2 Summarization of provenance of aggregate queryresultsData summarization rulesID Title Director Gender Year Genre Rev (M$)t1 Lincoln Steven Spielberg M 2012 Drama 182t2 Bonjour Anne Eleanor Coppola F 2016 Comedy 13t3 Sicario Denis Villeneuve M 2015 Action 47t4 Mamma Mia Phyllida Lloyd F 2008 Comedy 144t5 Pitch Perfect 2 Elizabeth Banks F 2015 Comedy 184Table 3.1: Movies tableThe work in [JGP16] introduces summarization rules to summarize “in-teresting” aspects of a table. In this section, we use our version of suchrules to summarize and explore the provenance of aggregate queries. Theprovenance of an aggregate query is all the tuples that contributed to theaggregate value. Therefore, it is usually a much larger set than the results25of an aggregation query.Definition 3.1 (Summarization rules). A summarization rule s over a re-lation R with schema R = {A1, ..., An} is an n-ary tuple in which for everyAi ∈ R, s[Ai] ∈ Dom(Ai) ∪ {?}.The value ? is a wildcard that is not in Dom(Ai). It matches everyattribute value and allows the rule to summarize multiple tuples.Example: s1 = (?, ?, ?, 2015,Action, ?) is a summarization rule over Ta-ble 3.1 that matches every Action movie from 2015.In [JGP16] the score of a list of rules S = (s1, s2, ...) is defined as follows:Score(S) =∑si∈SMCount(si, S)×Weight(si). (3.1)where the score of a set of rules is the maximum score between all the possiblelists containing the rules in the set. Weight is a monotone function thatreturns a non-negative real number. The weight function conveys how well arule summarizes the values in a table. We use the common weight functionfrom [JGP16], w = the number of non-? values.The summarization problem is defined as follows: Given a relation R anda fixed value k, the summarization problem is to find a set of rules S with|S| = k and maximum Score(S). It is an NP-hard problem [JGP16]. Theauthors of [JGP16] present a greedy algorithm called Best Rule Set (BRS)that finds a sub-optimal set of rules efficiently. At a high level, BRS has ksteps. It starts with an empty ruleset S and at each step, it adds the bestrule that maximizes the Score function. In order to find the rule s to addin each step, the algorithm computes the impact of every possible rule onthe score function. This is done in several iterations over the tuples in therelation. The algorithm applies ideas from the apriori algorithm [AS94] forfrequent item-set mining to prune some of the rules without computing thescore function. The approximation guarantee in the algorithm is based on the26fact that the Score function is a sub-modular set-function [JGP16, Lemma 3].For functions other than count, the score function is not sub-modular. In thefollowing section, we show our own definition of a score function that takesimpact into consideration and is sub-modular for the avg and sum functions.Pastwatch summarizationIn Pastwatch, we present AScore for a set of rules as the maximum scorebetween every possible list that contains the rules in the set. AScore gener-alizes Score by replacing MCount(si, S) with MAggt(si, S). Unlike Score, theAScore function considers the impact of the tuples covered by rules in S onthe aggregate query result Qt(R).To measure this impact, we use sensitiv-ity analysis, a technique that measures the sensitivity of a query to a tupleor a set of tuples by comparing the answers to the query with and withoutthe tuple(s) in the database [KLD11]. This is noted by the superscript t inAScoret. For query Qt, we measure the impact of a rule si by sensitivity anal-ysis w.r.t. the tuples in the marginal cover set MCover(S, si). The followingfunction defines MAggt based on the sensitivity of Qt:MAggt(si, S) =∑r∈MCover(si,S)|Qt(R)−Qt(R \ {r})|. (3.2)Example: The user asks a query for the average revenue of all movies inTable 3.1. The user proceeds to click on the tuple: t = (Comedy, 113.6 M$),asking for a summary of the provenance of this tuple. The Why-provenanceof t is three tuples: t2, t4, and t5. In this example t2 is an interesting tu-ple because t2[Rev] = 13. This means t2 has a considerable impact onthe average revenue of comedy movies. In this case, we prefer rules thatcan single out and highlight this tuple. Say there is a list of rules S1 withonly one rule s1 = (?, ?,F, ?,Comedy, ?) that covers and explains all tuplest2, t4, t5. AScore would assign a higher score to a set of rules S2 = (s2, s1) withs2 = (?,Eleanor Coppola,F, ?,Comedy, ?) that highlights the movie with the27highest impact on the average result.AScore is sub-modular for aggregate functions Sum and Average whichmeans we can use the greedy algorithm with the same guarantees.We elaborate on and extend our work on aggregate summarization inChapter 4.3.4 User experimentWe performed a quantitative user study1 to validate the visualization andexploration components of Pastwatch. In this study, the users interactedwith a visualization of the provenance of a dataset and its provenance meta-data to answer a set of questions. The users also tried to answer similarquestions using a web interface that presented the provenance in HTMLtables in the same format of Perm [GMA13]. We purposefully did not includequerying of provenance as an interaction paradigm in this user study. Whilequerying provenance is mature enough to support any use cases, we felt ourusers did not have the expertise to write queries using a query languagelike SQL. Despite citing experience with data or data management systems,most of them were not comfortable enough to write SQL queries duringa user study. The other reason is that Pastwatch was initially developedas part of the GLEI system. The user study described here was meant toassess the provenance component of the GLEI system which has a differentgroup of users than a general provenance data management system. Whileusers performed these tasks, we measured the time of completion and answeraccuracy. The users also evaluated the difficulty of each task and offeredsubjective feedback at the conclusion of the study. We compiled the fullmaterials used in the study in Appendix A.1The study was approved as minimal risk by the Behavioural Research Ethics Boardat the University of British Columbia. UBC BREB number: H16-00797.283.4.1 HypothesesOur hypotheses for this user study were:• H1: The users will find it less difficult to answer questions using thePastwatch interface than the table interface.• H2: The users will complete the tasks faster using the Pastwatch inter-face than the table interface.• H3: The users will answer the questions more accurately using Past-watch than the table interface.A description of the different interfaces and measures follows in the nextfew sections.3.4.2 Participants and setupAll participants were graduate and undergraduate students from the Com-puter Science and Electrical and Computer Engineering departments at theUniversity of British Columbia who had sufficient familiarity with data andrelational tables. Familiarity is determined by taking an entry-level coursein databases or equivalent. However, none of the participants had any priorexperience with provenance information.The dataset used in the study is a real-world financial dataset usedin creating Global Legal Entity Identifiers (GLEIs) for financial institu-tions [LLP14] [CM19]. This is a real-world financial dataset collected fromvarious sources for financial institutions to create a single, universal identifierfor entities that are involved in any financial transaction. The data charac-teristics are as follows: The number of tuples: 250k each tuple correspondsto a real-world financial entity. The number of tables in the GLEI dataset:1. The total number of attributes in the tables: 12. The number of sourcetables in the provenance: 6.29The study was conducted with 21 participants: 6 women, 14 men, and 1participant who did not wish to disclose. Participants ranged from second-year undergrads to fourth-year Ph.D. students.Study sessions were done with a single user at a time on a Macbook Pro15” laptop. Participants who were not familiar with the Apple trackpad wereoffered a mouse.3.4.3 ProcedureEach study session started with a survey to collect demographic informa-tion and assess participants’ familiarity with the study concepts. The userswere shown a demo of the system component that produces the table formatoutput. The demo shows an example which is a smaller-scale problem thatresembles the four tasks the participants have to perform. Participants werealso shown how to access the visualization component and where to inputthe answers to the tasks’ answers. The participants were also provided de-tails on the dataset and what provenance means. The participants were thengiven instructions on how to perform their tasks with task questions andsubjective questions. At the end of each session, participants were handed aquestionnaire to evaluate the tool and provide comments.The participants’ tasks consisted of two different sets of questions. In thefirst set, users were asked to locate a data item in the output and then locateits origin point. Users were asked to find a specific entity in the datasetusing its unique identifier. They were then asked to locate the source of thisentity using provenance information. In the second set, users were asked tochoose any entity from a certain financial source and to find out how it haschanged on update. Participants performed a task using Pastwatch or thetable interface. 11 participants started with the visualization method, theother 10 started the first task with the table interface. The time of completionfor each task and solution accuracy was measured. The full details of tasksand questionnaires are in the appendix in Chapter A.1.2.30Figure 3.3: A screenshot of a table showing provenance information. Theprov prefix tells the user they are looking at provenance information. Thename of the table follows the prefix, and then the name of the attribute.Users did not write any queries to get the results, they simply clicked on abutton to generate the query results. In the table method, all the informationis presented in a single table. In the Pastwatch, users interacted with theworld map and provenance graph to navigate the dataset and its provenance.Each session lasted about 30-40 minutes.3.4.4 Experimental design and analysisThe study had one within-subject factor: the method used to find answersto the questions in each task and the following levels:1. A table representation of the results of a provenance generating query2. The Pastwatch interface. We refer to it as visualization.31The dependent measures were:1. The accuracy of answers (there was a binary correct or incorrect answerto each question).2. The time it took to complete a task in seconds. The timer starts as theuser begins to explore the data and ends by the time they have answeredthe main questions. The follow-up questions about the difficulty andsubjective feedback are not timed.3. The subjective perceived difficulty of a task on Likert scale of 1-5. 1 isvery difficult and 5 is very easy.The tasks were counterbalanced across interfaces. Half the users saw thetable interface first, and the other half saw the Pastwatch interface first. Be-cause the data does not follow a normal distribution, we used the Wilcoxonsigned rank test which tests the median difference between two sets of obser-vations. [McD09]3.4.5 Results and discussionEfficiency, Perceived difficulty, and Accuracy We saw statistically sig-nificant effects of the different methods on the time it took to complete atask, the perceived difficulty, and the accuracy (P < 0.01). Participantsspent less time completing tasks using Pastwatch (M = 163 seconds) thanthey did using the table interface (M = 262 seconds). On a scale of 1 beingvery difficult and 5 very easy, participants rated the task (M = 3.95) usingPastwatch and (M = 2.42) using the table interface. Participants, on av-erage, were able to answer 92% of the questions correctly using Pastwatchcompared to 82% using the table interface.Subjective feedback More than 80% of users commented that theyfound Pastwatch easier to deal with and easier to figure out the provenancerelationships between tables.320100200300400Case 1Case 2Case 3Case 4TaskTimeMethod: Table VisualisationFigure 3.4: Results for time (in seconds) broken down by task for eachmethod. Error bars correspond to standard error. Case refers to task.01234Case 1Case 2Case 3Case 4TaskDifficultyMethod: Table VisualisationFigure 3.5: Results for perceived difficulty (1 is very difficult - 5 very easy)broken down by task for each method. Error bars correspond to standarderror. Case refers to task.33The most requested feature was a search box; that feature was disabledprior to the study so as not to bias the study toward the visualization tool.The browser search function also did not work with Pastwatch due to incom-patibility with the scroll bar plug-in. This was left unfixed to keep the focuson general exploration using the visualization tool.20 participants rated it as likely or very likely that they would use theprovenance tool in their work to confirm the reliability or accuracy of a pieceof data/dataset. Only one user was not interested in using the provenancetool at all listing the reason as “because I prefer to write queries rather thantrusting my eyes.”Other comments from the subjective feedback survey: “As a normal user;this tool would be useful in any context where I know it is possible that mydata comes from several sources.” Another participant states: “First: it is agood tool to have. Second: in the case of troubleshooting it is very easy togo back to the source and check the accuracy of the information. I think itmakes troubleshooting easier in general.”Discussion Visualization of database provenance is not the end-all so-lution to all provenance information problems. However, it is a first steptoward a comprehensive understanding of provenance. We use the table rep-resentation of provenance with some visual aid to give a fair baseline to theuser. There are no other current approaches that can offer a comparablevisualization. Work-flow provenance systems work with different semanticsand other database approaches offer little in terms of user interface we couldcompare against. To make this a fair comparison, no other features such assearch, filter, or coloring were enabled in the user study. Enabling such fea-tures Pastwatch would likely perform above the numbers seen in the results.343.5 Related workProvenance Database Systems. Data provenance is studied extensivelyin the database literature. One of the earliest applications of data prove-nance is lineage in data warehouses as seen in WHIPS [CW00]. It generatesthe provenance of views in a data warehousing environment and supportsa manipulation language that extends SQL. The provenance information inWHIPS is the view definition and source tuples. DBNotes [CTV05,BCTV05]is a database annotation system that uses where-provenance. In DBNotes,the provenance information is simply user-made annotations propagated withthe results. DBNotes does not support aggregation due to the semanticsused and the way annotations are managed. Orchestra [KIT10] is a col-laborative data-sharing system where users share data using schema map-pings; it uses provenance semirings to represent how-provenance informa-tion. Perm [GMA13] generates and queries provenance information usingeasily optimizable SQL. The semantics of Perm is similar to why- and where-provenance. We use Perm to generate the provenance we summarize. Moreapproaches are explored in data provenance surveys such as [CCT09,SPG05].Even though systems like WHIPS [CW00] and Perm [GMA13] offer exten-sible and simple SQL-like syntax, provenance information is still prohibitiveto users and can easily be overwhelming for large datasets. The naturalapproach would be to visualize this information.More recent systems include developing provenance systems as an ex-tra layer above the DBMS, such as [AFG+18]. Other systems include morefeatures to support provenance and probabilistic queries [SJMR18] or aimto improve the performance of provenance capture with optimization tech-niques [PW18].Provenance Visualizations. A lot of work on user interaction with prove-nance information has been done in the field of scientific work-flow prove-nance [KOF+16] [ZGSB04] [CH06] [BYB+13]. Such systems offer visual35graphs that represent the processes that produced or changed the data.Database provenance has different semantics that do not adhere to the samegraph-like representation without some modification. We also offer a sum-mary of provenance tuples as a means to make it easier for the user tounderstand provenance information.Provenance summarization. The most similar work to our work in sum-marization is [ABD+15] in which the provenance of an aggregate query isrepresented as a polynomial expression, i.e. how-provenance [ADT11]. Ourprovenance summaries are shorter polynomial expressions that highlight theimportant aspects of the original provenance expression. The quality of asummary depends on general measures such as its size and its distance withthe original expression [ABD+15]. The algorithm for generating these sum-maries does not involve aggregated values within the data and thus can failto capture the user’s interest [ABD+15]. We utilize quantitative attributes inthe data, such as revenue, to make more meaningful summaries. We discussmore general summarization methods in the next chapter.3.6 Conclusions and Future WorkIn this chapter, we have looked extensively at provenance research. We haveidentified the most desirable features in a provenance system and used themto implement Pastwatch. We developed Pastwatch to support data explo-ration using provenance information. Pastwatch is ideal for broad explorationwith little knowledge of provenance semantics or the data itself.We used this system to develop a visualization component to visualizethe provenance of query results and explore provenance information. Weperformed a user study to validate it. The results of our user study showthat Pastwatch makes it easier for users to perform tasks with the data and tofind answers faster. Our summarization approach for aggregation provenancemakes it easier for users to find relevant tuples. We believe that a solution36that makes provenance information more manageable for users fills a gap inthis area and is a valid contribution to this field of research. It is also afirst step toward better integration of provenance information within datasystems.However, there is still a lot to be done in this field before a single approachis deemed complete. The size of the provenance data is still too large to han-dle, and scalability is a real concern. We feel that solutions in the vein ofPastwatch are a step in the right direction. In terms of data summarization,more research needs to be done to make sure summaries are comprehen-sive and cover all users’ needs. In the next chapter, we delve deeper intothe summarization of provenance information and present different types ofsummaries to extend the work we started here.37Chapter 4Provenance summarization4.1 IntroductionAs explained in Chapter 3, there is little research that focuses on present-ing database provenance information in a way that is not overwhelming tousers. Using existing provenance database systems without prior knowledgeof provenance models or the data itself can be overwhelming. Furthermore,provenance information can increase the data size considerably. This canhave serious implications on both storage and usability. We argue, as moti-vated in the previous chapter, that data provenance needs to be summarizedto support broad exploration. We made a first attempt at summarizing andpresenting provenance information in Chapter 3. In this chapter, we extendthis work to produce more comprehensive summaries for different scenarios.This chapter studies provenance summarization and exploration for aggre-gate query results in relational databases. We focus on aggregation queriesbecause they are common in database applications and their provenanceposes a greater challenge compared to other types of queries since it is usu-ally large and difficult to explore. The following running example explainsthe problem and our idea of our solution.Example 8. Consider the following aggregate SQL query, Q1, over the IMDB38table in Table 4.3 that contains data about a few movies and their respectivedirectors from the IMDB dataset.1Q1 : SELECT Gender, SUM(Rev) AS SumRevFROM IMDB GROUP BY GenderThe query asks for the sum of the revenues of the movies directed bydirectors of different genders. Table 4.1 shows Q1’s result. For answer a2,highlighted in Table 4.1, the provenance contains all the male directors andtheir movies. In this example, the provenance consists of seven tuples inTable 4.3; however, in practice, querying millions of movies and directors inthe IMDB dataset would yield a much larger number of tuples, which wouldhinder free-form exploration. Thus, instead of the full provenance, the userwould benefit from a summary.A summary can provide information showing that the revenue is dom-inated by a small set of movies allowing the user to see that the data isbadly skewed. A different type of summary could show that movies made bymale and female directors have different revenue patterns. This shows theuser that any analysis of the two groups needs to account for factors such asgenre, duration, and production costs. We will show summaries that can aidusers in those scenarios in Examples 10 and 11 ID Gender SumReva1 Female 624.6 M$a2 Male 4.208 B$Table 4.1: Q1’s resultID Gender Genre CountMa3 Male Drama 2a4 Female Comedy 2a5 Male Action 3a6 Male Comedy 1a7 Male Horror 1Table 4.2: Q2’s resultOur provenance summaries consist of rules that summarize groups oftuples. These rules were introduced for summarizing relational data and are1https://developer.imdb.com39ID Title Year Genre Rating Rev (M$) Country Duration Director Gendert1 Lincoln 2012 Drama 8 275.3 US 120 min Steven Spielberg Malet2 Sicario 2015 Drama 8 84.9 US 90 min Denis Villeneuve Malet3 Crimson Peak 2014 Horror 7 74.7 Mexico 90 min Guillermo del Toro Malet4 Bonjour Anne 2014 Comedy 5 8.9 US 90 min Eleanor Coppola Femalet5 The Terminal 2004 Comedy 7 219.4 US 90 min Steven Spielberg Malet6 Pacific Rim 2013 Action 7 411.5 Mexico 120 min Guillermo del Toro Malet7 Furious 7 2015 Action 8 1.516 B$ Australian 150 min James Wan Malet8 Jurassic World 2015 Action 8 1.627 B$ US 150 min Colin Trevorrow Malet9 Mamma Mia 2008 Comedy 6 615.7 US 120 min Phyllida Lloyd FemaleTable 4.3: IMDB tableID Country Duration Gender Cvg(%) Imp(%)s1 US ? Male 57 52s2 ? 90 min Male 42 9Table 4.4: A basic summaryID Country Duration Gender Cvg(%) Imp(%)s3 ? 150 min Male 28 74s4 US ? Male 57 52Table 4.5: An impact summaryID Country Duration Genre Cvg a4 Cvg a6c1 ? 90 min Comedy 50 100c2 US 120 min Comedy 50 0Table 4.6: A comparative summary40applied in several frameworks for other purposes [WZRY18,JGP16,JGMP15,EGAG+14] (see Section 4.2 for detail). Before we explain our provenancesummaries, we briefly review these rules and the summaries they producein [JGP16]. We refer to those summaries as basic summaries. We position oursolution as different summaries that can help users in the scenarios mentionedin Example 8.Example 9. A summarization rule over a relation is a tuple of the sameschema with some wild-card values, ?s, that match any value in the relationand enable the rule to cover and summarize several tuples [JGP16]. Forexample, rule s1 in Table 4.4 covers movies made in the US and directed bymale directors. A basic summary of a relation is a set of k rules, each of whichsummarizes some “interesting” aspects of the relation. Table 4.4 is a basicsummary of IMDB (Table 4.3) with k = 2, where we omitted the attributeswith ?s across different rules, e.g. Title and Rev. The score of a rule dependson its weight and coverage. The weight specifies how informative the rule isand is measured by the number of non-? values in the rule, whereas coverageis the number of tuples in the relation covered by the rule [JGP16]. Forexample, the coverage and weight of s1 are 4 (57% of the 7 movies directedby males) and 2, and its score is 4×2. In Table 4.4, the coverage percentagesare shown as values of a new attribute. We will use the basic summaries and the summarization rules in Exam-ple 9 and present two types of provenance summaries, impact summaries andcomparative summaries, which we explain using the running example. Whilebasic summaries are effective in summarizing a table, they are not as helpfulin summarizing the provenance of aggregate queries. Specifically, the scoreof a rule in a basic summary is independent of how much the tuples coveredby the rule contribute to the aggregate result in the answer. We proposeimpact summaries to resolve this issue.Example 10. Table 4.5 shows an impact summary of the provenance of a2from Table 4.1. Rules in this summary offer advantages over the rules in the41basic summary. Impact summaries contain rules, such as s3, that considerthe provenance tuples’ impact on the aggregate query answer. They differfrom basic summaries with rules, such as s2, that cover more tuples. s3 coversfewer tuples than s2, but the tuples covered by s3 account for a much higherimpact (74%) than the tuples covered by s2 (9%) because long movies (150minutes) include blockbusters (i.e. high revenue movies) such as JurassicWorld and Furious 7. We also introduce a second type of provenance summaries, comparativesummaries, that highlight the similarities between the provenance of twoanswers to an aggregate query and apply the summarization rules.Example 11. To explain comparative summaries, consider the followingaggregate query, Q2, that asks the number of directors from each gender andmovie genre.Q2 : SELECT Gender, Genre, COUNT(∗) AS CountMFROM IMDB GROUP BY Gender, GenreThe query result is shown in Table 4.2. Consider two highlighted answertuples a4 and a6, that specify the number of female directors and male direc-tors of comedy movies. Table 4.6 is a comparative summary with a rule thatcovers tuples from the provenance of both answers. The score of a rule insuch a summary depends on how many tuples it summarizes from the prove-nance of both selected answers. Comparative summaries can help users findsimilar tuples that contributed to the query answers. In Table 4.6, the newattributes show the coverage percentages of the tuples from the provenanceof a4 and a6, which help the user quickly identify key differences between thetwo groups. For example, c1 is a rule that shows that movies in the comedygenre that are of length 90 minutes are common for both male and femaledirectors but make a larger percentage of the movies made by females. c2shows that female directors have longer movies that span about 120 minutesthan male directors. These two rules highlight important differences between42the 2 groups which can compel the user to dig deeper and analyze individualmovies that may have a different sub-genre or may even be misclassified.Comparative summaries differ from basic summaries as they summarizeprovenance tuples from two sets of tuples, unlike basic summaries that sum-marize a single set. Note that comparative summaries cannot be reducedto basic summaries by using the union of the two sets. In particular, if thetwo sets are not of similar size, the basic summaries will be dominated byrules that cover the larger set. We present more examples that illustrate theusefulness of our summaries in our case study in Section 4.6.5. Also note that while we apply comparative summaries for provenancesummarization, in general, they can be used to summarize similarities anddifferences between two sets of tuples of the same schema and for otherpurposes, beyond provenance summarization.To specify good impact summaries and comparative summaries, we definescore functions by blending the factors in Examples 10 and 11, e.g. coverage,impact, and weight.We present impact and comparative summaries to the user as interactivesummarization rules that allow the user to explore the data. In our runningexample, the user can select an answer for which to create an impact summaryor a pair of answers for comparative summaries. Then the user can continueto explore the provenance by selecting one of the rules and applying thedrill-down operator that shows super-rules with fewer ?s and reveals moredetail of the provenance covered by the selected rule. Unlike the solutionin [JGP16], which produces summarization rules over a single relation, weuse our approaches to produce summarization rules for provenance tuplesthat may involve multiple relations (cf. Section 4.3 for detail).4.1.1 ContributionsOur contributions in this chapter are as follows:43• We define provenance summaries, impact summaries, and comparativesummaries, for the general form of aggregate SQL queries. We formalizescore functions for these summaries and present the summarizationproblems for finding the best provenance summaries (Section 4.3).• We present efficient algorithms for producing both impact and compar-ative summaries (Section 4.4).• We present novel interaction methods and visualization techniques ina user interface for impact and comparative summaries (Section 4.5)• We conduct performance experiments and a user survey to show thatour proposed solutions perform well and provide useful summaries (Sec-tion 4.6).4.2 Related workProvenance summarization. The most similar work to our work in thischapter is [ABD+15] in which the provenance of an aggregate query is rep-resented as a polynomial expression, i.e. how-provenance [ADT11]. Ourprovenance summaries are shorter polynomial expressions that highlight theimportant aspects of the original provenance expression. The quality of asummary depends on general measures such as its size and its distance withthe original expression [ABD+15]. The algorithm for generating these sum-maries does not involve aggregated values within the data and thus can failto capture the user’s interest [ABD+15]. We utilize quantitative attributesin the data, such as revenue, to make more meaningful summaries. Our userstudy shows that users favor impact summaries over basic summaries.Provenance Database Systems. There are several frameworks for gener-ating and managing provenance data in data management [CW00, GMA13,AFG+18, PW18, SJMR18]. Perm [GMA13] is a common provenance frame-work that manages provenance information using easily optimizable SQL.44The semantics of Perm are similar to why- and where-provenance. We usePerm to generate the provenance we summarize. Even though systems likeWHIPS [CW00] and Perm [GMA13] offer extensible and simple SQL-likesyntax, provenance information is still prohibitive to users and can easily beoverwhelming for large datasets. The natural approach would be to sum-marize this information. Our provenance summaries provide a tool for nav-igating and understanding provenance data and can be used in applicationsthat require understanding the provenance of aggregate queries, including re-producibility [RDA+20], collaborative scientific research [JDB20, CLMT22,SdOVM18], query composition, and query debugging [ADG18,ME22].Query Explanation. Query explanation is one of the main applicationsof our provenance summaries. It has been extensively studied with manytechniques to generate explanations. Sensitivity-based techniques generateexplanations using intervention and measuring the impact of data modifi-cation on query answers [WM13]. Complaint-based techniques start with auser complaint about query answers (e.g., why an aggregate value in theanswer is higher than expected) and find records or predicates that explainthe unexpected answer [RS14,ROS15]. Counterbalancing techniques explainoutliers in aggregate query answers using related outliers in the oppositedirection while providing counterbalance [MZGR19, MZL+19]. Recent tech-niques use repair models and anomalies [HW22], provenance augmented withcontext [LLM+22], human-in-the-loop and user interactions [MCB+20], andcontrasts between aggregate query answers [AKS+18] to generate explana-tions.Our application of summarization rules differs from the existing appli-cations in [WM13, ROS15]. Those approaches use rules to explain outliersor high/low results so their summaries are more specific. This makes theirtechniques inapplicable to our problem without modification. Likewise, ourgeneral-purpose summaries would not work to explain specific problems withquery results such as outliers. We use summary rules for summarizing the45provenance of aggregate queries and produce general summaries for prove-nance exploration. This requires new techniques for finding rules that con-sider the impact of the tuples covered by the rules on the aggregate resultand finding interesting patterns that do not explain any specific patterns. Weintroduce impact as a new quality metric to find the best provenance sum-maries for aggregate queries. The impact of a rule depends on the impact ofthe tuples covered by the rule on the query answers. In our experiments, weuse these metrics to compare our summaries with basic summaries, we donot conduct experiments against more specialized systems. While our tech-nique focuses more on impact due to the new score function, it still worksfor high coverage due to the algorithm we use. Therefore, our approachand [JGMP15] are very closely related. Another reason we did not compareagainst the system in [ROS15] is their use of entropy to generate rules. Asexplained in Appendix B.4, entropy-based functions cannot be used with ouralgorithm out of the box to generate rules with any guarantees. If we wereto repurpose the approach in [WM13] that uses sensitivity analysis to gen-erate general rules like ours, their approach would produce similar results asthose techniques are very similar to ours. Other factors for not comparingagainst such systems include time and availability of code. The implementa-tion of [JGMP15] we used was our implementation made specifically for thisproject, which we extended and modified to develop our approach. It wassimply not feasible to implement other systems within the time frame of theproject.Statistical methods. While we do not employ a statistical approach tofinding summaries, our approach has some statistical properties and bearssimilarity to known statistical approaches. Our approach most of all resem-bles regression [Fre09]. Wherein the aim of regression is to find relationshipsbetween dependent and independent variables for the purpose of prediction,our aim is to find the highest impact tuples on an aggregate value usingknown values stored in the database. Other similarities appear in our sam-46pling approach, random sampling allows for the probabilistic choosing oftuples to summarize. We employ a sampling approach that prioritizes high-impact tuples that lowers the effect of probability and relies mostly on impactmeasures.Summarization Rules. Summarization rules like those we use are appliedin many applications, including summarizing query results [WZRY18], outlierdetection and explanation [MZL+19,WM13], data quality analysis [GKKS10,WDM15], and feature selection [EGFG+18,EGAG+14] (see [DGS22] for a re-cent survey). Our purposes differ from these applications as we use the rulesfor summarizing the provenance of aggregate queries. Several quality metricsare used for finding summarization rules. Coverage measures the number ofrecords summarized by the rules and weight specifies the amount of informa-tion provided by a rule and is often measured by the number of non-? valuesin a rule [JGMP15,JGP16]. Diversity is another metric that determines theuniqueness of the rules and their values in a summary [WZRY18]. We in-troduce impact as a new metric to find the best provenance summaries foraggregate queries. The impact of a rule depends on the impact of the tuplescovered by the rule on the query answers. In our experiments, we use allthese metrics to compare our summaries with basic summaries.4.3 Formalizing Provenance SummarizationProblemsIn this section, we define impact summaries and comparative summaries,and we formalize the summarization problems for finding these summaries.A key challenge is to define new score functions that specify these provenancesummaries while preserving the sub-modularity property needed to computethem efficiently. Our new score function for impact summaries computes anaccumulative impact of the provenance records on the query answer in Sec-tion 4.3.2. We present an extension of the score function in Section 4.3.2 to47solve a problem that occurs when summarizing the provenance of some ag-gregate queries, such as queries with MIN and MAX aggregate functions andqueries with joins. We show how this extension works for queries with joinin Section 4.3.3. We then define a score function for comparative summariesby extending the coverage of summarization rules to a pair-wise coverage ofthe provenance of two answers in Section 4.3.4.4.3.1 Basics and Problem SettingWe assume an aggregate query Q over a database schema S as follows:Q: SELECT G1, ..., Gm, f(G∗) AS G FROM RWHERE conditions GROUP BY G1, ..., GmListing 4.1: The general form of aggregate queriesIn Q, {G1, ..., Gm, G∗} ⊆ R, f is an aggregate function, such as COUNTand AVG, and conditions contains a conjunction of conditions on R. G∗ isthe aggregated attribute (e.g. Revenue). We discuss more general queriesobtained by relaxing Q to aggregate-select-projection-join (ASPJ) queries inSection 4.3.3.Consider a database D of the schema S. For a ∈ Q(D), we define Qa inListing 4.2 as a query that returns a[G].Qa: SELECT f(G∗) FROM R WHEREconditions AND G1 = a[G1] AND ... Gm =a[Gm]Listing 4.2: A query that returns the aggregate value in tExample 12. For Q1 in Example 8, G1 = Gender, G = SumRev, G∗ = Rev,and f is SUM. For a2 ∈ Q1(IMDB), Qa21 is the following query:SELECT SUM(Rev) FROM IMDB WHERE Gender=MaleIt returns a2[SumRev] = 4.208B$, which is the sum of the revenues of themovies directed by male directors. 48For a ∈ Q(D) and R ∈ D, we use Ra ⊆ R to refer to the lineage of Qa(D)in R. For example, IMDBa2 for a2 ∈ Q1(IMDB) contains all the tuples inIMDB excluding those movies that are made by non-male directors.4.3.2 The Impact Summarization ProblemAs motivated in Section 4.1, an impact summary summarizes the prove-nance of a tuple in the result of an aggregate query. It does a better job ofshowing the impact on aggregate values compared to the basic summariesin Section 2.2. Impact on a numeric value (e.g. Revenue) is a very usefultool for summarization. Moreover, basic summaries and their score functioncannot address aggregate functions beyond Count, whereas the impact func-tions we present can cover Sum, AVG, MIN, and MAX. To define the impactsummarization problem, we specify the new score function, IScore. Similarto the score in Definition 2.6, we define IScore (impact score) for a list ofsummarization rules S.Consider a tuple a ∈ Q(D) and a relation R ∈ D with schema R and thelineage Ra 6= ∅. Let S be a set of rules over R. The impact score of S is themaximum impact score between every possible list that contains the rules inthe set:IScorea(S) =∑si∈SImpacta(si, S)×Weighta(si), (4.1)IScore considers the impact of the provenance tuples in Ra covered by rulesin S on tuple a in the query result. This is noted by the superscript a,R inIScorea and is applied by replacing MCount(si, S) with Impacta(si, S),Impacta(si, S) =∑t∈MCover(si,S)Impacta(t). (4.2)49where Impacta(t) = |Qa(D) − Qa(D \ {t})| is the impact of each tuple ton answer a using sensitivity analysis. It is a technique that measures thesensitivity of a query to a tuple or a set of tuples by comparing the answersto the query with and without the tuple(s) in the database [KLD11,WM13].In Equation 4.2, we apply this analysis w.r.t. the tuples in the marginalcover set MCover(si, S) and consider Qa. We omit relation names, e.g. R inEquations 4.2 and 4.1, in the superscripts when they are clear from context.Example 13. Consider Q1 and a2 ∈ Q1(IMDB) in Example 8, and rule sum-maries S = {s2} and S ′ = {s3} with s2, s3 in Tables 4.4 and 4.5. Based on thescore function in Definition 2.6, Score(S) = MCount(s2, S) ×Weight(s2) =3× 2 and Score(S ′) = MCount(s3, S)×Weight(s3) = 2× 2. The new scoresbased on Equation 4.1 are IScorea2(S) = Impacta2(s2, S) × Weight(s2) =379 M$× 2 and IScorea2(S ′) = Impacta2(s3, S)×Weight(s3) = 3.143 B$× 2.s2 covers a big part of a2’s provenance while s3 covers the most impactfulparts of the provenance of a2. Therefore, S′ is preferred over S w.r.t. IScore.Definition 4.1 (Impact summary and the impact summarization problem).Given relation R ∈ D, query Q over D, a tuple a in the answer Q(D), and aconstant k, the impact summarization problem is an optimization problemto find a summary S of size k with maximum argmaxS(IScorea(S)). S is animpact summary.The impact summarization problem is NP-hard because it extends thesummarization problem [JGP16] (Chapter 2, Section 2.2), which has beenproved to be NP-hard. The BRS baseline algorithm relies on the sub-modularity of Score in Definition 2.6. In Section 4.4, we present the IPSalgorithm for finding impact summaries. To guarantee the algorithm’s ap-proximation, we need to verify whether IScore is sub-modular.Theorem 1. IScore in Equation 4.1 is sub-modular.50The proof of Theorem 1 is based on that the marginal impact of everytuple a ∈ Q(D) in Equation 4.2, i.e. |Qa(D)−Qa(D\{t})|, is independent ofthe selected rules in S and it is only considered in the marginal score of onerule in S (see B.2 for the complete proof). As a result of this theorem, wecan efficiently generate approximately optimal impact summaries w.r.t. ourscore function.In the rest, whenever it is clear from context, we omit the superscripts,e.g. we use IScore instead of IScorea.Impact Summaries with ContingencyWe now explain a shortcoming of the impact definition in Equation 4.2 andwe present our solution to extend the impact with contingency.ID Title Year Genre Rating Rev (M$) Directorr1 Lincoln 2012 Drama 8 275.3 Steven Spielbergr2 Sicario 2015 Drama 8 84.9 Denis Villeneuver3 Crimson Peak 2015 Horror 7 74.7 Guillermo del Toror4 Bonjour Anne 2016 Comedy 5 8.9 Eleanor Coppolar5 The Terminal 2004 Drama 7 219.4 Steven SpielbergTable 4.7: Movies tableID Name Gender Countryr6 Steven Spielberg Male USr7 Denis Villeneuve Male Canadar8 Guillermo del Toro Male Mexicor9 Eleanor Coppola Female USTable 4.8: Directors tableExample 14. Consider the following query that asks the maximum ratingof movies from each genre in Table 4.7.51Q5 : SELECT Gender, MAX(Rating) AS MaxRFROM Movies GROUP BY Genrea = (Drama, 8) is an answer to Q5 with provenance which contains allthe drama movies. There is no meaningful impact summary for Ra usingthe score function in Equation 4.1 and the impact value in Equation 4.2.This is because IScore is 0 for every summary. This happens because thereare multiple tuples with the maximum rating 8 and removing each one fromMoviesDirectors does not change a. As a result, Impacta is 0 for every ruleand score is 0 for every summary. Example 14 shows that the sensitivity analysis used in the definition ofImpact in Equation 4.2 is not effective for certain queries, e.g. some querieswith MIN or MAX aggregate functions. To solve this problem, we define anew Impact, Impacta(t), that is based on the notion of the contingency set.Impacta(t) is more general and extends the Impact in Equation 4.2 to addressthe shortcoming in Example 14.Definition 4.2 (Contingency Set). Consider a query Q in Listing 4.1 overa database D, a tuple a ∈ Q(D), the query Qa as defined in Listing 4.2, andRa (the provenance of a in R). The contingency set for t ∈ Ra denoted byCa(t) is a minimal set of tuples in Ra such that Qa(D) 6= Qa(D \Ca(t)∪{t})and Qa(D) = Qa(D \ Ca(t)) = Qa(D \ {t}).Intuitively, the contingency set Ca(t) is a minimal subset of Ra that mustbe removed from R before Qa becomes sensitive to a. A particular case iswhen Ca(t) = ∅, which means removing a immediately changes Qa(D). Thenotion of contingency is first introduced in causal inference in AI to specifythe degree of responsibility [CH03, EL02]. In data management, Meliu etal. use the contingency set of a tuple to define its responsibility w.r.t. aquery answer [MGMS10,MGNS11]. Definition 4.2 is adapted from [MGNS11,Definition 2.1].52Example 15. In Example 14, Ca(r1) = {r2} and Ca(r2) = {r1}. This isbecause removing either r1 or r2 does not change the answer but removingboth does. We extend Impacta(t) to capture contingency:Impacta(t) =|Qa(D)−Qa(D \ Ca(t) ∪ {t})||Ca(t)|+ 1 . (4.3)In Equation 4.3, the impact of each tuple is computed w.r.t. its contingencyset Ca(t). The denominator |Ca(t)| + 1 is called the responsibility of a forthe answer Qa(D) [MGMS10].Example 16. Consider summary {s} for a = (Drama, 8) ∈ Q5(Movies)in Example 14 where s = (Title : ?,Year : 2012,Genre : Drama,Rating :?,Rev : ?,Director : ?). The rule only covers r1, which is the only dramamovie released in 2012, i.e. MCover(s, {s}) = {r1}. The score of {s} is 0if we use the impact function in Equation 4.2. According to Equation 4.3,the new impact value is IScorea({s}) = Impacta(s, {s})×Weighta(s) = ((8−7) × 1/2) × 1 = 1. This is because the contingency set of r1 is {r2}, theresponsibility of r1 is 1/2 and removing r1 and r2 from Movies changes theanswer to Qa5 from 8 to 7. Weighta(s) = 1 because s has two non-? valuesincluding Drama from a. The new Impacta(t) definition in Equation 4.3 is compatible with theimpact in Equation 4.2 in the sense that the former reduces to the latter whenthe aggregate function is SUM or COUNT. This is because the contingencyset of every tuple with a positive impact value according to Equation 4.2will be empty, its responsibility is 1, and therefore Equation 4.3 reduces toEquation 4.2. The score function with the new impact value is sub-modularwhich can be proved similar to Theorem 1 (see B.2).53The connection between impact summaries and provenance of ag-gregate queries:The provenance of aggregate query in Listing 4.1 is of the form r1⊗ r1[G∗]⊕r2 ⊗ r2[G∗] ⊕ ... ⊕ rn ⊗ rn[G∗] where ris are tuples in R and G∗ is the ag-gregate result in the query. Basic summaries can summarize the tuples riin the provenance but do not represent the numerical values of ri[G∗]. Theimpact summaries include these numerical values in the impact of summa-rization rules to define their score and therefore represent entire provenancesummaries of aggregate queries.4.3.3 Impact Summaries for Queries with JoinsThe class of queries we considered in Listing 4.1 does not allow joins, whichwe study in this section. Consider queries of the following form that is definedover a database D including relations R1, R2:Q: SELECT G1, ..., Gm, f(G∗) AS GFROM R1 AS rel1, R2 AS rel2WHERE conditions GROUP BY G1, ..., GmListing 4.3: The general form of aggregate queries with joinIn Listing 4.3, we assume G1, ..., Gm are attributed in either R1 or R2. With-out loss of generality, we assume G∗ is in R1. Our discussion in this sectioneasily extends to joins with multiple tables. We discuss the challenges ofextending this general form to more complex queries, e.g. nested queries, inSection 4.2. Without loss of generality, we assume the join conditions arecaptured by the conditions in the where-clause.For a tuple a ∈ Q(D), we define Qa similar to Listing 4.2 but over Ri.We also define Rai as the lineage (provenance) of Qa(D) in Ri, i ∈ {1, 2}.Example 17. Consider Q6 over Movies and Directors in Tables 4.7 and 4.8that asks the sum of the revenues of the movies directed by directors ofdifferent genders.54Q6: SELECT d.Gender, SUM(m.Rev) FROMMovies m, Directors d WHERE m.Director = d.NameFor the answer a = (Male, 654.3M$), Qa6 is the following query that returns654.3M$:Qa6: SELECT SUM(Rev) FROM Movies m, Directors dWHERE m.Director = d.Name WHERE d.Gender = MaleThe provenance of a = (Male, 654.3M$) contains its lineage tuples in bothMovies and Directors : Moviesa = {r1, r2, r3, r5} contains every movie di-rected by a male director, and Directorsa = {r6, r7, r8} are male directorswith at least one movie. The impact summaries in Section 4.3.2 summarize tuples in only onetable. The impact summary for a join query of the general form in Listing 4.3consists of two table summaries as defined next.Definition 4.3 (Provenance Summaries for Join Queries). Given a query Qof the form in Listing 4.3 over database D, and an answer tuple a ∈ Q(D),an impact summary is a set Sa = {〈rel1, S1〉, 〈rel2, S2〉} in which rel1 and rel2are table aliases for R1 and R2 in Q and S1 and S2 are table summaries onR1 and R2, respectively.In the impact summary in Definition 4.3, we use aliases rel1 and rel2 todistinguish between the summaries over the tables in the query. It allowsthese summaries to represent queries with self-join and queries with joinsover multiple tables.To define the provenance summarization problem for queries with join,we need to define the score of a summary specifying what constitutes a goodsummary. Similar to the impact summaries in Section 4.3.2, we consider thecoverage and the impact of the rules in the summaries. But additionally,we also take into account the relationship between the rules in the tablesummaries S1 and S2 to make sure they cover tuples that participate in thejoin operation.55The impact score of a summary S for an answer a to the join query isdefined as IScorea(S) =∑i∈{1,2} IScorea(Si) where IScorea(Si) is defined byEquations 4.1 and 4.2. To capture the relationship between the two tablesummaries S1 and S2, we define the impact of a tuple in Equation 4.2, i.e.Impacta(t), as follows. For t1 ∈ Ra1, the impact is defined by Equation 4.3and considering the contingency set for t1 if there is t2 ∈ Ra2 that is coveredby S2 and t1 and t2 satisfy the conditions in Q. Similarly, we define theimpact of tuples in Ra2.Example 18. Consider SM = {sm} and SD = {sd} as sets of rules overMovies and Directors (Tables 4.8 and 4.7). sm = (Title : ?,Year : ?,Genre :?,Rating : 7,Rev : ?,Director : ?) is a rule that summarises movies withrating 7, i.e. r3, r5, and sd = (Name : ?,Gender : Male,Country : US) coversmale directors from the US, i.e. r6. The impact of sm is r3[Rev] + r5[Rev] =294.1 and the score of SM is Impacta(sm) × weighta(sm) = 294.1 × 1. Theimpact of sd only depends on r6, i.e. Steven Spielberg. Since he directed twomovies in the Movies relation with revenues 275.3 and 219.4, the impact of sdthat covers him is 275.3+219.4 and that the score of SD is 2×(275.3+219.4)since the weight of sd is 2. 4.3.4 The Comparative Summarization ProblemAs motivated in Section 4.1, comparative summaries best summarize thesimilarities between the sets of provenance Ra and Ra′for a, a′ ∈ Q(D).To define the comparative summarization problem, we present the followingscore function that measures how well rules si ∈ S summarise Ra and Ra′(we omitted R is the superscripts similar to Equation 4.2 and 4.1):CScorea,a′(S) =∑si∈SMPCounta,a′(si, S)×Weighta,a′(si), (4.4)56In CScore (the comparative score), MPCounta,a′(si, S) is the marginal num-ber of tuple-pairs from Ra and Ra′that are covered by si. It is marginalbecause it does not count the pairs that are already covered by previous rulessj, j < i. The weight function Weighta,a′(si) returns the number of non-? val-ues in si that do not appear in a and a′. Using the standard marginal countfunction for the provenance of two tuples a and a′ where Ra is much biggerthan Ra′would result in a summary where Ra would dominate. CScore givesa summary that covers both Ra and Ra′in a balanced way.Example 19. In Example 11, the comparative score of {s2} for summarizingthe similarities between the provenance of a4, a6 inQ2(IMDB) is CScorea4,a6({s2}) =MPCounta4,a6(s2, {s2})×Weight(s2) = 0× 1. The marginal pair count MP-Count is 0 because s2 does not cover any pair from the provenance of a4, a6.For the set of rules {c1}, the score is the following: CScorea4,a6({c1}) =MPCounta4,a6(c1, {c1})×Weight(c1) = 1× 2. MPCount is 1 since c1 covers apair of tuples from the provenance of a4 and a6. The weight of c1 is 2 becauseit has 2 non-? values. Definition 4.4 (The comparative summarization problem). Given databaseD, relation R, query Q, tuples a, a′ in Q(D), and a constant k, the compara-tive summarization problem is to find a summary S of size k with maximumCScorea,a′(S).Theorem 2. CScorea,a′in Equation 4.4 is sub-modular.Theorem 2 holds because every pair of tuples in Ra, Ra′are countedonce in MPCounta,a′. As a result if S ⊇ S ′ then MPCounta,a′(ci, S) ≤MPCounta,a′(ci, S′). The detailed proof of the theorem is in B.2. We presenta greedy algorithm to find comparative summaries in Section 4.4. As a resultof Theorem 2, we can claim the algorithm gives an approximately optimalset of rules w.r.t. our score function in Equation 4.4. We study extensionsof comparative summaries considering the difference between the provenancetuples and with joins in B.3.574.4 Summarization AlgorithmsIn this section, we present the impact provenance summarization algorithm(IPS) and the comparative provenance summarization algorithm (CPS ) forfinding impact summaries and comparative summaries. These algorithmsextend the BRS algorithm in [JGP16] to summarize the provenance of queriesusing the new score functions in Section 4.3. In our description of IPS andCPS , we omit the optimization details of the BRS algorithm to focus on theextension for summarizing provenance, but we apply those optimizations inour experiments.Algorithm 1 shows the detail of IPS that takes as input D, R ∈ D, Q,an answer a ∈ Q(D), and value k and computes an impact summary S ofRa with k rules. First, it generates the provenance tuples Ra ⊆ R usingan existing provenance framework, such as Perm [GMA13] (Line 1). Thenit computes the impact of each tuple in Ra on Q(D), I(t) is the functionto calculate the impact of a tuple t (Line 2). The algorithm uses Ra andthe impacts to find the k best marginal rules by calling BestMarginalRule ktimes and returns the results as S. The best marginal rule s maximizes thescore of S ∪ {s}.Algorithm 1: The IPS AlgorithmInput: Database D, relation R, query Q, a ∈ Q(D), k.Output: A set of rules S.1 S := ∅, Ra := Provenance(D,R,Q, a)2 foreach t in Ra do I(t) := |Qa(D)−Qa(D \ {t})|;3 for i from 1 to k do4 s := BestMarginalRule(Ra, a, S, I)5 S := S ∪ {s}6 return SAlgorithm 2 shows the main steps of BestMarginalRule. To find the bestmarginal rule, s, the procedure maintains two sets of new and old candidaterules, Sn and So respectively. At the j-th iteration of the main loop, it58generates every possible candidate rule of weight j, stores them in Sn, andcomputes their marginal scores in M . For j > 1, the procedure generatesthe new rules in Sn using the rules with weight j − 1 in So (Line 4). Forexample, if so = (A : ?,B : b) is in So, sn = (A : a,B : b) will be added toSn. Here sn is a super-rule of so and so is a sub-rule of sn.Before computing the scores (Lines 11-14), the procedure prunes somecandidate rules that cannot beat the best rule s from the previous iterationswithout computing their scores (Lines 5-10). For each sn, the procedurecomputes an upper bound Un using the scores of its sub-rules so that arecomputed in the previous iteration. The value (M(so)/Weighta(so))× |R| inLine 8 is an upper bound for the marginal score of sn, since the impact ofsn is always less than M(so)/Weighta(so), which is the impact of its sub-ruleso, and the weight of sn can never exceed |R|. The procedure removes thecandidate sn from Sn if its score’s upper bound is still less than the currentbest marginal rule s. In line 10, if no candidate remains after pruning Sn = ∅,the procedure stops and returns the best marginal rule s.The procedure computes the marginal score of candidate rule sn in Sn inLine 14 by adding the impact of every tuple t in Ra to M(s) if t is not coveredby any rule in S. At the end of each iteration in Line 15, the procedure checksfor the best marginal rule s in Sn and then updates So for the next iteration.The procedure returns s after checking every candidate rule.Algorithm 3 details CPS , which takes R, Q, k, and a1, a2 ∈ Q(D) andreturns a comparative summary S with k rules. The algorithm first computesthe provenance of a1, a2, then uses it to find the top k marginal rules bycalling BestComparativeMRule (Algorithm 4) k times. This procedure takesthe provenance sets Ra1 , Ra2 , and the set of rules S, and finds the rule thatbest summarizes Ra1 and Ra2 . It computes the marginal score of all rulesexcept those that are already in S and returns the one with the highest score.However, to compute the marginal scores, it only adds to the score of a ruleif it covers pairs of tuples t1, t2 from Ra1 , Ra2 that are not covered by any59Algorithm 2: BestMarginalRule(Ra, a, S, I)Output: A rule s with maximum marginal score.1 for j from 1 to |R| do2 if j = 1 then Sn := all rules with weight 1;3 else4 Sn := all weight-j super-rules of rules in So5 foreach sn ∈ Sn do6 Un :=∞7 foreach so ∈ So i.e. a sub-rule of sn do8 Un := min(Un,M(so)Weighta(so)× |R|)9 if Un<M(s) then Sn := Sn \ {sn} break;10 if Sn = ∅ then break;11 foreach sn ∈ Sn do M(sn) := 0 ;12 foreach t ∈ Ra not covered by rules in S do13 foreach sn ∈ Sn that covers t do14 M(sn) := M(sn) + I(t)×Weighta(sn)15 s := argmaxsn∈Sn(M(sn)), So := Sn16 return srule in S (Line 7).IPS differs the BRS algorithm (as detailed in [JGMP15]) since IPS gen-erates provenance and considers the impact values while it computes themarginal scores. The BRS algorithm prunes candidate rules in a way that issimilar to IPS with the difference that IPS uses impact values that can helpprune rules faster when the numerical attribute that is aggregated has skeweddata. The CPS algorithm is also different from the BRS algorithm becauseCPS generates provenance and computes the score function considering pairsof tuples.4.4.1 Computing Impacts and Contingency SetsSo far, in our problem definition in Section 4.3 and the summarization al-gorithms earlier in this section, we considered the general class of aggregate60Algorithm 3: The CPS AlgorithmInput: Database D, relation R, query Q, a1, a2 ∈ Q(D), value k.Output: A set of rules S.1 S := ∅2 Ra1 :=Provenance(D,R,Q, a1); Ra2 :=Provenance(D,R,Q, a2)3 for i from 1 to k do4 c := BestComparativeMRule(Ra1 , Ra2 , a1, a2, S)5 S := S ∪ {c}6 return SAlgorithm 4: BestComparativeMRule(Ra1 , Ra2 , a1, a2, S)Output: A rule s with maximum marginal score.1 Ms := 02 Sn := all possible rules that are not in S3 foreach cn ∈ Sn do4 M := 05 foreach t1 ∈ Ra1 , t2 ∈ Ra2 covered by cn do6 if no rule in S covers t1 and t2 then7 M := M + Weighta1,a2(cn)8 if Ms < M then c := cn,Ms := M ;9 return s61SQL queries in Listing 4.1. However, in our experiments, we focus on thesub-class of Aggregate-Select-Project-Join (ASPJ) queries with built-in ag-gregate functions for two reasons. First, they cover a wide range of queriesthat are used in practice. Second, we can compute the provenance sum-maries for these queries efficiently as we discuss in Section 4.4.2. Note thatcomputing the impact of tuples on the general class of aggregate queries inListing 4.1 is intractable since finding the contingency set for the provenancetuples is NP-hard in general [MGMS10]. In addition, computing the impactof the provenance tuples t on a general query Q with user-defined aggregatefunctions requires running, in the worst case, Qa(D \ D′) for every subsetD′ which can be costly. We can avoid this costly query execution for ASPJqueries as we explain next.In Line 2, IPS computes the impacts of provenance tuples t in Ra andstores them in I. For queries in our experiments, we can compute the impactsof tuples without running queries. For example for an Aggregate-Select-Project (ASP) query Q with SUM, the impact of t ∈ Ra is |t[G∗]|, and it is|t[G∗]||Ra| for queries with AVG. In Example 13, the impact of the movie t1 on thesum of revenues in Qa22 is the movie’s revenue, i.e. t1[Rev] = 275.3M$. For anASP query with MIN or MAX, computing the impact in Equation 4.3 requiresfinding the contingency set Ca(t). Although computing the contingency set isproved to be NP-hard for general SQL queries [MGMS10], we can efficientlycompute it for queries of the general form in Listing 4.1. If t[G∗] = a[G],which means t[G∗] is the min or max value in the answer, the contingency setis the set of all tuples t′ such that t′[G∗] = t[G∗]. In Example 14, a[MaxR] =t2[Rating] and Ca(t2) = {t8}. The impact of t is |t[G∗]−m||Ca(t)|+1 in which m is thesecond min or max value in Ra. In Example 14, the impact of t2 is8−72. Ift[G∗] 6= a[G], the impact of t is 0, e.g. the impact of t1 is 0 in Example 14. Wenote that computing the impact in O(1) would require an additional datastructure (e.g., a hash table) to find all rows with a particular value andassumes that there is some constant k such that there are no more than k62rows with the min/max value.For an ASPJ query of the general form in Listing 4.3, we compute theimpact of t ∈ Ra as we explained above for queries without joins. If t ∈ T a,the impact of t depends on values all the tuples t′ ∈ Ra that join with t,e.g. t′[Ai] = t[Bj]. We compute the impact of t using t′[G∗] for every t′. Forexample, for ASPJ queries with the SUM aggregate function, the impact oft is∑(|t′[G∗]|).4.4.2 Analysis of Summarization AlgorithmsThe cost of running IPS is divided into (a) generating Ra, (b) computing theimpacts in I, and (c) finding the best marginal rules. We only analyze thecost of (b) and (c) since (a) depends on the provenance framework. For thequeries in our experiments, the cost of (b) is O(n) with n = |R| because theimpact of each tuple can be computed in O(1) as noted in Section 4.4.1. Thecost of (c) is at most O(k × n2 × 2m) with m = |R| since there are at mostn2× 2m possible rules, and the cost of computing the marginal score of eachrule is n. The rule pruning technique helps reduce the cost to O(k×n2×m)(the detail of its analysis is in [JGMP15]). Therefore, the total cost of IPS isat most O(k×n2×m). The cost of CPS only consists of the cost of generatingRa1 , Ra2 , which we omit, and the cost of finding the best marginal rules inLine 4 of Algorithm 4. That cost is n2 since BestComparativeMRule iteratesover pairs of tuples in Lines 5-7 of Algorithm 4. That means the total costof CPS is O(k × n3 ×m).IPS and CPS only incur the approximation caused by the greedy ruleselection. The score functions in both algorithms are monotone since themarginal scores are non-negative. They are also sub-modular as we provedin Theorems 1 and 2. As a result, the algorithms have the approximationratio α = 1− 1e, i.e. the score of a result summary is greater than the optimalscore multiplied by α [NWF78].634.4.3 A note about samplingSampling is the most common technique to optimize the performance of sum-marization algorithms. It is used in [JGP16] and [EGAG+14] to run the sum-marization algorithm on smaller samples instead of the full data set |D|. Thesimplest form is to draw a random sample every time the algorithm is run.The downside to random sampling is the loss of accuracy. [EGAG+14] findthat their algorithm requires a very large sample size which is still prohibitiveto real-time performance. The solution is a dynamic sampling solution withestimates on the drawn sample. For our purposes, for IPS, we require asampling algorithm that estimates and maximizes the impact of rules in thesampled set. For CPS, we require a sampling method that maximizes cov-erage for the two sets (if looking for similarities) or differences between thetwo sets (if looking for differences).The interactive sampling method in [JGP16] is more suited to their ap-proach and the interaction method they employ. We propose a samplingmethod similar to the flashlight strategy described in [EGAG+14]. We startby running a CUBE query that takes in the top rules for impact. We filterout any low-impact rules and their associated tuples based on a thresholdvalue set by the user. This gives us a decent estimate of the real impactvalues. We run our algorithm on this sample. We use the same strategyfor drill-down operations and obtaining super-rules. We use this method forAVG and SUM, summaries for MAX and MIN is very fast operations withoutthe need for sampling.As we discussed in Section 4.4.2, CPS is more costly compared to IPSsince it compares pairs of tuples. Therefore, we implemented a similar sam-pling optimization to IPS for CPS that prunes the rules with low coverageon both provenance sets using a coverage threshold.Since we do not have access to the sampling method used in [JGP16],we perform our experiments without sampling to show how the two methodscompare in terms of raw un-optimized performance.64Furthermore, [FGS17] shows that random samples at certain sizes onlydegrade the quality of the summary by a small margin. The gains in per-formance are worth the small loss in accuracy. We employ both impact andrandom sampling as possible optimization options.4.5 User Interface and visualizationThe user interface and visualizations provide users with all the necessaryfacilities to explore the provenance summarization rules. Rules are presentedto the user in a way that helps them uncover insights about the data.The user starts by writing a query and seeing the results of the query.The user then clicks on one or more tuples and asks for a summary of theprovenance. We offer two different interfaces depending on the type of queryor question: (a) Impact summaries if the user clicks on a single tuple; thisincludes impact summaries for the results of queries with joins. (b) Compar-ative summaries if a user clicks on multiple tuples.For impact summaries, rules are presented as rows in a table (or multipletables when the query involves multiple tables) with a quality measure foreach rule. This quality measure is one of the following. Score: the scoreof a rule according to Equations 4.1 and Equations 4.4, which reflect thecontribution of each rule to the summary’s total score. Coverage: thefraction of provenance tuples that are covered by a rule. Impact: the impactof a rule normalized by the total possible impact. The impact and coveragevalues are not marginal and do not depend on the other rules in the summary.For impact summaries for queries that involve multiple tables, the inter-face shows separate summaries for each table in the join. The user can clickon a rule in one summary to see how it relates to the rules in the other sum-mary. Figure 4.2 shows an example with three lines denoting different valuesfor the relationship between the rules. The thicker the line the stronger theconnection between the tuples.65Figure 4.1: User interface for impact summaries.Figure 4.2: User interface for summaries for queries with join (NA refers tomissing data).66Figure 4.3: User interface for comparative summaries.For comparative summaries, we offer a similar interface. The difference isthe horizontal bars show how balanced each rule is in covering the provenanceof the two tuples, e.g. in Figure 4.3 the first rule represents a large impact ofthe provenance of Action as it does in the provenance of Drama.In all our interfaces the rules offer the following interactions. The usercan click on a rule to expand it and see a set of super-rules contained withinit (see Section 4.4 for the definition of super-rule). The user can also contractthe list to hide any sets of super-rules. In a list of rules, there can be trivialattributes that have all their values as ? in all rules, e.g. the attribute Title inFigure 4.2. These attributes can be collapsed into a single attribute named? as seen in Figures 4.2674.6 Experimental EvaluationIn this section, we have three objectives: (a) to evaluate the performanceof our algorithms and show they can generate summaries in real-time (Sec-tion 4.6.2), (b) to compare provenance summaries with basic summaries andshow provenance summaries have higher quality w.r.t. our new metrics (Sec-tion 4.6.3), (c) to show the relevance of impact and other related metrics suchas diversity for provenance summarization using a user survey (Section 4.6.4).4.6.1 Experimental SetupThe performance of our summarization algorithms and their result summariesvary depending on the selected tuples in the query answer. Since there are norestrictions over these user selected tuples, for each experiment we producedsummaries for a large number of randomly selected answers and reportedthe results as the distribution of those answers. The selection of answers wasdone by a uniform random sampler.The results of our summarization algorithms also depend on the query.We ran our experiments for different queries. To analyze the algorithmson queries with different aggregate functions, we used the same queries andreplaced the aggregate function. We reported the results for all functionsonly if there is a significant difference between the results. We used thelabels IAGG and CAGG to refer to the IPS and CPS with AGG as theaggregate function, e.g. ISUM is IPS with SUM.We implemented our algorithms in Python and ran the experiments ona machine with 3.3GHz Intel CPU and 16 GB RAM that uses PostgreSQL9.4. The provenance generation component is Perm [GMA13].Datasets We used three datasets. For the GLEI, IMDB, and TPC-H datasets,the data characteristics are as follows: The number of tuples (|D|): 250k,181k + 323k, and 60k-3m. The number of tables (N): 1, 2, and 8. The totalnumber of attributes in the tables (mD): 12, 15, and 61. The number of68queries (q): 5, 6, 5.Global Legal Entity Identifier (GLEIs). This is a real world financialdataset collected from various sources for financial institutions [CM19] tocreate a single, universal identifier for entities that are involved in any finan-cial transaction. We used this dataset for performance analysis (Exp-3 inSection 4.6.2). In those experiments, we ran the following query over a singletable, GLEI, with a varying number of attributes G1, G2, ... and aggregatefunctions f :SELECT G1, G2, ..., f(Dist) FROM GLEI GROUP BY G1, G2, ...Dist is a numerical attribute describing the distance between each entity andthe center of the city where it is located.IMDB. We used a subset of the IMDB dataset with two tables, Movies andDirectors. The movies table includes revenue for which we calculated theaggregate results. We used this dataset for performance analysis (Exp-2 and4) and quality experiments (Exp-6 and 7). In those experiments, we ran thefollowing query with a different number of attributes and different aggregatefunctions:SELECT G1, G2, ..., f(Rev) FROM Movies m, Directors dWHERE m.Director = d.Name GROUP BY G1, G2, ...TPC-H. As far as we know, there is no standard benchmark for provenancesystems or summarization. We used TPC-H for performance experimentsand to show how our methods handle queries with multiple types of aggre-gation and multiple complex joins.2 We varied the database size as follows:60k, 300k, 600k, and 3m. In the TPC-H experiments, we ran five queries,Q1, Q3, Q5, Q6, Q10, as generated by the TPC-H tool. We chose those queriesbecause they contain features covered by our summarization algorithm.Parameters The default value of k, the size of provenance summaries, is2http://www.tcp.org/hspec.html698, which we decided based on survey results in Section 4.6.4. The valuemw specifies the maximum weight of rules and its default value is 4, highervalues of mw make the rules too verbose for a summary of our datasets. Thenumber of group-by attributes in the queries, mq, has the default value of1, we assume that users unfamiliar with a dataset would start their analysiswith a single group-by attribute query.4.6.2 Runtime PerformanceTo evaluate the performance of IPS, we compared its runtime with BRSwhile changing |D| and k in Exp-1 and Exp-2, and mq and mw in Exp-3,respectively. We studied the runtime of IPS for queries with joins in Exp-4and CPS in Exp-5.Exp-1: Effects of |D|. Figure 4.4a shows the effect of |D| on the runtimeof IPS for the queries in the TPC-H dataset. As we expected, the runtimeincreases for larger |D|. However, IPS scales differently for each query. Forexample, while the increase in the runtime of IPS for Q3, Q10 is hardly no-ticeable, there is a clear jump in the runtime of Q1. This is because theprovenance of Q1 involves a portion of D that increases as we increase |D|,while Q3 and Q10 access almost a fixed part of D. This experiment showsthat IPS scales w.r.t. |D| but its actual runtime depends on the query.Exp-2: Effects of k. Figure 4.4b shows the effect of k on the runtime of IPS.We see an increase in runtime as we increase k for all algorithms. The increasein runtime is linear because the main loop of IPS (cf. Algorithm 2) runs ktimes. We also observe that IMAX runs faster than the other algorithmssince it only summarizes a small subset of the provenance set. ISUM, BRS,and IAVG perform similarly. IAVG performs slightly worse because of theextra computations.Exp-3: Effects of mq and mw. According to Figure 4.4c, the runtime ofIPS greatly decreases as the number of group-by attributes mq increases. In70the GLEI experiments, the average size of a provenance set is 9k tuples, 4.5ktuples, and 922 tuples for mq = 1, 2, 3, respectively. This shows that themore variables used to aggregate the data, the faster the summaries can beproduced. As expected, mw has the inverse effect with runtime increasing asmw increases. The main loop for Algorithm 2 runs mw times.Exp-4: Effects of join in queries. We considered TPC-H queries thatcontain joins and generated the same queries without joins by materializingthe join result. Figure 4.4e shows the runtime of IPS for all queries. IPSperforms similarly for all queries when the data size is small. The join queriesslightly outperform those without join because the summaries for querieswith join have a smaller number of attributes, and the shared join attributesappear only once in the join result. However, we see a larger effect of joinfor larger data sizes because finding contingency sets is costly.Exp-5: Effect of sampling on performance. We evaluate the effect ofsampling on performance by comparing various sample sizes with runningthe various algorithms without sampling. Figure 4.7a shows the results. Wesee a linear effect of sampling that is very pronounced. We study the effectof sampling on the quality of the rules in experiment 8.We also evaluated the effect sampling in Figure 4.4f by comparing theruntime of CPS and optimized CPS using the IMDB dataset. The optimizedversion runs 250% faster because many tuples have a low coverage on at leastone provenance set. While this is shown to be very effective for IMDB, itmight not be as effective in other datasets.4.6.3 Quality of Provenance SummariesMeasuring the quality of a summary of this type is a challenging task. Wechose four objective metrics to evaluate summaries produced using the BRSalgorithm and IPS. We also later describe our user survey to study users’expectations for such summaries to show the relevance of our metrics (Sec-71tion 4.6.4). We define the following quality metrics for a summary:• Impact is the distribution of impact values for rules in the summary.The sum and average impact for a summary do not give the full picture.A good impact summary needs to have all high-impact rules.• Coverage is the total number of provenance tuples covered by therules in the summary.• Weight is the total weight (the number of non-? values) of the rules ina summary. A higher weight represents more descriptive summaries.• Diversity is the number of unique values for attributes present in thesummary. Diversity is used in [WZRY18] to optimize a summary usinga distance function. We used it as a quality measure where a morediverse summary would cover more attribute values.We argue that a single measure by itself is not sufficient to evaluate thequality of a summary. A high-quality summary would have high-impactrules, high coverage, and high diversity, and its rules would have higherweights.Exp-6: Coverage and impact. Figures 4.5a and 4.5b respectively showthe coverage and the impact of the rules generated by different algorithmsfor the IMDB dataset. Figures 4.6a and 4.6b show the values for the TPC-Hqueries. Figures 4.5a and 4.6a show that BRS generates rules with highercoverage, which was expected. Surprisingly, Figures 4.5b and 4.6b revealthat BRS also generates rules with high impact. This can be explained bylooking at the distribution of the impact values, which shows a wide range ofimpact values in the basic summaries. However, impact as a quality metriccannot be analyzed in isolation, we need to also look at weight. This isbecause the basic summaries in BRS achieve high impact with a few high-coverage rules that have low weight and are thus not very informative. Therest of the rules in a basic summary do not have a high impact. However, the72impact summaries, e.g. ISUM and IAVG, gain high impact with informativerules with high weights. This confirms that IPS finds rules with high impactthat are also informative. For IMAX and IMIN, due to the distribution ofthe datasets in our experiments, IPS finds summaries that only contain a few(often one) rules with high impact and weight but low coverage and diversity.For TPC-H, impact and coverage values for some queries are not veryinformative. Q1 and Q10 specifically always produce similar rules and thusthe values for all variables do not change. This is due to the provenance ofthe query results being summarized which all contain the same categoricalvalues. In the other queries we see a similar trend to IMDB experimentswhere coverage and impact are close.Exp-7: Diversity and weight. Figure 4.5c also supports the fact thatIPS consistently picks higher weight rules than the BRS algorithm. ISUMgenerates rules with higher weights than IAVG due to the higher valuesof impact multiplied by the weight. Regarding diversity, IPS outperformsthe BRS algorithm (Figure 4.5e). With higher diversity values, we can saythat the higher weight rules of IPS are also more informative. Figures 4.6dand 4.6c show the diversity and weight values for all TPC-H queries withsimilar results. We see higher weight and diversity for ISUM and IAVGfor q3, q5, and q6. With similar coverage and impact, they produce moremeaningful rules. q1 and q10, similar to the previous experiment, do notshow any meaningful values.Exp-8: Effect of sampling on quality. The plots in Figure 4.7 showthe effect of sampling on all metrics: coverage, impact, weight, and diversityacross datasets. We see a very small effect of sampling on weight and diver-sity as the summary rules for the smallest samples have similar weight anddiversity values, we omit those figures to save space. Impact and coveragesee slight changes with the larger sample sizes getting close to the values ob-tained with unsampled runs. This is because the largest values are present inall samples as those values dominate the rules being picked, and as a result,73the patterns are very similar across datasets. Those attribute values includebinary values (male, female), as well as highly dominant values (country =”United States” in IMDB and GLEI). A good future direction could be totry to increase the diversity of rules by pruning out such values. Figures 4.7band 4.7c show the distribution of different coverage and impact values fromrunning multiple queries.4.6.4 User SurveyWe conducted an online survey to ask computer science students with entry-level knowledge of data and databases about their expectations of a data sum-marization system.3 We designed our questionnaire to be generic, presentinga use-case scenario that general users, with database entry-level course knowl-edge, would be familiar with. We tried to minimize bias by giving a verygeneric example of the IMDB dataset. We did not mention provenance orprovenance summarization, as those are specialized topics that the typicalcomputer science student is unlikely to be familiar with. Instead, we referto the summary as a summary of tabular data. We also used neutral termslike “group of movies with high revenue” or “groups that contain a lot ofmovies”, and tried to avoid using terms like “coverage” and “impact”. Wealso asked users for qualitative feedback in the form of justification for theirchoices. We present the full survey materials in Appendix B.We presented participants with a single scenario where a user posed aquery to the system, looked at an aggregate answer, and received a shortsummary of the data that contributed to the answer. The scenario is asfollows:Summarization scenario.A user accesses a dataset about movies and directors. The user asks the3The study was approved as minimal risk by the Behavioural Research Ethics Boardat the University of British Columbia. UBC BREB number: H20-01634.74system for the total revenue for action movies made in the year 2017. Theuser gets the result back: {Action; 2017; 7.3 Billion.} Now, given this resultwe would like to provide the user with a summary of movies made in 2017that made this 7.3 billion figure. Here is an example of a summary that is oflength 3. It contains 3 rows:Genre Year Country Duration Language coverage impactRow 1 Action 2017 US * English 35% 85%Row 2 Action 2017 * > 120 * 25% 78%Row 3 Action 2015 * < 90 * 39% 21%Table 4.9: Summary AThis summary is presented with real values for their respective columnsand * value as do-not-care values filling in for any other value in the column.For example, row 1 comprises action movies from 2017 made in the US withall possible duration values in English. Those movies make up 35% of rowsin the original database and have 85% of total revenue.We asked users to evaluate this summary and then asked them abouttheir thoughts on what type of information should be included in such asummary. We asked users to rank: rules covering movies with high revenue,rules covering a lot of movies, and rules with surprising information usingLikert scales from not important (1) to essential (5). These rules representimpact, coverage, and a surprise factor respectively. We also asked userswhat size of summary, in terms of the number of rules, would be appropriateand asked them to justify their choices. We used qualitative answers givenby users throughout the survey to filter out any survey responses with low-quality responses. We were able to remove 2 responses where the qualitativeanswers were not understandable by the researchers. We also did not recordany survey responses from participants who did not complete the full survey.Furthermore, we used qualitative responses as evidence of the quality metricsusers prefer.7527 participants completed the survey. Results show participants favorhigh-impact rules over rules with high coverage. They also favor surprisingrules the most (Figure 4.8a). In their evaluation of the summaries, mostusers picked the high impact, low coverage rules, and high weight rules asthe most interesting. Results also show that participants favor summariesof small sizes, i.e. 5–8. Only one user picked the summaries of size > 12,and users were given multiple size options above 12. 1 user picked other andwrote down “depends on the data”. Full results can be seen in Figure 4.8b.Users wrote out qualitative answers to justify their choices. Notably,users commented that high impact rules were most interesting and that theypreferred shorter summaries. We present some quotes from the survey par-ticipants: “Row 2 was most interesting showing that only 25% of moviescollected 78% of revenue which is significant.” “I care about ranking rulesbased on the impact factor.” “More than 5 rows is not a summary”. “I feelthat in 5-8 rows you could cover all the important groups of action moviesthat are of interest”.We acknowledge the limitations of a survey of this type. We took somemeasures to control the quality of responses: responses were inspected manu-ally before analysis. Qualitative responses were inspected to make sure usersunderstood the questions and provided relevant answers. We also asked forself-reporting of accuracy from users. We are confident this is a first step inevaluating the usefulness of our summaries and setting up future work.4.6.5 Case StudyWe present three examples to further explain how the provenance summariesare different from basic summaries and summarise provenance data moreeffectively.Impact Summaries. We look at the quality of an impact summary for theprovenance of Action movies from the following query:76SELECT Genre,SUM(Rev) FROM Movies GROUP BY GenreWe ran the query over Movies in the IMDB dataset with additional at-tributes, such as language and duration, compared in Table 2.2. Tables 4.10and 4.11 subsequently show the impact summaries and basic summaries ofsize k = 4 generated by IPS and the BRS algorithm. As we explained inExp-6, impact summaries usually have rules with higher weights comparedto basic summaries because of using the larger impact values, that are mul-tiplied by weight to compute the score of a rule. In this case, the impactsummary includes s3 with higher weight than s7 despite s7 having higherimpact and coverage. This is because s3’s marginal score, which is a functionof impact and weight, is higher than s7’s marginal score. Regarding coverageand impact, we see that basic summaries include rules that cover more tuplesbut do not have high impact, e.g. s6 has high coverage 0.5 and low impact0.03. This is unlike impact summaries that prioritize impact over coverage,e.g. s2 in our impact summary has low coverage, 0.08, and high impact, 0.52.This is an informative rule that covers movies with a duration of 150 min-utes; such movies account for a lot of recent blockbusters with huge revenuevalues such as Star Wars: The Force Awakens, Jurassic World, Furious 7,and Avengers: Age of Ultron. Such rules with high impact, high weight, andlow coverage can provide the surprising information that users are lookingfor.Impact Summaries for Queries with Joins. We look at the impactsummaries for the following query:SELECT m.Genre,AVG(m.Rev) FROM Movies m JOINDirectors d ON m.director=d.name GROUP BY m.GenreWe show how an impact summary containing separate rules over the moviesand directors tables can provide new information compared to those over thejoin result, MoviesDirectors. We assume that the user asks for an impactsummary for the answer containing action movies. In an impact summary77ID Genre Lang Country Duration Weight Coverage Impacts1 Action EN US ? 2 0.45 0.63s2 Action EN ? 150 min 2 0.08 0.52s3 Action EN US 120 min 3 0.22 0.29s4 Action EN ? ? 1 0.76 0.97Table 4.10: An impact summary from the IPS algorithmID Genre Lang Country Duration Weight Coverage Impacts5 Action EN US ? 2 0.45 0.63s6 Action EN ? 90 min 2 0.5 0.03s7 Action EN ? 120 min 2 0.37 0.42s8 Action EN ? ? 1 0.76 0.97Table 4.11: A basic summary from the BRS algorithmover MoviesDirectors, we do not see any insightful rules, and all rules revolvearound common categorical attributes such as country, language, and directorgender. However, looking at the individual contribution of each table in animpact summary over Movies and Directors, we see an informative rule with(Gender : Female and Name : Patty Jenkins) in the impact summary overDirectors. This is because Patty Jenkins made Wonder Woman, a movie thatmade a lot of money and has a substantial impact on the average revenuefor female directors.Comparative Summaries. We also look at an example to show the valueof our comparative summaries and compare them with basic summaries.We consider two answers t = (Romance, 167) and t′ = (Foreign, 39) to thefollowing query:SELECT Genre, COUNT(∗) FROM MoviesWHERE Language = EN AND ReleaseYear = 2010GROUP BY GenreWe compare two sets of rules: (a) a comparative summary obtained fromCPS and for the provenance of t and t′, and (b) a basic summary obtained78by running the BRS algorithm on Moviest ∪Moviest′ .In (a), we see interesting rules with values common in romance and foreignmovies. For example, a common class of movies are those made in Englishspeaking countries other than the US, e.g. the Phillipines. The rules in(b) are dominated by the bigger provenance set, i.e. Romance movies, andalways show the most occurring values in that set, e.g. movies that are madein the US, or with a runtime of 120 minutes. Our CPS algorithm showsthat movies made in foreign countries such as the Philippines had markedlydifferent characteristics from “standard” movies. The user may have wantedto make sure that such movies were only counted in one genre, i.e. foreignmovies, instead of both. This type of analysis would not have been possiblewith the basic summaries produced by the BRS algorithm.The basic summary is always dominated by the bigger set (Romancemovies) and always shows the most occurring values in that set, such as:(Country: US), (Rating: 0.0), and (Runtime: 120). In the comparison sit-uation in Section 4.3 the user is likely to be interested in exploring whichanswers are anomalous. For example, our CPS algorithm shows that moviesmade in foreign countries such as the Philippines had markedly differentcharacteristics from “standard” movies. The user may have wanted to makesure that such movies were handled differently. This type of analysis wouldhave been impossible with the BRS algorithm.While this analysis is not conclusive, it clearly shows that different sum-maries cover different user needs depending on the use case. The basic sum-maries work best for coverage, while the impact summaries highlight high-impact tuples and the comparative summaries are more effective in showingoverlooked interesting areas or tuples. As users seem to seek more informa-tive and interesting summaries, a summarization system needs to be flexibleto cover all users’ needs.794.7 Conclusion and Future WorkIn this chapter, we implemented new summarization techniques: impactsummaries and comparative summaries. Our summaries work well for userswithout knowledge of provenance semantics or the data. We validated ourtechniques with thorough experiments and a user survey.There are many viable avenues for future work. One direction is tosupport a bigger class of queries, such as nested queries. Another futurework item is extending comparative summaries to more than two tuples.We could also explore other semantics of contribution, such as the Shapleyvalue [Sha97]. Overall, there is still a lot to be done in this field. However, webelieve impact and comparative summaries are a step in the right direction.We utilize those summaries in Chapter 5 to develop new techniques for queryrefinement. Such techniques aim to show that summaries are useful for moreapplications beyond improving the usability of provenance information anddata exploration.80110060k 300k 600k 3m|D|Runtime (log) Q1 Q3 Q5 Q6 Q10(a) Effect of |D| in TPC-H.4 8 16101001000Runtime (log)BRS ISUM IAVG IMAXk(b) Effect of k in IMDB.1 2 3101000Runtime (log)BRS IAVG IMAXmq(c) Effect of mq in GLEI.2 3 4101000Runtime (log)BRS IAVG IMAXmw(d) Effect of mw in GLEI.60k 300k 600k 3m101,000100,000Runtime (log)JOIN NO JOIN|D|(e) Effect of join in TPC-H.CPSCPS_OPT4 8 12 16050010001500246kRuntimeCPS CPS_OPT(f) Effect of opt. on CPS.Figure 4.4: Effect of different parameters on Runtime, in seconds, of IPS.CPS experiments used the IMDB dataset.812 4 8300060009000CoverageBRS ISUM IAVGk(a) Effect of k on coverage.ll l2 4 80.01 M10.00 M10,000.00 MImpactBRS ISUM IAVGk(b) Impact for different tuples.lll2 4 85101520WeightBRS ISUM IAVGk(c) Effect of k on weight.lllll2 3 412.515.017.520.022.5WeightBRS ISUM IAVGmw(d) Effect of mw on weight.ll2 4 82468DiversityBRS ISUM IAVGk(e) Effect of k on diversity.ll lllll2 3 43456DiversityBRS ISUM IAVGmw(f) Effect of mw on diversity.Figure 4.5: The quality of summaries w.r.t. coverage, weight, impact, anddiversity for the IMDB data, and the impact of k and mw (the maximumweight) on these quality metrics.82q1 q3 q5 q6 q10100002000030000400005000060000CoverageBRS ISUM IAVGquery(a) Coverage for TPC-H.q1 q3 q5 q6 q101e+052e+053e+05ImpactBRS ISUM IAVGquery(b) Impact for TPC-H.q1 q3 q5 q6 q104567WeightBRS ISUM IAVGquery(c) Weight for TPC-H.q1 q3 q5 q6 q104567DiversityBRS ISUM IAVGquery(d) Diversity for TPC-H.Figure 4.6: The quality of summaries for five queries in the TPC-H dataset(k = 4 and mw = 3).83GLEI IMDB100500 1kno sample100500 1kno sample05101520Sample sizeTime (seconds)IAVG BRS ISUMDataset(a) Sampling performance.100 500 1000 No sample80001000012000CoverageBRS ISUM IAVGSample size(b) Sample size vs coverage.100 500 1000 No sample4e+116e+118e+11ImpactBRS ISUM IAVGSample size(c) Sample size vs impact.Figure 4.7: a shows sampling performance. b & c show the effect of samplingon the quality of summaries. (k = 4, mw = 3)84581109 93127151101020coverageimpact surpriseVotesImportance54321(a) Ranked summary metrics.0.02.55.07.510.01−4 5−8 9−12 >12 otherSizeVotes(b) Preferred summary size.Figure 4.8: Survey results show how users ranked the various metrics (5essential – 1 not important) and summary sizes.85Chapter 5Aggregate query refinementusing summary rules andprovenance summaries5.1 IntroductionUsers perform aggregation queries for many purposes, including exploring adataset, deriving numeric measures, and generating reports. Our focus ison the scenario of data exploration, where the user has limited knowledgeand expertise in dealing with the dataset. The data exploration processfor such a user is iterative and error-prone. The user starts the process bylooking to form a picture of what the data looks like. This is usually done byasking aggregate queries. When users receive an aggregate answer they ask:“What is included in the result? What is not included?” While databaseprovenance can provide an answer to the first question, it is not sufficient toanswer the second one and is often verbose and complex enough to requirefurther expertise. One variation of this problem is if the user knows thedomain well enough to know that the answer is wrong. In this case, the usermay want to modify the aggregate query to receive a specific answer.86We tackle this instance of the problem with a solution that shows theuser suggestions to help the user find the specific answer they are lookingfor. Our solution addresses two main problems: relaxing and contractingqueries. Intuitively, relaxing a query means expanding the query answer toinclude more tuples. Contracting a query means shrinking the query answerto include fewer tuples. We define the problem more formally later in thissection.There currently exist query refinement solutions such as [MK09], that cansolve the relax/contract query problem. Current solutions focus mainly oncardinality constraints and the query itself. Those solutions are very queryoriented, with minimal access to the database or underlying data. They alsorely heavily on the existence of hierarchies for categorical variables. In termsof interaction, these solutions rely on the user to interact with the data tomanually refine the query and reach a close enough answer. We argue thatsuch solutions are not sufficient for the scenario we describe above. In ourscenario, the user knows the answer is wrong but lacks the expertise to man-ually refine the query. Therefore, our solution is fully automated: the usersubmits a query and their feedback and we provide refinement suggestions.Our solution also helps users navigate the space of categorical variables with-out the need for input hierarchies, which may not be available. Example 20shows in detail how this works.Some promising related areas of research are in answer explanation [AKS+18],tuple recommendation [DP13], and query by example [FM19]. Such solutionsaccess the data and use different utilities to help users in different applica-tions. We use techniques similar to those used for query refinement. Access-ing the data and finding interesting patterns to show the user can help themunderstand their query and query answers, and can lead to a fuller under-standing of the refinement process. We differentiate our work from each ofthose domains in the related work section (Section 5.2).We formally define the problem as follows:87Definition 5.1 (Aggregate query refinement problem). A user asks an ag-gregate query, Q, to a database, D, where the answer, Q(D), is equal tosome single value, k. Additionally, the user has an expected target value, k′.If k 6= k′, the aggregate query refinement problem is to help the user finda query, Q′′, where the answer to Q′′, Q′′(D) is as close to k′ as possible.In other words, the goal of aggregate query refinement is to help the userto recover the hidden query Q′ where Q′(D) = k′; we approximate this byfinding Q′′, which ideally is equal to Q′.In this chapter, we propose a framework that uses the data itself, withoutusing query logs, hierarchies about the data, or user session information, asthose are rarely available. Our framework uses provenance summaries ofanswers and non-answers as well as summary statistics to get the user asclose to the desired answer as possible. We show that our framework isuseful and produces meaningful recommendations through a user study. Wealso conduct thorough experiments to show that our system can work inreal-time and is scalable.We go into more detail on our framework in Section 5.4.ID Title Year Genre(s) Rating Revenue Runtime Production Companyt1 Frozen 2013 Animation, Adventure 7 1.2B 102 Walt Disney Picturest2 Monsters, Inc. 2001 Animation, Adventure 7 560M 96 Walt Disney Picturest3 Aladdin 1992 Musical, Adventure 7 504M 90 Walt Disney Productionst4 Toy Story 1995 Comedy, Adventure 7 373M 89 Walt Disney Picturest5 Toy Story 2 1999 Adventure, Family 7 497M 95 Walt Disney Picturest6 Finding Nemo 2003 Family, Adventure 7 940M 100 Pixar Animation Studiost7 Up 2009 Adventure, Family, Animation 7 735M 96 Pixar Animation Studiost8 The Lion King 1994 Musical, Animation 7 788M 89 Walt Disney Productionst9 Star Wars: The Force Awakens 2015 Action, Sci-fi 7 2B 136 Lucasfilmt10 Guardians of the Galaxy 2014 Action, Sci-fi 7 773M 122 Marvel Studiost11 Dr. Strange 2016 Action, Adventure 7 677M 115 Marvel Studiost12 Rogue One: A Star Wars Story 2016 Action, Sci-fi 7 1.05B 133 LucasfilmTable 5.1: MoviesGenre sample tableExample 20. A user starts exploring a dataset of movies with informationabout movies and their respective genres (Table 5.1). For simplicity, we show88Table 5.1 as a joined table with the genre attribute denormalized. The useris looking for a set of highly rated, high-grossing, adventure movies made byDisney. The user tries to define the criteria for this task. Based on thosecriteria, the user asks a query Q to get all movies in the Adventure genre,that have revenue greater than 300 million, and a user rating greater than 7.Finally, the query specifies that the movies are made by Walt Disney Studiosor any variation of the studio name. Q1 shows the SQL query:Q1 : SELECT COUNT(∗) FROM movie m, genre gWHERE m.id = g.movie idAND m.revenue > 300mAND m.rating > 7AND g.genre = ‘Adventure’AND m.production company LIKE ‘Walt Disney%’This query can be expressed as a summarization rule in the form:(Title : ?,Year : ?,Genre : Adventure,Rating :> 7,Production company :WaltDisney%, count : 5,Rev :> 300m) The rule contains ? which is a wild-card variable that matches all values for an attribute. Other attributes con-tain values that match those specified in the query conditions. Summariza-tion rules are explained in depth in Chapter 2.There is a total of 5 movies (k) in Table 5.1 that match the criteria. Theuser expects a larger set of answers, so they examine the provenance of theresult (t1− t5 from Table 5.1). The user is surprised to see that some moviesthey know should be included are missing. So they submit feedback that theresult size is low and provide an expected number of results, k′ > 5.The system goes through the table looking for groups of tuples in thedata that meet the new cardinality constraint and meet the conditions in thequery as much as possible. The system provides several suggestions, in theform of summarization rules that summarize such groups. The rules providerelaxation suggestions that contain the original query results and meet or getclose to the cardinality constraints set by the user. In this case, it will return89the rules:1. s1 = {r1 : (Title : ?,Year : ?,Genre : ?,Rating :> 7,Production company : WaltDisney%, count : 6,Rev :>300m)}2. s2 = {r1 : (Title : ?,Year : ?,Genre : Adventure, Rating :> 7,Production company : WaltDisney%, count : 5,Rev :> 300m),r2 : (language : en,Title : ?,Year : ?,Genre : Adventure,Rating :>7,Production company : PixarAnimationStudios, count : 2,Rev :>300m)}The first suggestion s1 relaxes the genre attribute specified in the query,to include t8 The Lion King in the results. k′′ here is equal to 6. The secondsuggestion s2 is a conjunction of 2 rules that adds movies made by PixarAnimation Studios to the results and increases the result size to k′′ = 7. Bothsuggestions are made because the underlying tuples share common propertieswith those in the provenance set (t1 − t5). t8 is made around the same timeand has a similar rating and runtime. t6 and t7 are also made around thesame time, with similar ratings, revenue, and runtime. The other movies aremuch longer, contain different genres (Action, Sci-Fi), and are more recent,thus they are deemed dissimilar to those in t1 − t5. It is worth noting thatDisney bought Pixar in 2007 so the two are closely related. The exampleshows our system can detect similarities without augmenting it with moredata, using simple descriptive attributes such as genre and duration.Without our system, the user would have to manually explore the data.This would involve rewriting the query, relaxing, or removing conditions.The user would also have to inspect the data manually to see what is con-tained in the results. This is a costly and not necessarily intuitive process.Furthermore, without hierarchies or order for the categorical attributes, theuser would have no idea where to go without knowledge of the attribute val-ues. Moving from Action to Adventure or from a production company to90another that is related can be an ambiguous process without the aid of oursolution.With our approach, we define the problem of query relaxation/refinementunder a user-provided cardinality constraint as finding a summary (candidatequery) from the space of candidate summaries mined from the data (whichare also candidate queries) that fulfill the cardinality constraint and is mostsimilar to the user’s original query in terms of results. Figure 5.1 gives anoverview of the solution.As seen in Figure 5.2, which shows the details of our query refinementframework architecture, our system performs the following steps:1. Reduce the number of attributes using correlation coefficients.2. Produce rules using a CUBE query over all leftover attributes. Storethese rules in a rules database. Both of these steps are performed asinitial offline steps.3. When the user submits a complaint, generate a list of candidate rulesfrom the rule table using cardinality constraints and rule containment.This step prunes a large portion of non-answers.4. Generate a summary as a set of rules for the results of Q(D).5. Compare the summary of the provenance of answer Q(D) against thecandidate rules of non-answers. We encode rulesets as TFIDF vectorsthat are then compared using a similarity metric. The end result is aranked list of the most recommended non-answers that can fulfill theusers’ cardinality constraint.We explore the techniques we use further in Section 5.4.5.1.1 ContributionsIn summary, our contributions for this chapter are as follows:91Figure 5.1: Overview of solution from the query step all the way to therecommended groups of tuples92Figure 5.2: Query refinement framework architecture931. We develop a new method for query refinement for the scenario wherethe user does not like their initial query result and wants to see adifferent answer (Section 5.4).2. We conduct a user study to show that our method provides usefulrefinement suggestions to users (Section 5.5).3. We perform performance experiments to show that our method is scal-able and outperforms automated machine learning methods (Section5.6).5.2 Related workReverse engineering queries. Such works as [TCP14, TZES17] tacklethe query reverse engineering problem or QRE. The problem is defined asfinding a query, Q, from a set of results that has an output equal to theresults. This problem is relevant but not directly equivalent to the problemof refining query results. It is relevant because it takes a set of tuples wherethe query is unknown and produces a query. It is not equivalent because thisset is assumed to be a complete result. Systems such as TALOS [TCP14] canprovide explanations for missing answers and provide suggestions for refinedqueries. However, they require the user to provide a full set of such missinganswers to get a new query, Q′, that explains why the answers are missing.While this is indeed similar functionality, the requirement does not workfor our scenario where users are not very familiar with the data and cannotprovide the full set of results but a partial set at best.Query by example. [TCP09] An alternative method to declarative querylanguages is query by example or QBE. Here the user must provide a subset ofthe answer to receive suggestions on queries that produce results that includethe answer. While most commercial DBMSs provide such functionality, theresults are often lacking or simplistic. More modern solutions such as [FM19]94aim to find the users’ intentions and produce more intuitive queries. Whilethe description of QBE systems and query refinement systems sound similar,they are not quite the same. One element that is lacking is that QBE systemstake in a small set of tuples that contain very limited attribute values. Largeinputs would need to be filled in manually by the user and can be taxing.Whereas query refinement systems take in a query and full results. QBEsystems also rely on the user having some sort of intuition on what answerthey would like to see, which assumes some knowledge of the data.Interactive data exploration. Such systems work on the idea of provid-ing users with suggestions of individual tuples [SDP09, DP13] or interestingareas or groups of tuples [DPD16, CCD+13] to get them where they needto go as they explore a dataset. Such work is relevant but does not takein any constraints such as cardinality or relevance to a full set of results.Furthermore, the burden is often on the user to provide feedback on whatthey see as relevant. This user feedback can help build models that refinetheir suggestions the more they interact with the system. This line of workis directly relevant, but not specific enough for query refinement tasks.OLAP. Papers in the online analytical processing space, such as [SAM98]provide ideas for automatic exploration of data. However, the techniquesare better suited for the data warehousing context where data is cleaned,curated, and contains hierarchies and functional dependencies that are ex-plicitly defined. The scalability of such approaches is also in question whenapplied to larger datasets with more dimensions.Missing answers. [CJ09, HH10a, HCDN08] present the problem of ex-plaining missing answers. This is a directly related topic to relaxing queries.Where query relaxation has the goal of finding tuples closely related to thequery answer, explanations for a missing answer try to find the most probableexplanations for why a tuple is missing from an answer set. The explana-tions are typically in the form of conditions to be fulfilled to add the missingtuple to the result. While this work contains a lot of useful techniques and95is closely related, it does not address the problem of having multiple tuplesor a large result set and finding related query refinement candidates.Query refinement. There have been multiple systems in the query re-finement space that handle the same problem we defined in the introduc-tion [MK08, MK09, VRRM16, ASZ14, BHT16], those systems perform verysimilar tasks to ours. All systems, however, focus mostly on the query andprovide query-centric solutions. They make assumptions about the presenceof hierarchies for categorical values. They also offer different interfaces forusers to interactively refine their queries. Our solution makes different as-sumptions and provides fully automated suggestions that do not require userfeedback. Our solution is also data-centric. More specifically, we propose anapproach that uses the data without analyzing queries. We show the user asummary (candidate query) from the space of candidate queries mined fromthe data (which are summaries or sets of summaries) that fulfills the car-dinality constraint and is similar to the user’s original query. Whereas ourwork is focused mostly on categorical variables (due to the nature of the ruleswe use), the other related works we cite have made tremendous progress indealing with continuous attributes.5.3 Problem SettingIn this section, we formalize the problem of query refinement and define theparameters for every part of it. We use slightly different symbols than thosedefined in Chapter 2 as shown in Table 5.2. We define the class of aggregatefunctions we handle to be Count, Sum, Min, and Max. We also define theproblem in terms of attribute types: numeric or categorical. We use data-independent containment to find rules that cover query results. We also usebucketizing for numeric data. We discuss all of these concepts in detail inthis section.96Table 5.2: Summary of symbols and notations for query refinementSymbol DescriptionR,R relation and relational schemaRM Set of relations in database instance DA1, A2, .., An relational attributest tuplesQ,Q(D) query, query answerD,S database (instance), database schemar1, r2, .., rn rulesS set or list of rulesDom(A) domain of attribute A? wildcard characterP (Q(D)) provenance of results of Query Q in database DP (Q′(D)) provenance of results of Query Q′ in database Dk aggregate answer to query Qk′ expected answer and answer to target query Q′5.3.1 PreliminariesWe assume the user asks an aggregate query of the form:Q: SELECT AS, f(A∗) AS A FROM R1, R2, ...WHERE conditions GROUP BY AGListing 5.1: The general form of aggregate query asked by the userWhere:Query relations RM = {R1, R2, . . . Rm} is the set of relations in databaseDQuery attributes An = {A1, . . . , An} is the set of attributes ofR1, R2, . . . RmGroup By GROUP BY is an optional clause of the query, which uses stan-dard GROUP BY semantics97Group by attributes if there is a GROUP BY clause, then AG ⊆ An isthe set of attributes in that clauseSelected attributes AS is the selected attributes. If Q contains a GROUPBY clause, then AS ⊆ AG ⊆ AnAggregated attributes A∗ is the aggregated attributes where A∗ ⊆ AS.Function f is an aggregate function, such as COUNT, which is applied tothe aggregated attribute.Conditions contain a conjunction or disjunction of conditions on the tablesRM as well as the join predicates.Example 21. Continuing with Example 20, we have the aggregate query:SELECT COUNT(∗) FROM movie m, genre gWHERE m.id = g.movie idAND m.revenue > 100mAND m.rating > 7AND g.genre = ‘Adventure’AND m.production company LIKE ‘Walt Disney%’Listing 5.2: Aggregate query from example 20In this example, f is the aggregate COUNT function. A∗ is the wildcard ?.conditions contain a conjunction of 4 conditions.Query 5.2 returns k = 5 which is the number of movies that meet the condi-tions. Given a query, Q over a database, D, with schema, R, we define theprovenance of Q as the set of tuples P (Q(D)) that contributed to the ag-gregate answer Q(D) using lineage semantics (See Chapter 2 for provenancetypes details). We use P (Q(D)) to refer to the provenance of Q(D) in D. Forexample, P (Q(D)) in Query 5.2 contains all the tuples in the MoviesGenretable that meet the conditions in Q1 (t1 − t5 in Table 5.1).985.3.2 The scope of the query refinement solutionAs motivated and defined in Section 5.1 Definition 5.1, Q is a query withresults Q(D) such that k ∈ Q(D). The user submits feedback with k′ whichis the expected target value. The problem is to help the user find Q′′ whereQ′′(D) is as close to k′ as possible. In this section, we explain our assumptionsand define the subset of queries we target with our approach.For our study of this problem, we make an assumption that is commonacross many aggregate queries: the quantities that are being aggregated arenon-negative. For example, movies do not earn negative money at the boxoffice, and there are not a negative number of students who take classes.Under this assumption, we use P (Q(D)) to denote a set of tuples in theprovenance of k ⊆ Q(D). We define expanding and contracting queries interms of provenance:Definition 5.2 (Expanding the aggregate query). If k < k′, then the goal isto relax Q to get the answer P (Q′′(D)), where P (Q(D)) ⊂ P (Q′′(D)).Example 20 shows an example of relaxing the query Q1.Definition 5.3 (Contracting the aggregate query). Else if k > k′, then thegoal is to contract the query Q, where P (Q′′(D)) ⊂ P (Q(D)).We also restrict the class of aggregate functions we handle to: Count,Sum, Min, and Max. Count and Sum are both monotone functions that worksimilarly. For Min and Max, we utilize similar techniques to those used inChapter 4. Summarizing the Max/Min function requires the same operationsas finding a new Max/Min value set by the user. A natural extension tosupport the AVG function is to break down the average into Sum/Count.Other non-monotone functions require a more thorough investigation andare left as future work.We also further restrict the class of queries we handle to exclude sub-queries. Sub-queries introduce complex concepts to provenance and summa-rization and we leave them as future work.995.3.3 Rule containmentWe use summary rules to represent the aggregation queries and to presentsuggestions to users. We use rules as introduced in Chapter 2 to model everyquery and every group of tuples in our solution. Representing queries andgroups of tuples as rules enables our solution to find queries that containother queries, or queries contained by others. It also allows us to find groupsof tuples that fulfill refinement requirements. We use Definition 2.3 to definecontainment. A sub-rule contains super-rules, and super-rules are containedwithin sub-rules as per the definition.Rule containment is a quick check over the rules’ attributes and valueswithin. It works quickly and without checking the original data to determinegroups of tuples that contain other groups of tuples. For example, the ruleR1 : (language : en, T itle : ∗, Y ear : ∗, Genre : Adventure, Rating :>7, P roductioncompany : PixarAnimationStudios) is contained within therule R2 : (language : ∗, T itle : ∗, Y ear : ∗, Genre : Adventure, Rating :>7, P roductioncompany : ∗). We say R1 is contained in R2 when R2 is asuper rule of R1 as seen in Definition 2.3. It is the basis for our solution,which we go into further in Section 5.4.We use the same format for the rules that we use in previous chapters.The only addition is that of representing simple disjunctive queries, whichis a class of queries we did not handle in previous work. We expand thedefinition of rules to handle simple disjunctions for categorical values. Forsuch queries, we use multiple rules to represent the disjunction.Example 22. To give an example of what we mean by a simple disjunctivequery, we show a query to select Action or Adventure movies. The query:Qdis: SELECT count(∗) FROM moviesgenreWHERE genre in (‘Action’, ‘Adventure’)is represented by the rules: {r1 : (language : ?,Title : ?,Year : ?,Genre :Action, Rating : ?,Production company : ?, count : 4,Rev : ?),100r2 : (language : ?,Title : ?,Year : ?,Genre : Adventure,Rating : ?,Production company : ?, count : 8,Rev : ?)} 5.3.4 Continuous AttributesWe treat continuous numeric attribute values as categorical attributes bydefining buckets of intervals of values, e.g. 8 > Rating > 6. We also definebuckets of cumulative values, e.g. Rating > 6. The rules are created tofacilitate rule containment and as such, they contain cumulative values like> 100m or buckets such as Rating > 6 to <= 8. We initially bucketizenumeric values based on 10 quantiles for the initial set of rules. If sufficientrules are found to fulfill the user constraint k′ we return those rules andthe bucketization stops. We maintain access to the full values if we need todynamically bucketize numeric values further. In cases where the limits ofnumeric buckets are too wide for relaxation or too small for contraction, wefurther bucketize the relevant buckets into 10 more quantiles. The processcontinues until the buckets provide values that can satisfy the user cardinalityconstraint. We find bucketizing continuous data to be the best, and fastest,approach to handling such attributes for the datasets we use. We charac-terize our datasets as consisting of mostly categorical attributes with a fewcontinuous, numeric attributes that we use mainly as measure attributes (e.g.revenue in a movies dataset). There is research into finding patterns for nu-meric values [VGBS19] but it is not directly applicable to our problem andis currently outside of our scope.5.3.5 Categorical attributesWhile other query refinement solutions handle hierarchies, they do not pro-pose any solution to handle categorical attributes that do not have hierar-chies. Categorical attributes without hierarchies are the most common in ourdatasets. We believe users need to see other values of categorical attributes101to gain a full grasp of their data. In Example 20, the value of Pixar Anima-tion Studios is completely hidden from the user because their query is askingfor a specific categorical value (Disney Studios). Yet it is very likely to bethe refinement they seek. This also comes into play in datasets that containmiscategorized information. Finding and recommending relevant categoricalvalues is a key component of our solution.We handle categorical attributes differently depending on their type. Wedefine four different types of categorical attributes: 1) hierarchical attributes,2) ordinal attributes, 3) semantically meaningful attributes, and 4) none ofthe above. We encode order for all attributes depending on their type.For explicit hierarchies (e.g. City, State, Country) the traditional ap-proach is to move up through the hierarchy to relax or move down to con-tract a query. However, hierarchies are not naturally available in our dataand require user involvement to define them. In the presence of hierarchies,we use them as all other refinement systems.For ordinal attributes, we encode order to be able to show users adjacentvalues. For attributes such as days of the week, the encoded order helps findclosely related values such as the next day of the week to recommend morerelevant suggestions. We encode order into ordinal attributes to facilitatesuggesting relevant rules.For semantically meaningful values, (e.g. movie genre) we calculate se-mantic distance based on WordNet [Mil95]. Alternatively, corpus-based mea-sures can also serve this purpose. We use this measure to order these at-tributes based on conceptual closeness to each other. We can recommendmore closely related movies to Q1 such as Action movies which can be morerelevant to the user query. In Example 20, Action movies can be relevant toQ1 where the user is asking for Adventure movies. In cases where semanticsimilarity isn’t feasible, we can treat this class of attributes the same way wehandle the next one.For categorical attributes that do not fit any of the above, we use sum-102maries of associated attributes to encode order. For example, we can encodeorder to production companies in movies. Companies can be found to bemore closely related if we examine movies, revenue, location, or actors in-volved. In Example 20, Pixar Animation Studios is very relevant to Q1 wherethe user is asking for Disney movies. By analyzing the properties of bothproduction companies, we can encode order to the attribute values basedon the similarity of common properties. Those properties are co-occurringattribute values such as genres, years, revenue patterns, and runtime. Thisanalysis can be costly for attributes with many values and is done as anoffline pre-processing step.5.4 Solution OverviewWe propose a framework that allows the user to explore interesting groupsof tuples outside of the query answer set. Those groups correspond to queryrefinement candidates. Our system comprises the following components:1. Rule generator to perform attribute reduction and rule generation andstore rules in the rules database.2. Provenance summary component to summarize the provenance ofQ(D).3. Candidate rule mining component to find candidate rules.4. A candidate rule embedding and ranking component to compare thesummary of the provenance of answer Q(D) against the candidate rulesof non-answers.The end result is a ranked list of the most recommended non-answersthat can fulfill the users’ cardinality constraint.Figure 5.2 shows the overall architecture of our solution. The user submitsan aggregation query Q, they receive an unexpected result. The user thensubmits feedback on the expected value. For relaxing queries, we make the103assumption that the initial query Q is partially correct. As in the finalquery result the user wants Q′(D) containing the results they got from theirinitial query Q. The final result Q′(D) comprises a collection of tuples withcertain properties in common. Be it a categorical value, a numeric trend, ora correlation of values and trends. For contracting queries, the assumptionis that the correct result is contained within the initial query result Q(D).We produce a summary of the results that include common attribute values,numeric trends, and how those trends and values are correlated. We theorizethat a refinement of the user’s query would include tuples that are consistentwith those summary patterns. Those refinements are groups of tuples thatwhen added to, or removed from, the result can fulfill the user’s constraints.Refinements can be one of two things: 1) a single rule that satisfies thecardinality constraint. 2) A conjunction of multiple rules that together coverenough tuples to meet the cardinality constraint.Our framework comprises two parts: an offline and an online component.First is the rules generator component responsible for generating the rules ta-ble. This is done completely offline. In order to derive and recommend suchpatterns, we take the initial result Q(D) as well as the feedback from theuser k′ and run them through a number of different components. First, theprovenance summary component produces a summary of the results Q(D)with the highlights in terms of categorical properties and numeric trends.Second, is a candidate rule mining component to find candidate rules andtuples. Finally, we have a ranking mechanism that recommends these can-didates in a list to be added to Q(D) to produce the final answer Q′′(D).These components enable our approach to present real-time suggestions tousers that can aid them in refining their uncertain queries. Mining usefulrules alleviates the need for categorical hierarchies or multiple iterations.1045.4.1 Rule generatorThe rule generator component produces comprehensive rules that cover theentire database D. We simplify by joining the full database to produce a uni-versal table and refer to it as D. As a first step, we use correlation measuresto reduce the number of attributes present in the table D. Alternatively,we could use functional dependencies to achieve a similar effect. Withoutthose, we rely on the more general correlation measures. The number ofrules produced from a table is exponential in the number of attribute val-ues. Thus, reducing the number of attributes involved in generating rulesseverely reduces the complexity of the operation. We use the Cramer’s Vmeasure [AS79] for categorical attributes and the Pearson correlation coeffi-cient [BCHC09] for numeric attributes.After reducing the number of attributes, we run a CUBE query to gener-ate rules that summarize the full table. CUBE queries produce aggregationsfor all attributes involved. Those aggregations include key statistics andmeasurements that cover the whole database.The CUBE query is of the form:CREATE MATERIALIZED VIEW rules cube ASSELECT COALESCE(A1, ’∗’),COALESCE(A2, ’∗’),..COALESCE(An, ’∗’),count(∗) AS count,f1(A∗) AS STAT fA1 ,..fn(A∗) AS STAT fAn ,count(non NULL values) AS weightFROM R1, R2, .., RnWHERE conditions105GROUP BY CUBE(A1, .., An);Listing 5.3: The general form of cube query to generate rulesWe further augment the list of rules by joining it with cumulative values ofinterest from the user query. Cumulative queries take on the form:SELECT A1,count(∗) AS count,f1(G∗) AS CUMULATIV EfA1 ,(sum(count(∗)) OVER (ORDER BY A1)) AS cumulative count,(sum(sum(A∗)) OVER (ORDER BY A1)) AS cumulative sumFROM R1GROUP BY CUBE(A1);Listing 5.4: The general form of cumulative queries to generate cumulativevalues for attributes of interestExample 23. [Cumulative value rules] A user asks a query that contains aninequality condition. The query is of the form:Q: SELECT count(∗) FROM movie WHERE rating > 7;Typically, summarization rules contain attribute values and some aggrega-tion statistics (Min, Max, Avg, Sum, Count). To find rules that refine querieswith inequalities (> or <), we must look up the cumulative sum of all ratingsless than 7. This is an expensive query that requires a large operation overthe whole table. Instead, we perform a cumulative query that adds up thecumulative sum of all revenue and counts for ratings. We also add the resultsof this query to the rules table. Furthermore, this step provides this informa-tion for any future queries that want to access cumulative information. Thecumulative query to produce these rules for the query Q is as follows:SELECT rating,(sum(count(∗)) OVER (ORDER BY rating)) AS cumulative count106FROM movieGROUP BY rating;With the CUBE query and cumulative queries, we obtain a set of rulesthat cover the entire database including summary statistics (count, min, max,sum, and average) in addition to cumulative values for attributes of interest(e.g. rating in movies). Those values enable the querying of rules that aredirectly related to the user query that can contain equality or inequalityconditions.5.4.2 Provenance summaryWe use a summarization algorithm that produces a small number of rules kthat summarize the most important properties of the result Q(D). We takethe query result and summarize the provenance. Our summary algorithm canproduce a summary based on the coverage for count queries or the impactof categorical values on numeric measure variables in the query as seen inChapter 4.4.We use sampling to reduce the time it takes to produce a summary. Oursampling method is similar to the one described in Section 4.4.3. We sampleuniformly at random but also keep groups of tuples with a high likelihood ofcontaining high coverage or high impact values. We resample for every newrule to cover as much of the data as possible.5.4.3 Candidate rule miningThe search for candidate rules starts with the cardinality constraints set bythe user. Any rules that do not meet the constraints are filtered out as aninitial step. The rest of the rules that fulfill the constraint are added to alist of candidates C. Combinations of rules that fulfill the constraint are107checked for data-independent containment. If data-dependent containmentis needed, we go down to the tuple level to check for total marginal coverage.This is only done for rules that are not contained in higher-level rules thatare already in C.When individual rules in the rules database do not make up the cardinal-ity constraint set by the user, we need to recommend multiple rules as a setof conjunctive rules that make up the refined answer. In this case, we reduceour problem to the subset-sum problem. In our problem, the total is k′ orthe cardinality target which maps directly to the target sum T in the subset-sum problem. The rules are our individual items are given a value of size(coverage for count) or impact (for sum, or average), and all are non-negativevalues. We want to greedily choose a group of non-overlapping rules that fitthe total. We apply a greedy algorithm to solve this problem in polynomialtime with a guaranteed 1 − ε approximation of the optimal solution. Weleave the error threshold ε up to the user to choose, it affects the result interms of how close the algorithm gets to the cardinality constraint they setthemselves. We use a modified algorithm from [IK75]. Our main modifi-cations relate to pruning the candidates based on sub/super rules, and thevalues being marginal as in no overlap exists between candidate rules thatare input for the algorithm. Algorithm 5 shows the greedy algorithm details.Algorithm 5 is a greedy algorithm that solves the subset sum problem.The first step is to initialize an empty list. Then it proceeds to add rulesone by one. Each rule is checked if it is contained by the previous rule. Ifnot, the rule is added to the list if it does not exceed the size T . Rules arealso trimmed if they are too close to other rules in terms of size; closenessis determined by the approximation factor ε in εT/|Cn|. This last trimmingstep prunes the list and guarantees that the sum does not exceed the target.The algorithm returns a set of rules with a total size close to the target T.As an additional step, the rules in C are augmented with super-rules onlower levels that are contained by other rules in C. The lower-level rules108Algorithm 5: Subset-sum greedy algorithm to find sets of rulesthat satisfy cardinality targetInput: A set of rules Cn with resolved overlap, value T = targetcardinality, ε an approximation ratioOutput: A group of rules C with total cardinality sum T1 C = ∅2 S = all rules of size s < T sorted in ascending order3 for i from 1 to |Cn| do4 foreach r ∈ Cn do5 if r is contained by any rule in Cn: then remove r, break;6 if y + ε.T/|Cn| < (∑C) + r ≤ T then y = r, add r to C;7 return CRmake up a summary of what’s contained in a rule in C. The candidate rulesand their summaries (super-rules) are then added to a final set of candidatesCf that is given to the next component to be embedded and compared.5.4.4 Candidate rules embedding, and rankingCandidate rules with attribute values that are close in order to the attributevalues in the query are prioritized. For example, rules with the Pixar valueare prioritized for a query like Q1 which contains the Disney value. e.g.Adventure, family, and animation genres are close together. The same thingapplies for runtime values.We embed the candidate rules with super rules that make up a sum-mary of the candidate rules. We use Term Frequency Inverse DocumentFrequency [Sal91] vector embedding to facilitate comparison using soft co-sine similarity metric. We chose TFIDF for its simplicity and faster per-formance than other methods, such as one-hot encoding. This metric alsomaintains enough semantic information for our purposes. Our approach forencoding groups of tuples is in the vein of similar work such as [CD03], withthe exception of the absence of query workloads in our case. We treat each109Figure 5.3: t-SNE visualization of TFIDF representation of groups of rulesin example 20 in 2D spacerule and its corresponding super-rules as a single document. While TFIDFis more commonly used in natural language applications, we believe it isequally effective for our purpose. First of all, rules are composed mostlyof categorical variables and those are not unique and can mimic words indocuments. Unique values such as IDs and movie titles would not appearin summary rules and are replaced by the ? value. Second, rules containnumeric values that have been bucketized and thus can be treated the sameway as categorical variables. Third, IDF takes care of common values thatdominate summaries. Such values occur in most rules and are not distinctenough to use for ranking.Example 24. Figure 5.3 shows a t-distributed stochastic neighbor embed-ding (t − SNE [VdMH08]) visualization of the encoded TFIDF vectors in2-dimensional space. The visualization shows clearly how different attributesare encoded differently and clustered together. Furthermore, it shows how110similar values are clustered together, like Disney and Pixar for genre andduration. Whereas equally similar values such as production country areequidistant from each other. This example demonstrates that an encodingof TFIDF is sufficient to reach the suggestions highlighted in the result ofexample 20.After compiling the full list of candidates Cf , and generating the summaryof P (Q(D)), we rank the candidate rules and recommend the top rules tothe user. We use soft cosine similarity to rank the most likely candidates.The model finds the top likely candidates in Cf and ranks them accordingto the degree of similarity to the provenance of results P (Q(D)).5.5 User study5.5.1 Experiment designWe designed a user study to show that our approach gives meaningful anduseful suggestions. We aimed to design tasks that tested the effectiveness andmeaningfulness of our recommendations against those made by the baselinemethods. We refer to our method as the provenance summary method (Prov-Sum). This section aims to show that our method’s recommendations aremeaningful and that users prefer our method of interaction over those of thebaseline machine learning method.Baseline methods For our baselines, we used out-of-the-box machine learn-ing models that recommend users data that is relevant to their query results.Using such baselines, we can show that such methods cannot learn the samestructures and thus cannot match the performance of our framework. Themost suitable methods involve classification, where the query result is thetarget class, and the rest of the data contains both candidates for the targetclass and irrelevant tuples.111This task description falls into the category of Positive Unlabeled Learn-ing (PU learning) [BD20] where the tuples in the query result Q(D) arelabeled as positive. Everything else in the table is unlabeled. With a PUlearning model, we can find labels for the unlabeled data (positive or neg-ative) and show the user the positive results found by the classifier. Toaddress the nature of the nontraditional tabular dataset that has positiveand unlabeled records, Elkan and Noto proposed a method that leveragesthe estimated conditional probability of the positive instances being labeledto calibrate the prediction of a model trained on the labeled and unlabeledexamples [EN08]. Following this approach, we use the pulearn Python pack-age1 with a random forest underlying model to build the first baseline can-didate (baseline 1) for our test scenarios; the bagging meta-algorithm in therandom forests can mitigate the instability of classifiers caused by the PULearning problems [MV14].Additionally, we used the deep tabular data learning model TabNet [AP21]as another baseline candidate (baseline 2), which applies sequential attentionfor feature selection and mimics ensembling with its multi-step architecture.With TabNet, we built a classifier that treats the data as if it was tradition-ally labeled as positive and negative.In order to decide whether to use baseline 1 or baseline 2 in the user study,we conducted an initial walk-through and 2 pilot studies. We concluded thatthe original PUlearn method [EN08] served as a better baseline and removedTabNet [AP21] from the user study. This is simply because the users inthe pilot thought the output of PULearn was more relevant and concise.TabNet was not designed for such a task and the output included a lot ofirrelevant movies. In contrast, PULearn produced a more concise list withmore relevant tuples. Thus, since PULearn would have dominated TabNet,we did not include it in the full user study.We had the following goals for this experiment:1https://pulearn.github.io/pulearn/1121. Establish that our method (provenance summary) provides meaningfulquery refinement recommendations to the user.2. Find out which method (baseline or provenance summary) provides thebest performance and is preferred by users.ParticipantsIn this study, we selected computer science students with experience usingdatabases or tabular data. We define experience as an entry-level databasecourse or equivalent knowledge. We recruited participants through the de-partment of computer science public channels. We recruited 16 participants;we did not restrict recruiting based on other factors than experience withdata. We offered users compensation in the form of 15 dollars.ConditionsWe had two conditions for the recommendation method: provenance sum-marization method (ProvSum), and baseline method (PULearn). As wellas two conditions for the order of presentation: ProvSum first, and baselinefirst.We varied the order of presentation of tasks by dividing users into twogroups: A, and B. Tasks were the same across groups, but the order ofpresentation of recommendation method was varied by group.We conducted the experiment with 16 participants and fully balanced thegroups: A) 8 users started with the baseline method for the first task, andB) 8 users started with the ProvSum method for the first task.TasksThe users were presented with four different tasks. All tasks involved lookingat a pre-written query, formulating a refined query, then evaluating if the113presented suggestions helped in formulating this refined query. A summaryof tasks follows, the full details are in Appendix C.1.3:1. Task 1: Select all Action movies that have total revenue > $100m, andhave a vote average (rating) of >= 7. How would you go about ex-panding this query? Expand this query result by looking at suggestionsmade by our system, and choosing the most relevant ones.2. Task 2: Select all Adventure movies with total revenue > $100m, andhave a vote average (rating) >= 7. How would you go about expandingthis query? Expand this query result by looking at suggestions madeby our system, and choosing the most relevant ones.3. Task 3: Select all movies with total revenue > $100m, that are madeby male directors and released after the year 2015. How would you goabout expanding this query? Expand this query result by looking atsuggestions made by our system, and choosing the most relevant ones.4. Task 4: Select all movies with total revenue > $1m, that are made byfemale directors and released after the year 2015. How would you goabout expanding this query? Expand this query result by looking atsuggestions made by our system, and choosing the most relevant ones.We presented the users with preset queries and data from the IMDBdataset. This dataset included information about movies, genres, and direc-tors. See Section 4.6.2 for a more thorough dataset description. Each userhad to do the 4 tasks. Where they performed 2 tasks with each refinementmethod. For the tasks performed with the provenance summary method,users were presented with summaries of suggestions. Users could navigatethe summaries and examine the details if they wished. For tasks performedwith the baseline method, users were presented with a sample of individualmovies to choose from. We aimed to limit the number of tuples shown sothe mental load would be similar between the two methods. None of the114users were familiar with summary rules, so they needed time to process thenew data format. 5-6 suggestions were shown in the provenance summarymethod, while about 10-15 individual movies were shown in the baselinemethod. Users were allowed to sort or filter the lists as they saw fit.Instead of presenting all users with the 4 tasks using both interfaces for atotal of 8 tasks, we opted for a design where each user would see task 1 witha certain method and then task 2 with a different method. We did the samefor tasks 3 and 4. The two pairs of tasks (1, 2) and (3, 4) are very similar.We claim that tasks 1 and 2 are isomorphic ‘genre’ tasks. Whereas tasks 3and 4 are isomorphic ‘director gender’ tasks. We make this claim becausethose tasks are very similar and ask the user to perform the same steps withslightly different data but similar structures. We expected that there wouldbe strong learning effects, which we tried to avoid by using isomorphic tasks.In other words, we avoided users looking for the same recommendations theypicked with the other method. The order of presentation of methods wouldensure that the tasks are balanced and there is no bias against the methodusers see first in terms of time or preference.DesignOur user study design was a two-factor design. The first factor was meth-ods of recommending refinements (baseline, provenance summary; within-subject). The second factor was the order of presentation (baseline first,provenance summary first; between subject). We used a 2 x 2 design wherethe method of recommendation and the order of presentation were fully bal-anced.ProcedureFigure 5.4 shows the user interface of our system. We started by asking theuser to fill out a consent form. After that, each user took a demographic ques-tionnaire on a laptop. In the questionnaire, we collected user data (age, and115Figure 5.4: User interfaceexperience with databases). We also assessed users’ familiarity with the do-main (Movies dataset). We gave users a brief introduction to the data, tables,and user interface. We then briefed them about the tasks to be performed.Depending on which group they belonged to, the order of presentation of therefinement method was different, but the tasks remained consistent. Partici-pants in group A experienced task 1 using the ProvSum method. Participantsin group B experienced task 1 using the baseline method and so on.To proceed, the user would sit in front of a laptop. We instructed theuser to start a task. The moderator started the timer. The user performedthe task as instructed. The moderator stopped the timer at the end of thetask and asked the user to verbally evaluate satisfaction after the task andbriefly justify their choices. After all tasks were complete, we asked usersto fill in an exit questionnaire digitally on a laptop, see Appendix C.1.3 fordetails. The questionnaire has quantitative and qualitative questions that aresubjective. We used a 1-5 Likert scale for quantitative questions. We also116included questions of the form “If no, please explain” or “Please, explain.”to gain some qualitative feedback.In cases where the experiments had to be performed remotely, we had thesystem deployed on a server. Users were asked to perform the tasks throughtheir browsers while sharing their screens to be observed by the moderatorconducting the study. The questionnaires were filled out through a differenttab in the browser. 10 experiments out of the total of 18 were conductedremotely. We did not observe any effect on the time to perform tasks or thequality of answers.ApparatusWe used the following tools: a laptop with the software interface open in abrowser tab, a timer, and input forms open in a different tab. For remotestudies, we used Zoom to observe participants and asked them to share theirscreens. We deployed the system and allowed users to access it through alink.Variables and hypotheses• Independent variables: type of refinement method (baseline, prove-nance summary).• Dependent variables: Time to perform a task, satisfaction (subjec-tive 1-5 Likert scale), perceived usefulness and preference (subjective1-5 Likert scale).We measured each variable as follows:• Time: Timer from start to finish of the task. The timer started whenusers hit start. We define the end of the task as the point when theuser hit “submit result”.• Satisfaction: 1-5 Likert scale question after each task.117• Usefulness and preference: Subjective quantitative (1-5 Likert scale)and qualitative questions on usefulness and preference in exit question-naire.Hypotheses: We tested the following hypotheses:Performance (Task completion time)• H1: Users will perform the tasks faster with the provenance summarymethod compared to the baseline method.Usefulness and satisfaction• H2: Users will rate the provenance summary method higher in termsof perceived usefulness compared to the baseline method.• H3: Users will rate the provenance summary method higher in termsof perceived satisfaction compared to the baseline method.Limitations/ProblemsWe present our limitations regarding the different categories of threats tovalidity:Internal validity: We attempted to make the size of output for bothmethods equal. However, the Pu-learn methods generate more tuples thanour method generates rules. In our pilot study, we limited the tuples tothose with the highest accuracy. We also note that rules are harder to readand decipher and take longer for users. Therefore, we limited the ratio oftuples to rule to 3:1. We think this is fair as we observed users make quickdecisions about tuples but take 2-3 times longer to make decisions aboutrules. Furthermore, satisfaction and preference can be affected by elementsthat we cannot measure or control.Statistical validity: We believe we used the appropriate statistical tests.We also verified the assumptions of the tests before we ran them on our datato make sure they are appropriate.118External validity: The results should give a good representation of howusers would interact with our system.Ecological validity: Our tasks should be representative. We validatedthem with a small pilot study before proceeding with the full study.5.5.2 User Study results16 participants completed the study. 2 Results show participants favor ourmethod of interaction over presenting individual tuples. They also favor ourrecommendations over those presented by the baseline methods. In theirevaluation of the suggestions of both methods, most users picked the mostsemantically similar tuples or rules. We noticed users gravitate towards Ad-venture movies when the query is about Action movies and vice versa. Thisshows that our intuition in ranking rules according to semantic similarity issound.Time. We saw statistically significant effects of the different methods on thetime it took to complete a task, and the perceived usefulness of the methods.We report significance as P < 0.01. We ran an ANOVA test after runningsome checks to make sure it applies to our data. We ran a Bartlett test tocheck for homogeneity of variances, a Shapiro-Wilk normality test and drewqqplots to check normality. The ANOVA test we ran took method x groupas factors. Groups represent the order of presentation. The results of thetest show a significant main effect of the method (F = 41.67, P < 0.001) onthe time it takes to finish a task. We observed no significant effect of theorder of presentation (F = 2.01, P > 0.1) and no interaction effect betweenthe two factors (F = 2.88, P > 0.09). We also ran a separate test to makesure there was no significant effect between the different tasks (P > 0.01).In general, it took less time to finish tasks with ProvSum than PULearn,the breakdown for tasks and method statistics is in Table 5.3. It also took2The study was approved as minimal risk by the Behavioural Research Ethics Boardat the University of British Columbia. UBC BREB number:H21-03344.119more time to finish tasks for people in group A (Mean = 100.5 seconds)than in group B (Mean = 83.25), but this was not statistically significant,according to our tests.Task ProvSum PULearnt1 54.7 116.9t2 53.9 82.6t3 53.7 183.7t4 48.7 141.8Table 5.3: Table shows the average time (in seconds) it took users to finishtasks using the two methods (ProvSum and PULearn).Figure 5.6 presents the full set of results for time for the two groups. wesee the time it took users from both groups A and B to finish the tasks. Wesee group A took significantly longer to finish tasks with PULearn (t1 andt3) than tasks with ProvSum (t2 and t4). This effect is less pronounced forgroup B but still significant. Group B used ProvSum for t1 and t3 and usedPUlearn in t2 and t4. Figure 5.7 shows the breakdown of time by method,for ease of reading.Usefulness. We collected usefulness measurements as a question at the endof experiments, asking participants to evaluate usefulness on a 1-5 Likertscale where 1 is very useful and 5 is very useless. We collected two groupsof measurements: How users felt about ProvSum suggestions (mean = 1.3)and how they felt about PULearn suggestions (mean = 2.25). We ran a non-parametric test to compare the two measurements: the Wilcoxon SignedRanks test. We found a significant difference between the perceived use-fulness of the two methods (adjusted p=0.002). In Figure 5.5, we see thatmost users rated ProvSum as very useful, and only 1 user picked the neutralrating. The majority of users rated PULearn as useful or neutral, with only1 user rating it as very useful. None of the users rated either as less thanneutral (3).Satisfaction. We collected satisfaction measurements as a question at the120end of every task. We asked users to evaluate their satisfaction on a 1-5Likert scale. We ran a non-parametric test to compare the two measurements(satisfaction for group A and group B for each task). We ran the WilcoxonSigned Ranks test. We did not find a significant difference between the twogroups depending on which method was used to finish the task (adjustedp=0.9).Qualitative results. Users wrote justifications for their choices and an-swered open-ended questions. Notably, users commented that our rules areoptimal if the user is not familiar with the dataset. Individual movie rec-ommendations only worked for those familiar with the data or the domain.Users with no familiarity with movies (at least 3 of our users said they werenot familiar with American movies at all) had a hard time picking recom-mendations from a list of individual movies and much preferred the groupingformat of our rules. Some quotes from our users: “individual movies wouldgive more accurate answers but patterns are easier to use/interact with”,“The pattern tool gives very clear presentation. I think it would be very use-ful for such tasks.”, “It took time to find answers in the individual movies,time-consuming. The pattern is preferred.”.Discussion. We saw a significant effect on both usefulness (p < 0.002) andtime (p < 0.001). This leads us to believe that our hypotheses (H1 and H2)are supported. We did not find a significant effect on satisfaction to supportour third hypothesis (H3) (p > 0.5). We suspect that satisfaction was highacross the board because the question was asked after every task is doneand did not account for how much effort it took to finish the task. Perhapsa question about difficulty would have served us better. Usefulness datawas collected at the end of the experiment so users had an idea about bothmethods and could evaluate them with more complete knowledge. We didnot test for accuracy or errors because the tasks are fairly open-ended andsubjective. We did, however, inspect the responses by users and ask users toevaluate their choices. The qualitative answers give insight into how users1211234ProvSum PULearnMethodUsefulness (1−5)Figure 5.5: Users’ perceived usefulness for both types of refinement method(1: very useful - 5: Very useless).see their choices and how they feel about the two methods. All users showedinterest in our suggestions and none of them asked for different suggestions.They also commented that our suggestions work better for users unfamiliarwith the data which is the intended goal of our approach.This user study showed evidence that refinement suggestions are usefuland usable. We also showed that our users prefer our method’s suggestionsto those of comparable machine learning methods.5.6 Performance evaluationThis section has three objectives: (a) to evaluate the performance of ourprovenance summarization method and show it can work in real-time; (b) tocompare our method with machine learning methods and show provenancesummaries outperform those baselines in terms of real-time performance; and122050100150200t1 t2 t3 t4taskTime (seconds)groupABFigure 5.6: The time it took users to complete tasks for both groups ofusers (Group A started with the PULearn method, Group B started withthe ProvSum method)123050100150200t1 t2 t3 t4taskTime (seconds)methodprovsumpuFigure 5.7: The time it took users to complete tasks using both methods.124(c) to conduct experiments to show how our system compares to a baselinein query refinement in terms of interaction and output.5.6.1 Experimental SetupWe implemented our algorithms in Python and ran the experiments on amachine with a 3.4GHz Intel CPU and 32 GB RAM that uses PostgreSQL10. The provenance generation component is Perm [GMA13].We implemented our method and 2 baselines as described in the previoussection: PULearn and TabNet. We found TabNet, in general, to be moreexpensive to train. Since our problem requires retraining with every newquery, TabNet would take way too long (up to a day or so) for many experi-ments and including the results in the graphs would completely distort them.Hence we omit TabNet results where it becomes impossible to meaningfullyplot them with the other methods.datasets As far as we know, there is no standard benchmark for queryrefinement. We used two datasets to conduct our experiments: IMDB, andTPC-H. The data characteristics are as follows: The number of tuples (|D|):181k + 323k (IMDB), and 60k-3m (TPC-H). The number of tables (N): 3(IMDB) and 8 (TPC-H). The total number of attributes in the tables (mD):15 (IMDB) and 61 (TPC-H). The number of queries (q): 4 (IMDB) and 5(TPC-H).IMDB. We used a subset of the IMDB dataset with 3 tables, Movies, Genre,and Directors. The movies table included revenue for which we calculatedthe aggregate results. We used this dataset for performance analysis. Inthose experiments, we ran the same queries that were run in the user studywith a different number of attributes and different aggregate functions:SELECT G1, G2, ..., f(Rev) FROM Movies m, Directors dWHERE m.Director = d.Name GROUP BY G1, G2, ...This is the same dataset we used in Chapter 4.125Q5 Q6Q1 Q10 Q360k300k600k1.5m 3m 60k300k600k1.5m 3m60k300k600k1.5m 3m0.11.010.0100.00.11.010.0100.0sizeTime (seconds) logmethodprovsumPULearnFigure 5.8: Effect of |D| in TPC-H.TPC-H. We used TPC-H for performance experiments and to show howour methods handle queries with multiple types of aggregation and multiplecomplex joins.3 We varied the database size as follows: 60k, 300k, 600k, 1.5m,and 3m. In the TPC-H experiments, we ran five queries, Q1, Q3, Q5, Q6, Q10,as generated by the TPC-H tool. We chose those queries because they containfeatures covered by our provenance summarization method.5.6.2 Runtime PerformanceExp-1: Effects of |D|. Figure 5.8 shows clearly that our approach growslinearly with size while outperforming the machine learning methods. This3http://www.tcp.org/hspec.html126Q3 Q4Q1 Q2provsumPULearnTabNetprovsumPULearnTabNet010203040010203040methodTime (seconds)Figure 5.9: Method and time in IMDB.Q1 Q2 Q3 Q4PULearnPULearnPULearnPULearn0.00.51.01.52.02.5methodTime (seconds)stepPredictionTrainingFigure 5.10: Breakdown of prediction/training for PULearn in IMDBdataset.127Q1 Q2 Q3 Q4indexno indexindexno indexindexno indexindexno index0.000.030.060.09methodTime (seconds)Figure 5.11: Effect of indexing in IMDB.04812provsummethodTime (seconds)querycumulative_queriesindex_creationview_creationFigure 5.12: Preprocessing steps breakdown in IMDB.12801020304060k300k600k1.5m 3msizeTime (seconds)Stepcumulative_queryindex_creationview_creationFigure 5.13: Preprocessing steps breakdown in TPC-H.is mostly because training takes a long time even for smaller data sizes. Pre-diction, on the other hand, performs really well at small sizes. The problemis that machine learning methods need to train after every user query. Theonly exception is Q5 in TPC-H, where PULearn outperforms and scales bet-ter than our method. This is due to the small size of the query results whichminimizes the training time. Figure 5.9 shows the results for the IMDBdataset with the same trend we saw in the TPC-H data, except that nowwe see provsum outperforming the other methods. TabNet performs muchworse but it executes here, whereas, for the TPC-H data, TabNet takes toolong when data sizes exceed 600k tuples (over 1 hour).Exp-2: Effects of optimizations. We do not address the effects of sam-pling on summarization methods because it is already addressed in the previ-ous chapter. Summarization is also prohibitively expensive without sampling.The other major optimization is the indexing of the rules table. We buildindexes that facilitate access to key attributes in the rules table. Figure 5.11shows the effect on the IMDB dataset.Exp-3: Preprocessing costs. Figures 5.12 and 5.13 show the prepro-cessing times. Preprocessing is not as costly as we initially expected. It is129an offline step performed once at the beginning of the process. The CUBEqueries are surprisingly fast on modern hardware. The indexes take almost aslong to build as the CUBE queries take to execute. The cumulative queriesand joins to the rules table are quite fast, in comparison. For larger sizes(> 1.5m), the preprocessing is better left as an offline step but for smallerdata, it can work as an online step and still achieve real-time performance(under 1 minute).Exp-4: Comparison to existing query refinement solutions. Ourapproach is the only one as far as we can tell that is completely automatedand does not require much user interaction. We compared our approach toan implementation of the query refinement system in [MK08, MK09] to seehow many steps it would take a user to arrive at their best refinement whencompared to ours. We ran the same query Q1 to see how the system behaved.The lack of hierarchy limited our options for categorical variables; therefore,we set the same numeric values for revenue > 300m and rating > 7. Thesystem took our input query, as well as a cardinality constraint, k. Thesystem gave us an estimate for the number of tuples at that level, asked usto refine one of the two attribute values (revenue or rating), and providedestimates at different levels. Proceeding with the query, we provided a smallernumber for revenue and hit the target after 2 more refinements at revenue >95m. We note that a user with very little knowledge of the data wouldfind it difficult to navigate these suggestions. Whereas for our approach,the user would only have to submit the query with feedback and receive thesame answer contained within a set of suggestions. The main shortcomingof our solution, in comparison, is that it relies heavily on the bucketizationof numeric values, whereas the other approaches provide a more fleshed-outapproach to refining numeric attributes. Both approaches can complementeach other to achieve better summaries of categorical and numeric attributes.Discussion. Machine learning models require very costly training after everyquery, which makes them ill-suited for this problem. However, PUlearn meth-130ods are still comparable despite some assumptions about the data. Thoseassumptions include: 1) labeled data being selected randomly, and 2) the twoclasses (positive and negative) being naturally separate. Those assumptionsare not necessarily in line with the problem. The positive set isn’t necessarilyrepresentative and the 2 classes can be highly subjective. The approach isstill useful despite those assumptions.Another hurdle to using PULearn methods is the encoding of categoricaldata. 1-hot encoding is prohibitively expensive for any reasonably sizeddataset. In our experiments, 1-hot encoding became unusable at the secondscale for TPC-H and wasn’t usable at all for the IMDB dataset. We optedfor a simpler encoding of converting categorical values into numbers. Thisencoding adds order to non-ordinal values which could prove problematic forsome classifiers but seemed to be the only reasonable solution in terms ofscalability.Our main goal with these experiments was to show the scalability andreal-time performance of our method. As we can see with the TPC-H exper-iments, our query refinement approach works in real-time even at larger datasizes. Sampling and indexing contribute to this performance. Reducing thenumber of attributes also works to improve performance.We also show briefly, in comparison to [MK09], that our approach worksto give automated suggestions that the baseline here would take several stepsto show to the user, if at all.We set out to show the performance and scalability of our approach. Ourexperiments demonstrate that we can perform query refinement in real timefor datasets or sizes up to 3m tuples. With our user study, we demonstratedthat our refinement suggestions are useful and usable. We also showed thatour users prefer them to the output of comparable machine learning meth-ods.1315.7 Conclusion and future workIn this chapter, we presented a novel, automated, and data-centric approachto query refinement. This approach utilizes provenance summaries and sum-mary rules to present users with suggestions that can help them refine theiruncertain queries. With the performance experiments, we fully evaluatedour solution and studied the effects of different factors. In the user study weconducted, we showed that users prefer our recommendations against thosegenerated by machine learning methods. We also showed that our methodgives useful and meaningful recommendations. Given the results of our ex-periments and user study, we can conclude that our approach to query re-finement performs well and in real-time. There is more to be done to expandthe class of queries as well as the possible recommendations to include joinsand set operations. We leave those items as future work recommendationsthat we expand on in the following chapter.132Chapter 6Conclusions and future workThe main focus of this thesis has been on examining data provenance inthe context of relational database management systems from the perspectiveof potential users. The thesis does not present a single solution or systemthat addresses usability, instead, it works in three complementary differ-ent directions. The first direction is a visualization of relational provenanceinformation in a specific context. The second direction is summarizing rela-tional provenance information of aggregation queries for general applicationsto improve usability. The third direction had the goal of curating provenanceinformation of aggregation queries to address a specific challenge, that of ag-gregate query refinement. All three directions address related issues with theusefulness and usability of provenance information in relational databases.For the conclusion of this thesis, we will list a summary of contributionsfor each direction and give some brief future work recommendations. Fur-thermore, we will also include a discussion section to outline how this thesistackled the challenges posed and where it fits within the literature.1336.1 Summary of chapters and future workIn Chapter 3, we went through the process of developing a system we namePastwatch. We based our approach on certain principles from the literatureon data provenance and visualization. We touched briefly on the summa-rization of provenance as a component of this system. We conducted a userstudy to take in the user perspective on how such a system compares to onewith minimal effort to present provenance information. Our results showsignificant effects of visualization and curation techniques we employed inPastwatch.We left Chapter 3 with the following recommendations:1. Summarization techniques need further exploration to develop sum-maries that help users in different scenarios. This is an item that wewill cover in the next chapter.2. For more general-purpose applications, provenance can be catered tothe user with automated visualization suggestions such as those pre-sented in [DD19].In Chapter 4, we looked at provenance summarization for multiple pur-poses and devised different solutions for different scenarios. Impact sum-maries for users interested in certain numeric values. Comparative summariesfor users interested in comparing two or more values in an aggregate queryresult. Join summaries for queries with join. As well as different scenariosdepending on the different aggregate functions.For future work, we recommend the following:1. Support for nested queries with similar mechanics that we discussedfor join queries. However, the scalability of such queries is a concerngiven the added complexity of sub-queries and joins.2. We use contribution semantics for impact summaries. Other semanticssuch as [Sha97] are gaining traction in the field as a serious alternative.1343. Our focus was on optimizing sub-modular functions. Assuming a lackof sub-modularity, we briefly explored alternative score functions in B.Those functions would not work with the greedy algorithms we proposeand as such, we left them as future work.Last but not least, Chapter 5 presents an approach to query refinementfor aggregation queries. This approach is data-centric in that it mines thedata for useful refinement suggestions and does not rely on generating newqueries. Instead, the suggestions are shown to the users in the form of groupsof data.There is more work to be done in this area:1. In terms of expanding the class of queries. One direction is to expandthe work to include sub-queries. A simple and natural extension is toallow sub-queries without aggregation. However, nested aggregationpresents the extra complexity of dealing with multiple aggregates atmultiple levels.2. Another extension is giving the system the ability to suggest new joins.Techniques such as [ZNDM19] can be used to automate join discoveryas a more advanced method than relying on database constraints.Throughout the work in this thesis, we have used user-centric experiments(user studies in Chapters 3 and 5 and a user survey in Chapter 4). Weused those approaches not only to validate our work and results but alsoas a means to inform our design and validate our evaluation metrics. Webelieve any claims made about usability should be informed by the users andthis is the approach to research we took to inform our findings. We believegrounding our work in usability and following what we hope are best practiceshas helped us get closer to the goal of usable provenance information in thiscontext.1356.2 Discussion and reflectionsIn Chapter 1, we outlined 3 challenges. To reiterate them briefly:1. Provenance information needs to be visualized in a way that facilitatesexploration. Insightful visualizations of all aspects of provenance areimportant.2. The volume of provenance information for an aggregation result can belarge and prohibitive for exploration.3. When a user issues an erroneous aggregate query, provenance plays arole in looking at the origin of the answer but not finding the correctanswer. We utilize the techniques developed to tackle the first twochallenges to solve this one.Throughout this thesis, we have described solutions that we believe con-tribute to addressing these challenges. To summarize how we tackled thesechallenges:1. We presented a provenance visualization framework that includes allthe elements of provenance in databases. Furthermore, we presentedthe results of a user study we conducted to show that users prefer cu-rated and visualized provenance data and can use such data to performtasks more efficiently.2. We tackled the problem of aggregation provenance by presenting solu-tions to summarize this provenance. We present two different summa-rization methods with the main goal of supporting meaningful explo-ration of provenance information.3. We aimed to solve the aggregate query refinement problem using prove-nance summaries and data summaries. In doing so, we posed a problemwhere provenance data is useful if not sufficient by itself. We used thetechniques we developed in our work to handle this new problem.136Throughout these chapters, we presented user-centering methods to eval-uate our solutions. We believe that in doing so, we can further emphasize theneed for such methods in database research. In all our cases, we observeda relationship between performance experiments and user studies. Whileperformance experiments are great for evaluating efficiency, the objectivemetrics often proposed within may not always align with those important tousers. We hope our work on user experiments will motivate future researchin usability and efficiency.There is still a lot of work to be done in the area of provenance. Wehope that this thesis presents ample work in addressing some of the majorchallenges. The future is clearly headed toward employing such techniquesto explain the results of machine learning models. The challenges of visu-alization/summarization and improving usability are at the forefront of thisdirection. We believe our work can contribute to that, and we can furtherextend some of it in this direction.We have explored the use of machine learning methods in our query re-finement problem (Chapter 5) and found them lacking. Databases are atricky field for machine learning or deep learning approaches to be sufficienton their own, without tremendous engineering effort to make them fit. Themain challenge comes up when we have a lack of training data such as querylogs, session logs, or workloads. We presented our work to fill a gap wheresuch information may not be present or transferable from another domain.As with any other work, there are limitations to what can be done whentrying to work in two different directions. Doing deeply technical work whileutilizing user studies means one of these aspects will not be fully developedor explored. We did not purposefully undermine one side for the other, weattempted to balance both aspects of this work. While not the main focusof this thesis, we hope the user experiments described here will help to buildthe standards for user studies in database research.137Bibliography[ABC+10] Umut A Acar, Peter Buneman, James Cheney, Jan VanDen Bussche, Natalia Kwasnikowska, and Stijn Vansummeren.A graph model of data and workflow provenance. In TaPP,2010.[ABD+15] Eleanor Ainy, Pierre Bourhis, Susan B. Davidson, DanielDeutch, and Tova Milo. Approximated summarization of dataprovenance. In CIKM, pages 483–492, 2015.[ABL10] Manish Kumar Anand, Shawn Bowers, and Bertram Ludascher.Provenance browser: Displaying and querying scientific work-flow provenance graphs. In ICDE, pages 1201–1204, 2010.[ADG18] Efrat Abramovitz, Daniel Deutch, and Amir Gilad. Questpro:queries in sparql through provenance. Proceedings of the VLDBEndowment, 11(12):1994–1997, 2018.[ADT11] Yael Amsterdamer, Daniel Deutch, and Val Tannen. Prove-nance for aggregate queries. In PODS, page 153–164, 2011.[AFG+18] Bahareh Sadat Arab, Su Feng, Boris Glavic, Seokki Lee, XingNiu, and Qitian Zeng. Gprom-a swiss army knife for yourprovenance needs. A Quarterly bulletin of the Computer So-ciety of the IEEE Technical Committee on Data Engineering,41(1), 2018.138[AKS+18] Firas Abuzaid, Peter Kraft, Sahaana Suri, Edward Gan, EricXu, Atul Shenoy, Asvin Ananthanarayan, John Sheu, Erik Mei-jer, Xi Wu, Jeff Naughton, Peter Bailis, and Matei Zaharia.Diff: A relational interface for large-scale data explanation.PVLDB, 12(4):419–432, 2018.[ALMP19] Omar AlOmeir, Eugenie Yujing Lai, Mostafa Milani, andRachel Pottinger. Summarizing provenance of aggregationquery results in relational databases. http://www.cs.ubc.ca/~mkmilani/report.pdf, 2019.[ALMP20a] Omar AlOmeir, Eugenie Yujing Lai, Mostafa Milani, andRachel Pottinger. The Pastwatch: On the usability of prove-nance data in relational database systems. In ICDE, page FourPages. To appear., 2020.[ALMP20b] Omar AlOmeir, Eugenie Yujing Lai, Mostafa Milani, andRachel Pottinger. The pastwatch: On the usability of prove-nance data in relational databases. In 2020 IEEE 36th Inter-national Conference on Data Engineering (ICDE), pages 1882–1885. IEEE, 2020.[ALMP21] Omar AlOmeir, Eugenie Yujing Lai, Mostafa Milani, andRachel Pottinger. Summarizing provenance of aggregate queryresults in relational databases. In 2021 IEEE 37th Interna-tional Conference on Data Engineering (ICDE), pages 1955–1960. IEEE, 2021.[AP21] Sercan O. Arik and Tomas Pfister. Tabnet: Attentive inter-pretable tabular learning. Proceedings of the AAAI Conferenceon Artificial Intelligence, 35(8):6679–6687, May 2021.139[AS79] Alan C Acock and Gordon R Stavig. A measure of associationfor nonparametric statistics. Social Forces, 57(4):1381–1386,1979.[AS94] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithmsfor mining association rules in large databases. In VLDB, pages487–499, 1994.[ASZ14] Abdullah Albarrak, Mohamed A Sharaf, and Xiaofang Zhou.Saqr: An efficient scheme for similarity-aware query refinement.International Conference on Database Systems for AdvancedApplications, pages 110–125, 2014.[BCHC09] Jacob Benesty, Jingdong Chen, Yiteng Huang, and Israel Co-hen. Pearson correlation coefficient. In Noise reduction inspeech processing, pages 37–40. Springer, 2009.[BCTV05] Deepavali Bhagwat, Laura Chiticariu, Wang-Chiew Tan, andGaurav Vijayvargiya. An annotation management system forrelational databases. The VLDB Journal, 14(4):373–396, 2005.[BD20] Jessa Bekker and Jesse Davis. Learning from positive and unla-beled data: A survey. Machine Learning, 109(4):719–760, 2020.[BHT16] Nicole Bidoit, Melanie Herschel, and Katerina Tzompanaki.Refining sql queries based on why-not polynomials. TaPP,8:136, 2016.[BKWC01] Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. Whyand where: A characterization of data provenance. In ICDT,pages 316–330, 2001.[BMR97] Stefano Bistarelli, Ugo Montanari, and Francesca Rossi.Semiring-based constraint logic programming. In IJCAI (1),pages 352–357, 1997.140[BOH11] Michael Bostock, Vadim Ogievetsky, and Jeffrey Heer. D3 data-driven documents. IEEE Transactions on Visualization andComputer Graphics, 17(12):2301–2309, 2011.[BYB+13] Michelle A Borkin, Chelsea S Yeh, Madelaine Boyd, PeterMacko, Krzysztof Z Gajos, Margo Seltzer, and Hanspeter Pfis-ter. Evaluation of filesystem provenance visualization tools.IEEE Transactions on Visualization and Computer Graphics,19(12):2476–2485, 2013.[CCD+13] Ugur Cetintemel, Mitch Cherniack, Justin DeBrabant, Yan-lei Diao, Kyriaki Dimitriadou, Alex Kalinin, Olga Papaem-manouil, and Stan Zdonik. Query steering for interactive dataexploration. CIDR 2013 - 6th Biennial Conference on Innova-tive Data Systems Research, pages 1–4, 2013.[CCT09] James Cheney, Laura Chiticariu, and Wang-Chiew Tan. Prove-nance in databases: Why, how, and where. Now Publishers Inc,2009.[CD03] Surajit Chaudhuri and Gautam Das. Automated ranking ofdatabase query results. In In CIDR. Citeseer, 2003.[CH03] Hana Chockler and Joseph Y. Halpern. Responsibility andblame: A structural-model approach. In IJCAI, pages 147–153, 2003.[CH06] Kwok Cheung and Jane Hunter. Provenance explorer–customized provenance views using semantic inferencing. InISWC, pages 215–227. Springer, 2006.[CJ07] Adriane Chapman and HV Jagadish. Issues in building prac-tical provenance systems. IEEE Data Eng. Bull., 30(4):38–43,2007.141[CJ09] Adriane Chapman and HV Jagadish. Why not? In Proceed-ings of the 2009 ACM SIGMOD International Conference onManagement of data, pages 523–534, 2009.[CLMT22] Adriane Chapman, Luca Lauro, Paolo Missier, and RiccardoTorlone. Dpds: assisting data science with data provenance.Proceedings of the VLDB Endowment, 15(12):3614–3617, 2022.[CM13] Ka Kei Chan and Alistair Milne. The global legal entity identi-fier system: Will it deliver? Available at SSRN 2325889, 2013.[CM19] Ka Kei Chan and Alistair Milne. The global legal entity iden-tifier system: How can it deliver? J. of Risk and FinancialManagement, 12(1), 2019.[CTV05] Laura Chiticariu, Wang-Chiew Tan, and Gaurav Vijayvargiya.DBNotes: a post-it system for relational databases based onprovenance. In SIGMOD, pages 942–944, 2005.[CW00] Yingwei Cui and Jennifer Widom. Lineage tracing in a datawarehousing system. In ICDE, pages 683–684, 2000.[CWW00] Yingwei Cui, Jennifer Widom, and Janet L Wiener. Tracingthe lineage of view data in a warehousing environment. TODS,25(2):179–227, 2000.[DD19] Victor Dibia and Cagatay Demiralp. Data2vis: Automatic gen-eration of data visualizations using sequence-to-sequence recur-rent neural networks. IEEE Computer Graphics and Applica-tions, 39:33–46, 2019.[DF08] Susan B Davidson and Juliana Freire. Provenance and scientificworkflows: challenges and opportunities. In Proceedings of the2008 ACM SIGMOD international conference on Managementof data, pages 1345–1350, 2008.142[DGS22] Vargha Dadvar, Lukasz Golab, and Divesh Srivastava. Ex-ploring data using patterns: A survey. Information Systems,108:101985, 2022.[DP13] Marina Drosou and Evaggelia Pitoura. YmalDB: Exploringrelational databases via result-driven recommendations. VLDBJournal, 22(6):849–874, 2013.[DPD16] Kyriaki Dimitriadou, Olga Papaemmanouil, and Yanlei Diao.Aide: An active learning-based approach for interactive dataexploration. IEEE Transactions on Knowledge and Data Engi-neering, 28:2842–2856, 2016.[DSBHW06] A Das Sarma, Omar Benjelloun, Alon Halevy, and JenniferWidom. Working models for uncertain data. In ICDE, pages7–7, 2006.[EGAG+14] Kareem El Gebaly, Parag Agrawal, Lukasz Golab, Flip Korn,and Divesh Srivastava. Interpretable and informative explana-tions of outcomes. PVLDB, 8(1):61–72, 2014.[EGFG+18] Kareem El Gebaly, Guoyao Feng, Lukasz Golab, Flip Korn, andDivesh Srivastava. Explanation tables. Sat, 5:14, 2018.[EL02] Thomas Eiter and Thomas Lukasiewicz. Complexity results forstructure-based causality. Artif. Intell., 142(1):53–89, Novem-ber 2002.[EN08] Charles Elkan and Keith Noto. Learning classifiers from onlypositive and unlabeled data. In Proceedings of the 14th ACMSIGKDD International Conference on Knowledge Discoveryand Data Mining, KDD ’08, page 213–220, New York, NY,USA, 2008. Association for Computing Machinery.143[FGS17] Guoyao Feng, Lukasz Golab, and Divesh Srivastava. Scalableinformative rule mining. In 2017 IEEE 33rd International Con-ference on Data Engineering (ICDE), pages 437–448. IEEE,2017.[FM19] Anna Fariha and Alexandra Meliou. Example-driven query in-tent discovery: Abductive reasoning using semantic similarity.arXiv preprint arXiv:1906.10322, 2019.[Fre09] David A Freedman. Statistical models: theory and practice.cambridge university press, 2009.[GD07] Boris Glavic and Klaus R Dittrich. Data provenance: A cat-egorization of existing approaches. In BTW, volume 7, pages227–241, 2007.[GKKS10] Lukasz Golab, Howard Karloff, Flip Korn, and Divesh Srivas-tava. Data auditor: Exploring data quality and semantics usingpattern tableaux. Proceedings of the VLDB Endowment, 3(1-2):1641–1644, 2010.[GKT07] Todd J Green, Grigoris Karvounarakis, and Val Tannen. Prove-nance semirings. In PODS, pages 31–40, 2007.[Gla14] Boris Glavic. A primer on database provenance. Technicalreport, IIT, 2014.[GMA13] Boris Glavic, Rene´e J. Miller, and Gustavo Alonso. Using SQLfor Efficient Generation and Querying of Provenance Informa-tion, pages 291–320. Springer Berlin Heidelberg, 2013.[HCDN08] Jiansheng Huang, Ting Chen, AnHai Doan, and Jeffrey FNaughton. On the provenance of non-answers to queriesover extracted data. Proceedings of the VLDB Endowment,1(1):736–747, 2008.144[HH10a] Melanie Herschel and Mauricio A Herna´ndez. Explaining miss-ing answers to spjua queries. Proceedings of the VLDB Endow-ment, 3(1-2):185–196, 2010.[HH10b] Melanie Herschel and Mauricio A Herna´ndez. Explaining miss-ing answers to spjua queries. Proceedings of the VLDB Endow-ment, 3:185–196, 9 2010.[HSM07] Pat Hanrahan, Chris Stolte, and Jock Mackinlay. visual anal-ysis for everyone. Tableau White paper, 4, 2007.[HW22] Zezhou Huang and Eugene Wu. Reptile: Aggregation-level ex-planations for hierarchical data. In Proceedings of the 2022International Conference on Management of Data, SIGMOD’22, page 399–413, 2022.[IK75] Oscar H Ibarra and Chul E Kim. Fast approximation algo-rithms for the knapsack and sum of subset problems. Journalof the ACM (JACM), 22(4):463–468, 1975.[JDB20] Eduardo Jandre, Bruna Diirr, and Vanessa Braganholo. Prove-nance in collaborative in silico scientific research: a survey.ACM SIGMOD Record, 49(2):36–51, 2020.[JGMP15] Manas Joglekar, Hector Garcia-Molina, and AdityaParameswaran. Smart drill-down: A new data explorationoperator. PVLDB, 8(12):1928–1931, 2015.[JGP14] Manas Joglekar, Hector Garcia-Molina, and Aditya G.Parameswaran. Smart drill down. CoRR, abs/1412.0364, 2014.[JGP16] M. Joglekar, H. Garcia-Molina, and A. Parameswaran. Inter-active data exploration with smart drill-down. In ICDE, pages906–917, 2016.145[KIT10] Grigoris Karvounarakis, Zachary G Ives, and Val Tannen.Querying data provenance. In SIGMOD, pages 951–962, 2010.[KLD11] Bhargav Kanagal, Jian Li, and Amol Deshpande. Sensitivityanalysis and explanations for robust query evaluation in prob-abilistic databases. In SIGMOD, pages 841–852, 2011.[KOF+16] Troy Kohwalter, Thiago Oliveira, Juliana Freire, Esteban Clua,and Leonardo Murta. Prov viewer: a graph-based visualizationtool for interactive exploration of provenance data. In IPAW,pages 71–82. Springer, 2016.[LAB+06] Bertram Luda¨scher, Ilkay Altintas, Chad Berkley, Dan Higgins,Efrat Jaeger, Matthew B Jones, Edward A Lee, Jing Tao, andYang Zhao. Scientific workflow management and the kepler sys-tem. Concurrency and Computation: Practice and Experience,18(10):1039–1065, 2006.[LLG20] Seokki Lee, Bertram Luda¨scher, and Boris Glavic. Approximatesummaries for why and why-not provenance. Proceedings of theVLDB Endowment, 13(6):912–924, 2020.[LLM+22] Chenjie Li, Juseung Lee, Zhengjie Miao, Boris Glavic, andSudeepa Roy. Cajade: Explaining query results by augmentingprovenance with context. Proceedings of the VLDB Endowment,15(12):3594–3597, 2022.[LLP14] Ting Li, Victoria L. Lemieux, and Rachel Pottinger. Challengesin resolving semantic heterogeneity with the global legal entityidentifier system. In DSMM, pages 14:1–14:2, 2014.[LMZ+21] Chenjie Li, Zhengjie Miao, Qitian Zeng, Boris Glavic, andSudeepa Roy. Putting things into context: Rich explanationsfor query answers using join graphs. Proceedings of the ACM146SIGMOD International Conference on Management of Data,pages 1051–1063, 2021.[LNLG17] Seokki Lee, Xing Niu, Bertram Luda¨scher, and Boris Glavic.Integrating approximate summarization with provenance cap-ture. In Proceedings of the 9th USENIX Conference on Theoryand Practice of Provenance, TaPP’17, pages 2–2, 2017.[MCB+20] Zhengjie Miao, Tiangang Chen, lexander Bendeck, Kevin Day,Sudeepa Roy, and Jun Yang. I-rex: an interactive relationalquery explainer for sql. Proceedings of the VLDB Endowment,13(12):2997–3000, 2020.[McD09] John H McDonald. Handbook of biological statistics, volume 2.sparky house publishing Baltimore, MD, 2009.[ME22] Tobias Mu¨ller and Pascal Engel. How, where, and why dataprovenance improves query debugging: A visual demonstrationof fine–grained provenance analysis for sql. In 2022 IEEE 38thInternational Conference on Data Engineering (ICDE), pages3178–3181. IEEE, 2022.[MGMS10] Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore,and Dan Suciu. The complexity of causality and responsibil-ity for query answers and non-answers. PVLDB, 4(1):34–45,October 2010.[MGNS11] Alexandra Meliou, Wolfgang Gatterbauer, Suman Nath, andDan Suciu. Tracing data errors with view-conditioned causality.In SIGMOD, pages 505–516, 2011.[Mil95] George A Miller. Wordnet: a lexical database for english. Com-munications of the ACM, 38(11):39–41, 1995.147[MK08] Chaitanya Mishra and Nick Koudas. Stretch n’ shrink: Resizingqueries to user preferences. Proceedings of the ACM SIGMODInternational Conference on Management of Data, pages 1227–1229, 2008.[MK09] Chaitanya Mishra and Nick Koudas. Interactive query refine-ment. In Proceedings of the 12th International Conference onExtending Database Technology: Advances in Database Tech-nology, pages 862–873. ACM, 2009.[Mun14] Tamara Munzner. Visualization Analysis and Design. CRCPress, 2014.[MV14] F. Mordelet and J. P. Vert. A bagging SVM to learn frompositive and unlabeled examples. Pattern Recognition Letters,37:201–209, Feb 2014.[MZGR19] Zhengjie Miao, Qitian Zeng, Boris Glavic, and Sudeepa Roy.Going beyond provenance: Explaining query answers withpattern-based counterbalances. In SIGMOD, pages 485–502,2019.[MZL+19] Zhengjie Miao, Qitian Zeng, Chenjie Li, Boris Glavic, OliverKennedy, and Sudeepa Roy. Cape: explaining outliers bycounterbalancing. Proceedings of the VLDB Endowment,12(12):1806–1809, 2019.[NWF78] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysisof approximations for maximizing submodular set functions–i.Math. Program., 14(1):265–294, 1978.[PW18] Fotis Psallidas and Eugene Wu. Smoke: Fine-grained lineageat interactive speed. arXiv preprint arXiv:1801.07237, 2018.148[RDA+20] Lukas Rupprecht, James C Davis, Constantine Arnold, YanivGur, and Deepavali Bhagwat. Improving reproducibility of datascience pipelines through transparent provenance capture. Pro-ceedings of the VLDB Endowment, 13(12):3354–3368, 2020.[Rob07] Jonathan C Roberts. State of the art: Coordinated & multi-ple views in exploratory visualization. In IEEE Conference onCoordinated and Multiple Views in Exploratory Visualization,pages 61–71, 2007.[ROS15] Sudeepa Roy, Laurel Orr, and Dan Suciu. Explaining queryanswers with explanation-ready databases. PVLDB, 9:348–359,2015.[RS08] Christopher Re´ and Dan Suciu. Approximate lineage for prob-abilistic databases. Proceedings of the VLDB Endowment,1(1):797–808, 2008.[RS14] Sudeepa Roy and Dan Suciu. A formal approach to findingexplanations for database queries. In SIGMOD, pages 1579–1590, 2014.[Sal91] Gerard Salton. Developments in automatic text retrieval. sci-ence, 253(5023):974–980, 1991.[SAM98] Sunita Sarawagi, Rakesh Agrawal, and Nimrod Megiddo.Discovery-driven exploration of olap data cubes. In Interna-tional Conference on Extending Database Technology, pages168–182. Springer, 1998.[SdOVM18] Vı´tor Silva, Daniel de Oliveira, Patrick Valduriez, and MartaMattoso. Dfanalyzer: runtime dataflow analysis of scientificapplications using provenance. Proceedings of the VLDB En-dowment, 11(12):2082–2085, 2018.149[SDP09] Kostas Stefanidis, Marina Drosou, and Evaggelia Pitoura. Youmay also like results in relational databases. In ymal, 2009.[Sha97] Lloyd S Shapley. A value for n-person games. Classics in gametheory, 69, 1997.[Shn96] Ben Shneiderman. The eyes have it: A task by data type tax-onomy for information visualizations. In IEEE Symposium onVisual Languages, pages 336–343, 1996.[SJMR18] Pierre Senellart, Louis Jachiet, Silviu Maniu, and Yann Ra-musat. Provsql: Provenance and probability management inpostgresql. Proceedings of the VLDB Endowment (PVLDB),11(12):2034–2037, 2018.[SPG05] Yogesh L Simmhan, Beth Plale, and Dennis Gannon. A surveyof data provenance in e-science. SIGMOD Record, 34(3):31–36,2005.[TCP09] Quoc Trung Tran, Chee-Yong Chan, and SrinivasanParthasarathy. Query by output. Proceedings of the 2009ACM SIGMOD International Conference on Management ofdata, page 535, 2009.[TCP14] Quoc Trung Tran, Chee Yong Chan, and SrinivasanParthasarathy. Query reverse engineering. VLDB Journal,23:721–746, 2014.[TPC] TPC-H benchmark specification. http://www.tcp.org/hspec.html. Council, Transaction Processing Performance.[TZES17] Wei Chit Tan, Meihui Zhang, Hazem Elmeleegy, and DiveshSrivastava. Reverse engineering aggregation queries. Proceed-ings of the VLDB Endowment, 10:1394–1405, 2017.150[VdMH08] Laurens Van der Maaten and Geoffrey Hinton. Visualizing datausing t-sne. Journal of machine learning research, 9(11), 2008.[VGBS19] Michael Vollmer, Lukasz Golab, Klemens Bo¨hm, and Di-vesh Srivastava. Informative summarization of numeric data.ACM International Conference Proceeding Series, pages 97–108, 2019.[VRRM16] Manasi Vartak, Venkatesh Raghavan, Elke Rundensteiner, andSamuel Madden. Refinement driven processing of aggregationconstrained queries. Advances in Database Technology - EDBT,2016-March:101–112, 2016.[WDM15] Xiaolan Wang, Xin Luna Dong, and Alexandra Meliou. Datax-ray: A diagnostic tool for data errors. In Proceedings of the2015 ACM SIGMOD International Conference on Managementof Data, pages 1231–1245, 2015.[Wid04] Jennifer Widom. Trio: A system for integrated management ofdata, accuracy, and lineage. Technical report, Stanford InfoLab,2004.[WM13] Eugene Wu and Samuel Madden. Scorpion: Explaining awayoutliers in aggregate queries. PVLDB, 6(8):553–564, 2013.[WZRY18] Yuhao Wen, Xiaodan Zhu, Sudeepa Roy, and Jun Yang. Inter-active summarization and exploration of top aggregate queryanswers. PVLDB, 11(13):2196–2208, September 2018.[ZGSB04] Jun Zhao, Carole Goble, Robert Stevens, and Sean Bech-hofer. Semantically linking and browsing provenance logs fore-science. In ICSNW, pages 158–176, 2004.[ZNDM19] Erkang Zhu, Fatemeh Nargesian, Dong Deng, and Rene´e J.Miller. Josie: Overlap set similarity search for finding joinable151tables in data lakes. In SIGMOD, pages 847–864. Associationfor Computing Machinery, 6 2019.152Appendix AProvenance visualizationA.1 User study materialsThe following are the user tasks and questionnaires given to users in paperform to perform the study.A.1.1 Task QuestionnaireCase 1. Find the company with LEI “213800E546PSA5GCOD18” in Aus-tralia.Where does this piece of data come from originally? From which tabledoes it originate?Have the column names been changed from the origin?Has it been modified from its origin?On a scale of 1 to 5 with 1 being very difficult and 5 being very easy, howeasy was it to find the information on the data origin?1. Very difficult2. Difficult3. Normal1534. Easy5. Very easyWhy did you choose this rating?Case 2. Find the company with LEI “549300S208H6WNCAFD40” in Canada.Where does this piece of data come from originally? From which tabledoes it originate?Have the column names been changed from the origin?Has it been modified from its origin?On a scale of 1 to 5 with 1 being very difficult and 5 being very easy, howeasy was it to find the information on the data origin?1. Very difficult2. Difficult3. Normal4. Easy5. Very easyWhy did you choose this rating?Case 3. Find a company in the United States that originated from the”London Stock Exchange”.What is the LEI of this company?Have the column names been changed from the origin?Has it been modified from its origin?On a scale of 1 to 5 with 1 being very difficult and 5 being very easy, howeasy was it to find the information on the data origin?1. Very difficult1542. Difficult3. Normal4. Easy5. Very easyWhy did you choose this rating?Case 4. Find a company in the Australia that originated from the ”WMDatenservice”.What is the LEI of this company?Have the column names been changed from the origin?Has it been modified from its origin?On a scale of 1 to 5 with 1 being very difficult and 5 being very easy, howeasy was it to find the information on the data origin?1. Very difficult2. Difficult3. Normal4. Easy5. Very easyWhy did you choose this rating?A.1.2 Exit QuestionsIs there any extra information you wish to see in this tool?Do you have any suggestions for improvement of interaction? If so, whatare they?155On a scale from 1 to 5 with 1 being very likely and 5 being very un-likely, how likely are you to use provenance information to determine thereliability/accuracy of a piece of data?1. Very likely2. Likely3. Neutral4. Unlikely5. Very unlikelyWhy did you choose this rating?156Appendix BProvenance summarizationB.1 Alternative Score FunctionsWe present two alternative score functions, accumulative impact score for im-pact summaries and entropy-based score for comparative summaries. Whilethese score functions specify meaningful summaries that are different fromthe summaries in Section 4.3, they are non-submodular functions and do notallow efficiently computing sub-optimal summaries.B.1.1 Accumulative Impact SummariesWe present AImpactt (accumulative impact) as an alternative for Impactt inEquation 4.2 that computes the impact of a tuples covered by a rule as agroup:AImpactt(si, S) = |Qt(R)−Qt(R \MCover(si, S))|. (B.1)Using this impact function, we define a new score function in Equation B.2:157AIScoret(S) =∑si∈SAImpactt(si, S)×Weightt(si), (B.2)The following example applies this new score function and compares itwith the score function used in the impact summaries in Section 4.3.Example 25. Consider the following query on MoviesDirectors that returnstwo answers, w1 = (Female, 312.3 M$) and w2 = (Male, 337.3 M$):Q : SELECT Gender, AVG(Rev) AS AvgRevFROM MoviesDirectors GROUP BY GenderLet assume the user requests an impact summary for w2. Consider sum-maries S = {s1} and S ′ = {s3} with s1 = (Title : ?,Year : ?,Genre :?,Rating : 7,Rev : ?,Director : ?,Gender : Male,Country : ?) and s3 =(Title : ?,Year : ?,Genre : Action,Rating : ?,Rev : ?,Director : ?,Gender :Male,Country : ?), we compute the score functions w.r.t. the score functionsin Equations 4.1 and B.2 as follows:158IScorew2(S) = Impactw2(s1)×Weightw2(s1) =(|337.3− 344.2|+ |337.3− 366.5|+ |337.3− 350.4|+|337.3− 329.1|+ |337.3− 355.9|)× 1 = 76.03.IScorew2(S ′) = Impactw2(s3)×Weightw2(s3) = (|337.3−332.7|+ |337.3− 329.1|+ |337.3− 257.5|)× 1 = 92.7.AIScorew2(S) = AImpactw2(s1)×Weightw2(s1) == |337.3− 444.6| × 1 = 107.2.IScorew2(S ′) = Impactw2(s3)×Weightw2(s3)= |337.3− 218.2| × 1 = 119.18The rule s1 covers t1, t3, t5, t7, t11 and s3 covers t6, t7, t10. In both types ofsummaries, S ′ = {s3} is preferred to S = {s1} because it has a higher score.Proposition 1. The score function AIScore in Equation B.2 is sub-modularif the aggregate function in Q is monotone (e.g. COUNT, MIN, MAX) andit is not sub-modular if the aggregate function is non-monotone (e.g. SUMor AVG). B.1.2 Entropy-based Comparative SummariesWe presented comparative summaries in Section 4.3.4 based on a new scorefunction that measures the balance between the tuples covered by a summa-rization rule from two provenance sets. Now, we suggest an alternative score159function that gives a different measure of the balance between the coveredtuples using binary entropy function:ECScoret,t′(S) =∑si∈SMCountt,t′(si, S)×Weight(si), (B.3)This comparative score function is different from the sore function in Def-inition 2.6 in its marginal count function. Unlike MCount that counts thenumber of remaining records covered by si, MCountt,t′ counts records fromthe provenance of both t and t′. We define MCountt,t′as follows:(MCountt(si, S)+MCountt′(si, S))×Entropyt,t′(si, S). (B.4)Here, MCountt(si, S)+MCountt(si, S) is a marginal count of the tuples in theprovenance of t or t′ that are covered by si (MCountt and MCountt′are de-fined in Definition 2.5). The binary entropy function 0 ≤ Entropyt,t′(si, S) ≤1 measures the balance between the coverage from the provenance of t andt′. It is 0 if either MCountt(si, S) = 0 or MCountt(si, S) = 0 meaning allthe covered provenance records are from one side, and it is 1 if exactly thesame number of records are covered from the provenance of t and t′. Moreprecisely, the binary entropy function is defined as follows:Entropyt,t′(si, S) = H(p(si, S)t) = H(p(si, S)t′). (B.5)in which H(p) = −p × log p − (1 − p) × log(1 − p) is the binary entropyfunction, p(si, S)t is defined as follows,p(si, S)t =MCountt(si, S)MCountt(si, S) + MCountt(si, S),160while p(si, S)t′ is defined analogously. We define MCountt,t′= 0 if MCountt(si, S) =0 and MCountt(si, S) = 0 when si has no marginal coverage from fromRt ∪Rt′ .Example 26. In our running example, considering t = g1, t′ = g4 ands1, ..., s4, the score of {s1, ..., s4} is 0 because each si only covers recordsfrom the provenance of g4. The score of a set of rules {s5} is 6 becauseMCountt,t′(s5, {s5}) = 2×H(0.5) = 2 and Weight(s5) = 3. Proposition 2. The score function ECScore in Equation B.3 is not sub-modular. The proof of this proposition is based on a similar counter example in theproof of Proposition 1.B.2 ProofsProof of Theorem 1. Given a set of rules S that summarize the provenanceof t ∈ Q(R), and a tuple r ∈ R in the provenance of Qt(R), let L(r, S) bethe first rule in S that covers r (the rule that covers r and has the maximumscore). Let ∆t(r) = |Qt(R)−Qt(R \ {r})| be the impact of r on Qt(R). Thescore can be rewritten as the following:IScoret(S) =∑r∈RWeightt(L(r, S))×∆t(r). (B.6)Assuming a set of rules S ′ such that S ( S ′ and a rule s 6∈ S ′, we proveIScoret is submodular by showing the following always holds: IScoret(S ∪{s})− IScoret(S) ≥ IScoret(S ′ ∪{s})− IScoret(S ′). The marginal score for sw.r.t. S and S ′ can be written using Equation B.6. For example for S, themarginal score IScoret(S ∪{s})− IScoret(S) can be written as the following:161∑r∈R[Weightt(L(r, S ∪ {s}))−Weightt(L(r, S))]×∆t(r).Since ∆(r) is a positive value that only depends on r,Qt and R, we canconsider the following cases for every r ∈ R:Case 1. Weightt(L(r, S ′ ∪ {s})) −Weightt(L(r, S ′)) > 0 which means r isin the marginal cover set of s which has the highest weight between therules that cover r and L(r, S ∪ {s}) = s. Since S ( S ′, we can claim thatWeightt(L(r, S ∪ {s})) ≥Weightt(L(r, S)) and L(r, S) = s which meansWeightt(L(r, S ∪ {s}))−Weightt(L(r, S)) ≥Weightt(L(r, S ′ ∪ {s}))−Weightt(L(r, S ′)).Case 2. Weightt(L(r, S ′ ∪ {s}))−Weightt(L(r, S ′)) = 0 andWeightt(L(r, S ∪ {s}))−Weightt(L(r, S)) ≥Weightt(L(r, S ′ ∪ {s}))−Weightt(L(r, S ′))because Weightt(L(r, S ∪{s}))−Weightt(L(r, S)) ≥ 0. This means for everyr ∈ RWeightt(L(r, S ∪ {s}))−Weightt(L(r, S)) ≥Weightt(L(r, S ′ ∪ {s}))−Weightt(L(r, S ′))162which proves the theorem. This proof is based on the proof of [JGP16,Lemma 3]. Proof of Theorem 2. Similar to the proof of Theorem 1, consider S, t1, t2 ∈Q(R), r1 ∈ Rt1 , r2 ∈ Rt2 in the provenance of t1 and t2. Let L(〈r1, r2〉, S)be the first rule in S that covers 〈r1, r2〉 (the rule that covers both r1 and r2and has the maximum score). The CScore function can be rewritten as thefollowing:CScoret1,t2(S) =∑〈r1,r2〉∈Rt1×Rt2Weightt1,t2(L(〈r1, r2〉, S)). (B.7)Assuming a set of rules S ′ such that S ( S ′ and a rule s 6∈ S ′, we proveCScoret1,t2 is submodular by showing the following always holds: CScoret1,t2(S∪{s})−CScoret1,t2(S) ≥ CScoret1,t2(S ′ ∪ {s})−CScoret1,t2(S ′). The marginalscore for s w.r.t. S and S ′ can be written using Equation B.7. For examplefor S, the marginal score CScoret1,t2(S ∪{s})−CScoret1,t2(S) can be writtenas the following:∑〈r1,r2〉∈Rt1×Rt2[Weightt1,t2(L(〈r1, r2〉, S ∪ {s})) −Weightt1,t2(L(〈r1, r2〉, S))].Similar the proof of Theorem 1, we can consider two cases for every 〈r1, r2〉 ∈Rt1 ×Rt2 :Case 1. Weightt1,t2(L(〈r1, r2〉, S ∪ {s})) −Weightt1,t2(L(〈r1, r2〉, S)) > 0which means s covers both r1, r2 and has the highest weight between therules that cover them and L(〈r1, r2〉 , S ∪ {s}) = s. Since S ( S ′, we canclaim that Weightt1,t2(L(〈r1 , r2〉, S ∪ {s})) ≥Weightt1,t2(L(〈r1, r2〉, S)) and163L(〈r1, r2〉, S) = s which meansWeightt1,t2(L(〈r1, r2〉, S ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S)) ≥Weightt1,t2(L(〈r1, r2〉, S ′ ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S ′)).Case 2. Weightt1,t2(L(〈r1, r2〉, S ∪ {s})) −Weightt1,t2(L(〈r1, r2〉 , S)) = 0andWeightt1,t2(L(〈r1, r2〉, S ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S)) ≥Weightt1,t2(L(〈r1, r2〉, S ′ ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S ′)).because Weightt1,t2(L(〈r1, r2〉, S ∪ {s})) − Weightt1,t2(L(〈r1, r2〉, S)) ≥ 0.This means for every 〈r1, r2〉 ∈ Rt1 ×Rt2 ,Weightt1,t2(L(〈r1, r2〉, S ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S)) ≥Weightt1,t2(L(〈r1, r2〉, S ′ ∪ {s}))−Weightt1,t2(L(〈r1, r2〉, S ′))which proves the theorem. Proof of Proposition 1. The proof of sub-modularity for COUNT is givenin [JGP16, Lemma 3] which can be extended to any monotone aggregatefunction. For sets of rules S1 ⊆ S2 that summarize relation R and a new rules 6∈ S1∪S2, the proof is based on the fact that the marginal score w.r.t. everytuple t ∈ R after adding s is greater for S1 compared to S2. For the secondpart of the proposition, we apply the following counter-example that showsthe score function in (4.1) is not sub-modular when the aggregate functionis SUM. Similar counter examples can be generated for any non-submodular164function such as AVG.Let R = {(a, b,−1), (c, b, 1)} be a relation with attributes A1, A2, A3.Consider Q as the following query: SELECT SUM(A3) FROM R. LetS1 = ∅ and S2 = {(a, b, ?)} be sets of summarization rules and s = (?, b, ?) bea summarization rule. We compute the following score values using the scorefunction in (4.1) for the only tuple t in Q(R): IScoret(S1) = 0, IScoret(S2) =2, IScoret(S1∪{s}) = 0, IScoret(S2∪{s}) = 3. Therefore, IScoret(S1∪{s})−IScoret(S1) = 0 and IScoret(S2∪{s})− IScoret(S2) = 1 which shows S1 ⊆ S2does not imply IScoret(S2∪{s})−IScoret(S2) ≤ IScoret(S1∪{s})−IScoret(S1)and proves the claim. B.3 ExtensionsIn this section, we briefly discuss two extensions: one for summarizing dif-ferences and one for handling joins in comparative summaries.In Section 4.3.4, we focused on comparative summaries for capturing thesimilarities between two provenance sets. The differences can also be sum-marised using a new score function similar to the function in Equation 4.4.The change is that the marginal pair count (MPCount) in Equation 4.4 willbe replaced with a function that counts the number of tuples si covers fromRt and penalizes si if it covers tuples from Rt′ . The definition of such a scorefunction is in B.1 where we also prove it is sub-modular. The following exam-ple illustrates the problem of summarizing the differences in the provenanceof two tuples:Example 27. In Table 4.2, consider the provenance of a4, a6 ∈ Q2(MoviesDirectors).A rule s5 = (Title : ?,Year : ?,Genre : Comedy,Rating : 7,Rev : ?,Director :?,Gender : Male,Country : US) provides a comparative summary for the dif-ferences between the provenance of a4 and a6 since the rule summarizes tuplesin the provenance of a6 but it does not cover any tuple from the provenanceof a4. 165In B.1, we presented other score functions for comparative summariesusing the notion of binary entropy function that measure the balance betweenthe coverage of the provenance tuples. However, we show that those scorefunctions do not preserve the sub-modularity property.The comparative summarization problem can be extended for querieswith join operators. For example, if the user selects two tuples e1 and e2, wecan summarize similarities and differences between the provenance tuples inboth Movies and Directors.The main difference with the comparative summaries in Section 4.3.4 isthat the provenance sets for two selected tuples might overlap and this hasto be considered in the score function for such comparative summaries.B.4 User survey materialsThe following is a copy of the user survey questions. The survey itself wasgiven using an online tool.Introduction.The purpose of this questionnaire is to study the user needs for a datasummarization application. The goal is to find out which utility functions theusers value the most as well as the preferred size of a summary of tabular data.Our target demographic are users who have had at least an undergraduatecourse in databases or equivalent external experience.Demographic information.Age group:19-2930-3940-49More than 50Gender.:Male166FemaleOtherPrefer not to sayEducation. Highest level of education completed:High schoolBSc or equivalentMSc or equivalentPhD or equivalentOther:Experience with data. How do you describe your experience working withdata analysis or data management technologies?None at allA littleA moderate amountA lotA great dealTools. What data technologies are you familiar with?SQLRPythonExcelOther:Use. How often do you use data related technologies (data analysis tools,spreadsheets, databases) in your work?AlwaysMost of the timeAbout half the timeSometimesNeverSummarization scenario.167A user accesses a dataset about movies and directors. The user asks thesystem for the total revenue for action movies made in the year 2017. Theuser gets the result back:Action; 2017; 7.3 Billion. Now, given this result we would like to providethe user of a summary of movies made in 2017 that made this 7.3 billionfigure. Here is an example of a summary that is of length 3 . It contains 3rows:Genre Year Country Duration Language coverage impactRow 1 Action 2017 US * English 35% 85%Row 2 Action 2017 * > 120 * 25% 78%Row 3 Action 2015 * < 90 * 39% 21%Table B.1: Summary AThis summary is presented with real values for their respective columnsand * value as do-not-care values filling in for any other value in the column.For example, row 1 is action movies from 2017 made in the US with allpossible duration values in English. Those movies make up 35% of rows inthe original database and have 85% of total revenue.Q1. Can you rank the rows in the summary from most interesting (1) toleast interesting (3)?Row 1Row 2Row 3Can you elaborate on why you picked this order?Q2. Please rank the following statements according to their importancelevel when looking at a summary.The right length (number of rows) in a summary1. Very important2. important1683. Neutral4. important5. Not important at allShowing groups of high grossing movies1. Very important2. important3. Neutral4. important5. Not important at allShowing groups that contain a lot of movies1. Very important2. important3. Neutral4. important5. Not important at allShowing a summary that covers the whole table1. Very important2. important3. Neutral1694. important5. Not important at allHighlighting groups with surprising information1. Very important2. important3. Neutral4. important5. Not important at allQ3. The system will give you a summary overview of the data. Thisoverview will give you an immediate look at the interesting aspects of thedata. How long do you think this summary should be?1-4 rows5-8 rows9-12 rows13-16 rows17 or more rowsOther:Can you please elaborate on why you picked this length?Closing.Q1. How accurate do you feel you were about your answers?Less than I would likeAbout rightQ2. Is there any other information that you would like to share regardingyour needs for a data summarization system?170Appendix CAggregate query refinementC.1 User study materialsC.1.1 TasksThe following are the tasks given to the users:Task 1: Query 1: “SELECT count(*) FROM movie, genre WHERE id= movie id AND revenue > 100000000 AND vote average >= 7 AND genre= ’Action’”Explanation: Select all Action movies that have total revenue > $100m,and have a vote average (rating) >= 7The result is 91 movies. Assuming you want to expand the query toinclude more movies and get a bigger number, how would you go about it?We have a list of suggestions by our system we would like you to see.Look at the suggestions and choose the most relevant tuples based on yourexamination of results and query. Feel free to ask questions and talk throughthe process. When you are finished, you can hit submit.Task 2: Query 2: “SELECT count(*) FROM movie, genre WHERE id= movie id AND revenue > 100000000 AND vote average >= 7 AND genre171= ’Adventure’”Explanation: Select all Adventure movies that have total revenue >$100m, and have a vote average (rating) >= 7The result is 87 movies. Assuming you want to expand the query toinclude more movies and get a bigger number, how would you go about it?We have a list of suggestions by our system we would like you to see.Look at the suggestions and choose the most relevant tuples based on yourexamination of results and query. Feel free to ask questions and talk throughthe process. When you are finished, you can hit submit.Task 3: Query 3: “SELECT count(*) FROM movie m, director dWHERE m.dir id = d.id AND m.revenue > 100000000 AND d.gender =2 AND release date > 2015”Explanation: Select all movies that have total revenue > $100m, that aremade by male directors and released after the year 2015The result is 70 movies. Assuming you want to expand the query toinclude more movies and get a bigger number, how would you go about it?We have a list of suggestions by our system we would like you to see.Look at the suggestions and choose the most relevant tuples based on yourexamination of results and query. Feel free to ask questions and talk throughthe process. When you are finished, you can hit submit.Task 4: Query 4: “SELECT count(*) FROM movie m, director dWHERE m.dir id = d.id AND m.revenue > 1000000 AND d.gender = 1AND release date > 2015”Explanation: Select all movies that have total revenue > $1m, that aremade by female directors and released after the year 2015The result is 20 movies. Assuming you want to expand the query toinclude more movies and get a bigger number, how would you go about it?We have a list of suggestions by our system we would like you to see.172Figure C.1: Demographic questionnaire for the query refinement studyLook at the suggestions and choose the most relevant tuples based on yourexamination of results and query. Feel free to ask questions and talk throughthe process. When you are finished, you can hit submit.C.1.2 Questionnaires and interfacesFigure C.1 shows the demographic questions. Figure C.2 shows the tasksinterface. Figure C.3 shows the exit questions.C.1.3 SuggestionsFigures C.4 and C.5 show the suggestions made within the interface. Ta-bles C.1 and C.2 shows the full list of suggestions for both methods.173Figure C.2: Tasks interface for the query refinement studyFigure C.3: Exit questionnaire for the query refinement study174Figure C.4: Individual movie suggestions (PULearn)Figure C.5: Rules suggestions (ProvSum)175Task ID P Title Language Revenue Genre Release Date Rating Director name Director gender1 79 1.08 Hero zh 177394432 Drama 2002 7.21 89 2.09 Indiana Jones and the Last Crusade en 474171806 Adventure 1989 7.61 120 2.4 The Lord of the Rings: The Fellowship of the Ring en 871368364 Adventure 2001 81 146 1.28 Crouching Tiger Hidden Dragon zh 213525736 Adventure 2000 7.21 679 1.59 Aliens en 183316455 Horror 1986 7.71 1366 0.76 Rocky en 117235147 Drama 1976 7.41 1892 2.41 Return of the Jedi en 572700000 Adventure 1983 7.91 100402 1.59 Captain America: The Winter Soldier en 714766572 Action 2014 7.61 101299 0.61 The Hunger Games: Catching Fire en 847423452 Adventure 2013 7.41 281957 0.83 The Revenant en 532950503 Western 2015 7.31 296098 1.1 Bridge of Spies en 165478348 Thriller 2015 7.22 71 0.6 Billy Elliot en 1.1e+08 Drama 2000 7.42 79 0.5 Hero zh 177394432 Drama 2002 7.22 89 1.2 Indiana Jones and the Last Crusade en 474171806 Adventure 1989 7.62 120 1.26 The Lord of the Rings: The Fellowship of the Ring en 871368364 Adventure 2001 82 671 1.66 Harry Potter and the Philosopher’s Stone en 976475550 Adventure 2001 7.52 1366 0.51 Rocky en 117235147 Drama 1976 7.42 1892 1.48 Return of the Jedi en 572700000 Adventure 1983 7.92 4935 0.64 Howl’s Moving Castle ja 234710455 Fantasy 2004 8.12 49047 1.36 Gravity en 716392705 Science Fiction 2013 7.32 100402 1.24 Captain America: The Winter Soldier en 714766572 Action 2014 7.63 127380 1.08 Finding Dory en 1028570889 Adventure 2016 6.8 Andrew Stanton Male3 285783 1.16 The Walk en 61181942 Adventure 2015 6.9 Robert Zemeckis Male3 324786 1.07 Hacksaw Ridge en 175302354 Drama 2016 7.7 Mel Gibson Male3 315664 1.17 Florence Foster Jenkins en 44272267 Comedy 2016 6.6 Stephen Frears Other/unknown3 210860 1.05 Mortdecai en 30418560 Comedy 2015 5.4 David Koepp Male3 266647 1.17 Pan en 128388320 Adventure 2015 5.9 Joe Wright Male3 388399 1.11 Patriots Day en 44352284 Drama 2016 6.8 Peter Berg Male3 290250 1.08 The Nice Guys en 62788218 Action 2016 7 Shane Black Male3 300168 1.01 Dragon Blade zh 121545703 Action 2015 5.9 Daniel Lee Male3 256961 1.01 Paul Blart: Mall Cop 2 en 107597242 Action 2015 5 Andy Fickman Male3 241554 1.11 Run All Night en 71561644 Action 2015 6.3 Jaume Collet-Serra Male3 309245 1.1 Mistress America en 2500431 Comedy 2015 6.5 Noah Baumbach Male3 274167 1.09 Daddy’s Home en 242786137 Comedy 2015 5.8 Sean Anders Male3 323272 1.13 War Room en 67790117 Drama 2015 6.6 Alex Kendrick Male3 239573 1.16 Unfinished Business en 14431253 Comedy 2015 5 Ken Scott Other/unknown3 301875 1.13 Equals en 2e+06 Drama 2016 5.9 Drake Doremus Male3 166424 1.06 Fantastic Four en 167977596 Action 2015 4.4 Josh Trank Male3 288036 1.17 Sleeping with Other People en 3214116 Comedy 2015 6.1 Leslye Headland Other/unknown3 291870 1.05 Dirty Grandpa en 94073028 Comedy 2016 5.7 Dan Mazer Male4 399019 4.4 The Beguiled en 5535981 Drama 2017 6.4 Sofia Coppola Female4 297762 1.3 Wonder Woman en 770958279 Action 2017 7.1 Patty Jenkins Female4 175541 1.78 Black Nativity en 7018189 Drama 2013 5.8 Kasi Lemmons Female4 245775 1.27 Yves Saint Laurent fr 21026290 Drama 2014 6.4 Jalil Lespert Other/unknown4 109445 4.12 Frozen en 1274219009 Animation 2013 7.4 Chris Buck Other/unknown4 265228 1.27 Timbuktu fr 1076075 Drama 2014 6.9 Abderrahmane Sissako Other/unknown4 230266 1.27 Miss Julie en 5e+06 Drama 2014 6 Liv Ullmann Female4 286565 0.81 Paper Towns en 85512300 Drama 2015 6.1 Jake Schreier Other/unknown4 129139 0.94 The To Do List en 3566225 Comedy 2013 5.6 Maggie Carey Other/unknown4 254470 0.9 Pitch Perfect 2 en 287506194 Comedy 2015 6.8 Elizabeth Banks Female4 347026 1.27 A United Kingdom en 9607779 Drama 2016 6.5 Amma Asante Female4 384483 1.01 El Cuchillo es 85446075 Thriller 2016 0 Estela Gondrod Other/unknownTable C.1: PULearn suggestions for each task176Task Language Genre Year Country Company Rating Gender Runtime Revenue Count1 * Action * * * >= 7 * * >=90m 1001 * Action & Western * * * >=7 * * >100m 991 * Action & Horror * * * >=7 * * >100m 1021 * Action & War * * * >=7 * * >100m 1141 * Action & Adventure * * * >=7 * * >100m 1811 * Action * * * >=6 * * >100m 3232 * Adventure * * * >=7 * * >90m 982 * Adventure & Western * * * >=7 * * >100m 1002 * Adventure & Horror * * * >=7 * * >100m 1032 * Adventure & War * * * >=7 * * >100m 1152 * Adventure & Action * * * >=7 * * >100m 1812 * Adventure * * * >=6 * * >100m 2893 * * >2015 * * * Male & Other/Unknown * >100m 963 * * >2015 * * * Male & Female * >50m 943 * * >2015 * * * Male & Female * >100m 823 * * >=2015 * * * Male * >100m 1253 * * >=2014 * * * Male * >100m 1793 * * >=2013 * * * Male * >100m 3214 * * >=2015 * * * Female * >500k 304 * * >=2015 * * * Female * >1m 274 * * >=2014 * * * Female * >1m 414 * * >=2014 * * * Female * >500k 444 * * >2015 * * * Female & Other/Unknown * >1m 1044 * * >2015 * * * Female & Other/Unknown * >500k 205Table C.2: ProvSum suggestions for each task177
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Pottinger, Rachel
Provenance in relational databases : usability and applications
Text