3 장. 관계데이터모델 관계모델 (relational model) 의기초 E/R 다이어그램에서관계설계로의변환서브클래스구조를릴레이션으로변환함수적종속성 (functional dependency) 함수적종속성에관한규칙들관계데이터베이스스키마설계다중값종속성 (multivalue

Transcription

1 3 장 : 관계데이터모델 Prof. Jin Hyun Son jhson@cse.hanyang.ac.kr Department of Computer Science & Engineering Hanyang University

2 3 장. 관계데이터모델 관계모델 (relational model) 의기초 E/R 다이어그램에서관계설계로의변환서브클래스구조를릴레이션으로변환함수적종속성 (functional dependency) 함수적종속성에관한규칙들관계데이터베이스스키마설계다중값종속성 (multivalued dependency) 2

3 관계모델의기초 릴레이션 (relation) 2 차원테이블 (table) 각요소들이원자적값을가지는튜플들의집합 애트리뷰트 title year length filmtype Star Wars color Mighty Ducks color 튜플 Wayne s World color 릴레이션 Movies 3

4 관계모델의기초 ( 계속 ) 애트리뷰트 (attribute) 릴레이션의각칼럼 (column) 에대한이름 title, year, length, filmtype 튜플 (tuple) 릴레이션의행 (row) (Star Wars, 1977, 124, color) 스키마 (schema) 릴레이션의이름과릴레이션의애트리뷰트들의집합 Movies (title, year, length, filmtype) 4

5 관계모델의기초 ( 계속 ) 도메인 (domain) 릴레이션의각애트리뷰트에연관된타입 ( 예 ) 애트리뷰트 title: 스트링 릴레이션의동일한표현 튜플들의순서는무관릴레이션은튜플들의집합 ; ( 튜플들의리스트가아님 ) 칼럼 ( 즉, 애트리뷰트와애트리뷰트값들 ) 들의순서도무관 year title filmtype length 1991 Mighty Ducks color Wayne s World color Star Wars color 124 5

6 관계모델의기초 ( 계속 ) 릴레이션사례 (instance) 스키마릴레이션의이름과애트리뷰트들의이름 릴레이션사례 릴레이션스키마에따른튜플들의집합 6

7 E/R 에서관계설계로의변환 E/R 설계를관계설계로변환 ( 기본과정 ) 엔티티집합을릴레이션으로변환 약 (weak) 엔티티집합이아닌엔티티집합에대하여, 동일한애트리뷰트들을갖는같은이름의릴레이션생성 관계성을릴레이션으로변환 관계성 R 에연결된엔티티집합들의키애트리뷰트를 R 에대한릴레이션의애트리뷰트로만든다. 관계성이애트리뷰트를가지면, 이애트리뷰트도릴레이션 R 의애트리뷰트로만든다. 7

8 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) E/R 에서관계설계로의변환 title year name address Stars-in Stars Movies Owns name address length filmtype Studios name Carrie Fisher Mark Hamill Harrison Ford address 123 Maple St., Hollywood 456 Oak Rd., Brentwood 789 Palm Dr., Beverly Hills title year studioname Star Wars 1977 Fox Mighty Ducks 1991 Disney Wayne s World 1992 Paramount 엔티티 Stars 에대한릴레이션 관계성 Owns 에대한릴레이션 8

9 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) E/R 에서관계설계로의변환 ( 계속 ) title year starname Star Wars 1977 Carrie Fisher Star Wars 1977 Mark Hamill Star Wars 1977 Harrison Ford Mighty Ducks 1991 Emilio Estevez Wayne s World 1992 Dana Carvey Wayne s World 1992 Mike Meyers 관계성 Stars-in 에대한릴레이션 9

10 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) 다중방향관계성을릴레이션으로변환 Stars Movies Contracts Studio of star Producing studio Studios Contracts (starname, title, year, studio0fstar, producingstudio) 10

11 E/R 에서관계설계로의변환 ( 계속 ) 릴레이션의결합 어떤관계성에대해서는테이블을생성할필요가없다. 다대일관계성 s key s 2 S t 2 r 1 t key T (t key, t 2 ) R (s key, t key, r 1 ) S (s key, s 2 ) R T ê S (s key, s 2, r 1, t key ) T (t key, t 2 ) R 에대한테이블을생성하는대신, S 에 R 의모든애트리뷰트들과 T 의키를포함 11

12 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) 릴레이션 Movies 와릴레이션 Owns 를결합 title year length filmtype studioname Star Wars color Fox Mighty Ducks color Disney Wayne s World color Paramount 12

13 E/R 에서관계설계로의변환 ( 계속 ) one-one 관계성 r 1 t key t 2 S (s key, s 2 ) T (t key, t 2 ) R (s key, t key, r 1 ) s key S R T ê s 2 S (s key, s 2, r 1, t key ) R 에대한테이블을생성하는대신, S 에 R 의모든애트리뷰트와 T 의키를포함» 그역도가능하다. R 과 T 에대한테이블을생성하는대신, T (t key, t 2 ) ê ST (s key, s 2, r 1, t key, t 2 ) 모든것을하나의테이블로표현 13

14 E/R 에서관계설계로의변환 ( 계속 ) 엔티티집합과 many-many 관계성을하나로결합 중복발생좋지않은설계임 ( 예 ) Movies 엔티티집합과 Stars-in 관계성을결합 title year length filmtype starname Star Wars color Carrie Fisher Star Wars color Mark Hammil Star Wars color Harrison Ford Mighty Ducks color Emilio Estevez Wayne s World color Dana Carvey Wayne s World color Mike Meyers 14

15 E/R 에서관계설계로의변환 ( 계속 ) 약엔티티집합을릴레이션으로변환 약엔티티집합 W 에대한릴레이션 아래애트리뷰트들로구성 W 의애트리뷰트들지원 (supporting relationship) 관계성으로연결되어있는엔티티집합 (strong entity set) 들의키애트리뷰트들지원관계성에있는애트리뷰트들 지원관계성 릴레이션을생성하지않음 15

