Álgebra relacional

Teoría de las 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 fundada . La teoría fue presentada 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, el principal de los cuales es SQL . Las bases de datos relacionales almacenan datos tabulares representados como relaciones . Las consultas sobre bases de datos relacionales a menudo también devuelven datos tabulares representados como relaciones.

El objetivo principal del álgebra relacional es definir operadores que transforman 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, pueden combinarse y usarse para expresar consultas complejas que transforman 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. Los ejemplos incluyen operadores para filtrar ciertos 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 encontradas en cualquier relación ( unión ), eliminar tuplas de la primera relación que se encuentran en la segunda relación ( diferencia ), extender las tuplas de la primera relación con tuplas de la segunda relación que coincidan con ciertas condiciones, y así sucesivamente.

También se pueden incluir otros operadores más avanzados, donde la inclusión o exclusión de determinados 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 dicho álgebra como base para los lenguajes de consulta de bases de datos. (Consulte la sección Implementaciones).

El álgebra relacional opera con conjuntos homogéneos de tuplas donde comúnmente interpretamos que m es el número de filas de una tabla y n es el número de columnas. Todas las entradas de cada columna son del mismo tipo. Cinco operadores primitivos del álgebra de Codd son la selección , la proyección , el producto cartesiano (también llamado producto cruzado o unión cruzada ), la unión de conjuntos y la diferencia de conjuntos . ${\displaystyle S=\{(s_{j1},s_{j2},...s_{jn})|j\in 1...m\}}$

Establecer operadores

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

Para unión de conjuntos y 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 unión de conjuntos y 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 separados, es decir, no deben tener un nombre de atributo común.

Además, el producto cartesiano se define de forma diferente al 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 -tuplas "aplanadas" ( n  +  m ) (mientras que la teoría básica de conjuntos habría prescrito un conjunto de 2-tuplas, cada una que contiene una n -tupla y una m -tupla). Más formalmente, 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 hay 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 están restringidas 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 conjunto múltiple en lugar de un conjunto, y la proyección Π para eliminar datos duplicados se obtiene agregando 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 cuales φ se cumple. ${\displaystyle \sigma _{\varphi }(R)}$ ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

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

Cambiar nombre ( ρ )

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

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

