Clôture transitive

Yindique que la propriété de la colonne est toujours vraie pour le terme de la ligne (tout à gauche), tandis que ✗ indique que la propriété n'est pas garantie en général (elle peut ou non être vraie). Par exemple, le fait que toute relation d'équivalence soit symétrique, mais pas nécessairement antisymétrique, est indiqué par dans la colonne « Symétrique » et ✗ dans la colonne « Antisymétrique », respectivement.

Toutes les définitions exigent tacitement que la relation homogène soit transitive : pour tout si et alors. La définition d'un terme peut nécessiter des propriétés supplémentaires qui ne sont pas répertoriées dans ce tableau. ${\displaystyle R <semantics> <mrow> <mstyle> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle R}</annotation> </semantics> </math><img src=$ ${\displaystyle a,b,c, <semantics> <mrow> <mstyle> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mi>c</mi> <mo>,</mo> </mstyle> </mrow> <annotation>{\displaystyle a,b,c,}</annotation> </semantics> </math><img src=$ ${\displaystyle aRb <semantics> <mrow> <mstyle> <mi>un</mi> <mi>R</mi> <mi>b</mi> </mstyle> </mrow> <annotation>{\displaystyle aRb}</annotation> </semantics> </math><img src=$ ${\displaystyle bRc <semantics> <mrow> <mstyle> <mi>b</mi> <mi>R</mi> <mi>c</mi> </mstyle> </mrow> <annotation>{\displaystyle bRc}</annotation> </semantics> </math><img src=$ ${\displaystyle aRc. <semantics> <mrow> <mstyle> <mi>un</mi> <mi>R</mi> <mi>c</mi> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle aRc.}</annotation> </semantics> </math><img src=$

En mathématiques , la clôture transitive R ⁺ d'une relation binaire homogène R sur un ensemble X est la plus petite relation sur X qui contient R et est transitive . Pour les ensembles finis, « le plus petit » peut être pris dans son sens habituel, celui d'avoir le moins de paires liées ; pour les ensembles infinis, R ⁺ est l'unique sur-ensemble transitif minimal de R .

Par exemple, si X est un ensemble d'aéroports et x R y signifie « il existe un vol direct de l'aéroport x à l'aéroport y » (pour x et y dans X ), alors la fermeture transitive de R sur X est la relation R ⁺ telle que x R ⁺ y signifie « il est possible de voler de x à y en un ou plusieurs vols ».

Plus formellement, la clôture transitive d'une relation binaire R sur un ensemble X est la plus petite relation transitive R ⁺ sur X telle que R ⊆ R ⁺ ; voir Lidl & Pilz (1998, p. 337). On a R ⁺ = R si, et seulement si, R est lui-même transitif.

Inversement, la réduction transitive produit une relation minimale S à partir d'une relation R donnée telle qu'elles aient la même fermeture, c'est-à-dire S ⁺ = R ⁺ ; cependant, il peut exister de nombreux S différents possédant cette propriété.

La fermeture transitive et la réduction transitive sont également utilisées dans le domaine étroitement lié de la théorie des graphes .

Relations transitives et exemples

Une relation R sur un ensemble X est transitive si, pour tout x , y , z dans X , chaque fois que x R y et y R z alors x R z . Les exemples de relations transitives incluent la relation d'égalité sur tout ensemble, la relation « inférieur ou égal » sur tout ensemble linéairement ordonné et la relation « x est né avant y » sur l'ensemble de toutes les personnes. Symboliquement, cela peut être noté comme : si x < y et y < z alors x < z .

Un exemple de relation non transitive est « la ville x peut être atteinte par un vol direct depuis la ville y » sur l'ensemble de toutes les villes. Le simple fait qu'il existe un vol direct d'une ville vers une deuxième ville, et un vol direct de la deuxième ville vers la troisième, n'implique pas qu'il existe un vol direct de la première ville vers la troisième. La clôture transitive de cette relation est une relation différente, à savoir « il existe une séquence de vols directs qui commence à la ville x et se termine à la ville y ». Chaque relation peut être étendue de manière similaire à une relation transitive.

