엘비

2차 저장 공간

업데이트:

태그: ,

카테고리:

REF: fundamentals of database systems 7th edition

  • 이전까지는 top-down relational design 방식을 살펴봤다.
  • 이제 bottom-up(relational design by analysis)를 봐야할 차례이다.
  • bottom-up design에서 중요한 것은 Universal Schema를 Decomposition해나갈때, 특성들을 지켜야한다는 것이다.


  1. 각 relation의 정규형이 3NF이상이어야한다.
  2. functional dependency preservation property : 함수적 종속관계를 유지해야한다.
  3. lossless join property :이미 가지고 있던 정보가 사라져서는 안되며, 없던 정보가 생겨서도 안된다.


Relation Decomposition

정의

  • Relation Decomposition은 Bottom-up design 이다.


  • Input
    1. universal relation R = {A1, A2, … An}
    2. functional dependency set F
      • universal relation과 함수적 종속성 집합이 input이다.


  • Design Process
    1. universal relation R을 정규화해 여러 relation으로 분할한다.
      • R ==> D = {R1, R2, R3...Rm}
    2. 분할된 relation을 모두 union하면 원래의 모든 속성을 보존해야한다.
    3. 모든 relation은 3NF, BCNF여야한다.


문제점

  • 무작정 universal relation을 분할해 3NF, BCNF로 분할한다고 한들, 좋은 디자인이 될 수 없다.
  • 각 스키마를 tuple만 생각하면서 설계하면 spurious tuple이 생길수도 있고, tuple이 사라질수도 있다.
  • 특히, pk-fk가 아닌 속성으로 join했을때 이런 문제가 발생한다.
  • 따라서 분할된 relation을 모두 평가해야한다.


Dependency preserving condition

  • 함수적 종속성을 파악하기 위한 조건을 의미한다.
  1. 함수적 종속성에 의해 universal schema R을 R1, R2.. Rm으로 Decomposite하게되면,
    • 함수적 종속성 F의 FD는
      1. R𝑖에 직접적으로 나타나던가,
      2. R𝑖로부터 추론되어야한다.


  • 만약 추론됨으로서 함수적 종속성이 파악된다면, update마다 함수적 종속성을 확인해야함으로 성능상 이슈가 발생하게된다.


  1. D (R1, R2, ... Rm)의 Union⁺은 F⁺와 같아야만한다.



Relatioanl synthesis

  • 상향식 설계시

  • R -> D = {R1, R2, … Rm}이 있을때,

  1. F의 minimal cover G를 찾는다.
  2. G의 각 함수적 종속성 X->A𝑖에 대해서 스키마 Rｊ(X, A1, A2,…Am)을 생성한다.
  3. attribute preservation을 위해 남은 속성으로 Relation Rj을 정의한다.


-> 위 알고리즘은

  • minimal set G를 통해 Decomposition을 수행하므로,
    • 3NF를 보장하며
  • minimal set으로부터 나머지인 attribute를 새로운 relation을 정의해 보존하므로
    • dependency preserving을 만족한다.
  • 하지만, lossless join property 는 보장하지 못한다.

=> 따라서, lossless join propery를 테스트할 알고리즘이 필요하다



testing lossless join property

  • lossless join property란 join 연산시 정보의 추가나 소실이 없다는 것을 의미한다.
  • *(π<R1>(r), ... , π<Rm>(r)) = r
  • relation R의 모든 valid state r에 대해서
    • 모든 relation의 projection의 natural join이 r과 같다면 lossless join property이다.


lossless join property testing by step

  1. relation 갯수 * 전체 attribute 총 갯수의 matrix 생성
  2. matrix의 모든 값을 b로 채운다.
  3. 만약 relation이 해당 attribute를 가지고 있다면 a로 채운다.
  4. 각 함수적 종속성 X->Y에 대해
    • matrix의 X 값이 a인 쌍에 대해서
    • Y의 값의 둘 중 하나가 a라면
    • 둘 다 a로 바꾼다.
  5. 위 절차를 반복한 후 모든 값이 a인 행이 있다면 lossless join property를 만족한다.



finding minimal set

  • relational synthesis에서 minimal set을 찾는 방법에 대해서.
  1. 주어진 F를 minimal set이라고 가정하고 줄여나간다.
  2. 모든 FD를 하나씩 분해한다. (X->{A1, A2 ..}) => (X->{A1}, X->{A2} …)
  3. 각 X->A 에 대해서 G에서 이 함수적 종속성을 뺀 closure G⁺를 찾는다.
    • 만약 A가 여전히 G⁺에 있다면 방금 뺀 X->A를 삭제한다.
    • 중복되는 함수적 종속성을 삭제한다.
  4. 각 X->A에 대해서
    • X가 만약 1개 이상의 속성을 가진다면
    • X에서 B를 뺀 closure가 ∪ {(X−{B}) → A}}가 F와 같다면
    • X->A를 X-B->A로 치환한다.
    • 이 절차는 X의 LHS의 중복되는 속성을 삭제한다.

댓글남기기

참고