Dissertação
{en_GB= SQUARES : A SQL Synthesizer Using Query Reverse Engineering} {} EVALUATED
{pt=Actualmente, com a enorme quantidade de dados com que os analistas de dados precisam de lidar diariamente, estes frequentemente encontram tabelas com dados interessantes e não sabem como estas tabelas foram geradas. Deste modo, há uma necessidade crescente de sistemas capazes de resolver o problema de Engenharia Reversa de Consultas (ERC, Query Reverse Engineering da literatura inglesa). Dada uma base de dados D e uma tabela de saída Q(D), estes sistemas precisam encontrar uma consulta Q, de modo que, ao executar Q em D, o resultado é igual a Q(D). ERC pertence à área de Síntese de Programas. O objetivo da área de Síntese de Programas é gerar automaticamente programas que atendem a uma determinada especificação de alto nível. Desde os anos 60, Síntese de Programas é um problema bem estudado e tem sido considerado o Santo Graal da Ciência da Computação. Até agora, os sintetizadores de programas usavam uma única árvore para representar programas. Neste trabalho propomos um novo sintetizador de SQL baseado em enumeração, SQUARES, que usa uma nova representação por linhas na qual cada linha do programa é representada pela sua própria subárvore. Resultados experimentais na síntese de consultas SQL mostram que a codificação proposta baseada em linhas permite uma enumeração mais rápida de programas quando comparada à codificação usual baseada em árvore e permite encontrar programas com uma sequência maior de operações. Resultados experimentais na síntese de consultas SQL da OutSystems mostram que o SQUARES supera o Scythe, um sintetizador de SQL de última geração., en=Nowadays, with the massive amount of data that data analysts have to deal with, they frequently find tables with interesting data and they do not know how these tables were generated from a database. Hence, there is an increasing need for systems capable of solving the problem of Query Reverse Engineering (QRE). Given a database D and an output table Q(D), these systems have to find a query Q, such that, when running Q on D, the result is equal to Q(D). QRE is a subfield of Program Synthesis. The goal of Program Synthesis is to automatically generate programs that satisfy a given high-level specification. Since the 60's, Program Synthesis is a well studied problem, and has been considered the Holy Grail of Computer Science. Until now, program synthesizers have been using a single tree representation to represent programs. We propose a novel enumeration-based SQL synthesizer SQUARES, that uses a new line representation where we represent each program line with its own subtree. Experimental results on the synthesis of SQL queries, show that the proposed line-based encoding allows a faster enumeration of programs when compared to the usual tree-based encoding. Moreover, while the tree-based encoding does not scale beyond a small number of operations, the new line-based encoding allows finding programs with a larger sequence of operations. Experimental results on the synthesis of SQL queries from OutSystems show that SQUARES outperforms Scythe, a state-of-the-art SQL synthesizer.}
Novembro 15, 2019, 14:30
Orientação
ORIENTADOR
Vasco Miguel Gomes Nunes Manquinho
Departamento de Engenharia Informática (DEI)
Professor Associado
