Download Expresiones algebraicas equivalentes

Expresiones algebraicas
equivalentes
Francisco Moreno
Dos expresiones del álgebra relacional, E1 y
E2, son equivalentes si representan la
misma relación:
E1 E2
Sean E, E1, E2 y E3 expresiones del álgebra
relacional.
• Conmutatividad para reunión natural, reunión
y producto cartesiano. F es una condición que
involucra atributos de E1 y E2.
E2 ⋈ E1
E1 ⋈F E2 E2 ⋈F E1
E1 x E2 E2 x E1
E1 ⋈ E2
Natural Join
Reunión 
La reunión  es
E1 ⋈F E2  F(E1 x E2)
• Asociatividad para las mismas tres
operaciones. F1 y F2 son condiciones.
(E1 ⋈ E2 ⋈ E3 E1 ⋈E2 ⋈ E3 
(E1 ⋈F1 E2 ⋈F2 E3 E1 ⋈F1E2 ⋈F2 E3 
(E1 x E2  x E3 E1 x E2 x E3 
Donde: F1 involucra solo atributos de E1 y E2,
F2 involucra solo atributos de E2 y E3
• Las operaciones de unión en intersección
también son conmutativas y asociativas:
E1  E2  E2  E1
(E1  E2)  E3  E1  (E2  E3)
E1  E2  E2  E1
(E1  E2)  E3  E1  (E2  E3)
• Una consulta que involucra el join de N
relaciones genera T(N) * N! planes
diferentes de ejecución (planes basados
solo en asociatividad y conmutatividad)
• T(N) es el número de formas en que una
permutación particular se puede
parentizar.
• Ej: si N = 4, T(4) = 5 entonces
5 * 4! = 120 planes
Fórmula para obtener T(N)  Ver los números de Catalán
• Cascada de proyecciones.
 x1, …, xn( y1, …, yn (E))  x1, …, xn(E)
Con x1, …, xn  y1, …, yn
• Cascada de selecciones.
F1(F2(E))  F2 ^ F1(E)
Luego, se puede conmutar el lado
izquierdo:
F1(F2(E)) F2(F1(E))
• Conmutando selecciones y proyecciones.
Si F involucra solo atributos entre x1, …, xn
entonces:
x1, …, xn(F(E)) F(x1, …, xn(E))
De una manera más general, si F involucra
atributos y1, …, ym  x1, …, xn:
x1, …, xn(F (E))  x1, …, xn(F( x1, …, xn, y1, …, ym)(E))
• Conmutando selecciones con el producto
cartesiano.
Si todos los atributos usados en F
pertenecen a E1, entonces :
F(E1 x E2 ) F(E1) x E2
• Corolario 1:
Si F = F1 ^ F2 , donde F1 involucra solo
atributos de E1 y F2 involucra solo
atributos de E2, entonces :
F(E1 x E2) F1(E1) x F2(E2)
• Corolario 2:
Si F2 involucra atributos de ambas
expresiones y F1 solo de E1, entonces:
F(E1 x E2 ) F2(F1(E1) x (E2))
• Conmutando la selección con la unión.
F(E1  E2 ) F(E1)  F(E2)
• Conmutando
intersección.
la
selección
con
F(E1  E2 ) F(E1)  F(E2)
la
• Conmutando la selección con la
diferencia.
F(E1 - E2 ) F(E1) - F(E2 )
F(E1 - E2 ) F(E1) - E2
• Selección con reunión natural.
Si F involucra únicamente atributos que
son comunes a E1 y a E2, entonces :
F(E1 ⋈ E2 ) F(E1) ⋈ F(E2)
• Conmutando la proyección con un
producto cartesiano.
Sean los atributos A1,…,An de los cuales
B1,…,Bm aparecen en E1 y C1,…,Ck
aparecen en E2, entonces :
A1, …, An(E1 x E2)   B1, …, Bm(E1) x  C1, …, Ck(E2)
• Conmutando la proyección con la unión.
A1, …, An(E1  E2 ) A1, …, An(E1)  A1, …, An(E2)
• Note que esta equivalencia no se cumple para
la intersección ni para la diferencia (a menos
que A1,…, An sean todos los atributos de las
relaciones)
Un ejemplo concreto en Oracle:
CREATE TABLE emp(
cc NUMBER(8) PRIMARY KEY,
dep NUMBER(5) NOT NULL,
sal NUMBER(6) NOT NULL
);
INSERT INTO emp VALUES(1, 5, 100);
INSERT INTO emp VALUES(2, 5, 200);
INSERT INTO emp VALUES(3, 7, 100);
SET AUTOTRACE ON
Sea:
Cada empleado con todos los empleados (producto
cartesiano), pero solo se imprimen los datos de los
empleados (e1):
SELECT e1.*
FROM emp e1, emp e2;
En la siguiente consulta ¿el optimizador evita el producto?
SELECT e1.*
FROM emp e1, emp e2
WHERE e1.cc = e2.cc;
--Ahora sea:
CREATE TABLE curso(
cod NUMBER(8) PRIMARY KEY,
nom VARCHAR2(10) NOT NULL
);
INSERT INTO curso VALUES(1, 'Música');
INSERT INTO curso VALUES(2, 'Pintura');
Cada empleado con todos los cursos (producto cartesiano), pero
solo se imprimen los datos de los empleados:
SELECT e1.*
FROM emp e1, curso;
En la siguiente consulta ¿el optimizador evita el producto?
SELECT DISTINCT e1.*
FROM emp e1, curso;
• Otra prueba: Hacer un join entre las tablas
A y B donde B tiene un atributo que es
clave foránea con respecto a la clave
primaria de A. Ver que sucede si solo se
seleccionan en la consulta los datos de la
tabla B.
Considere también transformaciones como las siguientes.
“Imprimir el código de todos los empleados cuyos dptos.
aparecen en la tabla dept”
• Compare estas dos consultas:
SELECT idemp
FROM emp
WHERE dpto IN (SELECT dpto FROM dept);
SELECT idemp
FROM emp e, dpto d
WHERE e.dpto = d.dpto;