1 1 Álgebra Relacional Universidad de los Andes Demián Gutierrez Mayo 2010

2 2 Lenguajes de Consulta Base de Datos Relacional Usuario Aplicació n Otros... Consulta Resultado Una consulta es básicamente una pregunta sobre un hecho en particular que puede o no existir en la BD El resultado de una consulta es una colección de registros de la BD (Una Relación) Todos los autos marca Ford... (Lenguaje de consulta) La consulta se realiza sobre las relaciones de la BD

3 3 Tipos de Lenguajes de Consulta ● Son lenguajes que utilizan los usuarios para solicitar información a la BD ● Hay de dos tipos ● Procedimentales ● No-procedimentales ● Lenguajes puros ● Cálculo relacional de tuplas (N/P) ● Cálculo relacional de dominios (N/P) ● Álgebra relacional (P) Estas son las bases de los lenguajes de consulta comerciales

4 4 Tipos de Lenguajes de Consulta ● Lenguajes comerciales ● SEQUEL ● QBE (N/P) ● SQL (P + N/P) ● OQL (P + N/P) (Y todos los [Object Oriented]QL) ●...entre otros El estándar “de facto” usado hoy en día en la industria es el SQL, aunque con la incursión de los SGBDOO, ORMs y tecnologías similares el OQL y sus distintas alternativas y variantes son también bastante utilizados

5 5 Cálculo Relacional de Tuplas Es un lenguaje de consulta formal que permite expresar las consultas a partir de fórmulas bien formadas, donde las variables son interpretadas como variantes sobre las tuplas de las tablas. Fue presentado por Codd en 1972 y se deduce del Cálculo de Predicados – Una consulta en CRT es una expresión de tipo: – {t,e,x | C(t,e,x)} – Donde t,e,x son variables de tuplas y C(t,e,x) es una expresión condicional donde intervienen t,e,x

6 6 Cálculo Relacional de Tuplas ● Átomos: ● Las variables están asociadas a las tuplas de las tablas y se denota como relación(variable). Ej: Modelo(M). ● Los valores constantes están asociados a los valores de los dominios de los atributos y las funciones generadoras de los mismos se denotan como variable.atributo. Ej: M.marca ● Los predicados utilizados se construyen con los operadores de comparación {, , =,  } y constantes. ● Ejm: M.marca  ‘fiat’. A modo informativo

7 7 Cálculo Relacional de Tuplas ● Una fórmula bien formada se define como: – Todo átomo es una fórmula bien formada F. – Si F1 y F2 son fórmulas bien formadas, entonces F1 and F2, F1 or F2, not F1 o not F2 son fórmula bien formada. ● F1 es una fórmula bien formada (Cuantificador existencial, se lee, existe un...). ● ∀ F1 es una fórmula bien formada (Cuantificador universal, se lee, para todo...). A modo informativo

8 8 Cálculo Relacional de Tuplas ● Ejemplo 1: Obtener la fecha de nacimiento y la dirección del empleado (o empleados) cuyo nombre es 'Pedro Pérez': ● Empleado(Cédula, Nombre, Apellido FechaN, Dirección) ● {e.FechaN, e.Dirección | Empleado(e) and e.Nombre = 'Pedro' and e.Apellido = 'Pérez'}

9 9 Cálculo Relacional de Tuplas ● Ejemplo 2: Obtener el nombre y la dirección de todos los empleados que trabajan para el departamento 'Investigación') ● Empleado(Cédula, Nombre, Apellido FechaN, Dirección, NumDpto) ● Dpto(NumDpto, NomDpto) ● {e.Nombre, e.Dirección | Empleado(e) and ( d)(Dpto(d) and e.NumDpto = d.NumDpto and d.NomDpto = 'Investigación')}

10 10 Cálculo Relacional de Tuplas Es un lenguaje de consulta formal que permite expresar las consultas a partir de fórmulas bien formadas, donde cada variable se interpreta como variante sobre el dominio del atributo de una relación. Es similar al Cálculo Relacional de Tuplas y también se deduce del cálculo de predicados

11 11 Cálculo Relacional de Dominios ● Las variables están asociadas a los dominios de los atributos y se denota como relación(att1: variable1, att2: variable2,... ) Ejm: ModeloCarro(modelo: m, marca: c) – los predicados utilizados se construyen igual que para el cálculo relacional de tuplas

12 12 Cálculo Relacional de Tuplas ● Ejemplo 1: Obtener el nombre y el color de cada producto en almacén: ● Producto(nroPro, nombrePro, cantidad, color) ● {N, C | Producto(nombrePro: N, color: C, cantidad > 0)} El resultado, a diferencia del CRT son variables

13 13 Cálculo Relacional de Tuplas ● Ejemplo 2: Obtener los clientes que han comprado al menos un producto de color verde: ● Producto(nroPro, nombrePro, cantidad, color) ● Venta(nroVen, fechaVen, nombreCliente, nroProVen, cantidadVen) ● { V, P | NP Venta(nombreCliente: V, nroProVen: NP) and Producto(nroPro: NP, nombrePro: P, color = ‘verde’) } Se produce producto por medio de la variable NP

14 14 Álgebra Relacional Es un conjunto de operaciones que describen paso a paso (procedimental) la forma de transformar una serie de relaciones en otras para así obtener una respuesta a una consulta R2 = Operación1 (R1) R3 = Operación2 (R2) R5 = Operación2 (R3, R4)... Una operación de AR toma una serie de relaciones de entrada y genera una relación de salida

15 15 Álgebra Relacional (Operaciones) Producto Cartesiano R x Q Selección σ a,b (R) Proyección ∏ a,b (R) Reunión Natural R |x| a,b Q Unión R ∪ Q Intersección R ∩ Q Diferencia R - Q División R Q Reunión Externa R  Q Unión Externa Otras... Funciones Agregadas Operación Asignación Conjunto completo de operaciones del álgebra relacional

16 16 Proyección ∏ placa, marca (Carro) ∏ marca,modelo,color (Carro) Se eliminan todas salvo una de las tuplas repetidas (Ej, )

17 17 Proyección ∏ rombos (R ) R R' Todas las tuplas, pero no completas, sólo se seleccionan algunas columnas... Se eliminan todas las tuplas duplicadas

18 18 Producto Cartesiano Carro = R x Q No es relevante para el producto cartesiano, pero es notable, que en algunas tuplas marcaR = marcaQ

19 19 Producto Cartesiano R'=R x Q R' R Q Cada tupla de uno de los conjuntos se combina con todas las tuplas del otro conjunto

20 20 Selección R = σ marca=Ford Λ color=rojo (Carro) R = σ marca=Ford (Carro)

21 21 Selección σ rombo=negro (R ) RR' Se seleccionan sólo las tuplas que cumplen una condición dada

22 22 Producto / Reunión Natural Carro=R|x| marca Q Sin embargo aquí se perdió información (Descomposición con pérdida) Carro = σ (R.marca=Q.marca) (R x Q) o bien: Carro = R |x| Q

23 23 R'=R  círculo Q R' R Q Producto / Reunión Natural Producto cartesiano con condición de igualdad, se combinan solo las tuplas con valores iguales en ciertos atributos

24 24 Unión R = E  P Se realiza una operación de unión de conjuntos. Se eliminan las tuplas repetidas Las relaciones usadas como operandos deben ser compatibles entre si

25 25 Unión Todas las tuplas de ambas relaciones (que deben ser compatibles) R'=R ∪ Q R' QR Se eliminan todas las tuplas duplicadas

26 26 Intersección R = E  P Las relaciones usadas como operandos deben ser compatibles entre si

27 27 Intersección Sólo las tuplas comunes a ambas relaciones (que deben ser compatibles) R'=R ∩ Q R' QR

28 28 Diferencia R = E - P ¿Cómo sería P – E? Las relaciones usadas como operandos deben ser compatibles entre si

29 29 Diferencia Tuplas que aparecen en la primera relación pero no en la segunda R'=R - Q R' R Q ¿Cómo sería Q – R?

30 30 División Supongamos que tenemos dos relaciones A(x, y) y B(y) donde el dominio de y en A y B, es el mismo. El operador división A  B retorna todos los distintos valores de x tales que para todo valor y en B existe una tupla en A

31 31 División R=EM  M' M'=∏ materia (σ semestre=9 (M) ) R=EM  M' Luego...

32 32 División Tuplas de la primera que contienen a todas o alguna de las tuplas de la segunda R'=R Q R' R Q

33 33 Producto / Reunión Externa R = Prof  cédula=ced_jefe Dpto ¿Dónde están los demás profesores? ¿Dónde está el departamento de Investigación? Reunión Natural

34 34 Producto / Reunión Externa R = Prof  cédula=ced_jefe Dpto Reunión Izquierda

35 35 Producto / Reunión Externa R = Dpto  cédula=ced_jefe Prof Reunión Derecha ¿Es la misma relación resultante que la de la transparencia anterior?

36 36 Producto / Reunión Externa R = Dpto  cédula=ced_jefe Prof

37 37 Producto / Reunión Externa R = Prof  cédula=ced_jefe Dpto

38 38 Producto / Reunión Externa R = σ nombreP=NULO (Dpto  cédula=ced_jefe Prof) ¿Cuáles son los departamentos sin Jefe de Departamento?

39 39 Producto / Reunión Externa R = Dpto  cédula=ced_jefe Prof Reunión Abierta

40 40 Reunión Externa Si algunas tuplas de la izquierda no tienen pareja en la derecha, entonces se rellena con valores nulos R'=R  círculo Q null R' R Q En este caso se está haciendo una reunión externa izquierda (  ), pero se puede hacer también una reunión externa derecha (  ) y una reunión externa completa (  )

41 41 Agrupación (y Funciones Agregadas) R = nacionalidad ℱ avg(edad), count (P) Se agrupan los datos usando algún tipo de criterio y luego se calculan funciones sobre los datos agrupados Posibles funciones de agregación: avg, sum, max, min, count, entre otras

