fork download
copy 
  1.  ----------------------------------------------------------------------------
  2. -- HNU CE 데이터베이스(2025년 2학기 02분반): FD 관련 프로그래밍 과제
  3. ----------------------------------------------------------------------------
  4. -- 이름: 이재혁
  5. -- 학번: 20210501
  6. ----------------------------------------------------------------------------
  7.  
  8. import Data.List
  9. -- representing sets withi lists
  10.  
  11. subset xs ys = null (xs\\ys)	-- subset test in terms of set subtraction
  12.  
  13. -- functional dependency A B C -> D E encoded as (["A","B","C"],["D","E"])
  14. type FD = ([Attr], [Attr])
  15. type Attr = String  -- attributes are represented as strings
  16.  
  17.  
  18. --  3.2.4절 Algorithm 3.7
  19. closure :: [FD] -> [Attr] -> [Attr]   
  20. closure fds xs = if xs/=xs1 then closure fds xs1 else sort xs
  21. 	where xs1 = foldr union xs [cs | (bs,cs) <- fds, bs `subset` xs]
  22.  
  23. -- fd가 기존의 fds로부터 유도 가능한지 검사 (closure 활용한 간단한 함수)
  24. is_derived_from :: FD -> [FD] -> Bool
  25. is_derived_from fd fds = all (`elem` closureSet) rhs
  26.   where
  27.     lhs = fst fd
  28.     rhs = snd fd
  29.     closureSet = closure fds lhs
  30.  
  31.  
  32.  
  33. --  3.2.7절 관련 fds의 basis인지 검사
  34. is_basis_of :: [FD] -> [FD] -> Bool
  35. is_basis_of basis fds =
  36.     equivalent basis fds &&             
  37.     all singletonRHS basis &&           
  38.     all nonredundant basis &&       
  39.     all minimalLHS basis                 
  40.   where
  41.  
  42.     singletonRHS (_, rhs) = length rhs == 1
  43.     nonredundant fd = not ((is_derived_from fd (remove fd basis)))
  44.  
  45.     minimalLHS (lhs, rhs) =
  46.         all (\a -> not (is_derived_from (lhs \\ [a], rhs) basis)) lhs
  47.  
  48.     remove x = filter (/= x)
  49.     equivalent a b =
  50.         all (`is_derived_from` a) b &&
  51.         all (`is_derived_from` b) a
  52.  
  53.  
  54. --  3.2.7절 basis가 미니멀한지 검사
  55. is_minimal :: [FD] -> Bool             
  56. is_minimal basis = undefined
  57.  
  58. -- 3.2.8절 Algorithm 3.12
  59. project_FDs :: [Attr] -> [FD] -> [Attr] -> [FD]
  60. project_FDs as fds as1 = undefined
  61.  
  62.  
  63. -- the main function for running test examples
  64. main = do
  65. 	putStrLn "== Example 3.8 for closure test ============================="
  66. 	let fds = [ (["A","B"],["C"]),		
  67. 				(["B","C"],["A","D"]),  
  68. 				(["D"],["E"]),			
  69. 				(["C","F"],["B"]) ]	
  70. 	let xs = ["A","B"]
  71. 	putStrLn $ "S = " ++ showFDs fds
  72. 	putStrLn $ showAttrSet xs ++ "+ = " ++ showAttrSet (closure fds xs)
  73. 	putStrLn ""
  74.  
  75. 	let fds_1 = [ (["A"],["D"]),		
  76. 				(["B","C"],["A","D"]),  
  77. 				(["F", "G"],["H"]),		
  78. 				(["C","F"],["B"]) ]		
  79. 	let xs_1 = ["A","D"]
  80. 	putStrLn $ "S = " ++ showFDs fds_1
  81. 	putStrLn $ showAttrSet xs_1 ++ "+ = " ++ showAttrSet (closure fds xs_1)
  82. 	putStrLn ""
  83. 	--
  84.  
  85. 	putStrLn "== Example ... for is_derived_from test ====================="
  86.  
  87. 	let fds2 = [ (["A"], ["C"]) 
  88.                , (["C"], ["D"])
  89.                , (["C","F"], ["G"]) ]  
  90. 	let fd_test1 = (["A"], ["D"]) 
  91. 	let fd_test2 = (["A"], ["G"])     
  92. 	putStrLn $ "S = " ++ showFDs fds2
  93. 	putStrLn $ "A -> D is derived from S : " ++ show (is_derived_from fd_test1 fds2)  
  94. 	putStrLn $ "A -> G is derived from S : " ++ show (is_derived_from fd_test2 fds2)   
  95. 	putStrLn ""
  96.  
  97.  
  98. 	let fds2_2 = [ (["A"], ["D"]) 
  99.                , (["D"], ["G"]) 
  100.                , (["C"], ["F"]) ]  
  101. 	let fd_test1_1 = (["A"], ["F"]) 
  102. 	let fd_test2_2 = (["D"], ["G"])     
  103. 	putStrLn $ "S = " ++ showFDs fds2_2
  104. 	putStrLn $ "A -> F is derived from S : " ++ show (is_derived_from fd_test1_1 fds2_2)  
  105. 	putStrLn $ "D -> G is derived from S : " ++ show (is_derived_from fd_test2_2 fds2_2)   
  106. 	putStrLn ""
  107.  
  108.  
  109. 	--
  110. 	putStrLn "== Example ... for is_basis_of test ========================="
  111.  
  112. 	let s_fds = [ (["A"], ["B"]), (["B"], ["C"]), (["C"], ["D"]) ]		
  113. 	let b_basis = [ (["A"], ["B"]), (["B"], ["C"]), (["C"], ["D"]) ] 	
  114.  
  115. 	putStrLn $ "S = " ++ showFDs s_fds
  116. 	putStrLn $ "B = " ++ showFDs b_basis
  117. 	putStrLn $ "B is basis of S : " ++ show (is_basis_of b_basis s_fds)
  118. 	putStrLn ""
  119.  
  120. 	let s_fds2 = [ (["A"], ["C"]), (["C"], ["D"]), (["D"], ["G"]) ]		
  121. 	let b_basis2 = [ (["A","B"], ["E"]), (["G"], ["A"]) ]				
  122. 	putStrLn $ "S = " ++ showFDs s_fds2
  123. 	putStrLn $ "B = " ++ showFDs b_basis2
  124. 	putStrLn $ "B is basis of S : " ++ show (is_basis_of b_basis2 s_fds2)
  125. 	putStrLn ""
  126.  
  127. 	let s_fds3 = [ (["A", "B"], ["C"]), (["C"], ["D"]), (["D"], ["G"]) ]	 
  128. 	let b_basis3 = [ (["A","B"], ["C"]), (["C"], ["D"]), (["D"], ["G"]) ]			
  129. 	putStrLn $ "S = " ++ showFDs s_fds3
  130. 	putStrLn $ "B = " ++ showFDs b_basis3
  131. 	putStrLn $ "B is basis of S : " ++ show (is_basis_of b_basis3 s_fds3)
  132. 	putStrLn ""
  133. 	--
  134.  
  135.  
  136. 	putStrLn "== Example ... for is_minimal test =========================="
  137. 	putStrLn "B = { ..->., ..->., ... }"
  138. 	putStrLn "B is minimal : True/False"
  139. 	putStrLn ""
  140. 	--
  141. 	putStrLn "== Example ... for project_FDs test ========================="
  142. 	putStrLn "L = {......}"
  143. 	putStrLn "S = { ..->.., ..->.., ... ... ... }"
  144. 	putStrLn "L1 = {...}"
  145. 	putStrLn "S1 = { ..->.., ..->.., ... ... }"
  146. 	putStrLn ""
  147. 	--
  148.  
  149. -- helper functions for pretty printing
  150. showFD :: FD -> String
  151. showFD (as,bs) = concat $ intersperse " " (as ++ "->" : bs)
  152.  
  153. showFDs :: [FD] -> String
  154. showFDs fds = "{" ++ concat (intersperse ", " $ map showFD fds) ++ "}"
  155.  
  156. showAttrSet :: [Attr] -> String
  157. showAttrSet as = "{" ++ concat (intersperse "," as) ++ "}"
  158.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy
stdout
copy 
== Example 3.8 for closure test =============================
S = {A B -> C, B C -> A D, D -> E, C F -> B}
{A,B}+ = {A,B,C,D,E}

S = {A -> D, B C -> A D, F G -> H, C F -> B}
{A,D}+ = {A,D,E}

== Example ... for is_derived_from test =====================
S = {A -> C, C -> D, C F -> G}
A -> D is derived from S : True
A -> G is derived from S : False

S = {A -> D, D -> G, C -> F}
A -> F is derived from S : False
D -> G is derived from S : True

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

S = {A -> C, C -> D, D -> G}
B = {A B -> E, G -> A}
B is basis of S : False

S = {A B -> C, C -> D, D -> G}
B = {A B -> C, C -> D, D -> G}
B is basis of S : True

== Example ... for is_minimal test ==========================
B = { ..->., ..->., ... }
B is minimal : True/False

== Example ... for project_FDs test =========================
L = {......}
S = { ..->.., ..->.., ... ... ... }
L1 = {...}
S1 = { ..->.., ..->.., ... ... }
https://ideone.com/7lt8vF
language:
Haskell (ghc 8.4.4)
created:
10 hours 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!