En matemáticas , la clausura transitiva R + de una relación binaria homogénea R sobre un conjunto X es la relación más pequeña sobre X que contiene a R y es transitiva . Para conjuntos finitos, "más pequeña" puede tomarse en su sentido habitual, de tener la menor cantidad de pares relacionados; para conjuntos infinitos R + es el único superconjunto transitivo mínimo de R.
Por ejemplo, si X es un conjunto de aeropuertos y x R y significa "hay un vuelo directo del aeropuerto x al aeropuerto y " (para x e y en X ), entonces el cierre transitivo de R sobre X es la relación R + tal que x R + y significa "es posible volar de x a y en uno o más vuelos".
Más formalmente, la clausura transitiva de una relación binaria R en un conjunto X es la relación transitiva más pequeña (wrt ⊆) R + en X tal que R ⊆ R + ; véase Lidl y Pilz (1998, p. 337). Tenemos R + = R si, y solo si, R en sí es transitiva.
Por el contrario, la reducción transitiva aduce una relación mínima S a partir de una relación dada R tal que tienen el mismo cierre, es decir, S + = R + ; sin embargo, pueden existir muchos S diferentes con esta propiedad.
Tanto el cierre transitivo como la reducción transitiva también se utilizan en el área estrechamente relacionada de la teoría de grafos .
Una relación R en un conjunto X es transitiva si, para todo x , y , z en X , siempre que x R y y y R z entonces x R z . Ejemplos de relaciones transitivas incluyen la relación de igualdad en cualquier conjunto, la relación "menor o igual que" en cualquier conjunto ordenado linealmente y la relación " x nació antes que y " en el conjunto de todas las personas. Simbólicamente, esto puede denotarse como: si x < y y y < z entonces x < z .
Un ejemplo de una relación no transitiva es " se puede llegar a la ciudad x mediante un vuelo directo desde la ciudad y " en el conjunto de todas las ciudades. El simple hecho de que exista un vuelo directo desde una ciudad a una segunda ciudad, y un vuelo directo desde la segunda ciudad a la tercera, no implica que exista un vuelo directo desde la primera ciudad a la tercera. El cierre transitivo de esta relación es una relación diferente, a saber, "existe una secuencia de vuelos directos que comienza en la ciudad x y termina en la ciudad y ". Toda relación puede extenderse de manera similar a una relación transitiva.
Un ejemplo de una relación no transitiva con un cierre transitivo menos significativo es " x es el día de la semana después de y ". El cierre transitivo de esta relación es "algún día x viene después de un día y en el calendario", lo cual es trivialmente cierto para todos los días de la semana x e y (y por lo tanto equivalente al cuadrado cartesiano , que es " x e y son ambos días de la semana").
Para cualquier relación R , siempre existe el cierre transitivo de R . Para comprobarlo, nótese que la intersección de cualquier familia de relaciones transitivas es nuevamente transitiva. Además, existe al menos una relación transitiva que contiene a R , a saber, la trivial: X × X . El cierre transitivo de R viene dado entonces por la intersección de todas las relaciones transitivas que contienen a R .
Para conjuntos finitos, podemos construir el cierre transitivo paso a paso, comenzando desde R y agregando aristas transitivas. Esto nos da la intuición para una construcción general. Para cualquier conjunto X , podemos demostrar que el cierre transitivo está dado por la siguiente expresión
donde es la i -ésima potencia de R , definida inductivamente por
y, para ,
donde denota composición de relaciones .
Para demostrar que la definición anterior de R + es la relación menos transitiva que contiene a R , demostramos que contiene a R , que es transitiva y que es el conjunto más pequeño con ambas características.
La intersección de dos relaciones transitivas es transitiva.
La unión de dos relaciones transitivas no tiene por qué ser transitiva. Para preservar la transitividad, se debe tomar la clausura transitiva. Esto ocurre, por ejemplo, al tomar la unión de dos relaciones de equivalencia o dos preórdenes . Para obtener una nueva relación de equivalencia o preórden, se debe tomar la clausura transitiva (la reflexividad y la simetría, en el caso de las relaciones de equivalencia, son automáticas).
En informática , el concepto de cierre transitivo puede considerarse como la construcción de una estructura de datos que permite responder a preguntas de accesibilidad . Es decir, ¿se puede llegar del nodo a al nodo d en uno o más saltos? Una relación binaria solo le dice que el nodo a está conectado al nodo b , y que el nodo b está conectado al nodo c , etc. Después de construir el cierre transitivo, como se muestra en la siguiente figura, en una operación O(1) se puede determinar que el nodo d es accesible desde el nodo a . La estructura de datos normalmente se almacena como una matriz booleana, por lo que si matriz[1][4] = verdadero, entonces es el caso de que el nodo 1 puede alcanzar el nodo 4 a través de uno o más saltos.
El cierre transitivo de la relación de adyacencia de un gráfico acíclico dirigido (DAG) es la relación de alcanzabilidad del DAG y un orden parcial estricto .
El cierre transitivo de un grafo no dirigido produce un grafo de conglomerados , una unión disjunta de grupos . La construcción del cierre transitivo es una formulación equivalente del problema de encontrar los componentes del grafo. [1]
El cierre transitivo de una relación binaria no puede, en general, expresarse en lógica de primer orden (FO). Esto significa que no se puede escribir una fórmula usando símbolos de predicado R y T que se satisfaga en cualquier modelo si y solo si T es el cierre transitivo de R. En la teoría de modelos finitos , la lógica de primer orden (FO) extendida con un operador de cierre transitivo generalmente se llama lógica de cierre transitivo y se abrevia FO(TC) o simplemente TC. TC es un subtipo de lógicas de punto fijo . El hecho de que FO(TC) sea estrictamente más expresivo que FO fue descubierto por Ronald Fagin en 1974; el resultado fue redescubierto luego por Alfred Aho y Jeffrey Ullman en 1979, quienes propusieron usar la lógica de punto fijo como un lenguaje de consulta de base de datos . [2] Con conceptos más recientes de la teoría de modelos finitos, la prueba de que FO(TC) es estrictamente más expresivo que FO se desprende inmediatamente del hecho de que FO(TC) no es local de Gaifman. [3]
En la teoría de la complejidad computacional , la clase de complejidad NL corresponde precisamente al conjunto de oraciones lógicas expresables en TC. Esto se debe a que la propiedad de clausura transitiva tiene una relación estrecha con el problema NL-completo STCON para encontrar caminos dirigidos en un grafo. De manera similar, la clase L es lógica de primer orden con la clausura transitiva conmutativa. Cuando la clausura transitiva se agrega a la lógica de segundo orden , obtenemos PSPACE .
Desde la década de 1980, Oracle Database ha implementado una extensión SQLCONNECT BY... START WITH
propia que permite el cálculo de un cierre transitivo como parte de una consulta declarativa. El estándar SQL 3 (1999) agregó una WITH RECURSIVE
construcción más general que también permite que los cierres transitivos se calculen dentro del procesador de consultas; a partir de 2011, este último se implementó en IBM Db2 , Microsoft SQL Server , Oracle , PostgreSQL y MySQL (v8.0+). SQLite lanzó soporte para esto en 2014.
Datalog también implementa cálculos de cierre transitivo. [4]
MariaDB implementa expresiones de tabla comunes recursivas, que se pueden utilizar para calcular cierres transitivos. Esta característica se introdujo en la versión 10.2.2 de abril de 2016. [5]
En Nuutila (1995) se pueden encontrar algoritmos eficientes para calcular el cierre transitivo de la relación de adyacencia de un grafo. Al reducir el problema a multiplicaciones de matrices de adyacencia se logra la complejidad temporal de la multiplicación de matrices [ 6] . Sin embargo, este enfoque no es práctico ya que tanto los factores constantes como el consumo de memoria para grafos dispersos son altos (Nuutila 1995, pp. 22-23, sect.2.3.3). El problema también se puede resolver mediante el algoritmo Floyd-Warshall en , o mediante una búsqueda repetida en amplitud o en profundidad comenzando desde cada nodo del grafo.
Para los grafos dirigidos, el algoritmo de Purdom resuelve el problema calculando primero su DAG de condensación y su clausura transitiva, para luego elevarlo al grafo original. Su tiempo de ejecución es , donde es el número de aristas entre sus componentes fuertemente conectados . [7] [8] [9] [10]
Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados en el paradigma MapReduce . [11]