Bases de datos (teoría)

Qué es un sistema de bases de datos y cómo está construido

Imagina una escuela que guarda la dirección de cada alumno en dos lugares: la secretaría la anota en un cuaderno y la cafetería la anota en otro. Un alumno se muda, la secretaría corrige su cuaderno y la cafetería se olvida. Ahora la escuela tiene dos respuestas distintas para la misma pregunta. Guardar el mismo hecho en varios lugares se llama redundancia. Cuando las copias dejan de coincidir, hay inconsistencia.

Un sistema de bases de datos lo arregla poniendo los datos en un único lugar integrado, compartido por todos, y poniendo un programa a cargo: el SGBD. Puede quedar algo de redundancia por velocidad, pero entonces el propio SGBD se encarga de actualizar todas las copias.

Tres niveles de descripción

La arquitectura ANSI/SPARC describe los mismos datos en tres niveles, como tres maneras de mirar un edificio: el plano, la foto desde la calle y las tuberías dentro de las paredes.

  vista del usuario A  vista del usuario B  nivel EXTERNO
       |                |           (lo que ve cada usuario)
       +--- mapeo ------+
                |
        esquema conceptual            nivel CONCEPTUAL
                |               (todos los datos, lógicamente)
            mapeo
                |
         esquema interno              nivel INTERNO
                         (archivos, índices, orden físico)

• Nivel externo: la vista de cada usuario o programa. Pueden existir muchas vistas distintas.
• Nivel conceptual: una descripción lógica común de toda la base de datos.
• Nivel interno: cómo se guardan físicamente los datos: formatos de los registros almacenados, índices, orden físico.
• Los mapeos traducen entre los niveles, de modo que un cambio en un nivel se puede absorber sin tocar los otros.

Independencia de datos

Independencia de datos significa que los programas no se rompen cuando cambia la forma de guardar u organizar los datos. Sin ella, cada programa conocería el formato exacto del archivo y dejaría de funcionar cuando alguien lo cambiara. Hay dos tipos:

Ejemplo de independencia lógica: la tabla EMP se divide en EMP_PESSOAL y EMP_SALARIO. Una vista llamada EMP que une las dos tablas deja que los programas antiguos sigan funcionando. Las consultas quedan totalmente protegidas. Las actualizaciones solo funcionan si la vista es actualizable, porque no todo cambio en una vista se puede traducir de una única manera a las tablas reales. Crear un índice, en cambio, es un cambio físico: solo cambian el esquema interno y el mapeo conceptual/interno.

Lenguajes, catálogo y personas

• El DDL (lenguaje de definición de datos) describe los objetos: CREATE TABLE es una sentencia DDL.
• El DML (lenguaje de manipulación de datos) trabaja sobre el contenido: SELECT, INSERT, UPDATE, DELETE.
• El catálogo guarda los metadatos, que son datos sobre los datos: tablas, columnas, restricciones, usuarios. En un sistema relacional el propio catálogo está hecho de tablas, así que lo consultas con el mismo lenguaje que usas para los datos comunes.
• El administrador de datos (DA) decide qué datos guarda la organización y las políticas sobre ellos. El administrador de la base de datos (DBA) es el profesional técnico que implementa esas decisiones: esquemas, seguridad, recuperación y ajuste del rendimiento.

El modelo relacional: tablas, claves e integridad

Una lista de asistencia en papel tiene una fila de título (nombre, número, nota) y una fila para cada alumno. El modelo relacional convierte esa imagen en palabras precisas. Una relación es la tabla. Su encabezado es el conjunto de los nombres de columnas, llamadas atributos. Su cuerpo es el conjunto de las filas, llamadas tuplas. El grado es cuántos atributos hay, y la cardinalidad es cuántas tuplas hay en este momento.

Como una relación está hecha de conjuntos, tiene cuatro propiedades: no hay dos tuplas iguales, las tuplas no tienen orden, los atributos no tienen orden, y cada atributo guarda un único valor en cada tupla. Una tabla en papel es solo un dibujo de una relación, y el orden en que ves las filas no significa nada. Cada atributo se declara sobre un dominio, que es lo mismo que un tipo de dato: el conjunto de valores que puede tomar.

Un punto pequeño pero importante, de Date: un valor de relación nunca cambia, igual que el número 5 nunca cambia. Lo que cambia es la variable que guarda el valor. Esa variable se llama relvar (variable de relación). Cuando alguien dice 'actualizar una relación', en realidad está poniendo un valor nuevo en una relvar.

Claves

