In [1]:
R = (
set(['A','B','D']),
set(['B','C','E']),
set(['D','E'])
)
F = (
(set(['A']),set(['B','D'])),
(set(['D']),set(['A'])),
(set(['C']),set(['B','E'])),
(set(['E']),set(['D'])),
(set(['C']),set(['A']))
)
In [2]:
def closure(X, F):
res = X
mark = [0] * len(F)
while 1:
pre_visted = sum(mark)
for i in range(len(F)):
if mark[i] == 0: # not visited
if F[i][0].issubset(res):
res = res.union(F[i][1])
mark[i] = 1
after_visted = sum(mark)
if pre_visted == after_visted:
break
return res
In [3]:
G = []
closures = tuple(
(k, closure(k, F))
for k, _ in F
) # (X, X+)
for idx, (X, Y) in enumerate(F):
for rho in R:
if X.issubset(rho):
temp = closures[idx][1] & rho - X
if len(temp) > 0:
G.append((X, temp))
G
Out[3]:
[({'A'}, {'B', 'D'}), ({'D'}, {'A', 'B'}), ({'C'}, {'B', 'E'}), ({'E'}, {'B'}), ({'E'}, {'D'}), ({'C'}, {'B', 'E'})]
The FDs in F are contained in G except for $C\rightarrow A$, and MEMBER $(G, C\rightarrow A)$ is true. Therefore, $\rho$ keeps dependency preservation.