Fechamento transitivo - Transitive closure

Em matemática , o fechamento transitivo de uma relação binária R em um conjunto X é a menor relação em X que contém R e é transitiva . Para conjuntos finitos, "menor" pode ser tomado em seu sentido usual, de ter o menor número de pares relacionados; para conjuntos infinitos é o único mínima super transitiva de R .

Por exemplo, se X é um conjunto de aeroportos e XRY meios "existe um voo directo do Aeroporto de x para o aeroporto y " (para x e y em X ), em seguida, o encerramento transitória de R em X é a relação R ⁺ tal que x R ⁺ y significa "é possível voar de x para y em um ou mais voos". Informalmente, o fechamento transitivo fornece o conjunto de todos os lugares que você pode ir a partir de qualquer ponto de partida.

Mais formalmente, o fechamento transitivo de uma relação binária R em um conjunto X é a relação transitiva R ⁺ no conjunto X tal que R ⁺ contém R e R ⁺ é mínimo Lidl & Pilz (1998 , p. 337). Se a própria relação binária é transitiva, então o fechamento transitivo é a mesma relação binária; caso contrário, o fechamento transitivo é uma relação diferente.

Por outro lado, a redução transitiva aduz uma relação mínima S de uma dada relação R tal que eles têm o mesmo fechamento, isto é, S ⁺ = R ⁺ ; no entanto, podem existir muitos S diferentes com esta propriedade.

O fechamento transitivo e a redução transitiva também são usados na área intimamente relacionada da teoria dos grafos .

Relações transitivas e exemplos

Uma relação R em um conjunto X é transitiva se, para todo x , y , z em X , sempre que x R y e y R z então x R z . Exemplos de relações transitivas incluem a relação de igualdade em qualquer conjunto, a relação "menor ou igual" em qualquer conjunto ordenado linearmente e a relação " x nasceu antes de y " no conjunto de todas as pessoas. Simbolicamente, isso pode ser denotado como: se x < y e y < z, então x < z .

Um exemplo de relação não transitiva é "a cidade x pode ser alcançada por meio de um vôo direto da cidade y " no conjunto de todas as cidades. O simples fato de haver vôo direto de uma cidade para a segunda cidade e vôo direto da segunda cidade para a terceira não significa que haja vôo direto da primeira cidade para a terceira. O fechamento transitivo dessa relação é uma relação diferente, a saber, "há uma sequência de voos diretos que começa na cidade xe termina na cidade y ". Toda relação pode ser estendida de maneira semelhante a uma relação transitiva.

Um exemplo de relação não transitiva com um fechamento transitivo menos significativo é " x é o dia da semana após y ". O fechamento transitivo desta relação é "algum dia x vem depois de um dia y no calendário", que é trivialmente verdadeiro para todos os dias da semana x e y (e, portanto, equivalente ao quadrado cartesiano , que é " x e y são ambos os dias da semana ").

Existência e descrição

Para qualquer relação R , o fechamento transitivo de R sempre existe. Para ver isso, observe que a interseção de qualquer família de relações transitivas é novamente transitiva. Além disso, existe , pelo menos, uma relação transitória contendo R , ou seja, a uma trivial: X x X . O fecho transitória de R é então dado pela intersecção de todas as relações transitórias contendo R .

Para conjuntos finitos, podemos construir o fechamento transitivo passo a passo, começando de R e adicionando arestas transitivas. Isso dá a intuição para uma construção geral. Para qualquer conjunto X , podemos provar que o fechamento transitivo é dado pela seguinte expressão

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

onde é a i -ésima potência de R , definida indutivamente por ${\ displaystyle R ^ {i}}$

{\ displaystyle R ^ {1} = R}

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

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

onde denota composição de relações . ${\ displaystyle \ circ}$

Para mostrar que a definição acima de R ⁺ é a relação menos transitiva contendo R , mostramos que ela contém R , que é transitiva e que é o menor conjunto com ambas as características.

${\ displaystyle R \ subseteq R ^ {+}}$ : contém todos os , portanto, em particular, contém . ${\ displaystyle R ^ {+}}$ ${\ displaystyle R ^ {i}}$ ${\ displaystyle R ^ {+}}$ ${\ displaystyle R}$
${\ displaystyle R ^ {+}}$ é transitivo: Se , então e para alguns por definição de . Uma vez que a composição é associativa ,; portanto, por definição de e . ${\ 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 ^ {+}}$ é mínimo, isto é, se houver qualquer relação transitiva contendo , então : Dado qualquer um , indução em pode ser usada para mostrar para todos como segue: Base: por suposição. Etapa: Se é válido, e , então e para alguns , por definição de . Portanto, por suposição e por hipótese de indução. Conseqüentemente, por transitividade de ; isso completa a indução. Finalmente, para todos implica por definição 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 ^ {+}}$

Propriedades

A interseção de duas relações transitivas é transitiva.

A união de duas relações transitivas não precisa ser transitiva. Para preservar a transitividade, deve-se usar o fechamento transitivo. Isso ocorre, por exemplo, quando se toma a união de duas relações de equivalência ou duas pré-encomendas . Para obter uma nova relação de equivalência ou pré-ordem, deve-se tomar o fechamento transitivo (reflexividade e simetria - no caso de relações de equivalência - são automáticas).

Na teoria dos grafos

O fechamento transitivo constrói o gráfico de saída a partir do gráfico de entrada.