¿Cómo distinguir a dos alumnos que se llaman igual? Con una clave. Una superclave es cualquier conjunto de atributos cuyos valores son únicos en cada tupla. Una clave candidata es una superclave sin nada de sobra: si quitas cualquier atributo, deja de ser única. Una relación puede tener varias claves candidatas. Una se elige como clave primaria, y las otras son las claves alternativas.

Truco para contar: toda superclave es un conjunto que contiene alguna clave candidata. Si MATRICULA(aluno, disciplina, nota) tiene la única clave candidata {aluno, disciplina}, el único atributo libre es nota. Puedes agregarlo o no, así que hay exactamente 2 superclaves: {aluno, disciplina} y {aluno, disciplina, nota}.

Toda relación tiene al menos una clave candidata. La razón: no hay tuplas duplicadas, así que el conjunto de todos los atributos es siempre único, y quitarle los atributos innecesarios deja una clave candidata. Las tablas SQL que aceptan filas duplicadas pierden esta garantía.

Reglas de integridad

• Integridad de entidad: ningún componente de la clave primaria de una relación base puede ser nulo. Si no, habría una cosa registrada sin identidad conocida.
• Integridad referencial: una clave foránea es un conjunto de atributos cuyos valores deben coincidir con una clave candidata de otra relación, o de la misma relación. Todo valor no nulo de la clave foránea debe existir como valor de la clave referenciada. La regla se verifica al insertar en la relación que referencia y al borrar o cambiar la tupla referenciada.
• Una clave foránea puede apuntar a su propia relación. En EMP(eno, nome, gerente_eno), el atributo gerente_eno puede referenciar el eno de la propia EMP: el gerente también es un empleado.

Cuando se borra una fila referenciada, una acción referencial dice qué hace el SGBD con las filas que apuntan a ella:

CREATE TABLE emp (
	eno CHAR(3) PRIMARY KEY,
	dno CHAR(2) NOT NULL
		REFERENCES dept (dno) ON DELETE CASCADE
);
-- DELETE FROM dept WHERE dno = 'D1'
-- también borra a todos los empleados de D1 (CASCADE).
-- RESTRICT / NO ACTION lo rechazarían; SET NULL / SET DEFAULT
-- cambiarían la clave foránea en vez de borrar.

Restricciones por alcance, y el valor que falta

Date clasifica las restricciones de integridad según cuánto hay que examinar para verificarlas: una restricción de tipo mira un valor, una restricción de atributo mira el tipo de un atributo, una restricción de variable de relación mira una relvar, y una restricción de base de datos mira dos o más relvars. 'El salario de un empleado no puede ser mayor que el presupuesto de su departamento' menciona EMP y DEPT, así que es una restricción de base de datos. La integridad referencial es la restricción de base de datos más conocida.

A veces un valor es desconocido. SQL lo marca con NULL y usa lógica de tres valores: una condición puede ser verdadera, falsa o desconocida. Cualquier comparación con NULL es desconocida, y WHERE solo conserva las filas donde la condición es verdadera.

Diseñar antes de construir: entidades y relaciones

Antes de construir una casa dibujas un plano. Antes de construir una base de datos también dibujas un plano, y el más famoso es el diagrama entidad-relación (E/R). Una entidad es una cosa que queremos recordar (un alumno, una asignatura). Una relación (o asociación) conecta entidades (un alumno cursa una asignatura). Ambas pueden tener atributos.

En la notación original de Chen, los rectángulos son entidades, los rombos son relaciones y las elipses son atributos. Las líneas llevan la cardinalidad (1 o M).

+--------------+          /\          +-----------+
| DEPARTAMENTO |--1----- <  > ---M--| EMPREGADO |
+--------------+          \/          +-----------+
                         tem

rectángulo = entidad    rombo = relación

Cardinalidad

La cardinalidad de una relación dice cuántas ocurrencias de una entidad se conectan con una ocurrencia de la otra. Para averiguarla, lee la relación en los dos sentidos: ¿cuántos empleados tiene un departamento? Muchos. ¿Cuántos departamentos tiene un empleado? Uno. Entonces la relación es uno a muchos. Los tres tipos son uno a uno, uno a muchos y muchos a muchos.

¿Por qué una tercera tabla en muchos a muchos? Una clave foránea guarda un único valor, así que solo puede apuntar al lado 'uno'. Un alumno cursa muchas asignaturas y una asignatura tiene muchos alumnos, así que ninguna de las dos tablas puede guardar el vínculo. La nueva tabla se llama relación asociativa. En el lado 'uno' no se guarda nada: para hallar los empleados de un departamento consultas EMPREGADO por la clave foránea.

