A operação 'diferença' adiciona expressividade a uma linguagem de consulta que já inclui 'junção'?

19

O operador de diferença definida (por exemplo, EXCEPTem algumas variantes SQL) é um dos muitos operadores fundamentais da álgebra relacional. No entanto, existem alguns bancos de dados que não suportam diretamente o operador de diferença definida, mas que suportam LEFT JOIN(um tipo de junção externa) e, na prática, isso pode ser usado em vez de uma operação de diferença definida para obter o mesmo efeito.

Isso significa que o poder expressivo de uma linguagem de consulta é o mesmo, mesmo sem o operador de diferença definida, desde que o LEFT JOINoperador seja mantido? Como alguém provaria esse fato?

Ken Li
fonte
1
Mostrar que eles têm o mesmo poder expressivo está mostrando que a operação de diferença pode ser construída com a operação de junção esquerda (e possivelmente outras operações no RA).
Sxd 6/03/12

Respostas:

14

Na álgebra relacional, primeiro forneceremos uma definição informal de junção esquerda (externa) e continuaremos a provar que renomear, seleção, junção e projeção podem criar diferença, assim como essa diferença, seleção e união podem ser usadas para construir junção esquerda (externa). Na verdade, acabaremos fazendo isso na ordem inversa: mostraremos como construir junções esquerdas usando diferenças e, em seguida, mostraremos como construir diferenças usando junções esquerdas.

Seja e S os esquemas ( R ' , T ) e ( T , S ' ) , respectivamente, onde R ' e S ' são os conjuntos de atributos de um esquema, mas não o outro, e T é o conjunto de atributos comuns.RS(R,T)(T,S)RST

Deixe ser o tuplo nula para o esquema S ' . Ou seja, é a tupla que consiste em todos os valores nulos para cada atributo de S ' . Então, definimos a junção externa esquerda da seguinte forma: é o conjunto de todas as tuplas ( r , t , s ) pertencentes ao esquema ( R , T , S ) onde ...w=(ϵ,ϵ,...,ϵ)SSR LEFT JOIN S(r,t,s)(R,T,S)

  1. é uma tupla em R ;(r,t)R
  2. (a) é uma tupla de S ou (b) s = w ;(t,s)Ss=w
  3. Se estiver no conjunto para s w , ( r , t , w ) não estará no conjunto.(r,t,s)sw(r,t,w)

Exemplo: 's esquema é ( A 1 , A 2 , A 3 ) , S ' esquema s é ( A 2 , A 3 , A 4 ) , e que têm que R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } e S = { ( 2 , 3 , 4 )R(A1,A2,A3)S(A2,A3,A4)R={(1,2,3),(4,5,6)} . Por (1) e (2) obtemos o resultado intermediário { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 1 , 2 , 3 , ϵ ) , ( 4 , 5 , 6 , ϵ ) } . Por (3) devemos remover ( 1 , 2S={(2,3,4),(2,3,6)}{(1,2,3,4),(1,2,3,6),(1,2,3,ϵ),(4,5,6,ϵ)} , uma vez que temos (por exemplo) ( 1 , 2 , 3 , 4 ) e s = 4 ε = w . Ficamos assim com { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) }(1,2,3,ϵ)(1,2,3,4)s=4ϵ=w{(1,2,3,4),(1,2,3,6),(4,5,6,ϵ)}, o resultado esperado para uma junção esquerda.

Teorema: R LEFT JOIN Sé equivalente a (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Prova: (R EQUIJOIN S)fornece tudo o que é exigido por (1) e (2a). Afirmamos que isso ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)nos dá tudo da forma (r, t, w)exigida por (2b) e (3).

Para ver isso, primeiro aviso de que (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)é o conjunto de todas as tuplas em para o qual não há nenhuma tupla correspondente S . Para ver isso, basta observar que, projetando os atributos comuns de R e S (o conjunto de atributos T ) e considerando a diferença, resta apenas todas e apenas as tuplas (com o esquema T ) representadas em R, mas não S . Pelo com R , recuperamos todas e apenas as tuplas em R que têm valores para atributos em T que estão presentes em R, mas não em SRSRSTTRSEQUIJOINRRTRS; ou seja, precisamente o conjunto de tuplas que reivindicamos até agora.

Em seguida, observe que o esquema de (((PROJECT_T R) DIFFERENCE (PROJECT_T S))é o mesmo que (ou seja, ( R , T ) ), enquanto o esquema de w é S . A operação é, por conseguinte, um produto cartesiano, nós obtemos todos os tuplos de forma a ( r , t , w ) , onde não há ( t , s ) em S que corresponde a ( R , t ) em R .R(R,T)wSJOIN(r,t,w)(t,s)S(r,t)R

Para ver que esse é precisamente o conjunto de tuplas que precisamos adicionar para R EQUIJOIN Sconstruir R LEFT JOIN S, considere o seguinte: por construção, (3) é satisfeito, pois R EQUIJOIN Snão pode conter se contiver ( r , t , w ) (caso contrário, a segunda parte que contém ( r , t , w ) seria uma contradição); se adicionássemos outro ( r , t , w ) não em , haveria um ((r,t,s)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)(r,t,w)(r,t,w)(r,t,w)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) em S que corresponde a ( R , t ) em R , e pela definição de, ( r , t , s ) seria também, uma contradição de (3). Isso completa a prova.(t,s)S(r,t)REQUIJOIN(r,t,s)R LEFT JOIN S

