암스트롱의 공리

Armstrong's axioms

• 재귀성(reflexivity): 만약 Y가 X의 부분집합이면, X→Y이다.
• 부가성(augmentation): 만약 X→Y이면, XZ→YZ이다.
• 이행성(transitivity): 만약 X→Y이고 Y→Z이면, X→Z이다.
• 분해(decomposition): 만약 X→YZ이면, X→Y이고 X→Z이다.
• 합집합(union): 만약 X→Y이고 X→Z이면, X→YZ이다.
• 의사이행(pseudotransitivity): 만약 X → Y이고 YZ → W이면, XZ → W
• 자기결정(self-determination): 자기 자신은 자신에 의해 함수 종속적이다. 즉, X→X이다.

건전성과 완전성

이 가운데 재귀성·부가성·이행성 셋이 암스트롱의 공리이고, 분해·합집합·의사이행 규칙은 이 셋으로 유도된다. 공리는 건전(sound, 실제로 성립하는 함수 종속만 만든다)하고 완전(complete, 성립하는 함수 종속을 모두 만든다)하다.

성립하지 않는 추론

• XZ → YZ 이면 X → Y 는 성립하지 않는다. 부가성의 거꾸로가 아니다. 예: R(X, Y, Z) 에 (x1, y1, z1), (x1, y2, z2) 두 튜플이 있으면 XZ 값이 서로 달라 XZ → YZ 는 성립하지만, X 값이 같은 x1 인데 Y 값이 y1, y2 로 달라 X → Y 는 성립하지 않는다
• XY → Z 이면 X → Z 도 성립하지 않는다(왼쪽을 줄일 수 없다). 반대로 X → Z 이면 XY → Z 는 언제나 성립한다
• 분해는 오른쪽에서만 된다. X → YZ 이면 X → Y, X → Z 이지만, XY → Z 를 X → Z, Y → Z 로 쪼갤 수는 없다

같이 보기

• 함수적 종속성
• 데이터베이스 정규화
• 데이터베이스 후보 키