기능상속성

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "기능적 종속성" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2012년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

관계형 데이터베이스 이론에서 기능 종속성은 데이터베이스에서 관계된 두 속성 사이의 제약조건이다.다시 말해 기능 의존성은 관계에서 두 속성 사이의 제약조건이다.Given a relation R and sets of attributes ${\displaystyle X,Y\subseteq R}$, X is said to functionally determine Y (written X → Y) if and only if each X value in R is associated with precisely one Y value in R; R is then said to satisfy the functional dependency X → Y. Equivalently, the projection ${\displaystyle$$\Pi _{X,Y}R}$은(는) 함수, 즉 Y는 X의 함수다.^[1][2]간단히 말해 X 속성의 값을 알고 있는 경우(그 값을 x라고 말함), x에 해당하는 Y 속성의 값은 x를 포함하는 R의 어떤 튜플에서 찾아내어 결정할 수 있다. 관습적으로 X를 결정요인 집합, Y 종속 집합이라고 한다.기능상속성 FD: X → Y는 X의 부분집합일 경우 사소하다고 한다.

즉, 종속성 FD: X → Y는 Y의 값이 X의 값에 의해 결정된다는 것을 의미한다.X의 동일한 값을 공유하는 두 개의 튜플은 반드시 Y의 동일한 값을 가질 것이다.

기능 의존성의 결정은 관계 모델에서 데이터베이스 설계와 데이터베이스 표준화 및 탈원형화에 있어 중요한 부분이다.A simple application of functional dependencies is Heath's theorem; it says that a relation R over an attribute set U and satisfying a functional dependency X → Y can be safely split in two relations having the lossless-join decomposition property, namely into ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}$$(R)=R}$ 여기서$$ Z = U - XY는 속성의 나머지 부분이다.(속성 집합의 개념은 데이터베이스 이론에서 단지 대등분만으로 관습적으로 표시된다.)이 맥락에서 중요한 개념은 후보 키로, 관계에서 모든 속성을 기능적으로 결정하는 최소 속성 집합으로 정의된다.기능 의존성은 속성 도메인과 함께 사용자 도메인에 부적절한 데이터를 가능한 한 많이 시스템에서 제외할 수 있는 제약 조건을 생성하기 위해 선택된다.

논리적 함축성의 개념은 다음과 같은 방식으로 기능 의존성에 대해 정의된다: 기능 의존성 집합 ${\displaystyle \Sigma}$은 논리적으로$$ 다른 종속성 ${\displaystyle \Gamma}$을 암시한다$.$ 만약 σ ${\displaystyle \Sigma}}$의 모든 의존성을 만족하는 R도 충족한다면$$.$\gamma {\displaystyle \mathrm{}}$ ${\displaystyle \Gamma }$로부터 decidation$;$ 이것은 보통 ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \models }$ ⊨ ⊨ ⊨ {$$\ $\displaystyle$ \$Sigma \models \Gamma }}}}$이라고 쓰여 있다$.$ 기능적 의존성에 대한 논리적 함의 개념은 암스트롱의 공리로 알려진 건전하고 완전한 유한한 공리화를 인정한다.

예

자동차

차량과 엔진의 용량을 추적하기 위한 시스템을 설계한다고 가정합시다.각 차량에는 고유한 차량 식별 번호(VIN)가 있다.차량 엔진의 용량이 두 개 이상인 것은 부적절하기 때문에 VIN → EngineCapacity라고 표기할 수 있다.(이 경우, 차량은 하나의 엔진만 가지고 있다고 가정할 때)반면 엔진용량 → VIN은 엔진용량이 같은 차량이 많을 수 있기 때문에 부정확하다.

이러한 기능 의존성은 EngineCapacity 속성이 후보 키 VIN과 관련하여 배치된다는 것을 암시할 수 있다.그러나 그것이 항상 적절한 것은 아닐 수도 있다.예를 들어, 그러한 기능 의존성이 전이적 기능 의존성 VIN → VehicleModel 및 VehicleModel → EngineCapacity의 결과로 발생하는 경우, 이는 정상화된 관계를 초래하지 않을 것이다.

강의

이 사례는 기능 의존성의 개념을 예시한다.대학생들이 각각 교무조교(TA)를 배정받는 1개 이상의 강의를 방문하는 상황을 모델링한 것이다.더 나아가 모든 학생이 어느 학기에 재학 중이고 고유한 정수 ID로 식별된다고 가정해 보자.