16 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) Studios 와약엔티티집합 Crews number name addr Crews Unitof Studios Studios (name, addr) Crew (number, studioname) 16

17 E/R 에서관계설계로의변환 ( 계속 ) ( 예 ) 약엔티티집합으로표현된연결엔티티집합 salary Contracts salary Contracts Star_of Studio_of Movie_of filmtype Stars Studios Movies Stars Studios Movies length year name addr name addr title Contracts (starname, studioname, title, year, salary) 17

18 서브클래스를릴레이션으로변환 E/R 모델에서 isa 계층구조 루트엔티티집합이있다. 루트엔티티집합은 isa 계층구조에의해표현되는모든엔티티를식별할수있는키애트리뷰트를가진다. 한엔티티는 isa 계층구조에서서브트리에있는엔티티집합들의요소를가질수있다. 18

19 서브클래스를릴레이션으로변환 ( 계속 ) 세가지다른변환정책 E/R 모델관점객체지향관점 null 값을사용하여하나의릴레이션만생성 null 값 : 적절한값이없는경우에사용하는값 19

20 서브클래스를릴레이션으로변환 ( 계속 ) E/R 모델관점에따른변환 하나의객체는 isa 관계성으로연결된여러엔티티집합에속하는엔티티들에의해표현즉, 연결되어있는엔티티들이모여하나의객체를표현 각엔티티집합에대해하나의릴레이션. 릴레이션은엔티티집합에정의된모든애트리뷰트포함 각서브클래스에대한릴레이션은루트엔티티집합의키애트리뷰트를포함 F isa 관계성에대한릴레이션은만들지않음 20

21 서브클래스를릴레이션으로변환 ( 계속 ) 모든객체는루트엔티티집합의엔티티 서브클래스는루트엔티티집합에있는일부엔티티에추가적인특성표현 21

22 서브클래스를릴레이션으로변환 ( 계속 ) ( 예 ) isa 계층구조를 릴레이션으로변환 to Stars title year length filmtype Movies weapon Voices isa isa Movies (title, year, length, filmtype) MurderMysteries (title, year, weapon) Cartoons (title, year) Cartoons Murder- Mystery Voices (title, year, starname) 22

23 서브클래스를릴레이션으로변환 ( 계속 ) 객체지향관점에따른변환 객체는하나의클래스에만속한다. 객체는수퍼클래스의특성을상속받지만, 수퍼클래스의멤버는아니다. 각서브클래스는 하나의릴레이션으로변환. 그클래스에정의된모든특성과상속받는모든특성을포함 23

24 서브클래스를릴레이션으로변환 ( 계속 ) ( 예 ) 앞의 Movies 계층구조를고려하자. 영화의종류는다음네가지 단순히영화영화이면서 cartoon 영화이면서 murder-mystery 영화이면서, cartoon 이고 murder-mystery Movies (title, year, length, filmtype) MoviesC (title, year, length, filmtype) MoviesMM (title, year, length, filmtype, weapon) MoviesCMM (title, year, length, filmtype, weapon) Voices (title, year, starname) 24

25 서브클래스를릴레이션으로변환 ( 계속 ) NULL 값을사용하여한릴레이션으로결합 isa 계층에대해하나의릴레이션만생성 하나의릴레이션 isa 계층에있는모든특성들에대한애트리뷰트들을포함한객체는하나의튜플로표현이튜플은객체가가지고있지않은특성에대한애트리뷰트에는 NULL 값을가진다. ( 예 ) 앞의 Movies 계층구조를고려하자. Movie (title, year, length, filmtype, weapon) Voices (title, year, starname) 25

26 참고 : NULL 값 v 널 (null) 값 값이무엇인지정의할수없는경우사용될수있다. 알려지지않은값 (value unknown) 값이무엇인지알수없는경우» ( 예 ) 어떤영화스타의알려지지않은생일 적용불가능한값 (value inapplicable) 적합한값이존재하지않는경우» ( 예 ) 미혼인영화스타의배우자 보류된값 (value withheld) 값을알수있는자격이없는경우» ( 예 ) 공개되지않은전화번호 26

27 서브클래스를릴레이션으로변환 ( 계속 ) 여러방식들의비교 1) E/R 모델관점모든객체는루트엔티티집합에있음모든객체에대한질의루트엔티티집합에있는애트리뷰트만을사용하는경우 : 장점한객체의특성들이여러릴레이션에분산 서브클래스에있는객체에대한질의한객체에대한질의라도조인을필요로하는경우 : 단점 ( 예 ) murder-mystery 영화 A의 length와 weapon을찾아라 한객체에대한키가여러릴레이션에중복저장공간낭비 : 단점 27

28 서브클래스를릴레이션으로변환 ( 계속 ) 2) 객체지향관점각객체는특정엔티티집합에만속함 최소저장공간 : 장점 모든객체에대한질의클래스계층구조에관련된모든테이블들을검색 : 단점객체가속한릴레이션을모르는상황에서의질의 : 단점이객체를찾고자할때여러릴레이션들을탐색 ( 예 ) Roger Rabbit 객체가어느릴레이션에포함되어있는가? 즉, Movie, Cartoon, MurderMystery, Cartoon-MurderMystery 중어느릴레이션에포함되어있는가? 한객체의모든특성은한릴레이션에있음특정객체의애트리뷰트만을사용하는질의 : 장점 28

29 서브클래스를릴레이션으로변환 ( 계속 ) 3) NULL 값을사용하여한릴레이션으로결합 모든객체를한릴레이션에저장릴레이션이하나만있으므로간단 : 장점 NULL 값다수발생가능 저장공간낭비 : 단점 29

