Álgebra relacional

La versión estable se desprotegió el 29 de julio de 2022 . Hay cambios no verificados en plantillas o .

El álgebra relacional es un sistema cerrado de operaciones sobre relaciones en un modelo de datos relacional . Las operaciones del álgebra relacional también se denominan operaciones relacionales .

El conjunto original de 8 operaciones fue propuesto por E. Codd en la década de 1970 e incluía tanto operaciones que todavía están en uso ( proyección , unión , etc.) como operaciones que no han entrado en uso (por ejemplo, división de relaciones).

En el desarrollo de la teoría y la práctica relacional, se han propuesto varias operaciones relacionales nuevas, como la semiunión ( SEMI-JOIN ) y la semidiferencia, o la antisemiunión ( ANTI-SEMI-JOIN ) [1] [2 ] , CROSS APPLY y OUTER APPLY , cierre transitivo ( TCLOSE ) etc.

Dado que muchas operaciones son expresables entre sí, como parte del álgebra relacional, se pueden distinguir varias variantes de la base (un conjunto de operaciones mediante las cuales todas las demás son expresables). La base más famosa y estrictamente definida ( álgebra A ) fue propuesta por Christopher Date y Hugh Darwen [3] .

El álgebra relacional y el cálculo relacional son equivalentes en su poder expresivo [4] . Hay reglas para convertir solicitudes entre ellos.

La principal aplicación del álgebra relacional es proporcionar un marco teórico para las bases de datos relacionales , especialmente los lenguajes de consulta para dichas bases de datos, entre los que destaca SQL .

Álgebra relacional cerrada

El álgebra relacional es un conjunto de operaciones sobre relaciones tales que el resultado de cada una de las operaciones es también una relación. Esta propiedad de un álgebra se llama clausura .

Las operaciones en una relación se llaman unario , en dos relaciones - binario , en tres - ternario (estos son prácticamente desconocidos).

Un ejemplo de una operación unaria es una proyección, un ejemplo de una operación binaria es una unión.

Una operación relacional N -aria f puede representarse mediante una función que devuelve una relación y toma n relaciones como argumentos:

R=f(R_{1},R_{2},\puntos,R_{n})

Dado que el álgebra relacional es cerrada, otras expresiones de álgebra relacional (adecuadas para el tipo) pueden sustituirse como operandos en operaciones relacionales:

R=f(f_{1}(R_{11},R_{12},\puntos),f_{2}(R_{21},R_{22},\puntos),\puntos )

En expresiones relacionales, puede utilizar expresiones anidadas de una estructura arbitrariamente compleja.

Restricciones a las operaciones

Algunas operaciones relacionales, en particular la unión , la intersección y la resta , requieren que la relación tenga encabezados (esquemas) coincidentes (iguales). Esto significa que el número de atributos, los nombres de los atributos y el tipo ( dominio ) de los atributos del mismo nombre son los mismos.

Algunas relaciones no son formalmente compatibles debido a las diferencias en los nombres de los atributos, pero lo son después de aplicar la operación de cambio de nombre de los atributos.

La operación de producto cartesiano requiere que las relaciones de operandos no tengan atributos del mismo nombre. Se dice que las relaciones son compatibles tomando el producto cartesiano extendido si la intersección de los conjuntos de nombres de atributos tomados de sus esquemas de relación está vacía.

Operaciones de álgebra relacional

Las siguientes son algunas operaciones de álgebra relacional que son de interés histórico o práctico. Es imposible enumerar todas las operaciones, ya que cualquier operación que satisfaga la definición de relacional es parte del álgebra relacional.

Cambio de nombre

El resultado de aplicar la operación de cambio de nombre de atributos es una relación con los nombres de atributos cambiados.

Sintaxis :

R RENOMBRAR Atr 1 , Atr 2 , ... AS NewAtr 1 , NewAtr 2 , ...

dónde

R - relación Atr 1 , Atr 2 , ... — nombres de atributos iniciales NewAtr 1 , NewAtr 2 , ... son nuevos nombres de atributos.

Consolidación

Una relación con el mismo encabezado que las relaciones compatibles de tipo A y B , y un cuerpo que consta de tuplas que pertenecen a A , B o ambos.
Sintaxis:

UNA UNIÓN B

Cruce

Una relación con el mismo título que las relaciones A y B , y un cuerpo formado por tuplas que pertenecen a ambas relaciones A y B al mismo tiempo .
Sintaxis:

A INTERSECCIÓN B

Resta

Una relación con el mismo encabezamiento que las relaciones de tipo compatibles A y B , y un cuerpo formado por tuplas que pertenecen a la relación A y no pertenecen a la relación B.
Sintaxis:

A MENOS B

Operación de asignación

El operador de asignación (:=) le permite almacenar el resultado de evaluar una expresión relacional en una relación existente.

Producto cartesiano

Una relación cuyo encabezamiento ( A 1 , A 2 , …, A n , B 1 , B 2 , …, B m ) es la concatenación de los encabezamientos de las relaciones A ( A 1 , A 2 , …, A n ) y B ( B 1 , B 2 , …, B m ), y el cuerpo consta de tuplas que son todas combinaciones de tuplas de relaciones A y B : ( a 1 , a 2 , …, a n , b 1 , b 2 , … , b m ),

tal que

( un 1 , un 2 , …, un norte ) ∈ UN , ( segundo 1 , segundo 2 , ..., segundo metro ) ∈ segundo .

Sintaxis:

A VECES B

Muestreo (limitación)

Una relación con el mismo título que la relación A y un cuerpo que consta de tuplas cuyos valores de atributo se evalúan como VERDADERO cuando se sustituyen en la condición c . c es una expresión booleana que puede incluir atributos de la relación A y/o expresiones escalares.
Sintaxis:

A DONDE c

La muestra se escribe como o donde: ${\ estilo de visualización \ sigma _ {a \ theta b} (R)}$ ${\ estilo de visualización \ sigma _ {a \ theta v} (R)}$

a y b son nombres de atributo
θ es una de las operaciones binarias ${\displaystyle \{\;<,\leq ,=,\neq ,\geq ,\;>\))$
v es una constante
relación R

Proyección

La proyección es una operación unaria que le permite obtener un subconjunto "vertical" de una relación o tabla dada , es decir, un subconjunto que se obtiene seleccionando los atributos especificados , seguido de la eliminación, si es necesario, de tuplas duplicadas redundantes. . Deje que se proporcione una tabla con nombres de atributos , es decir , algún subconjunto del conjunto de nombres de atributos . El resultado de una proyección de tabla sobre los nombres de atributos seleccionados es una nueva tabla obtenida de la tabla original eliminando atributos que no están incluidos en el conjunto seleccionado, seguido de la posible eliminación de tuplas duplicadas redundantes. $T$ $A_{1},\;A_{2},\;\ldots,\;A_{n}$ $T(A_{1},\;A_{2},\;\ldots,\;A_{n})$ $\{A_{{i_{1}}},\;A_{{i_{2}}},\;\ldots,\;A_{{i_{k}}}\}$ $T(A_{{i_{1}}},\;A_{{i_{2}}},\;\ldots,\;A_{{i_{k}}})$

Al implementar una proyección, es necesario especificar la relación proyectada y un determinado conjunto de sus atributos, que se convertirán en el título de la resultante.

Cuando se realiza la proyección, se asigna un corte "vertical" de la relación del operando con la destrucción natural de las tuplas duplicadas que pueden surgir.

Sintaxis:

A[X, Y, …, Z]

PROYECTO A {x, y, …, z}

Conexión

La operación de unir las relaciones A y B por el predicado P es lógicamente equivalente a la aplicación secuencial del producto cartesiano de A y B y la selección por el predicado P. Si hay atributos con los mismos nombres en las relaciones, entonces antes de realizar la unión, estos atributos deben ser renombrados.

Sintaxis:

( A VECES B ) DONDE P

División

Una relación con un encabezado (X 1 , X 2 , …, X n ) y un cuerpo que contiene un conjunto de tuplas (x 1 , x 2 , …, x n ) tal que para todas las tuplas (y 1 , y 2 , … , y m ) ∈ B con respecto a A(X 1 , X 2 , …, X n , Y 1 , Y 2 , …, Y m ) existe una tupla (x 1 , x 2 , …, x n , y 1 , y 2 , …, ym ) .

