Dados hierárquicos (SQL Server)

Artigo
07/31/2024

Aplica-se a: SQL Server Banco de Dados SQL do Azure Instância Gerenciada de SQL do Azure

O tipo de dados interno hierarchyid facilita o armazenamento e a consulta de dados hierárquicos. hierarchyid foi otimizado para representar árvores, que são o tipo mais comum de dados hierárquicos.

Os dados hierárquicos são definidos como um conjunto de itens de dados mutuamente relacionados por relações hierárquicas. As relações hierárquicas existem onde um item de dados é o pai de outro item. Exemplos dos dados hierárquicos que geralmente são armazenados em bancos de dados incluem os seguintes itens:

Uma estrutura organizacional
Um sistema de arquivos
Um conjunto de tarefas em um projeto
Uma taxonomia de termos de linguagem
Um gráfico de links entre páginas da Web

Use hierarchyid como o tipo de dados para criar tabelas com uma estrutura hierárquica ou para descrever a estrutura hierárquica dos dados armazenados em outro local. Use as funções hierarchyid no Transact-SQL para consultar e gerenciar dados hierárquicos.

Principais propriedades

Um valor do tipo de dados hierarchyid representa uma posição em uma hierarquia de árvore. Os valores para hierarchyid têm as seguintes propriedades:

Extremamente compacto

O número médio de bits necessários para representar um nó em uma árvore com n nós depende da média de fanout (o número médio de filhos de um nó). Para fanouts pequenos (0-7), o tamanho é de aproximadamente $6log{A}{n}$ bits, em que A é o fanout médio. Um nó em uma hierarquia organizacional de 100.000 pessoas com um fanout médio de seis níveis usa cerca de 38 bits. Isso é arredondado para 40 bits, ou 5 bytes, para armazenamento.
A comparação está na ordem de profundidade

Considerando dois valores de hierarchyid a e b, a < b significa que a vem antes de b em uma travessia de balanceamento em profundidade da árvore. Índices em tipos de dados hierarchyid estão na ordem de profundidade e os nós próximos uns dos outros em uma passagem de profundidade são armazenados próximos um ao outro. Por exemplo, os filhos de um registro são armazenados próximo àquele registro.
Suporte a inserções e exclusões arbitrárias

Usando o método GetDescendant (mecanismo de banco de dados), é sempre possível gerar um irmão à direita de qualquer nó determinado, à esquerda de qualquer nó determinado ou entre dois irmãos. A propriedade de comparação é mantida quando um número arbitrário de nós é inserido ou excluído da hierarquia. A maioria das inserções e exclusões preserva a propriedade de densidade. Porém, inserções entre dois nós produzirão valores de hierarchyid com uma representação ligeiramente menos compacta.

Limitações

O tipo de dados hierarchyid tem as seguintes limitações:

Uma coluna do tipo hierarchyid não representa automaticamente uma árvore. Depende do aplicativo gerar e atribuir valores hierarchyid de maneira que a relação desejada entre as linhas seja refletida nos valores. Alguns aplicativos podem ter uma coluna do tipo hierarchyid que indica o local em uma hierarquia definida em outra tabela.
Depende do aplicativo gerenciar a simultaneidade na geração e atribuição de valores hierarchyid. Não há nenhuma garantia de que os valores hierarchyid em uma coluna sejam exclusivos a menos que o aplicativo use uma restrição de chave exclusiva ou force sua exclusividade em sua própria lógica.
Relações hierárquicas representadas por valores hierarchyid não são impostas como uma relação de chave estrangeira. É possível e, às vezes, apropriado ter uma relação hierárquica onde A tem um filho B e, depois, A é excluído, deixando B com uma relação para um registro inexistente. Se esse comportamento for inaceitável, o aplicativo deverá fazer a consulta por descendentes antes de excluir os pais.

Quando usar alternativas para hierarchyid

As duas alternativas para hierarchyid para representar dados hierárquicos são:

Pai/filho
XML

