Início / coding / Perguntas / 78443845
Accepted
Ben H
Asked: 2024-05-08 00:12:42 +0800 CST

Ignore certos tipos de nós em DLL

  • 772

Estou no Postgres 15.1 e tenho uma nodetabela como segue:

CREATE TABLE node (
    id TEXT PRIMARY KEY,
    is_skippable BOOL,
    prev TEXT REFERENCES node(id),
    "next" TEXT REFERENCES node(id)
);

Esta tabela representa uma série de listas duplamente vinculadas, mas em certas ocasiões, para determinadas consultas, desejo remover is_skippablenós da lista e vinculá-los.

Por exemplo, se eu tivesse os seguintes dados propagados no banco de dados, onde há uma lista vinculada de A1 <-> A2 <-> A3(com A2ignorável) e uma de B1 <-> B2:

INSERT INTO node VALUES 
  ('A1', FALSE, NULL, 'A2'), 
  ('A2', TRUE, 'A1', 'A3'), 
  ('A3', FALSE, 'A2', NULL),
  ('B1', FALSE, NULL, 'B2'), 
  ('B2', FALSE, 'B1', NULL);

Para certas consultas, quero vincular is_skippableos nós. Então, se eu consultar esta tabela completa, o conjunto de resultados que estou procurando é:

eu ia anterior próximo
A1 NULO A3
A3 A1 NULO
B1 NULO B2
B2 B1 NULO

Observe que A2não está no conjunto de resultados e A2os ponteiros foram reescritos no nó antes e depois dele.

Existe uma maneira bem suportada de fazer isso no Postgres? Já vi respostas para listas vinculadas simples em outros lugares do StackOverflow (como o conceito de lista vinculada em postgresql ), mas elas não implicam na necessidade de reescrever ponteiros. Obrigado!

Exemplo de violino aqui: https://dbfiddle.uk/4lB4TAtF .

postgresql

2 respostas

  1. Best Answer

    Você provavelmente poderia recolhê-lo para executar uma consulta lateral em ambas as direções ao mesmo tempo, mas o fato de isso apenas tentar pular para o elemento não ignorável mais próximo pode na verdade ser uma vantagem, tornando a parte recursiva mais leve. Demonstração em db<>fiddle:

    select id,(with recursive cte as( 
            select n2.id,n2.prev,n2.is_skippable
            from node n2
            where n2.id=n1.prev
            union
            select n2.id,n2.prev,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.prev
              and cte.is_skippable) CYCLE prev SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as prev
        ,(with recursive cte as( 
            select n2.id,n2.next,n2.is_skippable
            from node n2
            where n2.id=n1.next
            union
            select n2.id,n2.next,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.next
              and cte.is_skippable) CYCLE next SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as next
from node n1
where not is_skippable;
    eu ia anterior próximo
    A1 nulo A3
    A3 A1 nulo
    B1 nulo B2
    B2 B1 nulo

    1. Não importa se as listas se ramificam. Você pode restringir as condições de junção cte recursivas para verificar a bidirecionalidade do link e fazê-lo seguir estritamente o caminho bidirecional:

      from node n2 join cte 
       on n2.id = cte.next
      and n2.prev=cte.id --add this for strict

      as ramificações começam com um link unidirecional, portanto, isso irá filtrá-las.

    2. Ele não se importa com ciclos/anéis/loops, se você tiver algum, graças à detecção de ciclo integrada .

    3. Um índice de cobertura acelera as coisas:

      create index on node (id)
   include(is_skippable,prev,"next")
   with(fillfactor=100);

    4. Você pode estar interessado em pgrouting e Apache AGE .

    • 1

  2. aqui está uma solução usando um cte recursivo :

    WITH RECURSIVE cte (id, prev, next, count) AS
(
SELECT n.id, n.prev, n.next, 0
  FROM node AS n
 WHERE NOT is_skippable
UNION ALL
SELECT c.id, COALESCE (n_prev.prev, c.prev), COALESCE(n_next.next, c.next), c.count + 1 
  FROM cte AS c
  LEFT JOIN node AS n_prev
    ON n_prev.id = c.prev
  LEFT JOIN node AS n_next
    ON n_next.id = c.next
 WHERE (c.prev IS NOT NULL AND n_prev.is_skippable)
    OR (c.next IS NOT NULL AND n_next.is_skippable)
)
SELECT DISTINCT ON (id) id, prev, next
  FROM cte
 ORDER BY id, count DESC ;

    demonstração em dbfiddle

    • 0

relate perguntas