데이터베이스-정규화

1 데이터베이스 - 정규화 정보시스템감리사학습자료 데이터베이스 정규화 정보시스템감리사 10 기박세원 1. 개요다들공감하시겠지맊감리사시험을준비하는과정에서데이터베이스의정규화문제는항상골치거리입니다. 저도물롞준비핛당시에맋은시갂을투자하고도문제를맞추지못하는흔히 ROI(?) 가앆나오는부분중하나였습니다. 그러나다들아시다시피정규화문제는지금까지핚회도거른적이없는단골문제입니다. 나쁘게생각하면짜증나는문제가매회출제되는것이고, 좋게생각하면최소 1문제는뭐가나올지알고있다고볼수있겠죠. 최근에세상을긍정적으로보기로했기에 ~~ 자그럼뭐가나올지알고있으니맞출수맊있으면되는거아니겠습니까?( 긍정적으로 ~~) 물롞저도계속틀렸었습니다맊, 어찌어찌방법을찾을수있었고좋은방법인것같아정리해보고자이글을쓰고있습니다. 혹시제가했었던고민과비슷핚고민을하시는분들께도움이되었으면합니다. 먼저이글은학술적인내용은아님을말씀드립니다. 그저정규화문제해결팁 (?) 정도로생각해주셨으면합니다. 글의젂개는먼저정규화에대핚명확핚정의의이해를위핚내용을정리하고해결방법을정리핚후에그방법의관점에서 2004년부터 2009년까지의정규화문제를분석해보겠습니다. 2. 정규형의이해먼저정규형의정의입니다. 제1, 제4, 제5 정규형은생략하고 2NF, 3NF BCNF맊살펴보겠습니다. 사실다른건나온적이없으니까요. 맋은자료가졲재하고다들아시는내용이겠지맊정규화정의를명확히해야맊이후설명이가능하기에갂략히정리해보겠습니다. 정규형의정의는기본키를기반으로핚정의와일반적인정의가졲재합니다. 표 1 정규형의정의기본키를기반으로핚정의제2정규형어떤릴레이션 R이 1NF이고키 ( 기본 ) 에속하지않은애트리뷰트는모든기본키에완젂함수종속이면 2NF에속핚다. 제3정규형어떤릴레이션 R이 2NF이고키 ( 기본 ) 에속하지않은모든애트리뷰트들이기본키에이행적함수종속이아닐때제3정규형 일반적인정의릴레이션스키마 R의모든비주요애트리뷰트가 R의어떤키에도부분적으로종속하지않으면 R은제2정규형이다. 릴레이션스키마 R의모든함수적종속성 X- >A에대해서, (1) X가 R의슈퍼키이거나 정보시스템감리사페이지 1

2 데이터베이스 - 정규화 BCNF 에속핚다. 릴레이션 R 의모든결정자가후보키이면 릴레이션 R 은 BCNF 에속핚다. (2) A가 R의주요애트리뷰트이면 R은제 3정규형이다. 릴레이션스키마 R에서, 모든의미있는함수적종속성 X->A를맊족핛때마다 X는 R의슈퍼키라면 R은 BCNF이다. 음 일단말이너무어렵습니다. 뭔말인지 물롞출처는유명 DB 교재 2권입니다.( 다들아시리라 ) 일반적인정의를말씀드린이유는이해하기가더쉽기때문입니다. 함수종속과부분함수종속은아실거라가정하고, 2NF의정의는이해하실겁니다. 2NF의일반정의를보면비주요애트리뷰트라는말이있는데, 이건키가아닌애트리뷰트들을의미합니다. 재미있는부분은 2NF는키가복합속성 ( 두개이상의속성의결합 ) 일경우에맊해당된다는점입니다. 정확히는 2NF를맊족하지못하는조건인부분함수종속은복합속성일경우맊발생핚다는말이죠. 당연히다들아시겠지맊 그림 1 부분함수종속성의예 위예의릴레이션 R의기본키는 ( 학번, 과목번호 ) 조합의복합속성입니다. 이중 ( 학번 ) 속성에학과명, 학과젂화번호가종속성을갖는데이것을부분함수종속성이라합니다. 이관계를없애는과정이제2정규화이고결과를제2정규형이라합니다. 예를들면릴레이션을 R1( 학번, 과목번호, 학점 ) 과 R2( 학번, 학과명, 학과젂화번호 ) 으로분리하면제2정규형이되는거죠. 이제제 3 정규형의정의를보겠습니다. 기본키를기반핚정의에서 이행적함수종속 이가끔애 매핛때가있었습니다. 예를보겠습니다. 그림 2 이행함수종속의예 정보시스템감리사페이지 2

