9. Procesamiento de queries

9.1 Introducción

9.2 Heurísticas generales

  • ejecutar selecciones tan pronto como sea posible
  • remplazar expresiones de la forma

    p1 ^ p2 (e)

    por

    p1 ( p2 (e) )

  • ejecutar proyecciones tan pronto como sea posible
  • escoger un orden óptimo para el equi-join el cual es conmutativo

9.3 Reglas de Transformación

9.4 Heurísticas de optimización

  1. Generar el árbol canónico para el query
  2. Mover al nivel más bajo posible usando las reglas 2,4 y 6
  3. Reordenar el árbol de modo que las 's que producen menos tuplas se ejecuten primero (regla 9)
  4. Mover al nivel más bajo uando las reglas 3,4 y 7

9.5 Arbol Canónico

Arbol de una expresión relacional

Representación de un query en SQL previo a su optimización

  • las hojas representan las relaciones de entrada
  • los nodos internos representan operadores del álgebra relacional
  • su ejecución supone que los operadores se aplicarán tan pronto como sus operandos estén disponibles, sustituyendo el nodo por la relación resultante
  • la ejecución termina al aplicarse el operador representado por el nodo raíz

9.6 Ejemplos

9.6.1 Ejemplo 1

select vive.pnombre , cd

from vive, trabaja

where vive.pnombre = trabaja.pnombre and cnombre = 'FBC';

puede expresarse como:

vive.pnombre,cd ( cnombre='FBC' (vive |X| trabaja ))

y su árbol canónico sería

vive.pnombre,cd
|
cnombre='FBC'
|
|X|
/          \
vive             trabaja

vive.pnombre,cd
|
cnombre='FBC'
|
|X|
/          \
vive             trabaja

aplicando regla 6

vive.pnombre,cd
|
|X|
/      \
              vive              cnombre='FBC'
                 |
                    trabaja

aplicando regla 7

|X|
/        \
pnombre,cd            pnombre
 |                          |
             vive              cnombre='FBC'
                            |
                             trabaja

pnombre,cd(vive) |X|   pnombre(  cnombre='FBC' (trabaja) )

9.6.2 Ejemplo 2

Query: nombres de los estudiantes que toman cursos de "ii"

select nombre

from estudiantes e, est_cursos s

where e.id = s.id and depto='ii';

expresión en algebra relacional

nombre ( depto='ii' (estudiantes |X| est_cursos))

nombre
|
depto='ii'
|
|X|
/       \
estudiantes    est_cursos

 
aplicando regla 6
nombre
|
|X|
/       \
estudiantes    depto='ii'
                     |
                         est_cursos

nombre ( estudiantes |X| depto='ii'(est_cursos))

9.6.3 Ejemplo 3

Query:ids de los estudiantes de "is" que cursan materias de "ii"

select id

from estudiantes e, est_cursos s

where e.id = s.id and carrera='is' and depto='ii'

expresión en algebra relacional

nombre ( carrera='is' and depto='ii' (estudiantes |X| est_cursos))

id
|
carrera='is' and depto='ii'
|
|X|
/       \
estudiantes    est_cursos

 
aplicando regla 6
id
|
|X|
/       \
carrera='is'    depto='ii'
|                     |
 estudiantes                est_cursos
aplicando regla 7
|X|
/    \
id     id
/       \
carrera='is'    depto='ii'
|                     |
 estudiantes                est_cursos

id ( carrera='is' (estudiantes)) |X| id ( carrera='is' (est_cursos))

9.6.4 Ejemplo 4

Query: id,nombre y calificación de los estudiantes con id>103000 y cursos reprobados

select e.id, nombre, calif

from estudiantes e, est_cursos s

where e.id=s.id and e.id>103000 and calif <7.5

en álgebra relacional

nombre, id, calif ( id>103000 and calif < 7.5 (estudiantes |X| est_cursos))

nombre,id,calif
|
id>103000 and calif<7.5
|
|X|
/       \
estudiantes    est_cursos
nombre,id,calif
|
|X|
/         \
id>103000     calif<7.5
|                   |
estudiantes    est_cursos
|X|
/              \
nombre,id         id,calif
|                   |
id>103000     calif<7.5
|                   |
estudiantes    est_cursos
aplicando regla 4
|X|
/              \
id>103000  id>103000 and                    calif<7.5    
|                   |
nombre,id       id,calif
|                   |
estudiantes    est_cursos

9.6.5 Ejemplo 5

Query: nombres de estudiantes de 'is' y descripción de los cursos tomados

select nombre, desc

from estudiantes e, est_cursos s, cursos c

where carrera='is' and e.id=s.id and s.depto=c.depto and s.num=c.num;

en álgebra relacional

nombre,desc ( carrera='is' (estudiantes |X| est_cursos |X| curso))

nombre,desc
|
carrera='is'
|
|X|
/             \
estudiantes     |X|
                      /       \
                  est_cursos      curso
aplicando regla 6
nombre,desc
|
|X|
      /               \
carrera='is'      |X|
     |                    /       \
 estudiantes       est_cursos     curso
aplicando estadísticas de tablas
nombre,desc
             |
           |X|
            /        \
                     |X|          curso
  /         \
carrera='is'      est_cursos 
  |                    
estudiantes