30 함수적종속성 함수적종속성 (functional dependency: FD) 의정의 릴레이션 R 에 A1, A2,..., An 과 B 라는애트리뷰트가있다고하자. R의두튜플이 A1, A2,..., An 에대해동일한값을가지면, B 에대해서도동일한값을가져야한다. A1A2... An B: A1A2... An 은 B 를함수적으로결정 (determine) 한다. 라고말한다. 애트리뷰트의집합 A1, A2,..., An 이여러애트리뷰트 B1, B2,..., Bn 을함수적으로결정하면, A1A2... An B1B2... Bm 30

31 함수적종속성 ( 계속 ) 두튜플에대한함수적종속성 (FD) 의의미 A s B s t u t 와 u 가 여기에서도 여기서 반드시동일해야 동일하다면, 한다. title year length title year length filmtype studioname title year starname (false) 31

32 함수적종속성 ( 계속 ) 릴레이션의키 애트리뷰트들의집합 {A1,A2,..., An} 이다음을만족하면릴레이션의키가된다. 애트리뷰트 A1,A2,..., An 는릴레이션 R 에있는다른모든애트리뷰트들을함수적으로결정즉, A1,A2,..., An 의값에대해서동일한값을가지는두튜플이존재할수없다. {A1,A2,..., An} 의어떤진부분집합도 R 의모든나머지애트리뷰트들을함수적으로결정할수없다. 즉, 키는최소 (minimal) 의애트리뷰트들로이루어진다. 32

33 함수적종속성 ( 계속 ) ( 예 ) 아래릴레이션 Movies 를고려해보자. Movies (title, year, length, filmtype, studioname, starname) 키 : {title, year, starname} 키가여러개존재하면 이중하나를주 (primary) 키로명시 33

34 함수적종속성 ( 계속 ) 수퍼키 (superkey) 키를포함하고있는애트리뷰트들의집합릴레이션의다른모든애트리뷰트를함수적으로결정한다. 그러나최소성 (minimality) 을만족할필요는없다. ( 예 ) 릴레이션 Movies 를고려해보자. {title, year, starname} 은수퍼키 {title, year, starname, length} 도수퍼키 34

35 함수적종속성 ( 계속 ) E/R 로부터변환된릴레이션의키발견 엔티티집합에서변환된릴레이션 엔티티집합의키애트리뷰트가릴레이션의키 35

36 함수적종속성 ( 계속 ) 이진관계성에서변환된릴레이션 R many-many 관계성연결된두엔티티집합양쪽의키가함께모여 R 의키애트리뷰트 ( 예 ) Stars-in 관계성 : Movies 와 Stars Stars-in (title, year, starname) many-one 관계성» 엔티티집합 E1 으로부터엔티티집합 E2 로 E1 의키애트리뷰트들만 R 의키애트리뷰트 ( 예 ) Owns 관계성 : Movies 로부터 Studios 로 Owns (title, year, studioname) 36

37 함수적종속성 ( 계속 ) one-one 관계성연결된엔티티집합중어느한쪽의키애트리뷰트도 R 의키애트리뷰트가될수있다. many-one 이나 one-one 관계성 릴레이션을만들지않아도된다. 37

38 함수적종속성에관한규칙 함수적종속성에관한규칙 분할 (splitting)/ 결합 (combining) 규칙단순 (trivial) 종속성규칙애트리뷰트의총합 (closure) 이행 (transitive) 규칙 Armstrong의공리 (axiom) 38

39 함수적종속성에관한규칙 ( 계속 ) 분할 / 결합규칙 분할규칙 A1A2... An B1B2... Bm 형태의함수적종속성은 A1A2... An Bi (i = 1, 2, L, B m ) 인종속성들의집합으로대체가능 결합규칙 A1A2... An Bi (i = 1, 2,..., Bm ) 인종속성집합들을하나의함수적 종속성 A1A2... An B1B2... Bm 으로대체가능 39

40 함수적종속성에관한규칙 ( 계속 ) 단순 (trivial) 종속성 종속성 A1A2... An B1B2... Bm 은우변이좌변의부분집합이면, 단순 (trivial) 종속성 A 에속하지않은 B 가적어도하나있으면, 비단순 (nontrivial) 종속성 B 에있는어떤애트리뷰트도 A 에속하지않으면, 완전비단순 (completely nontrivial) 종속성 C1C2... Ck : 우변에는있으나좌변에는없는모든애트리뷰트들 함수적종속성 A1A2... An B1B2... Bm 은 A1A2... An C1C2... Ck 와 동등 (equivalent) 하다. 40

41 함수적종속성에관한규칙 ( 계속 ) 애트리뷰트의총합 (closure of attributes) 애트리뷰트의집합 {A 1,A 2,..., A n } 함수적종속성 (FD) 들의집합 S S 의종속성을기반으로한 {A1,A2,... An} 의총합 (closure) 집합 S 의모든종속성을만족하는릴레이션이 A1A2... An B 역시만족하는애트리뷰트 B 들의집합 {A1,A2,... An} 이함수적으로결정하는모든애트리뷰트들의집합 {A 1,A 2,..., A n } 의총합 : {A 1,A 2,..., A n } + 로표시 41

42 함수적종속성에관한규칙 ( 계속 ) ( 예 ) 릴레이션 Movies (title, year, studioname, studioaddr) 함수적종속성 : title year studioname studioname studioaddr {title, year} + : {title, year}, {title, year, studioname}, {title, year, studioname, studioaddr} 42

43 함수적종속성에관한규칙 ( 계속 ) 총합계산알고리즘» 입력 = {A1,A2,..., An} 1. X 를최종적으로얻게되는답이라고하자. X 의초기상태를 {A1,A2,..., An} 로설정 2. B1,B2,...,Bm 은애트리뷰트집합 X 에존재하며 C는그렇지않은함수적종속성 B1B2... Bm C 를찾는다. 이러한 C 가있으면, C를집합 X 에추가 3. X 에새로운애트리뷰트가추가되지않을때까지단계 2를반복더이상의애트리뷰트추가가없을때의집합 X 가 {A1,A2,... An} + X 는단지증가할수만있으며릴레이션에있는애트리뷰트들의수는 유한하므로, 단계 2 가무한히반복되는일은없다. 43

