Download Descargar - John Freddy Duitama

Optimización Algebraica.
Profesor:
John Freddy Duitama Muñoz.
Facultad de Ingeniería.
U.de.A.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 1
Optimización algebraica.
Sea la consulta : s
A= d (AB
BC)
Estrategias:
 Reunión natural y luego selección.
 Selección y luego reunión natural.
En general menor costo para la segunda
Definición: Equivalencia de expresiones.
Dos relaciones son iguales si coinciden en su esquema, sin
importar el orden de los atributos.
Dos expresiones del algebra E1 y E2 son equivalente si
representan la misma relación. E1  E2
John Freddy Duitama
U.de.A. Facultad de Ingeniería 2
Leyes del álgebra relacional.
Sean E1, E2 y E3 expresiones del álgebra relacional.
1. Ley conmutativa para la reunión natural, la reunión- q y
el producto cartesiano.
Sea F una condición en los atributos de E1 y E2. Entonces:
1.1. E1 E2  E2 E1
1.2. E1 E2  E2 E1
F
F
1.3 E1 x E2  E2 x E1
• Nota: No importa el orden de los operandos.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 3
Leyes del álgebra relacional.
2. Ley asociativa para la reunión natural, la reunión- q y
el producto cartesiano.
Sean F1 y F2 condiciones en los atributos de E1 y E2.
2.1. (E1 E2) E3  E1 (E2 E3 )
2.2. (E1 E2) E3  E1 (E2 E3 )
F
1
F
2
F
1
F
2
2.3. (E1 x E2 ) x E3  E1 x ( E2 x E3 )
• Nota: Puedo agrupar los pares que más me convengan.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 4
Leyes del álgebra relacional.
3. Cascada de proyecciones.
p x1,…,xn (p y1,…,yn (E) )  p x1,…,xn (E)
Siempre que {x1,…,xn}  {y1,…,yn}
• Nota: Puedo suprimir la proyección más interna.
4. Cascada de selecciones.
s F1(s F2 (E) )  s F2 ^ F1 (E)
Corolario: Puedo conmutar el lado izquierdo:
•
s F1(s F2 (E) )  s F2(s F1 (E) )
Nota: ejecuto las selecciones en el orden que más me
convenga.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 5
Leyes del álgebra relacional.
5. Conmutando selecciones y proyecciones.
5.1. Si F involucra solo atributos que  {x1,…,xn}, entonces :
p x1,…,xn ( sF (E) )  sF (p x1,…,xn (E))
Nota: Puedo escoger a conveniencia el orden.
5.2. Si F involucra atributos y1,…yn que no estan entre x1,…,xn :
p x1,…,xn ( sF (E) )  p x1,…,xn ( sF (p x1,…,xn,y1,…,yn) (E) )
Nota: Proyecto solo los atributos que requiero para después.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 6
Leyes del álgebra relacional.
6. Conmutando selecciones con el producto cartesiano.
Si todos los atributos usados en F pertenecen a E1, entonces :
s F (E1 x E2 )  s F (E1) x E2
• Nota: Puedo realizar primero la selección y luego el producto.
6.1. Corolario:
Si F = F1 ^ F2 ,
Donde F1 involucra solo atributos de E1
F2 involucra solo atributos de E2. , entonces :
s F (E1 x E2 )  s F1 (E1) x s F2 (E2 )
John Freddy Duitama
U.de.A. Facultad de Ingeniería 7
Leyes del álgebra relacional.
6.2. Corolario:
Si F2 involucra atributos de ambas expresiones
F1 involucra solo atributos de E1, entonces :
s F (E1 x E2 )  s F2 ( s F1 (E1) x (E2 ) )
Nota: Siempre que sea posible ejecuto primero las
operaciones unarias y luego las binarias.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 8
Leyes del álgebra relacional.
7. Conmutando la selección con la unión.
s F (E1 U E2 )  s F (E1) U s F (E2 )
8. Conmutando la selección con un conjunto diferencia.
s F (E1 - E2 )
s F (E1 - E2 )


