FARIAS, P. M. S. O Problema de ordenação de rodadas e problemas de otimização associados. 2014. 127 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:15:16Z No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:25:51Z (GMT) No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Made available in DSpace on 2015-09-23T16:25:51Z (GMT). No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) Previous issue date: 2013 / This thesis is composed of three well-delineated parts. In the first part, we introduce the round sorting problem (RSP), which models the minimization of the usage of buffer for the temporary storage of packets to be forwarded in TDMA communications of wireless mesh networks. We present a complete foundation for the definition of the RSP, and show that the problem is NP-hard for two theoretical models of radio interference known in the literature. A mixed integer programming formulation is also presented for a purely combinatorial and applicationindependent generalization of the RSP, the SMSP problem. In the second part of the work, we deal with problems about queries on insertions into sequences of numbers. Our main result in this part of the thesis is to show how, after a preprocessing step which runs in linear time on a sequence A of arbitrary real numbers, it is possible to compute in constant time the greatest sum of a (circular or not) contiguous subsequence of the sequence which results from the insertion of a given real number x into a given position p of A. In the third part of the thesis, we use the query algorithms from the second part to obtain an efficient implementation of the GRASP metaheuristic applied to the SMSP problem. An experimental analysis of this implementation is described, in which the values of the solutions returned by the metaheuristic are compared with those of the solutions obtained through the mixed integer formulation, in the case of small instances, and with the available lower bound, in the case of larger instances. / Esta tese é composta de três partes bem-delineadas. Na primeira parte, nós introduzimos o "problema de ordenação de rodadas" (POR), que modela a minimização do uso de memória ("buffer") para o armazenamento temporário de pacotes a serem repassados em comunicações TDMA de redes de rádio em malha. Nós apresentamos uma fundamentação completa para a definição do POR, e mostramos que o problema é NP-difícil para dois modelos teóricos de interferência de rádio conhecidos na literatura. Uma formulação de programação inteira mista é também apresentada para uma generalização puramente combinatória e independente de aplicação do POR, o problema SMSP. Na segunda parte do trabalho, nós abordamos problemas de consulta sobre inserções em sequências de números. O nosso principal resultado nesta parte da tese é mostrar como, após um passo de pré-processamento que executa em tempo linear sobre uma sequência "A" de números reais quaisquer, é possível computar em tempo constante a maior soma de uma subsequência contígua (circular ou não) da sequência que resulta da inserção de dado um número real "x" numa dada posição "p" de "A". Na terceira parte da tese, nós utilizamos os algoritmos de consulta da segunda parte para obter uma implementação eficiente da meta-heurística GRASP aplicada ao problema SMSP. Uma análise experimental dessa implementação é descrita, onde os valores das soluções retornadas pela meta-heurística são comparados com os das soluções obtidas pela formulação inteira mista, no caso de instâncias pequenas, e com o limite inferior disponível, no caso de instâncias maiores.

