diff --git a/Koli_2017/Koli_2017_Stanger.tex b/Koli_2017/Koli_2017_Stanger.tex index 46dc52f..57a224e 100644 --- a/Koli_2017/Koli_2017_Stanger.tex +++ b/Koli_2017/Koli_2017_Stanger.tex @@ -119,37 +119,21 @@ \section{Related work} \label{sec-literature} -There have been many prior efforts to build learning systems for SQL. However, these have focused almost exclusively on SQL queries using the \texttt{SELECT} statement (i.e., DML) rather than schema definitions (DDL). This is unsurprising given that \texttt{SELECT} is probably the most frequently used of any SQL statement, and also because it is relatively complex compared to most other SQL statements. +There have been many prior efforts to build systems to support students learning SQL. Early examples such as RDBI \cite{Dietrich.S-1993a-An-educational} and esql \cite{Kearns.R-1997a-A-teaching} were essentially simple query execution environments that students could use to practice writing SQL queries. RDBI provided relatively little feedback about the correctness of a query, whereas esql could visualize the intermediate tables generated by each step of a query, enabling students to better understand the steps in its execution. -\citeauthor{Dietrich.S-1993a-An-educational}'s \emph{RDBI} \cite{Dietrich.S-1993a-An-educational} was a Prolog-based interpreter for relational algebra, tuple and domain relational calculus, and SQL. It focused primarily on queries, and used its own non-SQL data definition language. RDBI did not provide feedback on students' attempts beyond basic syntax checking and displaying query results. +Later systems became more responsive in terms of the feedback they provided to students. Systems like SQL-Tutor \cite{Mitrovic.A-1998a-Learning}, SQLator \cite{Sadiq.S-2004a-SQLator}, AsseSQL \cite{Prior.J-2004a-Backwash}, ActiveSQL\footnote{\url{https://db.grussell.org/}} \cite{Russell.G-2004a-Improving,Russell.G-2005a-Online}, SQLify \cite{Dekeyser.S-2007a-Computer}, and aSQLg \cite{Kleiner.C-2013a-Automated} all provided varying levels of syntactic and semantic feedback. Many of these took a more ``functional'' approach to checking SQL query code, i.e., verifying that the code written fulfilled the requirements of the problem, rather than focusing on the code itself. This was most commonly done by checking how much the result set of a student's query differed from the correct result set (e.g., SQLator's ``equivalence engine''). ActiveSQL could also detect ``hard-coded'' queries that produced the desired result, but would fail if the data set changed \cite{Russell.G-2005a-Online}, while the SQL Exploratorium \cite{Brusilovsky.P-2010a-Learning} took an interesting alternative approach, using parameterized query templates to generate the questions given to students. -\citeauthor{Kearns.R-1997a-A-teaching}'s \emph{esql} \cite{Kearns.R-1997a-A-teaching} supported students in learning the fundamental concepts underlying SQL. It could parse and execute \texttt{CREATE}, \texttt{DROP}, \texttt{ALTER}, \texttt{DELETE}, \texttt{INSERT}, and \texttt{SELECT} statements, but all of these except \texttt{SELECT} were simply passed through to the DBMS. The system enabled students to better understand the steps in the execution of a query by visualizing the intermediate tables generated by each step of the query. It did not provide feedback on students' attempts beyond basic syntax checking and displaying query results. +Given the relatively static nature of an SQL schema, we feel this style of verification approach is the most appropriate way of approaching an automated grading system for SQL DDL. As an aside, the concept of verifying a schema against its specification sounds like it should be a useful application of formal methods \cite{Spivey.J-1989a-An-introduction}, but work with formal methods and databases has historically focused either on \emph{generating} a valid schema from a specification (e.g., \cite{Vatanawood.W-2004a-Formal,Lukovic.I-2003a-Proceedings,Choppella.V-2006a-Constructing}), or on verifying schema transformation and evolution \cite{Bench-Capon.T-1998a-Report}. Certainly formal methods approaches could be used to generate the model answer or rubric for grading an assessment, but this is effectively the inverse of what is needed to grade a student-written schema. -\citeauthor{Mitrovic.A-1998a-Learning}'s \emph{SQL-Tutor} \cite{Mitrovic.A-1998a-Learning} was an intelligent teaching system that provided students with a guided discovery learning environment for SQL queries. It supported only the \texttt{SELECT} statement, and used constraint-based modeling \cite{Ohlsson.S-1992a-Constraint-based,Ohlsson.S-2016a-Constraint-based} to provide feedback to students on both syntactic and semantic SQL errors. +Previous systems focused almost exclusively on SQL \emph{queries} using the \texttt{SELECT} statement (i.e., DML) rather than SQL \emph{schema definitions} (DDL). This focus is unsurprising given that \texttt{SELECT} is probably the most frequently used of any SQL statement, and also because it is relatively complex compared to most other SQL statements. Only a few of systems we reviewed even mentioned schema definition. RDBI \cite{Dietrich.S-1993a-An-educational} supported a DDL, but only its own non-SQL language, while esql \cite{Kearns.R-1997a-A-teaching} simply passed anything that was not a \texttt{SELECT} statement through to the DBMS. \citeauthor{Gong.A-2015a-CS-121-Automation}'s ``CS 121 Automation Tool'' \cite{Gong.A-2015a-CS-121-Automation} focuses primarily on SQL DML statements, but appears to be extensible and could potentially be modified to support SQL DDL statements. -\citeauthor{Sadiq.S-2004a-SQLator} \emph{SQLator} \cite{Sadiq.S-2004a-SQLator} was a web-based interactive tool for learning SQL. Students were presented with a series of questions in English, and had to write SQL \texttt{SELECT} statements to answer these questions. SQLator used an ``equivalence engine'' to determine whether an SQL query fulfilled the requirements of the original English question. SQLator supported only the \texttt{SELECT} statement, and provided only basic feedback (correct or incorrect) to students. SQLator was able to automatically mark about a third of submitted queries as correct, thus improving the speed of grading. +Many previous systems have implemented some form of automated or semi-automated grading, e.g., SQLator \cite{Sadiq.S-2004a-SQLator}, AssesSQL \cite{Prior.J-2004a-Backwash}, ActiveSQL \cite{Russell.G-2004a-Improving,Russell.G-2005a-Online}, SQLify \cite{Dekeyser.S-2007a-Computer}, aSQLg \cite{Kleiner.C-2013a-Automated}, \citeauthor{Gong.A-2015a-CS-121-Automation}'s ``CS 121 Automation Tool'' \cite{Gong.A-2015a-CS-121-Automation}, and XDa-TA\footnote{\url{http://www.cse.iitb.ac.in/infolab/xdata/}} \cite{Bhangdiya.A-2015a-XDa-TA,Chandra.B-2015a-Data,Chandra.B-2016a-Partial}. Some (e.g., SQLator, AssesSQL) provided only correct/incorrect responses, while others (e.g, ActiveSQL, SQLify, aSQLg, XDa-TA) had more sophisticated schemes for assigning partial credit, such as ActiveSQL's accuracy score, SQLify's eight-level scale, and XDa-TA's ability to generate data sets designed to catch common errors. In either case, these systems were often able to automatically mark a significant fraction (e.g., about a third for SQLator \cite{Sadiq.S-2004a-SQLator}) of submitted queries as correct without human intervention, thus reducing marking load for teachers. -\citeauthor{Prior.J-2004a-Backwash}'s \emph{AsseSQL} \cite{Prior.J-2004a-Backwash} was an online examination environment for evaluating students' ability to formulate SQL queries. Students would write and execute their queries, and the data set produced by their query would be compared against the correct data set. The answer would then be flagged as correct or incorrect as appropriate. AsseSQL supported only the \texttt{SELECT} statement. +To our knowledge there has been no work on automated grading of SQL DDL statements. While dealing with \texttt{CREATE} statements should be simpler than dealing with \texttt{SELECT} statements, the ability to at least semi-automate the grading of SQL schema definitions should reap rewards in terms of more consistent application of grading criteria, and faster turnaround time \cite{Douce.C-2005a-Automatic,Russell.G-2004a-Improving,Dekeyser.S-2007a-Computer,Prior.J-2004a-Backwash}. -\citeauthor{Russell.G-2004a-Improving}'s \emph{ActiveSQL}\footnote{\url{https://db.grussell.org/}} \cite{Russell.G-2004a-Improving,Russell.G-2005a-Online} was an online interactive learning environment for SQL that provided immediate feedback to students. ActiveSQL measured the accuracy of a query in a similar way to \citeauthor{Prior.J-2004a-Backwash}'s AsseSQL, but instead of a simple correct/incorrect answer, it computed an accuracy score based on the differences between the query output and the correct answer. It was also able to detect ``hard-coded'' queries that produced the desired result, but would fail if the data set changed \cite{Russell.G-2005a-Online}. ActiveSQL supported only the \texttt{SELECT} statement. +Another branch of related work is systems that actively aid students in learning SQL. SQL-Tutor \cite{Mitrovic.A-1998a-Learning} was an intelligent teaching system that provided students with a guided discovery learning environment for SQL queries, and used constraint-based modeling \cite{Ohlsson.S-1992a-Constraint-based,Ohlsson.S-2016a-Constraint-based} to provide feedback to students. \citeauthor{Kenny.C-2005a-Automated} \cite{Kenny.C-2005a-Automated} described a similar SQL learning system that incorporated an assessment of a student's previous progress. This enabled a more personalized and adaptive approach to student learning, where feedback was tailored according to student progress. -\citeauthor{Dekeyser.S-2007a-Computer}'s \emph{SQLify} \cite{Dekeyser.S-2007a-Computer} was another online SQL learning system that incorporated semantic feedback and automatic assessment. SQLify evaluated each query on an eight-level scale that covered query syntax, output schema, and query semantics. Instructors could use this information to award an overall grade. Again, SQLify supported only the \texttt{SELECT} statement. - -\citeauthor{Brusilovsky.P-2010a-Learning}'s \emph{SQL Exploratorium} \cite{Brusilovsky.P-2010a-Learning} took an interesting approach to generating problems, using parameterized query templates to generate the questions given to students. Again, the SQL Exploratorium supported only the \texttt{SELECT} statement. - -\citeauthor{Kleiner.C-2013a-Automated}'s \emph{aSQLg} \cite{Kleiner.C-2013a-Automated} was an automated assessment tool that provided feedback to students. This enabled students to improve their learning by making further submissions after incorporating this feedback. The aSQLg system checked queries for syntax, efficiency (cost), result correctness, and statement style. Again, aSQLg supported only the \texttt{SELECT} statement. - -\citeauthor{Kenny.C-2005a-Automated} \cite{Kenny.C-2005a-Automated} described an SQL learning system similar to those already described, which also incorporated an assessment of a student's previous progress. This enabled a more personalized and adaptive approach to student learning, where feedback was tailored according to student progress. Again, this system supported only the \texttt{SELECT} statement. - -\citeauthor{Bhangdiya.A-2015a-XDa-TA}'s \emph{XDa-TA}\footnote{\url{http://www.cse.iitb.ac.in/infolab/xdata/}} extended the idea of automated grading of SQL by adding the ability to generate data sets designed to catch common errors. These data sets were automatically derived from a set of correct SQL queries \cite{Bhangdiya.A-2015a-XDa-TA,Chandra.B-2015a-Data}. Later work \cite{Chandra.B-2016a-Partial} added support for awarding partial marks. - -\citeauthor{Gong.A-2015a-CS-121-Automation}'s ``CS 121 Automation Tool'' \cite{Gong.A-2015a-CS-121-Automation} was a tool designed to semi-automate the grading of SQL assessments, again focusing on SQL DML statements. Interestingly, the system appears to be extensible and could thus potentially be modified to support grading of SQL DDL statements. - -There is relatively little work on unit testing of databases. Most authors working in this area have focused on testing database \emph{applications} rather than the database itself (e.g., \cite{Binnig.C-2008a-Multi-RQP,Chays.D-2008a-Query-based,Marcozzi.M-2012a-Test,Haller.K-2010a-Test}). \citeauthor{Ambler.S-2006a-Database} discusses how to test the functionality of a database \cite{Ambler.S-2006a-Database}, while \citeauthor{Farre.C-2008a-SVTe} test the ``correctness'' of a schema \cite{Farre.C-2008a-SVTe}, focusing mainly on consistency of constraints. Neither consider whether the database schema meets the specified requirements. - -To our knowledge there has been no work on automated grading of SQL DDL statements. While dealing with these is simpler than dealing with \emph{SELECT} statements, the ability to at least semi-automate the grading of SQL schema definitions should reap rewards in terms of more consistent application of grading criteria, and faster turnaround time. - -Several of the systems discussed in this section \cite{Sadiq.S-2004a-SQLator,Prior.J-2004a-Backwash,Russell.G-2004a-Improving,Dekeyser.S-2007a-Computer,Kleiner.C-2013a-Automated} have considered a more ``functional'' approach to checking SQL code, i.e., verifying that the code written fulfills the requirements of the problem, rather than focusing on the code itself. Mainly this has focused on how much the result set of a student's query differs from the correct result set. Given the relatively static nature of an SQL schema, we feel this verification approach is the most appropriate way of approaching an automated grading system. This sounds like it should be a useful application of formal methods \cite{Spivey.J-1989a-An-introduction}, but work with formal methods and databases has mainly focused either on \emph{generating} a valid schema from a specification (e.g., \cite{Vatanawood.W-2004a-Formal,Lukovic.I-2003a-Proceedings,Choppella.V-2006a-Constructing}), or on verifying schema transformation and evolution \cite{Bench-Capon.T-1998a-Report}. +There is relatively little prior work on unit testing of databases. Most authors working in this area have focused on testing database \emph{applications} rather than the database itself (e.g., \cite{Binnig.C-2008a-Multi-RQP,Chays.D-2008a-Query-based,Marcozzi.M-2012a-Test,Haller.K-2010a-Test}). \citeauthor{Ambler.S-2006a-Database} discusses how to test the functionality of a database \cite{Ambler.S-2006a-Database}, while \citeauthor{Farre.C-2008a-SVTe} test the ``correctness'' of a schema \cite{Farre.C-2008a-SVTe}, focusing mainly on consistency of constraints. Neither consider whether a database schema conforms to the requirements of the original specification. \section{Motivation}