PDF de programación - 8. Procesamiento de consultas - Ficheros y bases de datos

Ficheros y bases de datos

8.1.
8.2.
8.3.
8.4.



Contenido:
8. Procesamiento de consultas
Visión general
Reescritura. Reglas de equivalencia del álgebra relacional
Heurísticas para la optimización
Coste
8.4.1. Atributos
8.4.2. Medidas
8.5.1. Ordenación externa
8.5.2. Selección
8.5.3. Reunión simple (condición θsimple)
8.5.4. Reunión compleja (condición θcompuesta)
8.5.5. Eliminación de duplicados
8.5.6. Proyección
8.5.7. Operaciones sobre conjuntos

Ejecución

8.5.

Bibliografía


8. Procesamiento de consultas

8.1. Visión general


TAREAS

DIAGRAMA DE FLUJO
DEL PROCESAMIENTO

DE CONSULTAS

• Análisis

(Compiladores)

• Consistencia

(Esquema, tipos,
parámetros...)
• Representación

con grafos o
árboles

• Reescritura para

optimizar

• Coste:

Estimación
Estadística
Índices

•

• Ejecución

Consulta

Analizador y

traductor

Expresión del

álgebra
relacional

Optimizador

Plan de
ejecución

Motor de
evaluación

Resultado de
la consulta

EJEMPLO

select saldo
from cuenta
where saldo < 500000

σ <
saldo

500000

(
π

saldo

(

cuenta

))

<σπ
saldo

saldo

(

500000 cuenta

(

))

Estadísticas de los datos

saldoπ

<σ
saldo

500000

índice
;

_

saldo

cuenta

Datos

saldo

15.000
100.000
300.000
...



7-1

Ficheros y bases de datos



8.2. Reescritura. Reglas de equivalencia del álgebra relacional
Equivalencia semántica: igual esquema, igual número de tuplas (quizás en diferente orden).
Sean:
θ condición simple
L lista de atributos
R , S y T relaciones
attrib

1) Operaciones σ, π, × ,

es el conjunto de atributos que aparecen en X .

(X

)

σ
θ
1
σσ
2
θ

(
=

K

∧∧
θ
n
R
))
(

)

R
σ
θ
1
(
σσ
1
θ

=
(

2
θ

(
L
R
))


(
σ
n
θ

(

R

)

)



L



nL

⊆⊆

⊆
en el caso general
=

))

R

(

(



θ

attrib
(

R

)



θ><
1.1) Cascada (secuencia) de σ:
(
1.2) Conmutatividad deσ:
1.3) Cascada de π:
(
(
π
Ln
(
(
π
Ln

R
))
R
))

i)
ii)

θ
1



R



L

(

∧

(

∧

(

S

)

R

)

R

R

S
)(

i)
ii)

i)
ii)

><
)
⊆

attrib
(

πσ
L

π
L
1
π
L
1

(
L
(
L

L
L2

)
=L
)
=
L

σ
><
θ
R
(
σ
θθ
2
1
attrib
(
θ
1

L
π
, si
L
1
1
R
(
)
π
LL
nL
∩∩∩
1
2
R
(
))
(
1.4) Conmutatividad de σ con π:
σπ
L
θ
SR
RS
1.5) Conmutatividad de × :
×=×

S
S
R
1.6) Conmutatividad de >< :
>< =
><
1.7) Distributividad de σ con ><:
attrib
R
S
(
)
=
σ
, si
><
θ
S
R
S
(
(
(
))
(
)
σ
σ
=
><
θ
θ
2
1
R
attrib
attrib
(
(
)
)
∧
⊆
θ
2
1.8) Distributividad de σ con × :
attrib
S
R
)(
(
)
⊆θ
×
σ
×
=
σ
, si
θ
θ
SR
R
S
(
(
))
))
)
(
(
(
, si
σ
×
σ
=
σ
θθ
θ
θ
2
1
2
1
attrib
attrib
R
S
attrib
attrib
(
)(
)
)
(
(

⊆
θ
∧
θ
⊆
2
1
R
SR
(
)
(
(
))
1.9) Distributividad de π con × :
×
×
π
π
=
L
L
1
attrib
S
)(

1.10) Distributividad de π con >< :
))

SR
)
×
)

)(
⊆θ
))
, si
attrib

