High-Dimensional Bayesian Optimization with Multi-Task Learning for RocksDB

  • RocksDB는 general-purpose embedded key-value store를 사용
  • 본 논문에서는 10개의 파라미터를 다양한 범위로 auto-tuning해서 Throughput을 개선한다.
  • 보통 optimizer들은 고차원 문제와 많은 training sample 요구를 한다.
  • 이 문제를 해결하기 위해 multi-task modeling과 clustering을 통한 차원 감소를 진행한다.
    • 일반적으로 최적화하는 것은 수렴 속도가 빠른 것과 다른 tuner들이 찾기 못하는 복잡한 세팅을 찾으려는 것이 목적
      • but, 계산량이 많아
      • 그래서 사전지식과 Bayesian Optimization loop를 사용해서 throughput을 최대화 하는 파라미터를 찾는다.

1. Introduction

  • RocksDB를 튜닝하는 것의 문제점
    • RocksDB는 30개가 넘는 파라미터를 가지고 있어서 configuration 조합들은 사용자에게 너무 많다
    • 하드웨어는 사용자가 선택한 configuration에 큰 영향을 준다.
    • 각 Application은 독특한 접근 패턴을 가지고 있다.
  • Auto-tuning으로 이러한 문제를 해결하려 함
    • 하지만 많은 training sample이 필요한데 이 training sample들은 restart and execution을 해야 함
    • 따라서 굉장히 효율적인 Bayesian Optimization(BO)를 사용. Process는 아래 그림과 같음

  • BO의 단점으로는 curse of dimensionality 때문에 고차원에서는 사용하기 어렵고, 계산량이 비싸다는 것이 단점이다.

    • 따라서 전문가의 지식을 추가해서 이 문제를 해소하고자 한다.
    • multiple target을 통한 최적화, sub-task decomposition을 통해 고차원 문제를 줄일 수 있다.
  • multiple target 통해 최적화 하는 것은 다양한 내부 component에 성능을 영향을 받기 때문에 이득이 있음

    • 예를 들어 RocksDB에서는 write throughput은 IO stalls에 bottleneck이 있지만 지연시간을 줄여서 향상 가능
  • 하지만 target을 늘리는 것은 계산량을 증가시키기 때문에 decomposition을 사용하도록 한다.

    • 모든 파라미터들을 한번에 다 고려하는 것이 아닌 일부 subset으로 decompose하고 target을 최적화함

  • 기여도는 다음과 같다.

    • BO에 structural knowledge를 주입해서 수렴속도를 낮춤
    • manual task decomposition을 사용해서 차원 문제를 해결함
    • default보다 최대 1.45배 향상시킴

2. Background

2.2 Bayesian optimization

  • Black-box function 최적화 문제를 해결하려는 효율적인 최적화 framework
  • 미지의 목적 함수(Surrogate Model)을 만들고 평가를 통해 최적의 하이퍼파라미터 조합을 탐색하는 것.
    • 즉 확률적인 추정을 수행하는 모델
    • 이 함수로 GP, Additive Kernel, TPE, RF를 사용하도록 한다.
  • Acquisition Function은 확률적 추정 결과를 바탕으로 유용한 다음 입력값 후보를 추천해 주는 함수를 지칭

3. Structured multi-task optimization

3.1 Overview

  • 메커니즘을 통해 전문가의 지식을 model에 넣고, 사용하들은 main objective를 최적화할 수 있는 low-level metrics를 확인할 수 있다.
  • multi-task learning을 통해 system component 간의 상호작용을 알 수 있고, 샘플에서 더 많을 것을 배워서 수렴에 필요한 관찰을 줄일 수 있다.
  • 파라미터의 manual grouping을 통해 최대 차원을 줄였고 수렴 속도를 빠르게 했다.

3.2 Problem space and assumptions

  • GP를 사용할 때, multivariate Gaussian distribution이고, 모든 점에서 미분 가능하다.

  • modeling space에서 랜덤하게 선택된 500개의 독립된 실험을 수행

  • 그 결과는 아래 그래프와 같음

3.3 Multi-task learning

