A divisão relacional (quando o AND e o OR não funcionam)

Boa Noite Pessoal,

Estou devendo várias postagens aqui no meu blog e hoje vou tentar sanar mais uma dívida do meu último Webcast. Dando continuidade à sessão de dicas hoje falarei sobre o problema da divisão relacional. Eu imagino que poucos já tenham ouvido falar sobre esse assunto e provavelmente a maioria que está lendo esse tópico não tem a menor idéia do que venha a ser esse termo. O termo é de fato pouco intuitivo, mas estou certo de que os problemas de divisão relacional são mais comuns do que o nome. Um dia desses respondi um problema de divisão relacional em uma Thread no fórum de SQL Server no Technet.

Uma operação de divisão normal submete-se um valor (dividendo) contra um outro valor (divisor) e obtém-se o resultado da divisão. Se fizermos o cálculo de 10 ÷ 2 obteremos o valor de 5 sendo 10 o valor do dividendo, 2 o valor do divisor e 5 o resultado da divisão. É possível que algumas divisões não sejam exatas, ou seja, gerem algum resto, mas a presença do resto é irrelevante para a analogia da matemática e de banco de dados.

A divisão de 10 por 2 resultou em 5. Quando fazemos a divisão de 10 por 2 estamos segmentando o dividendo 10 contra o divisor 2 e obtendo um determinado resultado igual a 5. Analogamente a um banco de dados é como se estivéssemos fazendo um SELECT em uma tabela chamada 10, e dividíssemos por um conjunto de registros chamado 2 e obtivéssemos o retorno de 5. Outra forma de expressar a divisão relacional refere-se à situação na qual divide-se um conjunto de registros de forma a filtrar registros em subconjuntos cujo o filtro atenda a mais de uma característica de forma exclusiva. Talvez essas frases não façam muito sentido e para facilitar um pouco o entendimento, usarei uma exemplificação. Nada melhor do que algo prático. As tabelas criadas não representam dados reais.

— Cria uma tabela de Clientes
CREATE TABLE tblClientes (ClienteID INT, NomeCliente VARCHAR(50))

— Popula a tabela de Clientes
INSERT INTO tblClientes VALUES (1,‘Wagner’)
INSERT INTO tblClientes VALUES (2,‘Sérgio’)
INSERT INTO tblClientes VALUES (3,‘Felipe’)
INSERT INTO tblClientes VALUES (4,‘Ricardo’)

— Cria uma tabela de carros
CREATE TABLE tblCarros (CarroID INT, ClienteID INT,
    CarroModelo VARCHAR(50), CarroMarca VARCHAR(20))

— Popula a tabela de carros
INSERT INTO tblCarros VALUES (01,01,‘Astra’,‘GM’)
INSERT INTO tblCarros VALUES (02,01,‘Fit’,‘Honda’)
INSERT INTO tblCarros VALUES (03,02,‘Astra’,‘GM’)
INSERT INTO tblCarros VALUES (04,02,‘207’,‘Peugeot’)
INSERT INTO tblCarros VALUES (05,02,‘Fusca’,‘Volks’)
INSERT INTO tblCarros VALUES (06,02,‘Mégane’,‘Renault’)
INSERT INTO tblCarros VALUES (07,03,‘C3’,‘Citroen’)
INSERT INTO tblCarros VALUES (08,03,‘Palio’,‘Fiat’)
INSERT INTO tblCarros VALUES (09,03,‘Polo’,‘Volks’)
INSERT INTO tblCarros VALUES (10,03,‘Fusca’,‘Volks’)
INSERT INTO tblCarros VALUES (11,04,‘Celta’,‘GM’)
INSERT INTO tblCarros VALUES (12,04,‘Palio Weekend’,‘Fiat’)
INSERT INTO tblCarros VALUES (13,04,‘Golf’,‘Volks’)

Para representar a divisão relacional no mundo dos bancos de dados, basta fazer uma pergunta bem simples: Quais são os clientes que tem carros da GM e da Volks e que carros são esses ? Visualmente sabemos que dos quatro clientes, apenas Sérgio e Ricardo de fato possui carros da GM e da Volks. Como representar isso em forma de consulta ? A irresistível vontade é de usar o IN.

SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE CR.CarroMarca IN (‘GM’,‘Volks’)

De fato essa é intuitivamente a solução quase que imediata, vejamos os resultados apresentados por essa consulta:

NomeCliente

CarroModelo

CarroMarca

Wagner

Astra

GM

Sérgio

Astra

GM

Sérgio

Fusca

Volks

Felipe

Polo

Volks

Ricardo

Celta

GM

Ricardo

Golf