Un exemple de relation non transitive avec une clôture transitive moins significative est « x est le jour de la semaine après y ». La clôture transitive de cette relation est « un jour x vient après un jour y sur le calendrier », ce qui est trivialement vrai pour tous les jours de la semaine x et y (et donc équivalent au carré cartésien , qui est « x et y sont tous les deux des jours de la semaine »).

Existence et description

Pour toute relation R , la clôture transitive de R existe toujours. Pour le constater, notez que l' intersection de toute famille de relations transitives est à nouveau transitive. De plus, il existe au moins une relation transitive contenant R , à savoir la relation triviale : X × X . La clôture transitive de R est alors donnée par l'intersection de toutes les relations transitives contenant R .

Pour les ensembles finis, nous pouvons construire la fermeture transitive étape par étape, en partant de R et en ajoutant des arêtes transitives. Cela donne l'intuition d'une construction générale. Pour tout ensemble X , nous pouvons prouver que la fermeture transitive est donnée par l'expression suivante

{\displaystyle R^{+}=\bigcup _{i=1}^{\infty }R^{i}. <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> <mo>=</mo> <munderover> <mo>⋃</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle R^{+}=\bigcup _{i=1}^{\infty }R^{i}.}</annotation> </semantics> </math></span><img src=

où est la i -ième puissance de R , définie inductivement par ${\displaystyle R^{i <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{i}}</annotation> </semantics> </math><img src=$

{\displaystyle R^{1}=R <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{1}=R}</annotation> </semantics> </math></span><img src=

et, pour , $0 je > 0$ 0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293">

{\displaystyle R^{i+1}=R\circ R^{i <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mi>R</mi> <mo>∘</mo> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{i+1}=R\circ R^{i}}</annotation> </semantics> </math></span><img src=

où désigne la composition des relations . ${\displaystyle \circ <semantics> <mrow> <mstyle> <mo>∘</mo> </mstyle> </mrow> <annotation>{\displaystyle \circ }</annotation> </semantics> </math><img src=$

Pour montrer que la définition ci-dessus de R ⁺ est la plus petite relation transitive contenant R , nous montrons qu'elle contient R , qu'elle est transitive et qu'elle est le plus petit ensemble avec ces deux caractéristiques.

${\displaystyle R\subseteq R^{+ <semantics> <mrow> <mstyle> <mi>R</mi> <mo>⊆</mo> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R\subseteq R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{i <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle R <semantics> <mrow> <mstyle> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle R}</annotation> </semantics> </math><img src=$
${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in R^{+ <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>,</mo> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\dans R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{2})\in R^{j <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mi>j</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{2})\dans R^{j}}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{2},s_{3})\in R^{k <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{2},s_{3})\dans R^{k}}</annotation> </semantics> </math><img src=$ ${\displaystyle j,k <semantics> <mrow> <mstyle> <mi>j</mi> <mo>,</mo> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle j,k}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{j+k}=R^{j}\circ R^{k <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>j</mi> <mo>+</mo> <mi>k</mi> </mrow> </msup> <mo>=</mo> <msup> <mi>R</mi> <mrow> <mi>j</mi> </mrow> </msup> <mo>∘</mo> <msup> <mi>R</mi> <mrow> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{j+k}=R^{j}\circ R^{k}}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{3})\in R^{j+k}\subseteq R^{+ <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mi>j</mi> <mo>+</mo> <mi>k</mi> </mrow> </msup> <mo>⊆</mo> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{3})\dans R^{j+k}\subseteq R^{+}}</annotation> </semantics> </math><img src=$ ${\displaystyle \circ <semantics> <mrow> <mstyle> <mo>∘</mo> </mstyle> </mrow> <annotation>{\displaystyle \circ }</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$
${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$ Base : par hypothèse. Étape : Si est vrai, et , alors et pour un certain , par définition de . Par conséquent, par hypothèse et par hypothèse d'induction. Par conséquent par transitivité de ; ceci achève l'induction. Enfin, pour tout implique par définition de . ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$ ${\displaystyle R <semantics> <mrow> <mstyle> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle R}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+}\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{+}\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{i}\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{i}\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{1}=R\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mi>R</mi> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{1}=R\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{i}\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{i}\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{3})\in R^{i+1}=R\circ R^{i <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mi>je</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mi>R</mi> <mo>∘</mo> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{3})\dans R^{i+1}=R\circ R^{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{2})\in R <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{2})\dans R}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{2},s_{3})\in R^{i <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle (s_{2},s_{3})\dans R^{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle s_{2 <semantics> <mrow> <mstyle> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle s_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle \circ <semantics> <mrow> <mstyle> <mo>∘</mo> </mstyle> </mrow> <annotation>{\displaystyle \circ }</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in T <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>,</mo> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\dans T}</annotation> </semantics> </math><img src=$ ${\displaystyle (s_{1},s_{3})\in T <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle (s_{1},s_{3})\dans T}</annotation> </semantics> </math><img src=$ ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{i}\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mi>je</mi> </mrow> </msup> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{i}\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+}\subseteq T <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> <mo>⊆</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle R^{+}\subseteq T}</annotation> </semantics> </math><img src=$ ${\displaystyle R^{+ <semantics> <mrow> <mstyle> <msup> <mi>R</mi> <mrow> <mo>+</mo> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle R^{+}}</annotation> </semantics> </math><img src=$

Propriétés

L' intersection de deux relations transitives est transitive.

L' union de deux relations transitives n'est pas nécessairement transitive. Pour préserver la transitivité, il faut prendre la clôture transitive. Cela se produit, par exemple, lorsqu'on prend l'union de deux relations d'équivalence ou de deux préordres . Pour obtenir une nouvelle relation d'équivalence ou un nouveau préordre, il faut prendre la clôture transitive (la réflexivité et la symétrie — dans le cas des relations d'équivalence — sont automatiques).

En théorie des graphes

La fermeture transitive construit le graphe de sortie à partir du graphe d'entrée.

En informatique , le concept de fermeture transitive peut être considéré comme la construction d'une structure de données qui permet de répondre à des questions d'accessibilité . Autrement dit, peut-on aller du nœud a au nœud d en un ou plusieurs sauts ? Une relation binaire vous indique uniquement que le nœud a est connecté au nœud b , et que le nœud b est connecté au nœud c , etc. Une fois la fermeture transitive construite, comme illustré dans la figure suivante, dans une opération O(1), on peut déterminer que le nœud d est accessible depuis le nœud a . La structure de données est généralement stockée sous forme de matrice booléenne, donc si matrix[1][4] = true, alors il est vrai que le nœud 1 peut atteindre le nœud 4 en un ou plusieurs sauts.

La fermeture transitive de la relation d'adjacence d'un graphe acyclique orienté (DAG) est la relation d'accessibilité du DAG et d'un ordre partiel strict .

Un graphe de cluster , la fermeture transitive d'un graphe non orienté

La fermeture transitive d'un graphe non orienté produit un graphe de cluster , une union disjointe de cliques . La construction de la fermeture transitive est une formulation équivalente du problème de recherche des composantes du graphe.

En logique et complexité computationnelle

La fermeture transitive d'une relation binaire ne peut pas, en général, être exprimée en logique du premier ordre (FO). Cela signifie qu'on ne peut pas écrire une formule utilisant les symboles de prédicats R et T qui sera satisfaite dans n'importe quel modèle si et seulement si T est la fermeture transitive de R. Dans la théorie des modèles finis , la logique du premier ordre (FO) étendue avec un opérateur de fermeture transitive est généralement appelée logique de fermeture transitive , et abrégée FO(TC) ou simplement TC. TC est un sous-type de logique à point fixe . Le fait que FO(TC) soit strictement plus expressive que FO a été découvert par Ronald Fagin en 1974 ; le résultat a ensuite été redécouvert par Alfred Aho et Jeffrey Ullman en 1979, qui ont proposé d'utiliser la logique à point fixe comme langage de requête de base de données . Avec des concepts plus récents de la théorie des modèles finis, la preuve que FO(TC) est strictement plus expressive que FO découle immédiatement du fait que FO(TC) n'est pas Gaifman-local.

En théorie de la complexité computationnelle , la classe de complexité NL correspond précisément à l'ensemble des phrases logiques exprimables en TC. Cela est dû au fait que la propriété de clôture transitive a une relation étroite avec le problème NL-complet STCON pour trouver des chemins orientés dans un graphe. De même, la classe L est une logique du premier ordre avec la clôture commutative et transitive. Lorsque la clôture transitive est ajoutée à la logique du second ordre , nous obtenons PSPACE .

Dans les langages de requête de base de données

Depuis les années 1980, Oracle Database a implémenté une extension SQL propriétaire CONNECT BY... START WITHqui permet le calcul d'une fermeture transitive dans le cadre d'une requête déclarative. La norme SQL 3 (1999) a ajouté une WITH RECURSIVEconstruction plus générale permettant également de calculer des fermetures transitives à l'intérieur du processeur de requêtes ; depuis 2011, cette dernière est implémentée dans IBM Db2 , Microsoft SQL Server , Oracle , PostgreSQL et MySQL (v8.0+). SQLite a publié un support pour cela en 2014.

Datalog implémente également des calculs de fermeture transitifs.

MariaDB implémente des expressions de table communes récursives, qui peuvent être utilisées pour calculer des fermetures transitives. Cette fonctionnalité a été introduite dans la version 10.2.2 d'avril 2016.

Algorithmes

Des algorithmes efficaces pour calculer la clôture transitive de la relation d'adjacence d'un graphe peuvent être trouvés dans Nuutila (1995). La réduction du problème à des multiplications de matrices d'adjacence permet d'atteindre la complexité temporelle de la multiplication de matrices , . Cependant, cette approche n'est pas pratique car les facteurs constants et la consommation de mémoire pour les graphes clairsemés sont élevés (Nuutila 1995, pp. 22–23, sect.2.3.3). Le problème peut également être résolu par l' algorithme de Floyd–Warshall dans , ou par une recherche répétée en largeur ou en profondeur à partir de chaque nœud du graphe. ${\displaystyle O(n^{2.3728596}) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>2.3728596</mn> </mrow> </msup> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle O (n ^ {2.3728596})}</annotation> </semantics> </math><img src=$ ${\displaystyle O(n^{3}) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mrow> <mn>3</mn> </mrow> </msup> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n^{3})}</annotation> </semantics> </math><img src=$

Pour les graphes orientés, l'algorithme de Purdom résout le problème en calculant d'abord son DAG de condensation et sa fermeture transitive, puis en le remontant jusqu'au graphe d'origine. Son temps d'exécution est , où est le nombre d'arêtes entre ses composantes fortement connectées . ${\displaystyle O(m+\mu n) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mi>m</mi> <mo>+</mo> <mi>μ</mi> <mi>n</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(m+\mu n)}</annotation> </semantics> </math><img src=$ ${\displaystyle \mu <semantics> <mrow> <mstyle> <mi>μ</mi> </mstyle> </mrow> <annotation>{\displaystyle \mu }</annotation> </semantics> </math><img src=$

Des recherches plus récentes ont exploré des moyens efficaces de calcul de fermeture transitive sur des systèmes distribués basés sur le paradigme MapReduce .