Ahierarchyid é geralmente superior a essas alternativas. Porém, há situações específicas detalhadas neste artigo em que as alternativas são provavelmente superiores.

Pai/filho

Ao usar a abordagem pai/filho, cada linha contém uma referência ao pai. A tabela a seguir define uma tabela típica usada para conter as linhas pai e filho em uma relação pai/filho:

USE AdventureWorks2022;
GO

CREATE TABLE ParentChildOrg (
    BusinessEntityID INT PRIMARY KEY,
    ManagerId INT REFERENCES ParentChildOrg(BusinessEntityID),
    EmployeeName NVARCHAR(50)
);
GO

Comparando pai/filho e hierarchyid em operações comuns:

Consultas de subárvore são significativamente mais rápidas com hierarchyid.
Consultas de descendente direto são ligeiramente mais lentas com hierarchyid.
A movimentação de nós não folha é mais lenta com hierarchyid.
A inserção de nós não folha e a inserção ou a movimentação de nós folha têm a mesma complexidade com hierarchyid.

Pai/filho pode ser superior quando as seguintes condições existem:

O tamanho da chave é crítico. Para o mesmo número de nós, um valor hierarchyid é igual ou maior que um valor da família de inteiros (smallint, int, bigint). Essa é a única razão para usar pai/filho em casos raros, porque hierarchyid tem localidade significativamente melhor de E/S e complexidade de CPU que as expressões de tabela comuns exigidas quando você está usando uma estrutura pai/filho.
Consultas raramente examinam por seções da hierarquia. Em outras palavras, as consultas normalmente se dirigem apenas a um único ponto na hierarquia. Nesses casos, a colocação não é importante. Por exemplo, pai/filho é superior quando a tabela de organização é usada somente para processar a folha de pagamento de funcionários individuais.
Subárvores de não folha mudam frequentemente e o desempenho é muito importante. Em uma representação pai/filho, alterar o local de uma linha em uma hierarquia afeta uma linha única. Alterar o local de uma linha em um uso de hierarchyid afeta n linhas, em que n é número de nós na subárvore sendo movida.

Se as subárvores sem folha mudarem frequentemente e o desempenho for importante, mas a maioria das mudanças estiver em um nível bem definido da hierarquia, considere dividir os níveis superiores e inferiores em duas hierarquias. Isso faz todas as mudanças em níveis de folha da hierarquia mais alta. Por exemplo, considere uma hierarquia de sites hospedados por um serviço. Sites contêm muitas páginas organizadas de uma maneira hierárquica. Sites hospedados poderiam ser movidos a outros locais na hierarquia do site, mas as páginas subordinadas raramente seriam reorganizadas. Isso poderia ser representado por:
```
CREATE TABLE HostedSites (
    SiteId HIERARCHYID,
    PageId HIERARCHYID
);
GO
```

XML

Um documento XML é uma árvore e, portanto, uma instância de tipo de dados XML única pode representar uma hierarquia completa. No SQL Server quando um índice XML é criado, são usados valores hierarchyid internamente para representar a posição na hierarquia.

Usar um tipo de dados XML pode ser vantajoso quando todos os seguintes itens forem verdadeiros:

A hierarquia completa é sempre armazenada e recuperada.
Os dados são consumidos no formato XML pelo aplicativo.
Pesquisas de predicado são extremamente limitadas e não têm de desempenho crítico.

Por exemplo, se um aplicativo controla várias organizações, ele sempre armazena e recupera a hierarquia organizacional completa e não faz a consulta em uma única organização. Uma tabela do formulário a seguir pode fazer sentido:

CREATE TABLE XMLOrg (
    Orgid INT,
    Orgdata XML
);
GO

Estratégias de indexação para dados hierárquicos

Há duas estratégias para indexar dados hierárquicos:

Profundidade

Um índice de profundidade armazena as linhas em uma subárvore próximas umas das outras. Por exemplo, todos os funcionários que se reportam a gerente são armazenados próximos do registro de seus gerentes.