Volks

Visualmente podemos perceber que os clientes Wagner e Felipe (marcados em cinza) não possuem carros da GM e da Volks. Wagner possui um carro da GM é verdade e da mesma forma Felipe possui um carro da Volks. Em todo caso nenhum dos dois possui carros das duas marcas como Sérgio e Ricardo e portanto não atendem à consulta inicial. Se a necessidade é de haver carros da GM e da Volks, o próximo impulso é utilizar a consulta abaixo:

SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE CR.CarroMarca = ‘GM’ AND CR.CarroMarca = ‘Volks’

Se a consulta acima for executada, nenhum resultado será retornado. Isso acontece porque o carro pode ser de uma marca somente, ou seja, ou o carro pertence à GM ou pertence a Volks. Como não é possível que um carro pertença às duas marcas não haverá nenhum carro que satisfaça aos predicados na cláusula WHERE e portanto nenhum registro é retornado.

Se você sentiu um nó na cabeça e não sabe como prosseguir para retornar o resultado desejado, eu acabo de apresentar-lhe o problema da divisão relacional. É justamente a ausência de um "OU" exclusivo na SQL que possibilita que esse "nó" apareça. É certo que existem alternativas, pois, seria vergonhoso se a SQL não tivesse alternativas para lidar com um problema tratado na álgebra relacional cuja as bases permitiram o surgimento da SQL. É claro que a resposta não é tão simples uma vez que não há um operador próprio para lidar com a divisão relacional. Aos que forem mais persistentes, sugiro continuar com mais algumas tentativas antes de prosseguir com a leitura das soluções.

Quando expus esse problema para alguns amigos DBAs em DB2, um dele expos uma solução que achei interessante. Aparentemente ela pode não ser performática, mas se propõe a resolver o problema e retornar os valores desejados

SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE
    CR.CarroMarca IN (‘GM’,‘Volks’)
    AND EXISTS (SELECT * FROM tblCarros AS CG
        WHERE CR.ClienteID = CG.ClienteID AND CarroMarca = ‘GM’)
    AND EXISTS (SELECT * FROM tblCarros AS CV
        WHERE CR.ClienteID = CV.ClienteID AND CarroMarca = ‘Volks’)

Confesso que quando fiz o Webcast eu não tinha levantado essa possibilidade. Ela é ANSI Compliance e funciona em outros SGDBs. O problema é o desempenho. Nas palavras desse DBA, "o problema é que são três consultas para retornar uma coisa só". Sim, eu concordo. Podemos diminuir os problemas de desempenho com índices sobre ClienteID e CarroMarca. Provalvelmente esses índices já existiriam, mas continuam sendo três consultas para retornar uma coisa só.

Uma outra alternativa compatível com a especificação ANSI é a utilização do operador INTERSECT para fazer a intersecção entre dois conjuntos. A operação de intersecção é aquela que retorna os membros de que estejam em todos os conjuntos. Sendo o conjunto A os clientes que possuem carros da GM e o conjunto B os clientes que possuem carros da Volks, a intersecção do conjunto A e B é o conjunto de clientes que possui carros da GM e da Volks.

— Selecionar todos que tem carros da GM
SELECT ClienteID FROM tblCarros WHERE CarroMarca = ‘GM’

INTERSECT — Faz a interseção

— Selecionar todos que tem carros da Volks
SELECT ClienteID FROM tblCarros WHERE CarroMarca = ‘Volks’

Para quem não conhece o operador INTERSECT, vale a pena lembrar que ele está na especifição ANSI 92 e que por uma razão que desconheço apenas no SQL Server 2005 é que finalmente ele foi contemplado no TSQL. A consulta acima fez a interseção dos clientes que possuem carros da GM e dos clientes que possuem carros da Volks. Para ficar uma solução mais completa é necessário efetuar o JOIN entre o resultado da intersecção e as tabelas de carros e de clientes. A consulta abaixo o faz através de uma Common Table Expression (CTE).

— Juntando tudo
;WITH ClientesGMVolks AS (
SELECT ClienteID FROM tblCarros WHERE CarroMarca = ‘GM’
INTERSECT — Faz a interseção
SELECT ClienteID FROM tblCarros WHERE CarroMarca = ‘Volks’)

SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN ClientesGMVolks AS GV ON CL.ClienteID = GV.ClienteID
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE CarroMarca IN (‘GM’,‘Volks’)

Uma outra solução que utiliza recursos do SQL Server 2005 é o uso do operador pivot para transformar as marcas em colunas. Como o interesse é apenas nas marcas GM e Volks, basta criar uma coluna para cada marca.

