Graph queries com recursive CTEs e extensions

1. Fundamentos de Grafos em Bancos de Dados Relacionais

1.1. Conceitos básicos: nós, arestas, caminhos e propriedades

Grafos são estruturas matemáticas compostas por nós (vértices) e arestas (edges) que conectam pares de nós. Em bancos de dados relacionais, modelamos grafos usando tabelas tradicionais, onde cada nó possui um identificador único e propriedades armazenadas como colunas, e cada aresta referencia dois nós (origem e destino) e pode conter atributos como peso, tipo ou timestamp.

1.2. Modelagem de grafos no esquema relacional

A modelagem mais comum utiliza duas tabelas:

-- Tabela de nós (vértices)
CREATE TABLE vertices (
    id SERIAL PRIMARY KEY,
    label VARCHAR(50),
    properties JSONB
);

-- Tabela de arestas (edges)
CREATE TABLE edges (
    id SERIAL PRIMARY KEY,
    source_id INTEGER REFERENCES vertices(id),
    target_id INTEGER REFERENCES vertices(id),
    weight NUMERIC,
    edge_type VARCHAR(20)
);

1.3. Diferenças entre bancos relacionais e orientados a grafos

Enquanto bancos como Neo4j e ArangoDB oferecem navegação nativa por ponteiros físicos (traversal), bancos relacionais exigem joins recursivos para simular essa navegação. A vantagem relacional é a maturidade em transações ACID e integração com sistemas existentes.

2. Recursive CTEs: A Base para Consultas Hierárquicas e em Grafo

2.1. Sintaxe de CTEs recursivas

Uma CTE recursiva possui duas partes: o termo âncora (que retorna o conjunto inicial) e o termo recursivo (que referencia a própria CTE):

WITH RECURSIVE cte_name AS (
    -- Termo âncora
    SELECT colunas FROM tabela WHERE condicao_inicial
    UNION ALL
    -- Termo recursivo
    SELECT colunas FROM tabela 
    JOIN cte_name ON condicao_recursiva
)
SELECT * FROM cte_name;

2.2. Controle de profundidade e prevenção de loops

O uso de UNION ALL permite duplicatas e pode gerar loops infinitos. Para prevenir, adicionamos um contador de profundidade:

WITH RECURSIVE hierarchy AS (
    SELECT id, name, parent_id, 1 AS depth
    FROM employees WHERE parent_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.parent_id, h.depth + 1
    FROM employees e
    JOIN hierarchy h ON e.parent_id = h.id
    WHERE h.depth < 10  -- limite de profundidade
)
SELECT * FROM hierarchy;

2.3. Exemplo clássico: hierarquia de empregados

WITH RECURSIVE org_chart AS (
    SELECT id, name, manager_id, name AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, 
           CONCAT(oc.path, ' -> ', e.name)
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT * FROM org_chart ORDER BY path;

3. Navegação em Grafos com Recursive CTEs

3.1. Busca em largura (BFS) e busca em profundidade (DFS)

Para BFS, controlamos a ordem de expansão com um campo level:

WITH RECURSIVE bfs AS (
    SELECT source_id, target_id, 1 AS level
    FROM edges WHERE source_id = 1
    UNION ALL
    SELECT e.source_id, e.target_id, bfs.level + 1
    FROM edges e
    JOIN bfs ON e.source_id = bfs.target_id
    WHERE bfs.level < 5
)
SELECT DISTINCT target_id, MIN(level) AS min_level
FROM bfs GROUP BY target_id ORDER BY min_level;

3.2. Encontrando caminhos entre dois nós (Dijkstra simplificado)

WITH RECURSIVE shortest_path AS (
    SELECT source_id, target_id, weight, 
           ARRAY[source_id, target_id] AS path,
           weight AS total_cost
    FROM edges WHERE source_id = 1
    UNION ALL
    SELECT e.source_id, e.target_id, e.weight,
           sp.path || e.target_id,
           sp.total_cost + e.weight
    FROM edges e
    JOIN shortest_path sp ON e.source_id = sp.target_id
    WHERE NOT e.target_id = ANY(sp.path)
)
SELECT path, total_cost
FROM shortest_path
WHERE target_id = 10
ORDER BY total_cost LIMIT 1;

3.3. Detectando ciclos com arrays de nós visitados

WITH RECURSIVE detect_cycles AS (
    SELECT source_id, target_id, ARRAY[source_id, target_id] AS visited
    FROM edges WHERE source_id = 1
    UNION ALL
    SELECT e.source_id, e.target_id, dc.visited || e.target_id
    FROM edges e
    JOIN detect_cycles dc ON e.source_id = dc.target_id
    WHERE e.target_id = ANY(dc.visited)  -- ciclo detectado
)
SELECT DISTINCT visited FROM detect_cycles 
WHERE visited[1] = visited[array_length(visited,1)];

4. Consultas Avançadas com Recursive CTEs

4.1. Cálculo de distâncias ponderadas e custos acumulados

WITH RECURSIVE weighted_paths AS (
    SELECT source_id, target_id, weight AS accumulated_cost,
           ARRAY[source_id, target_id] AS route
    FROM edges WHERE source_id = 1
    UNION ALL
    SELECT e.source_id, e.target_id, 
           wp.accumulated_cost + e.weight,
           wp.route || e.target_id
    FROM edges e
    JOIN weighted_paths wp ON e.source_id = wp.target_id
    WHERE NOT e.target_id = ANY(wp.route)
)
SELECT route, accumulated_cost
FROM weighted_paths
WHERE target_id = 5
ORDER BY accumulated_cost;

4.2. Agregações em subgrafos

WITH RECURSIVE subgraph AS (
    SELECT id FROM vertices WHERE label = 'start_node'
    UNION ALL
    SELECT e.target_id
    FROM edges e
    JOIN subgraph s ON e.source_id = s.id
)
SELECT COUNT(*) AS total_nodes, 
       SUM(v.properties->>'value') AS total_value
FROM vertices v WHERE v.id IN (SELECT id FROM subgraph);

4.3. Identificação de componentes conexos

WITH RECURSIVE components AS (
    SELECT id, id AS component_id
    FROM vertices
    UNION ALL
    SELECT v.id, c.component_id
    FROM vertices v
    JOIN edges e ON v.id = e.target_id
    JOIN components c ON e.source_id = c.id
    WHERE v.id < c.component_id
)
SELECT MIN(component_id) AS component, array_agg(DISTINCT id) AS nodes
FROM components GROUP BY component_id;

5. Extensões para Grafos: Apache AGE e pgRouting

5.1. Apache AGE: sintaxe openCypher dentro do PostgreSQL

Apache AGE permite consultas estilo Cypher diretamente no PostgreSQL:

-- Criar um grafo
SELECT * FROM ag_catalog.create_graph('social_network');

-- Consulta Cypher
SELECT * FROM cypher('social_network', $$
    MATCH (p:Person)-[:FRIENDS_WITH]->(f:Person)
    WHERE p.name = 'Alice'
    RETURN f.name, f.age
$$) AS (friend_name text, friend_age int);

5.2. pgRouting: funções especializadas para redes

pgRouting oferece algoritmos otimizados para problemas de roteamento:

-- Preparar a rede viária
SELECT pgr_createTopology('ways', 0.001, 'geom', 'id');

-- Dijkstra otimizado
SELECT * FROM pgr_dijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM ways',
    1, 100, directed := true
);

