Implementazione dell'algoritmo TALOS per il reverse engineering di Query SPJ

The paper presents a list of the various methods based on examples for relational data, focusing in particular on the problem of the exact reverse engineering of queries. Later, TALOS is presented, an algorithm for the Reverse Engineering of Query SPJ proposed by Quoc Trung Tran, Chee-Yong Chan and Srinivasan Parthasarathy which aims to improve the usability of even very complex databases by non-expert users. The algorithm takes the result of a query on a database and generates an alternative query that is instance-equivalent of the one supplied by the user. Basically TALOS to get to a result must find 3 components: relationship, projection and selection. The last is the most complicated component to identify and we make use of a classifier, specifically a decision tree-classifier based on the Gini index. Finally, an attempt is made to implement a basic version of the aforementioned algorithm and provides an example of its operation.

L’elaborato presenta un elenco dei vari metodi basati su esempi per dati relazionali, soffermandosi in modo particolare sul problema del reverse engineering esatto di query. In seguito, si presenta TALOS, un algoritmo per il Reverse Engineering di Query SPJ proposto da Quoc Trung Tran, Chee-Yong Chan e Srinivasan Parthasarathy che mira a migliorare l’usabilità di database anche molto complessi da parte di utenti non esperti. L’algoritmo prende in ingresso il risultato di una query su un database e genera una query alternativa che è instance-equivalent di quella fornita dall’utente. Fondamentalmente TALOS per arrivare a un risultato deve trovare 3 componenti: relazione, proiezione e selezione. L’ultima è la componente più complicata da identificare e ci si avvale di un classificatore, nello specifico un decision tree-classifier basato sull’indice di Gini. Infine, si mostra un tentativo di implementare una versione base dell’algoritmo sopracitato e se ne fornisce un esempio di funzionamento.