Las relaciones pueden tener atributos propios, cuando un hecho solo tiene sentido para el par. La nota nota pertenece a la relación MATRICULA, y no al alumno ni a la asignatura por separado, porque {aluno, disciplina} la determina y ninguno de los dos solo la determina.

Entidades débiles y subtipos

• Una entidad débil depende de otra entidad para existir. Si la dueña se va, la débil se va con ella. Los dependientes de un empleado, o las líneas de un pedido, son ejemplos. En las tablas, la clave de la entidad débil normalmente incluye la clave de la dueña.
• En el modelo E/R extendido, un supertipo y sus subtipos expresan 'es un'. Todo ENGENHEIRO es un EMPREGADO y hereda sus atributos. Un diseño común es una tabla para el supertipo y una para cada subtipo, donde la clave primaria del subtipo también es clave foránea hacia el supertipo.

La trampa ternaria

Una relación ternaria une tres entidades en un solo hecho: 'el proveedor F entrega la pieza P al proyecto J'. Es tentador reemplazarla por tres relaciones binarias (proveedor-pieza, pieza-proyecto, proyecto-proveedor). Pero tres hechos más débiles no suman el único hecho fuerte: unirlos puede inventar combinaciones que nunca ocurrieron. Este error es la trampa de conexión. El reemplazo solo es seguro cuando la tabla ternaria cumple una dependencia de junta sobre sus tres proyecciones, que es el tema de la quinta forma normal.

Álgebra relacional: hacer cuentas con tablas

En la aritmética tomas números y haces números nuevos con + y ×. En el álgebra relacional tomas relaciones (tablas) y haces relaciones nuevas con operadores. La regla importante es la clausura: el resultado de todo operador es de nuevo una relación. Por eso se pueden encajar operadores unos en otros, como una proyección de una selección de una junta.

Selección y proyección

FORNECEDOR            pi cidade (FORNECEDOR)
fno | cidade           cidade
F1  | Lisboa    --->  Lisboa
F2  | Porto           Porto
F3  | Lisboa           Faro
F4  | Faro
F5  | Porto         3 tuplas, no 5

La selección corta filas, la proyección corta columnas. La proyección puede volver iguales tuplas distintas, y como una relación es un conjunto, las repetidas aparecen una sola vez. SQL es distinto: mantiene las filas repetidas a menos que escribas DISTINCT.

Unión, intersección y diferencia

Estas vienen de la teoría de conjuntos, pero el resultado debe seguir siendo una relación. Por eso las dos entradas deben tener el mismo encabezado (mismos atributos y tipos). Esto se llama compatibilidad de unión. Unir proveedores con piezas daría tuplas de formas distintas.

La diferencia responde 'está en A y no está en B'. Con A = {1, 2, 3, 4} y B = {3, 4, 5}, A − B = {1, 2}. A diferencia de la unión y la intersección, no es conmutativa: B − A = {5}. La intersección ni siquiera es primitiva: A ∩ B = A − (A − B).

Producto y junta

El producto cartesiano R × S empareja cada tupla de R con cada tupla de S. Cada tupla del resultado son las dos pegadas, así que el grado es la suma de los grados y la cardinalidad es el producto de las cardinalidades. Si R tiene grado 3 y 4 tuplas, y S tiene grado 2 y 5 tuplas, el producto tiene grado 5 y 20 tuplas.

La junta natural conserva solo los pares que coinciden en los atributos comunes, y escribe el atributo común una sola vez. Las tuplas sin pareja desaparecen.

EMP            DEPT              EMP junta DEPT
eno dno        dno cidade        eno dno cidade
E1  D1        D1  Lima          E1  D1  Lima
E2  D1        D2  Quito         E2  D1  Lima
E3  D2        D4  Bogota        E3  D2  Quito
E4  D3

E4 busca D3: sin pareja.   Nadie busca D4.
Resultado: 3 tuplas.

Dos casos extremos muestran que el producto y la intersección son casos especiales de la junta. Con ningún atributo en común, todo par se acepta, así que la junta es el producto cartesiano. Con todos los atributos en común, solo se emparejan tuplas idénticas, así que la junta es la intersección R ∩ S.

División

La división responde preguntas del tipo 'para todos': ¿qué proveedores suministran todas las piezas de P? FP ÷ P devuelve los valores de fno que aparecen en FP junto con cada pno de P. Las piezas de más no importan. Una pieza que falta elimina al proveedor.

