In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
No, it is not. Transitive closure is the closure of composition on binary relations; composition can be expressed as a rename (to make join operate on the right attributes), followed by a join, followed by a project to remove the common attributes.
So composition can be expressed in terms of join, but (as Erwin Smout says) its transitive closure can not, and join (or composition) cannot be expressed in terms of transitive closure, either.
answered May 27, 2013 at 7:47
$\begingroup$
$\endgroup$
Imprecisely, Join is a bit like relational composition. Transitive closure is relational composition repeated 0 or more times.
answered May 27, 2013 at 7:45
$\begingroup$
$\endgroup$
Transitive closure of relations wasn't even part of Codd's algebra, while join indeed was, eurhm, sort of.
Transitive closure necessarily involves recursion, which takes its logical equivalent outside the realm of first-order predicate logic. That's why Codd's algebra was eventually demonstrated "expressively incomplete", why recursive querying was added so belatedly in the SQL standard, and why many courses even to this very day completely overlook the issue.
Join has none of that. Plus, transitive closure, eurhm, well, all versions I am personally aware of, operates on one single relation specifically. Join is not so constrained. Hence, there are joins that are not expressible as transitive closures, and join cannot possibly be a "special case" of TC.
