fork download 
  1. # ----------------------------------------------------------------------------
  2. # -- HNU CE 데이터베이스(2025년 2학기 02분반): FD 관련 프로그래밍 과제 Part B
  3. # ----------------------------------------------------------------------------
  4. # -- 이름: 이은섭
  5. # -- 학번: 20210508
  6. # ----------------------------------------------------------------------------
  7.  
  8.  
  9. import io
  10. from contextlib import redirect_stdout 
  11. # 위 두개 import하는 이유: 
  12. # (2) 구할때 (1)의 closure() 사용하려고 하는데 
  13. # 함수 안에 print문이 출력 안되게 하려고
  14.  
  15. # (1) 3.2.4절 Algorithm 3.7 관련 closure 함수
  16.  
  17. # closure : FD 집합 , 속성 집합 -> 속성 집합
  18. # closure(S, {A1,A2...})는 {A1,A2,...}+를 계산
  19. def closure(S, R):
  20.  
  21.  
  22.     # 1. split
  23.     temp = []
  24.     for FD in S:
  25.         if len(FD[1]) >= 2:
  26.             for j in range(len(FD[1])):
  27.                 temp.append((FD[0], [FD[1][j]]))
  28.             S.remove(FD)
  29.     S += temp
  30.  
  31.     # 2. 초기화
  32.     X = R.copy()
  33.  
  34.     # 3. 반복 확장
  35.     temp = []
  36.     while(temp != X):
  37.         temp = X.copy()
  38.         for FD in S:
  39.             if set(FD[0]).issubset(set(X)) and not(set(FD[1]).issubset(set(X))):
  40.                 X += FD[1]
  41.     X.sort()
  42.  
  43.     return X
  44.  
  45.  
  46.  
  47.  
  48. # (2) 주어진 한 FD가 기존의 FD 집합으로부터 유도 가능한지 검사하는 함수 (closure 활용하면 간단)
  49.  
  50. # is_derived_from : FD , FD 집합 -> Bool
  51. # is_derived_from(fd, S)는 fd가 S로부터 유도 가능하면 참, 그렇지 않으면 거짓
  52. def is_derived_from(fd, S):
  53.  
  54.  
  55.     # 1. 주어진 fd에서 좌항 뽑아내 리스트(R형식으로 만들기)
  56.     R = fd[0]
  57.     # print("========fd to List========")
  58.     # print(R)
  59.  
  60.     # 2. closure 함수 이용해 좌항에 있는 속성의 클로저 구하기
  61.     f = io.StringIO() # closure()안에 있는 print안나오게 하려고 씀
  62.     with redirect_stdout(f):
  63.         X = closure(S, R)
  64.  
  65.     # print("========closure calcurate========")
  66.     # print(R)
  67.  
  68.     # 3. X값 안에 fd의 우항이 있는지 확인
  69.     derived = set(fd[1]).issubset(set(X))
  70.  
  71.     # 4. 결과 값 반환
  72.     return derived
  73.  
  74.  
  75.  
  76. # (3)  3.2.7절 관련 주어진 FD 집합이 기존 FD집합의 basis인지 검사
  77.  
  78. # is_basis_of :: FD 집합 , FD 집합 -> Bool
  79. # is_basis_of(B, S)는 B가 S의 basis이면 (minimal이 아닌 경우도 포함) 참, 그렇지 않으면 거짓
  80. def is_basis_of(B, S):
  81.  
  82.  
  83.     # 1. 두 FD들의 집합 B, S의 좌항에 있는 속성 뽑아 합집합으로 만듬
  84.     lefts = []
  85.     for FD in B:
  86.         if(FD[0] not in lefts):
  87.             lefts.append(FD[0])
  88.     for FD in S:
  89.         if(FD[0] not in lefts):
  90.             lefts.append(FD[0])
  91.  
  92.     # print("========Combine leftS and leftB========")
  93.     # print(lefts)
  94.  
  95.     # 2. B와 S각각 lefts의 속성들 closure함수 사용하여 비교 둘이 같으면 basis O 틀리면 X
  96.     basis = True
  97.     for attr in lefts:
  98.         f = io.StringIO() # closure()안에 있는 print안나오게 하려고 씀
  99.         with redirect_stdout(f):
  100.             if closure(S, attr) != closure(B, attr):
  101.                 basis = False
  102.                 break
  103.  
  104.     # 3. 출력 및 반환
  105.     return basis
  106.  
  107. # (4)  3.2.7절 관련 주어진 FD 집합이 minimal인지 검사
  108. # is_minimal :: [FD] -> Bool             
  109. # is_minimal(B)는 B가 3.2.7절에 제시된 기준에 따라 minimal하면 참, 그렇지 않으면 거짓
  110.  
  111. def is_minimal(B):
  112.     answer = True
  113.  
  114.     # 1. 모든 FD의 우항이 singleton인지 검사
  115.     for FD in B:
  116.         if len(FD[1]) != 1:   # 2개 이상일 경우 minimal 아님
  117.             answer = False
  118.             return answer
  119.  
  120.     # 2. FD 하나라도 제거하면 동등성 깨지는지 검사
  121.     for FD in B:
  122.         temp = B.copy()
  123.         temp.remove(FD)
  124.         if is_basis_of(B, temp):  # 제거해도 동등하면 minimal 아님
  125.             answer = False
  126.             return answer
  127.  
  128.     # 3. FD의 좌항에서 속성을 줄이면 동등성 깨지는지 검사
  129.     for FD in B:
  130.         left = FD[0]
  131.         right = FD[1]
  132.         if len(left) >= 2:
  133.             for attr in left:
  134.                 reduced_left = left.copy()
  135.                 reduced_left.remove(attr)
  136.                 temp = B.copy()
  137.                 temp.remove(FD)
  138.                 temp.append((reduced_left, right))
  139.                 if is_basis_of(B, temp):  # 왼쪽 속성 줄여도 동등하면 minimal 아님
  140.                     answer = False
  141.                     return answer
  142.  
  143.     return answer
  144.  
  145. # (5) 3.2.8절 Algorithm 3.12
  146. # project_FDs :: [Attr] -> [FD] -> [Attr] -> [FD]
  147. # project_FDs(L, S, L1)은
  148. #   원래 관계(R)의 속성 집합을 L과 FD집합을 S라 할 때
  149. #   L의 부분집합인 L1을 속성으로 하는 (즉, R의 프로젝션인 R1) 관계에서 성립하는 성질을 나타내는 FD집합(즉, S의 프로젝션인 S1)을 계산
  150. def project_FDs(L, S, L1):
  151.     T = []   # projection 결과 잠정 FD 집합
  152.  
  153.     # 1. L1의 각 속성에 대해 closure 계산 → L1 내부에서 유효한 FD 추가
  154.     for attr in L1:
  155.         X = closure(S, [attr])  
  156.         for i in X:
  157.             if i not in [attr] and i in L1:  # 자기 자신 제외, L1 내부 속성만
  158.                 T.append(([attr], [i]))
  159.  
  160.     # 2. 중복/비최소 FD 제거 (minimal form으로 정리)
  161.     i = 0
  162.     while i < len(T):
  163.         temp = T.copy()
  164.         FD = T[i]
  165.         temp.remove(FD)
  166.         if is_basis_of(T, temp):  # 제거해도 동등하면 삭제
  167.             T.remove(FD)
  168.             i = 0  # 다시 처음부터 확인
  169.         else:
  170.             i += 1
  171.  
  172.     return T
  173.  
  174.  
  175.  
  176. # ===============================TEST===============================
  177.  
  178. # (1)-1. closure함수 예제 1 (Example 3.8)
  179. S = [
  180.      (['A', 'B'], ['C']), 
  181.      (['B', 'C'], ['A', 'D']), 
  182.      (['C', 'F'], ['B']), 
  183.      (['D'], ['E'])
  184.      ]
  185. R = ['A', 'B']
  186. print("== Example for closure test 1=============================")
  187. print("S = {", end='')
  188. for FD in S:
  189.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  190. print("}")
  191. X = closure(S, R)
  192.  
  193. print("{", end='')
  194. for i in R:
  195.     print(i, end=',' if R.index(i) != R.index(R[-1]) else "")
  196. print("}+ = ", end='')
  197.  
  198. print("{", end='')
  199. for i in X:
  200.     print(i, end=',' if X.index(i) != X.index(X[-1]) else "")
  201. print("}")
  202. print("")
  203.  
  204. # (1)-2. closure함수 예제 2 (MyExample)
  205. R = ['C', 'F']
  206. print("== Example for closure test 2=============================")
  207. for FD in S:
  208.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  209. print("}")
  210. X = closure(S, R)
  211. print("{", end='')
  212. for i in R:
  213.     print(i, end=',' if R.index(i) != R.index(R[-1]) else "")
  214. print("}+ = ", end='')
  215.  
  216. print("{", end='')
  217. for i in X:
  218.     print(i, end=',' if X.index(i) != X.index(X[-1]) else "")
  219. print("}")
  220. print("")
  221.  
  222.  
  223. # (2)-1. is_drived_from함수 예제 1 (MyExample)
  224. S = [
  225.      (['A', 'B'], ['C']), 
  226.      (['B', 'C'], ['A', 'D']), 
  227.      (['C', 'F'], ['B']), 
  228.      (['D'], ['E'])
  229.      ]
  230. fd = (['A', 'B'], ['C', 'D'])
  231.  
  232. print("== Example for is_derived_from test 1=====================")
  233. print("S = {", end='')
  234. for FD in S:
  235.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  236. print("}")
  237. derived = is_derived_from(fd, S)
  238. print("{" + ' '.join(fd[0]), "->", ' '.join(fd[1])+ "}", " is derived from S :", derived)
  239. print("")
  240.  
  241. # (2)-2. is_drived_from함수 예제 2 (MyExample)
  242. S = [
  243.      (['A', 'B'], ['C']), 
  244.      (['B', 'C'], ['A', 'D']), 
  245.      (['C', 'F'], ['B']), 
  246.      (['D'], ['E'])
  247.      ]
  248. fd = (['A', 'B'], ['C', 'D', 'F'])
  249.  
  250. print("== Example for is_derived_from test 2=====================")
  251. print("S = {", end='')
  252. for FD in S:
  253.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  254. print("}")
  255. derived = is_derived_from(fd, S)
  256. print("{" + ' '.join(fd[0]), "->", ' '.join(fd[1])+ "}", " is derived from S :", derived)
  257. print("")
  258.  
  259.  
  260. # (3)-1. is_basis_of 함수 예제 1 (example 3.11)
  261. S = [
  262.     (['A'], ['B']), 
  263.     (['B'], ['C']), 
  264.     (['C'], ['A'])
  265.     ]
  266.  
  267. B = [
  268.     (['A'], ['B']), 
  269.     (['B'], ['A']), 
  270.     (['B'], ['C']), 
  271.     (['C'], ['B'])
  272.     ]
  273.  
  274. print("== Example for is_basis_of test 1=====================")
  275. print("S = {", end='')
  276. for FD in S:
  277.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  278. print("}")
  279.  
  280. print("B = {", end='')
  281. for FD in B:
  282.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  283. print("}")
  284. basis = is_basis_of(B, S)
  285. print("B is basis of S :", basis)
  286. print("")
  287.  
  288. # (3)-2. is_basis_of 함수 예제 2(MyExample)
  289. S = [
  290.     (['A'], ['B']), 
  291.     (['B'], ['C']), 
  292.     (['C'], ['A'])
  293.     ]
  294.  
  295. B = [
  296.     (['A'], ['B']), 
  297.     (['B'], ['A']), 
  298.     (['D'], ['F']), 
  299.     (['C'], ['B'])
  300.     ]
  301.  
  302. print("== Example for is_basis_of test 2=====================")
  303. print("S = {", end='')
  304. for FD in S:
  305.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  306. print("}")
  307.  
  308. print("B = {", end='')
  309. for FD in B:
  310.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  311. print("}")
  312. basis = is_basis_of(B, S)
  313. print("B is basis of S :", basis)
  314. print("")
  315.  
  316.  
  317. # (4)-1 is_minimal 함수 예제1 (example 3.11)
  318. print("== Example for is_minimal test 1===========================")
  319. B = [
  320.     (['A'], ['B']), 
  321.     (['B'], ['A']), 
  322.     (['B'], ['C']), 
  323.     (['C'], ['B'])
  324.     ]
  325. print("B = {", end='')
  326. for FD in B:
  327.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  328. print("}")
  329.  
  330. minimal = is_minimal(B)
  331. print("B is minimal :", minimal)
  332. print("")
  333.  
  334. # (4)-2 is_minimal 함수 예제2 (my example)
  335. print("== Example for is_minimal test 2===========================")
  336. B = [
  337.     (['A'], ['B']),
  338.     (['B'], ['C']),
  339.     (['A'], ['C'])
  340. ]
  341. print("B = {", end='')
  342. for FD in B:
  343.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  344. print("}")
  345.  
  346. minimal = is_minimal(B)
  347. print("B is minimal :", minimal)
  348. print("")
  349.  
  350. # (5)-1. project_FDs 함수 예제 (example 3.13)
  351. L  = ['A', 'B', 'C', 'D']    
  352. S  = [                       
  353.     (['A'], ['B']),
  354.     (['B'], ['C']),
  355.     (['C'], ['D'])
  356. ]
  357. L1 = ['A', 'C', 'D']
  358.  
  359. print("== Example for project_FDs test 1===========================")
  360. print("L = {", end='')
  361. for FD in L:
  362.     print(FD, end="," if L.index(FD) != L.index(L[-1]) else "")
  363. print("}")
  364. print("S = {", end='')
  365. for FD in S:
  366.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  367. print("}")
  368. print("L1 = {", end='')
  369. for FD in L1:
  370.     print(FD, end="," if L1.index(FD) != L1.index(L1[-1]) else "")
  371. print("}")
  372.  
  373. S1 = project_FDs(L, S, L1)
  374. print("S1 = {", end='')
  375. for FD in S1:
  376.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if S1.index(FD) != S1.index(S1[-1]) else "")
  377. print("}")
  378. print("")
  379.  
  380.  
  381. # (5)-2. project_FDs 함수 예제 (my example)
  382. L  = ['A', 'B', 'C', 'D', 'E']
  383. S  = [
  384.     (['A'], ['B']),
  385.     (['A'], ['C']),
  386.     (['B'], ['C']),
  387.     (['C'], ['D']),
  388.     (['D'], ['E'])
  389. ]
  390. L1 = ['A', 'B', 'D']
  391.  
  392. print("== Example for project_FDs test 2===========================")
  393. print("L = {", end='')
  394. for FD in L:
  395.     print(FD, end="," if L.index(FD) != L.index(L[-1]) else "")
  396. print("}")
  397. print("S = {", end='')
  398. for FD in S:
  399.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  400. print("}")
  401. print("L1 = {", end='')
  402. for FD in L1:
  403.     print(FD, end="," if L1.index(FD) != L1.index(L1[-1]) else "")
  404. print("}")
  405.  
  406. S1 = project_FDs(L, S, L1)
  407. print("S1 = {", end='')
  408. for FD in S1:
  409.     print(' '.join(FD[0]), "->", ' '.join(FD[1]), end=", " if S1.index(FD) != S1.index(S1[-1]) else "")
  410. print("}")
  411. print("")
  412.  