3.3.1 Tasks

  • RocksDB 구조의 이해를 바탕으로 3개의 추가적인 objective를 선정함.
  • 이 objective들은 직접적으로 혹은 간접적으로 IOPS에 영향을 준다.
  • 선정한 3개는 다음과 같다.
    • WriteAmplification
    • ReadBlockGetP99
    • Level0Tolevel1P99

3.3.2 Intrinsic coregionalization model

  • 이 3가지 task를 더함에 따라 GP의 kernel 함수를 변경해야 한다.

    • Intrinsic Coregionalization Model kernel을 사용한다.

      • kx은 covariance kernel, kT는 task similarity kernel을 의미한다.
        • 따라서 서로 연관성을 파악하기 좋음
      • 각 output은 BO loop에서 최적화된다.
    • task간의 지식을 공유하는 능력과 각 task 별 충분한 sample이 있으면 수렴 속도를 빠르게 할 수 있다.

  • 수행하는 알고리즘은 다음과 같다.

  • scaling하고 normalizing 한다.
    • 이 것이 분포를 smooth하게 해서 더 쉽게 할 수 있도록 함

3.3.3 ICM challenges

  • ICM이 뭘 제공하긴 하는데 모르겠고, 이는 확장성에 문제가 있다고 함
    • 일반적으로 GP는 O(n3)인데, task가 생기면 O(Tn3)임
    • 그래서 Decomposition이 필요하다.

3.4 Decomposability through clustering

3.4.1 Decomposability in RocksDB

  • RocksDB의 large parameter space는 *"차원의 저주"* 와 높은 계산량을 발생시킨다.
    • multi-task 방법을 사용하면 계산량을 증가시켜서 차원의 저주 문제를 일부 해소 시킨다.
  • 계산량 문제를 줄이기 위해 RocksDB의 구조를 이용한다.
    • final observed metric = sum of multiple internal components performance. (functional decomposability)
    • 이는 차원을 줄이는 역할도 수행할 수 있다.

3.4.2 Manual clustering

  • 복잡도는 차원과 연관있기 때문에 이를 줄이도록 하자.
  • 500개의 random configuration trace를 이용하여, IOPS와 517 observable metric간의 correlation과 파라미터간의 correlation을 계산한다.
    • 이를 통해 cluster pool을 30개로 줄였고, 그 중 전문가 지식과 독립된 실험을 통해서 그림의 구조에 도달할 수 있었다.
  • parameter space를 decompose했고, 각 parameter cluster에 독립적인 GP를 사용했음
    • ICM Kernel을 사용한 GP로 지식을 공유하도록 했음

3.4.3 Unsupervised clustering

  • unsupervised clustering을 적용해서 이러한 cluster를 찾는다.
  • pass

4. Evaluation

4.1 Setup

  • IOPS를 최대화 하기 위해 10개의 RocksDB 파라미터를 튜닝한다.
  • parameter의 범위는 다음 표와 같다.

4.1.1 Experiment goals

  • tuner가 수렴 속도가 빠르고, IO throughput을 잘 하는 것이 중요하다.
  • Decomposability를 이용하는 cluster 기반의 multi-task의 효율성을 강조할 것이다.

4.1.2 Benchmark

생략

4.1.3 Libraries

생략

4.1.4 Hardware

생략

4.1.5 Baselines

4.2 IOPS performance

  • 제한된 계산량으로 IOPS를 최대화 하고 싶기 때문에 100개의 최적화 step만을 부여한다.

  • MultiTask를 사용할 때 1.38 ± 0.06 만큼의 성능 향상을 보였다.

4.3 Convergence

  • Multi-task와 cluster multi-task가 좀 더 빠르게 찾아냈다.
  • clustered MT는 10개의 iteration만에 1.3배의 향상을 보이는 config를 찾았다.(non-cluster-based는 60개의 iter가 걸림)
    • 대신 60 iter 후에는 더 좋은 것들을 찾을 수 있었지만 unstable 함
  • 일반 GP보다는 GP(BoTorch)가 더 좋음

5. Related work

pass

6. Conclusion

  • 이전에 tuning하는 과정은 고차원이라는 것이 문제였음.
  • 따라서 alternative observable metrics와 structural decomposability를 이용해서 수렴 속도를 빠르게 하고, 고차원을 줄임

문제:

풀이방법:

SELECT를 사용하는 기본적인 방법이다. FROM 절에서 출력하기 원하는 컬럼명을 SELECT에 명시해주면 그 컬럼 값들만 출력해준다.

1
SELECT ANIMAL_ID,NAME FROM ANIMAL_INS ORDER BY ANIMAL_ID;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59403

 

문제:

풀이방법:

아픈 동물 찾기 문제와 유사한 문제이다. 문제의 조건에서 젊은 동물은 INTAKE_CONDITION이 Aged가 아닌 경우를 뜻하기 때문에 WHERE INTAKE_CONDITION != 'Aged' 와 같이 조건문을 넣어주었고, ANIMAL_ID로 정렬을 하라고 했기 때문에 ORDER BY를 넣어주었다.

1
SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE INTAKE_CONDITION != 'Aged' ORDER BY ANIMAL_ID;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59037

문제:

풀이방법:

정해진 조건에 해당하는 값들을 찾아야 하는 문제이다. 정해진 조건에 해당하는 부분은 WHERE절로 만족시켜야 한다. 

따라서 WHERE INTAKE_CONDITION='SICK' 은 INTAKE_CONDITION이 SICK인 값들, 즉 아픈 동물들을 뜻하게 된다. 

일반 SELECT~FROM 절에 이 WHERE 조건을 추가하면 아픈 동물의 값들만 얻을 수 있다.

1
SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE INTAKE_CONDITION='Sick';
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59036

데이터베이스에서 보안과 권한관리를 하는 것은 매우 중요하다. 데이터베이스의 보안과 권한관리가 미약해서 손실된다면 데이터베이스를 소유한 조직의 운용데 큰 타격을 입기 때문이다. 따라서 권한이 없는 사람들이 함부로 데이터베이스에 접근을 하지 못하도록 하고, 일부 사용자들에게만 적절한 수준의 권한을 허가할 수 있는 기능을 가지고 있어야 할 것이다.

따라서 데이터베이스에는 이를 위해서 접근제어와 보안 및 권한 관리에 대한 기능을 제공하고 있다.

보안기법

데이터베이스에서 제공하는 보안 기법에는 크게 두 가지가 있다.

첫번째는 임의 보안 기법이다.

임의 보안 기법은 사용자들에게 특정 릴레이션, 투플, 또는 애트리뷰트를 지정된 모드로 접근할 수 있는 권한을 허가하고 취소하는 기법이다. 대부분의 상용 관계 DBMS에서 사용되는 기법으로 시스템 카탈로그에 누가 권한을 허가받았고 취소당했는가를 유지한다.

두번째는 강제 보안 기법이다.

강제 보안 기법은 데이터와 사용자들을 다양한 보안 등급으로 분류하고 해당 조직마다 적합한 보안 정책을 적용한다. 하지만 대부분의 상용 관계 DBMS는 이러한 보안 기법을 제공하지 않는다.

이러한 보안을 계속해서 유지하기 위해서는 데이터베이스를 관리하는 데이터베이스 관리자가 필요하다. 이 사람은 권한을 부여하거나 취소를 하고 사용자가 데이터베이스에 가한 모든 연산들을 기록할 수 있다. 만약 권한이 없는 사용자가 데이터베이스를 갱신했다는 의심을 들면 데이터베이스 감사를 실시할 수 있다.

권한 관리

사용자에게 권한을 주는 권리에는 다음과 같은 것들이 있다.

권한 허가

서로 다른 객체들에 대해서 다양한 권한들이 존재한다. 객체를 생성한 사람(소유한)은 모든 권한을 가지며 이 사람은 자신이 소유한 임의의 객체에 대해서 특정 권한을 GRANT문을 사용해서 다른 사용자에게 역할이나 권한을 허가할 수 있다.

GRANT 권한[(애트리뷰트들의 리스트)] ON 객체 TO {사용자|역할|PUBLIC} [WITH GRANT OPTION];


줄 수 있는 권한에는 SELECT, INSERT, DELETE, UPDATE, REFERENCES가 있으며 허가 받은 권한에 대해서만 사용을 할 수 있다. 또한 사용자가 WITH GRANT OPTION절과 함께 권한을 허가받으면 그 사용자도 다른 사용자에게 허가를 할 수 있는 권한을 가지게 된다. 만약 기본 릴레이션의 소유자가 다른 사용자들이 릴레이션에 직접 접근하지 못하게 하려고 하는 경우에는 릴레이션을 참조하는 뷰를 정의한 후 이 뷰에 대한 권한을 부여할 수 있다.

