PDF de programación - Tema 4 - algebra relacional

16/05/2012

1

Todo modelo de datos debe definir un lenguaje de definición de datos para crear
las estructuras donde se almacenará la información y un lenguaje de
manipulación de datos con el que acceder y gestionar esa información.



Codd eligió como núcleo de los lenguajes que se desarrollaran para el modelo
relacional el álgebra de conjuntos y el cálculo de predicados de primer orden. Del
primero salió el álgebra relacional, del segundo los cálculos relacionales. Y en
todos ellos, en mayor o menor medida se basa SQL.

2

Codd propuso estos tres lenguajes como base teórica de cualquier lenguaje que
quisiera cumplir con los requisitos formales del modelo. Ni AR ni los CR 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”. 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.

3

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.

4

Las tuplas son listas de valores (conjunto ordenado) tal que el i-ésimo valor pertenece al

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

Antes de continuar debemos definir una serie de términos que serán de uso habitual en el tema.
Evidentemente, partimos de las definiciones propias del modelo:

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


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:



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.

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

5

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


6

Nombre alternativo para una relación. Dada una relación R se define un alias
mediante la declaración:



define 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.


7

La relación nominada es toda relación definida en el esquema lógico relacional.
En otras palabras, las que constituyen nuestra base de datos.



8

Por contra, la relación derivada es aquella que se obtiene como resultado de una
expresión del Álgebra Relacional.



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.

9

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.

10

11

El estudio de los operadores definidos para AR incluye, obviamente, cuáles son y
qué resultado obtienen pero también hemos de conocer en qué condiciones se
pueden aplicar. Además, el resultado no es solo el conjunto de datos obtenido
sino la estructura de las tuplas en que se estructuran. Por último, algunos
operadores son conmutativos y asociativos.

12

Lo marcado en rojo es la notación, digamos, estándar. Lo no marcado, la que
vamos a utilizar por comodidad.

13

Se entiende que los derivados lo son a partir de los operadores básicos.

14

Entendemos por atributos comunes a las dos relaciones operando aquellos que se
llaman igual y se definen sobre los mismos dominios.



Si bien la intersección no necesita más explicación, la concatenación natural (que
se verá más adelante) obtiene como resultado los atributos de R y los de S que no
son comunes, al tiempo que son esas parejas de atributos comunes las que se
utilizan para comparar tuplas:



supongamos R(A:da, B:db, C:dc) y S(D:dd, C:dc, A:da)

el conjunto de atributos a = {R.A, R.B, R.C}

b= {S.D}

f(t) = (R.A=S.A and R.C=S.C)



Para la división, que obtiene únicamente los atributos de la primera relación no
comunes con los de la segunda, y reordenando componentes:

supongamos R(A:da, B:db, C:dc) y S(B:db, C:dc)

a = {R.A}

15

Ejemplos gráficos de lo que vamos a obtener.

16

Los operadores de conjuntos, excepto el producto cartesiano, necesitan que las
relaciones operando sean compatibles.



Tanto la concatenación natural como la división trabajan igualando componentes
comunes a ambas relaciones. Sin embargo, la división tiene reglas adicionales
para poder realizar la operación.

17

Toda relación derivada es una relación y, por tanto, un conjunto desordenado de
tuplas. La lista ordenada de componentes de esas tuplas se obtiene de las
relaciones operando y según sea la operación se obtienen unas u otras.



Sobre todo para expresiones que van encadenando operaciones hasta hacerse
relativamente complejas, en todo momento debemos ser conscientes de qué
columnas de cada tabla están disponibles para la siguiente operación ya que,
como hemos visto, ciertos operadores tienen reglas estrictas de aplicación.

álgebra relacional

18

álgebra relacional

19

álgebra relacional

20

Aquí se introduce la precedencia de operadores: no hay tal precedencia, se evalúa
de izquierda a derecha, salvo que se utilicen paréntesis. Puesto que la
intersección necesita relaciones compatibles, en el ejemplo se realiza una
proyección sobre S previa para conseguirlo.



En todo caso, lo que se pretende ilustrar aquí es que ciertos operadores son
"esencialmente" conmutativos y asociativos puesto que obtienen los mismos
datos. Sin embargo la estructura de la relación derivada, los nombres cualificados
de atributo y su orden no es el mismo. Solo hay que tenerlo en cuenta para
cuando se utilice este resultado en otra operación posterior.

álgebra relacional

21

La expresión en AR más simple a partir de un esquema lógico simple. Se muestra
también la consulta SQL equivalente para mejor comprensión del resultado.

22

La proyección es muy similar a la lista de columnas de la parte select de las
consultas SQL. Sin embargo, en AR la proyección puede utilizarse donde y
cuantas veces se quiera, no necesariamente ha de ponerse como la última
operación.

23

Igualmente, podemos pensar que la selección es como el where de las consultas
SQL. Igual que la proyección, se ha de tener claro que se diferencian en que la
selección de AR se puede utilizar (en realidad, como todos sus operadores) donde
y cuando se necesite dentro de una expresión en AR.



Sin embargo, y aquí tenemos un ejemplo de las implicaciones de la evaluación
procedimental de izquierda a derecha, no siempre se puede intercambiar el orden
en que se ejecutan. Si en esta expresión pusiéramos la proyección antes que la
selección, esta última operación no tendría la columna que precisamente utiliza
para filtrar el resultado final.

PEATONES obtiene una relación derivada con dni, nombre, y edad

PEATONES[nombre] obtiene una relación derivada con nombre, por tanto

PEATONES[nombre] donde edad<=30 no es posible porque ya no disponemos
de PEATONES.edad

24

25

Aquí, sin embargo, no hay problema en ordenarlo como queramos
(evidentemente, PEATONES ha de ser el