S
))
(
π

R
(
R
(
⊆
=

π
L
π
L
L
1
C
1

><
θ
attrib
attrib

S
R
(
)
(
(
π
π
=
><
L
L
θ
2
1
S
R
((
))
(
)
=
ππ
><
L
CL
∪
1
1
attrib
S
L
R
)(
(
)
∧
⊆
∧
2
attrib
attrib
CR
)(
(
)
)(
θ
=
∩
∧
θ
2
TS
SR
T
R
(
)
)
(
1.11) Asociatividad de × :
×
×
×
=×

R
R
T
S
(
)
(
1.12) Asociatividad de ><:
=
><
><
><
S
R
(
)
1.13) Asociatividad de
θ>< :
><
θ
RS
S
attrib
R
attrib
)
(
)(
∪
∧
attrib
S
T
attrib
)(
)
(
∪
∧
attrib
attrib
R
T
(
(
)
)
∪

attrib
(
θ
RS
attrib
(
θ
ST
attrib
(
θ
RT

attrib
(

⊆
⊆
⊆

⊆∧

i)
ii)

)
)
)

θθ
RT

, si

><

><

CL
∪
2

L
2

L
1

⊆

R

)

S

∧

ST

θ

(

θ



1.14) Equivalencia con σ, × y ><:

=

SR
(
× )
θσ
R
(
θσ
1

><

2
θ

R
S

><
θ
S
R
)
= ><

2
θθ

1
∧

i)
ii)


S



7-2

)



(
π
L
2

(

S

))

, si

R

)

⊆∧

L
2

attrib

S
)(



L
⊆
1
S
)))
(

attrib
(
, si

2

∩

attrib

S
)(



T
)
><
T
R
=



><

θθ
RT

RS

∧

(

S

><

θ
ST

T

)

, si




2) Operaciones con conjuntos

Ficheros y bases de datos

R

,

SR

∩=∩

S

R



SR

∪=∪

S

)

(

T

SR

2.1) Conmutatividad de ∪ y ∩ . – no lo es.
2.2) Asociatividad de ∪ y ∩ .
∪∪=∪∪

(
)
,
2.3) Distributividad de σ con ∪ :
σ
θ
2.4) Distributividad de σ con ∩ y –: Si
2.5) Distributividad de π con ∪ :

R

T

S

(

π
L

)

SR
T
S
)
)
∩∩=∩∩