권한 취소

다른 사용자에게 허가한 권한을 취소하기 위해서는 REVOKE문을 사용한다. 또한 어떤 사용자가 다른 사용자에게 허가했던 권한을 취소한다면 권한을 취소 당한 사용자가 WITH GRANT OPTION을 통해서 다른 사용자에게 허가했던 권한들도 연쇄적으로 취소된다.

REVOKE {권한들의 리스트|ALL} ON 객체 FROM {사용자|역할|PUBLIC};

역할

여러 사용자들에 대한 권한 관리를 단순화하기 위해서 역할을 사용한다.

역할은 사용자에게 허가할 수 있는 연관된 권한들의 그룹으로서 이름을 가진다. 각 사용자는 여러 역할에 속할 수 있으며 여러 사용자들이 동일한 역할을 허가받을 수 있다. 또한 어떤 역할과 연관된 권한들에 변화가 생기면 그 역할을 허가받은 모든 사용자들은 자동적으로 즉시 변경된 권한들을 가지게 된다.

ER 스키마를 관계 모델의 릴레이션으로 사상

ER 모델을 릴레이션들로 사상하는 7개의 단계로 이루어진 알고리즘을 통해서 사상한다.

릴레이션으로 사상하는 7단계 알고리즘

단계 1: 정규 엔티티 타입과 단일 값 애트리뷰트

ER 스키마의 각 정규 엔티티 타입 E에 대해 하나의 릴레이션 R을 생성한다.

E에 있던 단순 애트리뷰트들을 릴레이션 R에 모두 포함시킨다.

복합 애트리뷰트는 복합 애트리뷰트를 구성하는 단순 애트리뷰트들만 포함시킨다.

E의 기본 키가 릴레이션의 R의 기본 키가 된다.

단계 1: 정규 엔티티 타입과 단일 값 애트리뷰트

단계 2: 약한 엔티티 타입과 단일 값 애트리뷰트

ER 스키마에서 소유 엔티티 타입 E를 갖는 각 약한 엔티티 타입 W에 대하여 릴레이션 R을 생성한다.

소유 엔티티 타입에 해당하는 릴레이션의 기본 키를 약한 엔티티 타입에 해당하는 릴레이션에 외래 키로 포함시킴

약한 엔티티 타입의 부분 키와 소유 엔티티 타입의 외래 키의 조합으로 기본 키를 구성한다.

 

단계 2: 약한 엔티티 타입과 단일 값 애트리뷰트

단계 3: 2진 1:1 관계 타입

관계 타입 R에 대하여, R에 참여하는 엔티티 타입에 대응되는 릴레이션 S와 T를 찾음

S와 T 중에서 한 릴레이션을 선택하고, 만일 S를 선택했따면 T의 기본 키를 S의 외래 키로 포함시킨다.

보통 관계 타입에 완전하게 참여하는 릴레이션을 S 릴레이션으로 선택한다. 관계 타입 R이 가지고 있는 단순 애트리뷰트들은 S에 대응되는 릴레이션에 포함시킨다.

두 엔티티 타입이 R에 완전하게 참여할 때는 하나의 릴레이션으로 합치는 방법도 가능하다.

단계 3: 2진 1:1 관계 타입

단계 4: 정규 2진 1:N 관계 타입

관계 타입 R에 대하여 N측의 참여 엔티티 타입에 대응되는 릴레이션 S를 찾는다. 1측의 엔티티 타입에 대응되는 릴레이션 T의 기본 키를 S에 외래 키로 포함시킨다.

S의 기본 키를 T의 외래 키로 포함시키면 정보의 중복이 발생한다.

단계 4: 정규 2진 1:N 관계 타입

단계 5: 2진 M:N 관계 타입

관계 타입 R에 대해서는 릴레이션 R을 생성한다.

참여 엔티티 타입에 해당하는 릴레이션들의 기본 키를 릴레이션 R에 외래 키로 포함시키고, 이들의 조합이 R의 기본키가 된다.

단계 5: 2진 M:N 관계 타입

단계 6: 3진 이상의 관계 타입

3진 이상의 관계 타입 R에 대하여 릴레이션 R을 생성하고, R에 참여하는 모든 엔티티 타입에 대응되는 릴레이션들의 기본 키를 R의 외래 키로 포함 시킨다. 만약 R에 참여하는 엔티티 타입들의 카디날리티가 1:N:N 이면 1의 릴레이션의 기본 키를 참조하는 외래 키를 제외한 나머지 외래 키들의 조합이 릴레이션 R의 기본키가 된다.

단계 6: 3진 이상의 관계 타입

단계 7: 다치 애트리뷰트

각 다치 애트리뷰트에 대하여 릴레이션 R을 생성한다.

다치 애트리뷰트를 애트리뷰트로 갖는 엔티티 타입이나 관계 타입에 해당하는 릴레이션의 기본 키를 릴레이션 R에 외래 키로 포함시킨다.

단계 7: 다치 애트리뷰트

 

데이터베이스 설계

 데이터베이스 설계는 요구사항 분석 - 개념적 설계 - DBMS의 선정 - 논리적 설계 - 스키마 정제 -물리적 설계 - 보안 설계 -구현 단계로 이루어져 있다.

 

데이터베이스 설계의 주요 단계

 

 개념적 데이터베이스 설계는 실제로 데이터베이스를 어떻게 구현할 것인가와는 독립적으로 정보 사용의 모델을 개발하는 과정이다. 사용자의 요구사항으로부터 개념적 스키마가 만들어지며 실세계의 엔티티, 관계, 프로세스, 무결성 제약조건을 나타내는 추상화 모델을 구축하며 주로 엔티티 - 관계(ER) 모델을 사용한다. 엔티티는 서로 구분이 되면서 조직체에서 데이터베이스에 나타내려는 객체를 의미한다.

 

 DBMS 선정은 기술적인 요인, 정치적인 요인, 경제적인 요인 등을 검토한 후에 DBMS를 선정한다.

 

 논리적 설계는 개념적 스키마에 알고리즘을 적용해서 논리적 스키마를 생성한다. 논리적 스키마를 나타내기 위해 관계 데이터 모델을 사용하는 경우에는 ER모델로 표현된 개념적 스키마를 관계 데이터베이스 스키마로 사상한다. 또한 더 좋은 스키마로 변환하기 위해서 정규화 과정을 적용한다.

 

 물리적 설계는 처리 요구사항들을 만족시키기 위해 저장 구조와 접근 경로 등을 결정한다. 응답 시간, 트랜잭션 처리율 등을 기준으로 성능을 평가한다.

 

ER 모델

 데이터베이스 설계를 용이하기 위해서 제안되었으며, 계속해서 이 모델이 강화되어서 현재는 EER(Enhanced Entity Relationship) 모델이 데이터베이스 설계 과정에 널리 사용되고 있다. 기본적인 구문으로 엔티티, 관계, 애트리뷰트가 있고, 기타 구문으로는 카디날리티 비율, 참여 제약조건 등이 있다.

 

엔티티

 엔티티는 독립적으로 존재하면서 고유하게 식별이 가능한 실세계의 객체를 의미하며 엔티티 타입은 동일한 애트리뷰트들을 가진 엔티티들의 틀이고, 엔티티 집합은 동일한 애트리뷰트들을 가진 엔티티들의 모임이다. 엔티티 타입으로는 크게 강한 엔티티 타입과 약한 엔티티 타입이 있다.

 

1. 강한 엔티티 타입은 독자적으로 존재하며 엔티티 타입 내에서 자신의 키 애트리뷰트를 사용하여 고유하게 엔티티들을 식별할 수 있는 타입이다.

 

2. 약한 엔티티 타입은 키를 형성하기에 충분한 애트리뷰트들을 가지지 못한 엔티티 타입으로 이 엔티티 타입이 존재하려면 소유 엔티티 타입이 존재해야하며 소유 엔티티 타입의 키 애트리뷰트를 결합해야만 약한 엔티티 타입을 식별할 수 있다. ER 다이어 그램에서 이중선 직사각형으로 표기하며 부분 키는 점선 밑줄을 그어서 표시한다.

 

ER모델에서 엔티티는 직사각형으로 표시한다.