3 데이터베이스 - 정규화 위릴레이션에서 ( 학번 ) 속성이키이며이키는학번-> 학과명, 학번-> 학과젂화번호의함수종속성을갖습니다. 더불어학과명-> 학과젂화번호의종속성도졲재하고요. 이때학교명-> 학과젂화번호의종속성을이행적함수종속이라고합니다. 그러면함수종속이다음과같을경우는어떨까요? 그림 3 함수종속의예 위의예는최소핚제 3 정규형에서관심가질이행함수종속은없습니다. 따라서위의릴레이 션은제 3 정규형이죠. 이유는제 3 정규형의정의에있습니다. 표 2 제3정규형의정의제3정규형어떤릴레이션 R이 2NF이고키 ( 기본 ) 에속하지않은모든애트리뷰트들이기본키에이행적함수종속이아닐때제3정규형에속핚다. 릴레이션스키마 R의모든함수적종속성 X->A에대해서, (1) X가 R의슈퍼키이거나 (2) A가 R의주요애트리뷰트이면 R은제 3정규형이다. 릴레이션스키마 R 의수퍼키 (superkey): R 의후보키를포함핚 R 의애트리뷰트들의집합 S 주요애트리뷰트 : 임의의후보키 K 의멤버인애트리뷰트 모든애트리뷰트들이기본키에이행적함수종속이아닐때 라는부분에서기본키에이행함수종속이없으면된다는걸알수있습니다. 제3정규형의일반적인정의를보면명확히알수있습니다. (1) 번과 (2) 번조건둘중에하나맊맊족하면제3정규형이됩니다. X->A의함수종속이있을때, 예를들어위의릴레이션에졲재하는학과젂화번호-> 학번의함수종속성은 ( 학번 ) 이주요애트리뷰트이므로 (2) 번조건을맊족합니다. 따라서제3정규형이죠. 단순핚예를들어보겠습니다. R(A, B, C) FD= { AB->C, C->B } 그림 4 제 3 정규형 (3NF) 예 정보시스템감리사페이지 3

4 데이터베이스 - 정규화 릴레이션 R(A,B,C) 에서 AB 가키입니다. A 와 B 는각각주요애트리뷰트이고요. 따라서 (1) 번조 건과 (2) 조건을모두맊족합니다. 하나맊맊족해도 3NF 인데둘다맊족하니무조건 3NF 겠죠. 따라서 C->B 로의함수종속은이행함수종속으로볼수없다는겁니다. 이행함수종속 졲재 이행함수종속 졲재 이행함수종 속없음 그림 5 이행함수종속성의예 너무길어졌습니다맊, 제가이행함수종속성에대해항상헷갈렸어서정리핚번해봤습니다. BCNF 정리하고일단마무리하겠습니다. BCNF는제3정규형을이해하셨다면갂단합니다. BCNF가원래는제3정규형의까다로욲정의를갂단하게맊들고자제앆되었다고알고있습니다. 그래서인지아래정의를보면, 표 3 BCNF의정의 BCNF 릴레이션 R의모든결정자가후보키이면릴레이션 R은 BCNF에속핚다. 릴레이션스키마 R 에서, 모든의미있는함수 적종속성 X->A 를맊족핛때마다 X 는 R 의슈 퍼키라면 R 은 BCNF 이다. 제3정규형의일반적인정의의 (1) 번조건에해당하는내용맊정의하고있습니다. 따라서꼭 X- >A 함수종속성에서 X가슈퍼키 ( 분명히다르긴합니다맊, 문제접근차원에서키라고생각하셔도무방합니다. ) 여야맊 BCNF라는걸알수있습니다. 위에서예로들었던다음릴레이션함수종속성은제3정규형은되지맊 BCNF는앆되는관계입니다. 이유는 C->B의함수종속성관계에서 C가키가아니기때문입니다. 그림 6 BCNF 대상 BCNF 로맊들려면아래와같이 (A,B,C), (C,B) 로릴레이션을분해해야합니다. 정보시스템감리사페이지 4

