Cierre transitivo

En matemáticas , el cierre transitivo R ⁺ de una relación binaria homogénea R en un conjunto X es la relación más pequeña en X que contiene a R y es transitiva . Para conjuntos finitos, "más pequeña" puede tomarse en su sentido habitual, como aquella que tiene el menor número 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 en 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".

De forma más formal, el cierre transitivo de una relación binaria R en un conjunto X es la menor relación transitiva (con respecto a ⊆) R ⁺ en X tal que R ⊆ R ⁺ ; véase Lidl y Pilz (1998 , p. 337) . Tenemos R ⁺ = R si y solo si R misma es transitiva. 

Por el contrario, la reducción transitiva reduce una relación mínima S de una relación R dada de tal manera que tengan el mismo cierre, es decir, S ⁺ = R ⁺ ; sin embargo, pueden existir muchas relaciones 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 e 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 se puede denotar como: si x < y e y < z , entonces x < z .

Un ejemplo de 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 hecho de que exista un vuelo directo de una ciudad a otra, y de la segunda a la tercera, no implica que exista un vuelo directo de la primera a la tercera. La clausura transitiva de esta relación es diferente: "existe una secuencia de vuelos directos que comienza en la ciudad x y termina en la ciudad y ". Toda relación puede extenderse de forma 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 su clausura transitiva . Para comprobarlo, observe que la intersección de cualquier familia de relaciones transitivas también es transitiva. Además, existe al menos una relación transitiva que contiene a R , concretamente la trivial: X × X. La clausura transitiva de R viene dada 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 añadiendo aristas transitivas. Esto proporciona la intuición para una construcción general. Para cualquier conjunto X , podemos demostrar que el cierre transitivo viene dado por la siguiente expresión.

${\displaystyle R^{+}=\bigcup _{i=1}^{\infty }R^{i}.}$

dónde${\displaystyle R^{i}}$es la i -ésima potencia de R , definida inductivamente por

${\displaystyle R^{1}=R}$

y, para${\displaystyle i>0}$,

${\displaystyle R^{i+1}=R\circ R^{i}}$

dónde${\displaystyle \circ }$denota composición de relaciones .

Para demostrar que la definición anterior de R ⁺ es la relación transitiva más pequeña que contiene a R , mostramos que contiene a R , que es transitiva y que es el conjunto más pequeño con ambas características.

