경과적 폐쇄

수학에서, 집합 X에 대한 이항 관계 R의 전이적 폐쇄는 R을 포함하고 있고 전이적인 X에 대한 가장 작은 관계이다.유한 집합의 경우, "가장 작은"은 가장 적은 관련 쌍을 갖는 일반적인 의미로 받아들여질 수 있다. 무한 집합의 경우 R의 고유한 최소 전이 슈퍼 집합이다.

예를 들어, X가 공항 집합이고 x R y가 "공항 x에서 공항 y까지 직항 비행이 있다"를 의미한다면(X의 x와 y의 경우), X에⁺ 대한 R의 전이적 폐쇄는 "하나 이상의 비행에서 x에서 y로 비행할 수 있다"는 것을 의미하므로 X에 대한 R의 관계이다⁺.비공식적으로, 전환 폐쇄는 모든 시작 위치에서 도달할 수 있는 모든 장소의 집합을 제공합니다.

좀 더 형식적으로, 집합 X에서 이항 관계 R의 전이 폐쇄는 집합 X에서의 전이 관계⁺ R이며, 따라서⁺ R은 R을 포함하고⁺ R은 최소이다. Lidl & Pilz(1998, 페이지 337)를 참조한다.2진수 관계 자체가 추이적인 경우, 추이적 폐쇄는 동일한 2진수 관계이며, 그렇지 않은 경우 추이적 폐쇄는 다른 관계입니다.

반대로, 추이적 감소는 주어진 관계 R로부터 최소한의 관계 S를 도출하여 같은 폐쇄, 즉 S⁺ = R을⁺ 가지지만, 이 성질을 가진 많은 다른 S가 존재할 수 있다.

추이적 폐쇄와 추이적 감소는 그래프 이론의 밀접한 관련 영역에서도 사용된다.

추이적 관계 및 예

X의 모든 x, y, z에 대해 X의 모든 x, y, z에 대해 x R y 및 y R z가 그 다음에 x R z일 때 Transitional이다.transitional 관계의 예로는 임의의 집합에서의 등식 관계, 임의의 선형 순서 집합에서의 "미만" 관계, 그리고 모든 사람들의 집합에서 "x는 y보다 먼저 태어났다" 관계가 있다.심볼적으로는 x < y 및 y < z이면 x < z로 나타낼 수 있습니다.

비전이 관계의 한 예는 모든 도시 집합에서 "도시 x는 도시 y에서 직접 비행으로 도달할 수 있다"이다.단순히 한 도시에서 두 번째 도시로 가는 직항편과 두 번째 도시에서 세 번째 도시로 가는 직항편이 있다고 해서 첫 번째 도시에서 세 번째 도시로 가는 직항편이 있다는 것을 의미하지는 않는다.이 관계의 과도적 폐쇄는 다른 관계, 즉 "도시 x에서 시작해서 도시 y에서 끝나는 일련의 직항 비행이 있다"이다.모든 관계는 추이적 관계와 유사한 방식으로 확장될 수 있습니다.

덜 의미 있는 전이 폐쇄를 갖는 비전이 관계의 예로는 "x는 y 이후의 요일"이 있습니다.이 관계의 추이적 종결은 "일정 x가 달력에서 y일 후에 온다"이며, 이는 x와 y의 모든 요일에 대해 3차적으로 적용된다(따라서 "x와 y는 둘 다 요일"인 데카르트 사각형에 해당한다).

존재와 설명

모든 관계 R에 대해 R의 전이적 폐쇄가 항상 존재합니다.이를 확인하려면 모든 전이 관계군의 교차점이 다시 전이적이라는 점에 유의하십시오.또한 R을 포함한 적어도 하나의 전이관계, 즉 X×X가 존재한다.R의 전이적 폐쇄는 R을 포함하는 모든 전이적 관계의 교차점에 의해 주어진다.

유한 집합의 경우 R부터 시작하여 전이 에지를 추가하는 단계별로 전이 클로저를 구성할 수 있습니다.이것은 일반적인 구성에 대한 직감을 준다.임의의 집합 X에 대해, 우리는 다음 식에 의해 과도 폐쇄가 주어진다는 것을 증명할 수 있다.

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

${\displaystyle {여기}^{}}$서 Ri$(\$ R$^{i})$는 R의 i번째 거듭제곱으로 다음과 같이 정의됩니다.

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

i> < $displaystyle$ i $> 0$의 는,

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