SELECT ClienteID, [GM], [Volks]
FROM (SELECT ClienteID, CarroMarca FROM tblCarros) AS ST
PIVOT (COUNT(CarroMarca) FOR CarroMarca IN ([GM], [Volks])) AS PT

Uma vez que haja uma coluna para contar quantos carros cada cliente tem da GM e uma coluna para contar quantos carros cada cliente tem da Volks, para saber que clientes tem carros da GM e da Volks, para filtrar essas colunas para que a quantidade seja superior a zero. Como o objetivo é recuperar não só os clientes, como também os nomes e os carros, a query precisa ser um pouco mais trabalhada.

— Selecione todos os clientes e seus carros
SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE

— Onde o cliente esteja na lista de clientes que tem carros da GM e Volks
CL.ClienteID IN (

SELECT ClienteID
FROM (SELECT ClienteID, CarroMarca FROM tblCarros) AS ST
PIVOT (COUNT(CarroMarca) FOR CarroMarca IN ([GM], [Volks])) AS PT
WHERE GM >= 1 AND Volks >= 1)

— E o carro seja da GM ou da Volks
AND CarroMarca IN (‘GM’,‘Volks’)

A solução que costumava utilizar antes de parar para é bem simples e funciona relativamente bem além de não depender de recursos como o INTERSECT ou o PIVOT. Isso garante uma portabilidade maior para essa solução. Antes de postá-la é interessante detalhar o raciocínio para chegar à solução.

SELECT ClienteID, COUNT(CarroMarca) As TotalMarcas
FROM tblCarros
WHERE CarroMarca IN (‘GM’,‘Volks’)
GROUP BY ClienteID

Essa consulta produz o seguinte resultado:

ClienteID

TotalMarcas

1

1

2

2

3

2

4

2

O cliente 1 (Wagner) de fato só possui um carro da GM e por isso o TotalMarcas retornou 1. Os clientes 2 e 4 (Sérgio e Ricardo) possuem um carro da GM e um carro da Volks cada. A consulta estaria correta senão fosse o fato de que o cliente 3 (Felipe) possui dois carros da Volks e por isso sua contagem foi igual a dois mesmo que ele não possua carros da GM. A contagem de marcas é feita com base no total de carros e não é feita distintamente. Se a contagem fosse distinta, Felipe poderia ter dois carros da Volks, mas a marca seria apenas uma. O uso do DISTINCT faz a contagem distintamente. Posteriormente basta juntar os resultados seja com um JOIN ou com uma Common Table Expression (CTE). Fiz o exemplo baseado em CTE, mas é possível utilizar o SELECT da CTE em uma subquery.

;WITH CGV AS (
— Conte os clientes e suas marcas distintamente
SELECT ClienteID, COUNT(DISTINCT CarroMarca) As TotalMarcas
FROM tblCarros

— Onde a marca do carro seja GM ou Volks
WHERE CarroMarca IN (‘GM’,‘Volks’)
GROUP BY ClienteID

— Onde apenas os clientes com duas marcas sejam escolhidos
— Como só a GM e Volks não há como ter mais de duas marcas
HAVING COUNT(DISTINCT CarroMarca) = 2)

SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE CarroMarca IN (‘GM’,‘Volks’) AND EXISTS
    (SELECT * FROM CGV WHERE CL.ClienteID = CGV.ClienteID)

Há uma última solução baseada em lógica reversa que embora eu não tenha apresentado no Webcast é bem interessante. Como o entendimento dessa solução não é tão simples, eu a postarei de forma desmembrada.

— Grava as marcas em uma tabela temporária
CREATE TABLE #Marcas (CarroMarca VARCHAR(20))
INSERT INTO #Marcas VALUES (‘GM’)
INSERT INTO #Marcas VALUES (‘Volks’)

Se a tabela estivesse desnormalizada, possivelmente haveria uma tabela com as marcas desejadas, como faz parte da solução obter um conjunto com as marcas desejadas, faz-se necessário gravá-las em um formato tabular visto que não há uma tabela de marcas de carro.

— Produz um plano cartesiano de todos os clientes e marcas desejadas
SELECT ClienteID, CarroMarca
FROM tblClientes CROSS JOIN #Marcas

O resultado do plano cartesiano gera um registro para cada combinação cliente e marca. Como há duas marcas de interesse (GM e Volks), é gerado dois registros para cada cliente (um com GM e outro com Volks).

SELECT ClienteID, CarroMarca
FROM tblClientes AS CL CROSS JOIN #Marcas AS M
WHERE NOT EXISTS
    (SELECT * FROM tblCarros AS CR
    WHERE CL.ClienteID = CR.ClienteID AND M.CarroMarca = CR.CarroMarca)
    ORDER BY ClienteID