Na ciência da computação , o conceito de fechamento transitivo pode ser pensado como a construção de uma estrutura de dados que torna possível responder a questões de acessibilidade . Ou seja, é possível ir do nó a ao nó d em um ou mais saltos? Uma relação binária diz a você apenas que o nó a está conectado ao nó b , e que o nó b está conectado ao nó c , etc. Após o fechamento transitivo ser construído, conforme ilustrado na figura a seguir, em uma operação O (1), pode-se determine que o nó d é acessível a partir do nó a . A estrutura de dados é normalmente armazenada como uma matriz, portanto, se matriz [1] [4] = 1, então o nó 1 pode chegar ao nó 4 por meio de um ou mais saltos.

O fechamento transitivo da relação de adjacência de um grafo acíclico direcionado (DAG) é a relação de alcançabilidade do DAG e uma ordem parcial estrita .

Em complexidade lógica e computacional

O fechamento transitivo de uma relação binária não pode, em geral, ser expresso na lógica de primeira ordem (FO). Isto significa que não se pode escrever uma fórmula usando símbolos de predicados R e T que ficará satisfeito em qualquer modelo se e somente se T é o fechamento transitivo de R . Na teoria do modelo finito , a lógica de primeira ordem (FO) estendida com um operador de fechamento transitivo é geralmente chamada de lógica de fechamento transitivo e abreviada como FO (TC) ou apenas TC. TC é um subtipo de lógica de ponto fixo . O fato de FO (TC) ser estritamente mais expressivo do que FO foi descoberto por Ronald Fagin em 1974; o resultado foi então redescoberto por Alfred Aho e Jeffrey Ullman em 1979, que propôs usar a lógica de fixpoint como uma linguagem de consulta de banco de dados . Com os conceitos mais recentes da teoria do modelo finito, a prova de que FO (TC) é estritamente mais expressivo que FO segue imediatamente do fato de que FO (TC) não é local de Gaifman .

Na teoria da complexidade computacional , a classe de complexidade NL corresponde precisamente ao conjunto de sentenças lógicas expressáveis em TC. Isso ocorre porque a propriedade de fechamento transitivo tem um relacionamento próximo com o problema de NL-complete STCON para encontrar caminhos direcionados em um grafo. Da mesma forma, a classe L é lógica de primeira ordem com o fechamento transitivo comutativo. Quando o fechamento transitivo é adicionado à lógica de segunda ordem , obtemos PSPACE .

Em linguagens de consulta de banco de dados

Desde a década de 1980, o banco de dados Oracle implementou uma extensão SQL proprietária CONNECT BY... START WITHque permite o cálculo de um fechamento transitivo como parte de uma consulta declarativa. O padrão SQL 3 (1999) adicionou uma WITH RECURSIVEconstrução mais geral também permitindo que fechamentos transitivos sejam calculados dentro do processador de consulta; a partir de 2011, o último foi implementado em IBM DB2 , Microsoft SQL Server , Oracle e PostgreSQL , embora não em MySQL .

O Datalog também implementa cálculos de fechamento transitivo.

MariaDB implementa Expressões de Tabela Comuns Recursivas, que podem ser usadas para calcular fechamentos transitivos. Este recurso foi introduzido na versão 10.2.2 de abril de 2016.

Algoritmos

Algoritmos eficientes para calcular o fechamento transitivo da relação de adjacência de um grafo podem ser encontrados em Nuutila (1995). Os métodos de pior caso mais rápidos, que não são práticos, reduzem o problema à multiplicação de matrizes . O problema também pode ser resolvido pelo algoritmo Floyd – Warshall , ou por busca repetida em largura ou em profundidade a partir de cada nó do gráfico.

Pesquisas mais recentes exploraram maneiras eficientes de computar o fechamento transitivo em sistemas distribuídos com base no paradigma MapReduce .

Veja também

Relação ancestral
Fechamento dedutivo
Fechamento reflexivo
Fechamento simétrico
Redução transitiva (a menor relação tendo o fechamento transitivo de R como seu fechamento transitivo)

Referências

Lidl, R .; Pilz, G. (1998),Álgebra abstrata aplicada, Textos de Graduação em Matemática (2ª ed.), Springer, ISBN 0-387-98290-6
Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (manuscrito não publicado)
Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Teoria dos modelos finitos e suas aplicações . Springer. pp. 151-152. ISBN 978-3-540-68804-4.
Libkin, Leonid (2004), Elements of Finite Model Theory , Springer, ISBN 978-3-540-21202-7
Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Teoria do Modelo Finito (2ª ed.). Springer. pp. 123 -124, 151-161, 220-235. ISBN 978-3-540-28787-2.
Aho, AV; Ullman, JD (1979). "Universalidade das linguagens de recuperação de dados". Anais do 6º Simpósio ACM SIGACT-SIGPLAN sobre Princípios de Linguagens de Programação - POPL '79 . pp. 110–119. doi : 10.1145 / 567752.567763 .
Benedikt, M .; Senellart, P. (2011). "Bancos de dados". Em Blum, Edward K .; Aho, Alfred V. (eds.). Ciência da Computação. O hardware, o software e o coração dele . pp. 169–229. doi : 10.1007 / 978-1-4614-1168-0_10 . ISBN 978-1-4614-1167-3.
Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 páginas. Publicado pela Academia Finlandesa de Tecnologia. ISBN 951-666-451-2 , ISSN 1237-2404 , UDC 681.3.
Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Conceitos do sistema de banco de dados (6ª ed.). McGraw-Hill. ISBN 978-0-07-352332-3. Apêndice C (apenas online)
Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries , EDBT 2011, 22-24 de março de 2011, Uppsala, Suécia, ISBN 978-1-4503-0528- 0

links externos

" Fechamento e redução transitivos ", The Stony Brook Algorithm Repository, Steven Skiena.
" Apti Algoritmi ", Um exemplo e algumas implementações C ++ de algoritmos que calculam o fechamento transitivo de uma dada relação binária, Vreda Pieterse.

Languages

In other projects