Diseño y Fragmentación
Teoría de Particionamiento Top-Down

Estudio exhaustivo para evaluación teórica. Contiene todas las justificaciones lógicas, pasos algebraicos y métricas de corrección basadas en la bibliografía oficial de la asignatura.

1. Dimensiones del Diseño y Requerimientos

FUNDAMENTOS

El diseño Top-Down se aplica en sistemas desarrollados desde cero (sistemas homogéneos) y requiere establecer exactamente dónde se ubican el SGBDD, los fragmentos de relaciones y las aplicaciones. Para justificar el diseño en el examen, se deben dominar las tres dimensiones del problema:

1. Nivel de Conocimiento

Determina si la organización posee información parcial o completa sobre las consultas del sistema.

2. Patrón de Acceso

Clasifica el comportamiento de las consultas a lo largo del tiempo como un flujo estático o dinámico.

3. Nivel de Compartición

Evalúa si los nodos de la red comparten únicamente datos o si comparten datos + programas.

Requerimientos de Información Obligatorios

Antes de fragmentar cualquier base de datos, el ingeniero debe recopilar obligatoriamente cuatro categorías de datos operacionales:

Base de datos: Cardinalidad de las relaciones e implicaciones lógicas de sus atributos.

Aplicaciones: Frecuencias de acceso de las consultas (acc(q_i)) y uso explícito de atributos.

Red de comunicación: Topología y costo de transmisión entre nodos.

Sistema de computadores: Capacidad de procesamiento y almacenamiento de cada sitio físico.

2. Reglas de Corrección de Fragmentación

AUDITORÍA

Toda partición (horizontal, vertical o híbrida) debe ser verificada mediante tres reglas inquebrantables. Si un esquema falla en una sola de ellas, el diseño es nulo:

REGLA 01

Completitud

La descomposición de una relación R en fragmentos R_1..R_n es completa sí y solo sí cada ítem de datos de R se encuentra en algún fragmento R_i.

Objetivo: Cero pérdida de datos.

REGLA 02

Reconstrucción

Debe existir un operador algebraico ∇ tal que R = ∇ R_i. En fragmentación horizontal el operador es la Unión (∪); en vertical es el Join (⋈).

Objetivo: Reversibilidad del esquema.

REGLA 03

Disjunción

Si un dato está en R_i, no debe estar en R_j. Excepción teórica: En fragmentación vertical, las claves primarias están exentas porque deben replicarse obligatoriamente.

Objetivo: Evitar redundancia inútil.

3. Fragmentación Horizontal Primaria (FHP) y Lógica Minterm

ALGORITMO FHP

La FHP particiona una relación propietaria aplicando operaciones de selección (R_j = \sigma_{F_j}(R)). La base lógica del examen radica en cómo construir el conjunto de Predicados Minterm (M), que son conjunciones de predicados simples afirmativos o negados. El procedimiento teórico exacto consta de 4 pasos:

Metodología de los 4 Pasos para FHP

Aplicar COM_MIN(R, Pr):Se audita el conjunto de predicados simples iniciales (Pr) para garantizar que sea Completo (misma probabilidad de acceso para cada tupla en un fragmento) y Minimal (descartar predicados que no generen accesos diferenciados por las apps).

Determinar el conjunto M de predicados Minterm:Generar todas las combinaciones conjuntivas posibles (m_i = \bigwedge p_j^*). Si hay n predicados simples, el espacio genera 2ⁿ minterms teóricos.

Determinar el conjunto I de implicaciones lógicas:Se analizan las dependencias semánticas de los atributos. Por ejemplo, si un atributo define la ubicación, la afirmación LOC="Montreal" implica lógicamente la negación de las demás: → NOT(LOC="New York").

Eliminar los minterms contradictorios:Todo minterm que viole una implicación del paso 3 posee una selectividad igual a cero (sel(m_i) = 0) y debe ser eliminado del sistema. Por ejemplo, un minterm que contenga (LOC="Montreal") ⋀ (LOC="New York") es lógicamente absurdo.

4. Fragmentación Horizontal Derivada (FHD) y Semi-Joins

ALGORITMO FHD

Se define sobre una relación Miembro (R) de un enlace, basándose en la fragmentación previamente aplicada sobre una relación Propietaria (S). Algebraicamente se implementa mediante el operador de Semi-Join (R_i = R \ltimes S_i).

Justificación de Completitud

Se demuestra a través de la integridad referencial. Si A es el atributo join, por cada tupla t de la relación miembro R, estrictamente debe existir una tupla propietaria t' en S tal que t[A] = t'[A].

Auditoría de Disjunción

En FHD, los fragmentos miembro son disjuntos solo si existe una dependencia funcional estricta donde cada tupla miembro asocia a una única tupla propietaria. (Ej: Un empleado posee un solo cargo).

Criterios de decisión para cadenas FHD: Cuando una relación miembro es apuntada por múltiples propietarias (Ej: ASG depende de PAY, EMP y PROJ), el ingeniero debe elegir la alternativa que genere relaciones intermedias más pequeñas (para acelerar el join) o la que beneficie a la mayor cantidad de aplicaciones mediante fragmentaciones en cascada (PAY → EMP → ASG).

5. Fragmentación Vertical (FV) — Algoritmo BEA

SIMULADOR

La FV divide los atributos de una relación replicando su clave primaria. Utiliza la Matriz de Afinidad de Atributos (AA), donde cada celda aff(A_i, A_j) suma las ejecuciones de todas las consultas que acceden a ambos atributos simultáneamente.

Fórmula de Contribución de Enlace (Algoritmo BEA):

cont(A_i, A_k, A_j) = 2·bond(A_i, A_k) + 2·bond(A_k, A_j) - 2·bond(A_i, A_j)

Donde bond(A_x, A_y) = ∑ aff(A_z, A_x) · aff(A_z, A_y). El algoritmo evalúa esta métrica para posicionar cada atributo en el lugar que maximice la afinidad global.

ESTADO: 01/03 (Matriz AA Bruta)

Matriz de Afinidad (PROJ)Atributos A1..A4

Cálculo de Beneficio (Z)

6. Fragmentación Híbrida (FH)

ESQUEMA COMPUESTO

En aplicaciones corporativas complejas, las relaciones se someten a descomposiciones sucesivas combinando particionamientos horizontales y verticales.

Árbol de Descomposición

La jerarquía se lee de arriba hacia abajo. Por ejemplo, una relación original R se particiona primero horizontalmente (HF) en R₁ y R₂. Luego, el fragmento R₁ se rompe verticalmente (VF) generando los sub-fragmentos finales R₁₁ y R₁₂.

R (Relación Total)

├── HF ──> R₁

│ ├── VF ──> R₁₁

│ └── VF ──> R₁₂

└── HF ──> R₂

├── VF ──> R₂₁

└── VF ──> R₂₂