이해

• 관계 데이터베이스에서 Relation의 Tuple을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 아래 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness): 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality): 유일성을 가진 키를 구성하는 속성 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 예를 들어, “학번” 속성 하나로 릴레이션에 있는 모든 튜플이 유일하게 식별된다고 할 때, [“학번”, “이름”]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, “이름” 속성을 제외하여도 “학번” 속성 하나로 유일성을 만족하기 때문에 [“학번”, “이름”]은 후보 키가 될 수 없다.
• 릴레이션을 나타내는 문자열 배열 relation이 주어질 때, 후보 키의 개수를 return하라.

계획

• 속성의 모든 조합에 대해 완전 탐색을 진행하여 각 조합이 후보키가 될 수 있는지를 확인한다.
• 각 조합에 대해 유일성과 최소성을 체크한다.
• 유일성 체크
  • 속성 조합에 해당하는 튜플들을 set에 모두 넣은 후 set의 원소 개수가 전체 튜플의 개수와 같은 지 확인한다.
• 최소성 체크
  • 속성의 조합을 탐색하는 동안 속성의 조합이 이전의 속성의 조합들을 통해 구한 후보키들 중에서 아무것도 포함하지 않는 경우에 대해서만 탐색해준다.

실행

from itertools import combinations
def solution(relation):
    n, m = len(relation), len(relation[0])
    candidates = []
    for i in range(1, m+1):
        
        for comb in combinations(range(m), i):
            flag = True
            for candidate in candidates:
                if len(list(candidate - set(comb))) == 0:
                    flag = False
                    break
            if not flag:
                continue
            
            tuple_set = set()
            
            for record in relation:
                temp = []
                for c in comb:
                    temp.append(record[c])
                tuple_set.add(tuple(temp))
            if len(list(tuple_set)) == n:
                candidates.append(set(comb))
    return len(candidates)

개선

• set을 list로 바꾸지 않고 len함수를 사용하여 set의 원소의 개수를 구한다.
• 파이썬의 List Comprehension 기능을 사용하여 코드를 더 간단하게 만든다.

from itertools import combinations
def solution(relation):
    n, m = len(relation), len(relation[0])
    candidates = []
    for i in range(1, m+1):
        
        for comb in combinations(range(m), i):
            flag = True
            for candidate in candidates:
                if len(candidate - set(comb)) == 0:
                    flag = False
                    break
            if not flag:
                continue
            tuple_set = set([tuple([record[c] for c in comb]) for record in relation])

            if len(tuple_set) == n:
                candidates.append(set(comb))
    return len(candidates)

회고

• 구현하는 과정이 살짝 까다로웠고, for문을 여러 개 중첩시켜서 구현하다 보니 제대로 풀고 있는 지 의구심이 들었다. 하지만 매개변수인 문자열 배열 relation의 column과 row길이가 아주 작으므로 for문 3개 정도 중첩하는 것은 크게 걱정하지 않아도 됐었다. 자신있게 풀어야 겠다.

• set에 원소로 배열을 넣었더니 다음 아래와 같은 error가 출력됐다. TypeError: unhashable type: ‘list’

  • 파이썬에서 set에 포함되는 원소들은 해시 가능해야 하고, list는 mutable하기 때문에 해싱이 불가능하다. 따라서 list를 tuple로 변경한 후에 집합에 포함시켜주면 된다.