Em um índice por profundidade, todos os nós na subárvore de um nó são colocados. Índices por profundidade são portanto eficientes para responder consultas sobre subárvores, como "Localizar todos os arquivos nesta pasta e subpastas"
Amplitude

Um índice de balanceamento em largura armazena as linhas de cada nível da hierarquia juntas. Por exemplo, os registros de funcionários que se reportam diretamente ao mesmo gerente são armazenados próximos um do outro.

Em um índice por amplitude todos os filhos diretos de um nós são colocados. Índices por amplitude são, portanto, eficientes para responder consultas sobre filhos diretos, como "Localizar todos os empregados que se reportam diretamente a esse gerente"

Ter opções por profundidade, por amplitude, ou ambas, e qual delas tornar a chave de clustering (se houver), depende da importância relativa dos tipos de consultas anteriores e da importância relativa de operações SELECT versus DML. Para obter um exemplo detalhado de estratégias de indexação, consulte Tutorial: Usando o tipo de dados HierarchyId.

Criar índices

O método GetLevel() pode ser usado para criar uma ordem por amplitude. No exemplo seguinte, são criados índices por amplitude e por profundidade:

USE AdventureWorks2022;
GO

CREATE TABLE Organization (
    BusinessEntityID HIERARCHYID,
    OrgLevel AS BusinessEntityID.GetLevel(),
    EmployeeName NVARCHAR(50) NOT NULL
);
GO

CREATE CLUSTERED INDEX Org_Breadth_First
ON Organization (OrgLevel, BusinessEntityID);
GO

CREATE UNIQUE INDEX Org_Depth_First
ON Organization (BusinessEntityID);
GO

Exemplos

Os exemplos de código do Transact-SQL deste artigo usa o banco de dados de exemplo AdventureWorks2022 ou AdventureWorksDW2022, que pode ser baixado da home page Microsoft SQL Server Samples and Community Projects.

Exemplo básico

O exemplo a seguir é intencionalmente simplificado para ajudá-lo a começar. Primeiro crie uma tabela para manter alguns dados geográficos.

CREATE TABLE BasicDemo (
    [Level] HIERARCHYID NOT NULL,
    Location NVARCHAR(30) NOT NULL,
    LocationType NVARCHAR(9) NULL
);

Agora insira dados para alguns continentes, países/regiões, estados e cidades.

INSERT BasicDemo
VALUES ('/1/', 'Europe', 'Continent'),
    ('/2/', 'South America', 'Continent'),
    ('/1/1/', 'France', 'Country'),
    ('/1/1/1/', 'Paris', 'City'),
    ('/1/2/1/', 'Madrid', 'City'),
    ('/1/2/', 'Spain', 'Country'),
    ('/3/', 'Antarctica', 'Continent'),
    ('/2/1/', 'Brazil', 'Country'),
    ('/2/1/1/', 'Brasilia', 'City'),
    ('/2/1/2/', 'Bahia', 'State'),
    ('/2/1/2/1/', 'Salvador', 'City'),
    ('/3/1/', 'McMurdo Station', 'City');

Selecione os dados, adicionando uma coluna que converta os dados de nível em um valor de texto de fácil compreensão. Essa consulta também ordena o resultado pelo tipo de dados hierarchyid .

SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
    *
FROM BasicDemo
ORDER BY [Level];

Veja a seguir o conjunto de resultados.

Converted Level  Level     Location         LocationType
---------------  --------  ---------------  ---------------
/1/              0x58      Europe           Continent
/1/1/            0x5AC0    France           Country
/1/1/1/          0x5AD6    Paris            City
/1/2/            0x5B40    Spain            Country
/1/2/1/          0x5B56    Madrid           City
/2/              0x68      South America    Continent
/2/1/            0x6AC0    Brazil           Country
/2/1/1/          0x6AD6    Brasilia         City
/2/1/2/          0x6ADA    Bahia            State
/2/1/2/1/        0x6ADAB0  Salvador         City
/3/              0x78      Antarctica       Continent
/3/1/            0x7AC0    McMurdo Station  City

