Formal systems for join dependencies

We investigate whether a sound and complete formal system for join dependencies can be found. We present a system that is sound and complete for tuple generating dependencies and is strong enough to derive join dependencies from join dependencies using only generalized join dependencies in the derivation. We also present a system that sound and complete for tuple generating dependencies and is complete for extended join dependencies (which are a special case of generalized join dependencies). Finally, we construct a Gentzen-style system that is sound and complete for join dependencies. The last two systems have unbounded inference rules.

Authors

• Catriel Beeri
• Moshe Y. Vardi

Keywords

• Database
• relational model
• join dependency
• implication problem
• formal system