왜 집합론과 논리학부터 다시 보는가

왜 필요한가

관계형 데이터베이스(relational database)의 “관계”(relation)라는 말 자체가 수학의 집합론(set theory)에서 온 용어다. 06편에서 정식으로 정의하겠지만, 미리 한 줄로 말하면 릴레이션(relation, 테이블에 대응하는 개념)은 “튜플(tuple, 행 하나에 대응)들의 집합”이다. 그리고 07~09편에서 다룰 관계대수(relational algebra)와 관계해석(relational calculus)은 이름 그대로 각각 집합 연산과 논리식을 데이터베이스 질의(query, 데이터를 찾는 요청)에 그대로 가져다 쓴 것이다.

그런데 “집합”이라는 말을 SQL의 테이블에 적용하면 낯선 규칙이 여럿 따라온다. 예를 들어 집합에는 같은 원소가 중복으로 들어갈 수 없고, 원소들 사이에 순서도 없다. 이 규칙을 미리 정확히 알아 두지 않으면, 이후 편에서 “릴레이션에는 중복된 튜플이 있을 수 없다”거나 “합집합 연산을 하려면 두 릴레이션의 속성 구조가 같아야 한다(합집합 호환, union-compatible)“는 설명을 만났을 때 “왜 그런 규칙이 있는지” 근거 없이 암기만 하게 된다. 이 편은 그 근거가 되는 집합론과 논리학의 최소 도구 상자를 미리 정리해 두는 선행 파일이다.

쉽게 말하면: 관계대수는 “집합 연산을 표 사이의 연산으로 확장한 것”, 관계해석은 “논리식으로 원하는 데이터의 조건을 서술하는 것”이다. 이 편은 그 집합 연산과 논리식 자체를 익히는 자리다.

이 편에서 다루는 개념은 06편의 릴레이션·튜플·키 정의, 07~09편의 관계대수·관계해석 자체와는 겹치지 않는다. 여기서는 순수하게 수학 도구만 다루고, 그 도구를 데이터베이스에 적용하는 구체적인 내용은 각 본론 편에서 다룬다.

집합의 기본 표기

왜 필요한가

집합 연산을 계산하기 전에, 집합 자체를 표기하고 읽는 방법부터 통일해야 한다. 시험 문제의 관계대수 수식은 결국 집합 기호로 쓰여 있으므로, 기호를 정확히 읽지 못하면 연산 자체를 할 수 없다.

정의

집합(set)은 서로 다른 원소(element)들을 순서 없이 모아 놓은 것이다. 원소 $a$가 집합 $A$에 속한다는 것은 $a \in A$ (에이 원소 인 에이, “$a$는 $A$의 원소다”)로 쓰고, 속하지 않으면 $a \notin A$로 쓴다. 집합 $A$의 모든 원소가 집합 $B$에도 속하면 $A$를 $B$의 부분집합(subset)이라 하고 $A \subseteq B$로 쓴다.

집합을 표기하는 방법은 두 가지다.

• 원소 나열법: $A = \{1, 2, 3\}$처럼 원소를 직접 나열한다.
• 조건 제시법: $A = \{x \mid x는~짝수,\ 1 \le x \le 10\}$처럼 “이런 조건을 만족하는 $x$들의 모임”으로 표기한다. 세로 막대 |는 “~을 만족하는”이라고 읽는다.

집합에 들어 있는 원소의 개수를 기수(cardinality, 카디널리티)라 하고 $|A|$로 쓴다. 예를 들어 $A = \{1, 2, 3\}$이면 $|A| = 3$이다. 이 용어는 06편에서 릴레이션의 튜플 개수를 가리키는 이름으로 그대로 재사용되므로 여기서 확실히 익혀 둔다.

집합에서 중요한 성질 두 가지를 미리 기억해 두자.

1. 원소의 중복이 없다. $\{1, 1, 2\}$와 $\{1, 2\}$는 같은 집합이다.
2. 원소 사이에 순서가 없다. $\{1, 2, 3\}$과 $\{3, 1, 2\}$는 같은 집합이다.

이 두 성질은 06편에서 “릴레이션에는 중복 튜플이 없고, 튜플 사이에 순서가 없다”는 규칙의 수학적 근거가 된다.

자주 틀리는 점

집합의 기본 연산

왜 필요한가

관계대수의 여러 연산 중 합집합(∪, union)·교집합(∩, intersection)·차집합(−, difference)·카티전 곱(×, Cartesian product) 네 가지는 이름 그대로 집합론의 연산을 릴레이션(표)에 그대로 옮긴 것이다(07·08편에서 자세히 다룬다). 그 전에 순수한 집합 사이의 연산부터 정확히 계산할 수 있어야 한다.

