20. Propiedades algebraicas de las relaciones

Las relaciones binarias forman un álgebra: pueden unirse, intersectarse, complementarse, componerse e invertirse. Conocer las leyes que gobiernan estas operaciones permite razonar sobre relaciones complejas de forma sistemática.

20.1 Introducción

A lo largo del curso hemos estudiado las relaciones como conjuntos de pares. Al tratarlas como conjuntos, heredan todas las operaciones conjuntistas: unión, intersección, diferencia y complemento. Además, tienen operaciones propias: composición e inversa.

Reunir estas operaciones en un marco algebraico permite demostrar propiedades complejas combinando leyes simples, de la misma manera que el álgebra booleana simplifica circuitos lógicos.

20.2 Operaciones fundamentales sobre relaciones

Sean R y S relaciones sobre el mismo conjunto A × B. Las operaciones básicas son:

Operación Notación Definición
Unión R ∪ S {(a, b) | (a, b) ∈ R o (a, b) ∈ S}
Intersección R ∩ S {(a, b) | (a, b) ∈ R y (a, b) ∈ S}
Diferencia R \ S {(a, b) | (a, b) ∈ R y (a, b) ∉ S}
Complemento R̄ o Rᶜ {(a, b) | (a, b) ∉ R} dentro de A × B
Composición S ∘ R {(a, c) | ∃b: (a,b) ∈ R y (b,c) ∈ S}
Inversa R⁻¹ {(b, a) | (a, b) ∈ R}

20.3 Implementación base en JavaScript

Definimos las operaciones elementales sobre las que construiremos los ejemplos del tema.

function union(R, S) {
  const resultado = [...R];
  for (const [a, b] of S) {
    if (!resultado.some(([x, y]) => x === a && y === b))
      resultado.push([a, b]);
  }
  return resultado;
}

function interseccion(R, S) {
  return R.filter(([a, b]) => S.some(([x, y]) => x === a && y === b));
}

function diferencia(R, S) {
  return R.filter(([a, b]) => !S.some(([x, y]) => x === a && y === b));
}

function inversa(R) {
  return R.map(([a, b]) => [b, a]);
}

function complemento(R, A, B) {
  const resultado = [];
  for (const a of A) {
    for (const b of B) {
      if (!R.some(([x, y]) => x === a && y === b))
        resultado.push([a, b]);
    }
  }
  return resultado;
}

20.4 Leyes de unión e intersección

Las operaciones de unión e intersección sobre relaciones satisfacen las mismas leyes que sobre conjuntos:

Ley Unión Intersección
Conmutativa R ∪ S = S ∪ R R ∩ S = S ∩ R
Asociativa (R ∪ S) ∪ T = R ∪ (S ∪ T) (R ∩ S) ∩ T = R ∩ (S ∩ T)
Distributiva R ∪ (S ∩ T) = (R ∪ S) ∩ (R ∪ T) R ∩ (S ∪ T) = (R ∩ S) ∪ (R ∩ T)
Idempotente R ∪ R = R R ∩ R = R
Elemento neutro R ∪ ∅ = R R ∩ (A×B) = R
Absorción R ∪ (A×B) = A×B R ∩ ∅ = ∅

20.5 Leyes de De Morgan para relaciones

El complemento de una relación satisface las leyes de De Morgan, análogas a las de la lógica proposicional y el álgebra de conjuntos:

(R ∪ S)ᶜ = Rᶜ ∩ Sᶜ (R ∩ S)ᶜ = Rᶜ ∪ Sᶜ 
function union(R, S) {
  const resultado = [...R];
  for (const [a, b] of S) {
    if (!resultado.some(([x, y]) => x === a && y === b))
      resultado.push([a, b]);
  }
  return resultado;
}

function interseccion(R, S) {
  return R.filter(([a, b]) => S.some(([x, y]) => x === a && y === b));
}

function complemento(R, A, B) {
  const resultado = [];
  for (const a of A) {
    for (const b of B) {
      if (!R.some(([x, y]) => x === a && y === b))
        resultado.push([a, b]);
    }
  }
  return resultado;
}

const A = [1, 2, 3];
const B = ['a', 'b'];

const R = [[1, 'a'], [2, 'b']];
const S = [[1, 'a'], [3, 'b']];

// Verificar (R ∪ S)ᶜ = Rᶜ ∩ Sᶜ
const ladoIzq = complemento(union(R, S), A, B);
const ladoDer = interseccion(complemento(R, A, B), complemento(S, A, B));

// Ambos deben contener los mismos pares
console.log(JSON.stringify(ladoIzq.sort()) === JSON.stringify(ladoDer.sort()));

20.6 Leyes de la composición

La composición tiene su propio conjunto de leyes algebraicas:

Ley Enunciado ¿Se cumple siempre?
Asociativa (T ∘ S) ∘ R = T ∘ (S ∘ R) Sí
Elemento neutro I ∘ R = R ∘ I = R Sí
Conmutativa S ∘ R = R ∘ S No en general
Distributiva sobre unión R ∘ (S ∪ T) = (R ∘ S) ∪ (R ∘ T) Sí
Distributiva sobre intersección R ∘ (S ∩ T) ⊆ (R ∘ S) ∩ (R ∘ T) Solo inclusión, no igualdad

