algebra relacional

Temario
 Introducción y fundamentos

 Introducción a SQL
 Modelo Entidad / Relación
 Modelo relacional
 Diseño relacional: formas normales

 Consultas
– Cálculo relacional
– Álgebra relacional
 Implementación de bases de datos

– Estructura física: campos y registros
– Indexación
• Índices simples
• Árboles B
• Hashing

– Compresión
1

Cálculo y álgebra relacional
Formalismos para expresar operaciones de recuperación sobre una BD
en modelo relacional
– Cálculo es declarativo, álgebra es procedural

 Cálculo y álgebra son formalismos distintos pero lógicamente equivalentes
– Toda expresión de cálculo se puede expresar en álgebra y viceversa (Th Codd)
– Es decir, permiten expresar las mismas consultas

 Un lenguaje de consulta es completo sipermite expresar cualquier consulta
del cálculo relacional
– Generalmente los SGBDs proporcionan un lenguaje completo con extensiones

2

Cálculo y álgebra relacional (cont)
 Utilidad del cálculo relacional
– Es más adecuado para establecer y verificar propiedades formales,
la consistencia de los modelos relacionales y sus formalismos
– Es útil para verificar detenidamente la corrección deaspectos complejos
o delicados en ciertas consultas que lo precisen
– La creación original del modelo relacional se fundamenta en el cálculo relacional
Interesa entenderlo para una comprensión más profunda del modelo relacional
y el fundamento de la tecnología de bases de datos

 Utilidad del álgebra relacional
– Se utiliza con fines más prácticos; es más manejable que SQL para diseñarconsultas complejas
– Los motores de SQL basan su representación interna de las consultas
en álgebra relacional (SQL se “parsea” a una estructura interna de álgebra)
3

Temario
 Introducción y fundamentos

 Introducción a SQL
 Modelo Entidad / Relación
 Modelo relacional
 Diseño relacional: formas normales

 Consultas
– Cálculo relacional
– Álgebra relacional
 Implementaciónde bases de datos

– Estructura física: campos y registros
– Indexación
• Índices simples
• Árboles B
• Hashing

– Compresión
4

Cálculo relacional
 Subconjunto del cálculo de predicados de primer orden
 Una consulta básica tiene la forma { t | cond (t) }, donde…
– t representa una variable de tupla
– cond es una expresión condicional
– La expresión representa (literalmente) unconjunto de tuplas
que cumplen la condición

 Ejemplo: { t | Vuelo(t) and t.origen = ‘LHR’ }

 Pero se pueden formular consultas más elaboradas
 Vamos a ver la forma general…

5

Forma general de una consulta
{ variables | condición }

6

Variables de una consulta
 Representan tuplas de esquemas relacionales
 Pueden ser una o más
{ t1, t2, …, tn | condición }

 Puedenindicarse atributos específicos de las variables
(y mezclar variables con y sin atributos…)
{ t1 . A, t1 . B, t1 . C, t2, …, tn | condición } /* A, B, C atributos de t1 */

7

Condición de una consulta
 Es una expresión (fórmula) de cálculo de predicados de primer orden
 Puede ser (definición recursiva):
1. Una fórmula atómica…
a) R(t), donde R es un esquema relacional, y t es unavariable de tupla

b)

t1 . A op t2 . B

o bien

t1 . A op c

donde…

t1 y t2 son variables de tupla
A y B son atributos, c es una constante
op es un operador de comparación: =, , ,  /* Se puede ampliar… */

2. Operadores and, or, not aplicados a fórmulas
3. t, t aplicados a fórmulas

 Ejemplo: supongamos Usuario (nombre, nick), Contacto (usuario1, usuario2)
{ u2 . nombre | u1  cont ( Usuario (u1) and Usuario (u2) and Contacto (cont)
and cont . usuario1 = u2 . nick and cont . usuario2 = u1 . nick
and u1 . nombre = ‘María’ ) }

8

Variables en una consulta
En una condición sólo pueden aparecer dos tipos de variables:
 Las variables propias de la consulta
 Variables cuantificadas con  o  dentro de la condición
 Todas deben llevar una condición de tipo...