Project 2 Functional Dependencies and Normalisation Solution

In this project, we use Python 3.8. Use the Python le \project2.py" from Luminus les to answer the questions. You may add additional functions to help you answer the questions. However, do not change the name and the parameters of the given functions in the template le. You may import additional Python standard libraries (e.g itertools, copy) but not external libraries.

For all questions, we use the following representations. The schema is represented as a Python list of non-empty strings. For example, the schema fA; B; C; Dg is represented as [’A’, ’B’, ’C’, ’D’]. Even though it is represented as a list, the order of the elements in the list does not matter and it must have unique elements. A functional dependency is represented as a list of two lists. The order of the two elements matters. For example, the functional dependency fABg ! fCg is represented as [[’A’, ’B’], [’C’]]. A set of functional dependencies is a list of functional dependencies. The order of the functional dependencies does not matters.

You may assume that the input to the questions is always valid (e.g. no empty string, no incomplete functional dependency). You do not need to validate the input. The code should be readable and commented properly.

Question 1 [3 marks]

1. Write a function closure that takes three parameters: a schema, a set of functional dependen-cies and a set of attributes, which is the subset of the schema, and returns the closure of the set of attributes.

For example, the attribute closure of fA; Bg, fA; Bg⁺ = fA; B; C; Dg,

closure([’A’, ’B’, ’C’, ’D’], [[[’A’, ’B’], [’C’]], [[’C’], [’D’]]], [’A’, ’B’])

• [’A’, ’B’, ’C’, ’D’]

CS4221/CS5421

1. Write a function all closures that takes two parameters, a schema and a set of functional dependencies, and returns the closure of all subsets of attributes excluding super keys that are not candidate keys. The results is represented as a list of functional dependencies of the form S ! S⁺ where S is a subset of attributes.

For example,

all_closures([’A’, ’B’, ’C’, ’D’], [[[’A’, ’B’], [’C’]], [[’C’], [’D’]]])

• [[[’A’], [’A’]], [[’B’], [’B’]], [[’C’], [’C’, ’D’]], [[’D’], [’D’]], [[’A’, ’B’], [’A’, ’B’, ’C’, ’D’]], [[’A’, ’C’], [’A’, ’C’, ’D’]], [[’A’, ’D’], [’A’, ’D’]], [[’B’, ’C’], [’B’, ’C’, ’D’]],

[[’B’, ’D’], [’B’, ’D’]], [[’C’, ’D’], [’C’, ’D’]], [[’A’, ’C’, ’D’], [’A’, ’C’, ’D’]], [[’B’, ’C’, ’D’], [’B’, ’C’, ’D’]]]

Question 2 [7 marks]

1. Write a function min cover that takes two parameters, a schema and a set of functional depen-dencies, and returns a minimal cover of the functional dependencies. The results is represented as a list of functional dependencies.

For example,

min_cover([’A’, ’B’, ’C’, ’D’, ’E’, ’F’],

[[[’A’], [’B’, ’C’]],[[’B’], [’C’,’D’]], [[’D’], [’B’]], [[’A’,’B’,’E’], [’F’]]])

• [[[’A’], [’B’]], [[’B’], [’C’]], [[’B’], [’D’]], [[’D’], [’B’]], [[’A’, ’E’], [’F’]]]

There might be more than one correct answer to this question.

1. Write a function min covers that takes two parameters, a schema and a set of functional dependencies, and returns all minimal covers reachable from the set of functional dependencies. The results is represented as a list of minimal covers. Make sure that you clearly explained the rationale of the algorithm for this question in the indicated comment section in the code.

For example,

min_covers([’A’, ’B’, ’C’], [[[’A’], [’B’]],[[’B’], [’C’]], [[’C’], [’A’]]])

• [[[[’A’], [’B’]], [[’B’], [’C’]], [[’C’], [’A’]]]]

For the case above, we nd only one minimal cover.

1. Write a function all min covers that takes two parameters, a schema and a set of functional dependencies, and returns all minimal covers. The results is represented as a list of minimal covers. Make sure that you clearly explained the rationale of the algorithm for this question in the indicated comment section in the code.

For example,

min_covers([’A’, ’B’, ’C’], [[[’A’], [’B’]],[[’B’], [’C’]], [[’C’], [’A’]]]) = [

[[[’A’], [’C’]], [[’B’], [’A’]], [[’C’], [’A’]], [[’A’], [’B’]]],

[[[’B’], [’C’]], [[’C’], [’A’]], [[’A’], [’B’]]],

[[[’C’], [’B’]], [[’A’], [’C’]], [[’C’], [’A’]], [[’B’], [’C’]]],

[[[’C’], [’B’]], [[’A’], [’C’]], [[’B’], [’A’]]],

[[[’B’], [’C’]], [[’A’], [’B’]], [[’B’], [’A’]], [[’C’], [’B’]]]

]

For the case above, we nd ve minimal covers.