Assessing query fairness using query reverse engineering

Today the generated amount of data is growing at an unprecedented rate, therefore a way to organize it is badly needed and the databases, which are organized collections of structured data, have become fundamental for the management and the storage of this large quantity of information. Such data are often analyzed to extract information used to take critical decisions, for example staff evaluation, school admission, rewards assignment, criminal sentencing... It is therefore necessary to ensure that data processing respects ethical and legal principles, such as fairness, non-discrimination and transparency. For this purpose, this thesis describes a possible way to analyse a dataset in such a way as to allow to check if ethical requirements are fulfilled. Access to organized data is usually provided by a DBMS (DataBase Management System), which allows users to interact with the databases in an efficient way by writing queries in specific languages. The query is given as input in the DBMS, which analyses the data and computes the result. Query Reverse Engineering (QRE) makes the reverse process, i.e. it allows to find the input query given a set of output tuples (records). This thesis describes the program that I developed and tested, which combines different QRE methods and retrieves many equivalent input queries. Finding the input queries means to look for implicit relations among data, and these relations can support the detection of the violation of some ethical principles. So, the users can check if one of the retrieved input queries is unethical; in fact, it could happen that an ethical query is equivalent, i.e. returns the same set of tuples, to an unethical one.

La quantità di dati generata ogni giorno sta crescendo ad una velocità inaudita; nasce quindi la necessità di organizzarli e i database, ossia collezioni di dati strutturati, sono diventati fondamentali per la gestione e l'archiviazione di grandi quantità di informazioni. Tali dati vengono spesso analizzati per ricavare ulteriori informazioni con cui vengono poi prese decisioni critiche, per esempio la valutazione dei dipendenti, l'ammissione degli studenti nelle scuole, l'assegnazione di ricompense e borse di studio, le condanne penali... Diventa quindi necessario garantire che i processi di elaborazione dei dati rispettino dei principi etici e legali, quali correttezza, non discriminazione e trasparenza. A tal fine, questa tesi si propone di descrivere un modo per analizzare un insieme di dati per verificare se la loro estrazione da un determinato database è stata effettuata violando qualche principio etico. I sistemi di gestione dei database (DBMS) consentono la manipolazione e l'estrazione di dati in modo efficiente utilizzando delle query: la query viene fornita al DBMS, il quale analizza i dati e calcola il risultato. Query Reverse Engineering (QRE) effettua il processo inverso, cioè, partendo da un insieme di dati, trova la query iniziale. In questa tesi viene descritto il programma che ho implementato e testato, il quale combina diversi metodi di QRE per trovare molte query iniziali equivalenti. Trovare le query di partenza significa anche cercare delle relazioni implicite tra i dati, relazioni che possono rivelare la presenza di qualche violazione dei principi etici. Gli utenti possono controllare se tra le query trovate ve ne sia qualcuna non etica; infatti, può capitare che una query etica sia equivalente, cioè fornisca le stesse tuple, ad una non etica.