• ${\displaystyle R\subseteq R^{+}}$:${\displaystyle R^{+}}$contiene todo el${\displaystyle R^{i}}$, así que en particular${\displaystyle R^{+}}$contiene${\displaystyle R}$.
• ${\displaystyle R^{+}}$es transitivo: Si${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in R^{+}}$, entonces${\displaystyle (s_{1},s_{2})\in R^{j}}$y${\displaystyle (s_{2},s_{3})\in R^{k}}$para algunos${\displaystyle j,k}$por definición de${\displaystyle R^{+}}$. Dado que la composición es asociativa,${\displaystyle R^{j+k}=R^{j}\circ R^{k}}$; por eso${\displaystyle (s_{1},s_{3})\in R^{j+k}\subseteq R^{+}}$por definición de${\displaystyle \circ }$y${\displaystyle R^{+}}$.
• ${\displaystyle R^{+}}$es mínimo, es decir, si${\displaystyle T}$es cualquier relación transitiva que contiene${\displaystyle R}$, entonces${\displaystyle R^{+}\subseteteq T}$: Dado cualquier tal${\displaystyle T}$, inducción en${\displaystyle i}$se puede utilizar para mostrar${\displaystyle R^{i}\subseteteq T}$a pesar de${\displaystyle i}$de la siguiente manera: Base:${\displaystyle R^{1}=R\subseteq T}$por suposición. Paso: Si${\displaystyle R^{i}\subseteteq T}$sostiene y${\displaystyle (s_{1},s_{3})\in R^{i+1}=R\circ R^{i}}$, entonces${\displaystyle (s_{1},s_{2})\in R}$y${\displaystyle (s_{2},s_{3})\in R^{i}}$para algunos${\displaystyle s_{2}}$, por definición de${\displaystyle \circ }$. Por eso,${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in T}$por suposición y por hipótesis de inducción. Por lo tanto${\displaystyle (s_{1},s_{3})\in T}$por transitividad de${\displaystyle T}$; esto completa la inducción. Finalmente,${\displaystyle R^{i}\subseteq T}$a pesar de${\displaystyle i}$implica${\displaystyle R^{+}\subseteq T}$por definición de${\displaystyle R^{+}}$.

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, es necesario tomar el cierre transitivo. 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 preorden, es necesario tomar el cierre transitivo (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 entenderse como la construcción de una estructura de datos que permite responder preguntas sobre la alcanzabilidad . Es decir, ¿se puede llegar del nodo a al nodo d en uno o más saltos? Una relación binaria solo indica que el nodo a está conectado al nodo b , y que el nodo b está conectado al nodo c , etc. Una vez construido el cierre transitivo, como se muestra en la siguiente figura, en una operación de tiempo O(1) se puede determinar que el nodo d es alcanzable desde el nodo a . La estructura de datos se almacena normalmente como una matriz booleana, de modo que si matrix[1][4] = true, entonces el nodo 1 puede llegar al nodo 4 a través de uno o más saltos.

El cierre transitivo de la relación de adyacencia de un grafo 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 clúster , una unión disjunta de cliques . Construir el 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 los 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 se suele llamar 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 expresiva que FO fue descubierto por Ronald Fagin en 1974; el resultado fue redescubierto por Alfred Aho y Jeffrey Ullman en 1979, quienes propusieron usar la lógica de punto fijo como lenguaje de consulta de bases 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 expresiva que FO se deduce 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 sentencias lógicas expresables en TC. Esto se debe a que la propiedad de cierre transitivo guarda una estrecha relación con el problema STCON , completo en NL, para encontrar caminos dirigidos en un grafo. De manera similar, la clase L es lógica de primer orden con cierre transitivo conmutativo. Cuando se añade el cierre transitivo a la lógica de segundo orden , se obtiene PSPACE .

Desde la década de 1980, Oracle Database implementó una extensión SQLCONNECT BY... START WITH propietaria que permite el cálculo de un cierre transitivo como parte de una consulta declarativa. El estándar SQL 3 (1999) añadió una WITH RECURSIVEconstrucción más general que también permite calcular cierres transitivos dentro del procesador de consultas; a partir de 2011, esta última está implementada en IBM Db2 , Microsoft SQL Server , Oracle , PostgreSQL y MySQL (v8.0+). SQLite incorporó soporte para esta funcionalidad en 2014.

Datalog también implementa cálculos de cierre transitivo. ^{[ 4 ]}

MariaDB implementa expresiones de tabla comunes recursivas, que se pueden usar 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 . Reducir el problema a multiplicaciones de matrices de adyacencia permite alcanzar la complejidad temporal de los algoritmos rápidos de multiplicación de matrices , ^{[ 6 ].}${\displaystyle O(n^{2.3728596})}$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 puede resolverse mediante el algoritmo de Floyd–Warshall en ${\displaystyle O(n^{3})}$o mediante búsquedas repetidas en amplitud o en profundidad comenzando desde cada nodo del grafo.

Para grafos dirigidos, el algoritmo de Purdom resuelve el problema calculando primero su DAG de condensación y su cierre transitivo, y luego elevándolo al grafo original. Su tiempo de ejecución es${\displaystyle O(m+\mu n)}$, dónde${\displaystyle \mu }$es el número de aristas entre sus componentes fuertemente conectadas . ^{[ 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 ]}

• Relación ancestral
• Cierre deductivo
• Cierre reflejo
• Cierre simétrico
• Reducción transitiva (la relación más pequeña que tiene como clausura transitiva de R )

• Foto N. Afrati , Vinayak Borkar, Michael Carey , Neoklis Polyzotis, Jeffrey D. Ullman , Extensiones de Map-Reduce y consultas recursivas , EDBT 2011, 22-24 de marzo de 2011, Uppsala, Suecia, ISBN 978-1-4503-0528-0
• Aho, AV ; Ullman, JD (1979). "Universalidad de los lenguajes de recuperación de datos". Actas del 6.º Simposio ACM SIGACT-SIGPLAN sobre Principios de los lenguajes de programación - POPL '79 . págs. 110–119 . doi : 10.1145/567752.567763 . 
• Benedikt, M.; Senellart, P. (2011). «Bases de datos». En Blum, Edward K.; Aho, Alfred V. (eds.). Ciencias de la Computación. El hardware, el software y su esencia . pp. 169–229 . doi : 10.1007/978-1-4614-1168-0_10 . ISBN  978-1-4614-1167-3.
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Teoría de modelos finitos (2ª  ed.). Saltador. págs. 123 –124, 151– 161, 220– 235. ISBN  978-3-540-28787-2.
• Fischer, MJ; Meyer, AR (octubre de 1971). "Multiplicación de matrices booleanas y cierre transitivo" (PDF) . En Raymond E. Miller y John E. Hopcroft (eds.). Actas del 12.º Simposio Anual sobre Teoría de Conmutación y Autómatas (SWAT) . IEEE Computer Society. págs. 129–131 . doi : 10.1109/SWAT.1971.4 . 
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Teoría de modelos finitos y sus aplicaciones . Springer. págs. 151–152 . ISBN  978-3-540-68804-4.
• Keller, U., 2004, Algunas observaciones sobre la definibilidad del cierre transitivo en lógica de primer orden y Datalog (manuscrito inédito)
• Libkin, Leonid (2004), Elementos de la teoría de modelos finitos , Springer, ISBN 978-3-540-21202-7
• Lidl, R.; Pilz, G. (1998),Álgebra abstracta aplicada, Textos de pregrado en matemáticas (2.ª  ed.), Springer, ISBN 0-387-98290-6
• Munro, Ian (enero de 1971). "Determinación eficiente del cierre transitivo de un grafo dirigido". Information Processing Letters . 1 (2): 56– 58. doi : 10.1016/0020-0190(71)90006-8 .
• Nuutila, Esko (1995). Cálculo eficiente de cierre transitivo en grandes digrafos . Academia Finlandesa de Tecnología. ISBN 951-666-451-2OCLC 912471702​​ 
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Conceptos de sistemas de bases de datos (6.ª  ed.). McGraw-Hill. ISBN 978-0-07-352332-3.Apéndice C (solo en línea)

• " Cierre y reducción transitivos ", El repositorio de algoritmos de Stony Brook, Steven Skiena.