A hierarquia tem uma estrutura válida, embora ela não seja internamente consistente. Bahia é o único estado. Ele aparece na hierarquia como um par da cidade de Brasília. Da mesma forma, a estação McMurdo não tem uma região/país pai. Os usuários devem decidir se este tipo de hierarquia é apropriado para seu uso.

Adicione outra linha e selecione os resultados.

INSERT BasicDemo
VALUES ('/1/3/1/', 'Kyoto', 'City'),
    ('/1/3/1/', 'London', 'City');

SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
    *
FROM BasicDemo
ORDER BY [Level];

Isso demonstra mais problemas em potencial. Kyoto pode ser inserido como o nível /1/3/1/, embora não exista um nível pai /1/3/. Londres e Kyoto têm o mesmo valor para hierarchyid. Além disso, os usuários devem decidir se este tipo de hierarquia é apropriado para seu uso, e os valores do bloco que são inválidos para seu uso.

Além disso, essa tabela não usou a parte superior da hierarquia '/'. Ela foi omitida pois não há um pai comum de todos os continentes. Para adicionar um, adicione o planeta inteiro.

INSERT BasicDemo
VALUES ('/', 'Earth', 'Planet');

Migrando de pai/filho para hierarchyid

A maioria das árvores é representada usando pai/filho. O modo mais fácil de migrar de uma estrutura pai/filho para uma tabela usando hierarchyid é usar uma coluna ou uma tabela temporária para manter o controle do número de nós em cada nível da hierarquia. Para obter um exemplo de migração de uma tabela pai/filho, consulte a lição 1 do Tutorial: Usando o tipo de dados HierarchyId.

Gerenciar uma árvore com hierarchyid

Embora uma coluna hierarchyid não represente necessariamente uma árvore, um aplicativo pode garantir facilmente que ela o faça.

Para gerar novos valores, execute uma das seguintes etapas:
- Mantenha registro do último número filho da linha pai.
- Compute o último filho. Para executar esse procedimento com eficácia, é necessário um índice de primeira amplitude.
Imponha a exclusividade criando um índice exclusivo na coluna, talvez como parte de uma chave de clustering. Para garantir a inserção de valores únicos, execute uma das seguintes etapas:
- Detecte as falhas de violação de chave exclusiva e tente novamente.
- Determine a exclusividade de cada novo nó filho e insira-o como parte de uma transação serializável.

Exemplo utilizando detecção de erro

No exemplo a seguir, o código de exemplo computa o novo valor de EmployeeId filho e, em seguida, detecta quaisquer violações de chave para retorná-las ao marcador INS_EMP para computar novamente o valor de EmployeeId na nova linha:

USE AdventureWorks;
GO

CREATE TABLE Org_T1 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    OrgLevel AS EmployeeId.GetLevel(),
    EmployeeName NVARCHAR(50)
);
GO

CREATE INDEX Org_BreadthFirst ON Org_T1 (
    OrgLevel,
    EmployeeId
);
GO

CREATE PROCEDURE AddEmp (
    @mgrid HIERARCHYID,
    @EmpName NVARCHAR(50)
)
AS
BEGIN
    DECLARE @last_child HIERARCHYID;

    INS_EMP:

    SELECT @last_child = MAX(EmployeeId)
    FROM Org_T1
    WHERE EmployeeId.GetAncestor(1) = @mgrid;

    INSERT INTO Org_T1 (EmployeeId, EmployeeName)
    SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName;

    -- On error, return to INS_EMP to recompute @last_child
    IF @@error <> 0
        GOTO INS_EMP
END;
GO

Exemplo utilizando uma transação serializável

O índice Org_BreadthFirst garante que o @last_child determinante use uma busca de intervalo. Além de outros casos de erro que um aplicativo tente verificar, uma violação da chave duplicada depois da inserção indica uma tentativa de adicionar vários funcionários com a mesma ID e, portanto, @last_child deve ser computado novamente. O código a seguir computa o novo valor de nó dentro de uma transação serializável:

CREATE TABLE Org_T2 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    LastChild HIERARCHYID,
    EmployeeName NVARCHAR(50)
);
GO

CREATE PROCEDURE AddEmp (
    @mgrid HIERARCHYID,
    @EmpName NVARCHAR(50)
)
AS
BEGIN
    DECLARE @last_child HIERARCHYID;

    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

    BEGIN TRANSACTION;

    SELECT @last_child = EmployeeId.GetDescendant(LastChild, NULL)
    FROM Org_T2
    WHERE EmployeeId = @mgrid;

    UPDATE Org_T2
    SET LastChild = @last_child
    WHERE EmployeeId = @mgrid;

    INSERT Org_T2 (EmployeeId, EmployeeName)
    VALUES (@last_child, @EmpName);

    COMMIT;
END;

O código a seguir popula a tabela com três linhas e retorna os resultados:

INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES (HIERARCHYID::GetRoot(), 'David');
GO

AddEmp 0x, 'Sariya'
GO

AddEmp 0x58, 'Mary'
GO

SELECT * FROM Org_T2

Veja a seguir o conjunto de resultados.

EmployeeId LastChild EmployeeName
---------- --------- ------------
0x        0x58       David
0x58      0x5AC0     Sariya
0x5AC0    NULL       Mary

Impor uma árvore

Os exemplos anteriores ilustram como um aplicativo pode assegurar a manutenção de uma árvore. Para impor uma árvore usando restrições, uma coluna computada que define o pai de cada nó pode ser criada com uma restrição de chave estrangeira na identificação da chave primária.

CREATE TABLE Org_T3 (
    EmployeeId HIERARCHYID PRIMARY KEY,
    ParentId AS EmployeeId.GetAncestor(1) PERSISTED REFERENCES Org_T3(EmployeeId),
    LastChild HIERARCHYID,
    EmployeeName NVARCHAR(50)
);
GO

Esse método de impor uma relação é preferencial quando um código que não é confiável para manter a árvore hierárquica tem acesso DML direto à tabela. No entanto, esse método pode reduzir o desempenho porque a restrição deve ser verificada em todas as operações DML.

Localizando ancestrais com a CLR

Uma operação comum que envolve dois nós em uma hierarquia é encontrar o mais baixo ancestral comum. Essa tarefa pode ser escrita em Transact-SQL ou CLR, porque o tipo hierarchyid está disponível em ambas. Recomenda-se usar CLR porque o desempenho será mais rápido.

Use o código CLR a seguir para listar os ancestrais e localizar o ancestral comum mais baixo:

using System;
using System.Collections;
using System.Text;
using Microsoft.SqlServer.Server; // SqlFunction Attribute
using Microsoft.SqlServer.Types;  // SqlHierarchyId

