THE METHOD OF STUDENT'S QUERY ANALYSIS WHILE INTELLIGENT COMPUTER TUTORING IN SQL

Recently, IT specialties have become one of the most demanded specialties in the world labor market. Simultaneously the traditional teaching in conditions of mass production, even with a professional teacher, has a significant drawback – the fundamental impossibility of adapting to each student. Since the 60s of the twentieth century, researchers worldwide have been developing various computer-tutoring tools that have, less or more, adaptive functions. Nevertheless, the task of the perfect computer tutor development is still far from being solved. The article's research subject is the process of student requests analyzing during intelligent computer tutoring in SQL. The main goal is to develop a method for analyzing the student's SQL queries. The purposes: to form a general scheme and features of the method for analyzing student’s SQL queries based on the principles of technical diagnostics and methods of lexical, syntactic analysis of computer programs; to develop methods for parse tree construction; to create methods for comparing reference and real SQL queries according to their similarity rate; to demonstrate the function ability of the developed methods on specific examples. The methods used computer programs the automatic testing method, the computer programs lexical and syntactic analysis methods, the computer programs parsing trees construction methods, the objects diagnosing method based on comparison with a reference, the strings analysis methods, the method of q-grams. The following results were obtained: the student’s SQL queries analysis method was formed based on a system approach including automatic testing on real data, building query-parsing trees, comparison with a reference, and comprehensive determination of the queries similarity rate. The scientific novelty is the improvement of the method for the student's SQL query analysis during intelligent computer training in SQL query composition.


Introduction
In the recent decades information technology (IT) significantly transformed the environment of human life. They are currently used as a main tool for the information and knowledge processing [1,2].
In such conditions high-quality IT training is required in the different domains. An integral part of most complex IT systems are relational databases (RDB) and algorithms for data manipulation based on the Structured Query Language SQL. However, the traditional learning of SQL, similar to many other complex domains in terms of group studying, usually does not result in the required quality training of each student. The main issue is the complexity of the adaptive approach providing by the tutor in the case of multiple students task individual solving [3]. Such approach has to take onto account difference in skills and working pace of students, as well as limitation of human tutor cognitive abilities.
According to many researchers [4][5][6][7][8][9]12] the solution can be found in designing and implementing com-puter tutoring programs which have large computational power and advanced intelligent skills.
The most famous ITS for learning SQL is the SQL-Tutor system [6,7], developed at the University of Canterbury, New Zealand. Each task in it consists of a data model and information needed to be obtained. Students write SQL queries by filling out forms. After request completion, SQT-Tutor analyzes student requests to find errors and provides multiple levels of feedback and tips. Students independently choose the level of feedback they wish to receive. After receiving feedback and editing the request, a student can again send it for consideration by the system.
For the purpose of step analysis SQL-Tutor contains many constraints, which includes two parts: a relevance condition and a constraint satisfaction condition. The reaction occurs only if the first condition is met, and the second is not. This means that the constraint is violated and ITS identifies the corresponding feedbacks.
Although the restrictions were conceived by the authors as domain-independent, many of them deal with a correct solution stored in the system. For example, one  A. Chukhray, О. Havrylenko, 2021 of the constraints might check the FROM section of the query to see if the value filled in by the student is equal to the value in the correct solution. The relationship between steps, learning events, and constraints in the system is fairly straightforward. Each constraint meets the competency component.
On the basis of the above principles, other ITS have been developed [10,11].

Formulation of the problem
Despite the repeated presentation in publications by the developments as based on a fundamentally new and effective theory of constraint-based modeling (CBM) [12], in fact, this is not the case, since any restriction can be reduced to the well-known rules "ifthat". A number of restrictions are created for the purpose of syntactic comparison between the only ideal solution and the student's solution. Naturally, these restrictions do not give a chance to alternative solutions that may be more rational than those created by the authors.
An alternative approach, implemented in the form of rules-models of errors, is presented in [13]. It describes 37 classes of the most common semantic mistakes made by students while SQL queries construction.
It is also worth to mention such systems as AsseSQL [14] and SQLator [15] for assessing student requests; SQLify [16] a tool that implements semantic feedback; and also an intelligent computer system teaching SQL from the University of Malaysia [17]. In the latter, the student is limited only by entering data into the fields SELECT, FROM, WHERE, which significantly limits the flexibility of the system. Therefore a new development approach to ITS in SQL is required, combining existing effective techniques with the new methods of the SQL queries analysis and comparison.
To achieve the stated objective following tasks have been formulated and solved: 1. A method of student's SQL queries analysis development.
2. Parsing and syntactic tree building methods development.
3. A method development for two SQL-queries comparison aimed to detect their similarity.