44 함수적종속성에관한규칙 ( 계속 ) ( 예 ) 릴레이션 : R (A, B, C, D, E) 함수적종속성 : AB C, BC AD, D E, CF B {A, B} + : {A,B}, {A, B, C}, {A, B, C, D}, {A, B, C, D, E} 44

45 함수적종속성에관한규칙 ( 계속 ) A1A2... An B 가함수적종속성의집합 S로부터유도되는 (follow) 지를검사 {A1,A2,..., An} + 를계산 B 가 {A1,A2,..., An} + 에있으면 A1A2... An B 이다. ( 예 ) 앞의예제에서 AB D 가유도되는지를검사해 보자. {A, B} + 가 D 를포함하므로 AB D 는유도가능 45

46 함수적종속성에관한규칙 ( 계속 ) 총합과키 A1, A2,..., An 가릴레이션 R 에대한키인가를검사 {A1,A2,..., An} + 는 R 의모든애트리뷰트를포함 {A1,A2,..., An} 의어떤진부분집합 S 도,» S + 가 R 의모든애트리뷰트들을포함하지않음. 46

47 함수적종속성에관한규칙 ( 계속 ) 이행규칙 (Transitive rule) A 1 A 2... A n B 1 B 2... B m 와 B 1 B 2... B m C 1 C 2... C k 가성립하면, A 1 A 2... A n C 1 C 2... C k 도성립 ( 예 ) 릴레이션 Movies 를고려해보자. title year studioname studioname studioaddr title year studioaddr 47

48 함수적종속성에관한규칙 ( 계속 ) 총합알고리즘의증명 S: 함수적종속성 (FD) 들의집합 X = {A1,A2,..., An} + {A1,A2,..., An} 에총합알고리즘적용의결과 발견된 FD 는모두올바름 총합알고리즘의결과 X 에애트리뷰트 B 가있으면,» A 1 A 2... A n B 가반드시성립 올바른 FD 는모두발견 S 로부터유도 (follow) 가능한 A 1 A 2... A n B 가있으면,» 총합알고리즘의결과 X 에 B 가반드시포함 48

49 함수적종속성에관한규칙 ( 계속 ) 증명 : 발견된 FD 는모두올바름총합알고리즘결과 X 에애트리뷰트 D 가있으면,» A 1 A 2... A n D 가반드시성립 총합알고리즘의두번째단계적용횟수에대한귀납법 (induction) 으로증명 Basis: 두번째단계적용이없을때 D 는 A 1 A 2... A n 중의하나임 A 1 A 2... A n D 는단순 (trivial) 종속성 49

50 함수적종속성에관한규칙 ( 계속 ) Induction 귀납적가설 (inductive hypothesis): X 에 {B 1, B 2,..., B m } 가있으면,» A 1 A 2... A n B 1 B 2... B m 가성립 B 1 B 2... B m D 에의해 D 가 X 에추가되었다고가정하자. 귀납적가설에의해 A 1 A 2... A n B 1 B 2... B m 이므로, A 1 A 2... A n D 가성립 50

51 함수적종속성에관한규칙 ( 계속 ) 증명 : 올바른 FD 는모두발견총합알고리즘결과 X 에애트리뷰트 B 가없으면,» A 1 A 2... A n B 는 S 로부터유도되지않음 다음과같은릴레이션 I 가있음을보인다. S 에있는 FD 를모두만족한다. {A1,A2,..., An} + 에없는 B 에대해, A 1 A 2... A n B 는만족하지않는다. v 튜플 t 와 s 만을가진릴레이션 I 를고려하자. {A 1, A 2, A 3,..., A n } + 다른애트리뷰트들 t : s: 릴레이션 I 51

52 함수적종속성에관한규칙 ( 계속 ) 릴레이션 I 는 S 의모든 FD 를만족한다. S 에있지만릴레이션 I 에서만족되지않는함수적종속성 C 1 C 2... C k D 가있다고가정하자. 그림에서, 릴레이션 I 가 C 1 C 2... C k D 를만족하지않는다면 C 1 C 2... C k 는 {A1,A2,..., An} + 에있으며,» D 는 다른애트리뷰트들 에있어야한다. 총합알고리즘에따르면, C 1 C 2... C k 가 {A1,A2,..., An} + 에있고, C 1 C 2... C k D 가 S 에있으면,» D 도 {A1,A2,..., An} + 에반드시있어야한다. 따라서, 위와같은 C 1 C 2... C k D 는존재하지않는다. 52

53 함수적종속성에관한규칙 ( 계속 ) 릴레이션 I 는 {A1,A2,..., An} + 에없는 B 에대해, A 1 A 2... A n B 를만족하지않는다. 알고있는사항 A 1 A 2... A n 은단순종속성에의해 {A1,A2,..., An} + 에있으며, B 는 {A1,A2,..., An} + 에없다. 그림을보면, A 1 A 2... A n B 를만족하지않는것은명백함. 53

54 함수적종속성에관한규칙 ( 계속 ) 릴레이션의기저 (basis) 어떤릴레이션에있는모든함수적종속성들을유도할수있는함수적종속성들의집합최소기저 (minimal basis): 한릴레이션에있는모든종속성들을유도할수있는진부분집합을가지고있지않은기저 ( 예 ) A B, A C, B A, B C, C A, C B, AB C, AC B, BC A 최소기저들 : {A B, B A, B C, C B}, {A B, B C, C A} 등 최소기저를찾는방법은교재에언급되어있지않다. 54