SR
S
(
(
(
))
σ
∪

θ
SR
(
)
=Δ
σ
θ
S
(
(
))

π
∪
L

R
T
(
R
(
))
(
σ
=∪
θ
},{ −∩∈Δ
(
σ

θ
R
(
(
))
π
=∪
L

SR

)

(

(

R

))

S
Δ



8.3. Heurísticas para la optimización
En general se pueden aplicar reglas heurísticas simples tales como:
- Realizar las operaciones σ tan pronto como sea posible.
- Realizar las operaciones π tan pronto como sea posible, pero no antes de las operaciones σ.

Esquema de un algoritmo de optimización algebraico heurístico que incorpora las reglas de
equivalencia:
1. Usando la regla 1.1, descomponer las operaciones σcon condiciones conjuntivas en una

secuencia de operaciones σ. Permite mayor libertad al mover los nodos σ en el árbol.

2. Usando las reglas 1.2, 1.4, 1.7, 1.8, 2.3 y 2.4 (distributividad de σ con otras operaciones),

mover las operaciones σ hacia los nodos hoja tanto como sea posible.

3. Usando las reglas 1.5, 1.6 (conmutatividad), 1.11, 1.12, 1.13 y 2.2 (asociatividad),

reorganizar los nodos hoja según:
• Mover las operaciones σ más restrictivas hacia los nodos hoja tanto como sea posible.
• Asegurarse de que el orden de los nodos hoja no provocan operaciones × .

4. Usando la regla 1.14, combinar la operación × con una operación σ subsiguiente dando

como resultado una operación ><.
5. Usando las reglas 1.3, 1.4, 1.10 y 2.5 (secuencias de σ y conmutatividad/distributividad de
π con otras operaciones), separar y mover listas de los atributos hacia los nodos hoja tanto
como sea posible, creando las operaciones π necesarias.

6. Identificar los subárboles que representan grupos de operaciones que se puedan ejecutar por

un único algoritmo.

=

'

∧

>

2

4

=

∧

SSN

PNO

ESSN

BDATE

LNAME

PNAME

(
σ
(
1σ
c

Aquarius
'
∧
×

PNUMBER
=
PWE
)),

Ejemplo:
SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME=’Aquarius’ AND PNUMBER=PNO AND ESSN=SSN AND BDATE>’1957-12-31’
ON
π
π
c
1
c
c
c
4
E


(
×
c
c
c
∧∧∧
3
Aquarius
PNAME
,'
'
=
PNUMBER
PNO
,
=
SSN
ESSN
,
=
BDATE
1957
'
>
W
EMPLOYEE

LNAME
=
=
=
=
=

12
,'31
−
WORKS
=

EMPLOYEE

PROJECT

WORKS

PON

1957
'

12
−−

×

=

−

_

_

'31

2

3

(

,

,

×

PROJECT

)

=

7-3





Ficheros y bases de datos

))

PWEc
(

×

×

4

∧∧∧σπ
c
3

LNAME

c
2

c
1

(

Con los pasos 1 y 2 del algoritmo se pasa a (b):



π
×
Con el paso 3 se pasa a (c):

(
σσσ
c
4

LNAME

WE

)

(

(

(

c

2

c
3

)

×

σ
c
1

(

P

)))



7-4





Ficheros y bases de datos



LNAME

(
σσσ
c
1

π
×
Con el paso 4 se pasa a (d)

WP
)

(

(

(

c
3

c
2

)

×

σ
c
4

(

E

)))



LNAME

((
σ
c
1

(
π
σ
c
4
Aplicando el paso 5 se pasa a (e):

><

><

W

P

)

(

)

c
2

c
3

(

E

)))



7-5





Ficheros y bases de datos

8.4. Coste
Estimación del coste. Atributos, medidas y métricas.



8.4.1.
Atributos que determinan la estimación del coste [Def. atributo: Pressman]:

Atributos

Atributos para relaciones:
rn número de tuplas de la relación r .
rb número de bloques que contienen tuplas de la relación r .
rt tamaño en bytes de una tupla de la relación r .
rf factor de bloqueo de la relación r = número de tuplas por bloque
rAV
),
(
Aπ=
rAV
(
=),
•
rACS
es la cardinalidad media de la selección del atributo A en la relación r .
(
),
=rACS
(
1),
•
rACS
),

número de valores distintos del atributo A en la relación r .
si A es un atributo clave.

si A es un atributo clave.
n
(
distribuciones.

r
rAV
),

r
)(
rn

•

•
•
•
•
•

•



rt

(

=



para una distribución uniforme. Se pueden elegir otras

rf =3

rb

...

7-6

r







Se cumple

b
r

=

⎡
⎢
⎢

n
f

r

r

⎤
⎥
⎥

Ficheros y bases de datos

si las tuplas se almacenan contiguas físicamente.

Idealmente las medidas de los atributos se deben realizar cada vez que se modifique una tabla.
Como esto es costoso, se hace en los intervalos de menos carga del sistema.


Atributos para los índices:
ig grado de salida de los nodos internos del índice i (para índices con estructura de árbol).
iAA el el número de niveles del índice i para la relación r .
•
•

1=iAA
para tablas hash
⎡
⎤))
AA
log
i =


rAV
(
,

(

ig

•
•



Medidas

Tiempo de acceso a disco >
Fácil

8.4.2.
• Tiempo de acceso a disco
• Tiempo de UCP
• Tiempo de comunicación (SGBDs distribuidos o paralelos)
Cuantitativamente:
Realización de la medida:
Suposición: todas las transferencias de bloques a disco tienen el mismo coste (ignora la latencia
rotacional de disco y el tiempo de búsqueda).
Por lo tanto, la medida se toma como el número de transferencias de bloques.

8.5. Ejecución
Las diferencias entre estrategias diferentes son de varios órdenes de magnitud.
Para todos:

Tiempo de UCP
Difícil

coste del algoritmo



≡AiE

iA

JOIN, INTERSECTION

Ordenación externa

8.5.1.
• ORDER BY
•
• Eliminación de duplicados en la selección y proyección
•


[Wirth94]

Selección

8.5.2.
Suposición: Archivo -> relación, registro -> tupla.
1 Condición de igualdad
E =1
A1- Búsqueda lineal.
A

b
r

Se recorren todos los bloques

A2- Búsqueda binaria.

E

A

2

=

log2
⎡

b
r

⎤

+

rACS
),

(
f

r

⎡
⎢
⎢

1



⎤
−⎥
⎥

espacio en bloques ocupado por los

coste de localizar la primera tupla (número de bloques accedidos).
⎤
⎥
⎥

⎤rb2
log
⎡
rACS
(
),
⎡
⎢
rf
⎢
selección)
- 1, menos el que ya se ha encontrado
Para una distribución uniforme de valores se cumple (no siempre es cierto):

rACS
),

(

registros (los que satisfacen la

7-7




rACS
),

(

=

n
(

r
rAV
),

Ficheros y bases de datos



iAA es el número de niveles del índice

3

A

1

+

=

AA
i

, donde

A3- Índice primario, búsqueda basada en clave.
E
2- Condiciones de comparación
2.1 Selección simple
Tamaño del resultado
El resultado debe tener en media

)(rvA≤σ

tuplas.



rn
2

Más preci