FP            P        FP / P
fno pno       pno      fno
F1  P1        P1       F1   (tiene P1, P2)
F1  P2        P2       F2   (tiene P1, P2)
F1  P3
F2  P1        F3 tiene P2 y P3 pero no P1: fuera
F2  P2
F3  P2
F3  P3

Leyes que el optimizador adora

La selección decide cada tupla por sí sola, así que se distribuye sobre la unión, la intersección y la diferencia. La proyección se distribuye sobre la unión, pero no sobre la diferencia ni sobre la intersección, porque quitar atributos puede hacer que tuplas distintas coincidan. Por ejemplo, π A (R − S) no siempre es π A (R) − π A (S). Reglas así permiten al SGBD reescribir una consulta en otra igual pero más rápida.

Cálculo y SQL: decir lo que quieres

Hay dos maneras de pedirle un sándwich a un amigo. Puedes dar una receta: 'toma dos rebanadas, unta mantequilla, pon queso'. O puedes describir el resultado: 'quiero un sándwich con queso'. El álgebra relacional es la receta: operadores aplicados paso a paso. El cálculo relacional es la descripción: dice una condición que las tuplas del resultado deben cumplir, usando lógica de predicados. Los dos tienen el mismo poder, así que un SGBD puede aceptar una descripción y convertirla en álgebra por dentro.

Los dos cuantificadores se enlazan por la negación: FORALL x (p) es lo mismo que NOT EXISTS x (NOT p). SQL tiene EXISTS y no tiene FORALL, así que una consulta 'para todos' usa dos negaciones. 'Alumnos matriculados en TODAS las asignaturas' se vuelve: alumnos para los cuales no existe una asignatura en la que no estén matriculados.

SELECT a.nome FROM aluno a
WHERE NOT EXISTS (
	SELECT * FROM disciplina d
	WHERE NOT EXISTS (
		SELECT * FROM matricula m
		WHERE m.aid = a.aid AND m.did = d.did));

El orden en que SQL realmente piensa

Escribes el SELECT primero, pero el SGBD piensa en otro orden: el FROM arma las filas, el WHERE descarta filas, el GROUP BY forma grupos, el HAVING descarta grupos, y solo entonces se calcula la lista del SELECT. Así, WHERE filtra filas y HAVING filtra grupos.

-- pedido(cliente, valor): (A,10) (A,30) (B,50)
--                       (C,5)  (C,5)  (C,15)
SELECT cliente
FROM pedido
GROUP BY cliente
HAVING SUM(valor) > 30;
-- A: 40, B: 50, C: 25  ->  A y B

Dónde SQL se aparta del modelo

• Multiconjuntos, no conjuntos. Una tabla de 5 proveedores en 3 ciudades da 5 filas para SELECT cidade FROM fornecedor. Las repeticiones solo desaparecen con SELECT DISTINCT.
• Las agregaciones ignoran NULL. SUM, AVG, MAX, MIN y COUNT(columna) ignoran los nulos. Solo COUNT(*) cuenta filas. Para bonos 10, 20, NULL, 30, AVG(bonus) es 20 (tres valores), y no 15.
• NOT IN y NULL. x NOT IN (lista) significa x <> v1 AND x <> v2 AND .... Si la lista contiene un NULL, un término es siempre desconocido, la condición entera nunca es verdadera, y la consulta no devuelve ninguna fila. Usa NOT EXISTS, o quita los nulos de la subconsulta.

Vistas

Una vista es una tabla virtual: el catálogo guarda solo la consulta que la define. Cuando consultas la vista, el SGBD reemplaza su nombre por la definición. Así la vista siempre muestra los datos actuales: si se inserta un producto nuevo de precio 500, la vista caros (productos por encima de 100) lo muestra de inmediato.

Actualizar a través de una vista es más difícil. Una fila de una vista que promedia salarios por departamento resume muchas filas de emp, así que UPDATE media_depto SET media = 5000 no tiene una única traducción a las filas base, y el SGBD lo rechaza.

Completitud relacional

Un lenguaje es relacionalmente completo cuando puede expresar toda consulta que el cálculo relacional puede expresar. El álgebra y el cálculo cumplen ese mínimo, y SQL también. Es solo un mínimo: las preguntas recursivas, como 'todos los componentes de una pieza a cualquier profundidad', quedan fuera.

Dependencias funcionales y formas normales

