Trabalhando com dados hierárquicos – Parte II

No capítulo anterior desta série, Trabalhando com dados hierárquicos – Parte I, descrevi o que são dados hierárquicos e defini algumas terminologias que utilizarei nesta e nas próximas partes. Apresentei o script para a criação das tabelas e ilustrei com maestria a estrutura hierárquica que servirá como base. Caso não tenha visto o post anterior, volte para a primeira parte antes de continuar.

Neste capítulo, falarei sobre o método mais intuitivo – para mim – de lidar com dados hierárquicos, o método iterativo.

MÉDOTO ITERATIVO

No método iterativo, utilizarei loops para varrer a estrutura hierárquica. Existem soluções que varrerão a árvore de nó em nó, mas essas geralmente são as escolhas mais custosas e lentas. Neste artigo utilizarei soluções iterativas que varrerão a árvore de nível em nível. Desta forma, serão feitas menos iterações nos laços de repetição.

jean_luc_cursor

Isso mesmo, Jean Luc. Esse comportamento iterativo é típico de cursores, mas veremos que esta solução pode ser uma saída flexível para nosso problema, e para situações onde nossa massa de dados é muito grande pode ser nossa única solução – veremos como resolver isso depois com a materialização da hierarquia.

Uma das maiores vantagens dos métodos iterativo e recursivo é que não precisamos alterar ou acrescentar nenhuma estrutura. Dependemos apenas dos dados para criar nossas soluções. Outra vantagem importante é não ter limite de níveis em nossa hierarquia. Podemos varrer quantos níveis quisermos.

SUBORDINADOS – MÉTODO ITERATIVO

Traduzindo a solicitação dos subordinados de um determinado nó através do método iterativo temos o seguinte algoritmo para montarmos nosso script:

  1. Criar uma tabela temporária para armazenar nossa hierarquia;
  2. Inserir nossa raiz no nível inicial (i.e. 0);
  3. Enquanto tivermos resultados, vamos inserir no próximo nível (i.e. 1) de nossa tabela temporária todos os nós cujos pais estejam entre os nós do nível anterior (i.e. 0);

Elaborando nosso script para trazer as patentes subordinadas à patente de Comandante, teríamos algo como o script abaixo.

USE tempdb;
GO
IF OBJECT_ID('tempdb..#Subordinados') IS NOT NULL
DROP TABLE #Subordinados;
GO
-- Criar a tabela temporária
CREATE TABLE #Subordinados (
	patente_id INT PRIMARY KEY,
	nivel INT NOT NULL,
	UNIQUE CLUSTERED(nivel,patente_id)
);
-- Declarar e iniciar a variável
DECLARE @nivel INT;
SET @nivel = 0;
-- Inserir a raiz
INSERT INTO #Subordinados(patente_id,nivel)
SELECT patente_id, @nivel
FROM dbo.Patentes
WHERE patente_id = 2 -- Comandante
-- Iniciar loop
WHILE(@@ROWCOUNT > 0)
BEGIN
	-- Avançar um nivel
	SET @nivel = @nivel + 1;
	-- Inserir subordinados (filhos)
	INSERT INTO #Subordinados(patente_id,nivel)
	SELECT Filho.patente_id, @nivel
	FROM #Subordinados AS Pai
	JOIN dbo.Patentes AS Filho
	ON Pai.patente_id = Filho.patente_superior_id
	WHERE Pai.nivel = @nivel - 1; -- Apenas nivel anterior
END
-- Retornar a hierarquia
SELECT patente_id, nivel
FROM #Subordinados;

Na criação da tabela temporária, acrescentei o índice único que, além de ajudar nos filtros da consulta, favorece a busca por nível na hierarquia. Esse tipo de índice também é chamado de breadth-first index. Depois, inicio a variável que controlará o nível da árvore e insiro o nó raiz que neste caso é a patente de Comandante. Então entro no loop, incremento o nível e insiro os filhos cujos pais pertençam ao nível anterior através de um JOIN da tabela temporária com a tabela base. Finalmente, retorno a hierarquia de subordinados à patente de Comandante. Para retornar não só a hierarquia, mas também a descrição de cada patente, basta realizar um JOIN da tabela resultante com a tabela base.

