Técnicas para Alocação de Fragmentos em Projeto de Bancos de Dados Distribuídos
Autores
|
4693 |
893,51,2081
|
|
|
4694 |
893,51,2081
|
|
|
4695 |
893,51,2081
|
Informações:
Publicações do PESC
Um projeto de distribuição de bancos de dados visa obter fragmentos da base de dados e alocá-10s dentre os nós do sistema distribuído. O objetivo do projeto de alocação é associar fragmentos aros pontos de acesso relevantes e com isso tornar o custo de execução o menor possível. Para isso o projeto de alocação também pode sugerir o uso de réplicas. Devido às dificuldades em modelar o custo de execução e o enorme espaço de soluções, este é um problema caracterizado como NP-Completo. Esta dissertação propõe dois algoritmos, Aloc e GRADA, para alocação de fragmentos em sistemas de banco de dados distribuídos. Aloc é um algoritmo heurístico baseado num algoritmo eficiente da literatura com mesma ordem de complexidade, enquanto GRADA é um algoritmo baseado na meta-heurística GRASP. Foram executados diversos experimentos, que se utilizaram de um modelo de custo validado experimentalmente com aplicações de pequeno e grande porte (onde utilizamos a especificação do benchmark TPC-C). Nos experimentos realizados identificaram-se situações em que o algoritmo Aloc conseguiu atingir a, solução ótima ou reduzir o custo final do esquema de alocação em relação ao algoritmo da literatura, especialmente em cenários de atualização intensiva. O algoritmo GRADA apresentou resultados melhores que o algoritmo Aloc em situações com maior número de nós na rede e/ou uma quantidade menor de transações de atualização, obtendo resultados semelhantes aos resultados alcançados pelo algoritmo Aloc nos demais casos.
The distributed database design aims at obtaining fragments of the database and allocating fragments among the sites of the distributed system. The goal of the distributed database design is to associate fragments to the most adequate network nodes, thus minimizing the application execution cost. Tlie fragment allocation problem also includes decisions about fragment replication. Due to the number of parameters for the problem, and to the number of possible solutions in tlie search space, the allocation problem is considered in tlie literature as a NP-Complete problem. In this work, two algorithms are proposed for fragment allocation in distributed database systems: Aloc and GRADA. Aloc is a heuristic algorithm based on another algorithni from the literature that produced good results. Aloc maintains tlie complexity of the original algorithm. GRADA is an algorithm based on the GRASP meta-heuristic. Through simulations perfoimed on top of the TPC-C benchmark, it was possible to identify scenarios wliere the Aloc algorithm found the optimal solution and other scenarios where Aloc fouiid allocation schema with a reduced cost when compared to the original algorithni. The GRADA algorithm obtained better results than the Aloc algorithm in scenarios with a large number of sites (where the number of alternative solutions considered is very large) and in scenarios with lower update traiisaction rates. In other cases, the GRADA algorithm obtained the same results as the Aloc algorithni.