Mira una tabla que guarda, en cada fila, el pedido, el producto, la cantidad y también el nombre del producto. El nombre del producto 7 se escribe de nuevo en cada fila que menciona el producto 7. Eso gasta espacio y, peor, cuando el nombre cambia hay que arreglar muchas filas. La normalización es el remedio: dividir la tabla para que cada hecho se escriba una sola vez.

Dependencia funcional

Una dependencia funcional X → Y se cumple cuando dos tuplas que coinciden en X siempre coinciden en Y. X es el determinante. Como un código postal que determina la ciudad: mismo código, misma ciudad. Es una regla sobre el significado de los datos, así que debe cumplirse en todo valor válido de la relación.

Las inferencias válidas vienen de las reglas de Armstrong: reflexividad, aumento y transitividad. Puedes dividir el lado derecho libremente (A → BC da A → B y A → C). No puedes encoger el lado izquierdo: de AB → C no se concluye A → C, porque es una afirmación más fuerte que puede ser falsa.

Clausura, claves y coberturas

La clausura X+ es todo lo que X determina. Empieza con X y ve agregando el lado derecho de toda dependencia cuyo lado izquierdo ya está dentro, hasta que nada cambie. Si X+ es la relación entera, X es una superclave.

F = { A -> B,  B -> C,  CD -> E }

{A}+ :  {A}  --A->B-->  {A,B}  --B->C-->  {A,B,C}
                                CD -> E necesita D: alto

resultado: {A}+ = {A, B, C}

• Un atributo que aparece en ningún lado derecho nunca se puede derivar, así que pertenece a toda clave candidata. En R(A, B, C, D) con A → B y B → C, A y D son esos atributos, y {A, D}+ es todo, así que {A, D} es la única clave candidata.
• Para R(A, B, C, D) con AB → C, C → D, D → A, el atributo obligatorio es B. Probando los otros salen tres claves irreducibles: {A, B}, {B, C} y {B, D}.
• Una dependencia redundante se puede derivar de las demás. En {A → B, B → C, A → C}, la dependencia A → C se va, porque {A}+ sin ella ya contiene C. El conjunto limpio se llama cobertura irreducible (mínima).

La escalera de las formas normales

Para hallar la forma normal más alta, sube desde abajo y detente en el primer fallo. ITEM cumple la 1FN pero falla la 2FN. Una relación en 1FN cuya clave tiene un solo atributo ya está automáticamente en 2FN. Para una cadena transitiva, descompón en EMP(eno, dno) y DEPT(dno, cidade_depto).

Una relación que mezcla dos temas sufre tres anomalías. Inserción: no se puede registrar la ciudad de un proveedor hasta que suministre una pieza. Borrado: eliminar el último suministro de un proveedor borra también la ciudad. Modificación: el mismo hecho repetido en muchas filas debe cambiarse en todas.

3FN frente a FNBC

Solo se diferencian cuando hay claves candidatas compuestas que se solapan. Toma AULA(aluno, disciplina, professor) con {aluno, disciplina} → professor y professor → disciplina. Las claves son {aluno, disciplina} y {aluno, professor}. La dependencia professor → disciplina tiene un determinante que no es clave, pero un atributo primo (de clave) en el lado derecho. La 3FN lo tolera, la FNBC no. Entonces AULA está en 3FN, pero no en FNBC.

AULA(aluno, disciplina, professor)
   aluno, disciplina -> professor     professor -> disciplina

FNBC:  R1(professor, disciplina)   R2(aluno, professor)
sin pérdida: sí
perdida:     aluno, disciplina -> professor (queda en dos tablas)

Una buena descomposición es sin pérdida (juntar las partes devuelve exactamente el original, sin tuplas inventadas) y preserva las dependencias (cada dependencia se puede verificar dentro de una parte). Una descomposición a 3FN con las dos cualidades siempre existe. A FNBC siempre existe una sin pérdida, pero se puede perder una dependencia. El teorema de Heath da un caso seguro: si R(A, B, C) cumple A → B, entonces R(A, B) y R(A, C) se juntan de nuevo en R.

Formas superiores: 4FN y 5FN

Hay redundancia que no tiene una dependencia funcional detrás. En OFERTA(curso, professor, livro), los profesores de un curso y los libros de un curso son independientes, así que cada profesor debe listarse con cada libro. Esto es una dependencia multivaluada curso →→ professor. La relación está en FNBC, porque la única clave son los tres atributos, pero no está en 4FN. La solución son dos tablas: curso, professor y curso, livro.

Una dependencia de junta dice que una relación se puede reconstruir juntando algunas proyecciones. Con dos proyecciones es igual a una dependencia multivaluada. Algunas relaciones solo se descomponen sin pérdida en tres o más pedazos, y la 5FN (forma normal de proyección-junta) se ocupa de ellas. Es la última forma cuando solo se usan proyección y junta.

Hacer rápidas las consultas: optimizador e índices

Cuando le pides a un taxi que vaya al aeropuerto, no eliges las calles. Una consulta SQL es igual: dice lo que quieres, no cómo encontrarlo. Dentro del SGBD, el optimizador de consultas es el conductor que elige el camino. Reescribe la consulta en otras iguales, lista las maneras posibles de ejecutarla (leer toda la tabla, usar un índice, qué método de junta), estima el costo de cada una con las estadísticas del catálogo y elige un plan barato. Esta elección automática es lo que hace práctica la independencia de datos.

Corta primero

El truco más conocido: aplicar las selecciones lo antes posible, y las proyecciones también. Si unes dos tablas grandes y solo después te quedas con una ciudad, la junta trabaja con todo. Si te quedas con la ciudad primero, la junta recibe muchas menos filas. Los dos planes dan la misma respuesta por las leyes del álgebra, pero no el mismo costo.

plan lento                  plan rápido

  selección ciudad = X        junta
       |                     /    \
     junta             selección    \
    /    \             ciudad = X    \
  R        S              |          S
                          R

Índices

Un índice es la lista del final de un libro: lleva de un valor a las páginas donde aparece. Las búsquedas se vuelven más rápidas, pero toda inserción, actualización o borrado también debe arreglar el índice, y el índice ocupa espacio. Ese es el intercambio: búsqueda más rápida, actualización más lenta. Por eso se indexan las columnas muy buscadas y poco cambiadas.

Tres maneras de unir

Con 1.000 filas en R y 10.000 en S, el bucle anidado hace 1.000 × 10.000 = 10.000.000 de comparaciones. El hash hace alrededor de 1.000 + 10.000 = 11.000 pasos. Una junta con R.a < S.b no es una igualdad, así que el hash no se aplica, pero el bucle anidado sigue funcionando. El optimizador debe saber qué algoritmos son posibles antes de comparar costos.

El mini-proyecto Mini relational DBMS lo midió: diez veces más filas le cuestan al bucle anidado unas 80 veces más tiempo (la teoría dice 100), mientras que el hash y el ordenamiento con mezcla crecen casi en línea recta. Los números dependen de la máquina registrada en los resultados del proyecto.

Transacciones y recuperación

Enviar 100 pesos de Ana a Bia tiene dos pasos: quitarle 100 a Ana, sumarle 100 a Bia. Si se va la luz entre los dos pasos, 100 pesos desaparecen. Una transacción es una caja alrededor de los pasos: una unidad lógica de trabajo que lleva la base de datos de un estado correcto a otro estado correcto. O todo lo que está en la caja ocurre, o no ocurre nada.

COMMIT y ROLLBACK

• COMMIT dice 'éxito': las actualizaciones se vuelven permanentes.
• ROLLBACK dice 'fracaso': el SGBD deshace todas las actualizaciones desde que empezó la transacción, usando los valores antiguos guardados en el log, y la transacción termina.
• Después de cualquiera de los dos, se liberan los bloqueos y puede empezar una transacción nueva.

ACID

El log y la regla del write-ahead

El log (o diario) es un archivo secuencial donde el SGBD escribe el inicio y el fin de cada transacción y, por cada actualización, el valor antes y después. Es la base de toda recuperación. La regla del log write-ahead dice que el registro del log siempre va al disco antes que la página de datos modificada. Antes de escribir una página, el valor antiguo ya está en el log (así se puede deshacer). Antes de que el COMMIT termine, todos los registros ya están en el disco (así se puede rehacer).

El gestor de buffer tiene dos libertades. Puede escribir páginas de una transacción que no ha terminado (para liberar memoria): el disco puede tener cambios por deshacer. Y no está obligado a escribir las páginas en el COMMIT: al disco le pueden faltar cambios confirmados, que hay que rehacer. La mayoría de los sistemas usa las dos libertades, así que necesita deshacer y rehacer.

Reinicio tras una caída

Un checkpoint (punto de control) es un momento en que todas las páginas modificadas se escriben en el disco. Al reiniciar, el SGBD lee el log desde el último checkpoint y arma dos listas: las transacciones que hicieron COMMIT después del checkpoint van a rehacer, las que no tienen COMMIT hasta la caída van a deshacer. Las transacciones que terminaron antes del checkpoint se dejan en paz.

                 tc (checkpoint)          tf (caída)
