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.

E1 ⋈E2E2 ⋈E1

E1 ⋈FE2E2 ⋈FE1

E1 x E2E2 x E1

La reunión es

E1 ⋈F E2 F(E1 x E2)

Natural Join

Reunión

• Asociatividad para las mismas tres

operaciones. F1 y F2 son condiciones.

(E1 ⋈E2 ⋈E3E1 ⋈E2 ⋈E3

(E1 ⋈F1E2 ⋈F2E3E1 ⋈F1E2 ⋈F2E3

(E1 x E2xE3E1 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 la selección con la intersección.

F(E1 E2 ) F(E1) F(E2)

• 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 e2WHERE 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 idempFROM empWHERE dpto IN (SELECT dpto FROM dept);

SELECT idempFROM emp e, dpto dWHERE e.dpto = d.dpto;