정의

두 집합 $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$를 예로 네 가지 연산을 정의한다.

앞의 세 연산(합·교·차)은 $A$와 $B$가 같은 종류의 원소를 담고 있을 때 의미가 통한다. 관계대수에서는 이를 합집합 호환(union-compatible) 조건이라 부르며, 07·08편에서 “두 릴레이션의 속성 개수(차수)와 각 속성의 도메인이 같아야 합집합·교집합·차집합을 쓸 수 있다”는 규칙으로 다시 등장한다.

카티전 곱은 정의가 조금 다르다. $A$와 $B$의 원소 종류가 달라도 상관없이, $A$의 원소 하나와 $B$의 원소 하나를 짝지은 순서쌍(ordered pair) 전체를 만든다. 순서쌍이라는 이름처럼 $(1, 3)$과 $(3, 1)$은 서로 다른 원소로 취급한다(집합 자체에는 순서가 없지만, 순서쌍이라는 하나의 원소 내부에서는 첫째 자리와 둘째 자리가 구분된다는 뜻이다).

계산·적용: 카티전 곱의 원소 개수 세기

$|A| = 3$, $|B| = 3$일 때 카티전 곱 $A \times B$의 원소 개수는 몇 개일까? $A$의 원소 하나마다 $B$의 원소 3개와 각각 짝지어지므로, 전체 경우의 수는 다음과 같다.

• $|A|$: 집합 $A$의 기수(원소 개수)
• $|B|$: 집합 $B$의 기수
• $|A \times B|$: 카티전 곱의 기수, 즉 만들어지는 순서쌍의 총개수

앞의 표에서 실제로 나열한 순서쌍이 9개인지 세어 보면 정확히 일치한다. 이 곱셈 규칙은 07·08편에서 두 릴레이션을 카티전 곱으로 결합했을 때 “결과 튜플 수는 두 릴레이션의 튜플 수를 곱한 값”이라는 성질로 그대로 이어진다.

결과 해석

카티전 곱의 결과가 원래 두 집합의 원소 개수를 곱한 만큼 커진다는 사실은, 실제 데이터베이스에서 카티전 곱을 그대로 실행 결과로 쓰는 경우가 드문 이유를 설명해 준다. 학생 100명과 과목 50개를 카티전 곱하면 5,000개의 조합이 만들어지는데, 그중 “그 학생이 실제로 그 과목을 수강한” 조합은 일부에 불과하다. 그래서 실제 질의에서는 카티전 곱 뒤에 선택(σ) 조건을 붙여 원하는 조합만 걸러내며, 이 과정이 07편의 조인(join) 연산으로 이어진다.

자주 틀리는 점

명제논리의 기본 연산

왜 필요한가

09편의 관계해석은 “이런 조건을 만족하는 튜플을 모두 찾아라”라는 질의를 논리식으로 표현하는 언어다. 이 논리식을 읽고 쓰려면 참(true)·거짓(false) 두 값만 갖는 문장인 명제(proposition)와, 명제를 조합하는 기본 연산자를 먼저 알아야 한다.

쉽게 말하면: 명제논리는 “그리고”, “또는”, “아니다”, “~이면 ~이다”라는 우리말 접속사를 기호로 정확하게 표기하는 방법이다.

정의

명제 $p$, $q$를 예로 네 가지 기본 연산자를 정리한다.

이 네 기호 중 논리곱(∧)·논리합(∨)·부정(¬)은 09편의 관계해석 질의문에서 “그리고”, “또는”, “~이 아닌”이라는 조건을 결합할 때 그대로 쓰이고, 함의(→)는 15편에서 함수적 종속(functional dependency)의 공리를 다룰 때 다시 등장한다.

계산·적용: 진리표로 직접 확인하기

$p$ = “학생의 학과가 컴퓨터공학이다”, $q$ = “학생의 학년이 4학년이다”라는 두 명제가 있다고 하자. 아래 표는 $p$, $q$의 참·거짓 조합에 따라 $p \land q$, $p \lor q$가 어떻게 결정되는지 보여주는 진리표(truth table)다.

이 표를 그대로 읽으면 “컴퓨터공학과이고(∧) 4학년인” 학생을 찾는 조건은 두 조건이 둘 다 참인 학생만 통과시키고, “컴퓨터공학과이거나(∨) 4학년인” 학생을 찾는 조건은 둘 중 하나만 참이어도 통과시킨다는 뜻이다.

