01. El modelo relacional de datos: aproximación algebráica

El modelo relacional

En el tema 1 se definió una base de datos como una colección de datos estructurada de acuerdo a las reglas de un modelo. En este tema se va a presentar el Modelo Relacional de Datos que es el modelo seguido por la familia actual de sistemas de gestión de bases de datos.

El Modelo Relacional fue propuesto por E.F. Codd en 1970 imponiéndose sobre los modelos anteriores (jerárquico y red) durante la década de los ochenta. El motivo de su éxito reside por un lado en su sencillez, el usuario percibe la base de datos como un conjunto de “tablas” (datos organizados en filas y columnas), y por otro lado, en el carácter declarativo de su lenguaje de manipulación, el usuario al formular una consulta, expresa lo que desea obtener y no cómo obtenerlo.

A lo largo de este tema se va a estudiar este modelo de datos desde dos puntos de vista: algebraico y lógico.

En la perspectiva algebraica, el Modelo Relacional se presenta como un conjunto de estructuras de datos donde éstas son definidas en el mismo marco teórico en el que se estudia la teoría de tipos es decir, definiendo sus operadores asociados.

La presentación del modelo desde una perspectiva lógica se justifica por el hecho de que el lenguaje aceptado como estándar actual para los sistemas relacionales, el lenguaje SQL, es un lenguaje de tipo lógico.

Estructuras: tupla y relación

El modelo relacional proporciona dos estructuras de datos: la tupla y la relación. La estructura "tupla" coincide con la estructura de datos registro presente en todos los lenguajes de programación así como en los modelos de datos anteriores. La estructura "relación" es específica del Modelo Relacional y es la que lo caracteriza.

TUPLA

Para definir la estructura de datos tupla se introduce previamente el concepto de esquema de tupla.

Un esquema de tupla se define como un conjunto de pares de la forma: {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)} donde {A₁, A₂, ..., A_n} (n > 0) es un conjunto de nombres de atributos y D₁, D₂ ..., D_n son los dominios asociados a dichos atributos que no tienen que ser necesariamente distintos.

Una tupla de esquema {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)} es un conjunto de pares de la forma {(A₁, v₁), (A₂, v₂),..., (A_n, v_n)} tal que ∀i v_i ∈ D_i.

Sean τ = {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)} un esquema de tupla, Tuplaτ el conjunto de tuplas de esquema τ, A_τ = {A₁, A₂,..., A_n} el conjunto de los nombres de atributos del esquema τ y D_τ = D₁ ∪ D₂ ∪ ... ∪ D_n la unión de los dominios de τ entonces los operadores que permiten crear y consultar tuplas son los siguientes:

Asignar: Tupla_τ × A_τ × D_τ → Tuplaτ; este operador permite asignar un valor a un atributo de una tupla. Asignar(t, A_i, v_i) es correcto si v_i ∈ Di
Consultar: Tupla_τ × A_τ → D_τ; este operador permite consultar el valor de un atributo en una tupla

Si t = {(A₁, v₁), ..., (A_i, v_i), ..., (A_n, v_n)} es una tupla del esquema τ anterior, entonces la semántica de estos operadores es la siguiente:

Consultar(t, A_i) = v_i
Asignar(t, A_i, w_i) = {(A₁, v₁), ..., (A_i, w_i), ..., (A_n, v_n)}

Ejemplo 2.1

Dados los dominios:

dom_dni: entero

dom_nom: cadena(20)

dom_dir: cadena(15)

dom_edad: entero

sea el siguiente esquema de tupla:

Persona = {(dni, dom_dni), (nombre, dom_nom), (dirección, dom_dir), (edad, dom_edad)}

y sea la siguiente tupla:

t = {(dni, 12.345.678), (nombre, “Pepa Gómez”), (dirección, “Paz 10”), (edad, 37)}

El comportamiento de los operadores de la estructura tupla se ilustra a continuación:

Consultar(t, nombre) = “Pepa Gómez”

Asignar(t, dirección, “Colón 15”) = {(dni, 12.345.678), (nombre, “Pepa Gómez”), (dirección, “Colón 15”), (edad, 37)}

Generalmente para los operadores de la tupla se utiliza una sintaxis más simplificada que la presentada.

Notación de punto: t.A_i para la consulta y t.A_i ← w_i para la asignación.
Notación funcional: t(A_i) para la consulta y t(A_i ) ← w_i para la asignación.

Con la notación de punto las operaciones del Ejemplo 2.1 serían:

t.nombre= "Pepa Gómez"

t.dirección ← "Colón 15" = {(dni, 12.345.678), (nombre, “Pepa Gómez”), (dirección, “Colón 15”), (edad, 37)}}