T1  |------|      |                   |   terminó antes de tc: nada
T2       |--------|--------|          |   COMMIT después de tc: REHACER
T3           |----|-------------------|   sin COMMIT:           DESHACER
T4                |   |---------|      |   COMMIT después de tc: REHACER
T5                |          |---------|   sin COMMIT:           DESHACER

Una falla del sistema pierde la memoria, pero la base de datos en disco sigue ahí, así que la recuperación deshace y rehace desde el checkpoint. Una falla de medio destruye el disco mismo. Entonces la recuperación restaura la última copia de seguridad (backup) y rehace, desde el log, las transacciones confirmadas después de ella. Por eso el log vive en un dispositivo distinto al de la base de datos.

Confirmación en dos fases

Cuando una transacción cambia datos en dos sistemas, cada uno con su log, un COMMIT separado en cada uno podría salir bien en uno y fallar en el otro. En la confirmación en dos fases (two-phase commit), un coordinador primero pide a todos que se preparen y voten. Si todos dicen sí, decide confirmar. Un solo no hace que la decisión sea deshacer. Luego anuncia la decisión.

Muchos usuarios a la vez: bloqueos y aislamiento

Dos niños intentan escribir en la misma línea de un cuaderno al mismo tiempo. Sin una regla, uno borra las palabras del otro. Una base de datos tiene miles de usuarios, así que necesita reglas para compartir. El accidente clásico es la actualización perdida.

saldo = 100

T1 (+10)                T2 (+20)
READ saldo  -> 100
                        READ saldo  -> 100
WRITE saldo <- 110
                        WRITE saldo <- 120
COMMIT
                        COMMIT

saldo = 120   (debería ser 130: el +10 se perdió)

Bloqueos

Un bloqueo (lock) es un letrero en la puerta: 'en uso'. Un bloqueo compartido (S) se pide para leer, y varios pueden tenerlo a la vez. Un bloqueo exclusivo (X) se pide para cambiar, y no deja a nadie más. Si una petición es incompatible con un bloqueo que otra transacción mantiene, quien pidió espera.

Interbloqueo

Los bloqueos crean un peligro nuevo: dos niños sostienen un lápiz cada uno y cada uno espera el lápiz del otro. Un interbloqueo (deadlock) es un ciclo de transacciones en que cada una espera un bloqueo de la siguiente. El SGBD dibuja un grafo de espera (una flecha Ti → Tj significa que Ti espera a Tj). Un ciclo significa interbloqueo. Elige una transacción del ciclo como víctima y la deshace, lo que libera sus bloqueos.

T4 ---> T1 ---> T2
        ^        |
        |        v
        +------ T3

ciclo: T1 -> T2 -> T3 -> T1   (T4 solo espera)

Serializabilidad y bloqueo en dos fases

Una ejecución intercalada es serializable cuando su resultado es igual al de alguna ejecución serial (una transacción después de la otra). Cada transacción es correcta por sí sola, así que cualquier orden serial es correcto. Órdenes seriales distintos pueden dar resultados distintos, y todos se aceptan.

Para probarlo, arma un grafo de precedencia: una flecha Ti → Tj cuando una operación de Ti va antes de una operación conflictiva de Tj sobre el mismo elemento (al menos una es escritura). La ejecución es serializable si y solo si el grafo no tiene ciclos. En r1(A) w1(A) r2(A) w2(A) r2(B) w2(B) r1(B) w1(B), w1(A) antes de r2(A) da T1 → T2, y w2(B) antes de r1(B) da T2 → T1. Hay un ciclo, así que no es serializable.

El bloqueo en dos fases (2PL) es la regla que garantiza la serializabilidad. Una transacción tiene una fase de crecimiento, en que solo toma bloqueos, y luego una fase de encogimiento, en que solo los suelta. Después de la primera liberación, nunca más puede bloquear. Así, lock(A), unlock(A), lock(B), unlock(B) rompe el protocolo, mientras que lock(A), lock(B), unlock(A), unlock(B) lo obedece.

Niveles de aislamiento

El aislamiento total cuesta velocidad, así que el estándar SQL ofrece cuatro niveles definidos por los fenómenos que permiten. Una lectura sucia (dirty read) lee datos de una transacción que todavía no hizo COMMIT. Una lectura no repetible lee una fila dos veces y la encuentra cambiada o borrada por otra transacción. Un fantasma ejecuta la misma condición dos veces y encuentra una fila nueva que otra transacción insertó.

