Clausura transitiva

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 en un conjunto X es la relación más pequeña en X que contiene R y es transitiva . Para conjuntos finitos, "más pequeño" puede tomarse en su sentido habitual, el de tener el menor número de pares relacionados; para conjuntos infinitos R ⁺ es el superconjunto transitivo mínimo único de R .

Por ejemplo, si X es un conjunto de aeropuertos y x R y significa "hay un vuelo directo desde el 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, el cierre transitivo de una relación binaria R en un conjunto X es la relación transitiva R ⁺ más pequeña (wrt ⊆) en X tal que R ⊆ R ⁺ ; véase Lidl y Pilz (1998, p. 337). Tenemos R ⁺ = R si, y sólo si, R en sí es transitivo.

Por el contrario, la reducción transitiva aduce una relación mínima S a partir de una relación R dada tal que tienen el mismo cierre, es decir, S ⁺ = R ⁺ ; sin embargo, pueden existir muchas 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" 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 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. Simplemente porque hay un vuelo directo de una ciudad a una segunda ciudad, y un vuelo directo de la segunda ciudad a la tercera, no implica que haya un vuelo directo de la primera ciudad a la tercera. El cierre transitivo de esta relación es una relación diferente, es decir, "hay una secuencia de vuelos directos que comienza en la ciudad x y termina en la ciudad y ". Cada relación se puede extender 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 , la clausura transitiva de R siempre existe. Para ver esto, observe que la intersección de cualquier familia de relaciones transitivas es nuevamente transitiva. Además, existe al menos una relación transitiva que contiene R , a saber , la trivial: X × X. La clausura transitiva de R viene dada entonces por la intersección de todas las relaciones transitivas que contienen R.

Para conjuntos finitos, podemos construir el cierre transitivo paso a paso, comenzando desde R y agregando aristas transitivas. Esto da 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 está 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 mostrar 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 transitivo: si , entonces y para algunos 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ínimo, es decir, si hay alguna relación transitiva que contenga , entonces : Dada cualquiera de ellas , la inducción en puede usarse para mostrar para todos de la siguiente manera: Base: por suposición. Paso: Si se cumple, y , entonces y para algunos , por definición de . Por tanto, por suposición y por hipótesis de inducción. Por 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 preorden 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 , se puede considerar que el concepto de cierre transitivo construye una estructura de datos que permite responder preguntas sobre accesibilidad . Es decir, ¿se puede pasar del nodo a al nodo d en uno o más saltos? Una relación binaria sólo 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 determine que el nodo d es accesible desde el nodo a . La estructura de datos generalmente se almacena como una matriz booleana, por lo que si matriz [1] [4] = verdadero, entonces se da el caso de que 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 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 cluster , una unión disjunta de camarillas . Construir la clausura transitiva es una formulación equivalente del problema de encontrar las componentes del gráfico. ^[1]

En lógica y complejidad computacional

La clausura transitiva 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 utilizando los símbolos de predicado R y T que se satisfaga en cualquier modelo si y sólo si T es la clausura transitiva de R. En la teoría de modelos finitos , la lógica de primer orden (FO) extendida con un operador de cierre transitivo suele denominarse 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 por Alfred Aho y Jeffrey Ullman en 1979, quienes propusieron utilizar 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 deriva 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 cierre transitivo tiene una estrecha relación con el problema STCON completo de NL para encontrar rutas dirigidas en un gráfico. De manera similar, la clase L es lógica de primer orden con cierre conmutativo y transitivo. Cuando se agrega un cierre transitivo 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 patentada 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 calcular cierres transitivos dentro del procesador de consultas; a partir de 2011, este último está implementado 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 gráfico. Reducir el problema a multiplicaciones de matrices de adyacencia logra la menor ^{[ cita necesaria ]} complejidad temporal, a saber. el de la multiplicación de matrices (Munro 1971, Fischer & Meyer 1971), que es a diciembre de 2020 . Sin embargo, este enfoque no es práctico ya que tanto los factores constantes como el consumo de memoria para gráficos dispersos son altos (Nuutila 1995, págs. 22-23, sección 2.3.3). El problema también se puede resolver mediante el algoritmo de Floyd-Warshall en , o mediante una búsqueda repetida en amplitud o en profundidad comenzando desde cada nodo del gráfico. ${\displaystyle O(n^{2.3728596})}$^[actualizar] ${\displaystyle O(n^{3})}$

Para gráficos dirigidos, el algoritmo de Purdom resuelve el problema calculando primero su condensación DAG y su cierre transitivo, y luego elevándolo al gráfico original. Su tiempo de ejecución es , donde es el número de aristas entre sus componentes fuertemente conectados . ^{[6] [7] [8] [9]} ${\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 . ^[10]

Ver también

• Relación ancestral
• Cierre deductivo
• Cierre reflexivo
• Cierre simétrico
• Reducción transitiva (una relación más pequeña que tiene el cierre transitivo de R como cierre transitivo)

Referencias

1. McColl, WF; Noshita, K. (1986), "Sobre el número de aristas en el cierre transitivo de un gráfico", Matemáticas Aplicadas Discretas , 15 (1): 67–73, doi :10.1016/0166-218X(86)90020-X, Señor  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. Purdom Jr., Paul (marzo de 1970). "Un algoritmo de cierre transitivo". BIT Matemáticas Numéricas . 10 (1): 76–94. doi :10.1007/BF01940892.
7. Paul W. Purdom Jr. (julio de 1968). Un algoritmo de cierre transitivo (Informe Técnico de Informática). vol. 33. Universidad de Wisconsin-Madison .
8. ""Algoritmo de Purdom "en AlgoWiki".
9. ""Cierre transitivo de un gráfico dirigido "en AlgoWiki".
10. (Afrati et al.2011)

• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, 22 al 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 el corazón . págs. 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 (ed.). Proc. 12º Ana. Síntoma. sobre Teoría de Conmutación y Autómatas (SWAT) . Sociedad de Computación IEEE. págs. 129-131. doi :10.1109/SWAT.1971.4.
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Martín Marx; Joel Spencer; Moshé Y. Vardi; Ydé Venema; Scott Weinstein (2007). Teoría de modelos finitos y sus aplicaciones . Saltador. 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 registro de datos (manuscrito no publicado)* 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". Cartas de procesamiento de información . 1 (2): 56–58. doi :10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995). Cálculo eficiente del cierre transitivo en dígrafos grandes. Academia Finlandesa de Tecnología. ISBN 951-666-451-2. OCLC  912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Conceptos del sistema de bases de datos (6ª ed.). McGraw-Hill. ISBN 978-0-07-352332-3.Apéndice C (solo en línea)

enlaces externos

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