También existe la notación, donde R pasa a llamarse x y los atributos pasan a llamarse . ^[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 tipo unión

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 Empleado y Departamento y su unión natural: ^{[ cita necesaria ]}

Tenga en cuenta que ni la empleada llamada 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 Empleado y Departamento es su combinación como se muestra arriba, proyectada en todos menos en el atributo común NombreDepto . En la teoría de categorías , la unión es precisamente el producto de 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 dos predicados que están conectados por AND, entonces esa variable representa lo mismo y ambas apariciones siempre deben ser sustituidas 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 mediante una clave externa . Por ejemplo, en el ejemplo anterior probablemente exista una clave externa de Empleado . NombreDepto al Departamento . DeptName y luego la unión natural de Empleado y Departamento combina a todos los empleados con sus departamentos. Esto funciona porque la clave externa se mantiene entre atributos con el mismo nombre. Si este no es el caso, como en la clave externa del Departamento . Gerente a Empleado . Nombre, entonces se debe cambiar el nombre de estas columnas antes de realizar la unión natural. A veces, esta unión también se denomina unión equi-join (ver unión θ ).

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 t es una función (es decir, t no asigna ningún atributo a múltiples valores). Generalmente se requiere que R y S tengan al menos un atributo común, pero si se omite esta restricción y R y S no tienen atributos comunes, 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. Supongamos que c ₁ ,..., cm son los nombres _de atributos comunes a R y S , r ₁ ,..., r _n son los nombres de atributos exclusivos de R y s ₁ ,..., s _k son los atributos nombres exclusivos de S . Además, supongamos que los nombres de atributos x ₁ ,..., x _m no están ni en R ni en S . En un primer paso, se puede cambiar el nombre de los nombres de atributos comunes en S :

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:

θ -unión y equiunión

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

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 un valor constante, y R y S son relaciones. El resultado de esta operación consta de todas las combinaciones de tuplas en R y S que satisfacen θ . El resultado de la unión θ se define sólo 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 denomina unión equi .

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

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

Semiunión (⋉ y ⋊)

La semiunión izquierda 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 para las cuales hay una tupla que es igual en sus nombres de atributos comunes. La diferencia con una unión natural es que no aparecen otras columnas . Por ejemplo, considere las tablas Empleado y Departamento y su semiunión: ^{[ cita necesaria ]} ${\displaystyle R\ltimes S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

Más formalmente, 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 llama 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 sólo aquellas tuplas en R para las cuales no hay ninguna tupla en S que sea igual en su común nombres de atributos. ^{[ cita necesaria ]}

Como ejemplo, considere las tablas Empleado y Departamento y su antiunión:

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

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

o

R ▷ S = { t  : t ∈ R , no hay 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 esto en cuenta, la antiunión a veces se denomina antisemiunió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 de que las relaciones tengan los mismos atributos (compatibles con la unión), antiunión es lo mismo que menos.

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 . Para ver un ejemplo, consulte las tablas Completed , DBProject y su división:

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 en el proyecto de base de datos. Más formalmente, la semántica de la división se define de la siguiente manera:

donde { a ₁ ,..., an } es _{el conjunto de nombres de} atributos exclusivos de R y t [ a ₁ ,..., an ] es la restricción de t a este conjunto. Generalmente se requiere que los nombres de los 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 atributos exclusivos de R y b ₁ ,..., b _m son los nombres de atributos de S . En el primer paso proyectamos R en 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 tal que cada Estudiante (porque Estudiante es la clave/atributo único de la tabla Completada) se combina con cada Tarea dada. Entonces Eugene, por ejemplo, tendría dos filas, Eugene → Database1 y Eugene → Database2 en T.

EG: Primero, supongamos que "Completado" tiene un tercer atributo llamado "calificación". Aquí es un equipaje no deseado, por lo que debemos proyectarlo siempre. De hecho, en este paso también podemos eliminar "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 | compilador1, 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 fueron.

EG: Nuevamente con proyecciones: T y R deben tener nombres/encabezados de atributos 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 exclusivos de 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 )

Por ejemplo: Proyecto U hasta solo 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

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

Extensiones comunes

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

Uniones exteriores

Mientras que el resultado de una unión (o unión interna) consta de tuplas formadas combinando tuplas coincidentes en los dos operandos, una unión externa contiene esas tuplas y, además, algunas tuplas formadas extendiendo 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 asumen la existencia de un valor nulo , ω , que no definimos, para ser utilizado 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 sean significativas, es necesario 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 eludimos esos detalles en este artículo.

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

Unión exterior izquierda (⟕)

La unión exterior 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 necesaria ]}

Como ejemplo, considere las tablas Empleado y Departamento y su combinación externa izquierda:

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

Dado que no hay tuplas en Departamento con un NombreDepto de Finanzas o Ejecutivo , se producen ω en la relación resultante donde las tuplas en Empleado tienen un Nombre de Departamento de Finanzas o Ejecutivo .

Sean r ₁ , r ₂ , ..., r _n los atributos de la relación R y sea {( ω , ..., ω )} la relación singleton sobre los atributos que son únicos de la relación S (aquellos que no son atributos de R ). Entonces, la unión exterior izquierda se puede describir en términos de unión natural (y, por 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 exterior derecha (⟖)

La combinación externa derecha se comporta de manera casi idéntica a la combinación externa izquierda, pero las funciones de las tablas se cambian.

La unión exterior 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 necesaria ]}

Por ejemplo, considere las tablas Empleado y Departamento y su combinación externa derecha:

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

Dado que no hay tuplas en Empleado con un NombreDepto de Producción , ω ocurren en los atributos Nombre y EmpId de la relación resultante donde las tuplas en Departamento tenían NombreDepto de Producción .

