Álgebra relacional

Teoría de bases de datos relacionales

En teoría de bases de datos , el álgebra relacional es una teoría que utiliza estructuras algebraicas para modelar datos y definir consultas sobre ellos con una semántica bien fundamentada . La teoría fue introducida por Edgar F. Codd .

La principal aplicación del álgebra relacional es proporcionar una base teórica para las bases de datos relacionales , en particular los lenguajes de consulta para dichas bases de datos, entre los que se destaca SQL . Las bases de datos relacionales almacenan datos tabulares representados como relaciones . Las consultas sobre bases de datos relacionales también suelen devolver datos tabulares representados como relaciones.

El objetivo principal del álgebra relacional es definir operadores que transformen una o más relaciones de entrada en una relación de salida. Dado que estos operadores aceptan relaciones como entrada y producen relaciones como salida, se pueden combinar y utilizar para expresar consultas complejas que transformen múltiples relaciones de entrada (cuyos datos se almacenan en la base de datos) en una única relación de salida (los resultados de la consulta).

Los operadores unarios aceptan una única relación como entrada. Algunos ejemplos son los operadores para filtrar determinados atributos (columnas) o tuplas (filas) de una relación de entrada. Los operadores binarios aceptan dos relaciones como entrada y las combinan en una única relación de salida. Por ejemplo, tomar todas las tuplas que se encuentran en cualquiera de las relaciones ( unión ), eliminar las tuplas de la primera relación que se encuentran en la segunda relación ( diferencia ), extender las tuplas de la primera relación con las tuplas de la segunda relación que cumplan determinadas condiciones, etcétera.

También se pueden incluir otros operadores más avanzados, donde la inclusión o exclusión de ciertos operadores da lugar a una familia de álgebras.

Introducción

El álgebra relacional recibió poca atención fuera de las matemáticas puras hasta la publicación del modelo relacional de datos de EF Codd en 1970. Codd propuso dicha álgebra como base para los lenguajes de consulta de bases de datos.

El álgebra relacional opera con conjuntos homogéneos de tuplas, donde comúnmente interpretamos que m es el número de filas en una tabla y n es el número de columnas. Todas las entradas en cada columna tienen el mismo tipo. ${\displaystyle S=\{(s_{j1},s_{j2},...s_{jn})|j\in 1...m\}}$

Los cinco operadores primitivos del álgebra de Codd son la selección , la proyección , el producto cartesiano (también llamado producto vectorial o unión vectorial ), la unión de conjuntos y la diferencia de conjuntos .

Operadores de conjuntos

El álgebra relacional utiliza la unión de conjuntos , la diferencia de conjuntos y el producto cartesiano de la teoría de conjuntos , pero agrega restricciones adicionales a estos operadores.

Para la unión de conjuntos y la diferencia de conjuntos, las dos relaciones involucradas deben ser compatibles con la unión , es decir, las dos relaciones deben tener el mismo conjunto de atributos. Debido a que la intersección de conjuntos se define en términos de la unión de conjuntos y la diferencia de conjuntos, las dos relaciones involucradas en la intersección de conjuntos también deben ser compatibles con la unión.

Para que se defina el producto cartesiano, las dos relaciones involucradas deben tener encabezados disjuntos, es decir, no deben tener un nombre de atributo común.

Además, el producto cartesiano se define de forma diferente a la de la teoría de conjuntos , en el sentido de que las tuplas se consideran "superficiales" a los efectos de la operación. Es decir, el producto cartesiano de un conjunto de n -tuplas con un conjunto de m -tuplas produce un conjunto de ( n  +  m ) -tuplas "aplanadas" (mientras que la teoría de conjuntos básica habría prescrito un conjunto de 2-tuplas, cada una de las cuales contendría una n -tupla y una m -tupla). De manera más formal, R × S se define de la siguiente manera:

$${\displaystyle R\times S:=\{(r_{1},r_{2},\dots ,r_{n},s_{1},s_{2},\dots ,s_{m})|(r_{1},r_{2},\dots ,r_{n})\in R,(s_{1},s_{2},\dots ,s_{m})\in S\}}$$

La cardinalidad del producto cartesiano es el producto de las cardinalidades de sus factores, es decir, | R × S | = | R | × | S |.

Proyección

Una proyección ( Π ) es una operación unaria escrita como donde es un conjunto de nombres de atributos. El resultado de dicha proyección se define como el conjunto que se obtiene cuando todas las tuplas en R se restringen al conjunto . ${\displaystyle \Pi _{a_{1},\ldots ,a_{n}}(R)}$ ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$

Nota: cuando se implementa en el estándar SQL , la "proyección predeterminada" devuelve un multiconjunto en lugar de un conjunto, y la proyección Π para eliminar datos duplicados se obtiene mediante la adición de la DISTINCTpalabra clave .

Selección

Una selección generalizada (σ) es una operación unaria escrita como donde φ es una fórmula proposicional que consta de átomos como se permite en la selección normal y los operadores lógicos ( y ), ( o ) y ( negación ). Esta selección selecciona todas aquellas tuplas en R para las que φ es válido. ${\displaystyle \sigma _{\varphi }(R)}$ ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

Para obtener una lista de todos los amigos o socios comerciales de una libreta de direcciones, la selección se puede escribir como . El resultado sería una relación que contenga todos los atributos de cada registro único donde isFriend sea verdadero o donde isBusinessContact sea verdadero. ${\displaystyle \sigma _{{\text{isFriend = true}}\,\lor \,{\text{isBusinessContact = true}}}({\text{addressBook}})}$

Rebautizar

Un cambio de nombre ( ρ ) es una operación unaria escrita como donde el resultado es idéntico a R excepto que el atributo b en todas las tuplas se renombra a un atributo a . Esto se usa simplemente para cambiar el nombre del atributo de una relación o de la relación misma. ${\displaystyle \rho _{a/b}(R)}$

Para cambiar el nombre del atributo "isFriend" a "isBusinessContact" en una relación, se podría utilizar . ${\displaystyle \rho _{\text{isBusinessContact / isFriend}}({\text{addressBook}})}$

También existe la notación, donde R se renombra a x y los atributos se renombran a . ^[1] ${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$ ${\displaystyle \{A_{1},\ldots ,A_{n}\}}$

Uniones y operadores similares a uniones

Unión natural

La unión natural (⨝) es un operador binario que se escribe como ( R ⨝ S ) donde R y S son relaciones . ^[a] El resultado de la unión natural es el conjunto de todas las combinaciones de tuplas en R y S que son iguales en sus nombres de atributos comunes. Como ejemplo, considere las tablas Employee y Dept y su unión natural: ^{[ cita requerida ]}

Tenga en cuenta que ni el empleado llamado Mary ni el departamento de Producción aparecen en el resultado.

Esto también se puede utilizar para definir la composición de las relaciones . Por ejemplo, la composición de Employee y Dept es su unión, como se muestra arriba, proyectada sobre todos los atributos excepto el común DeptName . En la teoría de categorías , la unión es precisamente el producto de la fibra .

La unión natural es posiblemente uno de los operadores más importantes, ya que es la contraparte relacional del operador lógico AND. Tenga en cuenta que si la misma variable aparece en cada uno de los dos predicados que están conectados por AND, entonces esa variable representa lo mismo y ambas apariciones siempre deben sustituirse por el mismo valor (esto es una consecuencia de la idempotencia del AND lógico). En particular, la unión natural permite la combinación de relaciones que están asociadas por una clave externa . Por ejemplo, en el ejemplo anterior, una clave externa probablemente se cumple desde Employee.DeptName hasta Dept.DeptName y luego la unión natural de Employee y Dept combina todos los empleados con sus departamentos. Esto funciona porque la clave externa se cumple entre atributos con el mismo nombre. Si este no es el caso , como en la clave externa de Dept. Manager a Employee . Name , entonces estas columnas deben renombrarse antes de tomar la unión natural. A este tipo de unión a veces también se le conoce como equijoin .

Más formalmente, la semántica de la unión natural se define de la siguiente manera:

donde Fun(t) es un predicado que es verdadero para una relación t (en el sentido matemático) si y solo si t es una función (es decir, t no asigna ningún atributo a múltiples valores). Por lo general, se requiere que R y S tengan al menos un atributo en común, pero si se omite esta restricción y R y S no tienen atributos en común, entonces la unión natural se convierte exactamente en el producto cartesiano.

La unión natural se puede simular con las primitivas de Codd de la siguiente manera. Suponga que c ₁ ,..., c _m son los nombres de atributos comunes a R y S , r ₁ ,..., r _n son los nombres de atributos únicos a R y s ₁ ,..., s _k son los nombres de atributos únicos a S . Además, suponga que los nombres de atributo x ₁ ,..., x _m no están ni en R ni en S . En un primer paso, los nombres de atributos comunes en S se pueden renombrar:

Luego tomamos el producto cartesiano y seleccionamos las tuplas que se van a unir:

Finalmente tomamos una proyección para deshacernos de los atributos renombrados:

θ-unirse y equiunirse

Considere las tablas Car y Boat , que enumeran los modelos de automóviles y barcos y sus respectivos precios. Suponga que un cliente desea comprar un automóvil y un barco, pero no desea gastar más dinero en el barco que en el automóvil. La unión θ (⋈ _θ ) en el predicado CarPrice ≥ BoatPrice produce los pares de filas aplanadas que satisfacen el predicado. Cuando se utiliza una condición donde los atributos son iguales, por ejemplo Price, entonces la condición puede especificarse como Price = Price o, alternativamente, ( Price ) en sí misma.

Para combinar tuplas de dos relaciones donde la condición de combinación no es simplemente la igualdad de atributos compartidos, es conveniente tener una forma más general de operador de unión, que es la unión θ (o unión theta). La unión θ es un operador binario que se escribe como o donde a y b son nombres de atributos, θ es un operador relacional binario en el conjunto {<, ≤, =, ≠, >, ≥ }, υ es una constante de valor y R y S son relaciones. El resultado de esta operación consiste en todas las combinaciones de tuplas en R y S que satisfacen θ . El resultado de la unión θ se define solo si los encabezados de S y R son disjuntos, es decir, no contienen un atributo común. ${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ b}}$ ${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ v}}$

La simulación de esta operación en las operaciones fundamentales es por tanto la siguiente:

R ⋈ _θ S = σ _θ ( R × S )

En caso de que el operador θ sea el operador de igualdad (=) entonces esta unión también se llama equijoin .

Tenga en cuenta, sin embargo, que un lenguaje de computadora que admite los operadores de unión y selección naturales no necesita también θ -join, ya que esto se puede lograr mediante la selección a partir del resultado de una unión natural (que degenera en producto cartesiano cuando no hay atributos compartidos).

En las implementaciones de SQL, la unión en un predicado se suele denominar unión interna y la palabra clave on permite especificar el predicado utilizado para filtrar las filas. Es importante tener en cuenta lo siguiente: formar el producto cartesiano aplanado y luego filtrar las filas es conceptualmente correcto, pero una implementación utilizaría estructuras de datos más sofisticadas para acelerar la consulta de unión.

Unión semiautomática

La unión semipermanente izquierda (⋉ y ⋊) es una unión similar a la unión natural y se escribe como donde y son relaciones . ^[b] El resultado es el conjunto de todas las tuplas en para las que hay una tupla en que es igual en sus nombres de atributos comunes. La diferencia con una unión natural es que las otras columnas de no aparecen. Por ejemplo, considere las tablas Employee y Dept y su unión semipermanente: ^{[ cita requerida ]} ${\displaystyle R\ltimes S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

De manera más formal, la semántica de la semiunión se puede definir de la siguiente manera:

${\displaystyle R\ltimes S=\{t:t\in R\land \exists s\in S(\operatorname {Fun} (t\cup s))\}}$

donde es como en la definición de unión natural. ${\displaystyle \operatorname {Fun} (r)}$

La semiunión se puede simular utilizando la unión natural de la siguiente manera. Si son los nombres de los atributos de , entonces ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle R}$

${\displaystyle R\ltimes S=\Pi _{a_{1},\ldots ,a_{n}}(R\bowtie S).}$

Dado que podemos simular la unión natural con los operadores básicos, se deduce que esto también es válido para la semiunión.

En el artículo de Codd de 1970, la semiunión se denomina restricción. ^[2]

Antiunión

La antiunión (▷), escrita como R ▷ S donde R y S son relaciones , ^[c] es similar a la semiunión, pero el resultado de una antiunión son solo aquellas tuplas en R para las cuales no hay ninguna tupla en S que sea igual en sus nombres de atributos comunes. ^{[ cita requerida ]}

Como ejemplo, considere las tablas Employee y Dept y su antijoin:

La antiunión se define formalmente de la siguiente manera:

R ▷ S = { t  : t ∈ R ∧ ¬∃ s ∈ S ( Fun ( t ∪ s )) }

o

R ▷ S = { t  : t ∈ R , no hay ninguna tupla s de S que satisfaga Fun ( t ∪ s ) }

donde Fun ( t ∪ s ) es como en la definición de unión natural.

La antiunión también se puede definir como el complemento de la semiunión, de la siguiente manera:

Teniendo en cuenta esto, a la antiunión a veces se la llama anti-semiunión, y el operador antiunión a veces se escribe como un símbolo de semiunión con una barra encima, en lugar de ▷.

En el caso donde las relaciones tienen los mismos atributos (compatibles con la unión), antijoin es lo mismo que minus.

División

La división (÷) es una operación binaria que se escribe como R ÷ S . La división no se implementa directamente en SQL. El resultado consiste en las restricciones de las tuplas en R a los nombres de atributos únicos de R , es decir, en el encabezado de R pero no en el encabezado de S , por lo que se cumple que todas sus combinaciones con tuplas en S están presentes en R .

Ejemplo

Si DBProject contiene todas las tareas del proyecto de base de datos, entonces el resultado de la división anterior contiene exactamente los estudiantes que han completado ambas tareas del proyecto de base de datos. De manera más formal, la semántica de la división se define de la siguiente manera:

donde { a ₁ ,..., a _n } es el conjunto de nombres de atributos exclusivos de R y t [ a ₁ ,..., a _n ] es la restricción de t a este conjunto. Por lo general, se requiere que los nombres de atributos en el encabezado de S sean un subconjunto de los de R porque, de lo contrario, el resultado de la operación siempre estará vacío.