애트리뷰트

 하나의 엔티티는 연관된 애트리뷰트들의 집합으로 설명된다. 엔티티는 독립적인 의미를 가지지만 애트리뷰트는 독립적인 의미를 가지지 않는다. ER 모델에서 타원형으로 나타내며 기본키의 경우에는 밑줄을 그어준다. 애트리뷰트와 엔티티 타입은 실선으로 연결한다.

 

1. 단순 애트리뷰트

 더 이상 다른 애트리뷰트로 나눌 수 없는 애트리뷰트로 ER 다이어그램에서 실선 타원으로 표현한다. ER 다이어그램에서 대부분의 애트리뷰트는 단순 애트리뷰트인 경우가 많다. 대부분의 단순 애트리뷰트는 단일 값 애트리뷰트이다. 단일 값 애트리뷰트는 각 엔티티마다 정확하게 하나의 값을 가지는 애트리뷰트를 의미한다. 예를 들면 학생의 학번 애트리뷰트는 어떠한 학생도 두 개 이상의 학번을 가지지 않으므로 단일 값 애트리뷰트이다.

단순 애트리뷰트와 복합 애트리뷰트

2. 복합 애트리뷰트

 두 개 이상의 애트리뷰트로 이루어진 애트리뷰트로 동일한 엔티티 타입이나 관계 타입에 속하는 애트리뷰트들 중에서 연관된 것을 모아놓은 것이다.

 

이 외에도 다치 애트리뷰트, 저장된 애트리뷰트, 유도된 애트리뷰트가 있다.

 

관계와 관계 타입

관계는 엔티티들 사이에 존재하는 연관이나 연결로서 두 개 이상의 엔티티 타입들 사이의 사상으로 생각할 수 있다. 요구사항에서 동사가 ER 다이어그램에서 관계로 표현되며 다이아몬드로 표기한다. 관계 타입은 관계의 특징을 기술하는 애트리뷰트들을 가질 수 있으며, 키 애트리뷰트를 가지지 않는다. 

 관계와 관계 타입에는 차수와 카디날리티라는 것이 있다. 차수란 관계로 연결된 엔티티 타입들의 개수를 의미하며 주로 2진 관계가 흔하다. 카디날리티 비율은 한 엔티티가 참여할 수 있는 관계의 수를 나타낸다. 흔히 1 : 1, 1:N, M:N으로 구분을 한다.

1. 1:1 관계

 E1의 각 엔티티가 정확하게 E2의 한 엔티티와 연관되고, E2의 각 엔티티가 정확하게 E1의 한 엔티티와 연관되었을 경우

ex) 각 학생에 대해 최대한 한 개의 노트북이 있고, 각 노트북에 대해 최대 한 명의 학생이 있다면 학생과 노트북 간의 관계는 1 : 1 관계이다.

 

2. 1:N 관계

 E1의 각 엔티티가 E2의 임의의 개수의 엔티티와 연관되고, E2의 각 엔티티는 정확하게 E1의 한 엔티티와 연관되면 이 관계를 1 : N 관계라고 하며 실세계에서 가장 흔히 나타나는 관계이다.

ex) 각 학생은 한 명의 지도교수님을 가지고 있지만, 지도 교수님은 여러 학생들을 가지고 있다.

 

3. M:N 관계

 한 엔티티 타입에 속하는 임의의 개수의 엔티티가 다른 엔티티 타입에 속하는 임의의 개수의 엔티티와 연관될 경우 M:N 관계이다.

ex) 각 학생은 여러 강의를 수강할 수 있고, 각 강의는 여러 명의 학생들을 가질 수 있으므로 M : N 관계이다.

 

 카디날리티 비율의 최솟값과 최댓값을 관계와 엔티티를 연결하는 실선 위에 (min, max) 형태로 표기한다. 어떤 관계 타입에 참여하는 각 엔티티 타입에 대하여 min은 이 엔티티 타입 내의 각 엔티티는 적어도 min번 관계에 참여함을 의미한다. max는 이 엔티티 타입 내의 각 엔티티는 최대한 max 번 관계에 참여함을 의미한다.

