Algoritmos básicos para implementar operaciones de consultas.
a) Reglas heurísticas: Permiten ordenar operaciones en una estrategia de ejecución.
b) Estimación de costo: Estimar el costo de las estrategias de ejecución.

El SGBD

Tiene implementado los algoritmos de las operaciones relacionales, las cuales aparecen en una estrategia de ejecución.

- Considerando el siguiente esquema de B.D:

Clic en la imagen para agrandar.

¿Cuántas tuplas dan las siguientes sentencias?

σ noEmpleado = 115 (Empleado) --- 1 tupla

σ noDepto > 5 (Depto) --- algunas

σ noDepto = 5 (Empleado) --- algunas

σ noDepto = 5^salario > 3000 ^sexo =”F” (Empleado) --- algunas

σ noEmpleado = 115^noProyecto = 10 (TrabajaEn) ---- algunas

Implementación de la operación de Selección

1) Selección (σ)

2) Proyección (π)

3) Reunión (IXI)

4) Conjuntos

a) Búsqueda Lineal (fuerza bruta)

- Leer todos los registros del archivo

- Verificar si todos los valores de los atributos satisfacen la condición de selección.

b) Búsqueda binaria

- Condición de selección, implica una comparación de igualdad sobre un atributo clave (es ordenado).

- Se efectúa en bloques en vez de registros.

- Utiliza una asignación indizada (donde uno o más bloques de índice contienen apuntadores a los bloques de archivos reales).

Bloque: Unidad de transferencia de datos entre el disco y la memoria.

Clic en la imagen para agrandar.

Descriptor de archivo: Contiene la información necesaria para los programas que tienen acceso a los registros de un archivo.

c) Empleo de un índice primario o una clave de dispersión para obtener un solo registro.

- Se aplica cuando la condición de igualdad es un atributo clave o un índice primario o bien una clave de dispersión.

Indice primario: Es un archivo ordenado cuyos registros son de longitud fija, el cual contiene dos campos:

Valor de la clave primaria del ancla del bloque

Apuntador a un bloque de disco (dirección de bloque)

Ejemplo:

Clic en la imagen para agrandar.

Clave de dispersión

- Proporciona un acceso rápido en ciertas condiciones de búsqueda.

- Basado en la técnica hashing.

- Establece una función h, llamada función de dispersión o aleatorización.

- Se aplica al campo de dispersión de un archivo y produce la dirección del bloque de disco en el que se está almacenando el registro.

- La condición de búsqueda debe ser una condición de igualdad sobre un campo (campo de dispersión).

d) Empleo de un índice primario para leer múltiples registros

- La condición de comparación >, >=,<,<= sobre un campo que tiene un índice primario. - En el caso de (1.2), se usa el índice para satisfacer la condición de igualdad (noDepto=5) y luego se leen los registros subsecuentes del archivo (ordenado). σ noDepto > 5 (Depto) --- (1.2)

e) Empleo de un índice de agrupamiento para leer múltiples registros

- Indice de agrupamiento acelera la obtención de registros que tienen el mismo valor en el campo de agrupamiento.
- Si los registros de un archivo están ordenados físicamente según un campo no clave que no tiene un valor distinto para cada registro, dicho campo se llama campo de agrupamiento.
- (1.3) La condición de selección implica una comparación de igualdad sobre un campo no clave que tiene un índice de agrupamiento.

σ noDepto = 5 (Empleado) --- (1.3)

f) Empleo de un índice secundario (árbol B+) en una comparación de igualdad.

- Se aplica cuando la condicicón de selección es una comparación de igualdad.

- Permite obtener un solo registro si el campo de indización tiene valores únicos (es una clave).

- Permite obtener multiples registros si el campo de indización no es una clave.

- Obtener registros que satisfacen las condiciones >, >=,<,<=.

Indice Secundario

g) Selección conjuntiva

- Se dice que la condición de selección esta compuesta por condiciones simples, las cuales están conectadas por operadores lógicos como AND.

- Se pueden utilizar los métodos anteriores para resolver tales consultas. (1.4)

h) Selección conjuntiva con índice compuesto.

- Se aplica cuando existe un índice compuesto (o estructura de dispersión) sobre los campos combinados. (1.5)

Indice compuesto: Si dos o más campos intervienen en la condición de igualdad.

σ noDepto = 5^salario > 3000 ^sexo =”F” (Empleado) --- (1.4)

σ noEmpleado = 115^noProyecto = 10 (TrabajaEn) ---- (1.5)