La simulación de la división con las operaciones básicas es la siguiente. Suponemos que a ₁ ,..., a _n son los nombres de los atributos únicos de R y b ₁ ,..., b _m son los nombres de los atributos de S . En el primer paso proyectamos R sobre sus nombres de atributos únicos y construimos todas las combinaciones con tuplas en S :

T  := π _{a 1 ,..., a n} ( R ) × S

En el ejemplo anterior, T representaría una tabla en la que cada Estudiante (porque Estudiante es la clave/atributo único de la tabla Completado) se combina con cada Tarea dada. Por ejemplo, Eugene tendría dos filas, Eugene → Base de datos1 y Eugene → Base de datos2 en T.

EG: Primero, supongamos que "Completado" tiene un tercer atributo llamado "calificación". Es un atributo no deseado, por lo que siempre debemos proyectarlo. De hecho, en este paso también podemos quitar "Tarea" de R; la multiplicación lo vuelve a poner.

T  := π _Student ( R ) × S // Esto nos da todas las combinaciones deseadas posibles, incluidas aquellas que en realidad no existen en R y excluyendo otras (por ejemplo, Fred | compiler1, que no es una combinación deseada)

En el siguiente paso restamos R de T

relación :

U  := T − R

En U tenemos las posibles combinaciones que "podrían haber" estado en R , pero no lo estuvieron.

EG: Nuevamente con las proyecciones: T y R deben tener nombres de atributos/encabezados idénticos.

U  := T − π _{Estudiante,Tarea} ( R ) // Esto nos da una lista de "lo que falta".

Entonces, si ahora tomamos la proyección sobre los nombres de atributos únicos para R

Entonces tenemos las restricciones de las tuplas en R para las cuales no todas las combinaciones con tuplas en S estaban presentes en R :

V  := π _{a 1 ,..., a n} ( U )

EG: Proyecto U reducido únicamente a los atributos en cuestión (Estudiante)

V  := π _Estudiante ( U )

Entonces lo que queda por hacer es tomar la proyección de R sobre sus nombres de atributos únicos y restar los de V :

W  := π _{a 1 ,..., a n} ( R ) − V

Ej: W  := π _Estudiante ( R ) − V .

Extensiones comunes

En la práctica, el álgebra relacional clásica descrita anteriormente se extiende con varias operaciones como uniones externas, funciones agregadas e incluso cierre transitivo. ^[3]

Uniones externas

Mientras que el resultado de una unión (o unión interna) consiste en tuplas formadas mediante la combinación de tuplas coincidentes en los dos operandos, una unión externa contiene esas tuplas y, además, algunas tuplas formadas mediante la extensión de una tupla no coincidente en uno de los operandos mediante valores de "relleno" para cada uno de los atributos del otro operando. Las uniones externas no se consideran parte del álgebra relacional clásica analizada hasta ahora. ^[4]

Los operadores definidos en esta sección suponen la existencia de un valor nulo , ω , que no definimos, que se utilizará para los valores de relleno; en la práctica, esto corresponde al NULL en SQL. Para que las operaciones de selección posteriores en la tabla resultante tengan sentido, se debe asignar un significado semántico a los valores nulos; en el enfoque de Codd, la lógica proposicional utilizada por la selección se extiende a una lógica de tres valores , aunque omitimos esos detalles en este artículo.

Se definen tres operadores de unión externa: unión externa izquierda, unión externa derecha y unión externa completa. (A veces se omite la palabra "externa").

Unión externa izquierda

La unión externa izquierda (⟕) se escribe como R ⟕ S donde R y S son relaciones . ^[d] El resultado de la unión externa izquierda es el conjunto de todas las combinaciones de tuplas en R y S que son iguales en sus nombres de atributos comunes, además (en términos generales) de las tuplas en R que no tienen tuplas coincidentes en S. ^{[ cita requerida ]}

Como ejemplo, considere las tablas Employee y Dept y su unión externa izquierda:

En la relación resultante, las tuplas en S que no tienen valores comunes en nombres de atributos comunes con las tuplas en R toman un valor nulo , ω .

Dado que no hay tuplas en Dept con un DeptName de Finance o Executive , aparecen ω en la relación resultante donde las tuplas en Employee tienen un DeptName de Finance o Executive .

Sean r ₁ , r ₂ , ..., r _n los atributos de la relación R y sea {( ω , ..., ω )} la relación singleton sobre los atributos que son únicos para la relación S (aquellos que no son atributos de R ). Entonces la unión externa izquierda puede describirse en términos de la unión natural (y por lo tanto utilizando operadores básicos) de la siguiente manera:

${\displaystyle (R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\omega ,\dots ,\omega )\})}$

Unión externa derecha

La unión externa derecha (⟖) se comporta casi idénticamente a la unión externa izquierda, pero los roles de las tablas se intercambian.