Success #stdin #stdout 0.12s 14176KB
comments (?)
stdin 
Standard input is empty
stdout 
== Example for closure test 1=============================
S = {A B -> C, B C -> A D, C F -> B, D -> E}
{A,B}+ = {A,B,C,D,E}

== Example for closure test 2=============================
A B -> C, C F -> B, D -> E, B C -> A, B C -> D}
{C,F}+ = {A,B,C,D,E,F}

== Example for is_derived_from test 1=====================
S = {A B -> C, B C -> A D, C F -> B, D -> E}
{A B -> C D}  is derived from S : True

== Example for is_derived_from test 2=====================
S = {A B -> C, B C -> A D, C F -> B, D -> E}
{A B -> C D F}  is derived from S : False

== Example for is_basis_of test 1=====================
S = {A -> B, B -> C, C -> A}
B = {A -> B, B -> A, B -> C, C -> B}
B is basis of S : True

== Example for is_basis_of test 2=====================
S = {A -> B, B -> C, C -> A}
B = {A -> B, B -> A, D -> F, C -> B}
B is basis of S : False

== Example for is_minimal test 1===========================
B = {A -> B, B -> A, B -> C, C -> B}
B is minimal : True

== Example for is_minimal test 2===========================
B = {A -> B, B -> C, A -> C}
B is minimal : False

== Example for project_FDs test 1===========================
L = {A,B,C,D}
S = {A -> B, B -> C, C -> D}
L1 = {A,C,D}
S1 = {A -> C, C -> D}

== Example for project_FDs test 2===========================
L = {A,B,C,D,E}
S = {A -> B, A -> C, B -> C, C -> D, D -> E}
L1 = {A,B,D}
S1 = {A -> B, B -> D}
https://ideone.com/sY80JW
이은섭
language:
Python 3 (python  3.12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!