20.7 Leyes de la inversa

La operación inversa interactúa con las demás operaciones de formas muy regulares:

(R⁻¹)⁻¹ = R (R ∪ S)⁻¹ = R⁻¹ ∪ S⁻¹ (R ∩ S)⁻¹ = R⁻¹ ∩ S⁻¹ (Rᶜ)⁻¹ = (R⁻¹)ᶜ (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹

Estas leyes permiten simplificar expresiones que combinan inversas con otras operaciones sin necesidad de recalcular todo desde cero.

20.8 Relación con la clausura y la identidad

La relación identidad I_A y la relación universal A × A actúan como los extremos del álgebra:

R ∘ I_A = I_A ∘ R = R (identidad: neutro de la composición) R ∪ ∅ = R (vacía: neutro de la unión) R ∩ (A×A) = R (universal: neutro de la intersección) R ∪ Rᶜ = A×A (complemento da la relación universal) R ∩ Rᶜ = ∅ (complemento da la relación vacía)

20.9 Ejemplo: verificar distributividad en JavaScript

Comprobamos que la composición distribuye sobre la unión.

function union(R, S) {
  const resultado = [...R];
  for (const [a, b] of S) {
    if (!resultado.some(([x, y]) => x === a && y === b))
      resultado.push([a, b]);
  }
  return resultado;
}

function componer(R, S) {
  const resultado = [];
  for (const [a, b] of R) {
    for (const [b2, c] of S) {
      if (b === b2 && !resultado.some(([x, y]) => x === a && y === c))
        resultado.push([a, c]);
    }
  }
  return resultado;
}

const R = [[1, 2], [2, 3]];
const S = [[2, 4]];
const T = [[3, 4]];

// R ∘ (S ∪ T)
const ladoIzq = componer(R, union(S, T));

// (R ∘ S) ∪ (R ∘ T)
const ladoDer = union(componer(R, S), componer(R, T));

console.log(JSON.stringify(ladoIzq.sort()) === JSON.stringify(ladoDer.sort()));

La verificación devuelve true, confirmando la ley distributiva.

20.10 Orden de inclusión entre relaciones

El conjunto de todas las relaciones sobre A × B puede ordenarse por inclusión: decimos que R ⊆ S cuando todo par de R también está en S. Este orden es parcial y tiene propiedades útiles:

R ⊆ S implica R ∪ T ⊆ S ∪ T R ⊆ S implica R ∩ T ⊆ S ∩ T R ⊆ S implica R ∘ T ⊆ S ∘ T R ⊆ S implica R⁻¹ ⊆ S⁻¹ 
function estaContenida(R, S) {
  return R.every(([a, b]) => S.some(([x, y]) => x === a && y === b));
}

const R = [[1, 2]];
const S = [[1, 2], [2, 3]];

console.log(estaContenida(R, S)); // true
console.log(estaContenida(S, R)); // false

20.11 Álgebra relacional y bases de datos

El álgebra relacional, base formal de los sistemas de bases de datos SQL, es directamente una instancia del álgebra de relaciones que estudiamos en este tema:

Operación algebraica Equivalente en SQL Ejemplo
Unión (R ∪ S) UNION Combinar dos listas de clientes
Intersección (R ∩ S) INTERSECT Clientes que compraron en ambas tiendas
Diferencia (R \ S) EXCEPT / MINUS Clientes de A que no están en B
Composición (S ∘ R) JOIN Empleados con sus proyectos asignados
Selección WHERE Filtrar pares que cumplen una condición

20.12 Resumen de leyes algebraicas

Operación Conmutativa Asociativa Neutro
Unión ∪ Sí Sí ∅
Intersección ∩ Sí Sí A×B
Composición ∘ No Sí I_A
Inversa ⁻¹ — — I_A⁻¹ = I_A

20.13 Errores comunes

  • Suponer que la composición distribuye exactamente sobre la intersección: solo se garantiza la inclusión, no la igualdad.
  • Confundir el complemento de una relación con su inversa: son operaciones distintas.
  • Creer que la composición es conmutativa por analogía con la unión o la intersección.
  • Olvidar que el elemento neutro de la composición es la identidad I_A, no la relación vacía.
  • Aplicar leyes de De Morgan sin verificar que los complementos se calculan sobre el mismo universo A × B.

20.14 Qué debes recordar de este tema

  • Las relaciones admiten unión, intersección, diferencia, complemento, composición e inversa.
  • Unión e intersección satisfacen conmutatividad, asociatividad, distributividad e idempotencia.
  • La composición es asociativa y tiene a la identidad como neutro, pero no es conmutativa.
  • Las leyes de De Morgan se cumplen para el complemento de relaciones.
  • La inversa distribuye sobre unión, intersección y composición (invirtiendo el orden).
  • El álgebra relacional de las bases de datos es una aplicación directa de estas propiedades.

20.15 Conclusión

Las propiedades algebraicas de las relaciones forman un sistema coherente y potente. Conocerlas permite manipular relaciones complejas, simplificar expresiones y razonar formalmente sobre estructuras de datos, consultas en bases de datos y algoritmos sobre grafos.

En el próximo tema iniciaremos el estudio de las funciones, que son un tipo especial de relación donde cada elemento del dominio tiene exactamente una imagen.

Volver al índice