Transitive Relation과 Transitive Closure

\(a > b\) && \(b > c\Rightarrow a > c\)는 당연해 보인다.

그러나 가위바위보(rock-paper-scissors)를 생각해 보자.

R beats S && S beats P \(\nrightarrow\) R beats P

이런 cyclic한 경우는 intransitive한 예이다.

한편, transitive closure라는 걸 생각할 수 있는데, 예를 들면 이런 것이다.

(조선 왕조의) 세종 전의 왕은 태종, 태종 전의 왕은 정종, 정종 전의 왕은 태조이다.

• 태조, 정종, 태종 모두 세종보다 선대의 왕이다.
• 태조, 정종 모두 태종보다 선대의 왕이다.
• 태조는 정종보다 선대의 왕이다.

집합 연산에서 포함 관계는 일종의 transitive closure이다.

\(A\subset B\)
\(B\subset C\)
\(\Rightarrow A\subset C\)

스키마가 고정되어있지 않은 어떤 DB에서 transitive relation을 설정하는 기능이 없다면
1) 필요한 edge가 만들어지지 않을 것이다.
2) 자동으로 만들어준다면 edge 수가 마구 늘어날 것이다.

Transitive relation으로 설정하고 edge를 따로 만들지 않는다면 검색 시간은 더 걸릴 것이다. 그러나 transitive closure를 구하는 효율적인 방법이 있다(...고 한다.).

Transitive closure table을 별도로 두든가...
stackoverflow.com/tags/transitive-closure-table/info

이 글을 쓴 이유

블로그 포스트에 태그를 백날 달아 봤자, transitive closure를 찾아주지 않으면 소용이 없다는 생각이 들었는데(예를 들어 이 포스트를 discrete math로 찾으면 검색되고, math로 찾으면 검색되지 않는다면 문제다!) transitive라는 단어가 떠오르지 않았다.

생각 난 김에 더 쓰면
역, 이, 대우는 영어로 각각 converse, inverse, contrapositive이다.
Contraposition은 contrapositive가 logically equivalent하다는 법칙을 가리킨다.

교환법칙commutative, 결합법칙associative, 분배법칙distributive law

더 보기:

Reflexive relation: \(\forall x \in\) A, x R x \(\Leftrightarrow\) R is reflexive on A.

• \(\le\)는 reflexive하지만 <는 not reflexive하다.