Join dependency

<h2 id="formal-definition">Formal definition</h2>
<p>Let 
  
    
      
        R
      
    
    {\displaystyle R}
  
 be a relation schema and let 
  
    
      
        
          R
          
            1
          
        
        ,
        
          R
          
            2
          
        
        ,
        …
        ,
        
          R
          
            n
          
        
      
    
    {\displaystyle R_{1},R_{2},\ldots ,R_{n}}
  
 be a decomposition of 
  
    
      
        R
      
    
    {\displaystyle R}
  
.
</p><p>The relation 
  
    
      
        r
        (
        R
        )
      
    
    {\displaystyle r(R)}
  
 <i>satisfies</i> the join dependency
</p>

∗
        (
        
          R
          
            1
          
        
        ,
        
          R
          
            2
          
        
        ,
        …
        ,
        
          R
          
            n
          
        
        )
      
    
    {\displaystyle *(R_{1},R_{2},\ldots ,R_{n})}
  
 if 
  
    
      
        
          ⋈
          
            i
            =
            1
          
          
            n
          
        
        
          Π
          
            
              R
              
                i
              
            
          
        
        (
        r
        )
        =
        r
        .
      
    
    {\displaystyle \bowtie _{i=1}^{n}\Pi _{R_{i}}(r)=r.}

<p>A join dependency is trivial if one of the 
  
    
      
        
          R
          
            i
          
        
      
    
    {\displaystyle R_{i}}
  
 is 
  
    
      
        R
      
    
    {\displaystyle R}
  
 itself.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>2-ary join dependencies are called <a href="/facts/Multivalued_dependency/a9b3na1u">multivalued dependency</a> as a historical artifact of the fact that they were studied before the general case. More specifically if <i>U</i> is a set of attributes and <i>R</i> a relation over it, then <i>R</i> satisfies 
  
    
      
        X
        ↠
        Y
      
    
    {\displaystyle X\twoheadrightarrow Y}
  
 <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> <i>R</i> satisfies 
  
    
      
        ∗
        (
        X
        ∪
        Y
        ,
        X
        ∪
        (
        U
        −
        Y
        )
        )
        .
      
    
    {\displaystyle *(X\cup Y,X\cup (U-Y)).}

</p>
<h2 id="example">Example</h2>
<p>Given a pizza-chain that models purchases in table Order = {order-number, customer-name, pizza-name, courier}.
The following relations can be derived:
</p>
<ul><li>customer-name depends on order-number</li>
<li>pizza-name depends on order-number</li>
<li>courier depends on order-number</li></ul>
<p>Since the relationships are independent there is a join dependency as follows: *((order-number, customer-name), (order-number, pizza-name), (order-number, courier)).
</p><p>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.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Chase_(algorithm)/JfTgn5nt">Chase (algorithm)</a></li>
<li><a href="/facts/Universal_relation_assumption/52jzHj4Y">Universal relation assumption</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Petrov, S. V. (1989). "Finite axiomatization of languages for representation of system properties". Information Sciences. 47: 339–372. doi:10.1016/0020-0255(89)90006-6. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Abiteboul; Hull; Vianu (1995). Foundations of databases. Addison-Wesley. ISBN 9780201537710. <a href="9780201537710" target="_blank">9780201537710</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Abiteboul; Hull; Vianu (1995). Foundations of databases. Addison-Wesley. ISBN 9780201537710. <a href="9780201537710" target="_blank">9780201537710</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Silberschatz, Korth. Database System Concepts (1st ed.). <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Join dependency open-in-new

Join dependency