s F (E1) - s F (E2 )
s F (E1) - E2
9. Conmutando la Selección con la reunión natural.
Si F involucra únicamente atributos compartidos por E1 y E2,
entonces :
s F (E1  E2 )  s F (E1)  s F (E2 )
John Freddy Duitama
U.de.A. Facultad de Ingeniería 9
Leyes del álgebra relacional.
10.Conmutando proyección con un producto cartesiano.
Sea los atributos:
B1,…,Bm que aparecen en E1 y
C1,…,Ck que aparecen en E2, entonces :
p B1,…,Bm,C1,...,Ck (E1 x E2 )  p B1,…,Bm (E1) x p C1,…,Ck (E2)
11. Conmutando una proyección con una unión.
p A1,…,An (E1 U E2 )  p A1,…,An (E1) U p A1,…,An (E2)
John Freddy Duitama
U.de.A. Facultad de Ingeniería 10
Algoritmo para optimizar expresiones relacionales.
Entrada :
Una expresión del algebra relacional equivalente a la consulta
del usuario.
Salida : Un programa para evaluar tal expresión.
Método:
Ejecutar en orden los pasos que ilustraremos con un ejemplo.
Sean las relaciones existentes en la Base de datos:
• Libro(Código,Título,Autor,Editor,)
• Usuario(Cédula,Nombre,Dirección,Ciudad)
• Préstamo(Código,Cédula,Fecha)
John Freddy Duitama
U.de.A. Facultad de Ingeniería 11
Algoritmo para optimizar expresiones relacionales.
ptítulo,autor,editor,código,cédula,nombre,dirección,ciudad,fecha
slibro.código= préstamo.código
and préstamo.cédula = usuario.cédula
X
X
USUARIO
John Freddy Duitama
Sea la vista LibrosPrestados =
LIBRO
PRESTAMO
Dos
producto
cruz,
una
selección y una proyección.
O dos reuniónes naturales y una
proyección.
U.de.A. Facultad de Ingeniería 12
Algoritmo para optimizar expresiones relacionales.
SELECT titulo
FROM LibrosPrestados
WHERE fecha > 10/10/2001.
ptitulo
sfecha > 10/10/2001
Consulta del usuario
utilizando
la
vista
existente en la B. De D.
PASO 1:
La consulta escrita en
S.Q.L es convertida a su
equivalente en álgebra
relacional.
LIBROSPRESTADOS
John Freddy Duitama
U.de.A. Facultad de Ingeniería 13
Algoritmo para optimizar expresiones relacionales.
ptitulo
sfecha > 10/10/2001
ptitulo,autor,editor,código,cédula,nombre,direccion,ciudad,fecha
slibro.código= préstamo.código AND préstamo.cédula = usuario.cédula
X
X
USUARIO
John Freddy Duitama
LIBRO
PASO 2:
Reemplazo la vista por
su definición.
PRESTAMO
U.de.A. Facultad de Ingeniería 14
Algoritmo para optimizar expresiones relacionales.
ptitulo
sfecha > 10/10/2001
ptitulo,autor,editor,código,cédula,nombre,direccion,ciudad,fecha
slibro.código= préstamo.código
s préstamo.cédula = usuario.cédula
X
X
LIBRO
PASO 3:
Use ley 4 para separar
cada selección con
condiciones
de
la
forma F1 ^ F2.
USUARIO
John Freddy Duitama
PRESTAMO
U.de.A. Facultad de Ingeniería 15
Algoritmo para optimizar expresiones relacionales.
ptítulo
ptítulo,autor,editor,código,cédula,nombre,dirección,ciudad,fecha
s libro.código= préstamo.código
X
LIBRO
spréstamo.cédula = usuario.cédula
X
USUARIO
sfecha > 10/10/2001
PASO 4:
Use leyes 4 a 8, para
mover cada selección
tan abajo en el árbol
como sea posible.
PRESTAMO
John Freddy Duitama
U.de.A. Facultad de Ingeniería 16
Algoritmo para optimizar expresiones relacionales.
ptitulo
Regla 3.
s libro.código= préstamo.código
X
LIBRO
s préstamo.cédula = usuario.cédula
X
USUARIO
sfecha > 10/10/2001
PRESTAMO
John Freddy Duitama
Paso 5:
Use reglas 3,5, 10 y 11
para
mover
las
proyecciónes tan abajo
en el árbol como sea
posible.
U.de.A. Facultad de Ingeniería 17
Algoritmo para optimizar expresiones relacionales.
ptitulo
slibro.código= préstamo.código
ptitulo,libro.código,préstamo.código
X
LIBRO
s préstamo.cédula = usuario.cédula
X
USUARIO
sfecha > 10/10/2001
Regla 5.2.
Se agrega una proyección con los
atributos que serán necesarios
posteriormente.
Paso 5:
Use reglas 3,5, 10 y 11
para
mover
cada
proyección tan abajo en
el árbol como sea
posible.
PRESTAMO
John Freddy Duitama
U.de.A. Facultad de Ingeniería 18
Algoritmo para optimizar expresiones relacionales.
ptitulo
s libro.código= préstamo.código
X
ppréstamo.código
ptitulo,libro.código
s préstamo.cédula = usuario.cédula
LIBRO
X
USUARIO
Regla 10
sfecha > 10/10/2001
Paso 5:
Use reglas 3,5, 10 y 11
para
mover
cada
proyección tan abajo en
el árbol como sea
posible.
PRESTAMO
John Freddy Duitama
U.de.A. Facultad de Ingeniería 19
Algoritmo para optimizar expresiones relacionales.
ptitulo
s libro.código= préstamo.código
X
ppréstamo.código
ptitulo,libro.código
s préstamo.cédula = usuario.cédula
LIBRO
X
pusuario.cédula
ppréstamo.cédula, préstamo.código
USUARIO
John Freddy Duitama
sfecha > 10/10/2001
Paso 5:
Uso reglas 5.2 y 10
para
mover
la
proyección tan abajo en
el árbol como sea
posible.
PRESTAMO
U.de.A. Facultad de Ingeniería 20
Algoritmo para optimizar expresiones relacionales.
ptitulo
s libro.código= préstamo.código
X
ppréstamo.código
ptitulo,libro.código
s préstamo.cédula = usuario.cédula
LIBRO
X
pusuario.cédula
ppréstamo.cédula, préstamo.código
USUARIO
John Freddy Duitama
sfecha > 10/10/2001
PRESTAMO
Paso 6:
Particionar los nodos interiores
del árbol resultante en grupos:
Todo nodo interior representando
una operación binaria, ( x , U , - )
conforma un grupo.
Se incluyen además en el grupo
todos sus ancestros inmediatos
que
representen
operaciones
unarias
Tambien
se
incluyen
los
descendientes
representando
operaciones unarias, excepto en
los casos que aparezca una
operación binaria en el camino.
U.de.A. Facultad de Ingeniería 21
Bibliografía.
• Jeffrey D. Ullman. Principles of Database and
Knowledge-Base System. Volúmenes II. Computer
Science Press. 1988. Capítulo 11. pp. 662-673.
• Copyright: Esta presentación puede ser reproducida
solo para fines académicos y mencionando siempre
al autor.
John Freddy Duitama M.
Universidad de Antioquia.
Facultad de Ingeniería.
John Freddy Duitama
U.de.A. Facultad de Ingeniería 22