fork download
copy 
  1. # ----------------------------------------------------------------------------
  2. # -- HNU CE 데이터베이스(2025년 2학기 02분반): FD 관련 프로그래밍 과제 Part A
  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.     # 0. S 출력
  21.     print("S = {", end='')
  22.     for FD in S:
  23.         print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  24.     print("}")
  25.  
  26.     # 1. split
  27.     temp = []
  28.     for FD in S:
  29.         if len(FD[1]) >= 2:
  30.             for j in range(len(FD[1])):
  31.                 temp.append((FD[0], [FD[1][j]]))
  32.             S.remove(FD)
  33.     S += temp
  34.     # print("========FD Spliting========")
  35.     # print(S)
  36.  
  37.     # 2. 초기화
  38.     X = R.copy()
  39.     # print("========X Reset========")
  40.     # print(X)
  41.  
  42.     # 3. 반복 확장
  43.     temp = []
  44.     while(temp != X):
  45.         temp = X.copy()
  46.         for FD in S:
  47.             if set(FD[0]).issubset(set(X)) and not(set(FD[1]).issubset(set(X))):
  48.                 X += FD[1]
  49.     X.sort()
  50.     # print("========Repeat Expansion========")
  51.     # print(X)
  52.  
  53.     # 4. X 출력과 결과 반환
  54.     print("{", end='')
  55.     for i in R:
  56.         print(i, end=',' if R.index(i) != R.index(R[-1]) else "")
  57.     print("}+ = ", end='')
  58.  
  59.     print("{", end='')
  60.     for i in X:
  61.         print(i, end=',' if X.index(i) != X.index(X[-1]) else "")
  62.     print("}")
  63.  
  64.     return X
  65.  
  66.  
  67.  
  68.  
  69. # (2) 주어진 한 FD가 기존의 FD 집합으로부터 유도 가능한지 검사하는 함수 (closure 활용하면 간단)
  70.  
  71. # is_derived_from : FD , FD 집합 -> Bool
  72. # is_derived_from(fd, S)는 fd가 S로부터 유도 가능하면 참, 그렇지 않으면 거짓
  73. def is_derived_from(fd, S):
  74.     # 0. S 출력
  75.     print("S = {", end='')
  76.     for FD in S:
  77.         print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  78.     print("}")
  79.  
  80.     # 1. 주어진 fd에서 좌항 뽑아내 리스트(R형식으로 만들기)
  81.     R = fd[0]
  82.     # print("========fd to List========")
  83.     # print(R)
  84.  
  85.     # 2. closure 함수 이용해 좌항에 있는 속성의 클로저 구하기
  86.     f = io.StringIO() # closure()안에 있는 print안나오게 하려고 씀
  87.     with redirect_stdout(f):
  88.         X = closure(S, R)
  89.  
  90.     # print("========closure calcurate========")
  91.     # print(R)
  92.  
  93.     # 3. X값 안에 fd의 우항이 있는지 확인
  94.     derived = set(fd[1]).issubset(set(X))
  95.     print(' '.join(fd[0]), "->", ' '.join(fd[1]), " is derived from S :", derived)
  96.  
  97.     # 4. 결과 값 반환
  98.     return derived
  99.  
  100.  
  101.  
  102. # (3)  3.2.7절 관련 주어진 FD 집합이 기존 FD집합의 basis인지 검사
  103.  
  104. # is_basis_of :: FD 집합 , FD 집합 -> Bool
  105. # is_basis_of(B, S)는 B가 S의 basis이면 (minimal이 아닌 경우도 포함) 참, 그렇지 않으면 거짓
  106. def is_basis_of(B, S):
  107.     # 0. B, S 출력
  108.     print("S = {", end='')
  109.     for FD in S:
  110.         print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  111.     print("}")
  112.  
  113.     print("B = {", end='')
  114.     for FD in B:
  115.         print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  116.     print("}")
  117.  
  118.     # 1. 두 FD들의 집합 B, S의 좌항에 있는 속성 뽑아 합집합으로 만듬
  119.     lefts = []
  120.     for FD in B:
  121.         if(FD[0] not in lefts):
  122.             lefts.append(FD[0])
  123.     for FD in S:
  124.         if(FD[0] not in lefts):
  125.             lefts.append(FD[0])
  126.  
  127.     # print("========Combine leftS and leftB========")
  128.     # print(lefts)
  129.  
  130.     # 2. B와 S각각 lefts의 속성들 closure함수 사용하여 비교 둘이 같으면 basis O 틀리면 X
  131.     basis = True
  132.     for attr in lefts:
  133.         f = io.StringIO() # closure()안에 있는 print안나오게 하려고 씀
  134.         with redirect_stdout(f):
  135.             if closure(S, attr) != closure(B, attr):
  136.                 basis = False
  137.                 break
  138.  
  139.     # 3. 출력 및 반환
  140.     print("B is basis of S :", basis)
  141.     return basis
  142.  
  143.  
  144.  
  145.  
  146.  
  147. # ===============================TEST===============================
  148.  
  149. # (1)-1. closure함수 예제 1 (Example 3.8)
  150. S = [
  151.      (['A', 'B'], ['C']), 
  152.      (['B', 'C'], ['A', 'D']), 
  153.      (['C', 'F'], ['B']), 
  154.      (['D'], ['E'])
  155.      ]
  156. R = ['A', 'B']
  157. print("== Example for closure test 1=============================")
  158. X = closure(S, R)
  159. print("")
  160.  
  161. # (1)-2. closure함수 예제 2 (MyExample)
  162. R = ['C', 'F']
  163. print("== Example for closure test 2=============================")
  164. X = closure(S, R)
  165. print("")
  166.  
  167.  
  168. # (2)-1. is_drived_from함수 예제 1 (MyExample)
  169. S = [
  170.      (['A', 'B'], ['C']), 
  171.      (['B', 'C'], ['A', 'D']), 
  172.      (['C', 'F'], ['B']), 
  173.      (['D'], ['E'])
  174.      ]
  175. fd = (['A', 'B'], ['C', 'D'])
  176.  
  177. print("== Example for is_derived_from test 1=====================")
  178. is_derived_from(fd, S)
  179. print("")
  180.  
  181. # (2)-2. is_drived_from함수 예제 2 (MyExample)
  182. S = [
  183.      (['A', 'B'], ['C']), 
  184.      (['B', 'C'], ['A', 'D']), 
  185.      (['C', 'F'], ['B']), 
  186.      (['D'], ['E'])
  187.      ]
  188. fd = (['A', 'B'], ['C', 'D', 'F'])
  189.  
  190. print("== Example for is_derived_from test 2=====================")
  191. is_derived_from(fd, S)
  192. print("")
  193.  
  194.  
  195. # (3)-1. is_basis_of 함수 예제 1 (example 3.11)
  196. S = [
  197.     (['A'], ['B']), 
  198.     (['B'], ['C']), 
  199.     (['C'], ['A'])
  200.     ]
  201.  
  202. B = [
  203.     (['A'], ['B']), 
  204.     (['B'], ['A']), 
  205.     (['B'], ['C']), 
  206.     (['C'], ['B'])
  207.     ]
  208.  
  209. print("== Example for is_basis_of test 1=====================")
  210. is_basis_of(B, S)
  211. print("")
  212.  
  213. # (3)-2. is_basis_of 함수 예제 2(MyExample)
  214. S = [
  215.     (['A'], ['B']), 
  216.     (['B'], ['C']), 
  217.     (['C'], ['A'])
  218.     ]
  219.  
  220. B = [
  221.     (['A'], ['B']), 
  222.     (['B'], ['A']), 
  223.     (['D'], ['F']), 
  224.     (['C'], ['B'])
  225.     ]
  226.  
  227. print("== Example for is_basis_of test 2=====================")
  228. is_basis_of(B, S)
  229. print("")
  230.  
Success #stdin #stdout 0.07s 14124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
== 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=============================
S = {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
https://ideone.com/KsBouM
-- HNU CE 데이터베이스(2025년 2학기 02분반): FD 관련 프로그래밍 과제 Part A
-- 이름: 이은섭
-- 학번: 20210508
language:
Python 3 (python  3.12)
created:
2 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!