Sean s ₁ , s ₂ , ..., s _n los atributos de la relación S y sea {( ω , ..., ω )} la relación singleton sobre los atributos que son únicos de la relación R (aquellos que no son atributos de S ). Luego, al igual que con la unión exterior izquierda, la unión exterior 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 exterior o unión exterior completa combina de hecho los resultados de las uniones exteriores 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 tienen no hay tuplas coincidentes en S en sus nombres de atributos comunes. ^{[ cita necesaria ]}

Como ejemplo, considere las tablas Empleado y Departamento y su combinación externa completa:

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

La unión exterior completa se puede simular utilizando las uniones exteriores izquierda y derecha (y, por tanto, la unión natural y la unión establecida) de la siguiente manera:

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

Operaciones para cálculos de dominio.

No se ha introducido nada en el álgebra relacional hasta ahora que permita cálculos en los dominios de datos (aparte de la evaluación de expresiones proposicionales que implican igualdad). Por ejemplo, no es posible utilizar únicamente el álgebra introducida hasta ahora para escribir una expresión que multiplique los números de dos columnas, por ejemplo, un precio unitario por una cantidad para obtener un precio total. Los lenguajes de consulta prácticos tienen tales facilidades, por ejemplo, SQL SELECT permite operaciones aritméticas para definir nuevas columnas en el resultado , y la palabra clave del Tutorial D proporciona una facilidad similar de manera más explícita . ^[5] En 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, calcular varias funciones en una columna, como la suma de sus elementos, tampoco es posible utilizando el álgebra relacional presentada hasta ahora. Hay cinco funciones agregadas 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 álgebra relacional _, la operación de agregación sobre un esquema ( A ₁ , A ₂ , ... An ) 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 Ai _, 1 ≤ i ≤ n .

Los atributos que preceden a la g son atributos de agrupación, que funcionan como una cláusula "agrupar por" en SQL. Luego hay un número arbitrario de funciones de agregación aplicadas 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 en toda la relación a la que se aplica la operación.

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

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

Clausura transitiva

Aunque el álgebra relacional parece lo suficientemente poderosa para la mayoría de los propósitos prácticos, existen algunos operadores simples y naturales en las relaciones que no pueden expresarse mediante el álgebra relacional. Uno de ellos es el cierre transitivo 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 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)}$

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

Sin embargo, SQL admite oficialmente este tipo de consultas de puntos fijos desde 1999, y mucho antes tenía extensiones específicas del proveedor en esta dirección.

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 posibles planes de consulta , estiman su costo y eligen el plan con el costo estimado más bajo. Si las consultas están representadas por operadores de álgebra relacional, el optimizador de consultas puede enumerar 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 á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 es menor que 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 evaluada al mismo tiempo, en todas esas consultas. La razón detrás del segundo objetivo es que es suficiente calcular las subexpresiones comunes una vez y los resultados se pueden usar en todas las consultas que contengan esa subexpresión.

Aquí hay un conjunto de reglas que se pueden utilizar en tales transformaciones.

Selección

Las reglas sobre los operadores de selección juegan el papel más importante en la optimización de consultas. La selección es un operador que disminuye de manera muy efectiva el número 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 de selección básicas

La selección es idempotente (varias 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 ningún 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)\,\!}$

Romper selecciones con condiciones complejas

Una selección cuya condición es una conjunción de condiciones más simples equivale a una secuencia de selecciones con esas mismas condiciones individuales, y una selección cuya condición es una disyunción equivale 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 de 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 cruzado 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 disminuir el tamaño de ambos operandos antes de aplicar el operador de producto cruzado. ${\displaystyle NM}$

Esto se puede hacer de manera efectiva si el producto cruzado 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 cruzado no va seguido de un operador de selección, podemos intentar bajar una selección de 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 usando las reglas de división sobre condiciones de selección complejas, de modo que B contiene atributos solo de R , C contiene atributos solo de P y D contiene la parte de A que contiene atributos de R y P . Tenga en cuenta 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 configuración.

