¿La operación 'diferencia' agrega expresividad a un lenguaje de consulta que ya incluye 'unirse'?

19

El operador de diferencia de conjuntos (p. Ej., EXCEPTEn algunas variantes de SQL) es uno de los muchos operadores fundamentales del álgebra relacional. Sin embargo, hay algunas bases de datos que no admiten el operador de diferencia de conjunto directamente, pero que admiten LEFT JOIN(una especie de unión externa), y en la práctica esto se puede usar en lugar de una operación de diferencia de conjunto para lograr el mismo efecto.

¿Significa esto que el poder expresivo de un lenguaje de consulta es el mismo incluso sin el operador de diferencia establecida, siempre y cuando LEFT JOINse mantenga el operador? ¿Cómo se probaría este hecho?

Ken Li
fuente
1
Para demostrar que tienen el mismo poder expresivo está demostrando que la operación de diferencia se puede construir con la operación de unión izquierda (y posiblemente otras operaciones en RA).
sxd

Respuestas:

14

En álgebra relacional, primero proporcionaremos una definición informal de unión izquierda (externa), y procederemos a demostrar que, renombrar, seleccionar, unir y proyectar puede construir la diferencia, así como esa diferencia, selección y unión pueden usarse para construir izquierda combinación externa. En realidad, terminaremos haciéndolo en el orden inverso: mostraremos cómo construir uniones izquierdas usando diferencias, y luego mostraremos cómo construir diferencias usando uniones izquierdas.

Deje que y tengan esquemas y , respectivamente, donde y son los conjuntos de atributos en un esquema pero no en el otro, y es el conjunto de atributos comunes.RS(R,T)(T,S)RST

Sea la tupla nula para el esquema . Es decir, es la tupla que consiste en todos los valores nulos para cada atributo de . Luego, definimos la unión externa izquierda de la siguiente manera: es el conjunto de todas las tuplas pertenecen al esquema donde ...w=(ϵ,ϵ,...,ϵ)SSR LEFT JOIN S(r,t,s)(R,T,S)

  1. (r,t) es una tupla en ;R
  2. (a) es una tupla de o (b) ;(t,s)Ss=w
  3. Si está en el conjunto para , entonces no está en el conjunto.(r,t,s)sw(r,t,w)

