본문 바로가기

Library/Database

최소 커버(minimal cover)와 3NF로의 분해 BCNF로 무손실 조인 분해하는 방식은, 3NF로 무손실 조인 분해하는 방식에 역시 그대로 적용될 수 있다(알고리즘의 수행 단계에서 3NF 릴레이션들을 모두 얻게 되면 수행을 종료하면 된다). 그러나, 이 방법은 항상 종속성 유지를 보장하지 않는다. 3NF 릴레이션들로 분해하는 알고리즘을 설명하기 전에, 최소 커버라는 개념이 필요하다. FD들의 집합 F에 대한 최소 커버는 다음 조건을 만족하는 FD들의 집합 G로 정의된다. 1. G에 속하는 모든 종속성들은 X → A의 형태이고, 이때 A는 단일 애트리뷰트이다. 2. 폐쇄 F+는 폐쇄 G+와 동등하다. 3. 만약 G의 종속성들을 몇 개 삭제하거나, 혹은 G의 어떤 종속성에 있는 애트리뷰트들을 몇 개 삭제한 후, G로부터 얻게 되는 종속성들의 집합 H에 대.. 더보기
정규화와 BCNF로의 분해 어떤 릴레이션 스키마가 BCNF에 속하지 않는다면, 이를 여러 개의 BCNF 릴레이션 스키마들로 무손실 조인을 유지하면서 분해하는 것은 항상 가능하지만, 불행히도 종속성 유지를 유지하면서 분해하는 방법은 가능하지 않다. 그러나, 여러 개의 3NF 릴레이션 스키마들로 종속성 유지와 무손실 조인을 모두 유지하면서 분해하는 것은 항상 가능하다. 함수 종속성들의 집합 F를 갖는 릴레이션 스키마 R을 여러 개의 BCNF 릴레이션 스키마들로 분해하는 알고리즘은 다음과 같다. 1. R이 BCNF에 속하지 않는다고 하자(이 말은, 주어진 FD가 해당 릴레이션에서 만족하지 않는다다는 이야기다). X ⊂ R이며, A는 R에 속한 단일 애트리뷰트이며, X → A는 BCNF를 위배하는 FD라고 하자. 이제 R을 R - A와 .. 더보기
Data Mining 데이터가 엄청나게 증가하면서, 필요한 정보를 찾아내는 것은 매우 어려워졌다. 데이터마이닝은 방대한 데이터베이스에서 앞으로의 활동에 대한 결정을 도와주는, 관심 있는 경향이나 패턴을 찾는 것이다. 데이터 웨어하우징은, 이것과 관련되어 있다. 데이터 마이닝(Data Mining) 툴은 사용자의 최소 입력으로 이러한 패턴을 구별해야 한다. 이러한 도구를 통하여 확인된 패턴들은 데이터 분석가들에게 다른 의사 결정 지원 툴들을 이용해서 계속적으로 좀 더 주의 깊게 조사할 수 있는 유용한 정보를 제공한다. 데이터 마이닝은 KDD(Knowledge Discovery from Data)라고 하기도 한다. 현대의 데이터베이스 시스템은 데이터 마이닝 툴을 제공해 주기도 한다 데이터 마이닝은 먼저 데이터를 모아야 하며(Da.. 더보기
Data Warehousing 데이터베이스는 크게 2가지 목적에서 사용된다. 즉, 트랜잭션 처리(OnLine Transaction Process), 분석(OnLine Transaction Analysis)이 그것이다. 예를 들어, 인터넷은 거대한 데이터베이스로 생각할 수 있다. 여기서 실제로 유용한 정보를 찾아내는 것이 중요한데, 여기서 의미있는 데이터를 얻어내기 위한 분석 따위를 의미하는 것을 OLAP라 할 수 있다. OLTP가 동적인 형태인 것에 비해서, OLAP는 좀 더 정적인 형태를 가진다. 즉, 데이터 웨어하우징은, 흩어져 있는 데이터들을 분석에 적합한 형태로 통합, 관리하는 것이라 할 수 있다. 그렇다면, 어떤 방식으로 데이터가 저장되는가? 보통 다차원 배열 형태로 저장된다고 할 수 있는데, 이것을 기하학적인 의미로 생각할.. 더보기
Lossless-join Decomposition 무손실 조인 분해라는 것은, 나뉘어진 2개의 관계를 합쳤을 때, 원래 가지고 있던 테이블에서 어떠한 데이터 손실이 없다는 것을 의미한다. 스키마를 정제할 때, 스키마를 분할하고 합칠 때 데이터의 손실이 발생한다면 이 작업은 잘못된 것이다. R을 어떤 관계 스키마라 하고, F를 R에 정의된 FD들의 집합이라 하자. R을 속성들의 집합 X와 Y로 구성된 두개의 스키마로 분해했을 때, F에 속하는 종속성을 만족하는 R의 모든 인스턴스 r에 대해, π(x)(r) join π(Y )(r) = r이 성립하면, 이러한 분해를 무손실 조인 분해라 한다. 물론, 새롭게 추가되는 정보도 없다. 중복성을 제거하기 위해 사용되는 분해는 반드시 무손실이어야 한다. 무손실인지 아닌지 검증하기 위해, 다음의 정리가 사용된다. R을.. 더보기
BCNF and 3NF 어떤 관계 스키마를 R이라 하고, R에 속하는 속성(attribute)들의 부분집합을 X라 하고, R에 속하는 어떤 속성을 A라고 하자. 이때 R에 주어진 함수 종족성들의 집합 F에 속하는 모든 FD X → A에 대해, 다음의 조건들 중 하나만 만족하는 경우, R을 제3정규형(Third Normal Form : 3NF)이라 한다. 1. A ∈ X (즉, 당연한 FD이다), 혹은 2. X는 수퍼 키, 혹은 3. A는 R의 어떤 키의 일부이다. 3NF의 정의는 BCNF와 유사한데 다른 점이라고는 세 번째 조건뿐이다. 따라서 모든 BCNF 관계 역시 3NF에도 속하게 된다. 세 번쨰 조건을 이해하려면 어떤 관계에서 키는 해당 관계를 유일하게 결정하는 속성들의 최소 집합임을 떠올리면 된다. 여기서 A는 반드시 .. 더보기
종속성 유지 분해 종속성 유지 분해란, 새로운 튜플(tuple)을 삽입하거나 혹은 어떤 튜플을 수정하고자 할 때, 단지 단일 관계에 속한 인스턴들 자체만 조사하기만 하면, 모든 FD들이 만족되는지를 검증해 줄 수 있다는 것을 의미한다(여기서 튜플을 삭제하는 경우는 어떠한 FD의 위반을 유발하지 않는다). 어떤 관계 스키마 R이 속성(attribute)들의 집합인 X와 Y로 구성된 두 개의 스키마로 분해되고, 이 R에 정의된 FD들의 집합을 F라고 하자. X에 대한 F의 프로젝션은 X에 속하는 속성들만을 포함하는 폐포 F+(F만이 아님)에 속하는 FD들의 집합으로 정의된다. 여기서 편의상 X에 대한 F의 프로젝션을 Fx로 표기하기로 한다. 이제 F+에 속하는 어떤 종속성 U → V가 Fx에 속하기 위해서는, U와 V에 속하.. 더보기
정규형(Normal Form) 어떤 관계 스키마가 주어졌을 때, 이 스키마가 좋은 설계인지, 혹은 그렇지 않으면 여러 개의 더 작은 관계들로 분해해야 하는지 판단할 필요가 있다. 따라서, 좋은 설계가 어떤 것인지 판단할 수 있는 기준이 필요한데, 이는 현재 주어진 스키마로부터 발생할 수 있는 문제점들이 무엇인지를 이해하는 것으로부터 출발한다. 이러한 기준을 제공하기 위해서 몇 개의 유용한 정규형(normal form)이 제안되었다. FD(functional dependency)에 기반한 정규형들은 제1정규형(first normal form : 1NF), 제2정규형(second normal form : 2NF), 제3정규형(third normal form : 3NF), 보이스-코드 정규형(Boyce-Codd normal form : B.. 더보기
함수 종속성(Functional Dependency) 함수 종속성(funational dependency, 이하 FD)은, 일종의 무결성 제약조건으로서, 키의 개념을 일반화한 것이다. 어떤 관계 스키마를 R이라 하고, X와 Y를 R에 속한 속성들의 집합이라 하자(X와 Y는 공집합이 아니다). 이제 R의 어떤 인스턴스 r에 속한 모든 튜플 t1, t2에 대해서 다음의 조건을 만족할 때 r은 FD X → Y를 만족한다고 한다. 만약, t1.X = t2.X이면, t1.Y = t2.Y이다. 즉, R에 있는 각각의 X 값이 R에 있는 정확하게 하나의 Y 값과 관련을 갖는다. 여기에서, t1.X는 튜플 t1을 X의 속성들로 프로젝션(projection)하는 것을 의미하는 것으로, 튜플 관계 해석의 표기법 t.a는 튜플 t의 속성 a를 지칭한다는 것을 자연스럽게 확장한.. 더보기
스키마 정제의 필요성 데이터베이스에서 데이터의 무결성을 제약하는 강력한 수단은 스키마다. 그러나, 데이터의 무결성을 제약하는 조건, 즉 스키마 자체에도 중복이 발생할 수 있으며, 검증 조건의 중복 저장은 잠재적으로 문제가 될 수 있다. 즉, 동일한 정보를 데이터베이스 내의 여러 곳에 반복해서 저장하는 것은 다음과 같은 여러 문제들을 가진다 : 1. 어떤 정보가 반복적으로 저장되는 중복 저장(redundant storage)의 문제 2. 반복 저장된 데이터 전체가 갱신되지 않는 경우, 데이터의 불일치가 발생하는 갱신 이상(update anormaly)의 문제 3. 어떤 새로운 정보를 저장하기 위해 이와 관련이 없는 다른 정보도 함께 저장해야 하는 삽입 이상(insertion anormaly)의 문제 4. 어떤 정보를 삭제하는 .. 더보기