[Python] 프로그래머스 후보키

이 문제는 데이터베이스에서 관계형 데이터의 후보키(candidate key)를 찾는 문제입니다. 데이터베이스에서는 후보키(candidate key)라는 개념을 사용하여 테이블에서 튜플을 유일하게 식별할 수 있는 속성 또는 속성의 집합을 의미합니다. 이때 후보키는 다음 조건들을 만족해야 합니다

후보키란?

후보키는 릴레이션들의 속성 또는 속성들의 집합을 이용해서 유일하게 식별할 수 있는 값을 의미합니다.
후보키에 구성하기위한 필수적인 조건들이 있습니다.

1. 유일성(uniqueness): 테이블에서 모든 튜플에 대해 유일하게 식별할 수 있어야 합니다.
2. 최소성(minimality): 최소한의 속성 집합으로 테이블에서 유일하게 식별할 수 있어야 합니다.

유일성이란

유일성은 데이터베이스의 모든 ROW 중에 유일하게 존재해서 식별이 가능한 값을 의미합니다.

1. 학번: 모든 row의 값이 중복되지 않는것을 볼 수 있습니다. 이 같은 경우는 후보키가 가능합니다.
2. 이름: apeach가 중복되는 것을 볼 수 있습니다. 그렇기 때문에 하나의 속성으로는 후보키가 될 수 없습니다.
3. 전공: 전공도 마찬가지로 단일로는 후보키가 될 수 없습니다.
4. 학년: 학년도 중복이 많이 되죠?? 그렇기에 단일로는 될 수 없습니다.

하지만 여러개의 속성을 조합하면 유일성을 가질 수 있습니다.

EX)
[학번, 이름], [학번, 전공], [학번, 학년], [이름, 전공], [학번, 이름, 전공] ....

이렇게 다양한 조합이 있습니다. 그러면 이 모든 조합들은 후보키가 될 수 있을까요??

아닙니다.

후보키의 두번째 속성 최소성이 존재하기 때문입니다. 그러면 최소성에 대해서 확인해 보겠습니다.

최소성이란

최소성은 후보키로 선택된 속성(Attribute) 집합에서 어떤 속성 하나를 제외하거나 두 개 이상의 속성을 합쳐서도 여전히 유일성이 보장되는 속성 집합을 말합니다.

최소성 적용하기

[학번, 이름], [학번, 전공], [학번, 학년], [이름, 전공], [학번, 이름, 전공]

[학번, 이름] 조합은 학번 자체로도 유일성을 유지할 수 있기 때문에 최소성을 충족하지 못해 후보키로 사용할 수 없습니다.

[학번, 전공] 조합은 학번, 전공 단일은 유일성이 유지될 수 없지만 2개 이상 같이 사용하면 유일성 유지가 가능합니다.

결국은 위의 조합에서 사용할 수 있는 후보키는 [학번, 전공] 밖에 없습니다.

이렇게 후보키를 구할 수 있습니다.

후보키 의사 코드 작성

1. 모든 후보키의 조합을 만듭니다 -> combinations
   • 순서 상관 X
   • 중복 X
2. 구한 조합들 중, 각 속성 조합이 후보키인지 검사합니다.
3. 각 속성 조합이 후보키인지 검사하는 방법은 다음과 같습니다.
   • 속성 조합에 해당하는 데이터들을 추출하여 튜플의 리스트를 만듭니다. (중복 제거를 위해 set으로 변환)
   • set으로 변환한 튜플의 수가 relation의 레코드 수와 같다면, 해당 속성 조합은 후보키입니다.
   • 최소성을 만족하지 않는 속성 조합은 제외합니다.
4. 모든 후보키 조합을 검사한 후, 후보키의 개수를 반환합니다.

실제 코드 작성

from itertools import combinations
def solution(relation):
    col_size = len(relation[0])
    nums = range(col_size)
    candidates = []

    # 모든 후보키 조합 구하기
    for key_size in nums:
        for combination in combinations(nums, key_size+1):
            candidates.append(combination)

    # 각 조합에서 row들이 중복되는지 확인(유일성 확인)
    unique = []
    for candidate in candidates:
        lists = []
        for row in relation:
            rows = []
            for col in candidate:
                rows.append(row[col])
            lists.append(tuple(rows))
        if len(set(lists)) == len(relation):
            unique.append(candidate)

    # 유일성을 만족한 조합에서 부분집합이 있는지 확인(최소성 확인)
    answer = set(unique)
    for i in range(len(unique)):
        for j in range(i+1, len(unique)):
            if set(unique[i]).issubset(set(unique[j])):
                answer.discard(unique[j])
    return len(answer)