[데이터베이스 개론] 4. 대수적/논리적 쿼리 언어(Algebraic and Logical Query Language)

이 챕터는 두개의 추상적인 언어를 다룬다. 하나는 대수적(algebraic)인것, 하나는 논리적인것(logic-based)이다.

대수적인 것은 챕터2에서 다룬 관계대수학과 같지만, 그 범위를 확장할 것이다. 챕터2에서는 집합에 대해서 연산했다면, 이 챕터에서는 중복을 허용한 Bags로 연산할 것이다. 논리적인 언어는 데이터로그(Datalog)라고 부른다. 우리는 원하는 결과를 구하는 알고리즘을 찾기보다, 우리가 원하는 쿼리를 표현하는데에 집중할 수 있다.

5.1 Relational Operations on Bags

말했듯이 Bags는 집합에서 같은 튜플의 중복을 허용한 것이다. 왜 Bags를 사용할까? 두 릴레이션의 합집합을 구할때, 중복되는 원소를 제거하는 연산을 하지 않아도 된다. 그저 두 릴레이션을 복사해서 합하면 그만이다. 릴레이션을 사영(projection)시킬때도 마친가지이다. 불필요한 컬럼을 제거하기만 하면 그만이다. 혹은, 집합에서와 bags에서 어떤 컬럼의 평균을 구한다고 하면, 두 결과는 다를 것이고 우리가 원하는 결과가 후자일 수 있기 때문이다.

이제 원래 우리가 알던 관계대수적 연산들이 어떻게 바뀌는지 살펴보자.

먼저 집합 연산들이다. 튜플 t가 두 릴레이션 R과 S에서 각각 n개, m개 들어있다고 하면, 각 연산의 결과는 다음과 같다.

• 합집합 RuS: t가 n+m개
• 교집합 RnS: t가 min(n,m)개
• 차집합 R-S: t가 max(0, n-m)개

• 선택(Selection): 중복을 처리하지 않을뿐, 기존 연산과 동일
• 조인(Join): 중복을 처리하지 않을뿐, 기존 연산과 동일
• 곱(Product): 중복을 처리하지 않을뿐, 기존연산과 동일. R과 S의 튜플 개수의 곱 만큼의 row가 생길 것이다.
• 사영(Projection): 원래 사영은 컬럼들 중 우리가 원하는 컬럼들 만을 고르고, 관심밖의 컬럼은 삭제하는 연산이였다. 이제는 그 기능이 확장되어, 컬럼의 이름을 바꿀 수 있다. 또한, 두 컬럼을 조합하여 새로운 연산을 만드는 등의 연산도 가능하다. 아래의 표현은 A컬럼은 유지하고, B 와 C 컬럼은 합쳐서 X 라는 새로운 컬럼을 만들라는 표현식이다.

5.2 Extended Operators of Relational Algebra

Bags가 생김에 따라 정의할 수 있게된 새로운 연산자들을 소개한다.

• 중복 제거 연산자(Duplicate-elimination operator): δ(R)
  • Bags의 중복을 제거해서 Set으로 바꾼다.
• 집계 연산자(Aggregation operator)
  • SUM, AVG, MIN, MAX 등 어느 한 컬럼을 요약해서 하나의 값을 반환한다.
• 분류 연산자(Grouping operator): γ(R)
  • 튜플들을 종류에 따라 묶는다. Grouping이 이루어지면, 새로운 튜플들로 묶인 튜플들이 표현된다. 새로운 튜플은 묶은 기준이 된 속성들과 aggregation된 기존 속성들, 두 종류로 표현된다. 아래는 릴레이션을 starName으로 묶고, year와 title을 각각 aggregate하라는 표현식이다. starName, minYear, ctTitle이 새로운 튜플의 속성들이 된다

• 정렬 연산자(Sorting operator): τ(R)
  • 튜플들을 순서에 맞게 정렬한다. 이 연산의 결과물은 튜플의 집합이 아니라, 순서가 있는 배열이다.