La unión externa derecha de las relaciones R y S se escribe como R ⟖ S . ^[e] El resultado de la unión externa derecha es el conjunto de todas las combinaciones de tuplas en R y S que son iguales en sus nombres de atributos comunes, además de las tuplas en S que no tienen tuplas coincidentes en R . ^{[ cita requerida ]}

Por ejemplo, considere las tablas Employee y Dept y su unión externa derecha:

En la relación resultante, las tuplas en R que no tienen valores comunes en nombres de atributos comunes con las tuplas en S toman un valor nulo , ω .

Dado que no hay tuplas en Employee con un DeptName de Production , aparecen ω en los atributos Name y EmpId de la relación resultante donde las tuplas en Dept tenían DeptName de Production .

Sean s ₁ , s ₂ , ..., s _n los atributos de la relación S y sea {( ω , ..., ω )} la relación singleton sobre los atributos que son únicos para la relación R (aquellos que no son atributos de S ). Entonces, al igual que con la unión externa izquierda, la unión externa derecha se puede simular utilizando la unión natural de la siguiente manera:

${\displaystyle (R\bowtie S)\cup (\{(\omega ,\dots ,\omega )\}\times (S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\bowtie S)))}$

Unión externa completa

La unión externa (⟗) o unión externa completa en efecto combina los resultados de las uniones externas izquierda y derecha.

La unión externa completa se escribe como R ⟗ S donde R y S son relaciones . ^[f] El resultado de la unión externa completa es el conjunto de todas las combinaciones de tuplas en R y S que son iguales en sus nombres de atributos comunes, además de las tuplas en S que no tienen tuplas coincidentes en R y las tuplas en R que no tienen tuplas coincidentes en S en sus nombres de atributos comunes. ^{[ cita requerida ]}

Como ejemplo, considere las tablas Employee y Dept y su unión externa completa:

En la relación resultante, las tuplas en R que no tienen valores comunes en nombres de atributos comunes con las tuplas en S toman un valor nulo , ω . Las tuplas en S que no tienen valores comunes en nombres de atributos comunes con las tuplas en R también toman un valor nulo , ω .

La unión externa completa se puede simular utilizando las uniones externas izquierda y derecha (y, por lo tanto, la unión natural y la unión de conjuntos) de la siguiente manera:

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

Operaciones para cálculos de dominio

No hay nada en el álgebra relacional introducido hasta ahora que permita realizar cálculos en los dominios de datos (aparte de la evaluación de expresiones proposicionales que involucran igualdad). Por ejemplo, no es posible usar solo el álgebra introducida hasta ahora para escribir una expresión que multiplique los números de dos columnas, por ejemplo, un precio unitario con una cantidad para obtener un precio total. Los lenguajes de consulta prácticos tienen tales facilidades, por ejemplo, el SELECT de SQL permite que las operaciones aritméticas definan nuevas columnas en el resultado , y una facilidad similar se proporciona de manera más explícita mediante la palabra clave del Tutorial D. ^[5] En la teoría de bases de datos, esto se llama proyección extendida . ^{[6] : 213}SELECT unit_price * quantity AS total_price FROM tEXTEND

Agregación

Además, el cálculo de varias funciones en una columna, como la suma de sus elementos, tampoco es posible utilizando el álgebra relacional presentada hasta ahora. Hay cinco funciones de agregación que se incluyen con la mayoría de los sistemas de bases de datos relacionales. Estas operaciones son Suma, Conteo, Promedio, Máximo y Mínimo. En el álgebra relacional, la operación de agregación sobre un esquema ( A ₁ , A ₂ , ... A _n ) se escribe de la siguiente manera:

${\displaystyle G_{1},G_{2},\ldots ,G_{m}\ g_{f_{1}({A_{1}}'),f_{2}({A_{2}}'),\ldots ,f_{k}({A_{k}}')}\ (r)}$

donde cada A _j ', 1 ≤ j ≤ k , es uno de los atributos originales A _i , 1 ≤ i ≤ n .

Los atributos que preceden a g son atributos de agrupación, que funcionan como una cláusula "group by" en SQL. Luego, hay una cantidad arbitraria de funciones de agregación que se aplican a atributos individuales. La operación se aplica a una relación arbitraria r . Los atributos de agrupación son opcionales y, si no se proporcionan, las funciones de agregación se aplican a toda la relación a la que se aplica la operación.

Supongamos que tenemos una tabla llamada Cuenta con tres columnas, a saber, Account_Number, Branch_Name y Balance . Deseamos encontrar el saldo máximo de cada sucursal. Esto se logra mediante _{Branch_Name} G _{Max( Balance )} ( Account ). Para encontrar el saldo más alto de todas las cuentas independientemente de la sucursal, simplemente podríamos escribir G _{Max( Balance )} ( Account ).

La agrupación a menudo se escribe como _{Branch_Name} ɣ _{Max( Balance )} ( Account ). ^[6]

Cierre transitivo

Aunque el álgebra relacional parece lo suficientemente potente para la mayoría de los propósitos prácticos, existen algunos operadores simples y naturales sobre relaciones que no pueden expresarse mediante el álgebra relacional. Uno de ellos es la clausura transitiva de una relación binaria. Dado un dominio D , sea la relación binaria R un subconjunto de D × D . La clausura transitiva R ⁺ de R es el subconjunto más pequeño de D × D que contiene a R y satisface la siguiente condición:

${\displaystyle \forall x\forall y\forall z\left((x,y)\in R^{+}\wedge (y,z)\in R^{+}\Rightarrow (x,z)\in R^{+}\right)}$

Esto se puede demostrar utilizando el hecho de que no existe una expresión de álgebra relacional E ( R ) que tome R como argumento variable que produzca R ⁺ . ^[7]

Sin embargo, SQL admite oficialmente dichas consultas de punto fijo desde 1999, y tenía extensiones específicas del proveedor en esta dirección mucho antes de eso.

Uso de propiedades algebraicas para la optimización de consultas

Dos posibles planes de consulta para la consulta triangular R(A, B) ⋈ S(B, C) ⋈ T(A, C) ; el primero une S y T primero y une el resultado con R , el segundo une R y S primero y une el resultado con T

Los sistemas de gestión de bases de datos relacionales suelen incluir un optimizador de consultas que intenta determinar la forma más eficiente de ejecutar una consulta determinada. Los optimizadores de consultas enumeran los posibles planes de consulta , calculan su coste y seleccionan el plan con el coste estimado más bajo. Si las consultas se representan mediante operadores del álgebra relacional, el optimizador de consultas puede enumerar los posibles planes de consulta reescribiendo la consulta inicial utilizando las propiedades algebraicas de estos operadores.

Las consultas se pueden representar como un árbol , donde

• Los nodos internos son operadores,
• Las hojas son relaciones ,
• Los subárboles son subexpresiones.

El objetivo principal del optimizador de consultas es transformar los árboles de expresión en árboles de expresión equivalentes, donde el tamaño promedio de las relaciones generadas por las subexpresiones en el árbol sea menor que el que había antes de la optimización . El objetivo secundario es intentar formar subexpresiones comunes dentro de una sola consulta o, si hay más de una consulta que se está evaluando al mismo tiempo, en todas esas consultas. La razón detrás del segundo objetivo es que basta con calcular las subexpresiones comunes una vez y los resultados se pueden usar en todas las consultas que contengan esa subexpresión.

A continuación se presenta un conjunto de reglas que se pueden utilizar en tales transformaciones.

Selección

Las reglas sobre los operadores de selección desempeñan el papel más importante en la optimización de consultas. La selección es un operador que reduce de forma muy eficaz la cantidad de filas en su operando, por lo que si las selecciones en un árbol de expresión se mueven hacia las hojas, las relaciones internas (generadas por subexpresiones) probablemente se reducirán.

Propiedades básicas de selección

La selección es idempotente (múltiples aplicaciones de la misma selección no tienen ningún efecto adicional más allá de la primera) y conmutativa (el orden en que se aplican las selecciones no tiene efecto sobre el resultado final).

1. ${\displaystyle \sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!}$
2. ${\displaystyle \sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!}$

Descomponer selecciones con condiciones complejas

Una selección cuya condición es una conjunción de condiciones más simples es equivalente a una secuencia de selecciones con esas mismas condiciones individuales, y una selección cuya condición es una disyunción es equivalente a una unión de selecciones. Estas identidades se pueden utilizar para fusionar selecciones de modo que sea necesario evaluar menos selecciones, o para dividirlas de modo que las selecciones componentes se puedan mover u optimizar por separado.

1. ${\displaystyle \sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R))}$
2. ${\displaystyle \sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)}$

Selección y producto cruzado

El producto vectorial es el operador más costoso de evaluar. Si las relaciones de entrada tienen N y M filas, el resultado contendrá filas. Por lo tanto, es importante reducir el tamaño de ambos operandos antes de aplicar el operador de producto vectorial. ${\displaystyle NM}$

Esto se puede hacer de manera efectiva si el producto vectorial va seguido de un operador de selección, por ejemplo . Teniendo en cuenta la definición de unión, este es el caso más probable. Si el producto vectorial no va seguido de un operador de selección, podemos intentar introducir una selección desde niveles superiores del árbol de expresión utilizando las otras reglas de selección. ${\displaystyle \sigma _{A}(R\times P)}$

En el caso anterior, la condición A se divide en las condiciones B, C y D utilizando las reglas de división sobre condiciones de selección complejas, de modo que B contiene solo atributos de R , C contiene solo atributos de P y D contiene la parte de A que contiene atributos tanto de R como de P. Nótese que B , C o D posiblemente estén vacíos. Entonces se cumple lo siguiente: ${\displaystyle A=B\wedge C\wedge D}$