public partial class HierarchyId_Operations
{
    [SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
    public static IEnumerable ListAncestors(SqlHierarchyId h)
    {
        while (!h.IsNull)
        {
            yield return (h);
            h = h.GetAncestor(1);
        }
    }

    public static void FillRow_ListAncestors(
        Object obj,
        out SqlHierarchyId ancestor
    )
    {
        ancestor = (SqlHierarchyId)obj;
    }

    public static HierarchyId CommonAncestor(
        SqlHierarchyId h1,
        HierarchyId h2
    )
    {
        while (!h1.IsDescendantOf(h2))
        {
            h1 = h1.GetAncestor(1);
        }

        return h1;
    }
}

Para usar os métodos ListAncestor e CommonAncestor nos exemplos do Transact-SQL a seguir, compile a DLL e crie o assembly HierarchyId_Operations no SQL Server executando um código semelhante ao seguinte:

CREATE ASSEMBLY HierarchyId_Operations
    FROM '<path to DLL>\ListAncestors.dll';
GO

Listar os ancestrais

A criação de uma lista de ancestrais de um nó é uma operação comum; por exemplo, para mostrar a posição em uma organização. Uma das formas de fazer isso é usar uma função com valor de tabela usando a classe HierarchyId_Operations definida acima:

Usando Transact-SQL:

CREATE FUNCTION ListAncestors (@node HIERARCHYID)
RETURNS TABLE (node HIERARCHYID)
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors;
GO

Exemplo de uso:

DECLARE @h HIERARCHYID

SELECT @h = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/

SELECT LoginID,
    OrgNode.ToString() AS LogicalNode
FROM HumanResources.EmployeeDemo AS ED
INNER JOIN ListAncestors(@h) AS A
    ON ED.OrgNode = A.Node
GO

Localizar o ancestral comum mais baixo

Usando a classe HierarchyId_Operations definida anteriormente, crie a seguinte função Transact-SQL para localizar o ancestral comum mais baixo que envolva dois nós em uma hierarquia:

CREATE FUNCTION CommonAncestor (
    @node1 HIERARCHYID,
    @node2 HIERARCHYID
)
RETURNS HIERARCHYID
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor;
GO

Exemplo de uso:

DECLARE @h1 HIERARCHYID, @h2 HIERARCHYID;

SELECT @h1 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\jossef0';-- Node is /1/1/3/

SELECT @h2 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0';-- Node is /1/1/5/2/

SELECT OrgNode.ToString() AS LogicalNode, LoginID
FROM HumanResources.EmployeeDemo
WHERE OrgNode = dbo.CommonAncestor(@h1, @h2);

O nó resultante é /1/1/

Mover subárvores

Outra operação comum é mover subárvores. O procedimento abaixo toma uma subárvore de @oldMgr e a transforma (inclusive @oldMgr) em uma subárvore de @newMgr.

CREATE PROCEDURE MoveOrg (
    @oldMgr NVARCHAR(256),
    @newMgr NVARCHAR(256)
)
AS
BEGIN
    DECLARE @nold HIERARCHYID, @nnew HIERARCHYID;

    SELECT @nold = OrgNode
    FROM HumanResources.EmployeeDemo
    WHERE LoginID = @oldMgr;

    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

    BEGIN TRANSACTION;

    SELECT @nnew = OrgNode
    FROM HumanResources.EmployeeDemo
    WHERE LoginID = @newMgr;

    SELECT @nnew = @nnew.GetDescendant(max(OrgNode), NULL)
    FROM HumanResources.EmployeeDemo
    WHERE OrgNode.GetAncestor(1) = @nnew;

    UPDATE HumanResources.EmployeeDemo
    SET OrgNode = OrgNode.GetReparentedValue(@nold, @nnew)
    WHERE OrgNode.IsDescendantOf(@nold) = 1;

    COMMIT TRANSACTION;
END;
GO

Compartilhar via

Dados hierárquicos (SQL Server)

Principais propriedades

Limitações

Quando usar alternativas para hierarchyid

Pai/filho

XML

Estratégias de indexação para dados hierárquicos

Criar índices

Exemplos

Exemplo básico

Migrando de pai/filho para hierarchyid

Gerenciar uma árvore com hierarchyid

Exemplo utilizando detecção de erro

Exemplo utilizando uma transação serializável

Impor uma árvore

Localizando ancestrais com a CLR

Listar os ancestrais

Localizar o ancestral comum mais baixo

Mover subárvores

Comentários

Recursos adicionais

Compartilhar via

Dados hierárquicos (SQL Server)

Principais propriedades

Limitações

Quando usar alternativas para hierarchyid

Pai/filho

XML

Estratégias de indexação para dados hierárquicos

Criar índices

Exemplos

Exemplo básico

Tarefas relacionadas

Migrando de pai/filho para hierarchyid

Gerenciar uma árvore com hierarchyid

Exemplo utilizando detecção de erro

Exemplo utilizando uma transação serializável

Impor uma árvore

Localizando ancestrais com a CLR

Listar os ancestrais

Localizar o ancestral comum mais baixo

Mover subárvores

Conteúdo relacionado

Comentários

Recursos adicionais