O CROSS JOIN entre Clientes e Marcas produz todas as combinações hipotéticas entre Clientes e Marcas enquanto que a tabela de carros possui todas as combinações Clientes e Marcas que realmente existem. Se retirarmos as combinações Clientes e Marcas existentes do conjunto das combinações de Clientes e Marcas hipotéticas, teremos o conjunto de Clientes e Marcas que não foram utilizados. A consulta acima retorna o seguinte resultado:

ClienteID

CarroMarca

1

Volks

3

GM

Como o cliente 1 (Wagner) só possui carros da GM, a combinação Wagner – Volks é apenas hipotética já que ela não existe. O mesmo ocorre para a combinação Felipe (Cliente 3) e a marca GM. Os clientes 2 e 4 (Sérgio e Ricardo) não são retornados, pois, ambos possuem carros da Volks e da GM. As combinações referentes a esses clientes são de fato existentes e não apenas hipotéticas. 

SELECT DISTINCT ClienteID
FROM tblClientes AS CL CROSS JOIN #Marcas AS M
WHERE NOT EXISTS
    (SELECT * FROM tblCarros AS CR
    WHERE CL.ClienteID = CR.ClienteID AND M.CarroMarca = CR.CarroMarca)
    ORDER BY ClienteID

A consulta acima apenas retira a coluna CarroMarca da consulta anterior, pois, o que importa é saber os clientes que não atendam às duas marcas (GM e Volks). O uso do DISTINCT é necessário, pois, se um cliente não possuir nem carros da GM e nem carros da Volks, ele apresentará duas combinações e será portanto duplicado. O interesse não é descobrir qual das duas marcas o cliente não possui, mas sim que ele não possui as duas marcas. Uma vez que os clientes que não possuam carros da GM e da Volks sejam conhecidos, basta retirar esse resultado do conjunto de clientes. O resultado será o conjunto de clientes que possui carros da GM e da Volks conforme a consulta abaixo:

SELECT * FROM tblClientes WHERE ClienteID
NOT IN (
    SELECT DISTINCT ClienteID
    FROM tblClientes AS CL CROSS JOIN #Marcas AS M
    WHERE NOT EXISTS
    (SELECT * FROM tblCarros AS CR
    WHERE CL.ClienteID = CR.ClienteID AND M.CarroMarca = CR.CarroMarca))

O resultado exibirá apenas os clientes 2 e 4, pois, são os únicos clientes que possuem carros da GM e da Volks. O código baseado em lógica reversa (foram dois NOT EXISTS) é didático, mas da forma que foi exposto está cheio de práticas desaconselháveis como tabelas temporárias e o degradador NOT IN. O mesmo código pode ser escrito de uma forma um pouco mais performática.

;WITH

— Informa as marcas desejadas
MarcasDesejadas (CarroMarca) AS
(SELECT ‘GM’ UNION ALL SELECT ‘Volks’),

— Localiza todos os clientes que não tenham essas marcas
CSGV (ClienteID) AS

(SELECT DISTINCT ClienteID
FROM tblClientes AS CL CROSS JOIN MarcasDesejadas AS M
WHERE NOT EXISTS
    (SELECT * FROM tblCarros AS CR
    WHERE CL.ClienteID = CR.ClienteID AND M.CarroMarca = CR.CarroMarca))

— Retorna todos os clientes e seus carros que não estejam na lista CSGV
SELECT NomeCliente, CarroModelo, CarroMarca
FROM tblClientes AS CL
    INNER JOIN tblCarros AS CR ON CL.ClienteID = CR.ClienteID
WHERE CarroMarca IN (SELECT CarroMarca FROM MarcasDesejadas)
AND NOT EXISTS
    (SELECT * FROM CSGV WHERE CL.ClienteID = CSGV.ClienteID)

A alternativa da lógica reversa é um pouco mais díficil, mas não deixa de ser uma alternativa válida. Acredito que as alternativas apresentadas aqui sejam suficientes para resolver problemas comuns de divisão relacional (mesmo que não se saiba exatamente que esse é o nome do problema quando se depara com ele). O interessante de haver muitas alternativas é possibilitar ao implementador a escolha. É importante avaliar sempre a melhor das alternativas em termos de desempenho. Algumas alternativas podem apresentar um desempenho melhor ou pior que outras dependendo do volume de dados, da proposta de indexação, etc.

Espero que agora "divisão relacional" seja apenas um nome difícil de lembrar e não mais uma consulta difícil de fazer.

[ ]s,

Gustavo

Deixe uma resposta

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