여기서 $"\displaystyle\display"$는 관계의 구성을 나타냅니다.

위의 R의 정의가⁺ R을 포함하는 최소 전이 관계임을 보여주기 위해 R이 포함되고, R이 전이적이며, 두 특성을 모두 가진 최소 집합임을 나타냅니다.

• ${\displaystyle R}$ +${\displaystyle {}^{}}$+ ${\$R\$subseteq$ R$^\{+\}$ :${\displaystyle {}^{}}R{\displaystyle {}^{}}$ +$${\$displaystyle$ $R^{+}$ 에는 R$$ {\$displaystyle$ R$^{+}$ 가$$ 모두 포함되어 있습니다.$따라서{\displaystyle {}^{}}$ 특히$$R +${\displaystyle {}^{}}${\$displaystyle$ R$^{+}}$$$에는$$R {\$displaystyle$ R$\}$ 가 $포함$되어 있습니다.
• ${\displaystyle R^{}}$ {\$displaystyle$ R$^{+}$ 은$$ transitionive 입니다.${\displaystyle {}^{}}{\displaystyle }$경우 ( s${\displaystyle {}_{}{}_{}}$, ${\displaystyle {}_{}{}_{}}$2${\displaystyle ),}$ ( ${\displaystyle {s\mathrm{}}_{}}$2, $s$)${\displaystyle {+}^{}}$R + ($s$_ { { s _ { s _ {$}$ ), ( ${\displaystyle {s\_\mathrm{}}_{}}$${2$}$)\$$in$ $R$ ( ${\displaystyle {}_{}}$ 1, ${\displaystyle {s\mathrm{}}_{}}$2${\displaystyle }$)${\displaystyle r^{}}$R $jdisplay style$ ( s $_$ { { s$$_ { { 1$$} )${\displaystyle }$${\displaystyle j^{}}$${\displaystyle ,}$ $($$R$$$ {\$displaystyle$$$R$^\{+\}\})$의 $정의상{\displaystyle {}^{}}$ r${\displaystyle {,}^{}}$ $k(\$${\displaystyle {displaystyle}^{}}$ R^{$j+k$}) $= R^{$j}(\displaystyle $R^{k$${\displaystyle }$${\displaystyle {}^{}}$ R^{j}\$circ$ R$+$ ${\displaystyle {3\mathrm{}}_{})}$ ${\displaystyle {}^{}}$ 。$isplaystyle \circ }$ $및$ R$$+ {\$displaystyle$ R$^\{+\}\}$ 입니다.
• ${\displaystyle R^{}}$+ {\$displaystyle$ R$^{+}$은 최소입니다.즉$,$ T(\$displaystyle$ T$)$가 R$(\$$displaystyle$$$R$^\{+\}\backslash$$subseteq$ T$)$을 $포함$하는 전이 관계인 $경우{\displaystyle {}^{}}$, R${\displaystyle {}^{}}$+$$ T(\$displaystyle$ R$^{+}\$subseteq T$):$ 이러한 $(\$$displaystyle$ I$)$를 $사용$하여 표시할 수 있습니다${\displaystyle {}^{}}$$모든$ $i{\displaystyle }$$(\$displaystyle$$ i)에 $대해$ yle R$^{$$i}\subseteq$T를$$ 가정하면 다음과 같습니다. 베이스: ${\displaystyle {R\mathrm{}}^{}}$ 1 ${\displaystyle {}^{}}$ ${\displaystyle Rt}$T \ $displaystyle$ R$^{1$} =$R\subseteq$ T$$$$}스텝: ${\displaystyle R^{}}$ i${\displaystyle {}^{}t}$T {\$displaystyle$$$R$^{i}\subseteq T}$가 유지되고 $({\displaystyle {}_{}{}_{}}$1, s${\displaystyle {}_{}{3\mathrm{}}_{}}$)$$ ${\displaystyle R^{}{}^{}}$i + ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle R{}^{}}$ R$$i ( $s_{1}, s_{$3}\$in$ R^ {$i+1$} = R\$cirC ^{$i$\})$가 $유지$되면 s${\displaystyle {}_{}}$ s, s, s.$me{\displaystyle {}_{}}$ $({$$s_$${2$$\}\})$는${\displaystyle }$§$$(${\displaystyle {}_{}}$ 1,${\displaystyle {}_{}}$s${\displaystyle {}_{}{2\mathrm{}}_{}}$ ${\displaystyle ),}$ (${\displaystyle {}_{}{}_{}}$2, s ${\displaystyle {3\mathrm{}}_{}}$의 정의에 의해 정의됩니다${\displaystyle .}$따라서${\displaystyle }$가정 및 유도 가설에 의해 T$(s_{1}, s_${2$}),$ \displaystyle$$$(s_{$2}, $s_{3})\in$ T$.$따라서${\displaystyle }$( ${\displaystyle {s\mathrm{}}_{}{}_{}}$ ,${\displaystyle {}_{}{s\mathrm{}}_{}}$ 3 )${\displaystyle }$$t{\displaystyle }$$$T \ $displaystyle$ ($s$_ {$1}$ , s _ {3} \ $in$ T$$by$$ T$$、 T \ $displaystyle$$$T$$） 。이것으로 인덕션이 완료됩니다.마지막으로 모든$i$에 ${\displaystyle {대한}^{}}$ R i${\displaystyle {}^{}t}$T { \ $display$ $style$$R$^ {$$i$$$\}$ \ $subseteq$ T$$}는 R$$+$$${\displaystyle {+}^{}}$ T { display $style$ R$^$ { + } \ $subseteq$T 를 $의미$합니다.

특성.

두 과도 관계의 교차점은 타동적이다.

두 과도관계의 결합은 과도적일 필요는 없다.이동성을 유지하기 위해서는 과도적 폐쇄를 택해야 한다.예를 들어, 2개의 동등성 관계 또는 2개의 예약 주문을 결합할 때 이 문제가 발생합니다.새로운 동등성 관계 또는 사전 순서를 얻으려면 전이적 폐쇄를 취해야 합니다(등가 관계의 경우 반사성과 대칭성은 자동입니다).

그래프 이론에서

컴퓨터 과학에서 과도적 폐쇄의 개념은 도달 가능성 질문에 대답할 수 있는 데이터 구조를 구성하는 것으로 간주할 수 있다.즉, 노드a에서 노드d에 1개 이상의 홉으로 도달할 수 있습니까?바이너리 관계에서는 노드 a가 노드 b에 접속되어 노드 b가 노드 c 등에 접속되어 있는 것만을 알 수 있습니다.다음 그림에 나타낸 것과 같이 전이폐쇄가 구성된 후 O(1) 동작에서는 노드 d가 노드 a에서 도달 가능하다고 판단할 수 있다.데이터 구조는 일반적으로 행렬로 저장되므로 행렬 [1][4] = 1이면 노드 1이 하나 이상의 홉을 통해 노드 4에 도달할 수 있습니다.

Directed Acyclic Graph(DAG; 유도 비순환 그래프) 인접 관계의 전이적 폐쇄는 DAG의 도달 가능성 관계와 엄밀한 부분 순서입니다.

무방향 그래프의 전이적 닫힘은 클러스터 그래프를 생성합니다. 클러스터 그래프는 분리 결합입니다.과도적 폐쇄를 구성하는 ^[1]것은 그래프의 성분을 찾는 문제에 대한 동등한 공식입니다.

로직과 계산의 복잡성

이항 관계의 전이적 폐쇄는 일반적으로 1차 논리(FO)로 표현할 수 없습니다.즉, T가 R의 전이적 폐쇄인 경우에만 모든 모형에서 만족할 수 있는 술어 기호 R과 T를 사용하여 공식을 작성할 수 없습니다.유한 모델 이론에서, 전이적 폐쇄 연산자와 함께 확장된 1차 논리(FO)는 보통 전이적 폐쇄 논리라고 불리며, 약어 FO(TC) 또는 단순한 TC로 불린다.TC는 고정점 로직의 하위 유형입니다.FO(TC)가 FO보다 훨씬 표현력이 뛰어나다는 사실은 1974년 Ronald Fagin에 의해 발견되었고, 그 결과는 1979년 Alfred Aho와 Jeffrey Ulman에 의해 재발견되었으며, 그는 데이터베이스 쿼리 ^[2]언어로 고정점 논리를 사용할 것을 제안했다.유한 모델 이론의 보다 최근의 개념으로, FO(TC)가 FO보다 엄격히 더 표현적이라는 증거는 FO(TC)가 ^[3]게이프만-국소적이지 않다는 사실로부터 바로 뒤따른다.

계산 복잡도 이론에서 복잡도 클래스 NL은 TC에서 표현 가능한 논리 문장의 집합과 정확히 일치합니다.이는 과도적 폐쇄 속성이 그래프에서 방향 경로를 찾기 위한 NL-완전 문제 STCON과 밀접한 관계가 있기 때문입니다.마찬가지로 클래스 L은 가환성, 전이성 폐쇄를 갖는 1차 논리입니다.대신 2차 로직에 전이 폐쇄가 추가되면 PSPACE를 얻을 수 있습니다.

데이터베이스 쿼리 언어

1980년대 이후 Oracle Database는 독자적인 SQL 확장을 구현하고 있습니다.CONNECT BY... START WITH선언적 쿼리의 일부로 전이적 닫힘을 계산할 수 있습니다.SQL 3(1999) 표준은 보다 일반적인 기능을 추가했습니다.WITH RECURSIVE또한 Query Processor 내부에서 과도적 폐쇄를 계산할 수 있도록 구축합니다. 2011년 현재 Query Processor는 IBM Db2, Microsoft SQL Server, Oracle, Postgre에 구현되어 있습니다.SQL 및 MySQL(v8.0+).

데이터로그는 또한 과도 폐쇄 ^[4]계산을 구현합니다.

MariaDB는 전이적 폐쇄를 계산하는 데 사용할 수 있는 재귀적 공통 테이블 식을 구현합니다.이 기능은 2016년 ^[5]4월 릴리즈 10.2.2에서 도입되었습니다.

알고리즘

그래프의 인접관계 전이폐쇄를 계산하기 위한 효율적인 알고리즘은 Nuutila(1995)에서 찾을 수 있다.인접 행렬의 곱셈으로 문제를 줄이면 행렬 곱셈의 복잡성이 최소가^{[citation needed]} 된다. (Munro 1971, Fischer & Meyer 1971 harvnb 오류: no target: CITREFFischerMeyer1971 (도움말), 2020년$$ 12월^[update] O$(n 2.3728596)$에 해당한다.)그러나, 이 접근방식은 상수 인자와 희박한 그래프에 대한 메모리 소비가 모두 높기 때문에 실용적이지 않다. (Nuutila 1995, 페이지 22-23, 제2.3.3장)이 문제는 Floyd-Warshall 알고리즘이나 그래프의 각 노드에서 시작하는 폭 우선 검색 또는 깊이 우선 검색을 반복하여 해결할 수도 있습니다.

보다 최근의 연구는 MapReduce ^[6]패러다임을 기반으로 분산 시스템에서 효율적인 과도적 폐쇄 계산 방법을 모색하고 있습니다.

「 」를 참조해 주세요.

• 조상 관계
• 연역마감
• 재귀적 폐쇄
• 대칭 폐쇄
• 전이적 감소(R의 전이적 폐쇄를 전이적 폐쇄로 하는 최소 관계)

레퍼런스

• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D.Ulman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, 2011년 3월 22-24일, 스웨덴, 웁살라, ISBN 978-1-4503-0528-0
• Aho, A. V.; Ullman, J. D. (1979). "Universality of data retrieval languages". Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages - POPL '79. pp. 110–119. doi:10.1145/567752.567763.
• Benedikt, M.; Senellart, P. (2011). "Databases". In Blum, Edward K.; Aho, Alfred V. (eds.). Computer Science. The Hardware, Software and Heart of It. 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). Finite Model Theory (2nd ed.). Springer. pp. 123–124, 151–161, 220–235. ISBN 978-3-540-28787-2.
• M.J. Fischer and A.R. Meyer (Oct 1971). "Boolean matrix multiplication and transitive closure" (PDF). In Raymond E. Miller and John E. Hopcroft (ed.). Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Computer Society. pp. 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). Finite Model Theory and Its Applications. Springer. pp. 151–152. ISBN 978-3-540-68804-4.
• Keller, U.S., 2004, 1차 로직 및 데이터로그에서의 과도적 폐쇄의 정의에 관한 일부 발언(미공개 원고)*
• Lidl, R.; Pilz, G. (1998), Applied abstract algebra, Undergraduate Texts in Mathematics (2nd ed.), Springer, ISBN 0-387-98290-6
• Munro, Ian (Jan 1971). "Efficient determination of the transitive closure of a directed graph". Information Processing Letters. 1 (2): 56–58. doi:10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995). Efficient transitive closure computation in large digraphs. Finnish Academy of Technology. ISBN 951-666-451-2. OCLC 912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th ed.). McGraw-Hill. ISBN 978-0-07-352332-3. 부록 C(온라인만)

외부 링크

• Stony Brook 알고리즘 저장소, Steven Skiena.