7.40

Given a relational schema \(r(A,B,C,D)\), does \(A \twoheadrightarrow BC\) logically imply \(A \twoheadrightarrow B\) and \(A \twoheadrightarrow C\)? If yes prove it, or else give a counter example.

No. That is \(A \twoheadrightarrow BC\) does not logically imply \(A \twoheadrightarrow B\) and \(A \twoheadrightarrow C\).

It is clear that the multivalued dependency \(A \twoheadrightarrow BC\) holds on the following instance of \(r\).

A B C D
1 3 7 2
1 6 4 5
1 3 7 5
1 6 4 2

The following Python3 code verifies exactly just that (in fact it does more than that).

from typing import List, Set, Tuple

def tuple_over_set_equality_checker(t1: Tuple, t2: Tuple, t3: Tuple, t4: Tuple, s: Set[int]) -> bool:
    for i in s:
        if not (t1[i] == t2[i] == t3[i] == t4[i]):
            return False
    return True

class Solution: 
    def __init__(self, doesTheMultivaluedDependencyHold=True, t1=tuple(), t2=tuple()): 
        '''
        t1 and t2 are only meaningful if the parameter 
        doesTheMultivaluedDependencyHold is False. That is 
        if the multivalued dependency does not hold, then t1 and 
        t2 represent tuples in the instance of the relation that don't 
        have corresponding t3 and t4 to satisfy the definition of the 
        multivalued dependency.  
        '''
        self.doesTheMultivaluedDependencyHold = doesTheMultivaluedDependencyHold
        self.t1 = t1
        self.t2 = t2
    
    def __str__(self): 
        if self.doesTheMultivaluedDependencyHold: 
            return 'Multivalued Dependency holds!! ๐Ÿ‘๐Ÿ‘'
        else: 
            return 'Multivalued Dependency does NOT hold ๐Ÿ˜ฅ๐Ÿ˜”\n' \
            'Problem causing tuples are \n\t t1: {} \n\t t2: {}'.format(self.t1, self.t2)
        
def multivalued_dependency_checker(r: List[Tuple], R: Set[int], alpha: Set[int], beta: Set[int]) -> bool:
    '''
    r: is the instance of the relation. It is basically 
    a list of the tuples, where each tuple represents 
    a row inside of the relation. 

    R: the schema. Is the set of integers to indicate the attributes. 
    It usually includes numbers from 0 upto n, where n is 
    some natural number.

    We are testing the multivalued dependency alpha ->-> beta.
    alpha and beta are subsets of R. 
    '''
    R_minus_beta = R - beta
    number_of_attributes = len(r[0])

    for i in range(0, len(r)):
        for j in range(i+1, len(r)):
            t1 = r[i]
            t2 = r[j]

            # build t3
            t3 = [0] * number_of_attributes

            # since t3[beta] is equal to t1[beta]
            for k in beta:
                t3[k] = t1[k]

            # also t3[R - beta] = t2[R - beta]
            for k in R_minus_beta:
                t3[k] = t2[k]

            # build t4
            t4 = [0] * number_of_attributes

            # since t4[beta] is equal to t2[beta]
            for k in beta:
                t4[k] = t2[k]
            
            # since t4[R - beta] is equal to t1[R - beta]
            for k in R_minus_beta:
                t4[k] = t1[k]
            
            if (not tuple_over_set_equality_checker(t1, t2, t3, t4, alpha)): 
                return Solution(False, t1, t2)
            
            t3 = tuple(t3)
            t4 = tuple(t4)
            
            if (t3 in r) and (t4 in r): 
                # all is good
                pass 
            else: 
                return Solution(False, t1, t2)
    return Solution(True)


if __name__ == '__main__':
    print(multivalued_dependency_checker(
        [
            (1, 3, 7, 2),
            (1, 6, 4, 5),
            (1, 3, 7, 5),
            (1, 6, 4, 2),
        ], # the relation
        {0, 1, 2, 3}, # the schema
        {0,}, # alpha
        {1,2}, # beta
    ))

However, the multivalued dependency \(A \twoheadrightarrow B\) does NOT hold.

The following explanation shows it does not hold.

Now letโ€™s assume to the contrary that the multivalued dependency \(A \twoheadrightarrow B\) holds.

Take \(t_1 = (1, 3, 7, 2)\) and \(t_2 = (1, 6, 4, 5)\).

Note that the first component of \(t_1\) is value of attribute \(A\), the second component of \(t_1\) is value of attribute \(B\) and so on. Similarly for \(t_2\).

Since the multivalued dependency \(A \twoheadrightarrow B\) holds we know that there exist tuples \(t_3\) and \(t_4\) in \(r\) satisfying the conditions of the definition of multivalued dependency. Take \(\alpha := \{A\}\) and \(\beta := \{B\}\). Then \(R - \beta = \{A, C, D\}\).

We know that \(t_3[\beta] = t_1[\beta]\).

\(t_1[\beta] = t_1[\{B\}] = 3\)

Thus we know the value of the attribute \(B\) in tuple \(t_3\), it is \(3\).

We also know that \(t_3[R - \beta] = t_2[R - \beta]\).

\(t_2[R - \beta] = t_2[\{A, C, D\}] = (1, 4, 5)\)

Thus we know the value of the attributes \((A,C,D)\) of tuple \(t_3\), they are \((1, 4, 5)\).

Putting our results together, we get \(t_3 = (1, 3, 4, 5)\).

But we see that the tuple \(t_3\) doesnโ€™t belong to the instance of \(r\) that we took.

Thus the multivalued dependency \(A \twoheadrightarrow B\) DOES NOT hold.

Therefore, \(A \twoheadrightarrow BC\) DOES NOT logically imply \(A \twoheadrightarrow B\) and \(A \twoheadrightarrow C\).