Agora mostramos que a junção esquerda pode ser usada para construir a diferença:

Teorema: R DIFFERENCE Sé equivalente aPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Prova: Note que aqui, e S ' estão vazios, uma vez que todos os atributos são compartilhados para fazer sentido. Primeiro, criamos uma nova relação a partir de S duplicando o atributo definido em S (manipulado por e ) para que ele consista em tuplas ( t , t ) no conjunto de atributos ( T , T ) onde t = t ' (manipulado por o ). A junção esquerda nos deixa com tuplas da forma ( t , t )RSDIFFERENCESSRENAMEJOIN(t,t)(T,T)t=tSELECT(t,t)onde ou t ' = w . Agora, para se livrar das entradas que também aparecem em S , devemos manter apenas as tuplas do formulário ( t , w ) , que é tratado pela parte externa . O último se livra do conjunto de atributos temporários T e nos deixa com a diferença em termos do esquema original.t=tt=wS(t,w)SELECTPROJECTT

Exemplo: Seja e S = { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 , 8 ) } . Primeiro obtemos S com o conjunto de atributos d T : { ( 3 , 4 )R={(1,2),(3,4),(5,6)}S={(3,4),(5,6),(7,8)}SRENAMET . Aoperação nos fornece o produto cartesiano com todos os nove pares possíveis; este conjunto não está escrito aqui por razões de formatação. Oentão compara isso com { ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) , ( 7 , 8 , 7 , 8 ) } . Ocom{(3,4),(5,6),(7,8)}JOINSELECT{(3,4,3,4),(5,6,5,6),(7,8,7,8)}LEFT JOIN fornece { ( 1 , 2 , ϵ , ϵ ) , ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) } . O resultadoé { ( 1 , 2 , ϵ , ϵ ) } . Odá { ( 1 , 2 ) } , a resposta desejada.R{(1,2,ϵ,ϵ),(3,4,3,4),(5,6,5,6)}SELECT{(1,2,ϵ,ϵ)}PROJECT{(1,2)}

Patrick87
fonte
Edite sua postagem para usar a sintaxe do LaTeX. Comece colocando toda a sua fórmula nos símbolos $ (por exemplo, $ (1,2) $ torna-se ). Palavras-chave como select devem ser colocadas em `(por exemplo,` SELECT` se torna ). (1,2)SELECT
Raphael
@ Rafael Obrigado por apontar que eu deveria estar usando o LaTeX para isso. Fiz uma tentativa de boa fé no LaTeX'ing the math e backtick'inging the code ... por favor, deixe-me saber se há mais alguma coisa que devo fazer. Obrigado novamente!
precisa saber é o seguinte
Ótimo, obrigado! Você pode considerar $ $ ... $ $ para criar peças de matemática recuadas (não embutidas). Isso geralmente pode melhorar a legibilidade se usado corretamente. MathJax também suporta equações numeradas, mas não tenho certeza de como fazer isso.
Raphael
Eu acho que sua lógica está com defeito aqui. Você está usando DIFFERENCEpara definir LEFT JOINe, em seguida, LEFT JOINpara expressar DIFFERENCE, concluindo que o SQL pode ficar sem ele. Para que isso seja válido, você deve expressar LEFT JOINem termos de operadores que não sejamDIFFERENCE e, em seguida, provar que DIFFERENCEé equivalente a ele.
Janoma
@Janoma, acho que não é necessário ... estamos tentando mostrar que a diferença pode ser expressa em termos de junções esquerdas, portanto, uma junção esquerda em funcionamento é assumida. Pense nisso: se o que você está dizendo tiver mérito, eu poderia afirmar que LEFT JOIN é a operação "fundamental" ou "necessária" e exigir que você defina DIFERENÇA em termos de outros operadores, mas não LEFT JOIN. Eu mostrei que cada um pode simular o outro, portanto, nem é mais ou menos "fundamental" que o outro ... o que torna a DIFERENÇA especial? Em prop. lógica, NOT e AND são completos, como são OR e NOT; você não precisa dos três.
precisa saber é o seguinte
-1

LEFT JOIN, conforme implementado pelo SQL, não produz relações como resultado (porque alguns atributos do resultado não terão valor).

Ergo, LEFT JOIN, conforme implementado pelo SQL, não é uma contrapartida direta de nenhum operador de álgebra relacional.

Portanto, o operador de diferença relacional não pode ser expresso em termos de LEFT JOIN (porque LEFT JOIN não pode fazer parte da álgebra relacional, porque LEFT JOIN produz algo que não é uma relação, violando o fechamento da álgebra).

Qualquer conjunto de operadores primitivos de uma álgebra relacional que satisfaça o fechamento que eu conheço sempre inclui a diferença relacional ou a semidiferença relacional.

Erwin Smout
fonte