Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Huang, Jingxuan
Master of Science - MSc
University of British Columbia
Data provenance contains valuable information about the data involved in a query and the process it underwent to produce the output. Despite extensive research on different data provenance models and their characteristics, its potential in query debugging has not been fully exploited. Observing students’ struggle in writing aggregate queries, we adapted a provenance summarization technique for pedagogical purposes and introduced a novel feedback approach to assist students in query debugging. Our user study confirmed the effectiveness and helpfulness of this technique.
Empowering Student QueryDebugging: Feedback for AggregateQueries via ProvenanceSummarizationbyJingxuan HuangB.Sc., Nanjing University, 2022A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)June 2024© Jingxuan Huang 2024The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Empowering Student Query Debugging: Feedback for Aggregate Queriesvia Provenance Summarizationsubmitted by Jingxuan Huang in partial fulfillment of the requirements forthe degree of Master of Sciencein Computer ScienceExamining Committee:Rachel Pottinger, Professor, Computer Science, UBCSupervisorEd Knorr, Associate Professor Emeritus of Teaching, Computer Science, UBCSupervisory Committee MemberiiAbstractData provenance contains valuable information about the data involved ina query and the process it underwent to produce the output. Despite exten-sive research on different data provenance models and their characteristics,its potential in query debugging has not been fully exploited. Observingstudents’ struggle in writing aggregate queries, we adapted a provenancesummarization technique for pedagogical purposes and introduced a novelfeedback approach to assist students in query debugging. Our user studyconfirmed the effectiveness and helpfulness of this technique.iiiLay SummaryAs data volumes grow, the ability to query relational databases becomes es-sential for students regardless of their discipline or chosen profession. How-ever, it can be challenging to master query writing skills, and students oftenstruggle to identify errors in their queries and make necessary revisions.To address this issue, we propose a novel feedback mechanism designedto help students debug their queries. This feedback leverages data prove-nance, which refers to the information contributing to a query’s results,and presents a summarized, intuitive visualization to aid students’ under-standing. Our user study conducted among UBC students confirms theeffectiveness and helpfulness of this feedback approach.ivPrefaceThis thesis is an original and unpublished work by Jingxuan Huang, con-ducted under the supervision of Prof. Rachel Pottinger. The solution pro-posed in this study was built upon the code left by Omar AlOmeir, a PhDstudent who graduated under my supervisor’s guidance. Omar also providedvaluable comments and suggestions for the proposed technique.My contributions to this work include:• Conducting an extensive review of relevant literature,• Analyzing submissions from CPSC 304 final exams,• Developing the solution,• Designing and conducting the user study as well as analyzing its re-sults, and• Composing the manuscript.The user study conducted for this research was classified as minimalrisk by the Behavioural Research Ethics Board at the University of BritishColumbia (UBC BREB number: H24-00305).vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1 Inspiring example . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Analysis of student performance on aggregate queries in ex-ams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.1 Students’ struggle with SQL . . . . . . . . . . . . . . . . . . 73.2 SQL educational systems . . . . . . . . . . . . . . . . . . . . 83.3 Query explanation and query refinement . . . . . . . . . . . 93.4 Data provenance for query debugging . . . . . . . . . . . . . 104 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2 Extending the comparative summary to capture differences . 144.3 Supporting numerical attributes . . . . . . . . . . . . . . . . 154.4 Visual feedback . . . . . . . . . . . . . . . . . . . . . . . . . 17viTable of Contents5 User study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195.1 Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195.1.1 Participants . . . . . . . . . . . . . . . . . . . . . . . 195.1.2 Baseline . . . . . . . . . . . . . . . . . . . . . . . . . 205.1.3 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . 205.1.4 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.1.5 Design . . . . . . . . . . . . . . . . . . . . . . . . . . 235.1.6 Procedures . . . . . . . . . . . . . . . . . . . . . . . . 235.2 Results and discussion . . . . . . . . . . . . . . . . . . . . . . 255.2.1 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . 265.2.3 Helpfulness and likelihood of use in the future . . . . 285.2.4 Comments and suggestions . . . . . . . . . . . . . . . 285.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 306 Conclusion and future work . . . . . . . . . . . . . . . . . . . 31Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33AppendicesA Feedback in the user study . . . . . . . . . . . . . . . . . . . . 37A.1 Baseline feedback . . . . . . . . . . . . . . . . . . . . . . . . 37A.2 Summary rule feedback . . . . . . . . . . . . . . . . . . . . . 37B Questionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40B.1 Pre-study questionnaire . . . . . . . . . . . . . . . . . . . . . 40B.2 Post-study questionnaire . . . . . . . . . . . . . . . . . . . . 41C Results from pre-study questionnaire . . . . . . . . . . . . . 43viiList of Tables4.1 Sample movies table. . . . . . . . . . . . . . . . . . . . . . . . 125.1 Summarization of correctness. . . . . . . . . . . . . . . . . . . 27viiiList of Figures2.1 Error categories and frequency of student mistakes in threequestions about aggregate queries asked in UBC CPSC 304final exams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54.1 The Venn diagram for illustrating the differences between thetwo interpretations. . . . . . . . . . . . . . . . . . . . . . . . . 144.2 The demo query. . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Visualization of summary rules as feedback. . . . . . . . . . . 184.4 Visual feedback after clicking on the “Fantasy” tab. . . . . . 185.1 Task 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 Task 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.3 Task 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.4 Boxplots of time used for each task in different treatments. . 265.5 The diverging stacked bar chart of user-perceived helpfulnessof feedback and likelihood of using it in the future. . . . . . . 29A.1 Baseline feedback for each task. . . . . . . . . . . . . . . . . . 37A.2 Summary rule feedback for Task 1 (Figure 5.1). . . . . . . . . 38A.3 Summary rule feedback for Task 2 (Figure 5.2). . . . . . . . . 38A.4 Summary rule feedback for Task 3 (Figure 5.3). . . . . . . . . 39A.5 Summary rule feedback for the demo task (Figure 4.2). . . . . 39C.1 Participants’ self-assessed experience with relational databasesand SQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43C.2 Participants’ self-assessed difficulty with debugging SQL. . . 44C.3 Participants’ self-assessed familiarity with debugging SQL. . . 44ixAcknowledgementsI give my sincere gratitude to my supervisor, Prof. Rachel Pottinger, whocame up with the wonderful idea for this study and steered me on the rightpath throughout my thesis journey. I also owe my gratitude to the commit-tee members for their meticulous review and invaluable feedback. Specialthanks go to my lab mates and fellow students, who inspired me to opti-mize the solution and helped me get in touch with prospective participants.Finally, my heartfelt gratitude goes to my parents, who have supported methroughout my years of education both financially and emotionally.xChapter 1IntroductionWith the growing volume of data with potential value, the ability to writeand read SQL queries becomes increasingly critical to uncover the valuesin the data. While computer science students are typically introduced todatabases and SQL during their undergrad studies, many still encountergreat difficulties when it comes to authoring and troubleshooting SQL queries.To compound the problem, even after addressing syntax errors, queries maystill fail to produce desired outcomes. Unlike other programming languagesthat undergraduates usually get exposed to, SQL’s declarative nature com-plicates the debugging process. Consequently, students often resort to ex-amining the original database to pinpoint issues. However, this strategy hasserious drawbacks for aggregate queries, as they often involve substantialnumbers of tuples, sometimes even entire tables. For instance, consider theaggregate function COUNT, which produces just one real number as its out-put, but may involve the entire database during its computation. Therefore,manually inspecting individual tuples becomes impractical and inefficient foridentifying problems in aggregate queries.To tackle this challenge, data provenance [9] can offer valuable insights toassist students in debugging aggregate queries. Informally, data provenanceis a mechanism that allows users to understand what data contributes to aquery result and the process it goes through to shape that final outcome.For example, suppose we wanted to compute the average salary of all femaleemployees in the Sales department. Here, the data provenance includes a listof rows in the underlying table(s) that meet the qualification of the WHEREclause, and thus making up the average salary.While prior research has extensively studied provenance’s models andtheir characteristics [12], visualization [8, 33, 34], and applications acrossvarious domains [14, 26, 26], its application in SQL query debugging remainsrelatively unexplored. This presents a promising avenue, as data provenancecan serve as intermediate results at each stage of query execution, providingusers with additional information to pinpoint issues in their queries. Inour study, we aim to investigate the possibility of data provenance to aidstudents in debugging aggregate queries.1Chapter 1. IntroductionWe face two major challenges in achieving our goal. Firstly, the volumeof provenance information in aggregate queries tends to be too overwhelmingto provide useful insights when viewed directly. Secondly, since provenanceis not a familiar concept for most students, they may have trouble under-standing its meaning, let alone using it for debugging purposes. Our studyaddresses these challenges by proposing a new visual feedback display con-sisting of a summary of data provenance. Specifically, we extend an existingprovenance summarization technique [6] to extract useful information fordebugging from data provenance, significantly reducing the amounts of in-formation users need to review. Furthermore, we design an intuitive visualfeedback interface that does not require users to be familiar with the conceptof provenance in order to understand the feedback.This thesis has several contributions:• We analyze students’ responses to aggregate queries asked in previousfinal exams to confirm the necessity for assistance in query debuggingand to identify common issues encountered by students.• We enhance a summarization technique for data provenance to cap-ture the differences between two queries and accommodate numericalattributes in the summarization process.• We introduce a visual feedback display for the summarization of prove-nance to enhance its understandability and utility in query debugging.• We validate the effectiveness and usefulness of the proposed techniquethrough a user study.2Chapter 2MotivationIn this chapter, we discuss the example that serves as the motivation forthis work and the analysis of student performance that confirm the need fornew methods to assist students in debugging aggregate queries.2.1 Inspiring exampleOur work is motivated by a mistake that students made in a final exam forUBC CPSC 3041. Example 1 shows the details of the question.Example 1. Write a SQL query to find the name and total enrollments ofall courses that have at least one student who is under 19. Your list shouldbe in reverse alphabetical order by the name of the course. Below is theschema of the database.Student(snum: integer, sname: string, major: string, level: string, age:integer)Class(name: string, meets at: string, room: string, fid: integer)Enrolled(snum: integer, cname: string)Faculty(fid: integer, fname: string, deptid: string)Listing 2.1 is the correct answer to the question. However, some studentscame up with Listing 2.2, which is a legitimate query in its own right, but isnot equivalent to the correct query. Specifically, it only counts the numberof enrolled students under the age of 19, rather than counting all studentsfor the qualified courses. Nevertheless, beginners often struggle to discernthe nuanced differences between the proposed query and the intended one.□1“CPSC 304: Introduction to Relational Databases” is an undergraduate-level intro-ductory course on databases offered by UBC.32.2. Analysis of student performance on aggregate queries in examsSELECT cname, count(∗)FROM enrolledWHERE cname in(SELECT cnameFROM student s, enrolled eWHERE s.snum = e.snumAND s.age < 19)GROUP BY cnameORDER BY cname DESC;Listing 2.1: Correct query.SELECT cname, count(∗)FROM (SELECT cnameFROM student s, enrolled eWHERE s.snum = e.snumAND s.age < 19)GROUP BY cnameORDER BY cname DESC;Listing 2.2: Incorrect query.Inspired by the example, we identified two factors that complicate thedebugging process for incorrect queries like the one above. Firstly, whilethe query may be free of syntactical bugs, it can still yield incorrect resultsdue to what are known as “semantic errors” [3]. Semantic errors are par-ticularly difficult to debug because of the lack of meaningful feedback fromthe console, and the issue is compounded by the absence of out-of-the-boxdebuggers for SQL. Secondly, debugging SQL queries becomes even morechallenging when working on large databases. The sheer volume of tuplesinvolved in a query can make it exceedingly difficult to verify the correctnessof the answer, and pinpoint the root causes of an incorrect answer. There-fore, our goal is to improve the user experience in debugging queries withinlarge databases by providing meaningful feedback. Specifically, we will focuson debugging aggregate queries in this study to narrow down the scope ofthe problem. Aggregate queries typically involve more tuples, making themmore challenging to trace and uncover underlying issues.2.2 Analysis of student performance onaggregate queries in examsWe analyze student performance on questions related to aggregate queriesin UBC CPSC 304 final exams to identify common errors. Specifically, wewill examine three questions, one from 2023 and two from 2021. For eachquestion, we collected the anonymized scoring results, which includes thestudents’ scores on each rubric item.Since rubrics vary in each exam, we classify them into seven categoriesand calculate the frequency of student mistakes within each category. We42.2. Analysis of student performance on aggregate queries in examsFigure 2.1: Error categories and frequency of student mistakes in threequestions about aggregate queries asked in UBC CPSC 304 final exams.disregarded rubric items such as completely correct or completely blank.Each incorrect answer may contain errors in multiple categories. Figure 2.1shows these categories and their frequency. Both syntax and semantic errorscould occur within each category. While we will discuss those errors in detail,it is worth noting that we may overlook many ways in which students makemistakes, as we lacked access to students’ raw submissions.The ORDER BY clause exhibits the highest error rate at 22.4%. Stu-dents err in various ways within this clause, such as mistyping keywords(e.g., using ‘SORT BY’), overlooking reverse order specifications, or omit-ting the ORDER BY clause altogether. Nonetheless, these mistakes are typi-cally straightforward to identify and rectify given the query outputs. Errorsin the WHERE clause also show up frequently, comprising 20.8% of all errors.Common errors include joining incorrect or redundant tables or using wrongconditions. The errors in the GROUP BY clause, which account for 17.8% ofthe total faults, often have a straightforward reason: students may chooseincorrect attributes for grouping, resulting in either syntactic errors if at-52.2. Analysis of student performance on aggregate queries in examstributes not included in the GROUP BY clause are selected, or semantic errorswhere aggregate functions are applied to incorrect groups. Errors in theHAVING clause, totaling 13.7%, often stem from the mistakes in conditionsor misuse with the WHERE clause. Errors in the SELECT clause, represent-ing 12.2% of all errors, frequently occur due to a failure to select requiredattributes, omission of DISTINCT, or selection of unaggregated attributes.Aggregate function errors, while fewer at 6.32%, often arise from aggregat-ing over the wrong attribute or from incorrect table references. The latterissue is especially common in problems requiring self-joins. In addition tothe aforementioned categories, there are miscellaneous errors involving mul-tiple clauses that thus cannot be classified into any of the previously men-tioned categories. Examples of such errors are incorrect query structures,unnecessary duplication, or misinterpretations of questions, which alwayslead to semantic errors. Those errors constitute 6.8% of all observed errorsin student submissions.In conclusion, students can make mistakes in diverse ways, producingsyntactic errors, semantic errors, or both. Among them, mistakes were fre-quently spotted in the WHERE clause, as well as in others specific to aggregatequeries, such as GROUP BY and HAVING. The analysis confirms that studentsstruggle with aggregate queries and it reveals various types of incorrectqueries that our feedback is expected to handle.6Chapter 3Related workIn this section, we summarize the central ideas and key findings of literaturerelevant to our study. The connection and distinctions between previousworks and our study are also scrutinized.3.1 Students’ struggle with SQLSQL is hard to learn in part due to its declarative nature, which sepa-rates it from the imperative languages that students are more familiar with,such as C and Java [20]. Specifically, declarative languages require users tospecify desired outcomes, but they do not need to know the procedures oralgorithms used to derive those results. Despite adding flexibility to queryoptimization, users can be confused when they fail to get the anticipatedresults. Extensive works have investigated how students struggle with SQLand revealed some common problems. Alkhabaz et al. [4] tested students ondifferent operations across relational, document, and graph databases. Theyfound that students have trouble writing queries with aggregation and joinoperations regardless of the data models used in the databases. Migler andDekhtyar [20] measured students’ difficulty using newly introduced metricsand discovered that students generally have trouble understanding conceptssuch as self-joins and nested queries. Ahadi et al. [3] classified the errorsstudents make when writing SQL statements as syntactic2 and semantic3errors.In this thesis, we focus only on helping students with aggregation, ratherthan helping with all possible SQL queries. As cited above, aggregation isone of the concepts that students struggle the most with, yet few studies at-tempted to address the difficulty. Moreover, we only resolve semantic errors,as syntactic errors are readily identifiable through error messages and rel-atively straightforward to address, whereas semantic errors are challengingto rectify due to the absence of meaningful feedback.2A syntactic error will cause the query to terminate and provide an error message.3A semantic error will execute but does not return the expected answer.73.2. SQL educational systems3.2 SQL educational systemsLearning SQL can be challenging for beginners, and teaching SQL is also adaunting task for teachers. To support students and instructors, numerousSQL educational systems have been developed, each addressing differentsub-problems and using various techniques. Weston et al. [29] proposedEchelon, a system designed for instructors to rapidly assess students perfor-mance in a large-scale database course. It encodes the students’ submittedqueries using neural networks and presents the clustered results in a dash-board. Yang et al. [31] attempted to solve a similar problem, but theyencoded the student submissions with global sequence alignment scores andvisualized them with hierarchical clustering. They enhanced the visualiza-tion with a more compact textual representation later [32].In addition to the systems designed for the instructors, student-orientedsystems can enhance students’ understanding of SQL and serve as a com-plementary resource with other course materials. Hardt and Gutzmer [13]developed a visualization technique to show the impact of clauses and con-ditions on SELECT statements, which can help students understand SQLqueries. Sadiq et al. [25] proposed SQLator, a workbench containing greatamounts of SQL practice problems and an evaluation function to assessthe correctness of students’ answers. Kleerekoper and Schofield [15] devel-oped a new system where students can learn from practice tests, bridg-ing the gap between automated assessment tools and teaching platforms.However, those systems were unable to provide personalized recommenda-tion. SQL-Tutor [22] addressed this problem by incorporating the “StudentModel” in the system architecture, where a student’ previous submissionswere recorded to recommend the most helpful problems to the student inthe future. The system also provides feedback for semantic errors by check-ing if the student’s query violates predefined constraints. However, compil-ing constraints requires human labor and is time-consuming. In contrast,RATest [18] can automatically generate the smallest counterexample to anincorrect relational algebra query as feedback. I-Rex [19], a system builtupon RATest, further allows students to trace the intermediate results ofSQL queries over the smallest counterexample, similar to a debugger forimperative languages. However, the counterexamples generated in both sys-tems are based on specific database instances. To improve generalizability,CinsGen [17] utilizes “c-instances” to represent generalized minimal coun-terexamples. It also supports comparing two queries and summarizing thedistinctions in the form of counterexamples, giving students a chance tolearn the differences between their submission and the reference answer. Al-83.3. Query explanation and query refinementthough the problem CinsGen was trying to solve bears similarities to ours,the solution cannot be directly applied to our problem due to its lack ofsupport for aggregate queries.3.3 Query explanation and query refinementQuery explanation is a broad term that refers to a series of techniques thatcan enhance users’ understanding of queries. If we can help students under-stand incorrect queries, they are more likely to identify the problems andfix the bugs. Scorpion [30] is a system that can find explanations for theuser-defined outliers in a query output using the attributes in the dataset.To find the optimal explanation, the researchers defined the “influence” ofquery predicates on the query output. While Scorpion supports aggregationand the GROUP BY clause, it can only explain the differences between twotuples in the result of the same aggregate query and is not capable of com-paring the results of two different queries. Roy and Suciu [24] introduced theconcept of “intervention” for explaining SQL queries. They considered thetuples that will significantly affect the query output upon removal as a greatexplanation for the query. However, this technique is limited to explainingindividual queries and does not support query comparison. Abuzaid et al. [2]introduced the DIFF operator, which can extract combinations of attributesas explanations for why two queries differ. It also offers a unified interface tovarious “difference metrics”, encompassing those proposed in [30] and [24],and allows for customization to meet users’ specific requirements. However,DIFF cannot handle aggregate queries, and numerical attributes cannot beused in the explanation.Query refinement is an optimization problem that involves modifyingthe selection predicates in the user-authored aggregate query to approximatethe target output, or “cardinality constraints” in the literature. AlOmeir[5] encapsulated aggregate queries using “summary rules”, which highlightsthe selection predicates of the queries. The system generates rules for thedatabase offline and recommends the top-k rules that best match the user-authored query. Vartak et al. [27] proposed ACQUIRE, a technique thatcan fulfill cardinality constraints with minimal changes to the original query.Contrary to AlOmeir’s approach, ACQUIRE creates the search space andfinds the best answer from there on the fly. The Stretch ‘n’ Shrink (SNS)framework proposed by Mishra and Koudas [21] employs a similar approachto ACQUIRE, but keeps its user-in-the-loop due to the recognition thatthe optimal answer may vary under different circumstances, and thus the93.4. Data provenance for query debuggingsystem must keep aware of user preferences. The query refinement problemis relevant to us in that the semantic errors students make will lead to theviolation of the cardinality constraints, and our system aims at generatingfeedback to help the students change the query to meet the cardinalityconstraint. Despite the similarity, our task is different from query refinementbecause we know the correct answer for the practice problems, whereasin query refinement the system needs to guess the ideal query that theusers have in mind. Therefore, the great emphasis placed on generating andranking candidates is irrelevant and can be shifted to more important topicsin the pedagogical context such as student engagement.3.4 Data provenance for query debuggingGiven a query result, data provenance refers to the source of data and theprocess it went through to produce this result. Data provenance providesa way to trace back in declarative query languages like SQL. There aredifferent types of data provenance, such as data lineage, why-provenance,where-provenance, and how-provenance [9]. Gathani et al. [11] provided anoverview of recent advancements in debugging database queries, and theyclassified the strategies used in query debugging systems into three cate-gories: modelling the logical structure of a query, modelling the executionoutput of a query, and hybrid approaches combining both strategies. Dataprovenance is the keystone for systems in the second category, where it of-fers collectable and illustrative intermediate results essential for debuggingSQL queries. Their interviews with database users also revealed a demandfor understandable exceptions and debuggers for SQL, needs that can beaddressed using provenance. Nevertheless, only a few studies have applieddata provenance to query debugging, despite the extensive research on thetechnology itself. RATest [18] derived a satisfiability modulo theories (SMT)problem based on queries’ how-provenance to find the smallest counterexam-ple that is used for helping students debug their queries. Mu¨ller and Engel[23] designed a visualizer to illustrate how, where, and why data provenancefor query debugging. Although it supports aggregate queries, the visual rep-resentation is not scalable for debugging in large databases. Chapman andJagadish [7] introduced the notion of “Why-Not” provenance, which aimsat explaining why a particular entry does not show up in the query result.Lee et al. [16] further addressed the scalability issues of why-not provenancein their system PUG, where they employed sampling-based techniques toextract key insights from the provenance. However, PUG was designed for103.4. Data provenance for query debuggingDatalog and was not optimized for aggregate queries, which typically involvemuch larger amounts of provenance compared to normal queries. AlOmeiret al. [6] reduced the scale of provenance information in aggregate queriesthrough summary rules, thereby enhancing usability of provenance in largedatabases. Nevertheless, the system is unable to summarize the differencesin provenance between two queries, making it not directly applicable todebugging.11Chapter 4SolutionIn this chapter, we introduce the provenance summarization technique uponwhich we built, and we explain and justify our adaptations to it. Addition-ally, we describe the visual representation for summary rules as feedbackfor aggregating queries that we developed, which enhances student querydebugging.4.1 PreliminariesWe introduce several fundamental concepts to provide readers with the nec-essary context for understanding our solution. Specifically, throughout thisthesis we refer to the data provenance as its lineage: the exact set of sourcetuples that produce a result item [10]. For example, consider the followingquery:Q1: SELECT genres, COUNT(∗) FROM moviesWHERE vote average > 6 GROUP BY genresWhen running the query on the movies table (Table 4.1), the provenance of(‘Drama’, 3) in the query result is {t1, t3, t4}.ID Title Revenue Release date Vote average Genrest1 The Hustler 7600000 1961 7 Dramat2 Escape from New York 50244700 1981 6 Sciencet3 The Remains of the Day 23237911 1993 7 Dramat4 Frida 56298474 2002 7 Dramat5 Miss Congeniality 212000000 2000 6 ComedyTable 4.1: Sample movies table.Although Q1 has a simple provenance, the provenance of aggregatequeries usually involve significantly more tuples than the size of its out-124.1. Preliminariesput, making it hard for users to explore and utilize. To address the is-sue, AlOmeir [5] adopted summary rules to concisely represent the prove-nance of aggregate queries. For example, consider a summary rule s1 =(∗, ∗, ∗, ∗, Drama), which matches all drama movies and covers all tuples inthe provenance of Q1. Provenance can be summarized by multiple summaryrules, and we call such a list of rules S = (s1, s2, · · · ) as a summarization.There are numerous potential summarizations for the same query. For ex-ample, S2 = {s2} where s2 = (∗, ∗, ∗, 7, Drama) is an alternative summa-rization for Q1. It will match all drama movies with a vote average equalto 7, thereby including all tuples in the provenance of Q1. However, notall summarizations are equally desirable. For instance, compared to S2,S1 = {s1} contains fewer characteristics about the provenance. Therefore,we need to define a score for measuring the quality of a summarization anddevelop a specialized algorithm to find the optimal solution.The comparative summary problem was proposed in [6, Definition 4.4],aiming at finding the best summarization that can capture the similaritiesbetween two sets of provenance Ra and Ra′. To that end, [6] defined CScore(Equation 4.1) as the objective function. In this equation, MPCount rep-resents the number of shared tuples between Ra and Ra′covered by si butnot covered by any rule sj in a summarization S = (s1, s2, · · · ) where j < i.Weight represents how well a rule summarizes a provenance table and canbe any monotonic function that yields a non-negative real number. We willcontinue to use the one defined in [6], which computes the number of non-∗values in a rule. Intuitively, CScore favors a summarization that consists ofrules covering as many shared tuples as possible while still being selective.CScorea,a′(S) =∑si∈SMPCounta,a′(si, S)×Weighta,a′ (si) (4.1)While finding the optimal solution for CScore is NP-hard, its submod-ularity allows greedy algorithms to produce a satisfactory result efficiently.In [6], the Comparative Provenance Summarization algorithm (CPS) wasintroduced as a greedy approach to address this problem within reasonableamounts of time.134.2. Extending the comparative summary to capture differences4.2 Extending the comparative summary tocapture differencesIn our study, we want to compare the provenance of the correct query withthat of the incorrect query, aiming to provide users with valuable insightsinto query errors. Therefore, we need to redefine the goal of the compar-ative summary problem proposed in [6] to focus on differences instead ofsimilarities between two sets of provenance. This primarily requires adjust-ing MPCount in Equation 4.1.In fact, in [5, Appendix B.3], the author briefly discussed an approach tothis issue, where MPCount in Equation 4.1 is replaced with a function thatrewards a rule when it covers tuples from Ra and penalizes it when coveringtuples from Ra′. However, there are two possible interpretations of this idea.The first interpretation is to reward a rule when it covers tuples unique toRa and penalize it when it covers tuples shared by both Ra and Ra′. Thesecond interpretation is to reward a rule when it covers any tuples in Rabut penalize it when it covers any tuples in Ra′. Figure 4.1 illustrates thedifferences between these two interpretations using a Venn diagram. Despitesubtle differences, we chose the first approach because it better aligns withour objective of facilitating query debugging. It emphasizes the uniquetuples in one query by penalizing the shared ones, helping users discernwhat should have been included or excluded from their answer.Figure 4.1: The Venn diagram for illustrating the differences between thetwo interpretations.To formalize, we introduce MUCount4 to replace MPCount :MUCounta,a′(si, S) = max0, ∑ti∈MCover(si,S)Ia,a′(ti, si) (4.2)Where I stands for an indicator function:4“U” stands for “uniqueness”.144.3. Supporting numerical attributesIa,a′(t, s) =1, if t ∈ Ra −Ra′−1, if t ∈ Ra ∩Ra′0, otherwise(4.3)Here, MUCount counts unique tuples in Ra and subtracts the numberof shared tuples from it, with negative values forced to zero.Replacing MPCount with MUCount in Equation 4.1 will lead to a newscore function that can highlight the differences between two sets of prove-nance:UScorea,a′(S) =∑si∈SMUCounta,a′(si, S)×Weighta,a′ (si) (4.4)It’s worth noting that UScorea,a′differs from UScorea′,a since set differ-ence is asymmetrical. This property is desirable as we aim to distinguishunique tuples in the correct answer, and vice versa. UScore is sub-modular,and its proof will be similar to that of CScore in [5, Theorem 2]. Therefore,it is possible to use the CPS algorithm to approximate the optimal solution.Example 2. Consider this query:Q2: SELECT genres, COUNT(∗) FROM moviesWHERE release date >= 2000 GROUP BY genresSuppose that a student wrote Q2 as the answer to Q1’s question. Nowwe will compare the provenance of a1=(‘Drama’, 3) from Q1 and the prove-nance of a2=(‘Drama’, 1) from Q2. The provenance of a1 is {t1, t3, t4} fromTable 4.1, and the provenance of a2 is {t4}. Consider one comparative sum-marization S3 = {s1}, where s1 is the summary rule (∗, ∗, ∗, ∗, Drama).Then MUCounta1,a2 = 1, and MUCounta2,a1 = 0. Therefore, UScorea1,a2 =1× 1 = 1, and UScorea2,a1 = 0× 1 = 0. □4.3 Supporting numerical attributesNumerical attributes play a significant role in aggregate queries, since manycommon aggregate functions like AVG and SUM can only apply to numericalattributes. Hence, it is essential to integrate numerical attributes when gen-erating provenance summarization for aggregate queries. In [5, Chapter 5],154.3. Supporting numerical attributesthe author introduced an approach to include numerical attributes into thesummary rules by discretizing continuous variables with cumulative aggre-gated results. However, this method is very expensive and is suitable onlyfor off-line techniques. Moreover, in the context of query debugging, thereis no need to know the cumulative aggregated results as the correct answeris already known.To incorporate numerical attributes in the summary rules, we will con-tinue to use discretization techniques for binning continuous domains. Thisarea has been extensively researched with numerous methods proposed inprevious studies. For instance, Vollmer et al. [28] pursued a similar goalto us where they aimed to summarize a table with numerical explanatoryattributes. To solve the problem, they developed an algorithm to identifysemantic ranges, such as evening hour (“15-23”) for the “Hour” attribute, tooffer interpretable and informative summarization. However, in our study,we will start from the simple equal binning approaches. This is becausesophisticated techniques typically introduce a significant overhead, which isnot warranted as discretization is only a small component of our solution.Furthermore, the goal of discretization varies across different use cases. Evenif a method produces satisfactory results for explaining a table, it may notbe as helpful for revealing errors in a query. For our specific goal, the idealbinning method should: (1) generate concise and easily interpretable results,and (2) offer insights that can facilitate query debugging.One of the most commonly-used binning methods is the equal-width bin-ning, where values are segmented into intervals of equal size. However, thisapproach performs poorly on skewed data. Therefore, we opted for equal-depth binning. It creates buckets with approximately the same number ofdata points, effectively distinguishing values that cluster within a narrowrange. Nevertheless, presenting intervals with numerical endpoints can bechallenging for users who are unfamiliar with the dataset. For example, it ishard to know if a value is large or small compared to others in the dataset.To tackle this problem, we adopted quantile-binning to discretize numericalattributes with equal depth while representing the intervals with relativenumbers. We computed quintiles (i.e., 20%, 40%, etc.) for numerical at-tributes and replaced the original values with their corresponding quantilebins. It is possible to use other quantifications, but we found that 5-quantilesalone can produce informative and interpretable results for query debugging.164.4. Visual feedback4.4 Visual feedbackTo assist students in applying summary rules to debug aggregate queries,we developed a visual representation based on an example in [6] to serveas feedback. Figure 4.3 is an example of this visualization for the queryin Figure 4.2. It has three components: Coverage, Summary rules, andGroups. Each rule has two coverage percentages, one for the incorrect query(labeled “Coverage (Yours)”) and another for the correct query (labeled“Coverage (Answer)”), indicating the percentage of tuples covered by therule within a provenance table. The embedded bar charts in the columnshelp to improve readability. We derived rules from both UScorea,a′andUScorea′,a and combined them to form the final list of rules displayed in theSummary rules.Groups, presented as tabs at the top, were designed to support querieswith a GROUP BY clause. Aggregate queries with GROUP BY usually pro-duce results with multiple entries A = {a1, a2, · · · }. However, UScoreai,ajcan only compare two entries, making it not directly applicable to com-paring two aggregate queries with a GROUP BY clause. To address this,we used tabs to separate groups and compare pairs of entries from thesame group across two queries. For example, suppose we want to comparetwo queries with the clause GROUP BY genre. The results of two queriesare A1 = {a11 = (‘Action’, 3), a12 = (‘Fantasy’, 1)} and A2 = {a21 =(‘Action’, 2), a22 = (‘Fantasy’, 1)}, respectively. Since we can only comparea pair of entries at a time, we separate groups based on the genre attributeand generate rules for (a11, a21) and (a12, a22) independently. Figure 4.4 isthe visualization within the “Fantasy” tab following the example in Fig-ure 4.3. It is equivalent to filtering out movies other than the fantasy onesfrom the provenance tables before applying the algorithm.Figure 4.2: The demo query.174.4.VisualfeedbackFigure 4.3: Visualization of summary rules as feedback.Figure 4.4: Visual feedback after clicking on the “Fantasy” tab.18Chapter 5User studyWe conducted a user study5 to investigate the effectiveness and usefulness ofprovenance summary rules in assisting users in debugging aggregate queries.In the user study, participants were asked to rectify three pre-set incorrectqueries. They received feedback from either our system or a baseline methodto aid in query debugging. During the study, we recorded the time they tookto complete each task, the changes they made to the queries, and notes fromobserving how they approached each question. In addition, participants alsoevaluated the helpfulness of the feedback and their willingness to use it inthe future at the end of the study.We had the following hypotheses to test in the user study:• H1. Users can complete the tasks more quickly using our systemcompared to the baseline method.• H2. Users can achieve higher correctness using our system than thebaseline method.• H3. Users find our system more helpful in debugging aggregate queriesthan the baseline method.5.1 Setting5.1.1 ParticipantsWe recruited individuals who were either current UBC undergraduate orgraduate students or have graduated from UBC within one year. Addition-ally, participants were required to have database knowledge at least equiva-lent to that acquired in an introductory database course and feel comfortablewith reading and writing SQL.5This research is categorized as minimal risk as defined in TCP2 by the BehaviouralResearch Ethics Board at the University of British Columbia. UBC BREB number: H24-00305.195.1. SettingTo reach out to qualified individuals, we posted a call for participationon the discussion bulletin board in relevant classes that qualify studentsfor this study, such as CPSC 304 (Introduction to Relational Databases).In addition, announcements were made through the UBC Department ofComputer Science public channel. Ultimately, we recruited a total of 20participants, who were randomly assigned to either the baseline group orour group.5.1.2 BaselineWe selected SQL*Plus [1] as the platform to generate baseline feedback.SQL*Plus is a command-line interface that provides the basic querying util-ity for ORACLE databases. ORACLE is the designated database systemfor UBC CPSC 304 students to complete labs and assignments, making it agreat representative of the educational systems that we intend to comparewith. Furthermore, all participants in our study should be familiar withits output, thereby eliminating the need for training. To obtain feedback,we ran both correct and incorrect queries in SQL*Plus and combined thesystem output to form the baseline feedback. The exact feedback from thebaseline can be found at Appendix A.1.We also explored other systems proposed in the literature but foundnone suitable as a baseline, mostly due to their incompatibility with aggre-gate queries. For example, RATest [18], I-Rex [19], and CinsGen [17] arethe systems that most aligned with our objective of helping students debugqueries. However, RATest and CinsGen currently do not support aggregatequeries, and I-Rex lacks the feature of generating the smallest counterex-amples that we want to test against. Therefore, we chose SQL*Plus as theonly baseline in our user study.5.1.3 DatasetWe used the IMDB dataset6 in the user study. To simplify the dataset,we only kept one genre for each movie and merged the Movies and Genrestables. We sampled 500 movies and extracted their respective directors fromthe original database. After preprocessing, the test dataset comprises twotables: Movies and Directors. The Movies table consists of 490 distincttuples and 12 attributes, including genre and production company. TheDirectors table contains 448 distinct rows and 3 attributes. These two tablescan be linked by the condition ‘movies.dir id=directors.id’.6https://developer.imdb.com/205.1. Setting5.1.4 TasksIn our study, participants were asked to pinpoint the errors in the incorrectqueries and rectify them. There were three tasks with increasing complexity:aggregation, aggregation with GROUP BY, and aggregation with HAVING.Figures 5.1, 5.2, and 5.3 display the questions, incorrect queries, and refer-ence answers for the three tasks respectively. We also used the demo querymentioned in the previous chapter as a demo task (Figure 4.2) to familiarizethe participants with the interface before the testing began. Note that theanswers listed here are not the only correct answers, and equivalent alterna-tives will also be marked as correct. Appendix A.2 contains the summaryrule feedback for each task. We asked the algorithm to generate up to 7 rulesfor each UScore using no more than three attributes per rule. In practice,all feedback consists of no more than 7 rules.Figure 5.1: Task 1.Figure 5.2: Task 2.215.1. SettingFigure 5.3: Task 3.Task 1 is derived from the running example in [5, Chapter 5]. Whilepreserving the issue with the query (i.e., the absence of ‘Pixar AnimationStudios’ in the incorrect query), we adjusted the predicates to ensure thatthe query will involve a significant number of tuples when executed on thesample database. Additionally, we formulated a question to provide par-ticipants with essential information, while leaving the specifics of “Disneysubsidiaries” for them to explore. This setup resembles a real-world chal-lenge frequently encountered by database administrators (DBAs), wherethey must navigate databases with incomplete knowledge and rely on trialand error to uncover necessary information.Task 2 is adapted from the inspiring example (Example 1) to suit theschema of the test database. The error in the incorrect query is an actualresponse from a student on a final exam, making it highly representative ofthe issues we aim to address.Task 3 is a fabricated example featuring aggregation with HAVING. Theproblem with the query highlights a common yet often overlooked distinctionbetween ‘none’ and is not null, leading to an issue frequently spotted inquery writing. While debugging queries with such an error is inevitable, itoften proves challenging without informative feedback or prior experience.225.1. Setting5.1.5 DesignWe employed the 2x3 mixed factorial design7 with the following variables:• Between-subjects variable: Feedback type, with 2 levels: baseline feed-back or summary rule feedback.• Within-subjects variable: Task, with 3 levels.• Dependent variables, each corresponding to one hypothesis:– Time: We recorded the time taken by participants to completeeach task. The timer automatically starts when they choose thetask in the dropdown menu and stops when they hit the “Submit”or “Give up” button.– Correctness: We recorded the complete answer that participantswrote and measured two kinds of correctness: identifying the cor-rect issues and fixing the query successfully. We separated thesetwo concepts because those who identify the problems success-fully may still fail to correct the queries due to their varyinglevels of proficiency in query writing. This differentiation willhelp to assess the effectiveness of tools by mitigating the impactof individual variances.– Helpfulness and likelihood of future use: To assess perceived help-fulness, we utilized 5-point Likert scales in the post-study ques-tionnaire and asked for qualitative comments and suggestions.The participants were randomly divided into two groups, and each grouponly received one type of feedback across all tasks. Compared to having eachparticipant use both systems, this design can help to control the learningeffect, but the results will be influenced by individual differences.5.1.6 ProceduresWe scheduled an individual session with each participant via email. Theycould choose to participate either in person or online through Zoom. Foronline sessions, participants used their own personal computers to interact7The 2x3 mixed factorial design involves two independent variables, incorporating bothbetween-subjects and within-subjects factors, with two levels for the former and threelevels for the latter. The combination of the variables yields 6 different experimentalconditions. This design facilitates the examination of main effects and interactions betweenthe independent variables.235.1. Settingwith the interface and complete questionnaires. They were asked to sharetheir screen while using the interface, but screen sharing was not requiredfor filling questionnaires. No video or audio was recorded. Before the studystarts, the participant will receive the consent form and have enough timeto go through it. If they are willing to participate in the study, they willsign the form. The study always starts with participants’ signatures.At the beginning of each session, participants completed a pre-studyquestionnaire to collect basic demographic information such as age groupand education level. We also asked their self-assessed familiarity with rela-tional databases and experience with SQL. The contents of the pre-studyquestionnaire can be found in Appendix B.1. After completing the ques-tionnaire, participants were presented with the user interface. The interfaceconsists of the query requirement, the incorrect query, feedback, the rawdatabase, the database schema, and a text input area where participantscan write their answer. Participants can submit their answer or give upif they cannot find any issues with the given query. The only differencebetween the two groups is the feedback provided in the interface.We gave participants a brief introduction to the interface, explainingthe function of each component and how to use them to complete a task.Specifically, in the group using summary rule feedback, we elaborated onthe meaning of feedback, as it may not have appeared intuitive to them. Weargue that this would not bias results, as participants in the baseline grouphad also been previously exposed to the baseline feedback in CPSC 304classes. After the introduction, we invited the participants in both groupsto solve the demo task to become acquainted with the interface. Theycould ask questions during this demo task. Before proceeding to the threetasks, participants were informed that we would record the time and theiranswers, as well as taking notes when observing them solve the tasks. Weasked them not to think aloud during problem-solving to avoid biasing therecorded time, and instead encouraged them to share their thoughts aftersubmitting their answers. After all tasks were completed, we sent them alink to the post-study questionnaire to evaluate the helpfulness of feedbackand solicit comments and suggestions. Each session lasted approximately45-60 minutes. A $15 honorarium was offered to each participant at the endof their session.245.2. Results and discussion5.2 Results and discussionAmong the 20 participants, 11 chose in-person sessions, and 9 chose onlinesessions. There was no observed impact on performance by the format ofthe study. The majority of participants fell into the 20 to 29 age group(85%), with 2 participants aged 19 and under, and 1 participant aged 30to 39. There were 9 undergrads, 9 master students, and 2 PhD candi-dates. 60% of participants reported having less than 1 year of experiencewith SQL, and over half of the participants felt somewhat familiar with re-lational databases and SQL. In terms of difficulty, 60% of participants feltneutral about debugging SQL queries. While most participants did not haveprevious experience with assistance tools for debugging SQL queries, 3 par-ticipants reported using AI tools such as GitHub Copilot8 and Codeium9before for SQL debugging. Further details of participants’ self-assessmentscan be found in Appendix C.5.2.1 TimeFigure 5.4 shows the time distribution for each task and type of feedback.When using the summary rule feedback, participants spent much less timeon T1 and slightly less time on T3 than those in the baseline group. How-ever, students took more time to solve T2 with our feedback. This may beattributed to the distinct nature of T2 compared to the other two tasks. InT1 and T3, the primary challenge lies in identifying issues with the queries,and once these issues are recognized, correcting the queries is relativelystraightforward. However, in T2, although the problem with the query maybe apparent, the incorrect answer is so different from the correct one thatparticipants often spent the majority of their time attempting to rectify thequery.As we have both between-subjects and within-subjects independent vari-ables, we employed a mixed ANOVA to test the statistical significance oftheir impact on time. We examined ANOVA assumptions, including ho-mogeneity of variances, sphericity, and normality of residuals, to ensurethat the test is applicable to our data. The formula utilized in ANOVAis Time ~ Treatment*Task + Error(Participant_ID/Task). The resultsdo not demonstrate statistical significance for both Task and Treatment aswell as their interaction. There are several possible reasons for this outcome.Firstly, time can be affected by both the helpfulness of feedback and partici-8https://github.com/features/copilot9https://codeium.com/255.2. Results and discussionFigure 5.4: Boxplots of time used for each task in different treatments.pants’ familiarity with the feedback format. Since the concept of provenancewas not covered in the introductory database course, it would be challengingfor most participants to understand and utilize the summary rule feedback,which might eventually prolong the time they took to complete the tasks.Secondly, time appeared to be strongly influenced by individual differences.This is supported by our observations during the study. For example, whenparticipants encountered challenging questions that they ultimately failed toanswer, some quickly gave up, while others persevered for up to 16 minutesbefore giving up. Even when the issue seemed obvious, some individualswere very cautious and would double-check their findings in the database.We even found participants who recalculated the coverage of summary rulesto validate their assumptions. The high variances and outliers depicted inFigure 5.4 also highlight the individual differences.5.2.2 CorrectnessTable 5.1 summarizes the correctness in different tasks and types of feedback.Given the binary nature of the variables, we used the logit model and Waldtest to examine whether there were any statistically significant differencesin the data. The logit model passed Chi-square goodness of fit test with ap-value less than 0.05. From the table, it is evident that individuals usingsummary rule feedback outperformed those in the baseline group in both265.2. Results and discussionidentifying the problems and writing the correct answers. The Wald testindicated that the feedback type has a significant effect on identifying thecorrect issues (P < 0.01) and writing the right answers (P < 0.05). Insummary rule feedback, the log odds increase by 4.5545 (P < 0.01) foridentifying issues and by 1.6440 (P < 0.01) for writing the correct answer.In addition to feedback type, tasks also have a statistically significant impacton the success rate of identifying the problems (P < 0.05), but no notableeffect on writing the correct answer (P > 0.1). The probability of findingthe issues in T3 drops significantly (Estimate Std.=-3.6798, P < 0.01),possibly because no participants in the baseline group managed to identifythe problems in T3. The impact of tasks was anticipated as we intentionallydesigned them with increasing difficulty. The results demonstrate that oursystem effectively enhances students’ correctness in debugging aggregatequeries.Find problems Answer is correctBaseline Ours Baseline OursTask 1 80% 100% 10% 60%Task 2 80% 90% 40% 40%Task 3 0% 100% 0% 50%Average 53.3% 96.7% 16.7% 50%Table 5.1: Summarization of correctness.We observed distinct patterns in the mistakes participants made whenusing different feedback. In Task 1, 40% of participants in the baselinegroup added “Walt Disney Production” to the results instead of the correctanswer, “Pixar Animation Studios”, while no participants using summaryrule feedback made the same mistake. This occurred because when userstyped “Disney” in the database, they found only one entry with this com-pany name, which was not included in the results yet. Since the feedbackindicated that the wrong query only lost one count compared to the correctone, adding this entry seemed to be a compelling choice. However, theyoverlooked the fact that the revenue in this entry does not meet anotherpredicate revenue > 300000000 and thus will not be selected. This errorwas effectively prevented when participants received prompts from the sum-mary rule feedback, which helps them to narrow down the possibilities. Thedifferences in errors between the two treatment groups are more obvious inTask 3. In the baseline group, all participants failed to associate the prob-275.2. Results and discussionlem with “none”. 70% of them changed “d.id” in the aggregate functionto “m.id”, arguing that the specification required counting movies insteadof directors. However, this is not an issue when selecting from the joinedtable of Movies and Directors. In contrast, participants using summary rulefeedback all understood that the wrong query retrieved extra “none”, buthalf of them did not associate it with the clause is not null. Four of themadded one more production_company is not null in the outer query’sWHERE clause, which would not be useful. This finding demonstrates thatwhile our system is effective at helping users identify the semantic problems,identifying the correct clauses in the query that lead to those problems reliesmore on students’ experience.5.2.3 Helpfulness and likelihood of use in the futureWe chose the Mann-Whitney U test as the nonparametric test to comparethe differences in reported helpfulness and likelihood of future use betweenthe two groups. Results indicate that the user-assessed helpfulness of ourmethod is higher than the baseline (P < 0.01), but the increase in likelihoodis not statistically significant (P > 0.1). Figure 5.5 provides further detailsof participants’ responses. Based on our conversations with participants,the reason why people expressed a likelihood of using the baseline methodin the future despite giving it a low helpfulness rating is that they believedhaving a simple feedback would not cause cognitive overload and is betterthan having no feedback at all.5.2.4 Comments and suggestionsWe summarized several key points from the comments and suggestions par-ticipants left in the post-study questionnaire.A very common suggestion is to make the feedback interactive. Nineparticipants in the baseline group and two using our method mentioned thisissue. A basic improvement is to update the feedback when users changethe query, while a more advanced system could act like a debugger, showingsub-query results. Our system also has potential for other interactive fea-tures, like letting users choose the attribute for summarization. However,one participant expressed concern about the overhead associated with inter-activity. With high latency, they would “probably prefer to manually debugthe query with a smaller sample table”.Additionally, participants have raised several factors that will impactthe helpfulness of summary rule feedback, including context, types of er-285.2. Results and discussionFigure 5.5: The diverging stacked bar chart of user-perceived helpfulness offeedback and likelihood of using it in the future.rors, and aggregate functions. Three participants noted that this methodmay only be applicable to pedagogical settings where the correct answer isreadily available. One participant expressed concern that even within aneducational context, the feedback might already reveal the answer to thestudents. Moreover, two participants observed that the feedback is morebeneficial for T1 and T3 compared to T2, which aligns with our analysisof participants’ performance. They argued that summary rules are particu-larly helpful when there is a clear distinction in coverage between incorrectand correct queries, as seen in T3 where the coverage for the correct queryis 0 for ‘none’. However, its utility diminishes when the distinction is lessclear, as in T2. Furthermore, one participant highlighted that certain ag-gregate functions are easier to debug, reducing the necessity for feedback.For instance, COUNT has a simpler provenance compared to AVG, making itrelatively easier to identify issues within the query.Another interesting finding is that some suggestions participants pro-posed for the baseline method have been resolved in our technique. Forinstance, a participant suggested having a feature to visualize differencesbetween correct and incorrect outputs, a feature we have implemented ascoverage in our system. Another participant criticized the baseline methodfor its lack of effectiveness in narrowing down the possibilities. This may ex-plain a common strategy we observed in the baseline group: they spent con-295.2. Results and discussionsiderable time combing through the raw database to pinpoint issues. Whileparticipants using our method also occasionally consulted the database, itwas not like finding a needle in a haystack thanks to the hints provided bythe feedback.To our surprise, there was little comment on the understandability ofsummary rules. This is intriguing because understanding feedback in anunfamiliar format should have posed a challenge. Only one participant men-tioned that the feedback was hard to understand in the first place, but onceunderstood, it was very helpful.5.2.5 DiscussionThe study shows that participants achieved significantly higher correctnessusing our method, both in identifying the correct issues (P < 0.01) andwriting the right answers (P < 0.05). This finding supports our secondhypothesis (H2). There is also a statistical significance in the increase ofhelpfulness in our method, which supports H3. However, the likelihoodfor future use does not have significant increase compared to the baselinemethod. In addition, there is no significant difference in the time usedbetween two groups (P > 0.1), failing to reject the null hypothesis of H1. Wehave analyzed potential reasons of it in Section 5.2.1. While time appears notsuitable for differentiating the effectiveness of two feedback, user assessedconfidence could be a better alternative. In our observation, participantsusing the baseline method tended to feel unsure about their modification,which could not be represented in any measurements we have so far. Addingconfidence will provide a new perspective to understand students’ strugglesand compare different techniques.Since feedback is a between-subjects variable, participants did not havea chance to use different types of feedback in the study and give their prefer-ences. However, when we showed the summary rule feedback to the baselinegroup after the study, all of them felt that the tool would be more helpfulbased on their first impression and expressed strong interest in trying thetool.30Chapter 6Conclusion and future workIn this study, we analyzed the common mistakes of aggregate queries thatstudents made in final exams and proposed a new technique to assist stu-dents in debugging aggregate queries. We extended the comparative sum-mary method from [6] to handle two queries and support numerical at-tributes. Additionally, we designed an interactive visual feedback for thesummary to facilitate exploration. To evaluate the effectiveness and utilityof the technique, we conducted a user study to compare feedback consistingof summary rules with a baseline method. The results demonstrate a notableimprovement in students’ accuracy when debugging aggregate queries withour feedback. Moreover, participants rated the helpfulness of our feedbacksignificantly higher than that of the baseline method. In addition to aidingstudents in query debugging, our technique can also be applied to verify theequivalence of two aggregate queries in a broader context.There are many promising ways to extend this work.As shown in the user study, our feedback significantly enhanced partici-pants’ ability to identify problems, but it had limited impact on helping stu-dents make accurate revisions. A simple approach to mitigate this problemis to improve the interactivity of the system, such as regenerating summaryrules every time users finish their changes. We can also allow users to choosethe attributes to include in the summary rules. However, adding interac-tivity will require optimizing the efficiency of the algorithm to maintain asmooth user experience. A more sophisticated solution is to enable usersto trace the intermediate results of query evaluation, similar to a debugger.This idea draws inspiration from I-Rex [19], but by utilizing summary rulesto display intermediate results, we can improve efficiency by eliminating thenecessity of inspecting tuples one by one. Developing a debugger not onlyempowers users in query debugging, but also broadens the potential usecases of our system, as it reduces the dependency on standard answers.There are numerous ways students can make mistakes when authoringaggregate queries, and our feedback can only handle some of them. Whilethe summary rules effectively reveal issues in the WHERE clause, errors inother locations such as ORDER BY and SELECT are hard to identify with the31Chapter 6. Conclusion and future workcurrent solution. Future research can explore new techniques to handleerrors in those clauses. In addition, our method faces limitations when thewrong query uses different tables than those used in the correct one, as theprovenance of two queries may not share the same schema. While a quicksolution could be intersecting the provenance before running the algorithm,better solutions must exist and deserve further investigation.The comprehensibility of the feedback still has room for improvement.Even though participants did not raise concerns about this aspect, we sus-pected that the unintuitive display led to the participants spending moretime solving a question. Moreover, currently we used a tutorial to trainparticipants to read the feedback, but ideally, it should be self-explanatory.This requires more efforts in understanding the students’ mental model andrepresenting the summary rules with concepts familiar to them.In summary rules, we only used original value for categorical attributesand quantile intervals for numerical attributes. However, there are numer-ous ways to extract advanced features and encode additional informationin the summary. For instance, wildcards can be employed in emphasizingpatterns in categorical attributes, and constants within queries, such as the“6” in vote_average>6, can serve as cut points for discretizing numericalattributes. The relationship between attributes can also be exploited togenerate a more powerful summary. This will entail more complex methodsof feature selection, and integrating them with summary rules would be anintriguing topic to explore.While the scalability of the algorithm was not the focus of the study,it’s a crucial consideration for enhancing overall usability. In our solution,we fully materialized the JOIN before extracting the summary rules. Whileit’s possible to extract separate rules for individual tables, we opted forextracting a single rule to reduce complexity. Future research could focuson optimizing the algorithm to eliminate the need for materialization. Asample-based approach is also recommended for querying in a large database.Additionally, since students often need to attempt multiple times beforearriving at the correct answer, modifying rules based on previous iterationsis also a feasible way to reduce overhead. This approach also enables theincorporation of information from historical queries, potentially making thefeedback more beneficial.Finally, the CPS algorithm requires users to specify the attribute listsused for generating summary rules as a parameter. While manual selectionoffers higher interactivity, ideally, the algorithm should be able to automat-ically select relevant attributes for a query. Future work could draw uponfeature selection literature to automate this process.32Bibliography[1] SQL*Plus Quick Start. URL https://docs.oracle.com/cd/B14117_01/server.101/b12170/qstart.htm.[2] Firas Abuzaid, Peter Kraft, Sahaana Suri, Edward Gan, Eric Xu, AtulShenoy, Asvin Ananthanarayan, John Sheu, Erik Meijer, Xi Wu, et al.DIFF: a relational interface for large-scale data explanation. The VLDBJournal, 30:45–70, 2021.[3] Alireza Ahadi, Vahid Behbood, Arto Vihavainen, Julia Prior, and Ray-mond Lister. Students’ syntactic mistakes in writing seven differenttypes of SQL queries and its application to predicting students’ success.In Proceedings of the 47th ACM Technical Symposium on ComputingScience Education, pages 401–406, 2016.[4] Ridha Alkhabaz, Zepei Li, Sophia Yang, and Abdussalam Alawini.Student’s learning challenges with relational, document, and graphquery languages. In Proceedings of the 2nd International Workshop onData Systems Education: Bridging education practice with educationresearch, pages 30–36, 2023.[5] Omar AlOmeir. Provenance in relational databases: usability and ap-plications. PhD thesis, University of British Columbia, 2023.[6] Omar AlOmeir, Eugenie Y Lai, Mostafa Milani, and Rachel Pot-tinger. Summarizing provenance of aggregate query results in relationaldatabases. IEEE Transactions on Knowledge and Data Engineering,2023.[7] Adriane Chapman and HV Jagadish. Why not? In Proceedings ofthe 2009 ACM SIGMOD International Conference on Management ofData, pages 523–534, 2009.[8] Peng Chen, Beth Plale, and Mehmet S Aktas. Temporal representationfor mining scientific data provenance. Future Generation ComputerSystems, 36:363–378, 2014.33Bibliography[9] James Cheney, Laura Chiticariu, and Wang-Chiew Tan. Provenancein databases: Why, how, and where. Foundations and Trends® inDatabases, 1(4):379–474, 2009.[10] Yingwei Cui and Jennifer Widom. Lineage tracing in a data warehous-ing system. In Proceedings of 16th International Conference on DataEngineering (Cat. No. 00CB37073), pages 683–684. IEEE, 2000.[11] Sneha Gathani, Peter Lim, and Leilani Battle. Debugging databasequeries: A survey of tools, techniques, and users. In Proceedings of the2020 CHI Conference on Human Factors in Computing Systems, pages1–16, 2020.[12] Boris Glavic and Klaus Dittrich. Data provenance: A categorizationof existing approaches. In Datenbanksysteme in Business, Technologieund Web (BTW 2007) – 12. Fachtagung des GI-Fachbereichs “Daten-banken und Informationssysteme” (DBIS), pages 227–241. Gesellschaftfu¨r Informatik e. V., Bonn, 2007. ISBN 978-3-88579-197-3.[13] Ryan Hardt and Esther Gutzmer. Database query analyzer (DBQA)a data-oriented SQL clause visualization tool. In Proceedings of the18th Annual Conference on Information Technology Education, pages147–152, 2017.[14] Rui Hu, Zheng Yan, Wenxiu Ding, and Laurence T Yang. A survey ondata provenance in IoT. World Wide Web, 23:1441–1463, 2020.[15] Anthony Kleerekoper and Andrew Schofield. SQL tester: an onlineSQL assessment tool and its impact. In Proceedings of the 23rd AnnualACM Conference on Innovation and Technology in Computer ScienceEducation, pages 87–92, 2018.[16] Seokki Lee, Bertram Luda¨scher, and Boris Glavic. Provenance sum-maries for answers and non-answers. Proceedings of the VLDB Endow-ment, 11(12):1954–1957, 2018.[17] Hanze Meng, Zhengjie Miao, Amir Gilad, Sudeepa Roy, and Jun Yang.Characterizing and verifying queries via CINSGEN. In Companion ofthe 2023 International Conference on Management of Data, pages 143–146, 2023.[18] Zhengjie Miao, Sudeepa Roy, and Jun Yang. RATest: Explaining wrongrelational queries using small examples. In Proceedings of the 201934BibliographyInternational Conference on Management of Data, pages 1961–1964,2019.[19] Zhengjie Miao, Tiangang Chen, Alexander Bendeck, Kevin Day,Sudeepa Roy, and Jun Yang. I-Rex: an interactive relational queryexplainer for SQL. Proceedings of the VLDB Endowment, 13(12):2997–3000, 2020.[20] Andrew Migler and Alex Dekhtyar. Mapping the SQL learning pro-cess in introductory database courses. In Proceedings of the 51st ACMTechnical Symposium on Computer Science Education, pages 619–625,2020.[21] Chaitanya Mishra and Nick Koudas. Interactive query refinement.In Proceedings of the 12th International Conference on ExtendingDatabase Technology: Advances in Database Technology, pages 862–873, 2009.[22] Antonija Mitrovic. An intelligent SQL tutor on the web. InternationalJournal of Artificial Intelligence in Education, 13(2-4):173–197, 2003.[23] Tobias Mu¨ller and Pascal Engel. How, Where, and Why dataprovenance improves query debugging: A visual demonstration offine–grained provenance analysis for SQL. In 2022 IEEE 38th Inter-national Conference on Data Engineering (ICDE), pages 3178–3181.IEEE, 2022.[24] Sudeepa Roy and Dan Suciu. A formal approach to finding explana-tions for database queries. In Proceedings of the 2014 ACM SIGMODInternational Conference on Management of Data, pages 1579–1590,2014.[25] Shazia Sadiq, Maria Orlowska, Wasim Sadiq, and Joe Lin. SQLator:an online SQL learning workbench. In Proceedings of the 9th AnnualSIGCSE Conference on Innovation and Technology in Computer Sci-ence Education, pages 223–227, 2004.[26] Yogesh L Simmhan, Beth Plale, and Dennis Gannon. A survey of dataprovenance in e-science. ACM SIGMOD Record, 34(3):31–36, 2005.[27] Manasi Vartak, Venkatesh Raghavan, Elke Rundensteiner, and SamuelMadden. Refinement driven processing of aggregation constrainedqueries. Advances in Database Technology - EDBT, 2016.35[28] Michael Vollmer, Lukasz Golab, Klemens Bo¨hm, and Divesh Srivastava.Informative summarization of numeric data. In Proceedings of the 31stInternational Conference on Scientific and Statistical Database Man-agement, pages 97–108, 2019.[29] Matthew Weston, Haorong Sun, Geoffrey L Herman, Hisham Benot-man, and Abdussalam Alawini. Echelon: An AI tool for clusteringstudent-written SQL queries. In 2021 IEEE Frontiers in EducationConference (FIE), pages 1–8. IEEE, 2021.[30] Eugene Wu and Samuel Madden. Scorpion: Explaining away outliersin aggregate queries. Proceedings of the VLDB Endowment, 6(8), 2013.[31] Sophia Yang, Geoffrey L Herman, and Abdussalam Alawini. Analyzingstudent SQL solutions via hierarchical clustering and sequence align-ment scores. In 1st International Workshop on Data Systems Education,pages 10–15, 2022.[32] Sophia Yang, Geoffrey L Herman, and Abdussalam Alawini. MiningSQL problem solving patterns using advanced sequence processing algo-rithms. In Proceedings of the 2nd International Workshop on Data Sys-tems Education: Bridging education practice with education research,pages 37–43, 2023.[33] Ilkay Melek Yazici and Mehmet S Aktas. A novel visualization ap-proach for data provenance. Concurrency and Computation: Practiceand Experience, 34(9):e6523, 2022.[34] Jun Zhao, Chris Wroe, Carole Goble, Robert Stevens, Dennis Quan,and Mark Greenwood. Using semantic web technologies for representinge-science provenance. In International Semantic Web Conference, pages92–106. Springer, 2004.36Appendix AFeedback in the user studyA.1 Baseline feedbackFigure A.1 shows the feedback for each task in the user study.Figure A.1: Baseline feedback for each task.A.2 Summary rule feedbackFigures A.2, A.3, and A.4 are the summary rule feedback for each task. Thefeedback for the demo task can be found in A.5.37A.2.SummaryrulefeedbackFigure A.2: Summary rule feedback for Task 1 (Figure 5.1).Figure A.3: Summary rule feedback for Task 2 (Figure 5.2).38A.2.SummaryrulefeedbackFigure A.4: Summary rule feedback for Task 3 (Figure 5.3).Figure A.5: Summary rule feedback for the demo task (Figure 4.2).39Appendix BQuestionnairesB.1 Pre-study questionnaireSection I: Demographic InformationQ1. In what age group are you?• 19 and under• 20-29• 30-39• 40-49• More than 50Q2. Which program are you pursuing?• Bachelor• Master• PhDSection II: Experience with databasesQ3. How familiar are you with relational databases and SQL?• Not at all familiar• Slightly familiar• Somewhat familiar• Moderately familiar• Extremely familiarQ4. How many years of experiences do you have with writing SQL?40B.2. Post-study questionnaire• Less than one year• 1-2 years• 3-4 years• 5-6 years• More than 6 yearsQ5. In terms of difficulty, how would you describe your experience withdebugging SQL queries?• Very difficult• Difficult• Neutral• Easy• Very easyQ6. Have you ever used any assistance tools (e.g., debugger) for debug-ging SQL queries?• No, I never used any tools for debugging SQL queries.• YesIf yes, please specify: ______B.2 Post-study questionnaireQ1. How helpful did you find the tool you just used in debugging aggregatequeries?• Very helpful• Helpful• Neutral• Unhelpful• Very unhelpful41B.2. Post-study questionnaireQ2. If offered, how likely are you to use the tool for debugging aggregatequeries in the future?• Very likely• Likely• Neutral• Unlikely• Very unlikelyQ3. Do you have any suggestions or comments regarding the tool?42Appendix CResults from pre-studyquestionnaireFigures C.1, C.2, and C.3 are pie charts that summarize the results fromthe pre-study questionnaire.Figure C.1: Participants’ self-assessed experience with relational databasesand SQL.43Appendix C. Results from pre-study questionnaireFigure C.2: Participants’ self-assessed difficulty with debugging SQL.Figure C.3: Participants’ self-assessed familiarity with debugging SQL.44
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Pottinger, Rachel
Empowering student query debugging : feedback for aggregate queries via provenance summarization
Text