Encontrar farinha de rosca para conjuntos aninhados

Question

Eu estou usando conjuntos aninhados (aka modificado passagem de árvore pré-venda) para armazenar uma lista de grupos, e eu estou tentando encontrar uma maneira rápida de gerar pão ralado (como uma string, não uma tabela) para todos os grupos de uma vez só. Meus dados também são armazenados usando o modelo de lista de adjacência (existem gatilhos para manter os dois em sincronia).

Assim, por exemplo:

ID   Name    ParentId  Left   Right
0    Node A  0         1      12
1    Node B  0         2      5
2    Node C  1         3      4
3    Node D  0         6      11
4    Node E  3         7      8
5    Node F  4         9      9

O que representa a árvore:

• Nó A
  • Node B
    • Nó C
  • Nó D
    • Nó E
    • Nó F

Eu gostaria de ser capaz de ter uma função definida pelo usuário que retorna uma tabela:

ID  Breadcrumb
0   Node A
1   Node A > Node B
2   Node A > Node B > Node C
3   Node A > Node D
4   Node A > Node D > Node E
5   Node A > Node D > Node F

---

Para tornar este um pouco mais complicado (embora é tipo de fora do âmbito da pergunta), eu também tenho restrições de usuário que precisam ser respeitados. Assim, por exemplo, se eu só tenho acesso a id = 3, quando eu executar a consulta que eu deveria começar:

ID  Breadcrumb
3   Node D
4   Node D > Node E
5   Node D > Node F

Eu tenho uma função definida pelo usuário que leva um ID de usuário como um parâmetro, e retorna uma tabela com os ids de todos os grupos que são válidas, por isso, enquanto em algum lugar na consulta

WHERE group.id IN (SELECT id FROM dbo.getUserGroups(@userid))

que vai funcionar.

---

Eu tenho uma função escalar existente que pode fazer isso, mas simplesmente não funciona em qualquer número razoável de grupos (leva> 10 segundos em 2000 grupos). É preciso um groupid e ID de usuário como um parâmetro, e retorna um nvarchar. Ele encontra os grupos que receberam os pais (1 consulta para pegar os valores esquerda / direita, outra para encontrar os pais), restringe a lista para os grupos que o usuário tem acesso a (usando a mesma cláusula WHERE como acima, assim mais uma query), e então usa um cursor para passar por cada grupo e anexá-lo a uma corda, antes de finalmente retornar esse valor.

Eu preciso de um método para fazer isso que será executado rapidamente (por exemplo. <= 1s), na mosca.

Esta é em SQL Server 2005.

Answer 1

O que eu acabei fazendo é uma grande adesão que simplesmente amarra essa tabela a ela mesma, mais e mais para todos os níveis.

Primeiro eu preencher um @topLevelGroups tabela com apenas os grupos de 1º nível (se você só tem uma raiz que você pode pular esta etapa), e depois @userGroups com os grupos que o usuário pode ver.

SELECT groupid,
   (level1 
    + CASE WHEN level2 IS NOT NULL THEN ' > ' + level2 ELSE '' END
    + CASE WHEN level3 IS NOT NULL THEN ' > ' + level3 ELSE '' END
   )as [breadcrumb]
FROM (
  SELECT g3.*
    ,g1.name as level1
    ,g2.name as level2
    ,g3.name as level3
  FROM @topLevelGroups g1
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid
  INNER JOIN @userGroups g3 ON g3.parentid = g2.groupid 

  UNION

  SELECT g2.*
    ,g1.name as level1
    ,g2.name as level2
    ,NULL as level3
  FROM @topLevelGroups g1 
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid

  UNION

  SELECT g1.*
    ,g1.name as level1
    ,NULL as level2
    ,NULL as level3 
  FROM @topLevelGroups g1

) a
ORDER BY [breadcrumb]

Este é um muito grande corte, e é, obviamente, limitado a um determinado número de níveis (para meu aplicativo, há um limite razoável eu posso escolher), com o problema de que os mais níveis são suportados, aumenta o número de junta-se exponencialmente e, portanto, é muito mais lento.

Fazê-lo no código é certamente mais fácil, mas para mim isso simplesmente não é sempre uma opção -. Há momentos em que eu preciso esta disponível diretamente a partir de uma consulta SQL

---

Estou aceitando isso como a resposta, uma vez que é o que eu acabei fazendo e pode trabalhar para outras pessoas -. No entanto, se alguém pode vir até com um método mais eficiente eu vou mudar isso a eles

Answer 2

aqui está o SQL que funcionou para mim para obter o caminho "migalhas" de qualquer ponto na árvore. Espero que ajude.

SELECT ancestor.id, ancestor.title, ancestor.alias 
FROM `categories` child, `categories` ancestor 
WHERE child.lft >= ancestor.lft AND child.lft <= ancestor.rgt 
AND child.id = MY_CURRENT_ID 
ORDER BY ancestor.lft

Kath

Answer 3

Ok. Isto é para MySQL, não SQL Server 2005. Ele usa um GROUP_CONCAT com uma subconsulta.

Isso deve retornar a trilha completa como única coluna.

SELECT 
 (SELECT GROUP_CONCAT(parent.name SEPARATOR ' > ')
 FROM category parent
 WHERE node.Left >= parent.Left
 AND node.Right <= parent.Right
 ORDER BY Left
 ) as breadcrumb
FROM category node
ORDER BY Left

Answer 4

Se você puder, use um caminho (ou eu acho que já ouvi-lo referido como uma linhagem) campo como:

ID   Name    ParentId  Left   Right   Path
0    Node A  0         1      12      0,
1    Node B  0         2      5       0,1,
2    Node C  1         3      4       0,1,2,
3    Node D  0         6      11      0,3,
4    Node E  3         7      8       0,3,4,
5    Node F  4         9      9       0,3,4,

Para obter apenas nó D e para a frente (psuedocode):

path = SELECT Path FROM Nodes WHERE ID = 3
SELECT * FROM Nodes WHERE Path LIKE = path + '%'

Answer 5

I modificou a declaração de Kathy para obter migalhas de pão para cada elemento

SELECT
    GROUP_CONCAT(
        ancestor.name
        ORDER BY ancestor.lft ASC
        SEPARATOR ' > '
    ),
    child.*
FROM `categories` child
JOIN `categories` ancestor
ON child.lft >= ancestor.lft
AND child.lft <= ancestor.rgt
GROUP BY child.lft
ORDER BY child.lft

Sinta-se livre para adicionar uma condição WHERE por exemplo.

 WHERE ancestor.lft BETWEEN 6 AND 11

Answer 6

nenhum código específico do servidor SQL, mas você está simplesmente à procura de:

SELECT * FROM tabela WHERE esquerda <(currentid.left) e direito> (currentid.right)