Procesamiento de Consultas
Descomposición y Optimización
Transformación de consultas declarativas SQL a comandos de manipulación de bajo nivel. Estudiaremos la arquitectura de 4 capas, las reglas de reducción algebraica y el modelado de costos en red.
1. Las 4 Capas del Procesamiento de Consultas
ARQUITECTURACuando un usuario lanza una consulta SQL sobre un esquema global, el procesador distribuido la somete a un embudo de cuatro transformaciones secuenciales:
Traduce la consulta en cálculo relacional (SQL) a un árbol de álgebra relacional operando estrictamente sobre las relaciones globales, sin saber aún que están fragmentadas.
Reemplaza cada relación global por su ecuación de reconstrucción (Unión ∪ o Join ⋈) y aplica algoritmos de reducción para podar ramas que generen datos vacíos.
Analiza el espacio de búsqueda (árboles de join) y selecciona el plan global que minimice la función de costo ($I/O + CPU + Red$), inyectando operaciones de transmisión.
Cada sitio físico recibe su fragmento de consulta y lo optimiza localmente aprovechando sus propios índices y rutas de acceso físicas en el disco.
2. Paso 1: Descomposición y Reestructuración Algebraica
CAPA 01La primera capa descompone el SQL mediante 4 fases internas estrictas. Si en el examen te piden auditar una consulta mal escrita, debes pasarlas por este filtro:
Normalización
Lleva la cláusula WHERE a su Forma Normal Conjuntiva (FNC) o Disyuntiva (FND).
Análisis Semántico
Construye el Grafo de Conexión de Relaciones. Si el grafo resultante queda desconectado, se rechaza la consulta inmediatamente por carecer de condiciones de join lógicas.
Simplificación
Elimina predicados redundantes aplicando reglas de idempotencia algebraica (p ∧ p ≡ p).
Reestructuración Algebraica (Regla de Oro)
Aplica reglas de equivalencia para empujar las operaciones de Selección ($\sigma$) y Proyección ($\pi$) lo más abajo posible en el árbol.
Justificación teórica: Al filtrar filas y columnas anticipadamente, se reduce drásticamente la cardinalidad de las relaciones intermedias antes de ejecutar costosos joins.
3. Paso 2: Localización de Datos y Podado de Ramas
CAPA 02Al sustituir las relaciones globales por sus fragmentos, el árbol crece exponencialmente. Para hacerlo tratable, aplicamos Reglas de Reducción Algebraica orientadas a detectar subconsultas cuyo resultado es vacío ($\emptyset$):
Contradicción de Predicados
Si una selección se aplica sobre un fragmento horizontal: $\sigma_{p_i}(R_j)$, el resultado es nulo ($\emptyset$) si el predicado de consulta $p_i$ contradice la condición de fragmentación de $R_j$.
(Ej: Buscar salarios > 50k en un fragmento que almacena salarios ≤ 30k).
Atributos Ausentes
Una proyección sobre un fragmento vertical: $\pi_{A}(R_j)$, se elimina por completo si el conjunto de atributos solicitados $A$ no está contenido en los atributos que preserva el fragmento $R_j$.
4. Paso 3: Optimización Global — INGRES vs. Sistema R
EXAMENLa optimización global busca el mejor árbol de joins. En la prueba te pedirán completar una tabla comparativa o justificar las diferencias entre los dos grandes motores clásicos:
| MÉTRICA / RASGO | ALGORITMO INGRES | SISTEMA R (IBM) |
|---|---|---|
| Enfoque de Búsqueda | Dinámico. Optimiza paso a paso mientras descompone. | Estático. Búsqueda exhaustiva por programación dinámica. |
| Mecanismo de Join | Sustitución de Tuplas (OVQP) | Árboles de Join Lineales Izquierdos |
| Estrategia de Transmisión | Envía fragmentos a un sitio maestro e itera fragmento a fragmento. | Almacena resultados temporales en sitios de join intermedios. |
| Aprovechamiento Físico | No considera índices de forma predictiva en su formulación. | Aprovecha explícitamente índices y ordenamiento (Sort-Merge). |
Factor de Selectividad de Joins ($SF_{\bowtie}$)
Para que el Sistema R prediga el costo de un join, calcula su factor de selectividad:
5. Simulador Interactivo: Podado de Ramas en Relación EMP
REDUCCIÓNAuditemos el ejercicio bibliográfico de la relación EMP fragmentada verticalmente en: EMP₁ = π(Eno, Ename)(EMP) y EMP₂ = π(Eno, Title)(EMP). Lanzamos la consulta: SELECT Ename FROM EMP. Presiona el botón para ejecutar las fases algebraicas: