M.Sc Thesis

M.Sc StudentBorodin Gregory
SubjectEfficient Query Recommendation
DepartmentDepartment of Computer Science
Supervisors PROF. Shaul Markovitch
DR. Yaron Kanza


In large organizations, frequently the database has a large and intricate schema, hence, formulating queries is cumbersome. In such organizations, users can benefit from finding relevant queries in the query log of the database - queries that can serve as an initial example for query formulation, or queries that were written by experts and elucidate how to write the query in an optimized manner. In this work we describe a recommendation system that assists users by providing a query search capability over a repository of SQL queries. We distinguish between two types of search - semantic search and syntactic search. In semantic search, queries are deemed similar if they were written for the same task. In syntactic search, queries are considered similar if their formulation looks syntactically similar, to an ordinary user. In this work we illustrate these two types of similarity and the differences between them. We developed accurate methods for testing each type of similarity between given queries, and two additional less accurate but more efficient methods, which we use to improve the performance of the search. We present these methods and we provide an experimental evaluation that demonstrates the effectiveness of our methods. Finally, we demonstrate a recommendation system that assists users finding queries that are similar to a given user query, under each one of the two search semantics. In addition, the recommendation system allows searching for queries from scratch, where the search specifications are the syntactic fragments of the queries or the results of the queries that they yield on generated database samples.