55 Armstrong 의공리 Armstrong 의공리 : 함수적종속성들에관한올바르고 (sound) 완전한 (complete) 추론들의집합 재귀성 (reflexivity) {B 1,B 2,..., B m } Í {A 1,A 2,..., A n } 이면, A 1 A 2... A n B 1 B 2... B m 이성립한다. 이는단순 (trivial) 종속성에해당한다. 증가성 (augmentation) A 1 A 2... A n B 1 B 2... B m 가성립하면, 어떤애트리뷰트집합 C 1... C k 에대하여도 A 1 A 2... A n C 1... C k B 1 B 2... B m C 1... C k 이성립한다. 이행성 (transitivity) A 1 A 2... A n B 1 B 2... B m 와 B 1 B 2... B m C 1 C 2... C k 가성립하면, A 1 A 2... A n C 1 C 2... C k 도성립한다. 55

56 관계데이터베이스설계 이상 릴레이션의설계를잘못하였을때발생하는문제 ( 예 ) Movies (title, year, length, filmtype, studioname, starname) 릴레이션을고려해보자. 중복 (redundancy) 정보들이불필요하게여러튜플에반복되는현상 ( 예 ) 한영화의 length 와 filmtype 등이여러튜플에반복 56

57 관계데이터베이스설계 ( 계속 ) 갱신이상 (update anomaly) 여러튜플에중복되어나타나는정보가하나의튜플에서만변경되고다른튜플에서는갱신되지않은상태로남아있는문제 ( 예 ) Star Wars 의 length 를한튜플만변경 삭제이상 (deletion anomaly) 어떤값들의집합이공집합이되는경우, 부수적인결과로다른정보손실 ( 예 ) 스타이름이 Emlio Estevez 인튜플을삭제하면,» 영화 Mighty Ducks 에대한모든정보분실 57

58 관계데이터베이스설계 ( 계속 ) many 쪽정보를나타내는애트리뷰트» 다중값 (multi-valued) 애트리뷰트중복현상, 갱신이상 starname 애트리뷰트는다중값관계성으로부터생성 length, filmtype 정보등이반복 title year length filmtype studioname starname Star Wars color Fox Carrie Fisher Star Wars color Fox Mark Hamill Star Wars color Fox Harrison Ford Mighty Ducks color Disney Emilio Esteves Wayne s World color Paramount Dana Carvey Wayne s World color Paramount Mike Meyers 릴레이션 Movies 58

59 관계데이터베이스설계 ( 계속 ) 서로다른두개념을하나의테이블에저장» 특히, 두개의엔티티집합삭제이상 Movies 엔티티집합과 many-many 관계성을같이표현 Movies 엔티티집합과 Stars 엔티티집합을같이표현 59

60 관계데이터베이스설계 ( 계속 ) 릴레이션의분해 (decomposition) 이상문제들을해결하기위해릴레이션을분해. 스키마가 {A 1,A 2,...,A n } 인릴레이션 R 을스키마가 {B 1, B 2,..., B m } 과 {C 1, C 2,..., C k } 인릴레이션 S 와 T 로다음과같이분해가능 1. {A 1,A 2,...,A n } = {B 1, B 2,..., B m } U {C 1, C 2,..., C k } 2. 릴레이션 S 의튜플들 R 의모든튜플들을 {B 1, B 2,..., B m } 에대해프로젝션한결과 3. 릴레이션 T의튜플 R의모든튜플들을 {C 1, C 2,..., C k } 에대해프로젝션한결과 60

61 관계데이터베이스설계 ( 계속 ) ( 예 ) Movies (title, year, length, filmtype, studioname, starname) 다음두릴레이션들로분해 Movies1(title, year, length, filmtype, studioname) Movies2(title, year, starname) 61

62 관계데이터베이스설계 ( 계속 ) ( 예 ) Movies 분해계속 Movies1 title year length filmtype studioname Star Wars color Fox Mighty Ducks color Disney Wayne s World color Paramount Movies2 title year starname Star Wars 1977 Carrie Fisher Star Wars 1977 Mark Hamill Star Wars 1977 Harrison Ford Mighty Ducks 1991 Emilio Esteves Wayne s World 1992 Dana Carvey Wayne s World 1992 Mike Meyers 62

63 관계데이터베이스설계 ( 계속 ) 보이스-코드정규형 (Boyce-Codd Normal Form: BCNF) 릴레이션 R 이 BCNF에있다 (iff): 비단순종속성 A1A2... An B 가릴레이션 R 에있으면, {A1, A2,..., An} 은 R 의수퍼키 모든비단순종속성의좌변은수퍼키이어야한다. 릴레이션 R 이 BCNF 에있다 (iff) : 비단순종속성 A1A2... An B1B2... Bm 이릴레이션 R 에있으면, {A1, A2,..., An} 은 R 의수퍼키 63

64 관계데이터베이스설계 ( 계속 ) ( 예 ) Anomaly 가있는아래릴레이션 Movies 를고려해보자. many-many 관계성이 movie 정보와같이표현 title year length filmtype studioname starname Star Wars color Fox Carrie Fisher Star Wars color Fox Mark Hamill Star Wars color Fox Harrison Ford Mighty Ducks color Disney Emilio Esteves Wayne s World color Paramount Dana Carvey Wayne s World color Paramount Mike Meyers 이상이있는 Movies 키 : {tile, year, starname} title year length filmtype studioname 따라서 Movies 는 BCNF 형태가아니다. 다중값관계성이다른정보들과같이저장 64

65 관계데이터베이스설계 ( 계속 ) ( 예 : 릴레이션 Movies 계속 ) title year length filmtype studioname Star Wars color Fox Mighty Ducks color Disney Wayne s World color Paramount Movies1 키 : {tile, year} 키의어떤진부분집합도어떤 FD 의 determinant 가되지않음 따라서 Movies1 는 BCNF 형태 65

66 관계데이터베이스설계 ( 계속 ) BCNF 로의분해 적절한분해를반복하여한릴레이션스키마를다음의특성을만족하는애트리뷰트들의부분집합들로분리가능 각부분집합은 BCNF에있는릴레이션스키마본래의릴레이션에있는데이터들은분해후의릴레이션에정보의손실없이나타난다.» 즉, 분해된릴레이션들로부터원래의릴레이션을다시복원가능 66

67 관계데이터베이스설계 ( 계속 ) BCNF로분해하는알고리즘 1. X 가릴레이션 R 의수퍼키가아닌완전비단순종속성 X B 에대해, R 을 R 1 = (X, B) 와 R 2 = (R - B) 로분해 B 는 X 에함수적종속성이있는모든애트리뷰트들 B 에는비단순종속성이없다고가정 2. 이러한함수적종속성이존재하지않을때까지단계 1을반복 67

68 관계데이터베이스설계 ( 계속 ) ( 예 ) Movies (title, year, length, filmtype, studioname, starname) 릴레이션을고려해보자. 키 : {title, year, starname} title year length filmtype studioname 에서좌변이수퍼키가아니므로다음두릴레이션으로분해 Movie1(title, year, length, filmtype, studioname), Movie2(title, year, starname) 68

69 관계데이터베이스설계 ( 계속 ) ( 예 ) 이행종속성 (transitive dependency) 으로인한중복성 MovieStudio (title, year, length, filmtype, studioname, StudioAddr) 릴레이션을고려해보자 title year studioname /* 문제의근원 : 이행종속성 */ studioname studioaddr 키 : {title, year} title year length filmtype studioname studioaddr Star Wars color Fox Hollywood Mighty Ducks color Disney Buena Vista Wayne s World color Paramount Hollywood Addams Family color Paramount Hollywood 69

70 관계데이터베이스설계 ( 계속 ) ( 예 - 계속 ) MovieStudio1 title year length filmtype studioname Star Wars color Fox Mighty Ducks color Disney Wayne s World color Paramount Addams Family color Paramount MovieStudio2 studioname studioaddr Fox Hollywood Disney Buena Vista Paramount Hollywood 70

71 관계데이터베이스설계 ( 계속 ) ( 예 ) 이행종속성이연달아있는경우 MovieExec (title, year, studioname, president, presaddr) title year studioname, studioname president, president presaddr 키 : {title, year} president presaddr R1 = {president, presaddr}, R = {title, year, studioname, president} R 에서 : studioname president 이므로 R 은 BCNF 가아님. R2 = {studioname, president}, R3 = {title, year, studioname} 최종분해결과 : R1, R2, R3 BCNF 분해의결과는여러개있을수도있다. 71

72 참고 : BCNF 분해알고리즘 : Not Unique ( 예 ) MovieExec (title, year, studioname, president, presaddr) title year studioname, studioname president, president presaddr 키 : {title, year} studioname president R1 = {studioname, president}, R = {title, year, studioname, presaddr} R 에서 : studioname presaddr 이므로 R 은 BCNF 가아님. R2 = {studioname, presaddr}, R3 = {title, year, studioname} 최종분해결과 : R1, R2, R3 BCNF 분해의결과는여러개있을수도있다. 72

73 참고 : BCNF 분해알고리즘의복잡도 ( 예 ) R(A, B, C, D, E), F={A B, BC D, E B}» key: ACE R1={A, B}, R ={A, C, D, E} R in BCNF? No AC D is in F +» AC is not a key in R AC BC: augmentation from A B AC D: transitivity from AC BC and BC D may need to know all functional dependencies in F + BCNF 분해알고리즘의복잡도 : O(2 n ) 73

74 관계데이터베이스설계 ( 계속 ) 함수적종속성의추출 분해된결과에서함수적종속성찾기릴레이션 R 이분해되어릴레이션 S 와다른릴레이션생성 F 는릴레이션 R 에서성립하는함수적종속성들의집합 릴레이션 S 에서성립하는종속성찾기 S 의애트리뷰트집합의각부분집합 X 에대해, 애트리뷰트 B 가다음조건을만족하면 X B 가릴레이션 S 에서성립 1) B 는 S 에있는애트리뷰트 2) B 가 X + 에포함 B 는 X 에는없는애트리뷰트 O(2n) 74

75 관계데이터베이스설계 ( 계속 ) ( 예 ) R(A, B, C) 에서함수적종속성 A B와 B C 가성립. S(A, C) 가 R 을분해하여생긴릴레이션스키마의하나일때, S 에서성립하는종속성을찾아보자. {A} + = {A, B, C}. C 가 S 와 {A} + 에있으면서 C Ï {A} 이므로, A C 가성립 {C} + = {C} /* 이경우는고려할필요없음. */ 따라서 A C 가 S 에서성립하는유일한종속성이다. 75

76 관계데이터베이스설계 ( 계속 ) ( 예 ) R(A, B, C, D, E) 에서함수적종속성 A D, B E, DE C 가성립한다고할때, S(A, B, C) 에서성립하는종속성을찾아보자. {A} + = {A, D} /* S 에대한종속성만들어지지않음 */ {B} + = {B, E} /* S 에대한종속성만들어지지않음 */ {C} + = {C} /* S 에대한종속성만들어지지않음 */ {A, B} + = {A, B, C, D, E}: AB C AB C 가 S 에서성립하는유일한종속성이다. 76

77 관계데이터베이스설계 ( 계속 ) 분해된결과로부터정보를복원 ( 예 ) 부주의한분해 릴레이션이분해되었을때, 본래릴레이션은분해된릴레이션들의 조인 (join) 에의해서만복원가능 조인에대해서는 5 장에서기술 다음과같은스키마 {A, B, C} 를가진릴레이션 R 을고려 A B C A B B C 조인 A B C 정보의손실 77