Ejemplo: el esquema de es , el esquema de es , y tenemos eso y . Por (1) y (2) obtenemos el resultado intermedio . Por (3) debemos eliminar , ya que tenemos (por ejemplo) yR(A1,A2,A3)S(A2,A3,A4)R={(1,2,3),(4,5,6)}S={(2,3,4),(2,3,6)}{(1,2,3,4),(1,2,3,6),(1,2,3,ϵ),(4,5,6,ϵ)}(1,2,3,ϵ)(1,2,3,4) . Por lo tanto, nos quedamos con { ( 1 , 2 , 3s=4ϵ=w , el resultado esperado para una unión izquierda.{(1,2,3,4 4),(1,2,3,6 6),(4 4,5 5,6 6,ϵ)}

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

Prueba: (R EQUIJOIN S)nos da todo lo requerido por (1) y (2a). Afirmamos que ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)nos da todo el formulario (r, t, w)requerido por (2b) y (3).

Para ver esto, primero aviso de que (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)es el conjunto de todas las tuplas en para el que no hay ninguna tupla correspondiente en S . Para ver eso, es suficiente tener en cuenta que al proyectar los atributos comunes de R y S (el conjunto de atributos T ) y tomar la diferencia, uno queda con todas y solo aquellas tuplas (con esquema T ) que están representadas en R pero no S . Por el con R , recuperamos todas y solo aquellas tuplas en que tienen valores para atributos en que están presentes en pero no enRSRSTTRSEQUIJOINRRTRS; a saber, precisamente el conjunto de tuplas que hemos reclamado hasta ahora.

A continuación, observe que el esquema de (((PROJECT_T R) DIFFERENCE (PROJECT_T S))es el mismo que el de (es decir, ), mientras que el esquema de es . El por lo tanto, la operación es un producto cartesiano, que obtenemos todas las tuplas de la forma donde no hay en que corresponde a en .R(R,T)wSJOIN(r,t,w)(t,s)S(r,t)R

Para ver que este es precisamente el conjunto de tuplas que necesitamos agregar para R EQUIJOIN Sconstruir R LEFT JOIN S, considere lo siguiente: por construcción, (3) se cumple, ya R EQUIJOIN Sque no puede contener si contiene (si lo hiciera, entonces la segunda parte que contiene sería una contradicción); si tuviéramos que agregar otro no esté dentro , entonces habría un en correspondiente a en , y por la definición de , también estaría en , una contradicción de (3). Esto completa la prueba.(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)(t,s)S(r,t)REQUIJOIN(r,t,s)R LEFT JOIN S

Ahora mostramos que la unión izquierda se puede usar para construir la diferencia:

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

Prueba: tenga en cuenta que aquí, y están vacíos, ya que todos los atributos se comparten para que tengan sentido. Primero, creamos una nueva relación a partir de duplicando el conjunto de atributos en (manejado por y ) para que conste de tuplas en el conjunto de atributos donde (manejado por el ). La unión izquierda nos deja con tuplas de la forma donde o . Ahora, para deshacernos de las entradas que también aparecen en , debemos conservar solo las tuplas del formularioRSDIFFERENCESSRENAMEJOIN(t,t)(T,T)t=tSELECT(t,t)t=tt=wS(t,w), que es manejado por el más externo SELECT. El último PROJECTelimina el conjunto de atributos temporales y nos deja con la diferencia en términos del esquema original.T

Ejemplo: Sea y . Primero obtenemos con el conjunto de atributos d : . La operación nos da el producto cartesiano con los nueve emparejamientos posibles; este conjunto no está escrito aquí por razones de formateo. La entonces pares esto a . El con da . El da . El daR={(1,2),(3,4 4),(5 5,6 6)}S={(3,4 4),(5 5,6 6),(7 7,8)}SRENAMET{(3,4 4),(5 5,6 6),(7 7,8)}JOINSELECT{(3,4 4,3,4 4),(5 5,6 6,5 5,6 6),(7 7,8,7 7,8)}LEFT JOINR{(1,2,ϵ,ϵ),(3,4 4,3,4 4),(5 5,6 6,5 5,6 6)}SELECT{(1,2,ϵ,ϵ)}PROJECT{(1,2)}, la respuesta deseada.

Patrick87
fuente
Edite su publicación para usar la sintaxis de LaTeX. Comience encerrando toda su fórmula en símbolos $ (por ejemplo, $ (1,2) $ se convierte en ). Las palabras clave como select deben ponerse en `(por ejemplo,` SELECT` se convierte en ). (1,2)SELECT
Raphael
@Raphael Gracias por señalar que debería estar usando LaTeX para esto. He hecho un intento de buena fe para hacer que LaTeX calcule las matemáticas y modifique el código ... hágamelo saber si hay algo más que deba hacer. ¡Gracias de nuevo!
Patrick87
¡Muchas gracias! Es posible que desee considerar $ $ ... $ $ para las piezas de matemáticas creadas con sangría (no en línea). Esto a menudo puede mejorar la legibilidad si se usa correctamente. MathJax también admite ecuaciones numeradas, pero no estoy seguro de cómo hacerlo.
Raphael
Creo que tu lógica es defectuosa aquí. Está utilizando DIFFERENCEpara definir LEFT JOIN, y luego utiliza LEFT JOINpara expresar DIFFERENCE, concluyendo que SQL puede prescindir de él. Para que esto sea válido, debe expresarse LEFT JOINen términos de operadores distintos deDIFFERENCE , y luego demostrar que DIFFERENCEes equivalente a él.
Janoma
@ Janan No creo que sea necesario ... estamos tratando de mostrar que la diferencia se puede expresar en términos de uniones izquierdas, por lo que se supone una unión izquierda funcional. Piénselo: si lo que está diciendo tiene mérito, podría afirmar que LEFT JOIN es la operación "fundamental" o "necesaria", y exigir que defina la DIFERENCIA en términos de los otros operadores, pero no LEFT JOIN. He demostrado que cada uno puede simular al otro, por lo que ninguno es más o menos "fundamental" que el otro ... ¿qué hace que la DIFERENCIA sea especial? En prop. lógica, NOT y AND están completas, como OR y NOT; No necesitas los tres.
Patrick87
-1

IZQUIERDA ÚNICA implementada por SQL, no produce relaciones como resultado (porque algunos atributos del resultado no tendrán un valor).

Ergo, LEFT JOIN implementado por SQL, no es una contraparte directa de ningún operador de álgebra relacional.

Ergo, el operador de diferencia relacional no puede expresarse en términos de LEFT JOIN (porque LEFT JOIN no puede ser parte del álgebra relacional, esto se debe a que LEFT JOIN produce algo que no es una relación, lo que viola el cierre del álgebra).

Cualquier conjunto de operadores primitivos de un álgebra relacional que satisfaga el cierre que conozco, siempre incluye la diferencia relacional o la semidiferencia relacional.

Erwin Smout
fuente