-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNF3decomp.py
126 lines (105 loc) · 4.36 KB
/
NF3decomp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
# CMPUT 291 - Mini Project 2
# Author: Daniel Zhou
# November 2016
import itertools
from closure import *
#===============================================================================
# NF3 performs the third normal form decomposition. It requires the list of
# functional dependencies from some source.
#
# If in the event some attribute is not connected to any functional dependency
# then it is not captured by the function. Presumably these can be added to the
# relation containing the super key
#
# Input Format:
# Functional Dependneces should be converted into the following format.
#
# For example:
# T = [("ABH","CK"),("A","D"),("C","E"),("BGH","F"),("F","AD"),("E","F"),("BH","E")]
# NF3decomp(T)
#
# The input is a list containing set elements. These elements are in the for
# (X,Y) where X and Y are the functional dependency X -> Y.
# X and Y should be expressed as a sequence of capitalized strings.
#
# Output Format:
# The output format is similar to the input format. It is a list of sets
# containing the functional dependencies of a sub relation of R
#
# For example:
# T = [('AB', 'CDE'),('C', 'AD'),('D', 'AE'),('B', 'F')]
# NF3decomp(T)
# Returns>>> [('D', 'AE'), ('B', 'F'), ('AB', 'C'), ('C', 'D')]
# As such each of the 4 returned set are to be made into a table.
def NF3decomp(FDependencies):
# Input Transformation - Get minimum versions of the cover req.
Dependencies = min_closure(FDependencies)
print ("Minimal Cover:")
print ( Dependencies)
# Output Template
Output = []
# For each distinct X collect all elements relating to X. eg. X -> Y X -> Z = X -> YZ
for i in range(0, len(Dependencies) ):
# X,Y is the starting dependency comparisons are made to.
x = set (Dependencies[i][0]) # X comes the "anchor" to which dependencies are collected for.
y = set (Dependencies[i][1]) # Y becomes the inital set of dependencies related to X.
for j in range (0, len(Dependencies) ):
# Xb, Yb is the pair to be compared with.
xb = set (Dependencies[j][0])
yb = set (Dependencies[j][1])
# If X is the same, yet Y != Yb, ie. The dependency isn't the same, combine the pairs.
if x == xb and y != yb:
y = y.union(yb)
else:
continue
# At this point, per each unique X, each of the minimal cover dependencies are condensed for a given X.
# Recoverting back into strings adds order to the list, this order makes redundancy checking difficuilt.
# Things are thus made into lists, and sorted so to maintain an consistent order.
x = list(x)
y = list(y)
x.sort()
y.sort()
# Mend Sets into original format
x = "".join(x)
y = "".join(y)
if (x,y) not in Output: # Duplicate Checker - Note that string comparison incorporates order.
# The above set -> list -> sorted list, is to remove order for comparison.
Output.append( (x,y) )
# Add back suuper key if needed
FD_superkey = Get_SuperKey(FDependencies)
FD_superkey_inOutput = False
for FD in Output:
if set(FD[0]) == set(FD_superkey):
FD_superkey_inOutput = True
if not FD_superkey_inOutput:
Output.append( (FD_superkey,"") )
return Output
# Assumes that each the functional dependencies completely covers all
# attributes in the relation.
#
# Finds the superkey for that set of relations. Presumably used once the
# 3NF Form is found.
#
# Input Format:
# T = [("ABH","CK"),("A","D"),("C","E"),("BGH","F"),("F","AD"),("E","F"),("BH","E")]
#
# Output Format:
# A the string representation of the X in X->Y, it is drawing from the input
# functional dependencies.
#
# Note: If no superkey is found then nothing is returned, check for this condition.
def Get_SuperKey(FDependencies):
Attributes = ""
for FD in FDependencies:
Attributes += FD[0]
Attributes += FD[1]
Attributes = set( list(Attributes) )
for FD in FDependencies:
FD_Closure = closure(FD[0],FDependencies)
if FD_Closure == Attributes:
return FD[0]
#T = [('AB', 'CDE'),('C', 'AD'),('D', 'AE'),('B', 'F')]
#print ( NF3decomp(T) )
#E = [("ABH","CK"),("A","D"),("C","E"),("BGH","F"),("F","AD"),("E","F"),("BH","E")]
#print ( NF3decomp(E) )
#print ( Get_SuperKey(T) )