La composición de dos relaciones conecta elementos que están enlazados a través de un intermediario. Es el mecanismo que permite encadenar vínculos y recorrer estructuras en varios pasos.
Cuando dos relaciones comparten un conjunto intermedio, podemos combinarlas para obtener una nueva relación que va directamente del conjunto de partida al conjunto de llegada.
Esta operación, llamada composición, aparece con frecuencia en programación: encadenar funciones, recorrer grafos en múltiples pasos, combinar consultas en bases de datos o analizar dependencias transitivas son situaciones donde la composición de relaciones es la herramienta central.
Sean R una relación de A en B y S una relación de B en C. La composición de R y S, escrita S ∘ R, es la relación de A en C definida por:
El elemento b actúa como intermediario: pertenece al codominio de R y al dominio de S al mismo tiempo.
Nota sobre notación: en algunos textos se escribe R ∘ S en lugar de S ∘ R. En este curso usamos la notación en la que la relación aplicada primero se escribe a la derecha.
Sea A = {1, 2, 3}, B = {a, b}, C = {x, y}.
Para calcular S ∘ R buscamos todos los pares (elemento de A, elemento de C) conectados por un intermediario en B:
Podemos calcular la composición de dos relaciones con un algoritmo que busca intermediarios comunes.
const R = [[1, 'a'], [2, 'a'], [3, 'b']];
const S = [['a', 'x'], ['b', 'x'], ['b', 'y']];
function componer(R, S) {
const resultado = [];
for (const [a, b] of R) {
for (const [b2, c] of S) {
if (b === b2) {
const yaDuplicado = resultado.some(([x, y]) => x === a && y === c);
if (!yaDuplicado) resultado.push([a, c]);
}
}
}
return resultado;
}
console.log(componer(R, S));La función recorre todos los pares de R y S, y empareja aquellos cuyo elemento intermedio coincide.
Cuando R y S son relaciones sobre el mismo conjunto A, la composición también es una relación sobre A. En este caso suele escribirse R² para la composición de R consigo misma.
Ejemplo: Sea R = {(1, 2), (2, 3), (3, 4)} sobre A = {1, 2, 3, 4}.
Cada potencia avanza un paso más en la cadena de conexiones.
Si representamos las relaciones como matrices booleanas, la composición equivale a un producto booleano de matrices: en lugar de multiplicar con suma y producto ordinarios, usamos OR y AND.
function productoBooleanno(M1, M2) {
const n = M1.length;
const resultado = Array.from({ length: n }, () => Array(n).fill(false));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
if (M1[i][k] && M2[k][j]) {
resultado[i][j] = true;
break;
}
}
}
}
return resultado;
}
// Relación R: (1→2), (2→3), (3→4) en A = {1,2,3,4}
const MR = [
[false, true, false, false],
[false, false, true, false],
[false, false, false, true ],
[false, false, false, false]
];
const MR2 = productoBooleanno(MR, MR);
console.log(MR2);El producto booleano de matrices es equivalente al cálculo algebraico de la composición.
| Propiedad | ¿Se cumple? | Observación |
|---|---|---|
| Asociativa | Sí | (T ∘ S) ∘ R = T ∘ (S ∘ R) |
| Conmutativa | No en general | S ∘ R y R ∘ S pueden ser distintas |
| Elemento neutro | Sí | La relación identidad I cumple I ∘ R = R ∘ I = R |
| Distributiva sobre unión | Sí | R ∘ (S ∪ T) = (R ∘ S) ∪ (R ∘ T) |
La relación identidad sobre A es I_A = {(a, a) | a ∈ A}. Actúa como elemento neutro en la composición: componer cualquier relación con la identidad la deja igual.
Esto es análogo al papel del número 1 en la multiplicación ordinaria.
Calculemos R² para R = {(1, 2), (1, 3), (2, 4), (3, 4)} sobre A = {1, 2, 3, 4}.
Buscamos todos los pares (a, c) donde existe un b intermedio:
Aunque hay dos caminos de 1 a 4, el par (1, 4) aparece una sola vez en la composición.
| Área | Uso de la composición | Ejemplo concreto |
|---|---|---|
| Grafos | Alcanzabilidad en k pasos | ¿Hay camino de A a B en exactamente 2 saltos? |
| Bases de datos | JOIN entre tablas | Unir empleados con proyectos a través de asignaciones |
| Programación funcional | Composición de funciones | f ∘ g(x) = f(g(x)) |
| Redes | Encaminamiento en múltiples saltos | Ruta de un paquete a través de routers intermedios |
| Compiladores | Análisis de llamadas transitivas | ¿La función A llama a C a través de B? |
La clausura transitiva de una relación R puede definirse usando potencias de composición:
Cada potencia Rⁿ contiene los pares conectados por caminos de exactamente n pasos. La unión de todas las potencias da todos los pares alcanzables por cualquier camino.
function potencia(conjunto, relacion, n) {
let resultado = [...relacion];
let actual = [...relacion];
for (let i = 1; i < n; i++) {
actual = componer(actual, relacion);
for (const par of actual) {
const existe = resultado.some(([x, y]) => x === par[0] && y === par[1]);
if (!existe) resultado.push(par);
}
}
return resultado;
}
// t(R) aproximada hasta R^n (n = tamaño del conjunto)
function clausuraTransitivaPotencias(conjunto, relacion) {
return potencia(conjunto, relacion, conjunto.length);
}
const A = [1, 2, 3, 4];
const R = [[1, 2], [2, 3], [3, 4]];
console.log(clausuraTransitivaPotencias(A, R));La composición de relaciones es una operación fundamental que permite combinar relaciones para obtener nuevas conexiones indirectas. Aparece de forma natural en el encadenamiento de funciones, el recorrido de grafos, las consultas JOIN en bases de datos y el análisis de dependencias.
En el próximo tema estudiaremos las relaciones inversas, que permiten recorrer una relación en el sentido contrario, intercambiando el papel de dominio y codominio.