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.  
  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.  
  108.  
  109.  
  110.  
  111. # ===============================TEST===============================
  112.  
  113. # (1)-1. closure함수 예제 1 (Example 3.8)
  114. S = [
  115.      (['A', 'B'], ['C']), 
  116.      (['B', 'C'], ['A', 'D']), 
  117.      (['C', 'F'], ['B']), 
  118.      (['D'], ['E'])
  119.      ]
  120. R = ['A', 'B']
  121. print("== Example for closure test 1=============================")
  122. print("S = {", end='')
  123. for FD in S:
  124.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  125. print("}")
  126. X = closure(S, R)
  127.  
  128. print("{", end='')
  129. for i in R:
  130.     print(i, end=',' if R.index(i) != R.index(R[-1]) else "")
  131. print("}+ = ", end='')
  132.  
  133. print("{", end='')
  134. for i in X:
  135.     print(i, end=',' if X.index(i) != X.index(X[-1]) else "")
  136. print("}")
  137. print("")
  138.  
  139. # (1)-2. closure함수 예제 2 (MyExample)
  140. R = ['C', 'F']
  141. print("== Example for closure test 2=============================")
  142. for FD in S:
  143.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  144. print("}")
  145. X = closure(S, R)
  146. print("{", end='')
  147. for i in R:
  148.     print(i, end=',' if R.index(i) != R.index(R[-1]) else "")
  149. print("}+ = ", end='')
  150.  
  151. print("{", end='')
  152. for i in X:
  153.     print(i, end=',' if X.index(i) != X.index(X[-1]) else "")
  154. print("}")
  155. print("")
  156.  
  157.  
  158. # (2)-1. is_drived_from함수 예제 1 (MyExample)
  159. S = [
  160.      (['A', 'B'], ['C']), 
  161.      (['B', 'C'], ['A', 'D']), 
  162.      (['C', 'F'], ['B']), 
  163.      (['D'], ['E'])
  164.      ]
  165. fd = (['A', 'B'], ['C', 'D'])
  166.  
  167. print("== Example for is_derived_from test 1=====================")
  168. print("S = {", end='')
  169. for FD in S:
  170.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  171. print("}")
  172. derived = is_derived_from(fd, S)
  173. print("{" + ' '.join(fd[0]), "->", ' '.join(fd[1])+ "}", " is derived from S :", derived)
  174. print("")
  175.  
  176. # (2)-2. is_drived_from함수 예제 2 (MyExample)
  177. S = [
  178.      (['A', 'B'], ['C']), 
  179.      (['B', 'C'], ['A', 'D']), 
  180.      (['C', 'F'], ['B']), 
  181.      (['D'], ['E'])
  182.      ]
  183. fd = (['A', 'B'], ['C', 'D', 'F'])
  184.  
  185. print("== Example for is_derived_from test 2=====================")
  186. print("S = {", end='')
  187. for FD in S:
  188.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  189. print("}")
  190. derived = is_derived_from(fd, S)
  191. print("{" + ' '.join(fd[0]), "->", ' '.join(fd[1])+ "}", " is derived from S :", derived)
  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. print("S = {", end='')
  211. for FD in S:
  212.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  213. print("}")
  214.  
  215. print("B = {", end='')
  216. for FD in B:
  217.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  218. print("}")
  219. basis = is_basis_of(B, S)
  220. print("B is basis of S :", basis)
  221. print("")
  222.  
  223. # (3)-2. is_basis_of 함수 예제 2(MyExample)
  224. S = [
  225.     (['A'], ['B']), 
  226.     (['B'], ['C']), 
  227.     (['C'], ['A'])
  228.     ]
  229.  
  230. B = [
  231.     (['A'], ['B']), 
  232.     (['B'], ['A']), 
  233.     (['D'], ['F']), 
  234.     (['C'], ['B'])
  235.     ]
  236.  
  237. print("== Example for is_basis_of test 2=====================")
  238. print("S = {", end='')
  239. for FD in S:
  240.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if S.index(FD) != S.index(S[-1]) else "")
  241. print("}")
  242.  
  243. print("B = {", end='')
  244. for FD in B:
  245.     print(' '.join(FD[0]), "->",  ' '.join(FD[1]), end=", " if B.index(FD) != B.index(B[-1]) else "")
  246. print("}")
  247. basis = is_basis_of(B, S)
  248. print("B is basis of S :", basis)
  249. print("")
  250.  
Success #stdin #stdout 0.13s 14136KB
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=============================
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:
15 minutes 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!