• 외부조인 연산자(Outerjoin operator)
  외톨이 튜플(Dangling tuple)을 제거하지 않는 변형된 조인 연산자이다. 기존 조인은 다른 릴레이션과 공통 속성이 없으면, 버려지는 튜플이 생겼다. 이것을 외톨이 튜플이라 부른다. 두 릴레이션 R과 S에 대하여 아래의 연산들을 할 수 있다.
  
  • Left Outer Join: R의 외톨이 튜플을 남기고, 빈 속성은 NULL로 남긴다, (R ⟕ S)
  • Right Outer Join: S의 외톨이 튜플을 남기고, 빈 속성은 NULL로 남긴다, (R ⟖ S)
  • Full Outer Join: 양쪽의 외톨이 튜플을 남기고, 빈 속성은 NULL로 남긴다, (R ⟗ S)
  조건을 추가해서 세타조인(theta join)으로 사용할 수도 있다.

5.3 A Logic for Relations

Datalog(”database logic”)는 if-then 문을 포함하는 논리적 쿼리 언어이다. Datalog에서 릴레이션은 명제로 표현되며, 명제 안의 변수들은 아톰(atom)으로 불린다. 마치 전통적인 프로그래밍 언어에서 함수같은 것이다.

R(a1, a2, …, an) 은 (a1, a2, …, an)이 R에 속하는 튜플이면 TRUE, 아니면 FALSE를 반환한다. 아래의 릴레이션 R에서 R(1,2)와 R(3,4)는 TRUE지만, R(1,3)은 FALSE다.

또 다른 종류의 아톰도 있다. Arithmetic atoms는 x<y, x+1 ≥ y + z처럼 두 arithmetic expression의 비교식으로 표현된다. 구분을 위해, 앞서 언급한 숫자 아톰은 관계형 아톰(relational atoms)으로 부르겠다.

만약 우리가 “길이가 100분이 넘는 영화”들을 모아 LongMovies라는 릴레이션을 만들것이라면 아래와 같이 표현 할 수 있다.

화살표 왼편의 관계형 아톰을 head, 오른편을 body라고 부른다.

Body는 relational/arithmetic atoms 모두가 올 수 있고, 위에서는 이 두 아톰이 AND로 묶여서 등장했다. AND로 묶인 각각의 아톰을 “subgoals”라고 부른다. 이 식을 관계대수로도 아래처럼 표현할 수 있음을 기억하자. 5.4절에서 다시 다룬다.

우리는 이 Datalog 규칙의 안전함(Safety)을 논할 수 있다. 먼저 쿼리 결과는 항상 유한해야 한다. 만약 body에 NOT Movies(t,y,l,,,_)가 왔다면, 그것은 유한하지 않음으로 안전하지 않다. 또, l≥100이라는 두번쨰 subgoal에서 나올 수 있었던 이유는, 첫번째 relational subgoal에서 l이 정의되었기 때문이다. l이 여기서 정의되지 않았다면, 규칙은 안전하지 않았을 것이다. 마지막으로, LongMovie(t,y)의 t와 y 또한, 첫번째 subgoal에서 등장했기에 이 규칙이 안전한 것이다.

Datalog 규칙은 여러번 시행될 수 있다. 또, 집합이 아닌 bags에도 적용가능하다. 아래의 규칙을 시행하고 나면 H(x,y)에는 S(x,y)의 튜플 중에서 x가 1보다 크거나, y가 5보다 작은 튜플 모두가 담겨 있게 된다.

5.4 Relational Algebra and Datalog

Datalog 규칙과 관계대수는 서로 표현이 가능함을 앞서 잠깐 살펴봤다. 안전한 하나의(multiple이 아닌) Datalog 규칙은 관계대수로 표현이 가능하다.(증명은 교재에서 생략했다.) 그러나, datalog 규칙은 multiple 표현이 가능하기에 모든 관계대수를 표현을 대신할 수 있다. 특히, datalog는 재귀를 표현할 수 있다. 관계대수와 Datalog 규칙의 변환을 알아보자.

• 집합연산
  • 합집합
  • 교집합
  • 차집합
• 사영(Projection)
• 선택(Selection)
• 곱(Product)
• 조인(Join)

앞서 말했듯이, datalog는 재귀적인 표현도 가능하다. 아래는 노드간 이어진 edge들의 relation으로부터, 노드간의 path를 정의한 규칙이다.