Cierre transitivo

Relación transitiva más pequeña que contiene una relación binaria dada

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 .

Relaciones transitivas y ejemplos

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").

Existencia y descripción

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

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

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

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

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

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

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

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.

• ${\displaystyle R\subseteq R^{+}}$: contiene todos los , por lo que en particular contiene . ${\displaystyle R^{+}}$ ${\displaystyle R^{i}}$ ${\displaystyle R^{+}}$ ${\displaystyle R}$
• ${\displaystyle R^{+}}$es transitiva: Si , entonces y para algún por definición de . Como la composición es asociativa, ; por lo tanto por definición de y . ${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in R^{+}}$ ${\displaystyle (s_{1},s_{2})\in R^{j}}$ ${\displaystyle (s_{2},s_{3})\in R^{k}}$ ${\displaystyle j,k}$ ${\displaystyle R^{+}}$ ${\displaystyle R^{j+k}=R^{j}\circ R^{k}}$ ${\displaystyle (s_{1},s_{3})\in R^{j+k}\subseteq R^{+}}$ ${\displaystyle \circ }$ ${\displaystyle R^{+}}$
• ${\displaystyle R^{+}}$es mínima, es decir, si es cualquier relación transitiva que contiene , entonces : Dado cualquier tal , la inducción sobre se puede utilizar para mostrar para todos lo siguiente: Base: por suposición. Paso: Si se cumple, y , entonces y para algún , por definición de . Por lo tanto, por suposición y por hipótesis de inducción. Por lo tanto por transitividad de ; esto completa la inducción. Finalmente, para todos implica por definición de . ${\displaystyle T}$ ${\displaystyle R}$ ${\displaystyle R^{+}\subseteq T}$ ${\displaystyle T}$ ${\displaystyle i}$ ${\displaystyle R^{i}\subseteq T}$ ${\displaystyle i}$ ${\displaystyle R^{1}=R\subseteq T}$ ${\displaystyle R^{i}\subseteq T}$ ${\displaystyle (s_{1},s_{3})\in R^{i+1}=R\circ R^{i}}$ ${\displaystyle (s_{1},s_{2})\in R}$ ${\displaystyle (s_{2},s_{3})\in R^{i}}$ ${\displaystyle s_{2}}$ ${\displaystyle \circ }$ ${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in T}$ ${\displaystyle (s_{1},s_{3})\in T}$ ${\displaystyle T}$ ${\displaystyle R^{i}\subseteq T}$ ${\displaystyle i}$ ${\displaystyle R^{+}\subseteq T}$ ${\displaystyle R^{+}}$

Propiedades

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 teoría de grafos

El cierre transitivo construye el gráfico de salida a partir del gráfico de entrada.

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 .

Un gráfico de clúster , el cierre transitivo de un gráfico no dirigido

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]

En lógica y complejidad computacional

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 .

En lenguajes de consulta de bases de datos

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 RECURSIVEconstrucció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]

Algoritmos

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. ${\displaystyle O(n^{2.3728596})}$ ${\displaystyle O(n^{3})}$

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]} ${\displaystyle O(m+\mu n)}$ ${\displaystyle \mu }$

Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados ​​en el paradigma MapReduce . ^[11]

Véase también

• Relación ancestral
• Cierre deductivo
• Cierre reflexivo
• Cierre simétrico
• Reducción transitiva (una relación mínima que tiene como clausura transitiva la clausura transitiva de R )

Referencias

1. McColl, WF; Noshita, K. (1986), "Sobre el número de aristas en el cierre transitivo de un grafo", Discrete Applied Mathematics , 15 (1): 67–73, doi :10.1016/0166-218X(86)90020-X, MR  0856101
2. (Libkin 2004:vii)
3. (Libkin 2004:49)
4. (Silberschatz et al.2010:C.3.6)
5. "Descripción general de expresiones de tabla comunes recursivas". mariadb.com.
6. Munro 1971, Fischer y Meyer 1971
7. Purdom Jr., Paul (marzo de 1970). "Un algoritmo de cierre transitivo". BIT Numerical Mathematics . 10 (1): 76–94. doi :10.1007/BF01940892.
8. Paul W. Purdom Jr. (julio de 1968). Un algoritmo de cierre transitivo (Informe técnico de ciencias de la computación). Vol. 33. Universidad de Wisconsin-Madison .
9. ""El algoritmo de Purdom" en AlgoWiki".
10. ""Cierre transitivo de un gráfico dirigido" en AlgoWiki".
11. (Afrati y otros, 2011)

• 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 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 núcleo . 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 clausura transitiva" (PDF) . En Raymond E. Miller y John E. Hopcroft (ed.). Proc. 12th Ann. Symp. on Switching and Automata Theory (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 clausura transitiva en dígrafos grandes. Academia Finlandesa de Tecnología. ISBN 951-666-451-2.OCLC 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 (sólo en línea)

Enlaces externos

• "Cierre transitivo y reducción", The Stony Brook Algorithm Repository, Steven Skiena.