78 참고 : 무손실조인분해 ( 보충설명 ) S = {S, A, T, I, P}, 함수적종속성 : S A, T I, T P s 1 a 1 t 1 i 1 p 1 s 1 a 1 t 2 i 2 p 2 s 2 a 2 t 3 i 1 p 3 s 1 a 1 i 1 s 1 a 1 i 2 s 2 a 2 i 1 t 1 i 1 p 1 t 2 i 2 p 2 t 3 i 1 p 3 S S 1 S 2 S ¹ S 1 S 2 s i t i u i s j t i u k 교재에없는내용 S S ¹ S 1 S 2 S 1 S 2 s i s j t i t i t i t i u i u k 78

79 참고 : 무손실조인분해 ( 계속 ) 무손실조인 (lossless join) 분해 r = (R1,..., Rn) 를 R 의분해라고하자. 릴레이션 R1,..., Rn 의조인이릴레이션 R 과항상같으면, r 를 R의무손실조인분해라고한다. 교재에없는내용 79

80 참고 : 무손실조인분해 ( 계속 ) 무손실조인분해검사 R1 과 R2 가 R 의분해라고하자. R1 Ç R2 R1 또는 R1 Ç R2 R2가성립하면 (iff), 무손실조인분해이다. ( 예 ) R = {A, B, C}, 함수적종속성 : A B R1 = {A, B}, R2 = {A, C}: 무손실 (lossless) R1 = {A, B}, R2 = {B, C}: 손실 (lossy) R1 = {A, C}, R2 = {B, C}: 손실 (lossy) 교재에없는내용 80

81 관계데이터베이스설계 ( 계속 ) 제 3 정규형 (Third Normal Form: 3NF) BCNF 분해에서종속성이보존 (preserve) 되지않을수도있다. ( 예 ) Bookings (title, theater, city) /* 한영화가현재어떤도시의어떤극장에서상영중 */ theater city title city theater 한영화관은하나의도시에위치 키 : {title, city}, {theater, title} 같은도시에있는두영화관이동일한영화를상영하지않는다. 81

82 관계데이터베이스설계 ( 계속 ) BCNF 분해 : {theater, city}, {title, theater} 이분해에서는 theater city 만이보존 theater Guild Park city Menlo Park Menlo Park theater title Guild The Net Park The Net 조인 theater city title Guild Menlo Park The Net Park Menlo Park The Net title city theater 를만족시키지않는다. 82

83 관계데이터베이스설계 ( 계속 ) 다음의조건을만족하는릴레이션 R 은제 3 정규형에있다. 비단순종속성 A1A2... An B 가있으면, {A1, A2,..., An} 가수퍼키이거나또는 B 가어떤키의멤버이다.» 이때 B 를 prime 또는키애트리뷰트라고한다. 무손실조인이며모든종속성을보존하는제 3 정규형의릴레이션들로항상분해가능릴레이션들이 BCNF 조건을만족하지않을때에는, 스키마에약간의중복성이남아있다는것을의미 theater city title Guild Menlo Park Star Wars Guild Menlo Park Rocky 83

84 참고 : 3NF 분해알고리즘 무손실조인이며모든종속성을보존하는 3NF 분해 F: 릴레이션 R 에있는함수적종속성들의집합 F 는 minimal basis 1. F 에있는각 X A 에대해, 릴레이션스키마 {X È A 1 È... È A m } 를생성.» 여기서 X A 1,..., X A m 는 F 에있는종속성들. 2. 어떤릴레이션스키마에도포함되지않은애트리뷰트가있으면, 이러한애트리뷰트들만으로구성된릴레이션을생성. 3. R 2 Ì R 1 인릴레이션 R 1 과 R 2 가있으면, R 2 를제거. ( 예 ) R(C, S, Z): CS Z, Z C 4. R 의키를포함하는릴레이션스키마가없으면, R 의키애트리뷰트만으로구성된릴레이션스키마를추가. 교재에없는내용 84

85 참고 : 3NF 분해알고리즘 ( 계속 ) 앞의 3NF 분해알고리즘은 Not Unique 알고리즘에서 F는 minimal basis minimal basis 는여러개있을수있음 앞의알고리즘의복잡도는 polynomia 교재에없는내용 85

86 참고 : 3NF 분해알고리즘 ( 계속 ) ( 예 ) R = {C, T, H, R, S, G} 함수적종속성 : C T, HS R, CS G, HR C, HT R 키 : {H, S} 3NF: {C, T}, {H, R, S}, {C, S, G}, {H, R, C}, {H, T, R} ( 예 ) R = {B, O, I, S, Q, D} 함수적종속성 : S D, I B, IS Q, B O 키 : {I, S} 3NF: {S, D}, {I, B}, {I, S, Q}, {B, O} BCNF: {S, D}, {I, B}, {I, O}, {I, S, Q} /* 종속성 B O 가보존되지않음 */ BCNF: {S, D}, {B, O} {I, B}, {I, S, Q} /* 종속성이보존됨. */ 교재에없는내용 86

87 다중값종속성 다중값 (Multivalued) 종속성 BCNF 에있는릴레이션이지만, 함수적종속성과는관련이없는중복이발생하는경우가있다. BCNF 스키마에서중복들이발생하는가장큰원인은, 둘이상의서로독립적인다중값애트리뷰트들이있기때문이다. ( 예 ) star 엔티티와 movie 엔티티의애트리뷰트들로구성된 StarsMovies (name, street, city, title, year) 을고려해보자. 한스타는주소가둘이상있을수있다고가정주소를 street 와 city 로표현스타엔티티와영화엔티티는 many-many 관계성 87

88 다중값종속성 ( 계속 ) ( 예 - 계속 ) name street city title year C.Fisher 123 Maple St. Hollywood Star Wars 1977 C.Fisher 5 Locust Ln. Malibu Star Wars 1977 C.Fisher 123 Maple St. Hollywood Empire Strikes Back 1980 C.Fisher 5 Locust Ln. Malibu Empire Strikes Back 1980 C.Fisher 123 Maple St. Hollywood Return of the Jedi 1983 C.Fisher 5 Locust Ln. Malibu Return of the Jedi 1983 각영화마다영화에출연하는스타의모든주소들이나타난다. 주소와영화의모든조합이나타난다. BCNF 에있지만중복성을가진다. 다섯개의모든애트리뷰트가모여유일한키형성 88