42 42 Agrupación (y Funciones Agregadas) R = círculo ℱ count (R) R 12 1 R' Se agrupan las tuplas en base al valor de cierto atributo y luego se pueden calcular funciones sobre atributos de las tuplas agrupadas

43 43 Ejemplos de Álgebra Relacional ● Esquema de Ejemplo:

44 44 Ejemplos de Álgebra Relacional ● Esquema de Ejemplo:

45 45 Ejemplos de Álgebra Relacional ● TODO: Preguntas!!!

46 46 ● TODO: Falta: ● Ejercicios de Álgebra Relacional

47 47 Lenguaje de Consultas QBE ● Presentado por Zloff en el año 1977 y comercializado desde 1980 por IBM. ● Es un lenguaje de manipulación de datos gráfico. ● La idea de su construcción es la formulación de la consulta mediante un ejemplo de la posible respuesta. ● Está basado en el Cálculo Relacional de Dominios.

48 48 Lenguaje de Consultas QBE ● Las consultas se realizan invocando los esquemas de las tablas objeto de la consulta, las cuales serán desplegadas en forma gráfica en la pantalla. Una vez obtenidas, se posiciona el ratón en la o las columnas deseadas y se indica la operación a realizar.

49 49 Lenguaje de Consultas QBE ● Las variables se indican con el símbolo de subrayado como prefijo, ejemplo: _s, _3, _d5, o se subrayan, ejemplo: s, 3, d5. ● Las constantes se colocan directamente en la columna deseada precedidas por el operador de comparación deseado, si no es =. ● Toda variable desplegable está cuantificada implícitamente por el cuantificador existencial ● Todas las operaciones deben tener como sufijo un punto (Ver tabla siguiente)

50 50 Lenguaje de Consultas QBE Condiciones adicionales se expresan en una ventana aparte, en algunos SGBD. Las funciones cnt, avg, sum, min y max deben aplicarse a variables precedidas con ALL. Si no se desean eliminar las tuplas dobles en una proyección, se coloca P.ALL._v

51 51 Lenguaje de Consultas QBE Producto(nroPro, nombrePro, cantidad, color) Venta(nroVen, fechaVen, nombreCliente, nroProVen, cantidadVen) Compra(nroCom, fechaCom, nombreProveedor, nroProCom, cantidadComp) ● Esquema de Ejemplo:

52 52 Procesamiento de Consultas (Lo Básico) Análisis Léxico (separar en tokens) Optimizador de Consultas Procesamiento de la Consulta en la BD Análisis Sintáctico y Validación SELECT nombre, cedula FROM persona WHERE cedula='12.343.223' UPDATE departamento SET nombre='Control' WHERE codigo=1

53 53 Procesamiento de Consultas (Lo Básico) Conmutatividad de σ σ c1 (σ c2 (R)) = σ c2 (σ c1 (R)) Cascada de ∏ (se ignoran todas menos la última) ∏ lista1 (∏ lista2 (∏ lista3 (R))) = ∏ lista1 Cascada de σ σ c1 and c2 and c3 (R) = σ c1 (σ c2 (σ c3 (R))) Conmutación de σ con ∏ ∏ lista (σ c1 (R)) = σ c1 (∏ lista (R)) Conmutatividad de |x| o  R1  c R2 = R2  c R1

54 54 Procesamiento de Consultas (Lo Básico) ∏ apellido, nombrePR ( σ numeroPR=numPR AND cedulaEMP=cedula AND nombrePR='Acuario' AND horas < 20 ( Empleado|x| Trabaja_En |x|Proyecto)) Proyecto (numeroPR, nombrePR, descripcion) Empleado (cedula, nombre, apellido, fecha_nac) Trabaja_En (cedulaEMP, numPR, horas, categoria)

55 55 Optimización de Consultas X EmpleadoTrabaja_EnProyecto X σ numeroPR=numPR AND cedulaEMP=cedula AND nombrePR='Acuario' AND horas < 20 ∏ apellido, nombrePR

56 56 Optimización de Consultas X EmpleadoTrabaja_EnProyecto X σ numeroPR=numP R ∏ cedulaEMP=cedul a nombrePR='Acuario ' horas < 20 σ σ σ apellido, nombrePR

57 57 Optimización de Consultas X EmpleadoTrabaja_EnProyecto X numeroPR=numP R ∏ cedulaEMP=cedul a nombrePR='Acuario ' horas < 20 σ σ σ σ apellido, nombrePR

58 58 Optimización de Consultas X EmpleadoTrabaja_EnProyecto X numeroPR=numP R ∏ cedulaEMP=cedul a nombrePR='Acuario ' horas < 20 σ σ σ σ ∏ numeroPR, nombrePR apellido, nombrePR ∏ cedulaEMP, numPR, horas ∏ cedulaEMP, nombrePR ∏ cedula, apellid o

59 59 Gracias ¡Gracias!