5.3. Comparação de performance: recursive CTEs vs extensões nativas

Extensões como pgRouting usam implementações em C compiladas, sendo 10-100x mais rápidas que CTEs recursivas para grafos com milhares de nós. Para grafos pequenos (<1000 nós), CTEs são suficientes e mais portáveis.

6. Otimização de Performance em Graph Queries

6.1. Indexação estratégica

CREATE INDEX idx_edges_source ON edges(source_id);
CREATE INDEX idx_edges_target ON edges(target_id);
CREATE INDEX idx_edges_source_target ON edges(source_id, target_id);
CREATE INDEX idx_vertices_label ON vertices(label);

6.2. Limitação de profundidade e pruning

Sempre limite a profundidade máxima e use WHERE clauses para podar caminhos irrelevantes:

WITH RECURSIVE pruned_search AS (
    SELECT id, 1 AS depth FROM vertices WHERE label = 'start'
    UNION ALL
    SELECT e.target_id, ps.depth + 1
    FROM edges e
    JOIN pruned_search ps ON e.source_id = ps.id
    WHERE ps.depth < 5 
      AND e.weight < 100  -- pruning por custo
)
SELECT * FROM pruned_search;

6.3. Uso de materialized views para subgrafos consultados com frequência

CREATE MATERIALIZED VIEW frequent_subgraph AS
WITH RECURSIVE sub AS (
    SELECT id FROM vertices WHERE label = 'hub'
    UNION ALL
    SELECT e.target_id FROM edges e JOIN sub ON e.source_id = sub.id
    WHERE e.weight < 50
)
SELECT * FROM vertices WHERE id IN (SELECT id FROM sub);

REFRESH MATERIALIZED VIEW frequent_subgraph;

7. Casos de Uso Reais e Padrões de Projeto

7.1. Redes sociais: recomendação de amigos

WITH RECURSIVE friend_of_friend AS (
    SELECT target_id AS friend_id, 1 AS distance
    FROM edges WHERE source_id = 42 AND edge_type = 'friendship'
    UNION ALL
    SELECT e.target_id, fof.distance + 1
    FROM edges e
    JOIN friend_of_friend fof ON e.source_id = fof.friend_id
    WHERE fof.distance < 3 AND e.edge_type = 'friendship'
)
SELECT friend_id, MIN(distance) AS degree
FROM friend_of_friend
WHERE friend_id NOT IN (
    SELECT target_id FROM edges WHERE source_id = 42
)
GROUP BY friend_id ORDER BY degree, friend_id;

7.2. Logística e transporte: rotas otimizadas

WITH RECURSIVE routes AS (
    SELECT source, target, cost, ARRAY[source, target] AS path
    FROM road_network WHERE source = 'warehouse_A'
    UNION ALL
    SELECT rn.source, rn.target, r.cost + rn.cost, r.path || rn.target
    FROM road_network rn
    JOIN routes r ON rn.source = r.target
    WHERE NOT rn.target = ANY(r.path) AND r.cost < 500
)
SELECT path, cost FROM routes 
WHERE target = 'customer_Z' ORDER BY cost LIMIT 3;

7.3. Análise de dependências: árvores de decisão

WITH RECURSIVE dependencies AS (
    SELECT task_id, name, ARRAY[task_id] AS dependency_chain
    FROM tasks WHERE parent_task_id IS NULL
    UNION ALL
    SELECT t.task_id, t.name, d.dependency_chain || t.task_id
    FROM tasks t
    JOIN dependencies d ON t.parent_task_id = d.task_id
)
SELECT * FROM dependencies ORDER BY array_length(dependency_chain, 1);

Referências