min = 0은 어떤 엔티티가 반드시 관계에 참여해야 할 필요는 없음을 의미하고, max=*는 어떤 엔티티가 관계에 임의의 수만큼 참여할 수 있음을 의미한다.

 

 이와 비슷한 개념으로 전체 참여부분 참여가 있다. 전체 참여는 어떤 관계에 엔티티 타입 E1의 모든 엔티티들이 관계 타입 R에 의해서 어떤 엔티티 타입 E2의 어떤 엔티티와 연관되는 것을 의미한다. 부분 참여는 어떤 관계에 엔티티 타입 E1의 일부 엔티티만 참여하는 것을 의미한다. 약한 엔티티 타입은 항상 관계에 전체 참여로 표시되며, 전체 참여는 ER 다이어그램에서 이중 실선으로 표시된다. 

 

 

 위의 내용들에서 사용한 표기법으로 수십 개 이상의 애트리뷰트를 설명한다면 매우 불편하므로 새발 표기법이라는 것을 사용한다.

 

새발 표기법

 

'Lecture Note > DataBase' 카테고리의 다른 글

[강의노트_DB]18. 릴레이션 정규화  (0) 2019.07.18
[강의노트_DB]17. 데이터베이스 설계-2  (0) 2019.07.16
[강의노트_DB]15. SQL-5  (0) 2019.07.09
[강의노트_DB]14. SQL-4  (0) 2019.07.04
[강의노트_DB]13. SQL-3  (0) 2019.07.02

관계 데이터 모델에서 지원하는 언어에는 크게 두 가지가 있다.

 

1. 관계 해석 - 원하는 데이터만 명시하고 질의를 어떻게 수행할 것인가는 명시하지 않는 선언적인 언어

 

2. 관계 대수 - 어떻게 질의를 수행할 것인가를 명시하는 절차적 언어, SQL의 이론적인 기초

 

관계 대수

기존의 릴레이션들로부터 새로운 릴레이션을 생성한다. 즉 입력값, 출력 값이 모두 릴레이션이다.

연산자들을 적용하여 보다 복잡한 관계 대수식을 점차적으로 만들 수 있음. 기본적인 연산자들의 집합으로 이루어짐.

결과 릴레이션은 또 다른 관계 연산자의 입력으로 사용될 수 있다.

 

관계 연산자들의 종류와 표기법

실렉션 연산자

σ<실렉션 조건>(릴레이션) 과 같이 사용하며 한 릴레이션에서 조건을 만족하는 투플들의 부분 집합을 생성한다.

단항 연산자이며 결과 릴레이션의 차수는 항상 입력 릴레이션의 차수와 같으며 카디날리티는 결과가 항상 작거나 같다.

 

실렉션 연산자 예시

프로젝션 연산자

π<애트리뷰트 리스트>(릴레이션) 과 같이 사용하며 한 릴레이션의 애트리뷰트들의 부분 집합을 구한다.

결과 릴레이션은 애트리뷰트 리스트에 명시된 애트리뷰트들만 가진다. 실렉션의 결과로는 중복 투플이 존재할 수 있지만 프로젝션의 결과에는 중복된 투플이 존재하지 않음

 

프로젝션 연산자 예시

집합 연산자

릴레이션이 투플들의 집합이기 때문에 기존의 집합 연산이 릴레이션에 적용된다. 집합 연산자에는 합집합, 교집합, 차집합이 있다. 집합 연산자의 입력으로 사용되는 두 개의 릴레이션은 합집합 호환이어야 한다.

 

*합집합 호환

두 릴레이션 R1(A1, A2,..., An)과 R2(B1, B2,... , Bm)이 합집합 호환일 필요충분조건은 n=m이고, 모든 1 <=i <=n에 대해 domain(Ai)=domain(Bi)이다.

 

합집합 연산자

릴레이션 1 ∪ 릴레이션 2와 같이 사용하며 릴레이션1에 있거나, 릴레이션2에 있는 투플들로 이루어진 릴레이션을 반환

결과 릴레이션에서는 중복된 투플들은 제거한다.

 

합집합 연산자 예시

교집합 연산자

릴레이션1 ∩ 릴레이션2 와 같이 사용하며 릴레이션 1, 릴레이션 2에 동시에 속하는 투플들로 이루어진 릴레이션

 

교집합 연산자 예시

차집합 연산자