학생증	학기	강의	TA
1234	6	수치 방법	존
1221	4	수치 방법	스미스
1234	6	비주얼 컴퓨팅	밥
1201	2	수치 방법	피터야.
1201	2	물리학 II	사이먼

이 표의 두 행에 동일한 학생이 있을 때마다ID, 그들은 또한 같은 학기 가치를 가지고 있다.이러한 기본적인 사실은 기능상 의존성에 의해 표현될 수 있다.

• 학생증 → 학기.

학생이 다른 학기 가치를 갖는 행을 추가하면 기능 의존성 FD는 더 이상 존재하지 않게 된다는 점에 유의하십시오.이는 FD를 무효화할 수 있는 값을 가질 수 있기 때문에 데이터에 의해 FD가 함축되어 있다는 것을 의미한다.

다른 비경쟁적 기능 의존성을 다음과 같이 식별할 수 있다.

• {학생아이디, 강의} → TA
• {학생ID, 강의} → {TA, 학기}

후자는 세트 {학생}이(가)라는 사실을 표현한다.ID, 강의}은(는) 관계의 슈퍼키다.

사원부서모델

기능 의존성의 전형적인 예는 직원 부서 모델이다.

사원ID	사원명	부서ID	부서명
0001	존 도	1	인적 자원
0002	제인 도	2	마케팅
0003	존 스미스	1	인적 자원
0004	제인 구달	3	판매의

이 사례는 데이터의 단일 표현에 복수의 기능 의존성이 내재된 예를 나타낸다.직원은 한 부서의 구성원만 될 수 있기 때문에 해당 직원의 고유 ID가 부서를 결정한다는 점에 유의하십시오.

• 사원ID → 사원명
• 사원ID → 부서ID

이 관계 외에도 테이블은 비키 속성을 통한 기능 종속성을 가지고 있다.

• 부서 ID → 부서명

이 사례는 FD 직원 ID → 부서 ID가 존재하더라도 직원 ID가 부서 ID를 결정하는 논리적인 열쇠가 되지 않는다는 것을 보여준다.데이터의 정규화 과정은 모든 FD를 인식하고 설계자가 데이터에 기초하여 보다 논리적인 테이블과 관계를 구성할 수 있게 한다.

기능상속성의 속성 및 공리화

X, Y, Z가 관계 R의 속성 집합임을 감안할 때, 기능 의존성의 몇 가지 속성을 도출할 수 있다.가장 중요한 것 중에는 보통 암스트롱의 공리라고 불리는 다음과 같은 것들이 있다.^[3]

• 반사율:Y가 X의 부분 집합이면 X → Y
• 확대:X → Y이면 XZ → YZ
• 전이성:X → Y, Y → Z이면 X → Z

"유연성"은 $단지{\displaystyle }$ X${\displaystyle }$→ ${\displaystyle \varnothing }$ ${\displaystyle X\rightarrow \varnot },$즉 다른 두 가지가 적절한 추론 규칙인 실제 공리학으로, 보다 정확하게 다음과 같은 통사적 결과의 규칙을 발생시킬 수 있다.^[4]

${\displaystyle \vdash X\오른쪽 화살표 \varnoth}$
$(\displaystyle X\오른쪽 화살표 Y\vdash XZ\오른쪽 화살표 YZ}$
${\displaystyle X}$→ ${\displaystyle Y}$, ${\displaystyle Y}$→ ${\displaystyle Z}$⊢ ${\displaystyle X}$ → ${\displaystyle Z}$ ${\displaystyle$ X$\오른쪽$ 화살표 $Y,Y\오른쪽$ 화살표 $Z\vdash X\오른쪽$ 화살표 $Z$

이 세 가지 규칙은 기능 의존성에 대한 건전하고 완전한 공리화다.이러한 공리화는 추론 규칙의 수가 유한하기 때문에 때로는 유한하다고 설명되기도 하는데,^[5] 추론의 공리와 규칙은 모두 도식이며, 이는 X, Y, Z의 범위가 모든 지상 용어(속성 집합)에 걸쳐 있다는 것을 의미한다.^[4]

확대와 전이를 적용함으로써 두 가지 추가 규칙을 도출할 수 있다.

• 유사성:X^[3] → Y, YW → Z이면 XW → Z
• 구성:X → Y, Z → W이면 XZ → YW^[6]

또한 암스트롱의 공리로부터 조합과 분해 규칙을 도출할 수 있다.^[3][7]

X → Y, X → Z인 경우에만

기능상속성폐쇄

폐쇄는 본질적으로 기능 의존성을 이용하여 주어진 관계에 대해 알려진 값의 집합으로부터 결정될 수 있는 전체 값 집합이다.하나는 암스트롱의 공리를 사용하여 반사성, 증대, 과도성 등의 증거를 제공한다.

Given ${\displaystyle R}$ and ${\displaystyle F}$ a set of FDs that holds in ${\displaystyle R}$: The closure of ${\displaystyle F}$ in ${\displaystyle R}$ (denoted ${\displaystyle F}$⁺) is the set of all FDs that are logically implied by ${\displaystyle F}$.^[8]

속성 집합 닫기

$F{\displaystyle }$ ${\displaystyle F}$에 대한 속성 X 집합의 폐쇄는 $F{\displaystyle }$ ${\displaystyle F}$을(를) 사용하여 X에 의해 기능적으로 결정된 모든 속성의 집합 X이다⁺$.$⁺

예

FDs의 다음 목록을 상상해보라.우리는 이 관계에서 A에 대한 폐쇄를 계산할 것이다.

1. A → B
2. B → C 3. AB → D

폐쇄는 다음과 같을 것이다.

a) A → A (암스트롱의 반사능력에 의한)
b) A → AB (1 및 (a))
c) A → ABD (b), 3, 암스트롱의 전이성)
d) A → ABCD (by (c), 2)

