Avanços científicos estão cada vez mais sendo alcançados através de conjuntos complexos de cálculos e análises de dados, que podem compreender milhares de atividades encadeadas e representadas por meio de workflows científicos. Um workflow pode ser executado inúmeras vezes, sendo que os dados de proveniência destas execuções são uma fonte de informação cada vez mais relevante, além de um componente crucial para os Sistemas Gerência de Workflows Científicos (SGWfC). Vários sistemas que lidam com dados de proveniência os armazenam em Bancos de Dados Relacionais (BDR). No entanto, estes dados são naturalmente modelados como grafos direcionados acíclicos, o que faz parecer que a utilização de Bancos de Dados de Grafos (BDG) para sua gerência seria mais adequada. Esta dissertação tem como objetivo investigar, considerando diferentes cenários, qual das alternativas para gerência de dados de proveniência é a melhor, avaliando principalmente o desempenho de execuções de consultas típicas de proveniência. Além de comparar o desempenho, realizou-se uma análise em termos de uso de processador e memória, bem como do espaço ocupado em disco por cada base experimental. Nenhuma solução foi superior em todos os aspectos testados, porém, em termos gerais, o BDG superou o BDR.