La selección es distributiva entre los operadores de diferencia, intersección y unión establecidos. Las siguientes tres reglas se utilizan para impulsar la selección debajo de las operaciones establecidas en el árbol de expresiones. Para los operadores de diferencia de conjunto y de intersección, es posible aplicar el operador de selección a solo uno de los operandos después de la transformación. Esto puede resultar beneficioso cuando uno de los operandos es pequeño y la sobrecarga de evaluar el operador de selección supera los beneficios de utilizar 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 sólo 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 una selección antes de la proyección puede resultar útil si el operando es un producto cruzado 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 el número de tuplas que deben probarse (ya que la proyección puede producir menos tuplas debido a la eliminación de duplicados resultantes de 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) equivale 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 escenario.

La proyección es distributiva sobre la unión establecida.

${\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 ni establece la diferencia. Los contraejemplos vienen dados 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 cambios de nombre sucesivos de una variable se pueden contraer en un solo 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 cambios de nombre sucesivos sean adyacentes y puedan colapsarse.

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))\,\!}$

Cambiar el nombre y establecer operadores

El cambio de nombre es distributivo sobre la diferencia, unión e intersección establecidas.

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 el camino para convertir la idea de Codd en un lenguaje útil. Business System 12 fue un DBMS relacional de corta duración y sólido en la industria que siguió el ejemplo de ISBL.

En 1998, Chris Date y Hugh Darwen propusieron un lenguaje llamado Tutorial D destinado a 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. Rel es una implementación del Tutorial D.

Incluso el lenguaje de consulta de SQL se basa libremente en un álgebra relacional, aunque los operandos en SQL ( tablas ) no son exactamente relaciones y varios teoremas útiles sobre el álgebra relacional no se cumplen en la contraparte de SQL (posiblemente en detrimento de los optimizadores y/o o usuarios). El modelo de tabla SQL es una bolsa ( multiset ), en lugar de un conjunto. Por ejemplo, la expresión es un teorema del álgebra relacional en conjuntos, pero no del álgebra relacional en bolsas; para un tratamiento del álgebra relacional en bolsas, consulte el capítulo 5 del libro de texto "Completo" de García-Molina , Ullman y Widom . ^[6] ${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$

Ver también

• producto cartesiano
• D4 (lenguaje de programación) (una implementación de D)
• Base de datos
• Lógica de familiares
• Modelado de roles de objetos
• 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
• calculo 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 pajarita, que se utiliza ocasionalmente, es ⋈ (U+22C8).
2. En Unicode , el símbolo de tiempos es ⋉ (U+22C9). El símbolo de rtimes es ⋊ (U+22CA)
3. En Unicode , el símbolo antiunión es ▷ (U+25B7).
4. En Unicode , el símbolo de unión exterior izquierda es ⟕ (U+27D5).
5. En Unicode , el símbolo de unión exterior 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 del sistema de bases de datos (Séptima ed.). Nueva York. pag. 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; Patricio Valduriez (2011). Principios de los sistemas de bases de datos distribuidas (3ª ed.). Saltador. pag. 46.ISBN​ 978-1-4419-8833-1.
4. Patricio O'Neil; Elizabeth O'Neil (2001). Base de datos: principios, programación y rendimiento, segunda edición. Morgan Kaufman. pag. 120.ISBN​ 978-1-55860-438-4.
5. Fecha CJ (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. Héctor García-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. Ah, Alfred V.; Jeffrey D. Ullman (1979). "Universalidad de los lenguajes de recuperación de datos". Actas del sexto simposio ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación : 110–119. doi : 10.1145/567752.567763 . S2CID  3242505.
8. Fecha CJ. "Edgar F. Codd - Premio AM Turing". amturing.acm.org . Consultado el 27 de diciembre de 2020 .

Otras lecturas

Prácticamente cualquier libro de texto académico sobre bases de datos tiene un tratamiento detallado del álgebra relacional clásica.

• 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

• RATA. Software de traducción de á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 la conferencia: Á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 (Página eliminada; Alternativas más cercanas: Standford Query Optimization 2, Investigación de Microsoft sobre optimización de consultas en sistemas relacionales, artículo de Stanford: Query Optimization) Este artículo es una introducción al uso del álgebra relacional para optimizar consultas e incluye numerosas citas para obtener más información. estudio en profundidad.
• 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 registro)
• RA: un intérprete de álgebra relacional
• Traducción de SQL a álgebra relacional