A complex network models relationships among data elements in several applications, such as social networks, urban street organization, disease monitoring and treatment co-occurrences, and communication and transport infrastructures. To store and manage large volumes of data, the Relational Database Management Systems (RDBMSs) provide efficient disk-based data management, being present in the most diverse application domains, including enterprise information, finance, medical or clinical support, and in airline reservations and scheduling. However, RDBMSs still face challenges to efficiently process queries that navigate over complex networks represented as graphs. Those queries, named in this work as graph queries, are often expressed by recursive queries, which execute multiple join operations between an internal, temporary table that stores intermediary results and the table that stores the graphs edges. This Ph.D. dissertation focuses on developing methods and specialized data structures based on adjacency-lists aiming at improving graph query performance in an RDBMS through recursive queries. This projects main goal targets the question: How can we improve the performance of queries over graph data executed in a RDBMS?. To answer it, we proposed specializations over each table involved in a recursive query: the table of edges E, and the temporary result table T. The modifications in table T consists of adding extra measurement columns to enable employing it in multiple graph queries executed in a single database connection. In its turn, table E is specialized to allow storing multiple edges into a single row optimized for the execution of each join operation of the recursive query. Experiments using data from RDBMSs modeled as a graph allow concluding that: (i) enriching table T provides increased efficiency to execute multiple graph queries, such as the query types Single-Source Shortest Path (SSSP), Connected Components (CC), and PageRank (PR); (ii) grouping multiple edges from table E into a single row significantly improves the performance of individual recursive queries, reducing not only their elapsed time but also the required size to store the graph data; and (iii) employing Clustered Tables to group the edges into a single page also enables improved performance for recursive queries, with the advantage of requiring just a few changes in the SQL statements. Overall, specializing both tables T and E helps diminishing the gap of efficiently executing graph queries in a RDBMS

Uma rede complexa modela a inter-relação entre elementos nas mais diversas aplicações, tais como redes sociais, organização de ruas em regiões urbanas, monitoramento de doenças e co-ocorrência de tratamentos e infraestruturas de comunicação e de transporte. Para armazenar e gerenciar grandes volumes de dados, os Sistemas Gerenciadores de Bases de Dados Relacionais (SGBDRs) proporcionam um eficiente gerenciamento dos dados em disco, estando presente nos mais diversos domínios de aplicação, incluindo o gerenciamento de informações corporativas, de finanças, suporte médico ou clínico, e em reservas e agendamento de passagens aéreas. Entretanto, os SGBDRs ainda enfrentam desafios para processar eficientemente consultas para navegar em redes complexas representadas por grafos. Essas consultas, chamadas neste trabalho de consultas em grafos, são frequentemente expressas por meio de consultas recursivas, as quais realizam várias operações de junção entre uma tabela temporária interna que armazena resultados intermediários e a tabela que armazena as arestas do grafo. Esta tese de doutorado foca no desenvolvimento de métodos e de estruturas de dados especializadas baseadas em listas de adjacência com o objetivo de melhorar o desempenho de consultas em grafos em um SGBDR através de consultas recursivas. O objetivo principal deste projeto visa a questão: Como podemos melhorar o desempenho de consultas sobre dados de grafos executados em um SGBDR? . Para respondê-la, foram propostas especializações em cada uma das tabelas envolvidas na consulta recursiva: a tabela de arestas E e a tabela de resultados T. As modificações na tabela T consistem em adicionar colunas de medida extras para permitir sua utilização em múltiplas consultas em grafos executadas em uma única conexão de banco de dados. Por sua vez, a tabela E é especializada para permitir o armazenamento de múltiplas arestas em uma única linha otimizada para a execução de cada operação de junção da consulta recursiva. Experimentos usando dados de SGBDRs modelados como grafos permitem concluir que: (i) enriquecer a tabela T melhora a eficiência para executar várias consultas em grafo, como os tipos de consulta Single-Source Shortest Path (SSSP), Componentes Conexas (CC) e PageRank (PR); (ii) agrupar as arestas da tabela E em uma única linha melhora significativamente o desempenho de consultas recursivas individualmente, reduzindo não apenas o tempo decorrido, mas também o tamanho necessário em disco para armazenar os dados do grafo; e (iii) utilizar tabelas clusterizadas para agrupar as arestas em uma única página de disco também melhora desempenho para consultas recursivas, com a vantagem de exigir poucas alterações nas instruções SQL. No geral, especializar as tabelas T e E ajuda a reduzir a lacuna de execução eficiente de consultas em grafo em um SGBDR.