따라서 폐쇄는 A → ABCD이다.우리는 A의 폐쇄를 계산함으로써 A의 폐쇄가 관계의 모든 데이터 값이기 때문에 A도 좋은 후보 키라는 것을 검증했다.

커버 및 동등성

커버

정의:${\displaystyle }$$G{\displaystyle }$ ${\displaystyle G}$의 모든 FD를 $F{\displaystyle }$ ${\displaystyle F}$에서 추론할 수 있는$$ 경우$$ $F{\displaystyle }$ ${\displaystyle$ $G$$}$을(를) 포함하며$,$ $G{\displaystyle }$ ${\displaystyle G}$ ∆$$⁺ $F{\displaystyle }$ ${\displaystystyle F}$을(를$)$로 $한다{\displaystyle }$.
모든 기능 의존성 집합에는 표준 커버가 있다.

FD 두 세트의 등가성

만약 F{F\displaystyle}+)G{G\displaystyle}+스키마 R{R\displaystyle}이상 FDs F{F\displaystyle}G{G\displaystyle}의 두세트, F{F\displaystyle}≡ G{G\displaystyle},. 만약 F{F\displaystyle}≡ G{G\displaystyle}, F{\displaysty 같다.르$F}$은(는) $G{\displaystyle }$ ${\displaystyle G}$을(를) 위한 표지로, 그$$ 반대의 경우도 마찬가지다.즉, 기능 의존성의 등가 집합을 서로 커버라고 한다.

비중복 커버