Sintaxis:

A DIVIDIR POR B

Expresibilidad de algunas operaciones en términos de otras

Algunos de los operadores relacionales se pueden expresar en términos de otros operadores relacionales.

Unirse al operador

El operador de unión se define en términos del producto cartesiano y los operadores de selección de la siguiente manera:

(A VECES B) DONDE X=Y donde X e Y son atributos respectivamente de las relaciones A y B con nombres inicialmente iguales. Operador de intersección

El operador de intersección se expresa a través de la resta de la siguiente manera:

A INTERSECCIÓN B = A MENOS (A MENOS B) operador de división

El operador de división se expresa en términos de los operadores de resta, producto cartesiano y proyección de la siguiente manera:

A DIVIDIR POR B = A[X] MENOS ((A[X] VECES B) MENOS A)[X]

Implementaciones

El primer lenguaje de consulta basado en el álgebra de Codd fue Alpha, desarrollado por el mismo Codd. Posteriormente, se creó ISBL, y este trabajo pionero ha sido elogiado por muchas autoridades [5] por mostrar una forma de convertir la idea de Codd en un lenguaje útil. Business System 12 fue un DBMS relacional de corta duración que siguió el ejemplo de ISBL.

En 1998 , Christopher Date y Hugh Darwen propusieron un lenguaje llamado Tutorial D para usar en la enseñanza de la teoría de bases de datos relacionales; este lenguaje de consulta también se basó en ideas de ISBL. Rel es una implementación del Tutorial D.

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

Notas

↑ Introducción a las combinaciones . Consultado el 14 de noviembre de 2011. Archivado desde el original el 26 de noviembre de 2011. (indefinido)
↑ Fecha, Cristóbal. SQL y teoría relacional. Cómo escribir código en SQL correctamente. - Símbolo-Plus, 2010
↑ C. Fecha, Hugh Darwen. Fundamentos de los futuros sistemas de bases de datos. Tercer Manifiesto. M: Janus-K, 2004.
↑ Gris, 1989 , pág. 188.
↑ Fecha CJ. Edgar F. Codd - Laureado del Premio AM Turing . amturing.acm.org . Consultado el 27 de diciembre de 2020. Archivado desde el original el 23 de diciembre de 2017. (indefinido)
↑ Héctor García-Molina . Sistemas de bases de datos: el libro completo / Héctor García-Molina , Jeffrey D. Ullman , Jennifer Widom. — 2do. - Pearson Prentice Hall, 2009. - ISBN 978-0-13-187325-4 .

Literatura

Gray P. Lógica, álgebra y bases de datos. - M. : Mashinostroenie, 1989. - S. 188-213. — 368 págs.
Fecha CJ Introducción a los Sistemas de Base de Datos = Introducción a los Sistemas de Base de Datos. - 8ª edición. - M. : Williams , 2005. - 1328 p. - ISBN 5-8459-0788-8 (ruso) 0-321-19784-4 (inglés).

Enlaces

http://www.citforum.ru/database/dblearn/

Base de datos
Conceptos	Modelo de datos relacional modelo álgebra forma normal Integridad referencial base de datos SGBD modelo jerárquico modelo de red Orientado a objetos base de datos SGBD DBMS relacional de objetos transacción Diario ( proactivo ) Seccionamiento Segmentación Almacenamiento de columnas
Objetos	Actitud Columna ( virtual ) Línea Mesa Actuación Procedimiento almacenado Generar Cursor Índice espacio de mesa
Llaves	Primario ( sustituto ) Externo Potencial súper clave
sql	SELECCIONE INSERTAR ACTUALIZAR ELIMINAR TRUNCAR UNIR UNIRSE UNIÓN INTERSECARSE EXCEPTO CREAR ALTERAR DROP CONCEDER COMPROMETERSE RETROCEDER
Componentes	Lenguaje de consulta Optimizador de consultas Planificador de consultas Plan de ejecución de consultas caché de consultas ODBC ALHARACA ADO.NET JDBC