IV ÁLGEBRA RELACIONAL

Codd propuso tres lenguajes de especificación para el modelo

relacional como base teórica de cualquier lenguaje que quisiera

cumplir con los requisitos formales del modelo. Estos lenguajes

no pueden ser explotados comercialmente, al menos tal y como

los definió Codd, porque adolecen de falta de operadores:

carecen de operadores aritméticos simples (sumas, restas, etc.),

o de manipulación de cadenas de caracteres, por poner dos

ejemplos “escandalosos”. El propósito de estos lenguajes no es el

de definir y manejar bases de datos relaciones, tan sólo

constituyen una declaración de los mínimos requeridos para

cualquier lenguaje de manipulación de datos que se quiera

etiquetar a sí mismo como “relacional”. En otras palabras,

cualquier lenguaje de manipulación y definición de datos en

bases de datos relacionales ha de poseer la potencia suficiente

como para “hacer”, como mínimo, lo que pueden “hacer” los

lenguajes de Codd.

El primero de ellos, al menos por el orden en el que se van a

introducir en esta asignatura, es el álgebra relacional. Recibe este

nombre precisamente por su carácter algebraico: incluye un

conjunto de operadores (ocho, concretamente) cuyos operandos

son relaciones y el resultado de la operación es otra relación, del

mismo modo que cuando sumamos dos enteros obtenemos otro

número entero.

En primer lugar se definirán una serie de conceptos necesarios

para definir los operadores del álgebra relacional y para,

finalmente, trabajar con ellos. A continuación se describirán, uno

por uno, los ocho operadores propuestos por Codd:

Unión ∪ Selección donde

Intersección ∩ Proyección [ ]

Diferencia − Concatenación Natural ∞

Producto Cartesiano × División ÷

62

IV1. Conceptos previos.

Al describir las propiedades de cada operador se van a utilizar una serie de

términos que debemos definir previamente.

En primer lugar se presentará una adaptación del concepto de relación

matemática en la que se vuelve a hacer uso de la ordenación de las

componentes de una tupla. El resto, son expresiones o reformulaciones de

conceptos ya presentes en la definición del modelo.

Los conceptos a definir son:

• Relación

• Esquema de relación

• Nombres Cualificados de Atributo

• Alias de una relación

• Relación Nominada

• Relación Derivada

• Relaciones Compatibles

• Operación conmutativa

• Operación asociativa

relación

El AR hace uso del orden de las componentes de las tuplas para definir

operadores y propiedades de los operadores. En realidad, se trata de retomar

la definición original de la relación matemática como el subconjunto de un

producto cartesiano de n dominios, de tal forma que las tuplas resultado de

ese producto cumplían y cumplen que

Las tuplas son listas de valores (conjunto ordenado) tal que el

i-ésimo valor pertenece al i-ésimo dominio.

Vamos a combinar la definición anterior de tupla con la adaptación que en su

momento introdujimos a la relación matemática para adecuarla al objetivo final

que es una base de datos. Utilizaremos al mismo tiempo los nombres de

atributos y el orden de las componentes en una tupla:

El conjunto de nombres de atributos es un conjunto ordenado.

Las tuplas son listas de valores (conjunto ordenado) tal que el

i-ésimo valor pertenece al i-ésimo dominio asociado al i-ésimo

nombre de atributo.

A partir de ahora, los operadores pueden utilizar tanto el nombre simbólico de

un atributo como su orden dentro de la tupla.

álgebra relacional

63

esquema de relación

Es la descripción formal de la relación con sus atributos y dominios

asociados. En realidad se aplica únicamente a las relaciones nominadas,

aquellas descritas en el esquema lógico relacional.

R( A1:D1, A2:D2, ...,An:Dn )

donde: R es el nombre de la relación

Ai

es el nombre del atributo

Di

es el nombre del dominio asociado a Ai

nombres cualificados de atributo

Es, por decirlo así, el nombre completo de un atributo, por ejemplo R.Ai, el

atributo Ai de la relación R. Su uso evita la ambigüedad de dos atributos en

dos tablas distintas con el mismo nombre.

En general, nos referimos a los atributos por su nombre sin especificar la

relación a la que pertenecen. No obstante, es habitual que en distintas

relaciones, y sobre todo en las relaciones derivadas (los resultados de operar

con relaciones nominadas), nos podamos encontrar nombres de atributo

coincidentes en relaciones distintas. La forma de diferenciar unos de otros es

utilizar los nombres cualificados: “alumno.nombre”, “asignatura.nombre”.

En definitiva, se pueden utilizar indistintamente, siempre y cuando no se

produzcan ambigüedades, las dos formas ya conocidas de referirse a un

atributo:

• nombre cualificado: R.Ai

• nombre no cualificado: Ai

alias de una relación

Nombre alternativo para una relación. Dada una relación R se define un alias

mediante la declaración:

definir alias S para R

Entonces la relación puede referenciarse tanto por R como por S, y los

nombres cualificados de atributos R.Ai o S.Ai.

relación nominada

Es toda relación definida en el esquema lógico relacional. En otras palabras,

las que constituyen nuestra base de datos.

relación derivada

Es aquella que se obtiene como resultado de una expresión del Álgebra

Relacional.

BD1 2006-2007

64

Una relación derivada no tiene nombre ni alias. Así pues, los nombres de los

atributos de ésta se obtendrán a partir de los nombres cualificados de

atributos de las relaciones operando, y si existe ambigüedad se utilizarán los

alias.

Las reglas que rigen en los operadores para la asignación de nombres a los

atributos de relaciones derivadas se verán con cada uno de ellos.

relaciones compatibles

Dos relaciones son compatibles si el grado de ambas es el mismo y los

dominios asociados a los i-ésimos atributos de cada una son iguales.

R( A1:D1, A2:D2, ..., An:Dn )

S( B1:E1, B2:E2, ..., Bm:Em )

R y S son compatibles si y sólo si:

1) n = m

2) ∀i Di = Ei (1 ≤ i ≤ n)

Dicho de otra forma, el número de atributos ha de ser el mismo en ambas

relaciones y, además, los dominios han de ser los mismos para atributos de la

misma posición.

operación conmutativa

Un operación es conmutativa15 si se cumple que

A ⊗ B = B ⊗ A

operación asociativa

Una operación es asociativa si se cumple que

(A ⊗ B) ⊗ C = A ⊗ (B ⊗ C)

operadores

Los operadores del Álgebra Relacional (bajo el punto de vista de Codd) se

dividen en dos grupos:

de la teoría de conjuntos relacionales

UNIÓN

INTERSECCIÓN

DIFERENCIA

PRODUCTO CARTESIANO

SELECCIÓN

PROYECCIÓN

DIVISIÓN

CONCATENACIÓN NATURAL

15En la descripción de los operadores, algunos se dice que cumplen la propiedad conmutativa,

refiriéndonos exclusivamente al conjunto de tuplas de la relación derivada, y no al conjunto de

atributos de dicha relación resultado, cuyos nombres cualificados dependen del orden de las

relaciones operando.

álgebra relacional

65

Como el resultado de una expresión en Álgebra Relacional es otra relación,

ésta puede participar como operando a su vez, permitiendo la construcción de

expresiones anidadas.

R ⊗ S = D1

D1 ⊗ O = D2

R ⊗ S ⊗ O = D2

La única regla de precedencia entre operadores es la utilización de

paréntesis, en cualquier caso las expresiones se evalúan de izquierda a

derecha de tal forma que el resultado de una operación es el operando de la

siguiente operación a su derecha:

R ⊗ S = D1

O ⊗ D1 = D2

O ⊗ ( R ⊗ S ) = D2

Otra clasificación se basa en la propia definición de los operadores: Son

operadores básicos (o primitivas) la unión, diferencia, producto cartesiano,

selección y proyección, y operadores derivados la intersección, la división y

la concatenación natural ya se definen a partir de la combinación de varios

operadores básicos.

Dicho de otra forma, los cinco operadores básicos definen la potencia

expresiva del lenguaje, con ellos se pueden realizar todas las operaciones

que permite el álgebra relacional, mientras que los tres derivados se pueden

ver como “atajos” o “resúmenes” de varias operaciones básicas reunidas en

un único operador.

IV2. definición informal de los

operadores

En primer lugar, se pretende dar una visión de cómo operan y que resultado

obtienen los operadores antes mencionados. Posteriormente, se dará la

definición formal de todos ellos como referencia del lenguaje.

Cuando trabajamos con una base de datos relacional, si de manipulación de

datos estamos hablando, la recuperación de información desde las tablas es

un proceso habitual y necesario.

En álgebra relacional, si queremos recuperar el contenido completo de una

relación, por ejemplo todos los alumnos almacenados en mi base de datos,

una vez identificada la tabla de la que extraer los datos, la tabla alumno, la

evaluación del nombre de la relación nos devuelve todas sus filas:

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

select *

from alumno

BD1 2006-2007

66

Si a un intérprete de AR teórico le ordenamos simplemente “alumno”, el

resultado es la tabla de 3 filas anterior. Por razones de claridad los ejemplos

incluyen la operación, el esquema de la relación resultado y las filas

obtenidas, según se detalla en el gráfico siguiente.

A partir de ahora, los ejemplos muestran el contenido de las tablas utilizadas y

el resultado de cada uno de los operadores. También se darán las

expresiones correspondientes en SQL como ayuda para la comprensión de

cada operación.

selección

En muchas ocasiones sólo nos interesan algunos individuos de una relación,

aquellos que poseen unas determinadas características: “clientes de la

provincia de Alicante”, “artículos que cuestan mas de 500 euros”.

El operador selección (“donde condición”) recupera tuplas de una relación

que cumplen una determinada condición.

Alumno

alumno nombre dirección

577 YÉNIFER c/C, 33

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Alumno donde dirección = ‘c/C, 33’

alumno nombre dirección

577 YÉNIFER c/C, 33

321 JUAN c/C, 33

select *

from alumno

where dirección = ‘c/C, 33’

proyección

Si la selección recupera filas, la proyección ([columna(s)]) recupera atributos.

Alumno

alumno nombre dirección

577 YÉNIFER c/C, 33

operación

que se desea

evaluar

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

esquema de la tabla

resultado de evaluar

dicha operación

filas

obtenidas en

la operación

álgebra relacional

67

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Alumno [alumno, nombre]

alumno nombre

577 YÉNIFER

234 LUCÍA

321 JUAN

221 LUISA

select alumno, nombre

from alumno

La selección me permite recuperar aquellos individuos que me interesan y la

proyección elimina aquellos datos de los individuos que no necesito. Como ya

se ha dicho, se pueden realizar varias operaciones consecutivas, como se

muestra a continuación:

Alumno donde dirección = ‘c/C, 33’ [alumno, nombre]

alumno nombre

577 YÉNIFER

321 JUAN

select alumno, nombre

from alumno

where dirección = ‘c/C, 33’

La proyección podría eliminar la o las columnas definidas como clave

candidata y podría dar lugar a duplicados entre las filas (o más bien nuestra

percepción de la relación nos puede inducir a pensar que se puedan mostrar

filas iguales). Como el resultado de esta operación es también una tabla, ésta

está sujeta a las mismas restricciones del modelo que cualquier otra. Se

puede pensar que el AR realiza la proyección en dos pasos: la proyección

como tal y una eliminación de duplicados, si es que se producen.

Si proyectáramos sobre la columna dirección, la tabla alumno contiene dos

filas con los mismos valores. Sin embargo, el resultado de tal operación es el

siguiente:

Alumno [dirección]

dirección

c/C, 33

c/A, 3

c/E, 333

select dirección16

from alumno

16 En realidad, es habitual que los SGBD relacionales y su implementación de SQL, ante

expresiones como esta devuelvan filas duplicadas. El modificador distinct realiza ese segundo

paso al que hemos hecho referencia en el álgebra relacional. A partir de ahora, aunque no

aparezca en los ejemplos, se entenderá que todas las órdenes select incluyen este modificador:

“select distinct dirección from alumno where dirección = ‘c/C, 33’ ”

BD1 2006-2007

68

Obviamente, esto es aplicable a cualquier operación que hagamos puesto

que el resultado siempre va a ser una tabla derivada.

unión

La unión de dos relaciones da como resultado otra relación que contiene las

tuplas de las dos. Como en una relación no existen tuplas duplicadas (por ser

un conjunto, por estar definida por un producto cartesiano), sería más exacto

describir la unión de dos relaciones A y B como otra relación C que contiene

las tuplas de A que no están en B, las tuplas de B que no están en A, y las

tuplas que están en A y B a la vez.

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Profesor

profesor nombre dirección

522 JOSÉ c/F, 32

778 EVA c/F, 51

221 LUISA c/E, 333

Alumno ∪ Profesor

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

522 JOSÉ c/F, 32

778 EVA c/F, 51

select * from alumno

union

select * from profesor

La unión sólo se puede realizar si A y B son compatibles y, evidentemente, es

conmutativa y asociativa (ver las definiciones anteriores)

álgebra relacional

69

intersección

La intersección de dos relaciones da como resultado otra relación que

contiene las tuplas comunes a las dos primeras.

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Profesor

profesor nombre dirección

522 JOSÉ c/F, 32

778 EVA c/F, 51

221 LUISA c/E, 333

Alumno ∩ Profesor

alumno nombre dirección

221 LUISA c/E, 333

select * from alumno

intersect

select * from profesor

Al igual que la unión, la intersección sólo se puede realizar si A y B son

compatibles y es conmutativa y asociativa.

diferencia

La diferencia de dos relaciones se define como aquellas tuplas que están en

la primera pero no en la segunda. Nótese que este operador ya no es

conmutativo, importa el orden de los operandos.

BD1 2006-2007

70

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Profesor

profesor nombre dirección

522 JOSÉ c/F, 32

778 EVA c/F, 51

221 LUISA c/E, 333

Alumno - Profesor

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

select * from alumno

minus

select * from profesor

La diferencia sólo se puede realizar si A y B son compatibles.

producto cartesiano

Este operador se utiliza para generar todas las posibles combinaciones de las

tuplas de una relación con todas y cada una de las tuplas de otra relación; se

obtienen todas las combinaciones posibles de filas entre dos tablas.

Alumno

alumno nombre dirección

234 LUCÍA c/A, 3

321 JUAN c/C, 33

221 LUISA c/E, 333

Profesor

profesor nombre dirección

522 JOSÉ c/F, 32

778 EVA c/F, 51

221 LUISA c/E, 333

álgebra relacional

71

Alumno × Profesor

alumno nombre dirección profesor nombre dirección

234 LUCÍA c/A, 3 522 JOSÉ c/F, 32

234 LUCÍA c/A, 3 778 EVA c/F, 51

234 LUCÍA c/A, 3 221 LUISA c/E, 333

321 JUAN c/C, 33 522 JOSÉ c/F, 32

321 JUAN c/C, 33 778 EVA c/F, 51

321 JUAN c/C, 33 221 LUISA c/E, 333

221 LUISA c/E, 333 522 JOSÉ c/F, 32

221 LUISA c/E, 333 778 EVA c/F, 51

221 LUISA c/E, 333 221 LUISA c/E, 333

select * from alumno, profesor

concatenación natural

Este operador se utiliza para combinar información de dos tablas que

comparten un atributo común. En este caso quedará más claro un ejemplo en

el que la base de datos refleje una relación entre, por ejemplo, profesores y

departamentos a los que están adscritos. La relación entre los dos se

representa por una columna en la tabla profesor que indica el código de

departamento en el que trabaja.

La concatenación natural utiliza los atributos que tienen el mismo nombre y,

por supuesto, están definidos sobre el mismo dominio.

Profesor Departamento

profesor nombre dirección cod cod departamento

522 JOSÉ c/F, 32 LSI LSI LENGUAJES

778 EVA c/F, 51 LSI CCIA CIENCIAS

221 LUISA c/E, 333 FI FI FILOLOGÍA

Profesor ∞ Departamento

profesor nombre dirección cod departamento

522 JOSÉ c/F, 32 LSI LENGUAJES

778 EVA c/F, 51 LSI LENGUAJES

221 LUISA c/E, 333 FI FILOLOGÍA