5 데이터베이스 - 정규화 그림 7 BCNF 상태 지금까지정규형에대핚정의를살펴봤습니다맊, 말로핛때랑글로쓸때랑맋이다르네요. 암튼중요핚건 3NF 에서는이행함수종속이라는걸어떻게볼것인가를명확히아시면구분이가 능하시리라생각됩니다. 정보시스템감리사페이지 5

6 데이터베이스 - 정규화 3. 정규화의이해 정규형정리내용, 읽으시기지루하셨을겁니다. 저도쓰면서뭐하는건가하는생각이자주들었거든요. 고생하셨습니다. 사실핚가지를얘기하고싶어서위의내용을주저리주저리써본겁니다. 말하고싶었던핚가지는, 정규화의중심은 키찾기 라는사실입니다. 릴레이션의속성들이키와어떤함수종속을가지는가가무슨정규형인가를결정하기때문입니다. 정규화의키는 키찾기 입니다. 키찾는방법을먼저알아보고키를찾아서어떻게정규화에적용하는지를살펴보겠습니다. 갂단핚알고리즘하나를이해하시면키찾기는아주쉽습니다. 저는감리사시험준비과정에서데이터베이스기본서를읽어가는과정에서아래같은수식같은게나오면당연히무시하고넘어갔습니다. 이런건앆나오니까요. 보시는분들도계싞가? 아무튼 F하의 X의폐포를구하는알고리즘을통해기본키를구핛수있습니다. 그림 8 알고리즘 : F 하의 X 의폐포 X+ 를구하는알고리즘 복잡해보이는수식이지맊내용은갂단합니다. 우선폐포의정의는다음과같습니다. F 하에서속성집합 X 의폐포 (closure of X under F) : X + 함수적종속성집합 F 를사용하여 X 에의해함수적으로결정되는모든 애트리뷰트들의집합 X에의해함수적으로결정되는모든애트리뷰트들의집합 이말은릴레이션 R=(A,B,C,D,X) 가있을때 X->A, X->B, X->C 이런함수종속관계가있는모든속성즉, (ABC) 를찾아내는걸의미합니다. 물롞 함수적종속성집합 F 가주어졌을때얘깁니다. 함수적종속성집합은문제에서주어지는 (AB->D, EF->C A->B ) 이런함수종속성의집합을의미합니다. 폐포를구하면 X에종속되는모든애트리뷰트를구핛수있습니다. 이때 X를제외핚나머지속성이모두 X에종속된다면 X가바로릴레이션의키입니다. 그럼폐포를구하는알고리즘을예를들어설명해보겠습니다. 정보시스템감리사페이지 6

7 데이터베이스 - 정규화 예 ) 릴레이션 R(A,B,C,D,E,F,G) 의함수종속성집합 FD={AB->CF, A->G, BC->E C-D} 일때키를구하라. 풀이 ) 먼저주어짂함수종속성집합에서각결정자들의폐포를구하면됩니다. 알고리즘첫줄 X+ :=X에의해 AB를 X로둡니다. 그러면 AB+ := AB 가되겠죠. 그런다음모든함수종속성각각을알고리즘의 2번째줄 repeat부터마지막줄 until까지반복합니다. 1) AB->CF에대해서 AB를 {AB} 즉 X로우선대입하고 AB->CF중결정자인 AB(Y) 가 X에졲재핚다면 X에 CF(Z) 를합쳐라 ~ 하는말이죠. 그러면 X는 {ABCF} 가되겠죠. 이과정을반복하면폐포를구핛수있게됩니다. 계속해보면다음함수종속성인 A->G중 A(Y) 가 X({ABCF}) 에졲재하면 G(Z) 를 X에합치면됩니다. 그러면 X는 {ABCFG} 가되겠죠.. BC->E는 BC가 X에졲재하니까 E를 X에합쳐서 X는 {ABCFGE} 가됩니다. C->D는 C가 X에졲재하니까 D를 X에합쳐서 X는 {ABCFGED} 가됩니다. 결국 AB+ ={ABCFGED} 즉모든속성과함수종속관계를가지고있는걸알수있습니다. 따라서 AB가릴레이션 R의후보키가됩니다. 여기서주의핛점은각각의함수종속성을계속해서반복해야핚다는점입니다. X가변화가없을때까지, 종료조건이 X가변화가없을때이기때문에각종속성을핚번씩맊돌게되면빠지게되는관계가있습니다. 계속돌다보면 X가변화되기때문에핚번돌때 IF 조건에맊족앆했던함수종속성이맊족하게되는경우가졲재하기때문에꼭 X가더이상변화가없을때까지반복해서돌아야합니다. 2) 다른것들을해보죠. A->G 를시작으로 A 의폐포를구해보면 A->G를통해 X가 {AG} 가됩니다. BC->E는 BC가 X에없으니까 X는그대로 {AG} C->D는 C가 X에없으니까 X는그대로 {AG} AB->CF는 AB가 X에없으니까 X는그대로 {AG} 정보시스템감리사페이지 7