A set ${\displaystyle F}$ of FDs is nonredundant if there is no proper subset ${\displaystyle F'}$ of ${\displaystyle F}$ with ${\displaystyle F'}$ ≡ ${\displaystyle F}$. If such an ${\displaystyle F'}$ exists, ${\displaystyle F}$ is redundant.${\displaystyle }$$F{\displaystyle }$ ${\$$displaystyle$ $F}$이(가) G ${\displaystyle G}$의 덮개이고$$ $F$ ${\displaystyle F}$이(가) 비중복인 경우$$ F ${\displaystyle G}$의 비중복 커버다$$.
An alternative characterization of nonredundancy is that ${\displaystyle F}$ is nonredundant if there is no FD X → Y in ${\displaystyle F}$ such that ${\displaystyle F}$ - {X → Y} ${\displaystyle \models }$X → Y. Call an FD X → Y in ${\displaystyle F}$ redundant in ${\displaystyle F}$ if ${\di$$splaystyle F}$ $$- {X → Y} $\models {\displaystyle }$ ${\displaystyle \models }$ → Y.

정규화에 대한 응용 프로그램

히스의 정리

An important property (yielding an immediate application) of functional dependencies is that if R is a relation with columns named from some set of attributes U and R satisfies some functional dependency X → Y then ${\displaystyle R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$ where Z = U − XY.Intuitively, if a functional dependency X → Y holds in R, then the relation can be safely split in two relations alongside the column X (which is a key for ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$) ensuring that when the two parts are joined back no data is lost, i.e. a functional dependency provides 두 개의 작은 관계에서 R의 무손실 결합 분해를 구성하는 간단한 방법.이 사실은 때때로 히스 정리라고 불리기도 한다; 그것은 데이터베이스 이론의 초기 결과들 중 하나이다.^[9]

Heath's theorem effectively says we can pull out the values of Y from the big relation R and store them into one, ${\displaystyle \Pi _{XY}(R)}$, which has no value repetitions in the row for X and is effectively a lookup table for Y keyed by X and consequently has only one place to update the Y corresponding to each X unlike각 X의 복사본이 잠재적으로 많은 "큰" 관계 R. 업데이트에 동기화되어야 하는 Y의 복사본이 있는 "큰" 관계 R.(이러한 중복 제거는 많은 변화가 예상되는 OLTP 컨텍스트에서는 장점이지만, 대부분 쿼리를 수반하는 OLAP 컨텍스트에서는 그다지 큰 변화가 없다.)히스의 분해는 큰 테이블 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle X_{}}$ ${\displaystyle Z{}_{}}$( R${\displaystyle }$) ${\displaystyle \Pi _{XZ}(R)}$의 나머지 부분에서는 X만 외부 키로 작용하게 한다$.$

그러나 기능 의존성은 외부 키의 형식주의인 포함 의존성과 혼동해서는 안 된다.정상화에 사용되더라도 기능 의존성은 하나의 관계(구성표)에 대한 제약조건을 나타내는 반면, 포함 의존성은 데이터베이스 스키마의 관계 스키마 사이의 제약조건을 나타낸다.더욱이, 두 개념은 의존성의 분류에서도 교차하지 않는다. 기능 의존성은 동등하게 생성되는 의존성인 반면, 포함 의존성은 튜플 생성 의존성이다.관계 스키마 분해(정상화) 후 참조 구속조건을 시행하려면 새로운 형식주의, 즉 포함 의존성이 필요하다.히스의 정리에 따른 분해에서는 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle X_{}}$ ${\displaystyle Z_{}}$${\displaystyle {}_{}}$( ${\displaystyle R}$) ${\$$displaystyle$ $\$$Pi$에 X의 일부 값이 없는$$ 튜플 삽입을 막을 수 있는 것은 없다$.$

정상형식

정상 양식은 표의 "선호성"을 결정하는 데이터베이스 정규화 수준이다.일반적으로 세 번째 정규 형태는 관계형 데이터베이스에 대한 "좋은" 표준으로 간주된다.^{[citation needed]}

정규화는 데이터베이스를 업데이트, 삽입 및 삭제 이상 징후로부터 해방시키는 것을 목표로 한다.또한, 새로운 값이 관계에 도입되었을 때, 데이터베이스에 최소한의 영향을 미치고, 따라서 데이터베이스를 사용하는 애플리케이션에 최소한의 영향을 미치게 한다.^{[citation needed]}

집합에 따라 해석할 수 없는 함수

기능 의존성의 집합 S는 세트의 속성이 다음과 같은 세 가지라면 복구할 수 없다.

1. S의 기능적 의존성의 각 오른쪽 집합은 오직 하나의 속성만을 포함한다.
2. S의 기능적 의존성의 각각의 왼쪽 세트는 되돌릴 수 없다.왼쪽 집합에서 어떤 속성 하나라도 줄이면 S의 내용이 바뀐다는 뜻(S는 일부 정보가 손실된다).
3. 기능 의존도를 줄이는 것은 S의 내용을 변화시킬 것이다.

이러한 속성에 대한 기능적 의존성의 집합을 표준적 또는 최소적이라 부르기도 한다.입력으로 제공된 일부 입력 집합 S'와 동등한 기능 의존성의 집합 S를 찾는 것을 S'의 최소 커버를 찾는 것을 말한다: 이 문제는 다항 시간 내에 해결할 수 있다.^[10]

참고 항목

• 체이스(알고리즘)
• 포함 종속성
• 종속성 결합
• 다중값 종속성(MVD)
• 데이터베이스 정규화
• 첫 번째 정규 형태

참조

추가 판독값

• Codd, E. F. (1972). "Further Normalization of the Data Base Relational Model" (PDF). ACM Transactions on Database Systems. San Jose, California: Association for Computing Machinery.

외부 링크

• Gary Burt (Summer 1999). "CS 461 (Database Management Systems) lecture notes". University of Maryland Baltimore County Department of Computer Science and Electrical Engineering.
• Jeffrey D. Ullman. "CS345 Lecture Notes" (PostScript). Stanford University.
• Osmar Zaiane (June 9, 1998). "Chapter 6: Integrity constraints". CMPT 354 (Database Systems I) lecture notes. Simon Fraser University Department of Computing Science.