ARAÚJO, Arlino Henrique Magalhães de. Abordagens para a sintonia de comandos SQL. 2012. 141 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:13:44Z No. of bitstreams: 1 2012_dis_ahmaraujo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:33:40Z (GMT) No. of bitstreams: 1 2012_dis_ahmaraujo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) / Made available in DSpace on 2016-07-13T13:33:40Z (GMT). No. of bitstreams: 1 2012_dis_ahmaraujo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) Previous issue date: 2012 / Sistemas Gerenciadores de Bancos de Dados (SGBDs) permitem especificar comandos, por meio de linguagens declarativas de alto nível, como SQL Structured Query Language), por exemplo, com a finalidade de executar diferentes operações sobre os dados armazenados (consultas, atualizações, inserções e remoções). O otimizador de consultas é o módulo do SGBD responsável por escolher um plano de execução eficiente para cada comando SQL a ser executado. Para este propósito, os otimizadores procuram, em um grande espaço de busca, o plano de execução que proporcione o menor tempo de resposta. Dois comandos SQL são considerados equivalentes se retornarem os mesmos resultados. Uma vez que a sintaxe de um comando SQL influencia a escolha do plano de execução, o otimizador pode produzir planos de execução distintos para comandos SQL equivalentes. Consequentemente, comandos SQL equivalentes podem apresentar tempos de resposta diferentes. Este fato decorre das operações utilizadas em cada comando SQL (ordenações, agregações, remoção da valores duplicados, utilização de tabelas temporárias, subconsultas, dentre outras). Neste cenário, mesmo usando métodos de acesso e estratégias de avaliaçãao suportadas pelo SGBD, às vezes, os otimizadores não conseguem produzir planos ótimos. Nestes casos, deve ser realizado o ajuste (ou sintonia) do comando SQL. Para isso, em geral, duas estratégias são frequentemente utilizadas: (a) reescrever o comando SQL; e (b) aplicar Query Hinting. A técnica de reescrita consiste em escrever um novo comando SQL, equivalente ao comando SQL original, mas que apresente um tempo de resposta menor. Entretanto, o processo de reescrita de comandos SQL écomplexo e requer bastante conhecimento em diferentes áreas, tais como: (i) otimização de consultas, execução de operadores de planos de consultas, configuração de parâmetros e outros aspectos internos dos bancos de dados; (ii) identificação de índices necessários e outras e’struturas de acesso; (iii) manutenção de estatísticas sobre os dados; e (iv) características dos sistemas de armazenamento de dados. Este trabalho propõe duas abordagens distintas para suportar a reescrita de comandos SQL em bancos de dados relacionais: uma abordagem assistida e outra automática. As duas abordagens propostas utilizam um conjunto de heurísticas para realizar a reescrita dos comandos SQL. As heurísticas são constituídas de regras que visam identificar oportunidades de sintonia nos comandos SQL. Com o objetivo de avaliar a eficiência das abordagens propostas uma avaliação experimental foi realizada. Os experimentos foram conduzidos em trs diferentes cenários: i) com o benchmark TPC-H, ii) com a base de dados do TPC-H e uma carga de trabalho sintética e iii) com a base de dados do sistema SIG e uma carga de trabalho sintética. Para cada cenário, três SGBDs foram avaliados: PostgreSQL, Oracle e SQL Server. Os resultados dos testes realizados mostram que tanto a abordagem assistida quanto a automática proporcionaram ganhos de desempenho, reduzindo o tempo de resposta das cargas de trabalho avaliadas.