${\displaystyle \sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))}$

Operadores de selección y de conjunto

La selección es distributiva sobre los operadores de diferencia de conjuntos, intersección y unión. Las siguientes tres reglas se utilizan para introducir la selección por debajo de las operaciones de conjuntos en el árbol de expresión. Para los operadores de diferencia de conjuntos e intersección, es posible aplicar el operador de selección a solo uno de los operandos después de la transformación. Esto puede ser beneficioso cuando uno de los operandos es pequeño y la sobrecarga de evaluar el operador de selección supera los beneficios de usar una relación más pequeña como operando.

1. ${\displaystyle \sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P}$
2. ${\displaystyle \sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)}$
3. ${\displaystyle \sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)}$

Selección y proyección

La selección conmuta con la proyección si y solo si los campos a los que se hace referencia en la condición de selección son un subconjunto de los campos de la proyección. Realizar la selección antes de la proyección puede ser útil si el operando es un producto vectorial o una unión. En otros casos, si la condición de selección es relativamente costosa de calcular, mover la selección fuera de la proyección puede reducir la cantidad de tuplas que se deben probar (ya que la proyección puede producir menos tuplas debido a la eliminación de duplicados resultantes de los campos omitidos).

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},\ldots ,a_{n}}(R)){\text{ where fields in }}A\subseteq \{a_{1},\ldots ,a_{n}\}}$

Proyección

Propiedades básicas de proyección

La proyección es idempotente, de modo que una serie de proyecciones (válidas) es equivalente a la proyección más externa.

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(\pi _{b_{1},\ldots ,b_{m}}(R))=\pi _{a_{1},\ldots ,a_{n}}(R){\text{ where }}\{a_{1},\ldots ,a_{n}\}\subseteq \{b_{1},\ldots ,b_{m}\}}$

Operadores de proyección y conjuntos

La proyección es distributiva sobre la unión de conjuntos.

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(R\cup P)=\pi _{a_{1},\ldots ,a_{n}}(R)\cup \pi _{a_{1},\ldots ,a_{n}}(P).\,}$

La proyección no se distribuye sobre la intersección y la diferencia de conjuntos. Los contraejemplos se dan por:

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \})=\emptyset }$

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \})\cap \pi _{A}(\{\langle A=a,B=b'\rangle \})=\{\langle A=a\rangle \}}$

y

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \})=\{\langle A=a\rangle \}}$

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \})\setminus \pi _{A}(\{\langle A=a,B=b'\rangle \})=\emptyset \,,}$

donde se supone que b es distinto de b' .

Rebautizar

Propiedades básicas de cambio de nombre

Los sucesivos cambios de nombre de una variable se pueden agrupar en un único cambio de nombre. Las operaciones de cambio de nombre que no tienen variables en común se pueden reordenar arbitrariamente entre sí, lo que se puede aprovechar para hacer que los sucesivos cambios de nombre sean adyacentes y se puedan agrupar.

1. ${\displaystyle \rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!}$
2. ${\displaystyle \rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\!}$

Operadores de cambio de nombre y de configuración

El cambio de nombre es distributivo sobre la diferencia de conjuntos, la unión y la intersección.

1. ${\displaystyle \rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)}$
2. ${\displaystyle \rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)}$
3. ${\displaystyle \rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)}$

Producto y unión

El producto cartesiano es distributivo sobre la unión.

1. ${\displaystyle (A\times B)\cup (A\times C)=A\times (B\cup C)}$

Implementaciones

El primer lenguaje de consulta basado en el álgebra de Codd fue Alpha, desarrollado por el propio Dr. Codd. Posteriormente se creó ISBL , y este trabajo pionero ha sido aclamado por muchas autoridades ^[8] por haber mostrado la manera de convertir la idea de Codd en un lenguaje útil. Business System 12 fue un DBMS relacional de corta duración y de gran solidez industrial que siguió el ejemplo de ISBL.

En 1998 Chris Date y Hugh Darwen propusieron un lenguaje llamado Tutorial D, destinado a ser utilizado en la enseñanza de la teoría de bases de datos relacionales, y su lenguaje de consulta también se basa en las ideas de ISBL. ^[9] Rel es una implementación de Tutorial D. Bmg es una implementación de álgebra relacional en Ruby que sigue de cerca los principios de Tutorial D y El Tercer Manifiesto . ^[10]