89 다중값종속성 ( 계속 ) ( 예 - 계속 ) (street, city), (title, year) 서로독립 name 에대해, 각각다중값을가짐 89

90 다중값종속성 ( 계속 ) 다중값종속성의정의 애트리뷰트 A1A2... An 로부터애트리뷰트 B1B2... Bm 으로의다중값종속성은다음과같이표기 A1A2... An B1B2... Bm A1A2... An B1B2... Bm 이릴레이션 R 에서성립하기 위한조건은다음과같다. 90

91 다중값종속성 ( 계속 ) 릴레이션 R 의 A 애트리뷰트값이일치하는임의의두튜플 t 와 u 가있을때, 다음을만족하는튜플 v 도있다. 1) v 의 A 애트리뷰트값이 t 와 u 의 A 값과일치 2) v 의 B 애트리뷰트값이 t 의 B 와일치 3) A 나 B 에속하지않는릴레이션 R 의나머지모든애트리뷰트에대하여 v 는 u 와일치 t A s B s others u v 91

92 다중값종속성 ( 계속 ) 다중값종속성이란, 릴레이션 R 에서 애트리뷰트집합 A( 예를들어, name) 의값을고정시킬때, 다른특정애트리뷰트집합 B( 예를들어, street city) 의값이 A 나 B 에속하지않는릴레이션 R 의나머지모든애트리뷰트들 ( 예를들어, title year) 의값에독립이라는것을의미 name street city title year C.Fisher 123 Maple St. Hollywood Star Wars 1977 C.Fisher 5 Locust Ln. Malibu Empire Strikes Back 1980 name street city 이면다음의두튜플도반드시있어야한다. (C.Fisher, 123 Maple St., Hollywood, Empire Strikes Back, 1980) (C.Fisher, 5 Locust Ln., Malibu, Star Wars, 1977) 92

93 다중값종속성 ( 계속 ) 다중값종속성에대한추론 단순 (trivial) 종속성규칙이행 (transitive) 규칙보완 (complementation) 규칙모든함수적종속성은다중값종속성 93

94 다중값종속성 ( 계속 ) 단순종속성규칙 A1A2... An B1B2... Bm 이어떤릴레이션에서성립하면, B 에 A 의 어떤애트리뷰트를추가한 C 에대해서 A1A2... An C1C2... Ck 도성립 A 에속하지않는모든 B 애트리뷰트들을 D 라고하면 A1A2... An D1D2... Dr 도성립 이행규칙 어떤릴레이션에서다중값종속성 A1A2... An B1B2... Bm 과 B1B2... Bm C1C2... Ck 가성립하면, A1A2... An C1C2... Ck 도성립 94

95 다중값종속성 ( 계속 ) 보완 (complementation) 규칙 릴레이션 R 에서다중값종속성 A1A2... An B1B2... Bm 이성립하면, R 은다중값종속성 A1A2... An C1C2... Ck 도만족여기서 C는 A 와 B 에속하지않는 R 의모든다른애트리뷰트들 모든함수적종속성은다중값종속성이다. A1A2... An B1B2... Bm 이면 A1A2... An B1B2... Bm 이다. 다중값종속성에서분할 / 결합규칙은성립하지않는다. ( 예 ) name street city 가성립» 그러나, name street 는성립하지않는다. 95

96 다중값종속성 ( 계속 ) 비단순 (nontrivial) 다중값종속성 A1A2... An B1B2... Bm 이다음조건을만족하면비단순. 1) B 의애트리뷰트중 A 에포함되는것이하나도없다. 2) A 와 B 를합한것이릴레이션 R 의모든애트리뷰트가아니다. 제 4 정규형 (Fourth Normal Form: 4NF) 다음을만족하면릴레이션 R 은 4NF 이다 A1A2... An B1B2... Bm 이 R 에있는비단순다중값 종속성이면, {A1,A2,...,An} 는 R 의수퍼키이다. 96

97 다중값종속성 ( 계속 ) 두개의독립적인다중값애트리뷰트가한릴레이션에있어서는않된다. 4NF 조건은 BCNF 조건과본질적으로같은형태이나, 함수적종속성대신다중값종속성을사용한다. 97

98 다중값종속성 ( 계속 ) 4NF 으로분해하는알고리즘 1. X 가릴레이션 R 의수퍼키가아닌각비단순다중값종속성 X A 에대해, R 을 R 1 = (X, A), R 2 = (R - A) 인 R 1 과 R 2 로분해 A 내부에는비단순다중값종속성이없다고가정. 2. 이러한비단순다중값종속성이없을때까지단계 1 을 반복 98

99 다중값종속성 ( 계속 ) ( 예 ) 다음릴레이션을고려해보자. name street city title year C.Fisher 123 Maple St. Hollywood Star Wares 1977 C.Fisher 5 Locust Ln. Malibu Star Wares 1977 C.Fisher 123 Maple St. Hollywood Empire Strikes Back 1980 C.Fisher 5 Locust Ln. Malibu Empire Strikes Back 1980 name street city 이 4NF 조건을위반하는것이므로» {name, street, city} 와 /* name street city 는 trivial */» {name, title, year} 로분해 /* name title year 는 trivial */ 99

100 다중값종속성 ( 계속 ) 정규형들사이의관계 3NF 에있는릴레이션 BCNF 에있는릴레이션 4NF 에있는릴레이션 특성 3NF BCNF 4NF 함수적종속성에따른 Most Yes Yes 중복성의제거 다중값종속성에따른 No No Yes 중복성의제거 함수적종속성의보존 Yes Maybe Maybe 다중값종속성의보존 Maybe Maybe Maybe 100