3
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com May 27 '13 at 5:49

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Imprecisely, Join is a bit like relational composition. Transitive closure is relational composition repeated 0 or more times.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.