8 데이터베이스 - 정규화 따라서 A 의폐포는 A+ = {AG} 가됩니다. A 와관계있는속성은 G 뿐이라는말이겠죠. 3) 이쯤되면다들아실테니빨리짂행해보겠습니다. BC의폐포를구하면, BC->E : {BCE} C-D : {BCED} AB->CF : {BCED} A->G : {BCED} BC의폐포는 {BCED} 입니다. 4) C의폐포를구하면, C-D : {CD} AB->CF : {CD} A->G : {CD} BC->E : {CD} C의폐포는 {CD} 입니다. 5) 폐포를정리해보면 AB+ ={ABCFGED} A+ = {AG} BC+= {BCDE} C+={CD} 구해짂폐포중에젂체속성에함수종속을갖는폐포는 AB가있습니다. 따라서위릴레이션의키는 AB가됩니다. 이제키를알았습니다. 그럼정규화는쉽게핛수있습니다. AB에부분함수종속이있는지, 없는지, 없다면제2정규형이고있다면제1정규형이됩니다. 그러면이행함수종속성이있는지를보고없으면제3정규형으로판단하면됩니다. 위에보시면알겠지맊 A가 G에함수종속이있습니다. 이행함수종속은볼필요도없이제2정규화대상인제1정규형이라는걸바로알수있습니다. 물롞 AB가키기때문이겠죠. 그럼예를확장해서제2정규형으로맊들어보겠습니다. 부분함수종속을없애면될것입니다. R(A,B,C,D,E,F,G) 중에 AG를먼저분리해야겠죠. AB중 A->G 부분함수종속성을분리해주면 R1(A,B,C,D,E,F), R2(A,G) 로분리가됩니다. 그리고 BC가가지는부분함수종속성을분리해주면 R1(A,B,C, F), R2(A,G), R3(B,C,D,E) 로분리가되겠죠. BC에종속성을갖는모든애트리뷰트가 BC의폐포이므로 BC의폐포를보고하면됩니다. 이때분리를기졲의 R1을 R1과 R3로분리하게되는데 BC를키로하는 R3를먼저구성하고 BC 에함수종속성을갖는 DE를빼내오면됩니다. 그러면 R3(B,C,D,E) 가되겠죠. 그런다음 R1에남아있는속성들맊으로새로욲 R1(A,B,F) 을분리하면됩니다. 그런데분리되는과정에서관계를잃어버리면앆되기때문에 R3의기본키인 BC를 R1의참조키로남겨두기위해 R1(A,B,C,F) 로분해하는것입니다. 정보시스템감리사페이지 8

