Fundamentos das Linguagens de Consulta Modernas para Bancos de Dados em Grafo

Nós analisamos as características fundamentais que sustentam as linguagens de consulta em grafo modernas. Primeiro, discutimos dois modelos de dados em grafo populares: grafos com rótulos em arestas, onde os nós são conectados por arestas dirigidas e rotuladas, e grafos de propriedades, onde nós e arestas podem ter atributos adicionais. Em seguida, discutimos as duas funcionalidades de consulta em grafo mais fundamentais: padrões de grafo e expressões de navegação. Começamos com padrões de grafo, nos quais uma consulta estruturada em grafo é comparada aos dados. Depois, discutimos expressões de navegação, nas quais os padrões podem ser correspondidos recursivamente contra o grafo para navegar por caminhos de comprimento arbitrário; fazemos uma visão geral dos tipos de expressões que foram propostas e como elas podem ser combinadas com padrões de grafo. Também discutimos várias semânticas sob as quais consultas usando os recursos anteriores podem ser avaliadas, quais efeitos a seleção de recursos e semânticas tem sobre a complexidade, e oferecemos exemplos de tais recursos em três linguagens modernas que são usadas para consultar grafos: SPARQL, Cypher e Gremlin. Concluímos discutindo a importância da formalização para linguagens de consulta em grafo; um resumo do que se sabe sobre SPARQL, Cypher e Gremlin em termos de expressividade e complexidade; e um esboço de possíveis direções futuras para a área.