Tese

Storage and Navigation Operations on Graphs in Relational DBMS (2021)

• Authors:
  • Scabora, Lucas de Carvalho
  • Traina Junior, Caetano (Orientador)
• Autor USP: SCABORA, LUCAS DE CARVALHO - ICMC
• Unidade: ICMC
• Sigla do Departamento: SCC
• Subjects: REDES COMPLEXAS; BANCO DE DADOS RELACIONAIS; DADOS CINÉTICOS; ANÁLISE DE DADOS; MODELAGEM DE DADOS
• Keywords: Abordagens de armazenamento em listas de adjacências; Adjacency-list storage approaches; Consultas em grafos; Consultas recursivas; Graph queries; RDBMS; Recursive queries; SGBDR
• Agências de fomento:
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
    Processo FAPESP: 2016/17330-1,2016/17078-0,e2020/07200-9
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
• Language: Inglês
• Abstract: 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 propostasespecializaçõ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.
• Imprenta:
  • Publisher place: São Carlos
  • Date published: 2021
• Data da defesa: 07.05.2021


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  SCABORA, Lucas de Carvalho. Storage and Navigation Operations on Graphs in Relational DBMS. 2021. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-26052021-125443/. Acesso em: 26 abr. 2024.

• APA

  Scabora, L. de C. (2021). Storage and Navigation Operations on Graphs in Relational DBMS (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-26052021-125443/

• NLM

  Scabora L de C. Storage and Navigation Operations on Graphs in Relational DBMS [Internet]. 2021 ;[citado 2024 abr. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-26052021-125443/

• Vancouver

  Scabora L de C. Storage and Navigation Operations on Graphs in Relational DBMS [Internet]. 2021 ;[citado 2024 abr. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-26052021-125443/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Avaliação do Star Schema Benchmark aplicado a bancos de dados NoSQL distribuídos e orientados a colunas
• Augmentation techniques for sequential clinical data to improve deep learning prediction techniques
• APEHR: automated prognosis in electronic health records using multi-head self-attention
• Efficient indexing of multiple metric spaces with spectra
• UCORM: indexing uncorrelated metric spaces for concise content-based retrieval of medical images
• Enhancing recursive graph querying on RDBMS with data clustering approaches
• Segmenting skin ulcers and measuring the wound area using deep convolutional networks
• SHARq: sharing recursive queries in relational databases
• FeatSet: a compilation of visual features extracted from public image datasets
• FeatSet+: visual features extracted from public image datasets