La estructura de datos tupla permite representar objetos del mundo real a través de sus propiedades (atributos). Así en el Ejemplo 2.1, cada tupla del esquema Persona representa a una persona a través de sus propiedades dni, nombre, dirección y edad.

RELACIÓN

Para definir la estructura de datos relación se introduce previamente el concepto de esquema de relación.

Un esquema de relación se define como un conjunto de pares de la forma: {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)}, donde {A₁, A₂, ..., A_n} (n > 0) es un conjunto de nombres de atributos y D₁, D₂ ..., D_n son dominios escalares asociados a dichos atributos, dominios que no tiene que ser necesariamente distintos.

Una relación de esquema {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)} es un conjunto de tuplas de dicho esquema.

Se denomina grado de una relación al número de atributos de su esquema, cardinalidad de una relación al número de tuplas que la forman.

La notación que se va a utilizar a lo largo del texto para declarar un objeto relación R de esquema {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)} es:

R (A₁: D₁, A₂: D₂,..., A_n: D_n)

En esta notación no se realiza una definición explícita y previa del esquema de relación, éste se define implícitamente al definir la relación R.

Ejemplo 2.2

Una relación de nombre PERSONA del esquema Persona del Ejemplo 2.1, se definiría:

PERSONA (dni: dom_dni, nombre: dom_nom, dirección: dom_dir, edad: dom_edad).

Su valor en un instante determinado podría ser el siguiente conjunto de cuatro tuplas:

PERSONA:

{{(dni, 12.345.678), (nombre, “Pepa Gómez”), (dirección, “Colón 15”), (edad, 37)}, { (dni, 20.450.120), (nombre, “Juan Pérez”), (dirección, “Cuenca 20”), (edad, 28)}, { (nombre, “José Abad”), (dni, 12.904.569), (dirección, “Blasco Ibáñez 35), (edad, 39)}, { (nombre, “María Gutiérrez”), (dni, 35.784.843) (dirección, “Reina 7”), (edad, 27)}}

EL grado de esta relación es 4 y su cardinalidad es también 4.

La estructura de datos relación permite representar el conjunto de ocurrencias de un mismo tipo de objeto. Así, la relación PERSONA del Ejemplo 2.2 contiene la información relativa a cuatro personas.

En las definiciones anteriores, puede conducir a confusión el uso del término relación, para referirse a un valor de un tipo (o esquema) de relación y para referirse también a un objeto definido de un tipo (o esqema) de relación. Así, en el Ejemplo 2.2, se habla de la relación PERSONA definida del tipo (o esquema) {(dni, dom_dni), (nombre, dom_nom), (dirección, dom_dir), (edad, dom_edad)}, esta relación (objeto persistente) estará inicialmente vacía y podrá tomar como valor cualquier relación (conjunto de tuplas) de dicho esquema; en el ejemplo, la relación PERSONA tiene como valor un conjunto de cuatro tuplas.

El conjunto de definiciones de relación que representan un sistema de información se denomina esquema relacional, y los valores (o extensiones) de las relaciones del esquema en un instante determinado constituyen la base de datos.

La representación de una relación como conjunto de tuplas, como en el Ejemplo 2.2, a menudo resulta tediosa y poco clara; una forma más cómoda y sencilla de representar gráficamente una relación es mediante una tabla en la que cada fila representa una tupla de la relación y cada columna está etiquetada con un nombre de atributo.

Ejemplo 2.3

La representación de la relación del Ejemplo 2.2 mediante una tabla es la siguiente:

PERSONA

dni nombre dirección edad

20.450.120 Juan Pérez Cuenca 20 28

12.904.569 José Abad Blasco Ibáñez 35 39

35.784.843 María Gutiérrez Reina 7 27

12.345.678 Pepa Gómez Colón 15 37

Lo dicho anteriormente no debe inducir a confundir la estructura relación con la estructura tabla que suele ser su representación más habitual. Existen diferencias claras entre ambos conceptos: en la tabla existe un orden entre sus filas y también un orden entre los elementos de las filas, órdenes que no existen en una relación. En el siguiente cuadro se presentan las correspondencias entre términos asociados a ambas estructuras:

Concepto relacional Concepto tabular

• relación • tabla

• atributo • columna

• grado • número de columnas

• tupla • fila

• cardinalidad • número de filas

Se ha definido la relación como un "conjunto de tuplas", pero en la teoría de tipos de datos, una estructura de datos no queda completamente definida hasta que no se especifican sus operadores de consulta y de actualización. Estos operadores, presentados informalmente, son los siguientes:

