Resumo Técnico: PathFinder: Retornando Caminhos em Consultas de Grafos

Declaração do Problema

As linguagens modernas de consulta de grafos, incluindo SPARQL, Cypher, SQL/PGQ e o emergente padrão GQL, dependem fortemente de consultas de caminho. Embora o SPARQL suporte Regular Path Queries (RPQs) para identificar pares de nós conectados por caminhos que correspondem a uma expressão regular, ele retorna apenas os pontos finais. Em contraste, o Cypher, SQL/PGQ e GQL permitem que os usuários retornem o caminho inteiro (testemunhas) que satisfaz essas consultas.

No entanto, existe uma lacuna significativa entre as capacidades teóricas dessas linguagens e sua implementação prática. Os atuais motores de banco de dados de grafos carecem de suporte abrangente para retornar caminhos sob todo o espectro dos 27 modos de caminho definidos pelos padrões GQL e SQL/PGQ. Esses modos incluem várias restrições (ex: WALK, TRAIL, SIMPLE, ACYCLIC) e seletores (ex: ANY, ALL SHORTEST, SHORTEST k, SHORTEST k GROUPS). Motores existentes:

1. Suportam todas as RPQs, mas não conseguem retornar caminhos (motores SPARQL).
2. Podem retornar caminhos, mas apenas para um subconjunto limitado de expressões regulares ou modos de caminho (motores de propriedade de grafo como Neo4j, Kuzu, Nebula).
3. Sofrem com problemas de escalabilidade, frequentemente falhando ao lidar com consultas de caminho de forma eficiente devido ao potencial de um número exponencial de caminhos correspondentes.

Além disso, embora a complexidade teórica de encontrar caminhos simples ou trilhas seja conhecida como NP-completa, as implementações práticas muitas vezes lutam para fornecer desempenho estável mesmo para consultas teoricamente intratáveis em dados do mundo real.

Metodologia

O artigo apresenta o PATHFINDER, um framework unificado para avaliar RPQs e retornar camros sob todos os 27 modos de caminho do GQL. O núcleo da abordagem baseia-se na construção do grafo produto, combinando o banco de dados de grafo de entrada $G$ com um autômato finito não-determinístico (NFA) $A$ derivado da expressão regular da consulta.

Princípios Algorítmicos Principais

1. Construção do Grafo Produto: O framework constrói um grafo produto $G \times A$ onde os nós são pares $(v, q)$ representando um nó $v$ no grafo e um estado $q$ no autômato. As arestas no grafo produto correspondem a transições no autômato que coincidem com os rótulos das arestas no grafo.
2. Construção Preguiçosa (Lazy Construction): O grafo produto é construído de forma preguiçosa, o que significa que apenas as partes necessárias são geradas para avaliar a consulta, permitindo uma execução em pipeline onde os resultados são retornados assim que detectados.
3. Representação de Multiconjunto de Caminhos (PMR): Os algoritmos mantêm uma representação compacta de todos os caminhos correspondentes usando estados de busca. Um estado de busca normalmente inclui o nó atual, o estado do autômato, a profundidade e ponteiros para estados predecessores, permitindo a reconstrução de caminhos sem armazená-los explicitamente durante a busca.

Algoritmos Específicos para Modos de Caminho

O artigo detalha adaptações específicas da busca no grafo produto para diferentes modos de caminho:

• Modos WALK (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS):

  • ANY/ANY SHORTEST: Utiliza BFS ou DFS padrão no grafo produto. Para lidar com o não-determinismo e garantir um único caminho por par de pontos finais, o algoritmo rastreia estados visitados $(n, q)$ e utiliza um conjunto ReachedFinal para evitar retornos duplicados.
  • ALL SHORTEST: Estende o BFS para rastrear todos os caminhos mais curtos para um nó. O estado de busca inclui uma lista de ponteiros (prevList) para todos os predecessores que resultam em um caminho mais curto, permitindo a enumeração de múltiplos caminhos curtos.
  • SHORTEST k / ANY k: Rastreia caminhos de comprimentos crescentes até um limite $k$. O algoritmo mantém contagens de caminhos que alcançam cada estado para garantir a terminação e retorna os $k$ caminhos mais curtos.
  • SHORTEST k GROUPS: Semelhante ao anterior, mas agrupa caminhos por comprimento, retornando todos os caminhos até o $k$-ésimo comprimento distinto encontrado.

• Modos Restritos (TRAIL, SIMPLE, ACYCLIC):

  • Estes modos são conhecidos por serem NP-completos no pior caso. O framework emprega uma exploração de força bruta do grafo produto com poda (pruning).
  • A função isValid verifica se a extensão de um caminho viola a restrição específica (ex: repetir uma aresta para TRAIL ou um nó para SIMPLE).
  • Embora a complexidade de pior caso permaneça exponencial, a abordagem é projetada para ser eficiente em grafos do mundo real, onde o número de caminhos válidos é frequentemente gerenciável.