consulta_iterativa

Provavelmente, você irá reutilizar esse código ou terá que disponibilizar essa solução para outros. Para isso pode-se encapsular a lógica acima numa stored procedure ou numa função com valor de tabela (table-valued function). Como a estrutura que estou utilizando é pequena, optarei pela função, mas sugiro que valide o desempenho antes de descartar uma sp. Então, adaptando a solução anterior para retornar os tripulantes subordinados ao Tenente-Comandante Kelso resultaria numa função como a mostrada abaixo.

USE tempdb;
GO
IF OBJECT_ID('dbo.Subordinados') IS NOT NULL
DROP FUNCTION dbo.Subordinados;
GO
CREATE FUNCTION dbo.Subordinados
(@raiz AS INT) RETURNS @Subordinados TABLE
(
	tripulante_id INT PRIMARY KEY,
	nivel INT NOT NULL
	UNIQUE CLUSTERED(nivel, tripulante_id)
)
AS
BEGIN
-- Declarar e iniciar a variável
DECLARE @nivel INT;
SET @nivel = 0;
-- Inserir a raiz
INSERT INTO @Subordinados(tripulante_id, nivel)
SELECT tripulante_id, @nivel
FROM dbo.Tripulantes 
WHERE tripulante_id = @raiz;
-- Iniciar loop
WHILE(@@ROWCOUNT > 0)
BEGIN
	-- Avançar um nivel
	SET @nivel = @nivel + 1;
	-- Inserir subordinados (filhos)
	INSERT INTO @Subordinados(tripulante_id, nivel)
	SELECT Filho.tripulante_id, @nivel
	FROM @Subordinados AS Pai
	JOIN dbo.Tripulantes AS Filho
	ON Pai.tripulante_id = Filho.superior_id
	WHERE Pai.nivel = @nivel - 1; -- Apenas nivel anterior
END
-- Retornar a hierarquia
RETURN;
END
GO

Verificando a função com um JOIN com a tabela base da vez – dbo.Tripulantes – temos o seguinte resultado.

consulta_iterativa_funcao

SUPERIORES – MÉTODO ITERATIVO

Para obter os superiores, utilizarei a mesma lógica do processo de definir os subordinados, mas ao invés de descer níveis na hierarquia, vou subir. Como existe apenas um caminho do nó folha até o nó raiz, poderei utilizar mais este recurso como verificação. Logo, a função para obter a cadeia de comando do Oficial de Comunicações Farrell pareceria com o código abaixo.

USE tempdb;
GO
IF OBJECT_ID('dbo.Superiores') IS NOT NULL
DROP FUNCTION dbo.Superiores;
GO
CREATE FUNCTION dbo.Superiores
(@tripulante_id AS INT) RETURNS @Superiores TABLE
(
	tripulante_id INT PRIMARY KEY,
	nivel INT NOT NULL
)
AS
BEGIN
-- Declarar e iniciar a variável
DECLARE @nivel INT;
SET @nivel = 0;
-- Iniciar loop
WHILE(@tripulante_id IS NOT NULL)
BEGIN
	-- Inserir nó atual
	INSERT INTO @Superiores(tripulante_id, nivel) 
VALUES (@tripulante_id,@nivel);
	-- Avançar um nivel
	SET @nivel = @nivel + 1;
	-- Recuperar próximo gerente
	SET @tripulante_id = (SELECT superior_id
				  FROM dbo.Tripulantes
				  WHERE tripulante_id = @tripulante_id);

END
-- Retornar a hierarquia
RETURN;
END
GO

