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.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-04-02T12:19:53Z No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-04-04T12:11:32Z (GMT) No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Made available in DSpace on 2018-04-04T12:11:32Z (GMT). No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) Previous issue date: 2018-02-23 / A World Wide Web ? uma cole??o de informa??es sempre crescente. Esta informa??o ? distribu?da entre documentos diferentes, disponibilizados atrav?s do HTTP. Mesmo que essa informa??o seja acess?vel aos usu?rios na forma de artigos de not?cias, transmiss?es de ?udio, imagens e v?deos, os agentes de software geralmente n?o podem classific?-la. A falta de informa??es sem?nticas sobre esses documentos em um formato leg?vel por m?quina geralmente faz com que a an?lise seja imprecisa. Um n?mero significativo de entidades adotaram Linked Data como uma forma de adicionar informa??es sem?nticas aos seus dados, e n?o apenas public?-lo na Web. O resultado ? uma cole??o global de dados, chamada Web of Data, que forma um grafo global, composto por declara??es no formato RDF [22] de diversas fontes, cobrindo todos os tipos de t?picos. Para encontrar informa??es espec?ficas nesses grafos, as consultas s?o realizadas come?ando em um sujeito e analisando seus predicados nas instru??es RDF. Esses predicados s?o as conex?es entre o sujeito e o objeto, e um conjunto de trilhas forma um caminho de informa??o. O uso de HTTP como mecanismo padr?o de acesso a dados e RDF como modelo de dados padr?o simplifica o acesso a dados, o que nos motiva a pesquisar alternativas na forma como esses dados s?o buscados. Uma vez que a maioria das linguagens de consulta de banco de dados de grafo est?o na classe de Linguagens Regulares, n?s propomos seguir um caminho diferente e tentar usar uma classe de gram?tica menos restritiva, chamada Gram?tica Livre de Contexto Determin?stica, para aumentar a expressividade das consultas no banco de dados em grafo. Mais especificamente, aplicando o m?todo de an?lise LR(1) para encontrar caminhos em um banco de dados de grafo RDF. O principal objetivo deste trabalho ? prover meios para se permitir a utiliza??o de t?cnicas de reconhecimento de gram?ticas livres de contexto LR(1) para fazer consultas por caminhos formados pelas etiquetas das arestas em um banco de dados RDF. Fornecendo, como um resultado, uma ferramenta que se permita atingir melhor expressividade, efici?ncia e escalabilidade nestas consultas do que o que existe atualmente. Para atingir este objetivo, n?s implementamos um algoritmo baseado nas t?cnicas de reconhecimento LR(1), usando o GSS [30] ao inv?s de uma pilha, e permitimos ao usu?rio fazer consultas com uma gram?tica livre de contexto (LR1). Tamb?m analisamos a complexidade do nosso algoritmo e executamos alguns experimentos, comparando nossa solu??o com as outras propostas na literatura, mostrando que a nossa pode ter melhor desempenho em alguns cen?rios. / The World Wide Web is an always increasing collection of information. This information is spread among different documents, which are made available by using the HTTP. Even though this information is accessible to users in the form of news articles, audio broadcasts, images and videos, software agents often cannot classify it. The lack of semantic information about these documents in a machine-readable format usually makes the analysis inaccurate. A significant number of entities have adopted Linked Data as a way to add semantic information to their data, not just publishing it on the Web. The result is a global data collection, called the Web of Data, which forms a global graph, consisting of RDF [22] statements from numerous sources, covering all sorts of topics. To find specific information in this graph, queries are performed starting at a subject and analyzing their predicates in the RDF statements. These predicates are the connections between the subject and object, and a set of traces forms an information path. The use of HTTP as a standardized data access mechanism and RDF as a standard data model simplifies the data access, but accessing heterogeneous data on distinct locations may have an increased time complexity and current query languages have a reduced query expressiveness, which motivates us to research alternatives in how this data is queried. This reduced expressiveness happens because most query languages belong to the class of Regular Languages. The main goal of this work is to use LR(1) context-free grammar processing techniques to search for context-free paths over RDF graph databases, providing, as result, a tool which allows better expressiveness, efficiency and scalability in such queries than what is proposed today. To achieve that, we implemented an algorithm based on the LR(1) parsing technique that uses the GSS [30] structure instead of a stack, and give means for the user to input queries with an LR(1) context-free grammar. Also, we analyze our algorithm?s complexity and make some experiments, comparing our solution to other proposals present in the literature and show that ours can have better performance in given scenarios.

The search in the source code is gaining more and more space because of the increasing complexity of current software systems and also the need for improvements in source code. Although the paradigms of object-oriented programming and aspect-oriented programming have several features to improve code reuse and clarity when maintenance of code is required, developers tend to reduce productivity because of problems on locating the parts to be corrected or improved. Aiming maintenance activities, this paper presents a search code process that can be applied to source code repositories. This process is exemplified through three instantiations: searches in object-oriented code using SPARQL and SQL, and aspect-oriented code using XML, suggesting that its use may be of great value for any combination of tools and query languages. / As buscas em código-fonte estão ganhando cada vez mais espaço devido ao atual aumento da complexidade dos sistemas de software e também à necessidade de melhorias em código-fonte. Embora os paradigmas de programação orientada a objetos e de programação orientada a aspectos possuam diversos recursos para melhorar o reuso e a clareza de código, quando é necessária manutenção de trechos de código, os programadores tendem a reduzir sua produtividade em função de problemas em localizar os trechos a serem corrigidos ou melhorados. Visando as atividades de manutenção, este trabalho apresenta um processo de consulta que pode ser aplicado em repositórios de código-fonte. Tal processo é exemplificado através de três instanciações: buscas em código orientado a objetos usando SQL e SPARQL, e em código orientado a aspectos usando XML, evidenciando que seu uso poderá ser de grande valia para qualquer combinação entre ferramentas e linguagens de consulta.