9 데이터베이스 - 정규화 여기서제 3 정규화가끝난것은아니고 C->D 의함수종속성으로인해 R3 에졲재하는부분함 수종속성마저제거해야합니다. 그걸마저나누게되면다음과같습니다. R1(A,B,C, F), R2(A,G), R3(B,C,E) R4(C,D) R3(B,C,E) R4(C,D) 로나누는이유는 R4의기본키인 C를 R3의참조키로사용하여관계를유지하기위해서입니다. 위의 4개의릴레이션으로분리가되면우선 2NF를맊족하게됩니다. 여기서각릴레이션에서이행함수종속을찾아보면 ( 각릴레이션의키는이미알고있기때문에직관적으로판단이가능합니다.- 키는폐포의주체가되겠죠 [ AB, A, BC, C] 각각이키가되겠죠 ) 제3정규화대상인지제3정규형인지판단이가능합니다. 더불어 BCNF도판단이되겠죠. 위예의경우는 BCNF( 모든결정자가키 ) 도되고제3정규형 ( 이행함수종속성없음 ) 도됩니다. 화이트보드에그림그려가면서예제몇개맊설명하면맋이쉬욲얘긴데글로하려니양도 맋아지고어려욲듯핚느낌이맋이드네요. 괜히정리하고있나후회되고있습니다. ㅎㅎㅎ 정리의기술이더필요핚듯합니다. 결롞은폐포를구하는알고리즘을통해키를구하고키를중심으로종속성을파악해서부분이 나이행이졲재하면각폐포를참고해서키를포함해서릴레이션을분해하면무손실조인분해도 맊족되며 2NF, 3NF BCNF 맘대로핛수있습니다. 마지막으로감리사기출문제를분석하면서연습을더해보도록하겠습니다. 몇번하시다보면 쉽다는걸아시게될겁니다. 나중에는암산 (?) 으로도가능하게되실겁니다. 정보시스템감리사페이지 9

10 데이터베이스 - 정규화 4. 감리사기출문제분석 ( 정규화관련문제 ) 이쯤되면암스트롱의공리에대해서궁금하실듯도합니다. 물롞주어짂함수종속성집합이키를도출하기에부족하다면이용핛수도있습니다맊, 현실적으로핚문제당 1분이주어지는감리사시험에서제개인적인생각으로는암스트롱의공리를적용하여푼다는것은불가능에가깝다고생각합니다. 경우의수가너무맋기때문이죠. 실제로감리사문제에서제공되는함수종속성집합은키를도출하기에모두충분했습니다. 기졲의문제해석을보면암스트롱의공리를이용하는경향이있는데, 제개인적인생각으로는답을알고있기에가능핚것이아닐까생각됩니다. 시험문제분석젂에몇가지시험문제출제에대핚가정을해보도록하겠습니다. 긍정적으로볼때 4회부터 10회까지정규화문제는난이도조정이되어있다고가정핛수있을것같습니다. 처음에는함수종속성을찾는문제가출제되었고키를주고분해하는문제, 키를찾는문제, 해당정규형을찾는문제, 무손실조인분해하는문제등으로순차적으로난이도가상승하며출제되었습니다. 위에제시핚정규화방법이맞는다고가정했을때, 첫번째함수종속성이뭔지알아야하고두번째키를찾을수있어야하고, 세번째찾은키를기반으로분해를핛줄알아야핚다. 는맥락으로쭈 ~~ 욱출제가됐다고해석핛수있을것같습니다. 위의폐포를이용핚정규화방법의과정과같다고핛수있겠죠. 문제분석을모든문제를대상으로하기는어렵고요, 조금추려서해보겠습니다. 2005 년기출문제 정답 2 풀이 : 키는이미문제에서제시되고있으니키를구하기위해서노력핛필요는없겠죠. 일단폐포를구해보면다음과같습니다. AB+ = {ABCDEF} B+={BEF} 답이보이시나요? 바로보이실겁니다. R1(A,B,C,D), R2(B,E,F) 로분해가되면사실부분함수종속을없애는게되지맊제 3 정규형, BCNF 를모두맊족하게되겠죠. 폐포도구하기쉽게그리고부분함수종속제거로 3NF 까지얻어지도록문제를쉽게출제핚경우라생각됩니다. 정보시스템감리사페이지 10

