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

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?

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.$R$$S$$(R', T)$$(T, S')$$R'$$S'$$T$

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 = (\epsilon, \epsilon, ..., \epsilon)$$S'$$S'$R 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)$$S$$s = w$
3. Se estiver no conjunto para s ≠ w , ( r , t , w ) não estará no conjunto.$(r, t, s)$$s \neq w$$(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$$(A_{1}, A_{2}, A_{3})$$S$$(A_{2}, A_{3}, A_{4})$$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 , $S = \{(2, 3, 4), (2, 3, 6)\}$$\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$ , 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, \epsilon)$$(1, 2, 3, 4)$$s = 4 \neq \epsilon = w$$\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$, 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 $R$$S$$R$$S$$T$$T$$R$$S$EQUIJOIN$R$$R$$T$$R$$S$; 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)$$w$$S'$JOIN$(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)$$R$EQUIJOIN$(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 ′$R'$$S'$DIFFERENCE$S$$S$RENAMEJOIN$(t, t')$$(T, T')$$t = t'$SELECT$(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=t'$$t'=w$$S$$(t, w)$SELECTPROJECT$T'$

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)\}$$S$RENAME$T'$ . 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, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$SELECT$\{(1, 2, \epsilon, \epsilon)\}$PROJECT$\{(1, 2)\}$

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.