relacional - relational algebra database
¿se puede ver la combinación natural como un subconjunto de la combinación equitativa y la unión theta? (2)
Probablemente se refirió a lo siguiente:
Las uniones naturales son equi-uniones donde la comparación de igualdad se aplicará a los atributos que tienen el mismo nombre.
TABLE_A JOIN TABLE_B ON TABLE_A.X = TABLE_B.Y es un equi-join, pero no una combinación natural.
Por lo tanto, todas las uniones naturales son de hecho equi-uniones, pero no todas las equi-uniones son uniones naturales.
Por lo tanto, el conjunto de todas las uniones naturales posibles entre tablas es un subconjunto (a menudo adecuado) del conjunto de todas las equi-combinaciones posibles entre esas mismas tablas.
Tengo una pregunta con respecto al álgebra relacional y cómo theta-join, equi-join y natural-join se pueden clasificar en relación entre sí.
En un comentario sobre stackoverflow.com, sqlvogel cita a EF Codd , el científico informático que inventó el modelo relacional para la gestión de bases de datos, "[el] Natural [-join] es un subconjunto de Equi [-join] que es un subconjunto de Theta [- unirse]." * ( stackoverflow.com recuperado el 12 de febrero a las 9:01 PM).
Entiendo cómo se puede ver la combinación equitativa como un subconjunto de theta-join. Ambos se unen y ambos usan un número fijo de atributos, pero el equi-join está restringido a usar el operador de igualdad (=). La combinación natural por otro lado es el conjunto de todas las combinaciones de tuplas (no un número fijo de atributos) al unir dos relaciones y restringirse al uso del operador de igualdad (=). Equi-join y theta-join difieren en qué operadores pueden usar, pero veo que la combinación natural es diferente en una dimensión diferente ya que no necesita ningún atributo en su definición.
¿Alguien puede arrojar algo de luz sobre este tema?
* No puedo encontrar la fuente original para esta cita.
Resumen: las uniones naturales son un subconjunto de equi-combinaciones, si ignoras los detalles técnicos y te enfocas en la intención de la unión. Si incluye estos detalles técnicos, las cosas se complican mucho más rápido. Entonces, una unión natural puede ser un subconjunto de equi-join, dependiendo de las definiciones utilizadas.
En mi opinión, realmente depende de qué se tome el subconjunto.
Editar: Este párrafo está muy expandido en la sección de álgebra relacional de Wikipedia a continuación, pero se dejó aquí para preservar el contexto de la respuesta original.
Si estamos hablando de lo que las operaciones hacen técnicamente, entonces equi-join es claramente un subconjunto de theta-join, ya que solo puede unirse a la igualdad, mientras que theta puede unirse a mayor que las comparaciones, menos que las comparaciones, etc. Además , tanto equi-join como theta-join operan en atributos arbitrarios. Sin embargo, la unión natural es diferente a las otras dos uniones a este respecto. Estrictamente hablando, equi-join y theta-join solo pueden operar en relaciones que no comparten nombres de atributos comunes. La combinación natural unirá dos relaciones en la igualdad de los nombres de atributos comunes y "soltará" los atributos duplicados. Creo que esta es la definición con la que te encuentras cuando dices que las uniones naturales son diferentes, en cuyo caso estás en lo cierto.
Si estamos hablando de lo que las operaciones hacen semánticamente (o prácticamente), entonces diría que son subconjuntos el uno del otro. Theta-join se une en función de una variedad de condiciones booleanas entre atributos arbitrarios. Equi-join está restringido a solo una comparación de igualdad. La unión natural está restringida porque los atributos no son arbitrarios, deben compartir nombres.
Editar: una respuesta más técnica:
Descargo de responsabilidad: asumo el conocimiento de nivel de primer año de la teoría de conjuntos.
Definiciones
Para una respuesta técnica, necesitamos definiciones técnicas. Entonces, ¿qué definiciones técnicas respetamos? Si usas el álgebra relacional de Google, en la primera página probablemente obtendrás enlaces de Wikipedia, videos de Youtube y notas de conferencias de varios cursos de bases de datos universitarias (y, en particular, ningún enlace a un documento de Codd). Todos están de acuerdo en los "aspectos básicos" de la selección, proyección, uniones, etc. Pero, en algunos detalles, difieren, como por ejemplo:
- ¿Permitimos que theta-joins ocurra entre dos relaciones que comparten un nombre de atributo, y si es así, cómo lo tratamos?
- En selecciones y theta-joins, ¿qué predicados y proposiciones están permitidos?
- ¿Se pueden realizar uniones naturales cuando ningún atributo comparte un nombre (en cuyo caso se degenera en un producto cartesiano)?
Voy a ver dos definiciones de álgebra relacional: Wikipedia y Codd .
Álgebra relacional de Wikipedia
Comienzo con el artículo de álgebra relacional de Wikipedia , ya que está bastante cerca de lo que las universidades tienden a enseñar hoy en día en un curso introductorio de base de datos. Este artículo, sin embargo, no cita sus fuentes de manera efectiva, especialmente en los bits técnicos. También es bastante matemático. Como tal, realmente no recomiendo este artículo para cualquiera que esté buscando álgebra relacional por primera vez.
Unión natural
Wikipedia define una unión natural como:
[...] el conjunto de todas las combinaciones de tuplas en R y S que son iguales en sus nombres de atributos comunes.
También,
Normalmente se requiere que R y S tengan al menos un atributo común, pero si esta restricción se omite, y R y S no tienen atributos comunes, entonces la unión natural se convierte exactamente en el producto cartesiano.
Como, como veremos, Codd requiere un nombre de atributo común, vamos a ir con la definición que permite una unión natural degenerada. Tenga en cuenta que los atributos comunes solo aparecen una vez en la relación resultante. Entonces, si la relación R tiene m atributos, la relación S tiene n atributos y tienen x atributos en común ( x ≥ 0, x ≤ m , x ≤ n ), entonces la relación resultante R NATURAL JOIN S tiene m + n - x atributos .
Theta-join y equi-join
Wikipedia define una θ-unión entre las relaciones R y S como una unión que satisface la θ-relación a θ b o a θ v , donde a y b son nombres de atributos, v es un valor constante y θ es uno de {<, ≤ =, ≥,>}.
También,
El resultado de esta operación consiste en todas las combinaciones de tuplas en R y S que satisfacen la relación θ. El resultado de θ-join se define solo si los encabezados de S y R son disjuntos, es decir, no contienen un atributo común.
Un equi-join es simplemente un θ-join cuya operación es "=".
Relación entre las uniones
Simplemente por definición, equi-join es un subconjunto de theta-join.
Si R y S tienen atributos en común, entonces un theta-join no puede operar directamente en las relaciones. Por lo tanto, las uniones naturales pueden producir relaciones que theta-join no puede. Si no tienen atributos en común, la unión natural degenera en un producto cartesiano. Theta-join ahora es legal. Podrá unirse, pero puede producir resultados diferentes dependiendo de la relación θ particular utilizada. En el caso general, theta-joins puede producir relaciones que la unión natural no puede.
En conclusión, tenemos que las equi-uniones son un subconjunto de theta-joins, las uniones naturales no son subconjuntos de theta-joins, y theta-joins tampoco son subconjuntos de combinaciones naturales (esto es lo que quise decir originalmente cuando dije eran diferentes). Se deduce que las uniones naturales no son un subconjunto de equi-combinaciones .
Álgebra relacional original de Codd 1
Ahora, vayamos a la fuente y veamos un artículo anterior de Codd . Es cierto que esta es la primera vez que lo leo, así que no dude en señalar cualquier error que haya cometido. Sin embargo, en mi opinión, este documento es mucho más fácil de leer que el artículo de Wikipedia si descarta cualquier presuposición que pueda tener sobre el álgebra relacional.
Algunas notas:
- En este documento, Codd en realidad nunca define sus operaciones como "álgebra".
- Codd se centra en las relaciones binarias (es decir, relaciones con solo dos atributos), pero muestra al final de la sección 2.1.3 que las relaciones de mayor grado son fácilmente reducibles a las relaciones binarias.
- En realidad, la única operación que es idéntica a la definición de Wikipedia es la proyección.
Dominios y Roles
En la sección 1.3, una relación se define como un subconjunto del producto cartesiano de una cantidad finita de conjuntos. Cada uno de estos conjuntos se llama dominio y tiene un nombre de dominio 2 . Las relaciones pueden tener columnas con el mismo nombre de dominio (es decir, dos de las columnas provienen del mismo conjunto). En este caso, las columnas con nombres de dominio idénticos se pueden distinguir por un nombre de rol único. Por lo tanto, el nombre de atributo de Wikipedia es similar al nombre de dominio de Codd. Nombre_royal 3 .
Une
En la sección 2.1.3, Codd define una unión como sea posible solo si las dos relaciones comparten un dominio. Además, declara,
Una relación binaria R se puede unir con una relación binaria S si existe una relación ternaria U tal que π 12 ( U ) = R y π 23 ( U ) = S. Cualquier relación ternaria de este tipo se denomina unión de R con S. Si R , S son relaciones binarias tales que π 2 ( R ) = π 1 ( S ), entonces R se puede unir con S.
Eso es bastante teórico, pero lo que esencialmente significa es que una unión solo puede ocurrir entre R y S si las relaciones R y S pueden recuperarse completamente de la relación unida. Esto implica que el conjunto de valores de la columna que se está uniendo debe ser el mismo en R y S.
Esto es más restrictivo que las uniones de SQL y las uniones definidas en el artículo de Wikipedia (combinación natural incluida).
Unión natural
Dado lo anterior, la definición de Natural Join se cae fácilmente:
R x S = {( a , b , c ): R ( a , b ) ⋀ S ( b , c )}
Restricciones
Tomaremos un desvío rápido de las uniones para ver la sección 2.1.5 que describe la Restricción. Es una operación similar a la Selección (como se define en Wikipedia) . Una relación R puede restringirse por la relación S de la siguiente manera: se forma una nueva relación, R '' , consiste en las tuplas de R donde un subconjunto del valor de su columna es un elemento de un subconjunto de columnas de S. No estoy seguro de haber hecho un buen trabajo explicando eso, así que aquí hay un SQL equivalente:
SELECT * FROM R
WHERE some_attributes IN (
SELECT some_comparable_attributes FROM S)
Theta-join y equi-join
El documento no proporciona una definición explícita para theta y equi-join. Además, no parece posible definir simplemente un theta-join (aunque corrígeme si me equivoco). Sin embargo, podemos definir una serie de operaciones en las relaciones R y S , que dan un resultado bastante idéntico 4 a la combinación equitativa definida en el artículo de Wikipedia.
Aprovecharemos el hecho de que solo tenemos que considerar las relaciones binarias. Entonces, deje que R tenga las columnas ( a , b ) y S tenga las columnas ( b , c ). No son necesariamente unibles ya que π b ( R ) no es necesariamente igual a π b ( S ). Luego, forme las relaciones R '' restringiendo R con S con respecto al atributo b , y S'' restringiendo S por R nuevamente con respecto al atributo b . Ahora, π b ( R '' ) = π b ( S'' ), entonces podemos tomar la unión natural de R '' y S'' .
Relación entre las uniones
Se cae de la definición de equi-join dada, pero si π b ( R ) = π b ( S ), entonces el equi-join es equivalente a la Natural Join. Por lo tanto, la unión natural es un subconjunto de la combinación equitativa .
Lectura adicional: encuentro que esta respuesta brinda información más útil sobre theta-joins y las álgebras relacionales.
Notas a pie de página
No estoy seguro de cuán justo es llamar al álgebra relacional original de este Codd cuando descubrí en una respuesta de CS.SE que dos años más tarde, definiría un álgebra relacional muy similar a la de Wikipedia (aunque afortunadamente permitió ≠ en θ -juntos). Sin embargo, un punto importante de esta respuesta es enfatizar que existen diferentes definiciones de álgebra relacional, y se debe establecer una definición antes de que se pueda hacer cualquier tipo de prueba.
Estoy pasando por alto el paso donde primero se define la posición del dominio y la distinción entre una relación y una relación.
Codd define un identificador de generación adicional, que volveremos a pasar por alto.
En la teoría de Codd, las columnas a unir deben tener el mismo dominio. Esto no es un requisito de acuerdo con la teoría presentada en Wikipedia, aunque en realidad, no deberías hacer ese tipo de uniones de todos modos.