# Join dependency

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Join_dependency
> Markdown URL: https://mediated.wiki/source/Join_dependency.md
> Source: https://en.wikipedia.org/wiki/Join_dependency
> Source revision: 1328859961
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Database constraint}}
In [database theory](/source/database_theory), a '''join dependency''' is a constraint on the set of legal relations over a database scheme. A table <math>T</math> is subject to a join [dependency](/source/dependency_theory_(database_theory)) if <math>T</math> can always be recreated by [joining](/source/Relational_algebra) multiple tables each having a subset of the attributes of <math>T</math>. If one of the tables in the join has all the attributes of the table <math>T</math>, the join dependency is called trivial.

The join dependency plays an important role in the [fifth normal form](/source/fifth_normal_form) (5NF), also known as ''project-join normal form'', because it can be proven that if a scheme <math>R</math> is decomposed in tables <math>R_1</math> to <math>R_n</math>, the decomposition will be a [lossless-join decomposition](/source/Lossless_join_decomposition) if the legal relations on <math>R</math> are restricted to a join dependency on <math>R</math> called <math>*(R_1,R_2,\ldots,R_n)</math>.

Another way to describe a join dependency is to say that the relations in the join dependency are independent of each other.

Unlike in the case of [functional dependencies](/source/functional_dependencies), there is no [sound](/source/Soundness) and [complete](/source/Completeness_(logic)) axiomatization for join dependencies,<ref>{{cite journal|first=S. V.|last=Petrov|title=Finite axiomatization of languages for representation of system properties|journal=Information Sciences|volume=47|pages=339–372|year=1989|doi=10.1016/0020-0255(89)90006-6}}</ref> though axiomatization exist for more expressive dependency languages such as [full typed dependencies](/source/full_typed_dependencies).<ref name="Abiteboul">{{cite book|author1=Abiteboul|author2=Hull|author3=Vianu|title=Foundations of databases|date=1995 |publisher=Addison-Wesley |isbn=9780201537710 |url=https://archive.org/details/foundationsofdat0000abit|url-access=registration}}</ref>{{rp|Chapter 8}} However, implication of join dependencies is decidable.<ref  name="Abiteboul" />{{rp|Theorem 8.4.12}}

== Formal definition ==
Let <math>R</math> be a relation schema and let <math>R_1, R_2, \ldots, R_n</math> be a decomposition of <math>R</math>.

The relation <math>r(R)</math> ''satisfies'' the join dependency

: <math>*(R_1,R_2,\ldots,R_n)</math> if <math>\bowtie_{i = 1}^n \Pi_{R_i}(r) = r.</math>

A join dependency is trivial if one of the <math>R_i</math> is <math>R</math> itself.<ref>{{cite book|last=Silberschatz|first=Korth|title=Database System Concepts|edition=1st}}</ref>

2-ary join dependencies are called [multivalued dependency](/source/multivalued_dependency) as a historical artifact of the fact that they were studied before the general case. More specifically if ''U'' is a set of attributes and ''R'' a relation over it, then ''R'' satisfies <math>X \twoheadrightarrow Y</math> [if and only if](/source/if_and_only_if) ''R'' satisfies <math>*(X\cup Y, X\cup(U-Y)).</math>

== Example ==
Given a pizza-chain that models purchases in table Order = {order-number, customer-name, pizza-name, courier}.
The following relations can be derived:
* customer-name depends on order-number
* pizza-name depends on order-number
* courier depends on order-number
Since the relationships are independent there is a join dependency as follows: *((order-number, customer-name), (order-number, pizza-name), (order-number, courier)).

If each customer has his own courier however, there can be a join-dependency like this: *((order-number, customer-name), (order-number, pizza-name), (order-number, courier), (customer-name, courier)), 
but *((order-number, customer-name, courier), (order-number, pizza-name)) would be valid as well. This makes it obvious that just having a join dependency is not enough to normalize a database scheme.

==See also==
* [Chase (algorithm)](/source/Chase_(algorithm))
* [Universal relation assumption](/source/Universal_relation_assumption)

== References ==
{{Reflist}}

{{Database normalization}}

Category:Database normalization

---
Adapted from the Wikipedia article [Join dependency](https://en.wikipedia.org/wiki/Join_dependency) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Join_dependency?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.