Para esta função, estou utilizando o fato de que existe apenas um superior direto para cada tripulante. Desta forma a codificação se torna bem mais simples. Ressalto que não estou validando o parâmetro de entrada, o que poderia gerar resultados inesperados ou erros. No entanto, como o objetivo aqui é mostrar uma ideia, deixo o tratamento de erros com você.

Verificando os resultados para esta função, temos o seguinte resultado:

iteracao_superior_consulta

CAMINHO HIERÁRQUICO – MÉTODO ITERATIVO

Para definir o caminho hierárquico é necessário varrer a hierarquia também. O início do caminho será o nó raiz da sub-árvore escolhida delimitado pelo separador. Então o caminho para a raiz será “\” + raiz+ “\” e para os próximos níveis será “caminho do pai” + nó + “\”. Desta forma, é possível reutilizar a função Subordinados e adaptá-la para trazer também o caminho hierárquico.

USE tempdb;
GO
IF OBJECT_ID('dbo.SubordinadosCH') IS NOT NULL
DROP FUNCTION dbo.SubordinadosCH;
GO
CREATE FUNCTION dbo.SubordinadosCH
(@raiz AS INT) RETURNS @Subordinados TABLE
(
	tripulante_id INT PRIMARY KEY,
	nivel INT NOT NULL,
	caminho VARCHAR(20)
	UNIQUE CLUSTERED(nivel, tripulante_id)
)
AS
BEGIN
-- Declarar e iniciar a variável
DECLARE @nivel INT;
SET @nivel = 0;
-- Inserir a raiz
INSERT INTO @Subordinados(tripulante_id, nivel, caminho)
SELECT	tripulante_id, @nivel, 
		'.' + CAST(tripulante_id AS VARCHAR) + '.'
FROM dbo.Tripulantes WHERE tripulante_id = @raiz;
-- Iniciar loop
WHILE(@@ROWCOUNT > 0)
BEGIN
	-- Avançar um nivel
	SET @nivel = @nivel + 1;
	-- Inserir subordinados (filhos)
	INSERT INTO @Subordinados(tripulante_id, nivel, caminho)
	SELECT	Filho.tripulante_id, @nivel, 
			Pai.caminho + CAST(Filho.tripulante_id AS VARCHAR) + '.'
	FROM @Subordinados AS Pai
	JOIN dbo.Tripulantes AS Filho
	ON Pai.tripulante_id = Filho.superior_id
	WHERE Pai.nivel = @nivel - 1; -- Apenas nivel anterior
END
-- Retornar a hierarquia
RETURN;
END
GO

Para definir o caminho, utilizei o atributo “tripulante_id”, mas você pode substituí-lo facilmente pelo nome do tripulante para seguir o caminho mais claramente. No entanto, fique alerta para o tamanho do atributo “caminho”, pois este pode crescer muito. Retornando o resultado da função para o Capitão Kirk, temos:

iterativo_caminho_consulta

Através da ordenação dos resultados pelo atributo “caminho”, fica visualmente fácil de enxergarmos a hierarquia. Utilizando este atributo novo, partiremos para a última solicitação.

APRESENTAÇÃO GRÁFICA – MÉTODO ITERATIVO

A apresentação gráfica de uma hierarquia seguirá a ordenação do novo atributo “caminho”, para organizar os resultados utiliza-se uma string – escolhida pelo usuário – repetida pelo número do nível do nó. Desta forma, temos o seguinte resultado:

iterativo_apresentacao_consulta

Como o caminho de cada nó filho é naturalmente maior que o do nó pai – por conter o nó pai –, a ordenação pelo “caminho” retorna perfeitamente a estrutura hierárquica. Utilizei o retorno dos resultados no formato texto para melhor ilustrar nossa apresentação.

Assim, encerro o método iterativo. Espero que tenha gostado! Na próxima parte irei demonstrar estas soluções utilizando CTEs recursivas. Até lá!

Anúncios

Um pensamento sobre “Trabalhando com dados hierárquicos – Parte II

  1. Pingback: Trabalhando com dados hierárquicos – Parte III | Comunidade SQL Server

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s