결과 해석

이 진리표는 SQL의 WHERE 학과 = '컴퓨터공학' AND 학년 = 4와 WHERE 학과 = '컴퓨터공학' OR 학년 = 4가 왜 서로 다른 결과 집합을 돌려주는지를 논리적으로 설명해 준다. AND(그리고)는 논리곱에, OR(또는)는 논리합에 대응하므로, 조건을 더할수록 AND는 결과를 좁히고 OR는 결과를 넓힌다는 감각을 여기서 미리 잡아 두면 12·13편의 SQL 조건절과 07편의 선택 연산을 훨씬 수월하게 읽을 수 있다.

자주 틀리는 점

양화 기호: 전칭 양화사와 존재 양화사

왜 필요한가

“모든 학생은 이름이 있다”, “어떤 학생은 장학금을 받는다”처럼, 명제논리만으로는 “모든”과 “어떤”이라는 범위를 표현할 수 없다. 이 범위를 다루는 논리를 술어논리(predicate logic)라 하고, 그 핵심 도구가 양화사(quantifier, 양화 기호)다. 09편의 관계해석은 이 양화사를 그대로 사용해 “모든 과목을 수강한 학생을 찾아라” 같은 질의를 표현한다.

쉽게 말하면: 전칭 양화사는 “예외 없이 전부”, 존재 양화사는 “적어도 하나는”이라는 뜻을 기호로 나타낸 것이다.

정의

예를 들어 $x$가 학생 전체 집합의 원소를 가리킨다고 할 때, 다음 두 식은 전혀 다른 뜻이다.

이 식은 “모든 학생 $x$에 대해, $x$는 장학금을 받는다”는 뜻이다. 즉 예외 없이 전체 학생이 장학금을 받아야 참이 된다.

이 식은 “장학금을 받는 학생 $x$가 적어도 한 명 존재한다”는 뜻이다. 학생 전체 중 단 한 명만 장학금을 받아도 이 식은 참이 된다.

계산·적용: 부정과 결합했을 때의 변환 규칙

양화사에 부정(¬)을 씌우면 다음과 같이 서로 뒤바뀐다. 이 규칙을 드모르간의 법칙(De Morgan’s law)의 술어논리 버전이라 부른다.

• $P(x)$: $x$에 대한 임의의 조건(술어, predicate)
• 왼쪽: “모든 $x$가 $P$를 만족하는 것은 아니다”
• 오른쪽: “$P$를 만족하지 않는 $x$가 적어도 하나 존재한다”
• 두 식은 논리적으로 완전히 같은 뜻이므로 $\equiv$(동치, equivalent) 기호로 연결한다

• 왼쪽: “$P$를 만족하는 $x$는 존재하지 않는다”
• 오른쪽: “모든 $x$는 $P$를 만족하지 않는다”

결과 해석

이 변환 규칙은 09편에서 “모든 과목을 수강하지 않은 학생은 없다”처럼 이중 부정이 섞인 질의를 “모든 학생은 적어도 하나의 과목을 수강한다”는 단순한 형태로 바꿔 이해하는 데 쓰인다. 또한 18편·19편에서 다루는 관계대수의 디비전(division, ÷) 연산은 사실 “모든 ~에 대해”라는 전칭 양화사의 뜻을 집합 연산만으로 흉내 낸 것이며, 08편에서 이 연결 관계를 다시 설명한다.

자주 틀리는 점

핵심 정리

• 집합은 중복과 순서가 없는 원소의 모임이며, 기수(원소 개수)는 $|A|$로 표기한다. 이 두 성질이 06편의 “릴레이션에는 중복 튜플·순서가 없다”는 규칙의 근거가 된다.
• 합집합(∪)·교집합(∩)·차집합(−)은 같은 종류의 원소를 다루는 두 집합 사이에서 정의되며, 관계대수에서는 이를 합집합 호환 조건으로 다시 만난다. 카티전 곱(×)은 원소 종류가 달라도 되며, 결과 원소 개수는 두 집합 기수의 곱이다.
• 논리곱(∧)·논리합(∨)·부정(¬)·함의(→)는 SQL의 AND·OR·NOT과 대응하며, 함의는 전제가 거짓이면 항상 참으로 처리된다는 특성이 있다.
• 전칭 양화사(∀, 모든)와 존재 양화사(∃, 어떤 하나)는 관계해석과 디비전 연산의 논리적 기반이며, 부정과 결합하면 드모르간의 법칙에 따라 서로 뒤바뀐다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제