Dissertação

{en_GB=Database Partitioning via Symbolic Execution} {} EVALUATED

{pt=As bases de dados são uma peça fundamental para qualquer sistema que necessite de guardar dados de forma persistente. Com a emergência de sistemas de larga escala, as bases de dados que os suportam necessitam de abordar todas as questões de escalabilidade inerentes. Em particular, não é possível replicar os dados em todas as réplicas que constituem um sistema, sendo necessário distribuir os dados entre as réplicas, surgindo assim o particionamento de dados Trabalhos de investigação anteriores nesta área requerem extratos de execução do sistema para adquirir informação referente aos dados processados de forma a conseguir particionar os dados. Este trabalho sugere utilizar execução simbólica com o intuito de alcançar um esquema de particionamento de dados ideal. Com este objetivo em vista, formulamos o problema como um problema de particionamento de um grafo que utiliza a informação obtida durante a análise simbólica. Depois de resolver o problema de particionamento de um grafo, aplicamos o esquema de particionamento resultante â base de dados por forma a obter partições ideias de acordo com a nossa formulação do problema. Os resultados obtidos para o benchmark TPC-C são bastante satisfatórios tendo em consta que estão de acordo com a melhor solução conhecida para este benchmark., en=Databases are a fundamental piece of the jigsaw behind any system that requires persistent storage. With the emergence of large scale database systems, it is necessary to address all the scalability issues that come with them. In particular, it is not possible to fully replicate every data item across every single replica in a system hence the need for data partitioning. Previous work in this area relies on execution traces and prior knowledge of the data being processed in order to perform data partitioning. In this work, we propose to leverage Symbolic Execution to replace these techniques and explore symbolic formulas to reach an optimal data partitioning scheme. In order to achieve this, we formulate a graph partitioning problem that leverages all the information obtained during symbolic analysis. After obtaining the partitioning scheme from a graph partitioner, we apply it to the database in order to achieve optimized partitions according to our formulation. The experimental results obtained for the TPC-C benchmark are very satisfying as they are aligned with what is known to be the best partitioning scheme.}
{pt=bases de dados, particionamento de dados, execução simbólica, particionamento de grafos, en=database, data partitioning, symbolic execution, graph partitioning}

Janeiro 27, 2021, 13:0

Orientação

ORIENTADOR

Miguel Ângelo Marques de Matos

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Paolo Romano

Departamento de Engenharia Informática (DEI)

Professor Associado