릴레이션 R, S에 대해 차집합 R-S는 R에는 속하지만 S에는 속하지 않은 투플들로 이루어진 릴레이션

 

차집합 연산자 예시

릴레이션의 특성

릴레이션은 동일한 튜플이 두 개 이상 존재하지 않는다. 또한 한 튜플의 각 애트리뷰트는 원자값을 가진다. 즉 리스트, 집합, 튜플 값이 들어갈 수 없는 것이다.

 

릴레이션의 키

각 투플을 고유하게 식별할 수 있는 하나 이상의 애트리뷰트들의 모임이다. 

슈퍼 키

한 릴레이션 내의 특정 투플을 고유하게 식벽하는 하나의 애트리뷰트 또는 애트리뷰트 집합이다. 예를 들면 신용카드 회사에서 고객 릴레이션에서 (신용카드번호, 주소) 또는 (주민등록번호)가 해당 된다. 하지만 투플들을 고유하게 식별하는데 꼭 필요하지 않은 애트리뷰트들을 포함할 수 있다.

 

후보 키 

각 투플을 고유하게 식별하는 최소한의 애트리뷰트들의 모임이며 앞으로 추가될 값도 생각해야 한다. 모든 릴레이션에는 최소한 한 개 이상의 후보 키가 있다. 

 

기본 키

한 릴레이션에 후보 키가 두 개 이상 있으면 설계자 혹은 데이터베이스 관리자가 이들 중에서 하나를 기본 키로 선정 한다. 만약 자연스러운 기본 키를 찾을 수 없다면 인덱스 번호와 같이 인위적인 키를 추가할 수 있다.

 

대체 키

기본 키가 아닌 후보키를 뜻한다.

 

외래 키

어떤 릴레이션의 기본 키를 참조하는 애트리뷰트이다. 여기서 어떤 릴레이션은 다른 릴레이션일수도 있고, 자신의 릴레이션일수도 있다. 관계 데이터베이스에서 릴레이션들 간의 관계를 나타내기 위해서 사용된다.

 

 

관계 데이터 모델은 지금까지 제안된 데이터 모델 중에서 가장 개념이 단순한 데이터 모델 중 하나이다. 동일한 구조의 관점에서 모든 데이터를 논리적으로 구성하며, 선언적인 질의어를 통해 데이터 접근을 제공한다.

 

기본적인 용어

1. 릴레이션 : 2차원의 테이블

2. 레코드 : 릴레이션의 각 행

3. 튜플 : 레코드를 공식적으로 부르는 말

4. 애트리뷰트 : 릴레이션에서 이름을 가진 하나의 열

 

도메인(domain)

도메인은 한 애트리뷰트에 나타날 수 있는 값들의 집합을 뜻한다. 각 애트리뷰트의 도메인의 값들은 원자값을 가지고 동일한 도메인이 여러 애트리뷰트에서 사용될 수 있다. 프로그래맹 언어의 데이터 타입과 유사하다고 생각하면 된다.

 

차수(degree)

차수는 한 릴레이션에 들어 있는 애트리뷰트들의 수이다. 최소 차수는 1이여야 하며 차수가 자주 변하지는 않는다.

 

카디날리티(cardinality)

카니날리티는 릴레이션의 투플 수이다. 유효한 릴레이션은 카니날리티 0을 가질 수 있다.(릴레이션에 아무런 값이 없는 것이 가능하므로) 카디날리티는 시간이 지남에 따라 자주 변할 수 있다.

 

널값(null value)

'알려지지 않음' ,  '적용할 수 없음'을 나타내기 위해 널값을 사용한다. 하지만 널값이 숫자 0을 의미하거나 공백을 의미하지는 않는다. 

 

릴레이션 스키마(relation schema)

릴레이션의 이름과 릴레이션의 애트리뷰트들의 집합이다. 릴레이션을 위한 틀이라고 생각하면 된다. 기본키 애트리뷰트에는 밑줄로 표시해 준다.

릴레이션 이름( 애트리뷰트 1 , 애트리뷰트 2,....., 애트리뷰트 N)과 같이 표기한다.

 

릴레이션 인스턴스(relation instance)

릴레이션에 어느 시점에 들어 있는 튜플들의 집합이다. 시간의 흐름에 따라 계속 변화한다.

 

+ Recent posts