Álgebra relacional para la optimización de consultas

Cuando se realiza una consulta, primero se escanea, analiza y valida. A continuación, se crea una representación interna de la consulta, como un árbol de consulta o un gráfico de consulta. Luego, se diseñan estrategias de ejecución alternativas para recuperar resultados de las tablas de la base de datos. El proceso de elegir la estrategia de ejecución más adecuada para el procesamiento de consultas se denomina optimización de consultas.

Problemas de optimización de consultas en DDBMS

En DDBMS, la optimización de consultas es una tarea crucial. La complejidad es alta ya que el número de estrategias alternativas puede aumentar exponencialmente debido a los siguientes factores:

La presencia de varios fragmentos.
Distribución de los fragmentos o tablas en varios sitios.
La velocidad de los enlaces de comunicación.
Disparidad en las capacidades de procesamiento local.

Por lo tanto, en un sistema distribuido, el objetivo suele ser encontrar una buena estrategia de ejecución para el procesamiento de consultas en lugar de la mejor. El tiempo para ejecutar una consulta es la suma de lo siguiente:

Es hora de comunicar consultas a bases de datos.
Es hora de ejecutar fragmentos de consultas locales.
Es hora de recopilar datos de diferentes sitios.
Es hora de mostrar los resultados a la aplicación.

Procesamiento de consultas

El procesamiento de consultas es un conjunto de todas las actividades desde la ubicación de la consulta hasta la visualización de los resultados de la consulta. Los pasos son los que se muestran en el siguiente diagrama:

Álgebra relacional

El álgebra relacional define el conjunto básico de operaciones del modelo de base de datos relacional. Una secuencia de operaciones de álgebra relacional forma una expresión de álgebra relacional. El resultado de esta expresión representa el resultado de una consulta de base de datos.

Las operaciones básicas son:

Projection
Selection
Union
Intersection
Minus
Join

Proyección

La operación de proyección muestra un subconjunto de campos de una tabla. Esto da una partición vertical de la mesa.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Nombre de la tabla}>)} $$

Por ejemplo, consideremos la siguiente base de datos de estudiantes:

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Amit Prasad	BCA	1	Masculino
4	Varsha Tiwari	BCA	1	Hembra
5	Asif Ali	MCA	2	Masculino
6	Joe Wallace	MCA	1	Masculino
8	Shivani Iyengar	BCA	1	Hembra

Si queremos mostrar los nombres y cursos de todos los estudiantes, usaremos la siguiente expresión de álgebra relacional:

$$ \ pi_ {Nombre, curso} {(ESTUDIANTE)} $$

Selección

La operación de selección muestra un subconjunto de tuplas de una tabla que satisface determinadas condiciones. Esto da una partición horizontal de la mesa.

Syntax in Relational Algebra

$$ \ sigma _ {<{Condiciones}>} {(<{Nombre de la tabla}>)} $$

Por ejemplo, en la tabla de Estudiantes, si queremos mostrar los detalles de todos los estudiantes que han optado por el curso MCA, usaremos la siguiente expresión de álgebra relacional:

$$ \ sigma_ {Course} = {\ small "BCA"} ^ {(ESTUDIANTE)} $$

Combinación de operaciones de proyección y selección

Para la mayoría de consultas, necesitamos una combinación de operaciones de proyección y selección. Hay dos formas de escribir estas expresiones:

Utilizando secuencia de operaciones de proyección y selección.
Uso de la operación de cambio de nombre para generar resultados intermedios.

Por ejemplo, para mostrar los nombres de todas las alumnas del curso BCA:

Expresión de álgebra relacional usando secuencia de operaciones de proyección y selección

$$ \ pi_ {Name} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(ESTUDIANTE)}) $$

Expresión de álgebra relacional usando la operación de cambio de nombre para generar resultados intermedios

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)} $$

$$ Result \ leftarrow \ pi_ {Name} {(FemaleBCAStudent)} $$

Unión

Si P es el resultado de una operación y Q es el resultado de otra operación, la unión de P y Q ($ p \ cup Q $) es el conjunto de todas las tuplas que están en P o en Q o en ambos sin duplicados .

Por ejemplo, para mostrar todos los estudiantes que están en el Semestre 1 o están en el curso BCA:

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(ESTUDIANTE)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(ESTUDIANTE)} $$

$$ Result \ leftarrow Sem1Student \ cup BCAStudent $$

Intersección

Si P es el resultado de una operación y Q es el resultado de otra operación, la intersección de P y Q ($ p \ cap Q $) es el conjunto de todas las tuplas que están en P y Q ambos.

Por ejemplo, dados los siguientes dos esquemas:

EMPLOYEE

EmpID	Nombre	Ciudad	Departamento	Salario

PROJECT

PId	Ciudad	Departamento	Estado

Para mostrar los nombres de todas las ciudades donde se encuentra un proyecto y también reside un empleado:

$$ CityEmp \ leftarrow \ pi_ {Ciudad} {(EMPLEADO)} $$

$$ CityProject \ leftarrow \ pi_ {Ciudad} {(PROYECTO)} $$

$$ Resultado \ leftarrow CityEmp \ cap CityProject $$

Menos

Si P es el resultado de una operación y Q es el resultado de otra operación, P - Q es el conjunto de todas las tuplas que están en P y no en Q.

Por ejemplo, para enumerar todos los departamentos que no tienen un proyecto en curso (proyectos con estado = en curso):

$$ AllDept \ leftarrow \ pi_ {Departamento} {(EMPLEADO)} $$

$$ ProjectDept \ leftarrow \ pi_ {Departamento} (\ sigma_ {Estado = \ small "en curso"} {(PROYECTO)}) $$

$$ Result \ leftarrow AllDept - ProjectDept $$

Unirse

La operación de unión combina tuplas relacionadas de dos tablas diferentes (resultados de consultas) en una sola tabla.

Por ejemplo, considere dos esquemas, Cliente y Sucursal en una base de datos bancaria de la siguiente manera:

CUSTOMER

CustID	AccNo	TypeOfAc	BranchID	Fecha de apertura

BRANCH

BranchID	BranchName	Código IFSC	Habla a

Para enumerar los detalles del empleado junto con los detalles de la sucursal:

$$ Result \ leftarrow CLIENTE \ bowtie_ {Customer.BranchID = Branch.BranchID} {SUCURSAL} $$

Traducir consultas SQL a álgebra relacional

Las consultas SQL se traducen en expresiones de álgebra relacional equivalentes antes de la optimización. Al principio, una consulta se descompone en bloques de consulta más pequeños. Estos bloques se traducen a expresiones de álgebra relacional equivalentes. La optimización incluye la optimización de cada bloque y luego la optimización de la consulta como un todo.

Ejemplos

Consideremos los siguientes esquemas:

EMPLEADO

EmpID	Nombre	Ciudad	Departamento	Salario

PROYECTO

PId	Ciudad	Departamento	Estado

TRABAJOS

EmpID	PID	Horas

Ejemplo 1

Para mostrar los detalles de todos los empleados que ganan un salario MENOS que el salario promedio, escribimos la consulta SQL:

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Esta consulta contiene una subconsulta anidada. Entonces, esto se puede dividir en dos bloques.

El bloque interior es -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Si el resultado de esta consulta es AvgSal, el bloque externo es:

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Expresión de álgebra relacional para bloque interno -

$$ AvgSal \ leftarrow \ Im_ {PROMEDIO (salario)} {EMPLEADO} $$

Expresión de álgebra relacional para bloque externo -

$$ \ sigma_ {Salario <{AvgSal}>} {EMPLOYEE} $$

Ejemplo 2

Para mostrar el ID del proyecto y el estado de todos los proyectos del empleado 'Arun Kumar', escribimos la consulta SQL -

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Esta consulta contiene dos subconsultas anidadas. Por lo tanto, se puede dividir en tres bloques, de la siguiente manera:

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Aquí ArunEmpID y ArunPID son los resultados de consultas internas)

Las expresiones de álgebra relacional para los tres bloques son:

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Nombre = \ small "Arun Kumar"} {(EMPLEADO)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(FUNCIONA)}) $$

$$ Resultado \ leftarrow \ pi_ {PID, Estado} (\ sigma_ {PID = \ small "ArunPID"} {(PROYECTO)}) $$

Cálculo de operadores de álgebra relacional

El cálculo de los operadores de álgebra relacional se puede realizar de muchas formas diferentes, y cada alternativa se denomina access path.

La alternativa de cálculo depende de tres factores principales:

Tipo de operador
Memoria disponible
Estructuras de disco

El tiempo para realizar la ejecución de una operación de álgebra relacional es la suma de -

Es hora de procesar las tuplas.
Es hora de recuperar las tuplas de la tabla del disco a la memoria.

Dado que el tiempo para procesar una tupla es mucho menor que el tiempo para recuperar la tupla del almacenamiento, particularmente en un sistema distribuido, el acceso al disco se considera muy a menudo como la métrica para calcular el costo de la expresión relacional.

Computación de la selección

El cálculo de la operación de selección depende de la complejidad de la condición de selección y la disponibilidad de índices en los atributos de la tabla.

A continuación se muestran las alternativas de cálculo según los índices:

No Index- Si la tabla no está ordenada y no tiene índices, entonces el proceso de selección implica escanear todos los bloques de disco de la tabla. Cada bloque se lleva a la memoria y cada tupla del bloque se examina para ver si satisface la condición de selección. Si se cumple la condición, se muestra como salida. Este es el enfoque más costoso ya que cada tupla se lleva a la memoria y cada tupla se procesa.
B+ Tree Index- La mayoría de los sistemas de bases de datos se basan en el índice B + Tree. Si la condición de selección se basa en el campo, que es la clave de este índice B + Tree, este índice se utiliza para recuperar resultados. Sin embargo, procesar declaraciones de selección con condiciones complejas puede implicar un mayor número de accesos a bloques de disco y, en algunos casos, un escaneo completo de la tabla.
Hash Index- Si se utilizan índices hash y su campo clave se utiliza en la condición de selección, la recuperación de tuplas mediante el índice hash se convierte en un proceso sencillo. Un índice hash utiliza una función hash para encontrar la dirección de un depósito donde se almacena el valor clave correspondiente al valor hash. Para encontrar un valor clave en el índice, se ejecuta la función hash y se encuentra la dirección del depósito. Se buscan los valores clave en el depósito. Si se encuentra una coincidencia, la tupla real se obtiene del bloque de disco a la memoria.

Cálculo de uniones

Cuando queremos unir dos tablas, digamos P y Q, cada tupla en P debe compararse con cada tupla en Q para probar si se cumple la condición de unión. Si se cumple la condición, las tuplas correspondientes se concatenan, se eliminan los campos duplicados y se añaden a la relación de resultado. En consecuencia, esta es la operación más cara.

Los enfoques comunes para la computación de combinaciones son:

Enfoque de bucle anidado

Este es el enfoque de unión convencional. Puede ilustrarse a través del siguiente pseudocódigo (Tablas P y Q, con tuplas tuple_p y tuple_q y atributo de unión a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Enfoque de clasificación y combinación

En este enfoque, las dos tablas se ordenan individualmente según el atributo de unión y luego se fusionan las tablas ordenadas. Se adoptan técnicas de clasificación externa ya que el número de registros es muy alto y no se pueden acomodar en la memoria. Una vez que se ordenan las tablas individuales, una página de cada una de las tablas ordenadas se lleva a la memoria, se fusiona en función del atributo de unión y se escriben las tuplas unidas.

Enfoque de combinación hash

Este enfoque consta de dos fases: fase de partición y fase de sondeo. En la fase de partición, las tablas P y Q se dividen en dos conjuntos de particiones disjuntas. Se decide una función hash común. Esta función hash se utiliza para asignar tuplas a particiones. En la fase de sondeo, las tuplas de una partición de P se comparan con las tuplas de la partición correspondiente de Q. Si coinciden, se escriben.