T-SQL puzzles – Algoritmos iterativos/recursivos com UDFs e CTEs

Olá pessoal, tudo certo?

Hoje, começo a abordar um tema novo aqui no blog: T-SQL.

Vou apresentar duas técnicas de implementação para algoritmos iterativos/recursivos que percorrem grafos árvores. Essas técnicas são úteis em cenários onde há necessidade de gerar listas de dados pai-filho onde ambas entidades estão armazenadas em uma mesma tabela – como, por exemplo: “Chefe-Empregado”, “Diretório-arquivo”, “Unidade-setor”.

As técnicas que apresento hoje não são “novidades”, elas são apresentadas em alguns bons livros de T-SQL.

Preparando a base de dados

Para nossos exemplos de hoje, criamos uma estrutura de dados extremamente simples. Há apenas uma tabela (Nodes) que armazena o conjunto completo de dados que iremos utilizar. Nessa tabela, há um campo (ParentId) que indica um nodo “superior”. Caso o valor desse atributo esteja “nulo”, assume-se que trata-se de um nodo raíz.

Optei por utilizar tempdb, visto que estamos criando uma estrutura para estudos. Além disso, criei apenas as constraints mais óbvias.

O script que segue, cria a tabela e popula alguns dados de exemplo.

SET NOCOUNT ON;
USE tempdb;
GO

IF OBJECT_ID('dbo.Nodes') IS NOT NULL
        DROP TABLE dbo.Nodes;
GO

CREATE TABLE dbo.Nodes
(
        Id INT NOT NULL PRIMARY KEY,
        ParentId INT NULL REFERENCES dbo.Nodes,
        Name VARCHAR(25) NOT NULL,
        CHECK (Id <> ParentId)
);

INSERT INTO dbo.Nodes (Id, ParentId, Name) VALUES
        (1,     NULL,   'Root 1'),
        (2,     NULL,   'Root 2'),
        (3,     1,      'A'),
        (4,     2,      'B'),
        (5,     3,      'C'),
        (6,     3,      'D'),
        (7,     3,      'E'),
        (8,     4,      'F'),
        (9,     6,      'G'),
        (10,8,          'H'),
        (11,6,          'I'),
        (12,8,          'J'),
        (13,10,         'K'),
        (14,10,         'L'),
        (15,10,         'M');

CREATE UNIQUE INDEX idx_unique_id_parentid ON dbo.Nodes(Id, ParentId)

SELECT * FROM dbo.Nodes;

Executando nosso pequeno script. Temos nossa indicação de sucesso.

Nossos dados podem ser representados graficamente, conforme figura que segue.

Uma UDF para retornar um nodo e todos os seus filhos (diretos e indiretos)

Programas que utilizam estruturas de dados similares a que criamos necessitam, frequentemente, recuperar parte da árvore. Por exemplo, recuperar todos os nodos partindo de F.

O script que apresento cria uma função que executa essa tarefa. Observe:

USE tempdb;
GO

IF OBJECT_ID('dbo.GetNodeWithChildren') IS NOT NULL
        DROP FUNCTION dbo.GetNodeWithChildren;

GO

CREATE FUNCTION dbo.GetNodeWithChildren(@root AS INT)
RETURNS @result TABLE
(
        Id INT NOT NULL PRIMARY KEY     NONCLUSTERED,
        Depth INT NOT NULL,
                UNIQUE (Id, Depth)
)
AS
BEGIN
        DECLARE @depth AS INT = 0;

        INSERT INTO @result (Id, Depth)
                SELECT Id, @depth FROM dbo.Nodes WHERE Id = @root;

        WHILE @@ROWCOUNT > 0
        BEGIN
                SET @depth = @depth + 1;

                INSERT INTO @result
                        SELECT C.Id, @depth
                        FROM @result AS P
                                JOIN dbo.Nodes AS C
                                ON P.Depth = @depth - 1
                                AND C.ParentId = P.Id;
        END

        RETURN;
END
GO

Criamos uma UDF chamada GetNodeWithChildren. Defini como parâmetro o Id correspondente ao nó da árvores que desejo tornar raiz do meu retorno.

Falando em retorno, criei uma estrutura resumida, apenas com o Id correspondente ao nodo e um atributo para indicar a profunidade na árvore.

Utilizando a UDF para recuperar dados

A UDF que apresentei acima é muito fácil de utilizar. Para retornar a árvore partindo do Nodo com Id 2, basta:

SELECT * FROM dbo.GetNodeWithChildren(2)

Obtendo como resultado (em nosso conjunto de dados de exemplo):

A opção por retornar os Id’s e as “profundidades” na árvore é muito flexível visto que consigo agregar mais dados com facilidade. Observe:

SELECT S.*, e.Name
        FROM dbo.GetNodeWithChildren(3) AS S
        JOIN dbo.Nodes AS E
                ON E.Id = S.Id;

Com algum refinamento, também é muito simples identificar apenas os nós “folha”. Observe:

SELECT Id
        FROM dbo.GetNodeWithChildren(3) AS P
        WHERE NOT EXISTS
                (SELECT * FROM dbo.Nodes AS C
                 WHERE c.ParentId = P.Id);

Bonito, não!?

Uma CTE para retornar um nodo e seus filhos (diretos e indiretos)

Uma abordagem mais elegante (para mim) que a apresentada é indicada agora. A seguinte CTE retorna o mesmo conjunto de dados (com os mesmos campos) da UDF que apresentei anteriormente. Observe:

DECLARE @root AS INT = 3;

WITH result
AS
(
        SELECT Id, Name, 0 AS Depth
        FROM dbo.Nodes
        WHERE Id = @root

        UNION ALL

        SELECT C.Id, c.Name, P.Depth + 1
        FROM result AS P
        JOIN dbo.Nodes AS C ON C.ParentId = P.Id
)
SELECT * FROM result;

A lógica é, basicamente, a mesma. A primeira parte da consulta recupera o registro correspondente a raíz. A segunda consulta (após UNION ALL), faz a mágica acontecer recuperando, repetidamente, filhos gerados para o nível anterior.

Se você não sabe criar CTEs, é hora de aprender.

Por hoje, era isso!