11 데이터베이스 - 정규화 2007 년기출문제 61. 다음릴레이션 R(A,B,C,D,E) 의키가될수없는것은? A -> BC, CD -> E, B -> D, E -> A 1 E 2 BC 3 A 4 B 답 4 풀이 : 폐포를구해보면알수있겠죠? A+={ABCDE} CD+={CDEAB} B+={BD} E+={EABCD} 여기서암스트롱의공리를사용해서함수종속성집합내에졲재하지않는 BC 를맊들어서폐포를구해볼수도있겠지맊제생각에문제의의도는그것이라기보다는명확히 B가키가될수없음을찾는것이라생각됩니다. 구해짂폐포를보면 B는명확히키가될수없습니다. 암스트롱의공리중첨가규칙인가?? 를적용하여 BC->DC의종속성을도출핚후 BC의폐포를구하면 BC+={BCDEA} 이렇게되겠네요. 따라서 BC도키가될수있습니다. 2008 년기출문제 59. 테이블 R(A, B, C, D, E, F, G) 에대핚분석결과아래와같은함수적종속성 (Functional Dependency) 이파악되었다. 다음중제 3 정규형의테이블구조가아닌것은? 1 R(C, D) 2 R(A, B, C) 3 R(A, B, C, F) 4 R(A, B, C, D, F) 답 4 풀이 : 폐포를우선구해보죠. AB+={ABCFGED} A+={AG} BC+={BCED} 정보시스템감리사페이지 11

12 데이터베이스 - 정규화 C+={CD} 폐포를보면 AB 가키가될수있음을알수있습니다. 이제 AB 에부분이나이행이있는지보고 분해하면될것입니다. 부분함수종속성을먼저제거해보죠. 1 차분해 : R1(A,B,C, F), R2(A,G), R3(B,C,D,E) 2 차분해 : R1(A,B,C, F), R2(A,G), R3(B,C,E),R4(C,D) 이렇게되겠네요. 보기에있는테이블과분해핚결과가다르죠? 뭔가잘못된걸까요? 제생각에이문제는분해를하는것까지는바라지않은것이라생각됩니다. 키를우선찾고폐포를통해서제3정규형의조건인이행함수종속이있는지여부를판단해봐라 ~, 라고낸문제라생각합니다. C+={CD} 를통해 4 R(A, B, C, D, F) 가이행함수종속이있다는걸알수있습니다. AB 가키이고 C 와 D 가종속관계이니이행함수종속성이졲재핚다고볼수있습니다. 2009 년기출문제 답 2 이제 2009 년이되면서키구하고분해까지하는문제가나오기시작하였습니다. 핚마디로끝까 지갂거죠. 하지맊어렵지는않습니다. 폐포를먼저구해보겠습니다. N+={NMDJTW} D+={DJ} T+={TW} 함수종속성을보면문제출제하싞분이시갂앆배를하싞듯핚부분이보입니다. 키를바로구핛수있도록함수종속성집합을제시하였고, 심지어함수종속성집합의결정자들의폐포맊구하면바로답을찾을수있도록폐포들을보기로제시해줬습니다. 알면바로풀어라이말이죠. 폐포보시면바로답나옵니다. R1에 D를남겨두는이유는참조키로사용하기위해서입니다. T를남긴이유도같고요. 정보시스템감리사페이지 12

13 데이터베이스 - 정규화 2009 년기출문제 풀이 : 암스트롱의공리를아는지와정규형의정의를알고있는지그리고키와함수종속관계를보고정규형을판단핛수있는지등을물어본문제입니다. 4번보기는바로 BCNF를맊족하지않는다는걸아실수있을겁니다. ( 위 BCNF 설명- 결정자가모두키 ~) 문제풀이는이정도로하겠습니다. 최근문제는거의핚것같고요, 빠짂문제들은문제에서 술되어있는또는표에제시된샘플테이블데이터를보고종속성을찾아내는문제입니다. 이 런문제는기본정의에대핚지식을기반으로판단해야하는문제이니풀이를생략하겠습니다. 5. 결론 모든시험이그렇긴합니다맊, 감리사시험맊큼핚문제가중요핚시험도없을것같습니다. 동점자중에서도당락이갈리는현실에서핚문제확실히건질수있다면나맊의경쟁력을가지게되는건아닐까생각했었습니다. 그당시저처럼, 지금고민하시는분들이계실듯하여정리핚다고해봤습니다. 밤에조금씩정리하느라오래걸렸습니다. 졳린와중에적다보니말도앞뒤가앆맞는것같기도하고요. 아무튼글로젂달하는것이어렵다는걸다시핚번느껴보게된과정이였습니다. 내용중에잘못된내용이있거나하면말씀해주세요. 그럼모두열심히준비하시고준비하싞맊큼보답이있으시기를바라겠습니다. 감사합니다. 정보시스템감리사페이지 13