Metodos de Optimizar en SQL
185
UNIVERSIDAD DE SANTIAGO DE CHILE FACULTAD DE CIENCIAS DEPARTAMENTO DE MATEMATICA Y CIENCIA DE LA COMPUTACION METODOS DE OPTIMIZACION DE CONSULTAS PARA EL LENGUAJE SQL. MARIO CISTERNA NEIRA SANTIAGO - CHILE 2002
Transcript of Metodos de Optimizar en SQL
-
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE CIENCIAS
DEPARTAMENTO DE MATEMATICA Y CIENCIA DE LA COMPUTACION
METODOS DE OPTIMIZACION DE CONSULTAS PARA EL LENGUAJE SQL.
MARIO CISTERNA NEIRA SANTIAGO - CHILE
2002
-
1
TABLA DE CONTENIDOS
DEFINICIN DEL PROBLEMA...........................................................................4
ESTRUCTURA DEL LIBRO. .................................................................................6
CAPTULO 1. MODELO DE DATOS RELACIONAL.....................................8 1.1. INTRODUCCIN. ................................................................................................8 1.2. IMPLEMENTACIONES RELACIONALES................................................................9 1.3. CONCEPTOS GENERALES. ................................................................................10
CAPTULO 2. LENGUAJES DE CONSULTA PARA EL MODELO RELACIONAL. ..........................................................................16
2.1. INTRODUCCIN. ..............................................................................................16 2.2. ALGEBRA RELACIONAL. ..................................................................................17 2.3. CLCULO RELACIONAL DE TUPLAS. ................................................................23 2.4. SQL COMO LENGUAJE DE CONSULTAS RELACIONALES. ..................................27
CAPTULO 3. SISTEMAS DE GESTIN DE BASES DE DATOS RELACIONALES. .....................................................................31
3.1. INTRODUCCIN. ..............................................................................................31 3.2. TRANSACCIONES, CONCURRENCIA Y RECUPERACIN......................................33 3.3. TIPOS DE SGBD..............................................................................................40
CAPTULO 4. INTRODUCCIN AL PROCESAMIENTO DE CONSULTAS, EL ENFOQUE DE SYSTEM R....................48
4.1. INTRODUCCIN. ..............................................................................................48 4.2. EL OPTIMIZADOR DE SYSTEM R. .....................................................................51
CAPTULO 5. OPTIMIZACIN DE CONSULTAS, FUNDAMENTO TERICO. ..................................................................................69
5.1. INTRODUCCIN. ..............................................................................................69 5.2. INFORMACIN DEL CATLOGO........................................................................70 5.3. MEDIDAS DE COSTO. .......................................................................................72 5.4. EVALUACIN DE EXPRESIONES. ......................................................................95 5.5. ORDENES DE JOIN. ........................................................................................107 5.6. ELECCIN DE LOS PLANES DE EVALUACIN. .................................................123
CAPTULO 6. EL OPTIMIZADOR DE CONSULTAS DE SYBASE ADAPTIVE SERVER ENTERPRISE, UN EJEMPLO PRCTICO...............................................................................128
6.1. INTRODUCCIN. ............................................................................................128 6.2. ANLISIS DE LA CONSULTA. .........................................................................129
-
2
6.3. SELECCIN DE NDICES. ................................................................................135 6.4. SELECCIN DE LOS ORDENES DE JOIN............................................................137 6.5. USO DE TABLAS TEMPORALES. ......................................................................147 6.6. SELECCIN DEL PLAN....................................................................................148 6.7. RESUMEN. .....................................................................................................152
RESUMEN Y CONCLUSIONES........................................................................154 RESUMEN.............................................................................................................154 CONCLUSIONES. ...................................................................................................157
BIBLIOGRAFA...................................................................................................160
APNDICES. 162
A. SINTAXIS DE SQL..................................................................162 A.1. DEFINICIONES DE DATOS EN SQL.................................................................162 A.2. MANIPULACIN DE DATOS EN SQL..............................................................167
B. INDICES B+..............................................................................178
C. MTODOS DE ALMACENAMIENTO DE DATOS...........181 C.1. DISCOS MAGNTICOS...................................................................................182
-
3
TABLA DE TABLAS TABLA 2-1 - OPERADORES DEL ALGEBRA RELACIONAL ........................................................17 TABLA 4-1 - FACTORES DE SELECCIN PARA CAMINOS DE ACCESO A RELACIONES SIMPLES.58 TABLA 4-2 - FRMULAS DE COSTO PARA CAMINOS DE ACCESO A RELACIONES SIMPLES........61 TABLA 5-1 - INFORMACIN DEL CATLOGO PARA RELACIONES SIMPLES. .............................71 TABLA 5-2 - INFORMACIN DEL CATLOGO PARA NDICES DE RELACIONES..........................72 TABLA 5-3 - REGLAS DE EQUIVALENCIA PARA EXPRESIONES RELACIONALES......................104 TABLA A-1 - TIPOS DE DATOS DE SQL................................................................................164
TABLA DE ALGORITMOS
ALGORITMO 5-1 - JOIN EN BUCLES ANIDADOS. ......................................................................83 ALGORITMO 5-2 - JOIN EN BUCLES ANIDADOS POR BLOQUES.................................................84 ALGORITMO 5-3 - JOIN POR MEZCLA. ....................................................................................86 ALGORITMO 5-4 - JOIN POR ASOCIACIN. ..............................................................................89 ALGORITMO 5-5 - JOIN ENCAUZADO......................................................................................99
TABLA DE FIGURAS FIGURA 2-1 - ESQUEMA DE RELACIONES DE EJEMPLO...........................................................18 FIGURA 4-1 - PASOS EN EL PROCESAMIENTO DE UNA CONSULTA SQL...................................50 FIGURA 5-1 - COMPORTAMIENTO DEL ALGORITMO DE SIMULACIN DE COCCIN ..............116 FIGURA 5-2 - EJEMPLO DEL PRINCIPIO DE SELECCIN PARA EL ALGORITMO GENTICO PARA LA
OPTIMIZACIN DE ORDENES DE JOIN ............................................................................120 FIGURA 5-3 - EJEMPLO DEL PRINCIPIO DE COMBINACIN PARA EL ALGORITMO GENTICO
PARA LA OPTIMIZACIN DE ORDENES DE JOIN..............................................................121 FIGURA 5-4 - UN PLAN DE EVALUACIN DE EJEMPLO ..........................................................123
-
4
Definicin del problema.
En Bases de datos relacionales el lenguaje de consultas SQL es lo ms
utilizado por el comn de los programadores y desarrolladores para obtener
informacin desde la Base de datos. La complejidad que pueden alcanzar algunas
consultas puede ser tal, que el diseo de una consulta puede tomar un tiempo
considerable, obteniendo no siempre una respuesta optima.
Dada una consulta, generalmente existen varias maneras de calcular la
respuesta. En SQL una consulta puede expresarse de distintas maneras, todas
ellas diferentes, como lo expresa C. Date en [Date98], cada una de las formas
sugiere una estrategia para encontrar la respuesta y por lo tanto algunas pueden
ser ms optimas que otras.
El problema que se plantea entonces es, el encontrar la manera ms
apropiada de resolver la consulta, sin que, el proceso de determinar este resultado
exceda un tiempo razonable y un gasto de recursos adicional.
Como respuesta a este problema, nace el concepto de optimizacin de
consultas. El objetivo principal de este proceso es, encontrar o bien la mejor
alternativa para solucionar la consulta, o de lo contrario, la alternativa que mejor
cumpla las caractersticas de eficiencia, entre las estudiadas, cuando no sea
posible estudiarlas todas.
Este proceso tiene que ser lo bastante rpido como para que sea
conveniente para el motor efectuar este clculo sin afectar el rendimiento en la
construccin del resultado de la consulta.
-
5
Uno de los primeros estudios relativo a optimizacin de consultas para SQL
se hizo sobre el prototipo de un motor de base de datos relacional desarrollado por
IBM llamado system R, en los laboratorios de San Jos (California) a mediados
de la dcada de 1970. Este estudio proporcionara las bases para la construccin
de la mayora de los optimizadores para motores de base de datos relacionales de
orden comercial en la actualidad.
Entre otras cosas, este estudio propone la descomposicin del
procesamiento de una consulta SQL en 4 fases: el anlisis sintctico (parsing), la
optimizacin, la generacin de cdigo y la ejecucin de la consulta.
Se entiende entonces como proceso de optimizacin de consultas al
conjunto de tcnicas, algoritmos y reglas que le permiten, al motor de base de
datos, elegir una alternativa entre varias con la cual pueda rescatar los datos de la
manera ms optima.
El objetivo principal de este trabajo es Investigar este proceso y develarlo,
con la finalidad de que deje de ser algo desconocido para quienes interactan con
Sistemas de Gestin de bases de datos relacionales.
La idea de este trabajo es que le sirva de apoyo tanto al diseador de base
de datos relacionales, como a los desarrolladores que ejecutan consultas,
quienes, al entender mas de cerca el proceso de optimizacin de consultas
puedan evitar los errores ms comunes, que a la larga llevan muchas veces al
fracaso en la construccin e implementacin de sistemas de Informacin sobre
bases de datos relacionales.
-
6
Estructura del libro.
El Captulo 1 introduce el modelo relacional de datos, el cual es la base
para el desarrollo de este trabajo, se presentar un marco de trabajo terico sobre
el cual desarrollar el problema.
El Captulo 2 trata sobre los distintos lenguajes para recuperacin de datos
que existen para el modelo relacional, otorgando un nfasis especial sobre el
lgebra relacional y el clculo relacional de tuplas, fundamentales para la
presentacin de SQL como lenguaje de consultas.
El procesamiento de una consulta SQL depender en gran medida de la
implemetacin relacional en la cual se ejecute, por lo tanto, el Captulo 3 presenta
la conceptualizacin sobre Sistemas de Gestin de base de datos relacionales
(SGBD), a modo de explicacin de cmo se logran implementaciones relacionales
del modelo, en este captulo se explicarn brevemente conceptos tales como
transacciones, concurrencia y repcuperacin de datos.
El Captulo 4 Introduce al tema del procesamiento de consultas, para tales
efectos se presenta el estudio del optimizador de consultas de System R. Este
SGBD se considera una de las primeras implementaciones relacionales y motivo
de investigacin tanto como fundamento y guia para la construccin de la mayora
de los optimizadores relacionales comerciales actuales. El estudio de este caso
introduce conceptos como medidas de costo, caminos de acceso y utilizacin de
heursticas dentro de un optimizador.
El Captulo 5 desarrolla el fundamento terico del libro, estudia en profundidad el
proceso de optimizacin de consultas SQL. Este captulo explica como los
optimizadores determinan sus medidas de costo y en que informacin se basan
-
7
para estos clculos; como se produce la evaluacin de expresiones y como
determinar los ordenes de Join.
Dado que este trabajo no tiene asociado un desarrollo prctico del tema, el
Captulo 6 presenta un ejemplo de cmo trabaja en la prctica un optimizador de
consultas para un SGBD comercial, para tales efectos se presenta el caso de
Sybase Adaptive Server Enterprise (ASE). Este captulo llevar al lector a
entender que existe una correspondencia entre lo presentado en el Captulo 4, lo
explicado en el Captulo 5, y como se logra esto en la prctica.
-
8
Captulo 1. Modelo de Datos Relacional
1.1. Introduccin.
El objetivo de todo modelo de datos es proveer conceptos y estructuras de
datos capaces de interpretar los aspectos relevantes que existen en una
determinada parcela del mundo real. Esto se logra mediante un conjunto bien
definido de estructuras, operadores y restricciones que actan sobre dichas
estructuras.
El Modelo Relacional corresponde a un enfoque cientfico y tecnolgico que
surgi entre la dcada de 1960 y la dcada de 1970. Su estrategia de abstraccin
se basa en hacer una representacin tabular de los objetos y sus asociaciones
entre ellos. Sin embargo, este enfoque tabular que se sustenta en la teora de las
relaciones matemticas no permite diferenciar entre los tipos de entidad y los tipos
de relacin, lo que constituye una prdida semntica significativa con respecto a
su antecesor, el modelo de Entidad-Relacin.
Por otra parte, la representacin tabular de la informacin y los mecanismos
utilizados para establecer vnculos entre las tablas que se representan de objetos
relacionados han contribuido enormemente a su masificacin, a tal punto que en la
actualidad, el Modelo Relacional es un estndar de hecho en los que se
construyen los SGBD1 comerciales.
Es importante notar que el modelo relacional es un modelo basado en el
papel y que no todas sus caractersticas son implementadas en los SGBD, como a
1 SGBD : Sistemas de Gestin de Bases de datos.
-
9
su vez muchas implementaciones tienen ms caractersticas que las que
contempla el modelo.
1.2. Implementaciones Relacionales.
Una implementacin del modelo relacional debe soportar todas las
facilidades prescritas por el modelo, sin embargo existen algunas caractersticas a
las cuales no hace referencia el modelo de datos relacional, dentro de estas se
incluyen operaciones aritmticas, funciones agregadas, actualizaciones explcitas,
modificaciones, eliminaciones, etc. Para esto el Modelo relacional incluye un
ncleo de funciones que deben ser incorporadas en un SGBD.
Sin embargo existe una distincin entre las implementaciones consideradas
relacionales y los que no lo son en su totalidad (Pseudo-Relacionales). Estas
ltimas se pueden clasificar como sigue:
Tabular : Un SGBD Tabular es una implementacin de una Base de datos relacional que soporta las estructuras de datos tabulares (tablas), pero no
los operadores de nivel de conjuntos.
Relacional Mnimo: Un SGBD Mnimamente relacional es una implementacin de bases de datos relacionales que soporta slo tablas, los
operadores de seleccin, proyeccin y el operador JOIN (pero no los otros
operadores relacionales).
Relacional Completo: Un SGBD Completamente relacional es una implementacin de bases de datos relacionales que soporta slo tablas y
todos los operadores del lgebra relacional.
-
10
Relacional : Un SGBD Relacional es una implementacin de Bases de datos relacionales que soporta todos los aspectos del modelo relacional
incluidos los dominios y las dos reglas generales de Integridad (que se
explicarn ms adelante, en el punto 1.3.12).
1.3. Conceptos generales.
1.3.1. Datos Atmicos
Todos los valores de datos en el modelo relacional son atmicos. Esto
implica que cada posicin de fila-columna en cada tabla siempre tiene slo un
dato, y nunca un conjunto de valores.
1.3.2. Tuplas
Una tupla de una relacin o de una tabla corresponde a una fila de aquella
tabla. Las tuplas estn comnmente desordenadas puesto que matemticamente
una relacin se define como un conjunto y no como una lista. No Existen tuplas
duplicadas en una relacin o tabla dado el hecho de que una relacin es un
conjunto y los conjuntos por definicin no permiten elementos duplicados. Un
corolario importante en este punto es que la llave primaria siempre existe dada la
condicin de unicidad de las tuplas, por lo tanto, como mnimo la combinacin de
todos los atributos de una tabla puede servir para la conformacin de la llave
primaria, sin embargo usualmente no es necesario incluir todos los atributos,
comnmente algunas combinaciones mnimas son suficientes.
1.3.3. Dominios.
Un dominio se define como un conjunto de valores del mismo tipo. Por
ejemplo el dominio que corresponde a la edad de una persona (en aos) se puede
-
11
definir como el conjunto de todos los valores de nmeros posibles de edades, por
ejemplo desde 0 hasta 120. Siempre y cuando dos atributos tomen sus valores del
mismo dominio estos pueden ser comparados aunque pertenezcan a distintas
tablas. Los dominios son especificados como parte de la definicin de los datos,
estos pueden ser simples o compuestos. Un dominio compuesto se define como el producto de alguna coleccin de dominios simples. Por ejemplo la fecha es producto de el da, el mes y el ao, donde el mes es el dominio simple de 1 a 12 y
as sucesivamente).
1.3.4. Atributos.
Un atributo de una relacin o de una tabla corresponde a una columna de la
tabla. Los atributos estn desordenados y se referencian por nombres y no por la
posicin que ocupan. Esto significa que no se puede, por ejemplo, hacer
referencia al tercer atributo de una relacin. Todos los valores de los atributos son
atmicos y una relacin que satisfaga esta condicin se llama relacin
normalizada. Un atributo extrae sus valores desde un dominio simple.
Formalmente, un atributo es una funcin que se define entre un Dominio y
un determinado tipo de Entidad de la base de datos. Dicha funcin asocia una
ocurrencia de Tipo de Entidad con un determinado elemento del dominio.
1.3.5. Esquema de Relacin.
Un esquema de relacin es el conjunto que identifica todas las propiedades
(Atributos) de un objeto. Se representa por el conjunto :
{ }nAAAAE ,......,, 321= donde niAi ,...1, = corresponde a un atributo y n el nmero de atributos de
inters del objeto.
-
12
1.3.6. Relacin
Formalmente, una relacin R es un conjunto de n-tuplas tal que una n-tupla
cualquiera x es:
( ){ }niiADomaEAaA iii ,.....1,),(,/, =
donde E es el esquema de la relacin.
Las propiedades fundamentales de una relacin son :
No hay tuplas repetidas.
Las tuplas no estn ordenadas.
Los atributos no estn ordenados.
Todos los valores que toman las propiedades son atmicos.
1.3.7. Grado de una relacin
El grado de una relacin es el numero de atributos en la relacin. Una
relacin de grado 1 (uno) es llamada unaria, una relacin de grado 2 es llamada
binaria, una relacin de grado n es llamada de grado n. Los Grados de una
relacin no cambian todo el tiempo, pero es posible que se agreguen nuevas
columnas y se creen nuevas relaciones.
-
13
1.3.8. Cardinalidades de una relacin.
La cardinalidad de una relacin en un determinado momento est definida
como el nmero de tuplas en la relacin. Esta puede cambiar en cualquier
momento.
1.3.9. Compatibilidad de dos relaciones.
Sean A y B dos relaciones con esquemas { }nAAAE 112111 ,.....,= y { }nAAAE 222212 ,.....,= respectivamente. Se dice que A y B son compatibles si y slo
si :
1. 21 ','!, EPPEPP tal que )'()( PDomPDom =
2. 12 ','!, EPPEPP tal que )'()( PDomPDom =
En la prctica, esto significa que ambas relaciones deben ser del mismo
grado n y que el i-esimo atributo de cada relacin se debe basar en el mismo
dominio.
1.3.10. Llave Primaria / Llave Candidata
La llave primaria de una relacin o tabla es de hecho un caso especial de
una construccin ms general llamada la llave candidata. Una llave candidata es un atributo que sirve como identificador nico para una determinada tabla. Una de
las llaves candidatas es elegida para ser la llave primaria, las restantes pasarn a
llamarse claves alternativas. De todos modos, comnmente slo hay una sola llave candidata. Las llaves primarias proporcionan un mecanismo de
direccionamiento nico a nivel de tuplas para el modelo relacional. Garantizan un
nico camino para llegar a una tupla individual y por lo tanto son fundamentales
para las operaciones sobre el modelo relacional.
-
14
Formalmente, una llave se define como:
Sea una relacin con esquema { }nAAAAE ,......,, 321= . Una Llave de la relacin es un atributo o un conjunto de atributos { }lji CCCK ,.....,= que cumple :
Unicidad: No existen dos tuplas de tales que para ellas, el conjunto de atributos que componen K tienen los mismos valores.
Minimalidad: Ninguno de los atributos que componen K puede ser eliminado sin afectar la unicidad.
1.3.11. Llaves externas
Una Llave externa se define como un atributo (o combinacin de atributos)
en una relacin cuyos valores se requieren para emparejar a los valores de la llave
primaria de otra relacin. La llave externa y su correspondiente llave primaria
deben ser definidas en el mismo dominio.
Una llave externa no tiene que ser componente de la llave primaria de la
relacin que la contiene. El emparejamiento entre una llave externa y una llave
primaria representa una referencia entre dos relaciones, ellas son el pegamento
que mantiene la base de datos unida.
1.3.12. Reglas de Integridad.
Existen bsicamente 2 reglas de integridad asociadas con el modelo
relacional, la Integridad de Entidad y la Integridad Referencial. Estas dos reglas
son generales, se aplican a toda base de datos relacional y tienen que ver con las
llaves primarias y externas respectivamente. Estas reglas se refieren a los estados
-
15
de la base de datos. Dado que no existe un acuerdo de como se deben evitar los
cambios de estado en la base de datos es que muchos SGBD detienen la
ejecucin de la tarea en curso cada vez que se incurre en una violacin a una de
estas reglas.
La regla de Integridad de Entidad norma sobre la imposibilidad de que un
atributo que componga la llave primaria de una relacin base acepte valores nulos
(NULL)2.
La regla de integridad referencial para el modelo relacional formula que si
una relacin R2 incluye una llave externa FK que empareja a una llave primaria
PK de alguna relacin R1, entonces cada valor de FK en R2 debe:
a) Ser igual al valor de PK en alguna tupla de R1
o
b) Ser totalmente Nula, esto es, cada atributo en FK debe ser nulo.
2 Un Valor nulo en el modelo relacional es un valor especial distinto de cero o blanco
(dependiendo del tipo de dato) que significa No aplicable o Desconocido. Para mayor detalle, ver la discusin sobre valores nulos en [McJones97].
-
16
Captulo 2. Lenguajes de consulta para el Modelo
Relacional.
2.1. Introduccin.
Un lenguaje de consulta es un lenguaje en el que el usuario solicita
informacin de la base de datos, Los lenguajes de consulta se pueden clasificar en
procedurales y no procedurales. Los lenguajes procedurales son aquellos en los
cuales el usuario instruye al sistema para que lleve a cabo una serie de
operaciones en la base de datos con el fin de calcular el resultado deseado. En
los lenguajes no procedurales, en cambio, el usuario describe la informacin
deseada sin dar un procedimiento concreto para obtener esta informacin.
Los lenguajes puros para la consulta de datos son 3. El lgebra relacional,
el cual es procedural y los clculos relacionales tanto de tuplas como de dominios,
los cuales son lenguajes no procedurales. Estos 3 lenguajes son rgidos y
formales, por lo tanto la mayor parte de los sistemas comerciales de bases de
datos relacionales ofrecen lenguajes de consulta mixtos, que adems de ser ricos
en sintaxis ofrecen adicionalmente sublenguajes de definicin de datos,
administracin de seguridad y otras caractersticas.
Se estudiarn brevemente dos de los tres lenguajes puros de consultas de base
de datos, con el fin de presentar una base terica para introducir SQL. Se excluir
el clculo relacional de dominios dado que es una generalizacin del clculo
relacional de tuplas y queda fuera del alcance de este trabajo. Para un estudio
ms acabado del clculo relacional de dominios se recomienda leer
[Silbercshatz93].
-
17
2.2. Algebra relacional.
El Algebra relacional es un lenguaje de consulta procedural. Consta de un
conjunto de operaciones que toman como entrada una o dos relaciones y
producen como resultado una nueva relacin, por lo tanto, es posible anidar y
combinar operadores. Hay ocho operadores en el lgebra relacional que
construyen relaciones y manipulan datos, estos son:
1. Seleccin 2. Proyeccin 3. Producto
4. Unin 5. Interseccin 6. Diferencia
7. JOIN 8. Divisin Tabla 2-1 - Operadores del Algebra relacional
Las operaciones de proyeccin, producto, unin, diferencia, y seleccin son
llamadas primitivas, puesto que las otras tres se pueden definir en trminos de
estas.
Se hace necesario en este punto incluir un modelo de datos de ejemplo en
el cual trabajar para generar ejemplos de comandos y operadores. Para este
efecto se incluye un modelo bsico de administracin de RadioTaxis. El Grfico
que se presenta a continuacin representa el Modelo conceptual (Modelo Lgico)
o Diagrama de Entidad-Relacin:
-
18
por genera un
realiza
los hace un
manejalo manejaposee es de un
MovilPatenteMarcaModeloAo
ViajeHora DesdeHora HastaOrigenDestinoTarifaMetraje
DueoRutNombreTelfonoDireccinVigencia
ChoferRutNombreTelfonoDireccinFecha_licencia_desdeFecha_licencia_hastaVigencia
ValeCorrelativoHora desdeHora HastaMetraje totalTarifa Total
Conceptual Data ModelProject : Control de RadioTaxisModel : RadioTaxAuthor : Mario Cisterna Version 28/12/98
Figura 2-1 - Esquema de Relaciones de Ejemplo
Los Esquemas de relaciones que se pueden construir a partir de este
modelo son los siguientes:
Dueo = {rut, nombre, telfono, direccin, vigencia}
Chofer = {rut, nombre, telfono, direccin, fecha_licencia_desde, fecha_licencia_hasta, vigencia}
Vale = {correlativo, hora_desde, hora_hasta, metraje_total, tarifa_total}
Mvil = {patente, rut_dueo, rut_chofer, marca, modelo, ao}
Viaje = {correlativo_vale, patente_movil, Hora_Desde, hora_hasta, origen, destino, tarifa, metraje}
2.2.1. Seleccin.
El operador de seleccin opta por tuplas que satisfagan cierto predicado, se
utiliza la letra griega sigma minscula () para sealar la seleccin. El predicado
-
19
aparece como subndice de . La Relacin que constituye el argumento se da
entre parntesis despus de la .
Ejemplos :
)('' DueoSvigencia=
)('8483' MovilHLpatente =
2.2.2. Proyeccin.
La operacin de proyeccin permite quitar ciertos atributos de la relacin,
esta operacin es unaria, copiando su relacin base dada como argumento y
quitando ciertas columnas, La proyeccin se seala con la letra griega pi
mayscula (). Como subndice de se coloca una lista de todos los atributos que
se desea aparezcan en el resultado. La relacin argumento se escribe despus de
entre parntesis.
Ejemplos :
)(, Dueodireccionnombre
)(, Chofervigenciarut
2.2.3. Producto.
En lgebra relacional el producto de dos relaciones A y B es:
A Veces B o A X B
-
20
Produce el conjunto de todas las tuplas t tales que t es el encadenamiento de una tupla a perteneciente a A y de una b que pertenece a B. se utiliza el smbolo X
para representar el producto.
Ejemplos:
ChoferMovil
MovilDueo
2.2.4. Unin.
En lgebra relacional la unin de dos relaciones compatibles 3A y B es:
A UNION B o A B
Produce el conjunto de todas las tuplas que pertenecen ya sea a A o a B o a
Ambas. Al igual que en teora de conjuntos el smbolo representa aqu la unin
de dos relaciones.
Ejemplo :
)()( ,, ChoferDueo vigenciarutvigenciarut Devuelve todos los Dueos y los Choferes.
2.2.5. Interseccin.
En lgebra relacional la interseccin de dos relaciones compatibles A y B
3 Relaciones Compatibles : En el lgebra relacional la compatibilidad se aplica a las operaciones de Unin, Interseccin y Diferencia. Cada operacin requiere dos relaciones que deben ser compatibles, esto significa que deben ser del mismo grado, n, y el i-simo atributo de cada una (i= 1, 2n) se debe basar en el mismo dominio.
-
21
A INTERSECCION B o A B
Produce el conjunto de todas las tuplas pertenecientes a A y B. Al igual que en
teora de conjuntos el smbolo representa aqu la interseccin entre dos
relaciones.
Ejemplo:
)()( ,, ChoferDueo vigenciarutvigenciarut Devuelve todos los dueos que tambin son choferes
2.2.6. Diferencia
En lgebra relacional la diferencia entre dos relaciones compatibles A y B
A MENOS B o A B
Produce el conjunto de todas las tuplas t que pertenecen a A y no pertenecen a B.
Ejemplo:
)()( ,, ChoferDueo vigenciarutvigenciarut Devuelve todos los dueos que NO son choferes
2.2.7. Join o Reunin.
En lgebra relacional el JOIN entre el atributo X de la relacin A con el atributo Y de la relacin B produce el conjunto de todas las tuplas t tal que t es el encadenamiento de una tupla a perteneciente a A y una tupla b perteneciente a B que cumplen con el predicado A.X comp B.Y es verdadero (siendo comp un
-
22
operador relacional y los atributos A.X y B.Y pertenecientes al mismo dominio). Si
el operador relacional comp es = entonces el conjunto resultante es un EQUI-
JOIN. Si se quita uno de stos (usando una proyeccin) entonces el resultado es
un JOIN-NATURAL.
Ejemplo :
)(_.. MovilDueodueorutMovilrutDueo =
2.2.8. Divisin
En lgebra relacional el operador de divisin divide la relacin A con grado m + n por la relacin B entregando como resultado una relacin con grado m. El atributo m + i de A y el atributo i de B deben estar definidos dentro del mismo
dominio. As el resultado de
A DIVIDIDO POR B o A / B
produce la relacin C con un slo atributo X, tal que cada valor de x de C.X aparece como un valor de A.X, y el par de valores (x, y) aparece en A para todos los valores y que aparecen en B.
Ejemplo:
)(/ )()( 1999/01/01___, ChoferMovil hastalicenciafecharutchoferrutpatente
-
23
2.3. Clculo relacional de tuplas.
El clculo relacional de tuplas describe la informacin deseada sin dar un
procedimiento especfico para obtenerla. Las consultas en el clculo relacional de
tuplas se expresan como
{ t | P(t)},
es decir, son el conjunto de tuplas t tales que se cumple el predicado P para cada
t. Siguiendo la misma notacin, se utiliza t[A] para el valor de la tupla t en el
atributo A.
}''][|{ SvigenciatDueott =
}'8483'][|{ = HLpatentetMoviltt
Si slo se desea obtener un atributo de la tupla, se utiliza el constructor
Existe de la lgica matemtica. As, si lo que se desea es el Nombre de los
dueos de taxis que estn vigentes:
)}''][][][(|{ SvigenciasNombresNombretDueost ==
"Conjunto de todas las tuplas t tales que existe una tupla s en la relacin
Dueo para la que los valores de t y de s son iguales en el atributo Nombre y el
valor de s para el atributo vigencia = S ". La variable de tupla t se define slo en
el atributo Nombre, puesto que ste es el nico atributo para el que se especifica
una condicin para t. As, el resultado es una relacin sobre (Nombre).
-
24
Si lo que se desea es obtener las tarifas de todos los viajes que ha
efectuado todos los mviles de marca chevrolet, la consulta requiere de dos
clusulas Existe conectadas por el operador de conjuncin lgica y.
))}""][][][(
][][(|{
chevroletmarcaupatenteupatentesMovilu
tarifastarifatViajest
==
=
Que se lee como el conjunto de todas las tuplas(tarifa) correspondientes a los
viajes que han hecho todos los mviles de marca chevrolet.
Considrese ahora la consulta obtener todos los RUT de los dueos de
mviles, cuyos mviles no hayan efectuado nunca un viaje:
]))}[][(
][][(|{
patenteupatentesViajeu
RutsruttMovilst
=
=
que ocupa la clusula Existe para exigir que el dueo posea un mvil y la
clusula no existe para eliminar a aquellos mviles que tengan viajes realizados.
La consulta que se presenta a continuacin utiliza la implicacin, la frmula P
implica Q significa que si P es verdad entonces Q debe ser verdad, se introduce
el constructor para todo. Se desea Selecciona todos los autos a cuyos choferes
les caduca la licencia el 01/01/1999.
}]))[]_[][][(
"1999/01/01"]__[(|{
rutuchoferrutspatentespatentetMovils
hastalicenciafechauChoferut
==
-
25
2.3.1. Definicin Formal.
Una expresin del clculo relacional de tuplas es de la forma:
{t|P(t)} donde P es una frmula. En una frmula pueden aparecer varias variables
de tuplas. Se dice que una variable de tupla es una variable libre a menos que
este cuantificada por un o por un que entonces se dice variable ligada.
Una frmula en el clculo relacional de tuplas se compone de tomos. Un
tomo tiene una de las siguientes formas:
1. s r, donde s es una variable de tupla y r es una relacin. No se permite la
operacin .
2. s[x] u[y], donde s y u son variables de tuplas, x e y son atributos sobre los
que estn definidos s y u respectivamente, y es un operador de comparacin
(=). Se requiere que los atributos x e y tengan dominios cuyos
miembros puedan compararse por medio de .
3. s[x] c, donde s es una variable de tupla, x es una atributo sobre el que s esta
definida, es un operador de comparacin, y c es una constante en el dominio
del atributo x.
Ahora bien, Las frmulas se construyen a partir de tomos usando las
siguientes reglas:
1. Un tomo es una frmula.
2. Si P1 es una frmula, entonces tambin lo son P1 y (P1).
-
26
3. Si P1 y P2 son frmulas, entonces tambin lo son P1P2, P1P2 y P1P2.
4. Si P1(s) es una frmula que contiene una variable de tupla libre s y r es una
relacin, entonces:
s r (P1(s)) y s r (P1(s)) tambin son frmulas.
2.3.2. Seguridad de expresiones.
Una expresin del clculo relacional de tuplas puede generar relaciones
infinitas. Si por ejemplo se utiliza la construccin {t | (t Dueo)} hay infinitas
tuplas de personas que no son dueos de algn mvil, de hecho la mayora de
estas tuplas ni siquiera pertenecen a la base de datos.
Para ayudar a definir las ligaduras del clculo relacional de tuplas se
introduce el concepto de dominio de frmulas. De forma intuitiva, el dominio de la
frmula P (dom(p)) es el conjunto de todos los valores a los que P hace referencia.
Esto incluye a todos los valores mencionados en P como todos los valores que
aparezcan en las relaciones referenciadas por P.
Se dice que una expresin {t | P(t)} es segura si todos los valores que
aparecen en el resultado son valores del dominio de P.
2.3.3. Potencia expresiva de los lenguajes.
El clculo relacional de tuplas restringido a expresiones seguras es
equivalente en potencia expresiva al lgebra relacional. Por lo tanto, para cada
expresin del lgebra relacional hay una expresin equivalente en el clculo
relacional de tuplas y viceversa. La demostracin de este hecho queda fuera de
los alcances de este trabajo, una prueba formal de la equivalencia entre el clculo
-
27
relacional de tuplas y el lgebra relacional propuesta por E.F. Codd se puede
encontrar en [Codd71].
2.4. SQL como lenguaje de consultas relacionales.
2.4.1. Introduccin.
Los lenguajes formales presentados en las secciones 2.2 y 2.3
proporcionan una notacin concisa para la representacin de consultas. Sin
embargo, los sistemas de base de datos necesitan un lenguaje de consultas ms
cmodo para el usuario. Aunque SQL se considere un lenguaje de consultas,
contiene muchas otras capacidades que incluyen caractersticas para definir
estructuras de datos, modificacin de datos y la especificacin de restricciones de
integridad.
SQL se ha establecido como el lenguaje estndar de base de datos
relacionales. Hay numerosas versiones de SQL. La versin original se desarrollo
en el laboratorio de investigacin de San Jose, California (San Jose Research
Center) de IBM, este lenguaje originalmente denominado Sequel, se implement
como parte del proyecto System R, a principios de 1970 [McJones97]. Desde
entonces ha evolucionado a lo que ahora se conoce como SQL (Structured Query
Language, o lenguaje estructurado de consultas).
En 1986, ANSI (American National Standards Institute, Instituto Nacional
Americano de Normalizacin) e ISO (International Standards Organization,
Organizacin Internacional de Normalizacin) Publicaron una norma de SQL
denominada SQL-86. En 1987 IBM public su propia norma de SQL denominada
SAA-SQL(System Application Architecture Database Interfaz, Interfaz de base de
datos para arquitecturas de aplicacin de sistemas). En 1989 se public una
-
28
norma extendida para SQL (SQL-89) y actualmente los SGBD son compatibles al
menos con esta norma. La norma actual de SQL de ANSI/ISO es la SQL-92. Se
debe tener en cuenta que algunas implementaciones de SQL pueden ser
compatibles slo con SQL-89, no sindolo con SQL-92.
SQL proporciona dos tipos de lenguajes diferentes: uno para especificar el
esquema relacional y el otro para expresar las consultas y actualizaciones de la
base de datos.
2.4.2. Lenguaje de definicin de datos (DDL Data Definition
Language)
Un esquema de bases de datos se representa mediante un sublenguaje
especial llamado lenguaje de definicin de datos. El resultado de la compilacin de
estas instrucciones es un conjunto de tablas, relaciones y reglas cuyas
definiciones quedan almacenadas en un archivo (tabla u otro medio de
almacenamiento) que contiene metadatos, esto es, datos acerca de datos. Este
archivo comnmente llamado diccionario de datos (o catalogo del sistema) es el
que se consulta toda vez que se quiere leer, modificar o eliminar los datos de la
base de datos.
-
29
2.4.3. Lenguaje de manipulacin de datos (DML Data Manipulation
Language)
Un D.M.L. es un sublenguaje de consulta y manipulacin de datos.
Se entender por manipulacin de datos la :
Recuperacin de Informacin.
Insercin de nueva Informacin.
Eliminacin (Borrado) de informacin existente.
Modificacin de Informacin Almacenada.
2.4.4. Otras caractersticas de SQL.
Adems de los dos tipos de sublenguajes mencionados anteriormente, SQL
puede ser utilizado para otras caractersticas propias que no poseen los lenguajes
formales de consultas, estas son:
Definicin de vistas. El DDL de SQL incluye instrucciones para la definicin de vistas.
Autorizacin. El DDL de SQL incluye instrucciones para la especificacin de los derechos de acceso a los objetos de la base de
datos.
Integridad. El DDL de SQL tambin incluye un conjunto de sentencias para la especificacin de restricciones de integridad.
Control de transacciones. SQL incluye ordenes para la especificacin de los estados de una transaccin, algunas implementaciones permiten
-
30
adems el bloqueo explicito de objetos de datos con el fin de manejar
control de concurrencia.
Para los efectos de este trabajo se anexa en el apndice A una breve
descripcin de los sublenguajes de Definicin y manipulacin de datos.
-
31
Captulo 3. Sistemas de Gestin de Bases de datos
Relacionales.
3.1. Introduccin.
Un Sistema de Gestin de Bases de datos (SGBD) consiste en una
coleccin de datos interrelacionados y una coleccin de programas para acceder a
esos datos. El objetivo principal de un SGBD es proporcionar un entorno que sea
tanto conveniente como eficiente para las personas que lo ocupan en el
almacenamiento y recuperacin de la informacin.
Los sistemas de bases de datos se disean para almacenar grandes
volmenes de informacin, la gestin de los datos implica entonces la definicin
de estructuras para el almacenamiento de la informacin y la provisin de
mecanismos para la manipulacin de estos. Adems deben proporcionar
mecanismos de seguridad de los datos que protejan al sistema frente a cadas o a
intentos de acceso de personas no autorizadas. Si los datos estn compartidos
por varios usuarios, el sistema debe asegurar la consistencia de los datos evitando
posibles resultados anmalos.
Un propsito principal de un sistema de bases de datos es proporcionar a
los usuarios una visin abstracta de los datos. Esto se logra mediante la definicin
de 3 niveles de abstraccin que pueden ser observados: el nivel fsico, el nivel
lgico y el nivel de vistas.
El nivel fsico es el nivel ms bajo de abstraccin, es el que describe como
se almacenan los datos, a su vez, el nivel lgico describe que datos se
almacenan realmente en la base de datos y que relaciones existen entre estos
-
32
datos. El nivel ms alto de abstraccin de datos es el nivel de vistas, el cual slo
presenta una determinada porcin de la base de datos, dependiendo del tipo de
usuario que la consulta, as, el sistema puede proporcionar muchas vistas para la
base de datos.
Una base de datos sufre constantes cambios en el contenido de la
informacin que contiene en el transcurso del tiempo. La coleccin de datos
almacenada en un momento particular se denomina ejemplar de la base de datos.
El diseo completo de la base de datos se llama esquema de la base de datos.
La capacidad de modificar la definicin del esquema en un nivel sin que
afecte a una definicin de esquema en el nivel inmediatamente superior se
denomina independencia de datos. Existen 2 niveles de independencia de datos:
La independencia fsica de datos y la independencia lgica.
La Independencia fsica de los datos se describe como la capacidad de
modificar el nivel fsico de la base de datos sin tener que rescribir los programas
de aplicacin. En tanto la independencia lgica se define como la capacidad de
modificar el esquema lgico sin causar que los programas de aplicacin tengan
que rescribirse.
Un esquema de base de datos se especifica mediante un conjunto de
definiciones expresadas en un DDL (Lenguaje de definicin de datos). El resultado
de esta definicin es un conjunto de tablas y relaciones que se almacenan en una
tabla (o un conjunto de tablas) especial que se identifica como el diccionario de
datos o el catlogo de la base de datos.
Una transaccin de base de datos se define como coleccin de operaciones
que se lleva a cabo como una funcin lgica simple en una aplicacin de base de
datos. Cada transaccin es una unidad de atomicidad y consistencia. La
-
33
atomicidad aqu se entiende como la capacidad de que muchas instrucciones se
entiendan en ciertos casos como una sola, la consistencia se refiere a la
capacidad de respetar las restricciones de consistencia de datos que posee la
base de datos antes y despus de ejecutar una transaccin. El gestor de
transacciones es el responsable de asegurar que la base de datos permanezca en
un estado consistente a pesar de los fallos del sistema. El gestor de transacciones
tambin asegura que la ejecucin de transacciones concurrentes ocurran sin
conflictos. El gestor de almacenamiento de la base de datos es un programa (o
modulo) que proporciona la interfaz entre los datos de bajo nivel almacenados en
la base de datos y los programas de aplicacin y las consultas enviadas al
sistema. El gestor de almacenamiento es el responsable de la interaccin con los
datos almacenados en disco.
3.2. Transacciones, concurrencia y recuperacin.
3.2.1. Transacciones.
Una transaccin es una unidad de la ejecucin de un programa que accede
y posiblemente actualiza varios elementos de datos. Se delimita dependiendo del
lenguaje por las sentencias inicio transaccin y fin transaccin y se compone de
todas las instrucciones que se encuentran entre estos dos delimitadores.
Para asegurar la consistencia de los datos se necesita que el sistema de
base de datos tengan las propiedades llamadas ACID: (Atomicity, Consistency,
Isolation, Durability - Atomicidad, Consistencia, Aislamiento, Durabilidad
[Silberschatz97].
La atomicidad asegura que o bien todos los efectos de la transaccin se
reflejan en la base de datos, o bien ninguno de ellos; un fallo no puede dejar a la
base de datos en un estado en el cual una transaccin se haya ejecutado
-
34
parcialmente. La consistencia asegura que si la base de datos es consistente
inicialmente, la ejecucin de la transaccin deja la base de datos en un estado
consistente. El aislamiento asegura que en la ejecucin concurrente de
transacciones, estas estn aisladas unas de otras, de tal manera que cada una
tiene la impresin de que ninguna otra transaccin se ejecuta concurrentemente
con ella. La durabilidad asegura que una vez que la transaccin se ha
comprometido, las actualizaciones hechas por la transaccin no se pierden,
incluso si hay un fallo en el sistema.
Una transaccin que termina con xito se dice que est comprometida
(commited), una transaccin que haya sido comprometida llevar a la base de
datos a un nuevo estado consistente que debe permanecer incluso si hay un fallo
en el sistema. En cualquier momento una transaccin slo puede estar en uno de
los siguientes estados.
Activa (Active): el estado inicial; la transaccin permanece en este estado durante su ejecucin.
Parcialmente comprometida (Uncommited): Despus de ejecutarse la ultima transaccin.
Fallida (Failed): tras descubrir que no se puede continuar la ejecucin normal.
Abortada (Rolled Back): despus de haber retrocedido la transaccin y restablecido la base de datos a su estado anterior al comienzo de la
transaccin.
Comprometida (Commited): tras completarse con xito.
Cuando varias transacciones se ejecutan concurrentemente, existe la
posibilidad de que se pierda la consistencia de datos. Se hace necesario por lo
tanto un sistema que controle la interaccin entre las transacciones concurrentes.
Puesto que una transaccin por definicin conserva la consistencia, una ejecucin
-
35
lineal de transacciones la garantiza tambin. Un sistema que asegure esta
propiedad se dice que asegura la secuencialidad.
3.2.2. Concurrencia.
Existen varios esquemas de control de concurrencia que aseguran la
secuencialidad, todos estos esquemas o bien retrasan una operacin o bien
abortan la transaccin que ha realizado la operacin. Los ms conocidos son los
protocolos de bloqueo, el esquema de ordenacin por marcas temporales, las
tcnicas de validacin, el esquema de granularidad mltiple y los esquemas
multiversin.
Un protocolo de bloqueo es un conjunto de reglas que indican el momento
en que una transaccin puede bloquear o desbloquear un objeto de la base de
datos. El protocolo de bloqueo de dos fases permite que una transaccin bloquee
un objeto slo despus de que haya desbloqueado otro objeto distinto, este
mtodo asegura la secuencialidad.
El esquema de ordenacin por marcas temporales asegura la
secuencialidad seleccionando previamente un orden en todo par de transacciones.
Existen 2 formas de implementar este esquema, uno es por medio de valores
timestamp (dependientes del reloj del sistema) y por medio de un contador lgico
que se incrementa cada vez que asigna una nueva marca temporal. Este
protocolo asegura la secuencialidad en cuanto a conflictos y la ausencia de
interbloqueos, si una de las transacciones viola la norma la transaccin se retrasa
y se le asigna una nueva marca temporal. Por ejemplo, una operacin leer se
puede retrasar porque todava no se ha escrito el valor apropiado o incluso
rechazar si ha sobrescrito el valor que supuestamente se iba a leer.
-
36
Un esquema de validacin es un mtodo de control de concurrencia
adecuado para transacciones de slo lectura y en las cuales la tasa de conflictos
es baja. Se basa en dividir una transaccin en 3 etapas (lectura, validacin y
escritura) y trabajar con el esquema de marcas temporales sobre la etapa de
validacin. De esta manera se quita una sobrecarga en la etapa de lectura, en la
cual no se necesita un esquema de control de concurrencia dado que toda lectura
lleva a la base de datos al mismo estado de consistencia.
Una manera distinta manejar la concurrencia es por medio de la
granularidad, este concepto permite agrupar varios elementos de datos y definirlos
como un todo para efectos de sincronizacin. Se define como una jerarqua de
distintos niveles, donde el nivel superior puede representar toda la base de datos,
se esquematiza como estructura de rbol donde los nodos hijos de un nodo
interno representan las dependencias de datos asociadas. Se utilizan los tipos de
bloqueos Compartidos y Exclusivos ms un nuevo tipo de bloqueo llamado el
bloqueo intencional, el cual indica que existen nodos descendientes que tienen
bloqueos compartidos o exclusivos.
El esquema multiversin se basa en la creacin de nuevas versiones de los
elementos de datos cada vez que una transaccin vaya a escribir dicho elemento.
Cuando se va a realizar una escritura el sistema elige una de las versiones para
que se lea. El esquema de control de versiones garantiza que la versin que se va
a leer se elige de forma que asegure la secuencialidad por medio de marcas
temporales. En este esquema una operacin de lectura tiene xito siempre, sin
embargo, una operacin de escritura puede provocar el retroceso de una
transaccin.
Un sistema est en estado de interbloqueo si existe un conjunto de
transacciones tal que toda transaccin del conjunto est esperando a otra
transaccin del conjunto. En tal situacin, ninguna de las transacciones puede
-
37
progresar. Existen 2 mtodos para tratar los interbloqueos y ambos provocan un
retroceso de las transacciones, la diferencia radica en que uno es preventivo y otro
curativo. El protocolo de prevencin de interbloqueos asegura que el sistema
nunca llegar a un estado de interbloqueos mientras que el mtodo de deteccin y
recuperacin de interbloqueos permite que el sistema llegue a un estado de
interbloqueos para luego tratar de recuperarse. La prevencin se usa normalmente
cuando la probabilidad de que el sistema llegue a un estado de interbloqueo es
relativamente alta, de lo contrario lo ms conveniente es usar la deteccin y
recuperacin.
3.2.3. Recuperacin.
Los fallos que ocurren en un computador pueden darse por diferentes
motivos (fallos de disco, cortes de energa o fallos en el software). En cada uno de
estos casos puede perderse informacin concerniente a la base de datos. Existen
varios tipos de fallas, a considerar:
Fallo en la transaccin, que a su vez se dividen en errores lgicos y errores del
sistema. Un error lgico ocurre cuando una transaccin no puede continuar con
su ejecucin normal a causa de una condicin interna como lo es un
desbordamiento o un exceso de recursos. Un error del sistema ocurre cuando
el sistema se encuentra en un estado no deseado como en el caso de los
interbloqueos.
Cada del sistema, provocado ya sea por el hardware, el sistema operativo o
por el software de base de datos. Comnmente causa la prdida del contenido
de la memoria primaria y aborta el procesamiento de una transaccin.
-
38
Fallo de disco, para el cual slo sirve la recuperacin por medio de copias
existentes en medios de almacenamiento secundario como cintas magnticas.
La forma ms aceptada de lograr un tipo de almacenamiento lo ms estable
posible es replicando la informacin en varios medios de almacenamiento no
voltil, con modos de fallos independientes. Los sistemas RAID (disposicin
redundante de discos independientes) garantizan que el fallo de un slo disco no
conduzca a la perdida de datos. Sin embargo los sistemas RAID, no pueden
proteger al sistema de una prdida de datos en el caso de una catstrofe
geogrfica, para tales efectos muchos sistemas de almacenamiento guardan
copias de seguridad en cintas en otros lugares, no obstante, como las cintas no
pueden ser trasladadas continuamente, los ltimos cambios realizados luego del
traslado de cintas no se pueden volver a recuperar en el caso de tales desastres.
Los sistemas ms seguros guardan copias de cada bloque de almacenamiento en
otra disposicin geogrfica, datos que se transmiten por medios de redes de
computadores al sistema de respaldo remoto.
El estado de un sistema de base de datos puede no volver a ser consistente
en caso de que ocurran fallos, para preservar la consistencia es necesario que
cada transaccin sea atmica. Garantizar la propiedad de atomicidad es
responsabilidad del esquema de recuperacin.
Existen bsicamente 2 esquemas que garantizan la atomicidad.
Basados en el registro histrico4. Todas las modificaciones se graban en el
registro histrico, el cual debe estar guardado en almacenamiento estable. En el
esquema de modificacin diferida, durante la ejecucin de una transaccin, se
difieren todas las operaciones de escritura hasta que la transaccin se
4 Comnmente llamado log de transacciones.
-
39
compromete parcialmente, momento en el cual se utiliza la informacin del registro
histrico asociado con la transaccin para ejecutar las escrituras diferidas. Con la
tcnica de modificacin inmediata todas las modificaciones se aplican
directamente en la base de datos. Si ocurre una cada se utiliza la informacin del
registro histrico para llevar a la base de datos a un estado estable previo.
Paginacin en la sombra. Durante la vida de una transaccin se mantienen
2 tablas de pginas: la tabla actual de pginas y la tabla de pginas sombra.
Ambas tablas son idnticas al principio de la transaccin, sin embargo, la tabla
actual de pginas puede ir cambiando luego de cada operacin escribir. Todas las
operaciones de lectura y escritura utilizan la tabla de pginas actual, cuando una
transaccin se compromete parcialmente se desecha la tabla de pginas sombra y
la tabla actual se convierte en la nueva tabla de pginas. Si la transaccin fracasa,
simplemente se desecha la tabla actual de pginas.
El procesamiento de transacciones se basa en un modelo de
almacenamiento en el cual la memoria principal contiene una memoria intermedia
para el registro histrico, una memoria intermedia para la base de datos y una
memoria intermedia para el sistema. Una implementacin eficiente de un
esquema de recuperacin de datos requiere que sea mnimo el nmero de
escrituras de la base de datos y que sea realizado en almacenamiento estable.
Los registros del registro histrico pueden guardarse inicialmente en la memoria
intermedia del registro histrico pero deben ser llevados a almacenamiento estable
bajo dos situaciones:
a) deben escribirse en almacenamiento estable todos los registros del registro
histrico que referencien a la transaccin Ti antes de grabar el registro que
indique que la transaccin Ti ha sido comprometida
-
40
b) deben escribirse en almacenamiento estable todos los registros del registro
histrico pertenecientes a los datos de un bloque antes de que ese bloque de
datos se escriba desde la memoria intermedia a la base de datos.
3.3. Tipos de SGBD.
La arquitectura de un sistema de base de datos est influenciada por el
sistema informtico que soporta la instalacin del SGBD, lo que reflejar muchas
de las caractersticas propias del sistema subyacente en el SGBD.
La redes de computadores permiten separar tareas en un esquema de
clientes y servidores, el procesamiento paralelo dentro del computador permite
acelerar algunas de las tareas de la base de datos as como la posibilidad de
ejecutar ms transacciones por segundo. Las consultas se pueden paralelizar
permitiendo as que una consulta se pueda ejecutar por ms de un procesador al
mismo tiempo, esta caracterstica ha llevado al estudio de las bases de datos
paralelas.
La distribucin de datos a travs de distintos departamentos de una
organizacin permite que ellos residan donde han sido generados (y donde se
entiende que son ms requeridos); la idea de mantener una copia de estos datos
en otros lugares permite que puedan seguir las operaciones sobre los datos an si
alguno de estos sitios sufre algn desastre. El estudio de este tipo de
descentralizacin de los datos lleva al desarrollo de los sistemas de base de datos
distribuidos.
3.3.1. SGBD centralizados.
-
41
Un sistema de base de datos centralizado es aquel que se ejecuta en un
nico sistema computacional sin tener, para tal efecto, que interactuar con otros
computadores. El rango de estos sistemas comprende desde los sistemas de
bases de datos monousuario ejecutndose en computadores personales hasta los
sistemas de bases de datos ejecutndose en sistemas de alto rendimiento.
Normalmente los sistemas de base de datos monousuarios no suelen
proporcionar muchas de las facilidades que ofrecen los sistemas multiusuario, en
particular no tienen control de concurrencia y tienen precarios o inexistentes
sistemas de recuperacin.
Dado que las maquinas en las cuales se utilizan los sistemas monousuarios
son comnmente computadores de propsito general, la arquitectura de estas
maquinas es siempre parecida(de 1 a 2 procesadores que comparten la memoria
principal) por tanto los sistemas de base de datos que se ejecutan sobre estas
maquinas no intentan dividir una consulta simple entre los distintos procesadores,
sino que ejecutan cada consulta en un nico procesador posibilitando as la
concurrencia de varias consultas. Este tipo de sistemas dan la sensacin de una
mayor productividad (puesto que pueden ejecutar un mayor nmero de
transacciones por segundo) a pesar de que cada transaccin individualmente no
se ejecute ms rpido. Por el contrario las mquinas paralelas tienen un gran
nmero de procesadores y los sistemas de base de datos que ah se ejecutan
siempre tendern a paralelizar las tareas simples (consultas) que solicitan los
usuarios.
3.3.2. SGBD Cliente-Servidor.
Con el crecimiento de los computadores personales (PC) y de las redes de
rea local (LAN), se han ido desplazando hacia el lado del cliente la funcionalidad
de la parte visible al usuario de la base de datos (interfaces de formularios, gestin
-
42
de informes, etc.) de modo que los sistemas servidores provean la parte
subyacente que tiene que ver con el acceso a las estructuras de datos, evaluacin
y procesamiento de consultas, control de concurrencia y recuperacin. Los
sistemas servidores pueden dividirse en 2 tipos: los servidores transaccionales
(que sirven para agrupar la lgica del negocio en un servicio aparte, proveen una
interfaz a travs de la cual los clientes pueden enviar peticiones como lo son
ODBC5 o RPC6) y los servidores de datos(los cuales envan datos a ms bajo nivel
y que descansan en la capacidad de procesamiento de datos de las maquinas
clientes).
Existen 2 arquitecturas dominantes en la construccin de motores de base
de datos cliente-servidor: los motores multiprocesos y los motores multihilos.
3.3.2.1. Motores de base de datos multiprocesos (Multi-process database engines).
Algunos motores de base de datos confan en mltiples aplicaciones para
realizar su trabajo. En este tipo de arquitectura, cada vez que un usuario se
conecta a la base de datos, sta inicia una nueva instancia de la aplicacin de
base de datos. Con el fin de coordinar a muchos usuarios que accesan los mismos
conjuntos de datos estos ejecutables trabajan con un coordinador global de tareas
que planifica operaciones para todos los usuarios. La comunicacin entre
aplicaciones de este tipo se realiza por medio de un sistema propietario de
comunicaciones interprocesos (IPC).
5 Open database conectivity: API de acceso a datos que soporta el acceso a cualquier
fuente de datos para la cual exista un driver ODBC. ODBC se encuadra dentro de los estndares ANSI e ISO para la Interfaz de llamadas de datos (CLI).
6 Remote procedure call: Una forma de comunicacin entre aplicaciones que esconde la complejidad de la red utilizando un mecanismo de llamada de procedimientos ordinario. Es un proceso sincrnico firmemente acoplado.
-
43
El ejemplo ms popular de motores de base de datos multiprocesos es el
Oracle Server (Oracle corporation) el cual carga 16 tipos de ejecutables distintos
que realizan distintas tareas. El sistema ejecuta sus aplicaciones que sirven para
administrar el acceso de mltiples usuarios a las tablas, el registro y control de
versiones de una transaccin y otras caractersticas como la replicacin de datos,
transacciones distribuidas. Por otro lado, cuando una conexin a la base de datos
se establece, el sistema carga los ejecutables relacionados a tareas de usuario.
Cada vez que un usuario se conecta a una base de datos Oracle, esta
carga un ejecutable con una nueva instancia de la base de datos, las consultas de
usuario son transmitidas a este ejecutable, el cual trabaja en conjunto con otros
ejecutables en el servidor que retornan conjuntos de datos, manejan los bloqueos
y ejecutan todas las funciones necesarias para el acceso de datos.
La mayora de los motores de base de datos multiprocesos fueron
desarrollados antes de que los sistemas operativos soportaran caractersticas
tales como hilos o planificacin de tareas (scheduling). Como resultado de esto, el
hecho de descomponer una operacin significaba escribir un ejecutable distinto
para manejar esta operacin. Esta caracterstica proporciona el beneficio de la
fcil escalabilidad a travs de la adicin de ms CPUs.
En un ambiente de multitarea el sistema operativo divide el tiempo de
procesamiento entre mltiples aplicaciones asignndoles una porcin de tiempo
de CPU (slice) a cada una. De esta manera siempre hay una sola tarea
ejecutndose a la vez, sin embargo el resultado es que mltiples aplicaciones
aparenten estar corriendo simultneamente en una sola CPU. La ventaja real, sin
embargo, viene cuando el sistema operativo cuenta con mltiples CPUs.
-
44
3.3.2.2. Motores de base de datos multihilos (Single-Process multi-threaded database engines).
Los motores de base de datos multihilos abordan el problema del acceso
multiusuario de una manera distinta, pero con principios similares. En lugar de
confiar en que el sistema operativo comparta los recursos de procesamiento, el
motor toma la responsabilidad por s mismo, lo que en la prctica se asocia a una
mejor portabilidad del sistema. Motores de base de datos comerciales como
Sybase Adaptive Server o Microsoft Sql Server son ejemplos de este enfoque.
Las ventajas de este tipo de motores radican en una mayor eficiencia en el
uso de recursos para determinadas plataformas. Mientas un sistema
multiprocesos consume entre 500 Kb y 1 Mb por conexin, un motor multihilos
consume entre 50 y 100 Kb de RAM diferencia que puede ser utilizada en cach
de datos y procedimientos. Otra ventaja es que no hay necesidad de un
mecanismo de comunicacin interprocesos.
De esta manera, la base de datos utiliza un elemento finito de trabajo, (el
hilo) para una variedad de operaciones (instrucciones de usuarios, bloqueos de
datos, E/S de disco, administracin del cach, etc.) en vez de utilizar aplicaciones
especializadas para cada tarea.
Las desventajas ms reconocidas son dos: escalabilidad y portabilidad. La
escalabilidad se centra en la habilidad que tengan los distintos motores de base de
datos multihilos de descomponer una operacin de manera que mltiples tareas
puedan ejecutar esta operacin.
Los problemas de portabilidad guardan relacin con el SMP
(multiprocesamiento simtrico) y se originan en el hecho de que dado que
diferentes fabricantes de hardware dan soporte a SMP de diferentes maneras,
-
45
estos motores de base de datos han tenido que implementar tcnicas neutras que
buscan funcionar bien en cualquier implementacin fsica, lo que conlleva una
sobrecarga en el motor y una limitacin en la habilidad de escalar a un gran
nmero de procesadores.
3.3.3. SGBD Paralelos.
Los sistemas paralelos de base de datos constan de varios procesadores y
varios discos conectados a travs de una red de interconexin de alta velocidad.
Para medir el rendimiento de los sistemas de base de datos existen 2 medidas
principales: la primera es la productividad (throughput) que se entiende como el
nmero de tareas que pueden completarse en un intervalo de tiempo determinado.
La segunda es el tiempo de respuesta (response time) que es la cantidad de
tiempo que necesita para completar una nica tarea a partir del momento en que
se enve. Un sistema que procese un gran nmero de pequeas transacciones
puede mejorar su productividad realizando muchas transacciones en paralelo. Un
sistema que procese transacciones ms largas puede mejorar tanto su
productividad como sus tiempos de respuesta realizando en paralelo cada una de
las subtareas de cada transaccin.
Las ganancias en este tipo de SGBD se pueden dar en trminos de velocidad
(menor tiempo de ejecucin para una tarea dada) y ampliabilidad (capacidad de
procesar tareas ms largas en el mismo tiempo).
Existen varios modelos de arquitecturas para maquinas paralelas, los ms
mencionados son:
Memoria Compartida : Todos los procesadores comparten una memoria
comn.
-
46
Disco Compartido: Todos los procesadores comparten una disposicin de
discos comn.
Sin Compartimiento: Los procesadores no comparten ni memoria ni disco.
Jerrquico: Compartimiento tanto de memoria como de disco.
3.3.4. SGBD Distribuidos.
En un SGBD distribuido, la base de datos se almacena en varios
computadores que se pueden comunicar a sus vez por distintos medios de
comunicacin (desde redes de alta velocidad a lneas telefnicas). No comparten
memoria ni discos y sus tamaos pueden variar tanto como sus funciones
pudiendo abarcar desde PC hasta grandes sistemas. Se denomina con el trmino
de emplazamientos o nodos a todos aquellos computadores que pertenecen a un
sistema distribuido.
Las principales diferencias entre las bases de datos paralelas y las bases
de datos distribuidas son las siguientes: las bases de datos distribuidas se
encuentran normalmente en varios lugares geogrficos distintos, se administran
de forma separada y poseen una interconexin ms lenta. Otra diferencia es que
en un sistema distribuido se dan dos tipos de transacciones, las locales y las
globales. Una transaccin local es aquella que accede a los datos del nico
emplazamiento en el cual se inici la transaccin. Por otra parte una transaccin
global es aquella que o bien accede a los datos situados en un emplazamiento
diferente de aquel en el que se inici la transaccin, o bien accede a datos de
varios emplazamientos distintos.
Un sistema de base de datos distribuido se conoce por:
Los distintos emplazamientos estn informados de los dems.
-
47
Aunque algunas relaciones pueden estar almacenadas slo en algunos
emplazamientos, stos comparten un esquema global comn.
Cada emplazamiento proporciona un entorno para la ejecucin de
transacciones tanto locales como globales.
-
48
Captulo 4. Introduccin al Procesamiento de Consultas,
El enfoque de System R.
4.1. Introduccin.
El Procesamiento de consultas hace referencia a la serie de actividades a
seguir para llevar a cabo la recuperacin de datos desde una base de datos. Estas
actividades incluyen la traduccin de consultas en lenguajes de consultas de alto
nivel (Ej: SQL) a expresiones que se puedan implementar en un nivel fsico, as
como tambin los algoritmos de evaluacin y optimizacin de consultas.
Una de las ventajas principales del modelo relacional presentado por Codd
en 1970 es la que tiene relacin con la independencia de los datos que se
entiende aqu como la separacin entre el modelo (lgico) y la implementacin
(fsica). Esta separacin nos permite desarrollar una poderosa semntica lgica
independiente de una implementacin fsica particular.
Uno de los desafos de la independencia de datos es que la codificacin de
una consulta para la base de datos se componga de 2 fases:
1. La descripcin lgica de la consulta (que se supone que debe hacer).
2. La definicin del plan de ejecucin fsico (el que muestra como implementar la
consulta).
Antes de empezar el Procesamiento de la consulta el sistema debe traducir
la consulta a un medio de representacin interno con el cual le sea fcil operar.
-
49
As, por ejemplo para SQL la representacin ms til es la del lgebra relacional
extendida (rbol relacional). Este proceso cumple la misma funcin que el
analizador lxico y sintctico de un compilador, es decir, revisa la sintaxis de la
consulta y chequea que todos lo identificadores sean nombres de objetos de la
base de datos, en el caso de las vistas reemplaza el nombre de la vista por la
expresin relacional que la representa.
El plan de ejecucin es un rbol relacional armado a partir de la consulta y
que slo puede ser entendido por el motor de ejecucin de consultas. La
transformacin de la consulta a un plan puede ser hecha efectivamente a mano y
en algunos casos de consultas simples que se ejecutan miles de veces esta
podra ser la mejor estrategia, sin embargo, una de las ventajas que nos ofrece el
modelo relacional es la capacidad de usar la informacin del catalogo de la base
de datos, que como se ver ms adelante, podr responder una gran cantidad de
preguntas distintas.
Por otro lado, aunque una consulta simple pueda ser ejecutada miles de
veces, no existe un camino mecnico que garantice que el plan de ejecucin
elegido satisfaga la consulta que se quiere implementar, puesto que:
1. Un Plan calculado a mano (o un plan precalculado) ser invalidado por
cambios lgicos dentro del esquema o por cambios fsicos en el camino de
acceso a la informacin o en el almacenamiento fsico.
2. Si los parmetros de la consulta (o los datos) cambian, la relacin optima que
asocia a un plan con una consulta por sobre otros puede cambiar.
La siguiente figura nos muestra los pasos en el procesamiento de una
consulta.
-
50
ConsultaAnalizador y
traductor(parser)
Expresin en Algebra Relacional
(Arbol relacional)
Optimizador
Plan de Ejecucin
Motor de Ejecucin
Resultadode la Consulta
Informacin del Catalogo
Datos
Figura 4-1 - Pasos en el procesamiento de una consulta SQL
Despus de enviar la consulta, la base de datos debe producir su
correspondiente plan de ejecucin. El primer paso en este proceso es traducir la
consulta desde SQL a un rbol lgico en lgebra relacional, proceso comnmente
llamado parser.
El Prximo paso es traducir el rbol de la consulta en el plan de ejecucin.
Generalmente existe un gran nmero de planes que implementan al rbol de la
consulta; el proceso de encontrar el mejor de estos planes se le denomina
optimizacin de consultas, entendindose que esta optimizacin viene dada por una medida de rendimiento para la ejecucin de consultas (como por ejemplo el
tiempo de ejecucin), queremos encontrar entonces la consulta que tenga el mejor
rendimiento de ejecucin. El objetivo es que el plan sea el ptimo (o el ms
cercano a) dado el espacio de bsqueda del optimizador.
-
51
Finalmente el optimizador enva el plan ptimo al motor de ejecucin. El
motor de ejecucin ejecuta el plan usando como entrada las relaciones
almacenadas en las base de datos y produce una tabla con los datos solicitados
como salida.
Los primeros optimizadores de consultas fueron descritos para System R
[Selinger79] y para Ingress [Wong76] en los aos 1979 y 1976 respectivamente.
Estos fueron implementados para variantes particulares del modelo Relacional y
funcionan lo suficientemente bien en la medida de sus implementaciones fsicas
del modelo. El Optimizador de System R ha sido la base de otros optimizadores de
bases de datos comerciales.
4.2. El optimizador de System R.
[Selinger79] propone una descomposicin de 4 fases en el procesamiento
de una consulta SQL: parsing, optimizacin, generacin de cdigo y ejecucin. Al
principio cada sentencia SQL es enviada al parser (analizador sintctico), quien se
encarga de chequear la sintaxis de la consulta; si no hay errores, el parser llama
al optimizador, quien toma todos los nombres de tablas y columnas referenciadas
por la consulta y las busca en el catalogo de la BD para verificar su existencia y
rescatar estadsticas y caminos de accesos almacenados. Es el optimizador quien
tambin analiza los tipos de datos y tamaos de cada columna con el fin de revisar
en la lista SELECT7 como en el Arbol WHERE8 la existencia de errores de semntica e incompatibilidades de tipos de datos.
7 Lista de todos los elementos que estn en una clusula select.
8 Estructura de rbol que contiene todos los predicados contenidos en la clausula WHERE.
-
52
Finalmente realiza la seleccin de los caminos de acceso. Si una consulta
tiene ms de un query block9 (en adelante bloque) determina el orden de
evaluacin de estos a lo largo de la consulta, luego procesa para cada bloque las
relaciones enunciadas en la lista FROM10. Si en el bloque existe ms de una
relacin, el optimizador realiza permutaciones de los mtodos de join, por tanto, se
elige el camino de acceso que minimice el costo para el bloque. Esta solucin
recibe el nombre de plan de ejecucin [Selinger79] el cual se representa en el
lenguaje de especificacin de accesos (ASL) cuya definicin queda fuera de los
alcances de este trabajo. Para mayor Informacin consultar [Lorie78].
El generador de cdigo es un programa que traslada rboles ASL en
lenguaje de mquina para ejecutar el plan escogido por el optimizador, para hacer
esto utiliza un pequeo nmero de plantillas de cdigo para representar todos los
casos posibles, durante esta fase se reemplaza el rbol generado por el parser en
cdigo de maquina ejecutable y sus estructuras de datos asociadas.
4.2.1. RSS (research storage system)
El RSS es el subsistema de almacenamiento de system R, este es el
responsable de mantener el almacenamiento fsico de las relaciones, de los
caminos de acceso a ellas, bloqueos (en un ambiente multiusuario), y de las
capacidades de registro de transacciones y recuperacin. El RSI (Research
Storage Interface) es la interfaz orientada a la tupla que system R presenta al
usuario final.
9 Un query block es un bloque de clusulas que conforman una consulta sql de la forma
SELECT, FROM, WHERE, GROUP BY, ORDER BY.
10 Lista de todas las relaciones enunciadas en la clausula FROM de una consulta sql.
-
53
Una Relacin se almacena en el RSS como una coleccin de tuplas que
cumplen con las siguientes caractersticas:
sus columnas son contiguas,
se almacenan en pginas de 4 Kb,
una tupla no puede rebasar una pgina.
Las pginas se organizan en segmentos, los segmentos pueden contener
una o ms relaciones pero una relacin no puede rebasar un segmento.
La manera de accesar tuplas de una relacin es por medio de un proceso
llamado RSS scan, este retorna una tupla a la vez a lo largo del camino de acceso
indicado. Los comandos principales son: OPEN, NEXT y CLOSE.
Existen 2 tipos de recorridos (scan), el primero es un segment scan, el cual
encuentra todas las tuplas de una relacin dada, consiste bsicamente de una
serie de NEXT que recorren todas las pginas del segmento (que pueden
contener tuplas para cualquier relacin) y de donde rescatan aquellas tuplas que
pertenecen a la relacin dada.
El segundo tipo de recorrido es un index scan11, los ndices se almacenan
en pginas distintas a las pginas de datos y son implementados como B-tree
cuyas hojas del rbol son pginas que contienen conjuntos de ya sea claves,
identificadores, o tuplas que contienen la clave; por lo tanto una serie de NEXT
sobre un index scan, realiza una lectura secuencial a lo largo de las hojas
obteniendo las tuplas de identificadores que se igualan a la clave de bsqueda o
usndolas para encontrar y retornar las tuplas de datos en el orden de las claves
11 un ndice puede ser creado por un usuario de system R en una o ms columnas de una
relacin, y una relacin puede cero o ms ndices asociados a esta.
-
54
dadas. Las paginas de ndices estn encadenas juntas, por lo tanto las sentencias
NEXT no necesitan referenciar paginas que se encuentren ms arriba del ndice.
En un segment scan todas las pginas no vacas de un segmento se
accesan slo una vez sin importar si tienen o no tuplas que pertenezcan a la
relacin. En un index scan las pginas de ndices se accesan slo una vez, sin
embargo las pginas de datos se pueden tocar ms de una vez.
Si las tuplas han sido insertadas en las paginas del segmento en el orden
del ndice y si este orden se mantiene diremos que el ndice es un ndice en
cluster, este tipo de ndices tiene la propiedad de que adems de las paginas de
ndices, tambin las paginas de datos se accesan solamente una vez en un index
scan. Cabe destacar de que un index scan no necesita recorrer toda la relacin,
pues puede recibir llaves de inicio y fin.
Ambos tipos de scan pueden recibir un conjunto de predicados llamados
predicados sargables o SARGS (search arguments) los cuales tiene la
particularidad de que son aplicados a las tuplas antes de que sean devueltas al
RSI. Un predicado sargable es uno de la forma:
columna operador_de_comparacin valor.
4.2.2. Costos para los caminos de acceso de relaciones simples.
El optimizador de System trata de manera distinta a las consultas que
hacen referencia a una sola tabla (relaciones simples) de las que se deben tratar
como un Join. Para el primer caso, el optimizador examina tanto los predicados de
la consulta como tambin los caminos de acceso disponibles para la relacin
referenciada y evala una frmula de costo para cada plan de acceso usando la
siguiente frmula:
-
55
COSTO = Pginas Rescatadas + W * (RSI calls)
Este costo es una medida de peso entre las E/S (pginas rescatadas) y la
utilizacin de CPU (instrucciones ejecutadas). W es un factor de peso ajustable
entre E/S y la CPU12. RSI calls es la estimacin del nmero de tuplas a retornar.
Dada esta formula la eleccin del camino de costo mnimo para procesar una
consulta tiende a minimizar el total de recursos requeridos.
La ejecucin de la validacin semntica del optimizador examina cada
bloque WHERE (el respectivo rbol debe estar en la forma normal conjuntiva) con
el objetivo de identificar los factores booleanos.
Se llama factor booleano a cada uno de los predicados del Arbol WHERE (o
conjunciones) que ha sido previamente normalizado.
Se dice que un ndice calza un factor booleano si el factor booleano es un
predicado sargable cuya columna referenciada es la clave del ndice.
Se dice que un predicado o un conjunto de predicados calza a un camino
de acceso por ndice cuando los predicados son sargables y las columnas
mencionadas en los predicados son un substring inicial del conjunto de columnas
de la clave del ndice. Si un ndice calza un factor booleano entonces un camino
de acceso que ocupe este ndice ser una manera eficiente de satisfacer el factor
booleano.
12 Una forma de calcularlo puede ser tomar los MIPS de una determinada CPU y por otro
lado tomar el nmero de instrucciones que se utilizan en una llamada RSS. W podra ser el producto de estos 2 valores medidos durante el tiempo transcurrido en una bsqueda tpica a disco. Por lo tanto W tendr diferentes valores dependiendo de distintas configuraciones de hardware. (Don Chamberlin, 12/09/2001)
-
56
Durante la mirada al catlogo, el optimizador recupera estadsticas para las
relaciones de la consulta y caminos de acceso disponibles para cada relacin. Las
estadsticas son las siguientes:
Para cada relacin T.
NCARD(T), cardinalidad de la relacin T.
TCARD(T), nmero de pginas del segmento que contienen tuplas de la relacin T.
P(T), fraccin de paginas de datos que contienen tuplas de la relacin T. P(T) = TCARD(T)/Nmero_de_pginas_no_vacas_en_el_segmento.
Para Cada ndice en la relacin T.
ICARD(I), Nmero de claves distintas en el ndice I
NINDEX(I), Nmero de pginas en el ndice I.
Estas estadsticas son mantenidas por el catlogo de System R, y
provienen de distintas fuentes, son actualizadas peridicamente por el comando
UPDATE STATISTICS, el cual puede ser ejecutado por cualquier usuario.
Usando estas estadsticas, el optimizador asigna un factor de seleccin F
para cada factor booleano en la lista de predicados. Este factor es la estimacin
de la cantidad de tuplas que satisfacen el predicado. Se asume que una falta de
estadsticas implica la eleccin de un factor arbitrario.
-
57
La siguiente tabla muestra los factores a utilizar para los distintos tipos de
predicados:
columna = valor
F = 1 / ICARD(ndice) si existe un ndice para la columna. Esto asume una distribucin uniforme de los datos a lo largo del dominio de la columna.
F = 1 / 10 en otro caso.
columna1 = columna2
F = 1 / MAX(ICARD(ndice_columna1), ICARD(ndice_columna2)) si existen ndices tanto en columna1 como en columna2. Esto asume que cada valor
en el dominio del ndice con menor cardinalidad se iguala a un valor
en el otro ndice.
F = 1 / ICARD(indice_columna-i) si slo existe un ndice sobre la columna-i
F = 1 / 10 en otro caso
Columna > valor (o cualquier otra comparacin abierta) F = (mayor_valor_dominio valor) / (mayor_valor_dominio
menor_valor_dominio) si la columna es de tipo aritmtico y el valor es conocido en el momento de escoger el camino de acceso.
mayor_valor y menor_valor son los lmites del dominio.
F = 1 / 3 en otro caso. Responde a la hiptesis de que son menos las consultas que usan predicados que son satisfechos por ms de la mitad de las tuplas.
Columna between valor1 and valor2
F = (valor2 valor1) / (mayor_valor_dominio menor_valor_dominio) que corresponde a una razn entre el rango de valores de la clusula
-
58
BETWEEN con respecto al rango de valores del dominio siempre que la
columna sea aritmtica y ambos valores sean conocidos al momento de escoger el camino de acceso.
F = 1 / 4 en otro caso.
Columna in (lista_de_valores) F = (numero_de_elementos_de_la_lista) * (factor_de_seleccin para
columna = valor) siempre y cuando no sea mayor que .
Columna in subconsulta
F = (cardinalidad estimada de la subconsulta) / (producto de las cardinalidades de todas las relaciones de la lista FROM de la
subconsulta)
El clculo de la cardinalidad de una subconsulta se explica ms adelante.
Predicado1 OR predicado2
F = F(predicado1) + F(predicado2) F(predicado1) * F(predicado2)
Predicado1 AND predicado2
F = F(predicado1) * F(predicado2)
NOT predicado
F = 1 F(predicado)
Tabla 4-1 -
![351cnicas de SQL Injection - Un Repaso.doc)Warning: SQL error: [Microsoft][ODBC SQL Server Driver][SQL Server]Unclosed quotation mark before the character string '\')'., SQL state](https://static.fdocumento.com/doc/165x107/5e897ea269259814a7275a32/351cnicas-de-sql-injection-un-warning-sql-error-microsoftodbc-sql-server.jpg)