The student's SQL-queries analysis method
Because of the queries presentation redundancy in SQL for any problem more than one correct SQL-query might exist. Hence, it is necessary to verify whether a student's SQL-query fit a certain set of standards for a concrete given task.
In the case of resemblance to one of the reference solutions system identifies the student's solution as known. Each reference query stored in the system is characterized by a set of parameters that determine its quality and, consequently, knowledge and skills of a student. Such parameters, for example, can include performance and required memory capacity, the number of characters in a query that determines the reading and understanding convenience of a request by another person.
If the system does not identify the query as known it could be executed on a real database with multiple data sets. As the result of a data manipulation query is a set of certain tuples all the correct answers must return the same set of data for the same initial data set. Hence with high probability we can conclude that if the query is not known to the sys-tem but on the series of initial data sets output the same set of tuples as the reference solution then this query can be classified as the correct answer.
ITS based upon the described approach works according to the schema presented on fig.1, where high Shigh similarity, low Slow similarity, which is obtained experimentally.
After a new task for student has been generated the program displays the text with the assignments, ER-diagram of the given DB, and a field for student's answer in the form of SQL-query.
Once the answer was confirmed system starts analysis according to the following script: 1. The system estimates similarity rate between the student's answer and reference SQL-queries.
2. Finding similarity rate is compared with some threshold.
3. In the case of high similarity the system operates as follows: 3.1. Lexical and syntactic analysis of SQL-query carries out and a syntax tree is built.
3.2. The parsing tree is compared with the reference syntax tree, which has the highest similarity with the student's query. Every such a model of SQL-query is described by a set of parameters that characterize the quality in several aspects: performance and memory capacity requirements, readability.
3.3. If the system found a mismatch of some nodes of the trees it informs about the error location.
3.4. If the parsing trees are identic the student's answer is considered as correct, and a new task is generated.
4. In the case of low similarity between the student's query and reference queries the system runs both queries on the real database and then compares resulted sets of tuples. 4.2. If the sets of tuples differ, the answer is considered as wrong, and a student has to solve another task from the same topic.

The SQL-queries parsing method
SQL is a language which can be described in Backus-Naur Form (BNF). Its grammar is context-free (CF grammar). It allows developing SQL compiler in this project utilizing the programs LEX/YACC.
The main hypothesis of this paper is that the pedagogically correct feedback can be given by comparing syntax trees of the reference and the student SQLqueries. Fig. 2, 3 show examples of the parsing trees for the reference and student queries. After the trees traversal and nodes comparison the mismatch at one of the nodes has been detected. To make a decision about a necessity of parsing trees traversal system needs information about similarity rate of the student's and reference queries. In this paper advanced q-gram method is proposed for queries similarity rate estimation.
Classical q-gram method. In this method, the original strings are broken into sets of overlapping word forms (q-gram) consisting of q symbols.
For example, in the case q2  : original string: abcdef (Len=6) word forms: ab, bc, cd, de, ef (N=5) in the case q3  : word forms: abc, bcd, cde, def (N=4) Thus the number of q-grams for N strings of length Len , and a given q is described by following formula: Each word form from the first set is compared with each word form from the second set. If the pair coincide, a comparison with the given word form from the second set is no longer produced. The similarity rate of two strings S might be considered as the ratio of C matches to the total number of word forms N : Example 1. Assume that there are two strings representing SQL-queries (Len1 = Len2 = 19): 1) S1 = "SELECT color FROM p"; 2) S2 = "SELECT owner FROM p".
Given sets of word forms match in 17 positions: C(QG 1, QG 2) = 17 . In this case the similarity rate calculated by (2) with the grater word forms number is: The similarity rate based on the smaller word forms number: Method based upon SQL keywords replacement. Any syntactically correct SQL-query contains a limited set of the certain keywords. Since many of the keywords might appear as in a correct query, and in an incorrect query to reduce their impact on the similarity assessment it makes sense to replace such keywords with the corresponding ID. Example 3. Let consider a set of keywords: KW={"SELECT" "FROM" "WHERE"}.
Example 4. Let consider a parsing tree of the SQL-query «SELECT * FROM p WHERE City<>'Paris» (Table 1).
In tab.1: Node contentdescription of syntactic rules; Left index, Right indexindices of array elements for left and right descendants.
In order to distinguish a rule number, a child index and an ordinary numeric value, numbers could be marked with the following prefixes: %rule number; #descendant index; numeric values are stated without any additional marks.
The string obtained for the query: Further, constructed strings are compared by means of the classical q-gram method.
Presented methods for different types of similarity detection tasks give different output values. A promising challenge is to create a neural network and train it on the basis of student query series by giving as the input of the network the similarity values obtained by the three methods, and setting a required similarity rate as the output.

Conclusions
The approach proposed in the article allows providing comparison of the student's answer and reference query more efficiently then it is carried out in existing ITS for SQL.
A new approach to query's presentation in canonical form, as well as a scheme of the self-diagnosing method for the quality improvement of computer training in SQL were obtained.
The further investigations promising way is development of new task adaptive choice algorithms, depending on the current student progress, as well as interactive hints system creation.