Implementação e Integração

• Grafos de Propriedade: Implementado sobre o MillenniumDB, um motor de grafos de código aberto. A sintaxe estende padrões do tipo Cypher para incluir variáveis de caminho e modos (ex: MATCH (src)=[MODE ?p rgx]=>(tgt)).
• Extensão SPARQL: O framework estende a sintaxe SPARQL para suportar o retorno de caminhos (ex: src MODE (path AS ?p) tgt), demonstrando que motores RDF existentes podem ser aumentados com essas capacidades.
• Modelo de Execução: Os algoritmos são implementados usando iteradores lineares para execução em pipeline, garantindo que os caminhos sejam retornados conforme ocorrem, em vez de exigir a construção de todo o conjunto de soluções antes da saída.

Principais Contribuições

1. Primeiro Framework Unificado: O PATHFINDER é o primeiro sistema a suportar o retorno de caminhos para todos os 27 modos de caminho prescritos pelos padrões GQL e SQL/PGQ.
2. Novidade Algorítmica: Fornece algoritmos implementáveis baseados na construção do grafo produto que lidam com as complexidades dos modos de caminho, incluindo o tratamento de autômatos não-determinísticos e a enumeração de múltiplos caminhos mais curtos ou grupos de caminhos.
3. Extensão SPARQL: Demonstra a viabilidade de estender o SPARQL para retornar testemunhas de caminho, preenchendo a lacuna entre as capacidades de consulta de RDF e de grafos de propriedade.
4. Viabilidade Prática: Através de experimentação extensiva, o artigo mostra que, apesar da dureza teórica para certos modos (como TRAIL), a abordagem produz um desempenho notavelmente estável em dados do mundo real.

Resultados Experimentais

Os autores avaliaram o PATHFINDER usando três conjuntos de dados: Pokec (rede social), Wikidata (grafo de conhecimento de larga escala) e um grafo sintético Diamond (projetado para ter exponencialmente muitos caminhos).

• Desempenho: O PATHFINDMND superou consistentemente os motores de última geração (Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso) por uma a duas ordens de magnitude (10x–100x de aceleração).
• Escalabilidade:
  • No Pokec, o PATHFINDER manteve um desempenho estável à medida que os comprimentos dos caminhos aumentavam, enquanto outros sistemas frequentemente sofriam timeout.
  • No Wikidata, o PATHFINDER processou com sucesso 659 consultas complexas, enquanto os motores SPARQL (que não retornam caminhos) foram significativamente mais lentos, e os motores de grafos de propriedade (Neo4j) sofreram timeout na vasta maioria das consultas.
  • No grafo Diamond, o PATHFINDER demonstrou complexidade de tempo linear para modos WALK, enquanto outros motores exibiram crescimento exponencial. Para modos TRAIL, a variante de Busca em Profundidade (DFS) do PATHFINDER provou ser superior ao BFS no tratamento de números massivos de caminhos.
• Robustez: O sistema lidou com consultas teoricamente intratáveis (ex: TRAIL em grandes grafos) com desempenho estável, sugerindo que as distribuições de dados do mundo real mitigam a complexidade teórica de pior caso.

Significância e Alegações

O artigo afirma que o PATHFINDER representa um passo significativo no processamento de consultas de grafos ao unificar as capacidades teóricas de GQL/SQL/PGQ com a implementação prática.

• Viabilidade do Retorno de Caminhos: O trabalho prova que retornar testemunhas completas de caminhos para RPQs complexas não é apenas teoricamente possível, mas também praticamente eficiente, mesmo para modos anteriormente considerados intratáveis.
• Conformidade com Padrões: É o primeiro motor a suportar totalmente os 27 modos de caminho do padrão GQL, abordando uma lacuna crítica na tecnologia atual de bancos de dados.
• Extensibilidade: A integração bem-sucedida no MillenniumDB e a extensão do SPARQL demonstram que esses algoritmos podem ser incorporados em pipelines de banco de dados existentes sem exigir uma reescrita completa do motor subjacente.
• Perspectiva Futura Modesta: Os autores observam que, embora a implementação atual lide com RPQs padrão, trabalhos futuros explorarão consultas mais expressivas envolvendo propriedades de dados de nós e arestas, e uma investigação adicional é necessária sobre como a semântica de retorno de caminho se integra com a sintaxe específica de caminhos de propriedade do SPARQL.

Em conclusão, o PATHFINDER oferece uma estratégia sólida e de alto desempenho para consultas de retorno de caminho, desafiando a noção de que tais recursos devem vir ao custo da escalabilidade ou exigir a limitação do poder expressivo da linguagem de consulta.