select p.*, d.departamento

from profesor p, departamento d

where p.cod = d.cod17

Si no existen 2 filas, una en cada tabla con ese valor idéntico que las une, el

resultado de la concatenación es vacío (no devuelve ninguna tupla). En

nuestro ejemplo sería el caso de que ningún profesor trabajara en ningún

departamento (si la columna Profesor.cod almacenara nulos para todas las

filas en un determinado estado de la base de datos).

El problema se presenta cuando más de una columna comparte tanto nombre

como dominio: el operador intentará unir las filas que comparten los mismos

valores en todos esos atributos. Cambiando un poco el ejemplo anterior,

17 El operador concatenación natural lleva implícita la condición de la cláusula where. En realidad,

esta expresión en SQL es la descomposición en primitivas de la concatenación natural que se

verá más adelante: un producto cartesiano más una selección y una proyección.

BD1 2006-2007

72

podemos pensar que el esquema de Departamento tiene como nombre de la

columna de descripción nombre en vez de departamento. La concatenación

natural sólo devolverá aquellos profesores y departamentos que cumplan que

el profesor trabaja en él y que ambos tienen el mismo nombre.

Profesor Departamento

profesor nombre dirección cod cod nombre

522 LENGUAJES c/F, 32 LSI LSI LENGUAJES

778 EVA c/F, 51 LSI CCIA CIENCIAS

221 LUISA c/E, 333 FI FI FILOLOGÍA

Profesor ∞ Departamento

profesor nombre dirección cod

522 LENGUAJES c/F, 32 LSI

select p.*,d.departamento

from profesor p, departamento d

where p.cod = d.cod and p.nombre =

d.nombre

Cuando no se desea este comportamiento, si queremos que la unión de filas

se realice únicamente por las columnas etiquetadas como cod, estamos

obligados a utilizar una combinación de otros operadores. De hecho, la

concatenación natural es uno de los operadores derivados, y se puede

expresar en función de los operadores básicos selección, proyección y

producto cartesiano.

división

Este operador es el de aplicación menos habitual, se utiliza para consultas del

tipo “alumnos matriculados en todas las asignaturas”. Es, además, el

operador con más restricciones a la hora de construir una expresión en AR. El

dividendo debe tener más atributos que el divisor, dividendo y divisor han de

compartir uno o varios atributos, éstos han de ser los últimos del dividendo y

los únicos del divisor y estar en el mismo orden. Los atributos no comunes

son la información que se obtiene de la división. En la práctica, sea necesario

o no, se suele utilizar la proyección para asegurar que se cumplen todas

estas reglas.

En nuestro ejemplo, “alumnos matriculados en todas las asignaturas”,

usamos la tabla matriculado que es la que representa qué alumnos están

matriculados en qué asignaturas. Todas la asignaturas son, evidentemente,

las asignaturas almacenadas en la tabla asignatura18: el atributo común a

ambas relaciones es “asignatura”, y la información que queremos obtener es

“alumno” (que después se puede concatenar con la tabla Alumno para

obtener su “nombre” y “dirección”).

18 En realidad, debemos identificar ese “todos” al qué se refiere, a qué tabla y a qué datos, puede

no ser trivial: “alumnos matriculados en todas las asignaturas de menos de 6 créditos”, por

ejemplo.

álgebra relacional

73

Alumno Asignatura

alumno nombre dirección asignatura nombre

234 LUCÍA c/A, 3 BD1 Bases1

321 JUAN c/C, 33 BD2 Bases2

221 LUISA c/E, 333 FP2 Prog2

Matriculado

alumno asignatura

234 BD1

234 BD2

234 FP2

321 BD1

321 FP2

Matriculado [alumno, asignatura] % ( Asignatura [asignatura] )

select alumno

from matriculado m

where not exists

(select * from asignatura a

where not exists

(select * from matriculado m2

where m2.alumno = m.alumno

and m2.asignatura =

a.asignatura))19

La razón de que la división tenga unas reglas de composición tan estrictas

está en que éste es otro de los operadores derivados, ya que se puede

realizar la misma operación con una combinación de diferencias y

proyecciones.