Proteger las filas que leíste no protege contra filas que todavía no existían. Los fantasmas exigen bloquear la condición o el rango, lo que hace SERIALIZABLE.

Bloqueos de intención

Los bloqueos pueden ser sobre una tabla entera o sobre filas individuales. Antes de bloquear una fila, una transacción toma un bloqueo de intención en la tabla: IS para leer filas, IX para cambiar filas. Entonces una petición para bloquear la tabla entera se decide mirando solo los bloqueos de la tabla. IS e IX conviven entre sí, S convive con IS, y X no convive con nada. Así, si T1 mantiene IX en emp, la petición de T2 por S en la tabla entera espera.

Seguridad e integridad: quién puede qué, y qué es válido

Una escuela tiene dos tipos de protección. El portero pregunta '¿tienes permiso para entrar?'. La maestra que corrige la tarea pregunta '¿lo que escribiste es correcto?'. Una base de datos tiene las mismas dos. La seguridad protege contra usuarios no autorizados. La integridad protege contra errores de usuarios autorizados. Las dos funcionan igual: las reglas se declaran al SGBD, se guardan en el catálogo y se verifican en cada operación.

Las reglas de integridad se explicaron antes (claves, claves foráneas y restricciones). Un usuario con todos los permisos aún puede teclear un salario equivocado, y es la integridad la que lo rechaza. Las fallas de disco y los cortes de energía no son ni una ni otra: pertenecen a la recuperación.

Control discrecional: GRANT y REVOKE

En el control de acceso discrecional, los usuarios tienen privilegios (consultar, insertar, cambiar, borrar) sobre objetos, y los privilegios se dan con GRANT y se quitan con REVOKE. Este es el esquema de SQL. Con WITH GRANT OPTION, quien recibe puede pasar el privilegio a otros, lo que forma una cadena.

-- DBA:
GRANT SELECT ON emp TO ana WITH GRANT OPTION;
-- ana:
GRANT SELECT ON emp TO bruno;
-- DBA:
REVOKE SELECT ON emp FROM ana CASCADE;
-- bruno también lo pierde: su privilegio vino solo de ana

En SQL estándar, CASCADE también quita los privilegios derivados del que retiras, y RESTRICT rechaza la operación si existen privilegios derivados. Un privilegio sobrevive solo si algún otro GRANT todavía lo sostiene.

Control obligatorio

En el control de acceso obligatorio, cada elemento de dato tiene un nivel de clasificación y cada usuario tiene un nivel de autorización, y reglas fijas deciden, no el dueño. El modelo de Bell-LaPadula protege el secreto con dos reglas. Con los niveles Público < Confidencial < Secreto < Ultrasecreto, un usuario con autorización Secreto:

• puede leer elementos clasificados como Secreto o inferior (la propiedad de seguridad simple: no se lee por encima de la propia autorización);
• puede escribir solo en Secreto o superior (la propiedad estrella: no se escribe por debajo de la propia autorización), para que un programa no copie un elemento secreto, ni siquiera por accidente, a un lugar que usuarios de menor autorización puedan leer.

Juntando todo

Un sistema de bases de datos es una historia con un orden claro. Describimos los datos (los niveles y el modelo relacional), dibujamos un plano (E/R), hacemos preguntas (álgebra, cálculo, SQL), limpiamos el diseño (dependencias funcionales y formas normales), lo hacemos rápido (optimizador e índices) y lo mantenemos seguro y correcto (transacciones, concurrencia, seguridad, integridad).

Errores que atrapan a muchos alumnos

• Creer que una relación guarda las filas en el orden de inserción. No lo hace: una relación es un conjunto.
• Llamar clave a algo porque las filas de hoy no se repiten. Una clave es una regla sobre el significado de los datos.
• Esperar que SELECT quite los duplicados. Las tablas SQL son multiconjuntos, así que usa DISTINCT.
• Seleccionar con una condición de distinto cuando la pregunta es 'no tiene': eso pide diferencia o NOT EXISTS.
• Olvidar que NULL deja las comparaciones desconocidas, así que NOT IN con un nulo en la lista no devuelve nada y AVG ignora los nulos.
• Pensar que la FNBC es siempre mejor. Elimina más redundancia, pero puede perder una dependencia, que la 3FN siempre mantiene.
• Mezclar seguridad (quién) con integridad (qué es válido), y ambas con recuperación (fallas).
• Creer que un índice es gratis. Acelera las búsquedas y atrasa las actualizaciones.