Unión: la relación resultante de la unión de dos relaciones contiene las tuplas que aparecen en cualquiera de ellas.
Diferencia: la relación resultante de la diferencia de dos relaciones contiene las tuplas que aparecen en la primera y no aparecen en la segunda.
Producto Cartesiano: la relación resultante del producto cartesiano de dos relaciones contiene las tuplas que se pueden construir combinando ("uniendo") una tupla de la primera relación con una tupla de la segunda relación.
Selección: la relación resultante de aplicar una condición de selección a una relación contiene las tuplas de ésta que cumplen la condición especificada.
Proyección: este operador aplicado a una relación extrae de sus tuplas los valores de los atributos especificados en la operación.
Inserción: añade una tupla a la relación.
Borrado: elimina una tupla de la relación.

Ejemplo 2.4

Dada la relación del Ejemplo 2.2, a continuación se ilustran algunos de estos operadores:

PERSONA DONDE edad>30. Esta operación Selección selecciona las tuplas de la relación PERSONA que tienen en el atributo edad un valor mayor que 30, dando como resultado la siguiente relación (presentada en forma tabular):

dni nombre dirección edad

12.904.569 José Abad Blasco Ibáñez 35 39

12.345.678 Pepa Gómez Colón 15 37

PERSONA[dni,nombre]. Esta operación Proyección extrae de las tuplas de la relación PERSONA los valores de los atributos dni y nombre, dando como resultado la siguiente relación (presentada en forma tabular):

dni nombre

20.450.120 Juan Pérez

12.904.569 José Abad

35.784.843 María Gutiérrez

12.345.678 Pepa Gómez