Incluso el lenguaje de consulta de SQL se basa vagamente en un álgebra relacional, aunque los operandos en SQL ( tablas ) no son exactamente relaciones y varios teoremas útiles sobre el álgebra relacional no se sostienen en la contraparte de SQL (posiblemente en detrimento de los optimizadores y/o usuarios). El modelo de tabla de SQL es una bolsa ( multiconjunto ), en lugar de un conjunto. Por ejemplo, la expresión es un teorema para el álgebra relacional sobre conjuntos, pero no para el álgebra relacional sobre bolsas. ^[6] ${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$

Véase también

• Producto cartesiano
• D4 (lenguaje de programación) (una implementación de D)
• Base de datos
• Lógica de los relativos
• Modelado de objetos y roles
• Proyección (matemáticas)
• Proyección (álgebra relacional)
• Proyección (teoría de conjuntos)
• Relación
• Relación (base de datos)
• Álgebra de relaciones
• Composición de la relación
• Construcción de relaciones
• Cálculo relacional
• Base de datos relacional
• Modelo relacional
• Teoría de las relaciones
• Relación triádica
• Cálculo relacional de tuplas
• SQL
• Registro de datos
• Teorema de Codd

Notas

1. En Unicode , el símbolo de unión es ⨝ (U+2A1D), y el símbolo de moño, que ocasionalmente se usa en su lugar, es ⋈ (U+22C8).
2. En Unicode , el símbolo de tiempo de la letra l es ⋉ (U+22C9). El símbolo de tiempo de la letra r es ⋊ (U+22CA)
3. En Unicode , el símbolo Antijoin es ▷ (U+25B7).
4. En Unicode , el símbolo de unión externa izquierda es ⟕ (U+27D5).
5. En Unicode , el símbolo de unión externa derecha es ⟖ (U+27D6).
6. En Unicode , el símbolo de unión externa completa es ⟗ (U+27D7).

Referencias

1. Silberschatz, Abraham; Henry F. Korth; S. Sudarshan (2020). Conceptos de sistemas de bases de datos (Séptima edición). Nueva York. p. 56. ISBN 978-0-07-802215-9.OCLC 1080554130  .{{cite book}}: CS1 maint: location missing publisher (link)
2. Codd, EF (junio de 1970). "Un modelo relacional de datos para grandes bancos de datos compartidos". Comunicaciones de la ACM . 13 (6): 377–387. doi : 10.1145/362384.362685 . S2CID  207549016.
3. M. Tamer Özsu; Patrick Valduriez (2011). Principios de los sistemas de bases de datos distribuidas (3.ª ed.). Springer. pág. 46. ISBN 978-1-4419-8833-1.
4. Patrick O'Neil; Elizabeth O'Neil (2001). Base de datos: principios, programación y rendimiento, segunda edición. Morgan Kaufmann. pág. 120. ISBN 978-1-55860-438-4.
5. CJ Date (2011). SQL y teoría relacional: cómo escribir código SQL preciso. O'Reilly Media, Inc., págs. 133-135. ISBN 978-1-4493-1974-8.
6. Hector Garcia-Molina ; Jeffrey D. Ullman ; Jennifer Widom (2009). Sistemas de bases de datos: el libro completo (2.ª ed.). Pearson Prentice Hall. ISBN 978-0-13-187325-4.
7. Aho, Alfred V.; Jeffrey D. Ullman (1979). "Universalidad de los lenguajes de recuperación de datos". Actas del 6º Simposio ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación : 110–119. doi : 10.1145/567752.567763 . S2CID  : 3242505.
8. CJ Date. "Edgar F. Codd - Ganador del premio AM Turing". amturing.acm.org . Consultado el 27 de diciembre de 2020 .
9. CJ Date y Hugh Darwen. "Bases de datos, tipos y el modelo relacional: el tercer manifiesto" (PDF) . Consultado el 4 de julio de 2024 .
10. "Documentación de BMG" . Consultado el 4 de julio de 2024 .

Lectura adicional

• Imieliński, T. ; Lipski, W. (1984). "El modelo relacional de datos y álgebras cilíndricas". Revista de Ciencias de la Computación y de Sistemas . 28 : 80–102. doi : 10.1016/0022-0000(84)90077-1 .(Para relación con álgebras cilíndricas ).

Enlaces externos

• Traductor de álgebra relacional RAT Software gratuito para convertir álgebra relacional a SQL
• Vídeos de conferencias: Procesamiento de álgebra relacional: una introducción a cómo los sistemas de bases de datos procesan el álgebra relacional
• Notas de clase: Álgebra relacional: un tutorial rápido para adaptar consultas SQL al álgebra relacional
• Relacional: una implementación gráfica del álgebra relacional
• Optimización de consultas Este artículo es una introducción al uso del álgebra relacional para optimizar consultas e incluye numerosas citas para un estudio más profundo.
• Sistema de álgebra relacional para Oracle y Microsoft SQL Server
• Pireal – Una herramienta educativa experimental para trabajar con Álgebra Relacional
• DES – Una herramienta educativa para trabajar con Álgebra Relacional y otros lenguajes formales
• RelaX - Calculadora de álgebra relacional (software de código abierto disponible como servicio en línea sin necesidad de registro)
• RA: Un intérprete de álgebra relacional
• Traducción de SQL a álgebra relacional