ARAÚJO, Arlino Henrique Magalhães de. Abordagens para a sintonia de comandos SQL. 2012. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-31T20:05:00Z No. of bitstreams: 1 2012_dis_ahmaraújo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-31T20:05:12Z (GMT) No. of bitstreams: 1 2012_dis_ahmaraújo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) / Made available in DSpace on 2016-05-31T20:05:12Z (GMT). No. of bitstreams: 1 2012_dis_ahmaraújo.pdf: 3845909 bytes, checksum: a4d10d94371f6556e25effa5d9afd13a (MD5) Previous issue date: 2012 / Sistemas Gerenciadores de Bancos de Dados (SGBDs) permitem especificar comandos, por meio de linguagens declarativas de alto nível, como SQL Structured Query Language), por exemplo, com a finalidade de executar diferentes operações sobre os dados armazenados (consultas, atualizações, inserções e remoções). O otimizador de consultas é o módulo do SGBD responsável por escolher um plano de execução eficiente para cada comando SQL a ser executado. Para este propósito, os otimizadores procuram, em um grande espaço de busca, o plano de execução que proporcione o menor tempo de resposta. Dois comandos SQL são considerados equivalentes se retornarem os mesmos resultados. Uma vez que a sintaxe de um comando SQL influencia a escolha do plano de execução, o otimizador pode produzir planos de execução distintos para comandos SQL equivalentes. Consequentemente, comandos SQL equivalentes podem apresentar tempos de resposta diferentes. Este fato decorre das operações utilizadas em cada comando SQL (ordenações, agregações, remoção da valores duplicados, utilização de tabelas temporárias, subconsultas, dentre outras). Neste cenário, mesmo usando métodos de acesso e estratégias de avaliaçãao suportadas pelo SGBD, às vezes, os otimizadores não conseguem produzir planos ótimos. Nestes casos, deve ser realizado o ajuste (ou sintonia) do comando SQL. Para isso, em geral, duas estratégias são frequentemente utilizadas: (a) reescrever o comando SQL; e (b) aplicar Query Hinting. A técnica de reescrita consiste em escrever um novo comando SQL, equivalente ao comando SQL original, mas que apresente um tempo de resposta menor. Entretanto, o processo de reescrita de comandos SQL écomplexo e requer bastante conhecimento em diferentes áreas, tais como: (i) otimização de consultas, execução de operadores de planos de consultas, configuração de parâmetros e outros aspectos internos dos bancos de dados; (ii) identificação de índices necessários e outras e’struturas de acesso; (iii) manutenção de estatísticas sobre os dados; e (iv) características dos sistemas de armazenamento de dados. Este trabalho propõe duas abordagens distintas para suportar a reescrita de comandos SQL em bancos de dados relacionais: uma abordagem assistida e outra automática. As duas abordagens propostas utilizam um conjunto de heurísticas para realizar a reescrita dos comandos SQL. As heurísticas são constituídas de regras que visam identificar oportunidades de sintonia nos comandos SQL. Com o objetivo de avaliar a eficiência das abordagens propostas uma avaliação experimental foi realizada. Os experimentos foram conduzidos em trs diferentes cenários: i) com o benchmark TPC-H, ii) com a base de dados do TPC-H e uma carga de trabalho sintética e iii) com a base de dados do sistema SIG e uma carga de trabalho sintética. Para cada cenário, três SGBDs foram avaliados: PostgreSQL, Oracle e SQL Server. Os resultados dos testes realizados mostram que tanto a abordagem assistida quanto a automática proporcionaram ganhos de desempenho, reduzindo o tempo de resposta das cargas de trabalho avaliadas.

OLIVEIRA, Henrique Viana. Refinamento de Consultas em Lógicas de Descrição Utilizando Teoria dos Rough Sets. 2012. 111 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:23:02Z No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:23:47Z (GMT) No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) / Made available in DSpace on 2016-07-01T17:23:47Z (GMT). No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) Previous issue date: 2012 / Query Refinement consists of methods that modify the terms of a consult aiming the change of its result obtained previously. Refinements can be done of several ways and different approaches can be applied to it. This work proposes to apply methods of Query Refinement based on Rough Set theory, using it as an alternative for the refinement problem. The proposed methods will be grounded in the languages of Description Logics, which are commonly used on problems involving knowledge bases or ontologies representation. Two extensions of Description Logics with the Rough Set theory are introduced in this dissertation. We will prove the complexity of satisfiability of these logics, as well as the complexities of the query refinement methods applied to these logics. Finally, we will show quality measures which will aid to choose the results of the refinements obtained. / Refinamento de consulta consiste de técnicas que modificam os termos de uma consulta com o objetivo de alterar os resultados obtidos inicialmente. Para a realização de tal fim, diversas abordagens podem ser aplicadas e diferentes tipos de refinamentos podem ser considerados. Este trabalho propõe aplicar a teoria dos Rough Sets como uma nova alternativa de solução para o problema. Através das noções presentes nessa teoria, iremos desenvolver técnicas que serão aplicadas nas linguagens de Lógicas de Descrição, que são comumente utilizadas em problemas de representação de bases de conhecimento ou ontologias. Além disso, introduziremos duas extensões de Lógicas de Descrição capazes de representar as operações da teoria dos Rough Sets. Provaremos os resultados de complexidade de decisão dessas duas lógicas, assim como os resultados de complexidade das técnicas de refinamentos desenvolvidas. Por fim, mostraremos métricas de qualidade que poderão ser usadas para melhorar o resultado dos refinamentos obtidos.