Insertar(PERSONA,{(nombre,'Luisa León'), (dni, 11.222.333), (dirección, 'Cuba 33'), (edad,50)}. Esta operación añade una tupla a la extensión de la relación PERSONA dando como reultado la siguiente relación (presentada en forma tabular)

PERSONA

dni nombre dirección edad

20.450.120 Juan Pérez Cuenca 20 28

12.904.569 José Abad Blasco Ibáñez 35 39

35.784.843 María Gutiérrez Reina 7 27

11.222.333 Luisa León Cuba 33 50

12.345.67 Pepa Gómez Colón 15 37

Borrar (PERSONA, {(nombre,'José Abad'), (dni,12.904.569), (dirección, 'Ibáñez 35'), (edad, 39)}. Esta operación elimina una tupla de la extensión de la relación PERSONA dando como resultado la siguiente relación (presentada en forma tabular):

PERSONA

dni nombre dirección edad

20.450.120 Juan Pérez Cuenca 20 28

35.784.843 María Gutiérrez Reina 7 27

12.345.678 Pepa Gómez Colón 15 37

Como se puede observar en el Ejemplo 2.4, todos los operadores son unarios o binarios, es decir tienen como operandos una o dos relaciones, y dan como resultado otra relación; esta relación puede ser utilizada a su vez como operando de otro operador; permitiéndose el anidamiento de tantas operaciones como se desee (es posible, por ejemplo, obtener la proyección de una selección de la unión de dos relaciones). Así, con estos operadores se van a poder formular consultas a una base de datos relacional; el resultado de la evaluación de una expresión será una relación cuyas tuplas contendrán la información requerida por el usuario en su consulta.

Ejemplo 2.5

Consulta: "Obtener el nombre y la edad de las personas mayores de 30 años"

Persona DONDE edad>30 [nombre, edad]

En esta expresión se anidan dos operadores: Selección y Proyección. El resultado de su evaluación es la relación:

nombre edad

José Abad 39

Luisa León 50

Pepa Gómez 37

IMPLEMENTACIÓN DE RELACIONES

La estructura relación admite distintas implementaciones basadas en las diferentes organizaciones de ficheros proporcionadas por el Sistema Operativo: ficheros indexados, ficheros invertidos, ficheros con direccionamiento calculado, etc.

Ejemplo 2.6

La relación PERSONA del Ejemplo 2.2, puede implementarse como un fichero con un índice definido sobre el atributo dni:

Figura 2.1. Implementación de la relación Persona.

VALOR NULO

De las definiciones dadas se puede deducir que una tupla t es una función del conjunto de los atributos de su esquema sobre el conjunto de los valores de los dominios tal y como se representa en la figura siguiente:

Figura 2.2: Representación funcional de la tupla

de forma que si t(A_i) = v_i, entonces v_i pertenece al dominio D_i asociado a A_i en el esquema de la tupla.

Esta definición de tupla en la que todo atributo tiene necesariamente un valor asociado, no permite contemplar el caso en el que se desconoce el valor de un atributo en una tupla, situación que es frecuente cuando se representan objetos del mundo real. Por ello, y para superar esta limitación, se va a introducir la hipótesis de la existencia de un valor nulo en todo dominio de definición de las relaciones. Este valor nulo denota la ausencia de información, es decir, el desconocimiento de la propiedad representada por el atributo para el objeto representado por la tupla; cuando esto sucede se dice que dicho atributo tiene valor nulo en esa tupla. Es importante destacar que el valor nulo aún siendo un valor de cualquier dominio tiene un comportamiento especial frente a los operadores, existiendo predicados específicos para su manipulación que serán estudiados mas adelante. No existe un símbolo de constante para denotar el valor nulo, a partir de ahora en el texto se representará con el carácter ?

Ejemplo 2.7

En la tupla t = {(dni, 11.940.861), (nombre, Eva López), (dirección, ?), (edad, 60)} del esquema Persona del Ejemplo 2.1, el atributo dirección tiene valor nulo indicando que se desconoce la dirección de esta persona.

Resumiendo lo visto hasta ahora, de la definición de relación dada se deducen las siguientes características fundamentales:

no existen tuplas repetidas en una relación, ya que una relación es un conjunto de tuplas,
no existe un orden entre las tuplas de una relación por el mismo motivo. La única forma de seleccionar una tupla es especificando el valor de algunos de sus atributos en una operación de Selección.
los pares de una tupla no están ordenados entre sí, ya que la tupla es también un conjunto, de manera que la única forma de hacer referencia y acceder a un componente de una tupla es mediante el nombre de atributo correspondiente.
los operadores con los que se manipula una relación son de dos tipos: conjuntistas (Unión, Diferencia, ...) y relacionales (Selección, Proyección, ...).
la estructura de datos relación, admite distintas implementaciones. El Modelo proporciona independencia de datos.

Operadores asociados a la estructura relación. Álgebra Relacional

A continuación, se va a hacer una presentación formal de la sintaxis y semántica de los operadores de la estructura relación, que ya fueron presentados informalmente en el apartado anterior. Estos operadores constituyen el lenguaje del Álgebra Relacional.

El Álgebra Relacional es uno de los dos lenguajes que E.F. Codd propuso para su Modelo Relacional de Datos. Estos lenguajes, el Álgebra Relacional y el Cálculo Relacional, son equivalentes entre sí, en el siguiente sentido: "para cualquier expresión del Álgebra existe una expresión equivalente del Cálculo cuya evaluación devuelve el mismo conjunto de tuplas”. En este curso se estudiará sólo el lenguaje del Álgebra Relacional, en el apartado 2.3.2 se presentará las ideas básicas que subyacen a la definición del Cálculo Relacional.

Como ya se ha visto, el Álgebra Relacional consiste en un conjunto de operadores que actúan sobre relaciones; un subconjunto de ellos, los operadores básicos, fueron introducidos en el apartado anterior para presentar intuitivamente la estructura relación; los restantes operadores, los operadores derivados, se pueden definir a partir de ellos y se verán en este apartado.

Según la propuesta inicial de Codd, el Álgebra Relacional se compone de ocho operadores que se pueden clasificar en dos grupos:

Operadores conjuntistas: Unión, Intersección, Diferencia y Producto Cartesiano. Estos operadores son heredados de la estructura de datos conjunto.
Operadores relacionales: Selección, Proyección, División y Concatenación. Estos operadores son específicos de la estructura relación y son los que la diferencian del conjunto.

A continuación se introduce un ejemplo para ilustrar el comportamiento de los operadores del Álgebra Relacional.

Ejemplo 2.8

Sea el siguiente esquema de una base de datos relacional:

Río (rcod: dom_rcod, nombre: dom_nom)

Otros_Ríos (rcod: dom_rcod, nombre: dom_nom)

Provincia (pcod: dom_pcod, nombre: dom_nom)

Pasa_por (pcod: dom_pcod, rcod: dom_rcod)

cuyo significado es obvio: Río y Otros_Ríos son dos relaciones que almacenan información (código y nombre) de algunos ríos; Provincia representa los datos de interés de algunas provincias y por último la relación Pasa_por nos permite saber qué ríos pasan por las distintas provincias.

Una posible base de datos relacional del esquema anterior sería la siguiente (presentada tabularmente):

Para la definición de los operadores del Álgebra Relacional, son necesarias algunas definiciones previas. Sean:

ρ : un esquema de relación
Relación_ρ: conjunto de relaciones de esquema ρ
Tupla_ρ : conjunto de tuplas de esquema ρ.
P(ρ) :{β : β ⊆ ρ} es el conjunto de todos los subesquemas de ρ.
A_ρ :{A₁, A₂,..., A_n} es el conjunto de los nombres de atributos de ρ.
P(A_ρ) :{B : B ⊆ A_ρ} es el conjunto de los subconjuntos de A_ρ.
CONDICIÓN: conjunto de fórmulas bien formadas de un lenguaje lógico que permiten expresar propiedades sobre las tuplas.

Antes de estudiar con detalle los operadores del Álgebra Relacional, es necesario introducir el operador Renombrar que, aunque no forma parte del conjunto de operadores inicialmente propuestos por E.F. Codd, es indispensable para usar operadores del Álgebrar Relacional que tienen alguna restricción sobre la forma de sus operandos. Así mismo, se define la propiedad de compatibilidad de relaciones exigida en algunos operadores.

COMPATIBILIDAD DE RELACIONES

Se dice que dos relaciones R y S son compatibles si sus esquemas son idénticos, es decir

los esquemas de R y S tienen el mismo conjunto de nombres de atributo, y
cada nombre de atributo esté asociado al mismo dominio en ambos esquemas.

OPERADOR RENOMBRAR

El operador Renombrar cambia el esquema de la relación sobre la cual se aplica al cambiar algunos nombres de atributos.

Sea R una relación de esquema {(A₁, D₁), (A₂, D₂),..., (A_n, D_n)}. Renombrar en R los atributos A_i,..., A_j por B_i,..., B_j, denotado de la forma R((A_i, B_i),..., (A_j, B_j)), produce una relación que contiene cada una de las tuplas de R, cambiando adecuadamente los nombres de atributo.

Formalmente, esto se denota de la siguiente forma:

R((A_i, B_i),..., (A_j, B_j)) = {{(A₁, v₁),..., (B_i, v_i),..., (B_j, v_j),..., (A_n, v_n)} | {(A₁, v₁),..., (A_i, v_i),..., (A_j, v_j),..., (A_n, v_n)} ∈ R}

El esquema de la relación resultado es: {(A₁, D₁),..., (B_i, D_i),..., (B_j, D_j),..., (A_n, D_n)}.

Ejemplo 2.9

Dada la base de datos del Ejemplo 2.8 la operación:

Provincia ((pcod, código), (nombre, nom_prov))

obtiene una relación de esquema {(código, dom_pcod), (nom_prov, dom_nom)} y cuya extensión es la siguiente:

código nom_prov

44 Teruel

46 Valencia

16 Cuenca

10 Cáceres

45 Toledo

28 Madrid

08 Barcelona

OPERADORES CONJUNTISTAS

UNIÓN

Sean R y S dos relaciones compatibles cuyo esquema es ρ:{(A₁, D₁),..., (A_n, D_n)}. La unión de R y S, denotada como R ∪ S, es una relación cuyo esquema es el mismo que el de R y S, y que está formada por todas las tuplas pertenecientes a R, a S, o a ambas relaciones.

Sintaxis: Unión: Relación_ρ × Relación_ρ → Relación_ρ

Semántica: R ∪ S = { t | t ∈ R o t ∈ S}

La unión es asociativa, R ∪ (S ∪ T) = (R ∪ S) ∪ T, y conmutativa, R ∪ S = S ∪ R.

Ejemplo 2.10

Dada la base de datos del Ejemplo 2.8 la operación:

Río ∪ Otros_Ríos

obtiene como resultado una relación de esquema {(rcod: dom_rcod), (nombre: dom_nom)} y cuya extensión es la siguiente:

rcod nombre

rf1 Sena

r1 Tajo

rf2 Loira

rf3 Ródano

r2 Turia

DIFERENCIA

Sean R y S dos relaciones compatibles cuyo esquema es ρ:{(A₁, D₁),..., (A_n, D_n)}. La diferencia entre R y S, denotada como R − S, es una relación cuyo esquema es el de R y S, y que está formada por todas las tuplas que pertenecen a R y no pertenecen a S.

Sintaxis: Diferencia: Relación_ρ × Relación_ρ → Relación_ρ

Semántica: R − S = { t | t ∈ R y t ∉ S}

La diferencia no es ni asociativa ni conmutativa.

Ejemplo 2.11

Dada la base de datos del Ejemplo 2.8 la operación:

Río − Otros_Ríos

obtiene como resultado una relación de esquema {(rcod: dom_rcod), (nombre: dom_nom)} y cuya extensión es la siguiente:

rcod nombre

r1 Tajo

r2 Turia

INTERSECCIÓN

Sean R y S dos relaciones compatibles cuyo esquema es ρ:{(A₁, D₁),..., (A_n, D_n)}. La intersección de R y S, denotada como R ∩ S, es una relación cuyo esquema es el mismo que el de R y S, y que está formada por todas las tuplas pertenecientes a R y a S.

Sintaxis: Intersección: Relación_ρ × Relación_ρ → Relación_ρ

Semántica: R ∩ S = R ∩ S = { t | t ∈ R y t ∈ S}

La intersección es asociativa, R ∩ (S ∩ T) = (R ∩ S) ∩ T, y conmutativa, R ∩ S = S ∩ R.

El operador Intersección es un operador derivado que se puede definir a partir del operador Diferencia: R ∩ S = R − (R − S).

Ejemplo 2.12

Dada la base de datos del Ejemplo 2.8 la operación:

Río ∩ Otros_Ríos

obtiene como resultado una relación de esquema {(rcod: dom_rcod), (nombre: dom_nom)} y que no contiene ninguna tupla.

PRODUCTO CARTESIANO

Sean R y S dos relaciones cuyos respectivos esquemas ρ:{(A₁, D₁),..., (A_n, D_n)} y σ:{(B1, E1),..., (Bm, Em)} cumplen que no tienen ningún nombre de atributo en común. El producto cartesiano de R y S, denotado como R × S, es una relación cuyo esquema es la unión de los esquemas de R y S, y que está formada por todas las tuplas que se pueden construir uniendo una de R y una de S.

Sintaxis: Producto Cartesiano: Relación_ρ × Relación_σ → Relación_ρ ∪ σ

Semántica: R × S = { {(A₁, v₁),..., (A_n, v_n), (B₁, w₁),..., (B_m, w_m)} | {(A₁, v₁),..., (A_n, v_n)} ∈ R y {(B₁, w₁),..., (B_m, w_m)} ∈ S}

El esquema de la relación resultante de R × S es {(A₁, D₁),..., (A_n, D_n), (B₁, E₁),..., (B_m, E_m)}. El producto cartesiano cumple las propiedades asociativa y conmutativa.

Ejemplo 2.13

Dada la base de datos del Ejemplo 2.8 la operación:

Río × Provincia((nombre, nom_prov))

obtiene como resultado una relación de esquema {(rcod: dom_rcod), (nombre: dom_nom), (pcod: dom_pcod), (nom_prov, dom_nom)} y cuya extensión es la siguiente:

pcod nom_prov rcod nombre

44 Teruel r1 Tajo

46 Valencia r1 Tajo

16 Cuenca r1 Tajo

10 Cáceres r1 Tajo

45 Toledo r1 Tajo

28 Madrid r1 Tajo

08 Barcelona r1 Tajo

44 Teruel r2 Turia

46 Valencia r2 Turia

16 Cuenca r2 Turia

10 Cáceres r2 Turia

45 Toledo r2 Turia

28 Madrid r2 Turia

08 Barcelona r2 Turia

Obsérvese que para poder realizar el producto cartesiano ha sido necesario cambiar el nombre de un atributo con el operador Renombrar, ya que los esquemas de las relaciones originales no cumplían las condiciones que impone el operador Producto Cartesiano.

OPERADORES RELACIONALES

SELECCIÓN

Sea R una relación de esquema ρ:{(A₁, D₁),..., (A_n, D_n)}. La selección en R respecto a la condición F, denotada como R DONDE F, es una relación del mismo esquema que R y que está formada por todas las tuplas de R que cumplen la condición F.

Sintaxis: Selección: Relación_ρ × CONDICIÓN → Relación_ρ

Semántica: R DONDE F = { t | t ∈ R y F(t) se evalúa al valor cierto}

Las condiciones son fórmulas que se construyen a partir de comparaciones siguiendo las reglas que se enuncian posteriormente. Primero se presenta la definición de comparación.

Comparación

Una comparación es una expresión de una de las formas siguientes:

nulo(A_i),
A_i α Aj, o
A_i α a

donde α es un operador de comparación (<, >, ≤, ≥, =, ≠), A_i y Aj son nombres de atributo y a es un valor del dominio asociado al atributo A_i distinto del valor nulo.

Condición

Las condiciones se construyen aplicando las siguientes reglas:

toda comparación es una condición,
si F es una condición entonces (F) también lo es,
si F y G son condiciones entonces también lo son F∨G, F∧G y ¬F, y
nada más es una condición.

Una vez introducido el concepto de condición, hay que determinar cuándo estas expresiones se evalúan a cierto para una tupla, para ello y teniendo en cuenta la presencia de valores nulos en las tuplas, se va a utilizar una lógica trivaluada para evaluar F(t). En esta lógica existen tres valores {cierto, falso, indefinido} y las reglas de evaluación son las siguientes:

Valor de verdad de una comparación

si F es de la forma A_i α A_j entonces F(t) se evalúa a indefinido si al menos uno de los atributos, A_i o A_j tiene valor nulo en t, en caso contrario se evalúa al valor de certeza de la comparación t(A_i) α t(A_j);
si F es de la forma A_i α a entonces F(t) se evalúa a indefinido si A_i tiene valor nulo en t, en caso contrario se evalúa al valor de certeza de la comparación t(A_i) α a; y
si F es de la forma nulo(A_i) entonces F(t) se evalúa a cierto si A_i tiene valor nulo en t, en caso contrario se evalúa a falso.

Valor de verdad de una condición

El valor de verdad de una condición C se define inductivamente como sigue:

si C es una comparación entonces su valor de verdad es el de la comparación,
si C es de la forma (F) entonces su valor de verdad es el de F, y
si en C aparece alguna conectiva lógica (¬, ∧, ∨) entonces su valor de verdad es el que se muestra en las siguientes tablas:

Figura 2.3: Tablas de verdad de las conectivas lógicas ∧, ∨ y ¬

Ejemplo 2.14

Dada la base de datos del Ejemplo 2.8 la operación:

Pasa_por DONDE rcod = “r1”

obtiene como resultado una relación de esquema {(rcod: dom_rcod), (pcod: dom_pcod)} y cuya extensión es la siguiente:

pcod rcod

10 r1

45 r1

28 r1

16 r1

Esta operación permite obtener los códigos de las provincias por las que pasa el río de código "r1".

PROYECCIÓN

Sea R una relación de esquema ρ:{(A₁, D₁),..., (A_n, D_n)} y sea {A_i, A_j,..., A_k} un subconjunto de los nombres de atributo de R con m elementos (1 ≤ m ≤ n). La proyección de R sobre {A_i, A_j,..., A_k}, denotada como R[A_i, A_j,..., A_k], es una relación que extrae de las tuplas de R los valores de los atributos A_i, A_j,..., A_k.

Sintaxis: Proyección: Relación_ρ × P(A_ρ) → ∪_{β∈ P(ρ)}Relación_β

Semántica: R[A_i, A_j,..., A_k]={{(A_i, v_i), (A_j, v_j),..., (A_k, v_k)} | ∃t ∈ R tal que {(A_i, v_i), (A_j, v_j),...,(A_k, v_k)} ⊆ t }

Por lo tanto, el esquema de relación de R[A_i, A_j,..., A_k] es {(A_i, Di), (A_j, Dj),...,(A_k, Dk)}.

Ejemplo 2.15

Dada la base de datos del Ejemplo 2.8 la operación:

Pasa_por [pcod]

obtiene como resultado una relación de esquema {(pcod: dom_pcod)} y cuya extensión es la siguiente:

pcod

44

46

16

10

45

28

Esta operación permite obtener los códigos de las provincias por las que pasa algún río. Observar que la cardinalidad de esta proyección es menor que la cardinalidad de Pasa_por.

CONCATENACIÓN (NATURAL)

Sea R y S dos relaciones cuyos esquemas son respectivamente ρ:{(A₁, D₁),..., (A_n, D_n), (B1, E1),..., (Bm, Em)} y σ:{(B1, E1),...,(Bm, Em),(C1, F1),...,(Cp, Fp)}, con n≥0, m≥0, p≥0, n+m≥1, p+m≥1, y de forma que B1,..., Bm son los atributos comunes de los dos esquemas. La concatenación natural de R y S, denotada como R S, es una relación que contiene todas las tuplas que se pueden construir combinando (uniendo) una tupla de R con otra de S que tengan para cada atributo común el mismo valor.

Sintaxis: Concatenación (natural): Relaciónρ × Relaciónσ → Relación(ρ ∪ σ)

Semántica: R

S = {{(A₁, v₁),...,(A_n, v_n), (B1, w1),...,(Bm, wm), (C1, y1),...,(Cp, yp)}|

{(A₁, v₁),..., (A_n, v_n), (B1, w1),..., (Bm, wm)} ∈ R y

{(B1, w1),..., (Bm, wm), (C1, y1),..., (Cp, yp)} ∈ S }

Cuando el conjunto de atributos comunes está vacío se cumple: R

S = R × S.

La concatenación es asociativa y conmutativa. El esquema de la relación resultado de la concatenación de R y S es {(A₁, D₁),..., (A_n, D_n), (B1, E1),..., (Bm, Em), (C1, F1),..., (Cp, Fp)}. El operador Concatenación (natural) es un operador derivado que se puede definir a partir de los operadores

Producto Cartesiano, Selección y Proyección:

R

S = (R × S((B1, G1), ..., (Bm, Gm)))

DONDE (B1 = G1 ∧...∧ Bm = Gm) [A₁,..., A_n, B1,..., Bm, C1,...Cp]

Ejemplo 2.16

Dada la base de datos del Ejemplo 2.8 la operación:

Pasa_por

Provincia

obtiene como resultado una relación de esquema {(pcod: dom_pcod), (nombre: dom_nom), (rcod: dom_rcod)} y cuya extensión es la siguiente:

pcod nombre rcod

44 Teruel r2

46 Valencia r2

16 Cuenca r2

10 Cáceres r1

45 Toledo r1

28 Madrid r1

16 Cuenca r1

Esta operación permite extender la información contenida en la relación Pasa_por con el nombre de la provincia.

DIVISIÓN

Sean R y S dos relaciones cuyos esquemas son ρ:{(A₁, D₁),...,(A_n, D_n), (B1, E1),..., (Bm, Em)} y σ:{(B1, E1),..., (Bm, Em)} respectivamente. La división de R entre S, denotada como R ÷ S, es una relación que se define como sigue:

Sintaxis: División Relaciónρ × Relaciónσ → Relaciónρ - σ

Semántica: R ÷ S = { {(A₁, v₁),..., (A_n, v_n)}| ∀s ∈ S (s = {(B1, w1),...,(Bm, wm)} → ∃ t ∈ R y t = {(A₁, v₁),...,(A_n, v_n), (B1, w1),...,(Bm, wm)}) }

El esquema de R ÷ S es {(A₁, D₁),..., (A_n, D_n)}. La división no es asociativa ni conmutativa.

El operador División es un operador derivado que se puede definir a partir de los operadores Producto Cartesiano, Diferencia y Proyección:

R ÷ S = R[A₁,..., A_n] - ((R[A₁,..., A_n] × S) - R) [A₁,..., A_n]

Ejemplo 2.17

Dada la base de datos Ejemplo 2.8 la operación:

Pasa_por ÷ Río [rcod]

obtiene como resultado una relación de esquema {(pcod: dom_pcod)} y cuya extensión es la siguiente:

pcod

16

Esta operación permite obtener los códigos de las provincias por las que pasan todos los ríos de la relación Río.

Como ya se ha comentado anteriormente e incluso ilustrado en algunos ejemplos, los operadores del Álgebra Relacional pueden anidarse construyendo expresiones cuya evaluación devuelve la información requerida en una consulta; debido a esto, es necesario definir un orden de prioridad entre sus operadores que evite ambigüedades y que, evidentemente, puede ser alterado mediante el uso de los paréntesis. Este orden v_iene definido por dos niveles de prioridad, en el de mayor prioridad están incluidos todos los operadores unarios (Renombrar, Selección y Proyección), en el nivel de menor prioridad están los restantes (Unión, Intersección, Diferencia, Concatenación, Producto Cartesiano y División); por último, los operadores de igual nivel se evalúan de izquierda a derecha.

Ejemplo 2.18

Sea la siguiente consulta sobre la base de datos del Ejemplo 2.8. "Obtener el nombre de los ríos que sólo pasan por una provincia".

(Pasa_por [rcod] - ((Pasa_por (pcod, px) Pasa_por) DONDE pcod ≠ px))[rcod] ) Río)[nombre]

