Explaining query answers using query reverse engineering

The aim of this thesis is to find ways to discover hidden relations among a set of data extracted from a database. This relation enquiry is helpful to understand if those extracted data have some distinctive characteristics and in particular to highlight if some unethical principles are present. Querying data from databases is very simple and fast. Database management systems (DBMS) allow users to extract data in a very efficient way. They are optimized to lower the latency of a data request and they are designed to allow data security and consistency. Given a query, the database management system analyses data, computes the result and delivers it to the user. Once the user has the result, s/he could be interested in knowing if some valuable relation is present among the elements of the result. In particular, it could be very useful to know if those tuples are related in some way or if some unethical principles, with respect to the rest of the database, are injected in the result. To perform a similar analysis, the user cannot rely on the DBMS since, typically, they do not offer such instruments. We have then decided to develop a tool, called EXPLORER, for EXPLanation Oriented query Reverse EngineeRing, that supports an analysis on sensitive aspects of the data extraction. The input to be given is a group of tuples that could be the result of some known or unknown query. Starting from the result, EXPLORER uses different query reverse engineering methods we have implemented in order to find equivalent queries. This set of equivalent queries highlights the other ways in which the input result can be produced. Following this process, the implicit relations that tuples in the result have can be easily pointed out. These implicit relations, if put together, can produce an explanation. An explanation, as the word says, explains how the result has been obtained or, in other words, why the result is made up of those specific tuples. The natural explanation of a result is of course the query that has initially generated it. However, it can be very valuable to analyse the equivalent queries to know if ethically sensitive relations on data are present. This explanations-providing tool can also be thought as an extension of a DBMS that offers an analysis on query results every time the user is interested in having it. Moreover, the tool can also be used as a simple query reverse engineering method to infer equivalent queries. This allows our method to be useful for several purposes.

In questa tesi studieremo il problema dell'analisi di dati estratti da un database con lo scopo di facilitare l'individuazione di possibili principi non etici presenti tra essi. Ricavare dati da un database utilizzando delle query è molto semplice e veloce. I sistemi di gestione di database (DBMS da database management systems) permettono all'utente di estrarre dati in modo molto efficiente. Sono ottimizzati per diminuire la latenza di una richiesta e sono progettati per offrire un'ottimale sicurezza e consistenza dei dati. Data una query, il DBMS analizza i dati contenuti nel database, calcola il risultato e lo fornisce all'utente. Una volta ottenuti i risultati, l'utente potrebbe volerli analizzare per scoprire se qualche particolare relazione è presente tra essi. Nello specifico, potrebbe risultare molto utile conoscere se le tuple del risultato sono univocamente individuabili rispetto al resto del database, oppure se nel risultato è nascosto qualche principio non etico. Per fare ciò, l'utente non può affidarsi ai DBMS poiché, tipicamente, questi non offrono strumenti in grado di fare tale analisi. Il nostro lavoro consiste nello sviluppo di uno strumento chiamato EXPLORER (per EXPLanation Oriented query Reverse EngineeRing) che supporta un'analisi dei dati volta a scoprire eventuali relazioni riguardanti aspetti eticamente sensibili. L'input che viene fornito è un insieme di tuple risultante dall'esecuzione di una certa query, che sia essa conosciuta o meno. Partendo dal risultato di tale query, EXPLORER utilizza diversi metodi di query reverse engineering per trovare query equivalenti che restituiscano l'insieme di tuple in input. Il set di query equivalenti evidenzia i vari modi in cui il risultato in input può essere prodotto. Seguendo questo processo, risulta più semplice trovare le relazioni implicite presenti tra le tuple. Queste relazioni, se considerate collettivamente, possono produrre una explanation. Una explanation spiega come sono stati ottenuti i risultati oppure, in altre parole, spiega il motivo per cui il risultato contiene quelle specifiche tuple. La più scontata explanation di un risultato è ovviamente la query che lo ha generato inizialmente. Tuttavia, può essere molto interessante analizzare le query equivalenti per capire se è presente tra i dati qualche aspetto eticamente rilevante. EXPLORER può essere anche visto come uno strumento che estende le funzionalità del DBMS offrendo la possibilità di analizzare i risultati delle query ogni volta che un utente ne è interessato. Inoltre, può essere utilizzato come metodo di query reverse engineering per trovare query equivalenti. Questo rende EXPLORER uno strumento estremamente versatile.