En matemáticas , el cierre transitivo de una relación binaria 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, de tener la menor cantidad de pares relacionados; para conjuntos infinitos es el único mínimo superconjunto transitivo de R .
Por ejemplo, si X es un conjunto de aeropuertos y XRY medios "hay un vuelo directo desde el aeropuerto x a aeropuerto y " (para x y y en X ), entonces el cierre transitivo de R en X es la relación R + tal que x R + y significa "que es posible volar desde x a y en uno o más vuelos". De manera informal, el cierre transitivo le brinda el conjunto de todos los lugares a los que puede llegar desde cualquier lugar de partida.
Más formalmente, el cierre transitivo de una relación binaria R en un conjunto X es la relación transitiva R + en el conjunto X tal que R + contiene R y R + es mínimo Lidl y Pilz (1998 , p. 337). Si la relación binaria en sí es transitiva, entonces el cierre transitivo es esa misma relación binaria; de lo contrario, el cierre transitivo es una relación diferente.
En un área estrechamente relacionada de la teoría de grafos , la reducción transitiva es análoga a aducir un R mínimo del cierre R + dado .
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 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" en cualquier conjunto ordenado linealmente y la relación " x nació antes de 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 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 haya 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, a saber, "hay 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", que 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 , el cierre transitivo de R siempre existe. Para ver esto, tenga en cuenta 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, el uno trivial: X × X . El cierre transitivo de R viene dada entonces por la intersección de todas las relaciones transitivos que contienen R .
Para conjuntos finitos, podemos construir el cierre transitivo paso a paso, comenzando desde R y agregando bordes transitivos. Esto da la intuición para una construcción general. Para cualquier conjunto X , podemos probar que la clausura transitiva viene dada por la siguiente expresión
dónde es la i -ésima potencia de R , definida inductivamente por
y para ,
dónde denota composición de relaciones .
Para mostrar que la definición anterior de R + es la relación menos transitiva que contiene R , mostramos que contiene R , que es transitiva y que es el conjunto más pequeño con ambas características.
- : contiene todos los , entonces en particular contiene .
- es transitivo: Si , luego y para algunos por definición de . Dado que la composición es asociativa,; por eso por definición de y .
- es mínimo, es decir, si es cualquier relación transitiva que contenga , luego : Dado cualquiera de esos , inducción en se puede usar para mostrar para todos de la siguiente manera: Base: por suposición. Paso: si sostiene, y , luego y para algunos , por definición de . Por eso,por hipótesis y por hipótesis de inducción. Por eso por transitividad de ; esto completa la inducción. Finalmente, para todos implica por definición de .
Propiedades
La intersección de dos relaciones transitivas es transitiva.
La unión de dos relaciones transitivas no necesita ser transitiva. Para preservar la transitividad, hay que tomar el cierre transitivo. Esto ocurre, por ejemplo, al tomar la unión de dos relaciones de equivalencia o dos preordenes . Para obtener una nueva relación de equivalencia o preorden hay que tomar el cierre transitivo (la reflexividad y la simetría, en el caso de relaciones de equivalencia, son automáticas).
En teoría de grafos
En informática , el concepto de cierre transitivo se puede considerar como la construcción de una estructura de datos que permite responder preguntas de accesibilidad . Es decir, ¿se puede pasar del nodo a al nodo d en uno o más saltos? Una relación binaria le dice solo que el nodo a está conectado al nodo b , y que el nodo b está conectado al nodo c , etc. Después de que se construye el cierre transitivo, como se muestra en la siguiente figura, en una operación O (1) uno puede Determine que el nodo d es accesible desde el nodo a . La estructura de datos se almacena típicamente como una matriz, por lo que si matriz [1] [4] = 1, 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 grafo acíclico dirigido (DAG) es la relación de accesibilidad del DAG y un orden parcial estricto .
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 será satisfecho en cualquier modelo si y sólo 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 denomina 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 luego redescubierto 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 (Libkin 2004: vii). 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 (Libkin 2004: 49).
En la teoría de la complejidad computacional , la clase de complejidad NL corresponde precisamente al conjunto de oraciones lógicas que se pueden expresar en TC. Esto se debe a que la propiedad de cierre transitivo tiene una estrecha relación con el problema STCON de NL completo para encontrar rutas dirigidas en un gráfico. De manera similar, la clase L es lógica de primer orden con el cierre transitivo conmutativo. Cuando el cierre transitivo 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 SQL patentada CONNECT BY ... START WITH que permite el cálculo de un cierre transitivo como parte de una consulta declarativa. El estándar SQL 3 (1999) agregó una construcción WITH RECURSIVE más general que también permite que los cierres transitivos se calculen dentro del procesador de consultas; a partir de 2011, este último está implementado en IBM DB2 , Microsoft SQL Server , Oracle y PostgreSQL , aunque no en MySQL (Benedikt y Senellart 2011: 189).
Datalog también implementa cálculos de cierre transitivo (Silberschatz et al. 2010: C.3.6).
MariaDB implementa expresiones de tabla comunes recursivas, que se pueden usar para calcular cierres transitivos. Esta función se introdujo en la versión 10.2.2 de abril de 2016. [1]
Algoritmos
En Nuutila (1995) se pueden encontrar algoritmos eficientes para calcular el cierre transitivo de la relación de adyacencia de un gráfico. Los métodos más rápidos para el peor de los casos, que no son prácticos, reducen el problema a la multiplicación de matrices . El problema también se puede resolver mediante el algoritmo de Floyd-Warshall , o mediante una búsqueda repetida en amplitud o profundidad a partir de cada nodo del gráfico.
Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados en el paradigma MapReduce (Afrati et al. 2011).
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 su cierre transitivo)
Referencias
- ^ "Resumen de expresiones de tabla común recursiva" . mariadb.com.
- Lidl, R .; Pilz, G. (1998),Álgebra abstracta aplicada, Textos de pregrado en matemáticas (2a ed.), Springer, ISBN 0-387-98290-6
- Keller, U., 2004, Algunas observaciones sobre la definibilidad del cierre transitivo en la lógica de primer orden y el registro de datos (manuscrito inédito)
- 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 . Saltador. págs. 151-152. ISBN 978-3-540-68804-4.
- Libkin, Leonid (2004), Elementos de la teoría de modelos finitos , Springer, ISBN 978-3-540-21202-7
- Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Teoría de modelos finitos (2ª ed.). Saltador. pp. 123 -124, 151-161, 220-235. ISBN 978-3-540-28787-2.
- Aho, AV; Ullman, JD (1979). "Universalidad de los lenguajes de recuperación de datos". Actas del VI 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.
- Nuutila, E., Cálculo de cierre transitivo eficiente en grandes dígrafos. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 páginas. Publicado por la Academia de Tecnología de Finlandia. ISBN 951-666-451-2 , ISSN 1237-2404 , UDC 681.3.
- Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Conceptos del sistema de base de datos (6ª ed.). McGraw-Hill. ISBN 978-0-07-352332-3. Apéndice C (solo en línea)
- Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries , EDBT 2011, 22-24 de marzo de 2011, Uppsala, Suecia, ISBN 978-1-4503-0528-0
enlaces externos
- " Cierre y reducción transitiva ", The Stony Brook Algorithm Repository, Steven Skiena.
- " Apti Algoritmi ", un ejemplo y algunas implementaciones en C ++ de algoritmos que calculan el cierre transitivo de una relación binaria dada, Vreda Pieterse.