Observar la estructura de la expresión. El primer operando del operador Diferencia, obtiene el código de todos los ríos que pasan por alguna provincia, es decir que están presentes en la extensión de Pasa_por. El segundo operando del operador Diferencia es una operación de concatenación, en ella se obtienen los códigos de los ríos que pasan por (al menos) dos provincias, concatenando Pasa_por con Pasa_por sobre el atributo rcod, para poder hacerlo, es preciso renombrar en una de las dos ocurrencias de Pasa_por el atributo pcod como px; a continuación sobre el resultado de la concatenación se realiza una operación de selección para asegurar que las dos provincias son distintas. El resultado de la diferencia, contiene por lo tanto, los códigos de ríos que sólo pasan por una provincia. Por último la concatenación de esta última relación con la relación Río (sobre el atributo común rcod) y la posterior proyección sobre el atributo nombre devuelve los nombres de los ríos solicitados en la consulta.

RESUMEN

A continuación se describen los ocho operadores del Álgebra Relacional de forma intuitiva y gráfica:

Unión (binario): da como resultado una relación que contiene las tuplas que aparecen en cualquiera de las dos relaciones operandos.
Intersección (binario): la relación resultante contiene las tuplas que se encuentran en las dos relaciones especificadas como operandos.
Diferencia (binario): da como resultado una relación cuyas tuplas aparecen en el primer operando y no en el segundo.
Producto cartesiano (binario): las tuplas en la relación resultante son la combinación de dos tuplas de las relaciones operandos.
Selección (unario): da como resultado una relación que contiene las tuplas de la relación operando que cumplen una condición especificada.
Proyección (unario): extrae de la relación operando los valores de los atributos especificados.
Concatenación (binario): a partir de dos relaciones, produce una relación que contiene todas las combinaciones de dos tuplas, una de cada relación operando, que contienen los mismos valores en los atributos comunes.
División (binario): si, por ejemplo, los operandos son una relación binaria y una unaria de forma que el atributo de la unaria es común a ambas, el resultado es una relación unaria formada por los valores del atributo que no es común tal que cada uno de estos valores aparece combinado en tuplas de la relación binaria con todos los valores que aparecen en la relación unaria.

Figura 2.4. Representación gráfica de los operadores del Álgebra.