Localización de Fragmentos
Modelado Matemático y Costos
Fase 2 del diseño Top-Down. Análisis de algoritmos de asignación de fragmentos a sitios físicos de la red, evaluando el balance crítico entre costos de almacenamiento y transmisión.
1. El Problema de Localización y Optimización
TEORÍA BASEDados un conjunto de fragmentos F = {F1..Fn}, una red de sitios S = {S1..Sm} y un conjunto de aplicaciones Q = {q1..qk}, el problema consiste en encontrar la distribución óptima de F sobre S.
En el examen te pedirán contrastar los dos grandes enfoques teóricos de optimización:
Optimización por Costo Mínimo
Busca minimizar una función financiera combinada que suma: el costo de almacenar Fi en Sj, el costo de consultar Fi, el costo de actualizarlo en todas sus copias y el costo de comunicación de red.
Optimización por Mejor Desempeño
Ignora el dinero y se enfoca estrictamente en métricas de tiempo: busca minimizar el tiempo de respuesta de las consultas interactivas o maximizar los resultados (throughput) en cada sitio.
Respuesta: Mezclar ambas opciones de optimización (minimizar costo financiero y minimizar tiempo de respuesta simultáneamente) es matemáticamente complejo e intratable.
2. Formulación del Modelo Matemático
RESTRICCIONESPara modelar el sistema, definimos una variable de decisión booleana (Xj) que vincula físicamente un fragmento con un servidor:
El modelo matemático canónico impone que se debe minimizar el Costo Total, sujeto obligatoriamente a tres familias de restricciones operacionales:
Restricción de Tiempo de Respuesta
El tiempo de ejecución de una consulta estrictamente debe ser menor o igual al máximo permitido de tiempo de respuesta acordado con el usuario.
Restricciones de Almacenamiento (por sitio)
La sumatoria del requerimiento de almacenamiento de todos los fragmentos asignados a un sitio no puede superar la capacidad física del disco de dicho servidor.
Restricciones de Procesamiento (por sitio)
La carga de procesamiento en CPU/RAM requerida por todas las consultas derivadas a ese nodo no puede desbordar su capacidad de cómputo.
3. Desglose Anatómico del Costo Total (CT)
FINANZAS SGBDLa ecuación maestra que rige las evaluaciones teóricas divide el gasto en dos grandes sumatorias:
CALjk (Almacenamiento)
Es el costo estático de almacenar el fragmento Fj en el sitio Sk.
CPQi (Procesamiento)
Es el costo dinámico de procesar la consulta qi. Se descompone en dos sub-variables:
Anatomía Interna del Costo de Procesamiento por Consulta (CPQ)
Agrupa el Costo de Acceso (CA), Mantenimiento de Restricciones de Integridad (CR) y Control de Concurrencia (CC). El costo de acceso se formula evaluando las lecturas y actualizaciones:
- Costo de procesar actualizaciones (CPA): Multiplica el envío del mensaje de update más el costo del mensaje de recepción por cada sitio que posea una réplica del fragmento.
- Costo de procesar lecturas (CPL): Busca el mínimo necesario si los costos de transmisión difieren entre sitios: min(Sj)(CostoMensajeRecepción + CostoEnviarResultadoVuelta).
4. Auditor de Examen: Evaluación de Relación EMP
EJERCICIOEvaluaremos el ejercicio bibliográfico de la relación Emp(Eno, Ename, Dir, Dept, Job, Sal) fragmentada en F1(100Kb), F2(150Kb) y F3(200Kb). Existen 3 sitios (S1..S3) y 2 consultas: q1 (iniciada en S1) y q2 (iniciada en S2). Selecciona una alternativa para auditar su viabilidad financiera: