Álgebra relacional

Teoría de bases de datos relacionales

En la 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 . ^[1]

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.

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 de tuplas 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\}}$

Una relación también tiene una tupla única llamada encabezado que le da a cada columna un nombre o atributo único dentro de la relación. Los atributos se utilizan en proyecciones y selecciones.

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, y agrega restricciones adicionales a estos operadores para crear otros nuevos.

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 comúnmente para cambiar el nombre del atributo de una relación con el propósito de una unión. ${\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 . ^[2] ${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$ ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$ ${\displaystyle \{A_{1},\ldots ,A_{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 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 en todos los atributos excepto en el común DeptName .

El operador de unión natural es posiblemente uno de los operadores más importantes, ya que es la contraparte relacional del operador AND lógico. Nótese 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 sustituirse por el mismo valor (esto es una consecuencia de la idempotencia del operador AND lógico).

Formalmente, la semántica de la unión natural se define de la siguiente manera:

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 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:

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 . ^[b] 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 . ^[c] 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 . ^[d] 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.

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, pensado para su uso 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
• Teorema de Codd
• D4 (lenguaje de programación) (una implementación de D)
• Modelado de datos
• Base de datos
• Registro de datos
• Lógica de los relativos
• 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
• Cálculo relacional
• Base de datos relacional
• Modelo relacional
• SQL
• Teoría de las relaciones
• Relación triádica
• Cálculo relacional de tuplas

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 unión externa izquierda es ⟕ (U+27D5).
3. En Unicode , el símbolo de unión externa derecha es ⟖ (U+27D6).
4. En Unicode , el símbolo de unión externa completa es ⟗ (U+27D7).

Referencias

1. Codd, EF (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.
2. 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)
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