Relation Calculus 란?

이전 포스팅에서 이산수학의 Set 이론(집합론)과 1차 논리에 기반한 Relational Algebra 에 대해 알아보았다. 이번에는 Algebra(대수)가 아닌 Calculus(수치계산)에 대해 알아보자.

Relation Calculus

• Variable Quantity 를 다루는 수학.
  • Variable 은 양, 수량 등을 의미한다. 이전에 Algebra 에서 결국 표현하고 기술했던 방식이 어떤 문제의 계산 결과가 오는 것이 아니라 계산 결과를 얻을 수 있는 수식을 대수적으로 표현했음을 기억하자.
• 연산자, 피연산자 표기 대신 변수를 사용한 계산식 표기.
  • Relational Algebra 의 경우 operands 와 operator 를 정의하고 이에 우선순위 (괄호) 를 부여하여 Relation 에 대한 연산을 대수적으로 표기하였다.
  • Relational Calculus 는 각 Record 를 Tuple 로 보며 변수가 Tuple 인 Symbolic Logic 의 한 분야이다.
• Predicate Calculus, Descriptive 등으로 불림.
  - Predicate 즉, 술어를 의미한다. 왜 이렇게 불리는지는 하단의 First-order Logic 을 통해 이해해보자.
  
  

First-Order Logic

RC(Relational Calculus)는 first-order logic 에 기반을 두고 있다. 이에 따라 Predicate(술어) Logic 혹은 First-order predicate Calculus 라고 부른다.
여기서 Predicate 는 truth-valued(진리값) function 이다.

ex) ${x|Person(x)} = \{ x|(x.name = Beobwoo) \}$ 에서 $x$가 argument 이고 $P(x)$가 predicate 이다.

왜 Predicate Calculus 라고 하는 걸까?
Predicate Calculus 라는 의미는 술어 논리, 함수 논리 등으로 다르게 불린다."$x$ 는 인간이다." 라는 명제가 있을 때 주어는 $x$이고 술어는 "인간이다." 이다.
이렇게 명제들은 주어와 술어의 구조를 가지게 된다. 하나의 술어는 하나 이상의 객체를 서술 할 수 있는데 이러한 객체는 상수가 될 수도 있고 변수가 될 수도 있다. $x$의 정의역(domain)을 $D$라고 하면 이러한 정의역을 어떠한 방법을 통해 제한 하는 방법으로 원하는 "주어"를 표현 할 수 있는 것이다.

마찬가지의 논리로 Relation calcullus 또한 위의 예시에서 볼 수 있듯이 $Person(x)$ 라는 함수적 표기, 술어가 어떠한 정의역 $D$ 에서 $x$ 를 한정하게 되는 것이다.

First Order - $\exist x(P(x))$는 $\exist$가 argument 인 $x$에 적용
Second Order - $\exist P(P(x))$는 $\exist$가 또다른 predicate 인 $P(x)$ 에 적용된다.

CWA(Closed World Assumption)

??? 공부중 ...

Tuple Calculus

Relational Calculus 에서 변수가 tuple들을 대상으로 값을 갖게 되므로 여기서 사용된 변수를 Tuple Variable 혹은 Range Variable 이라고 한다. Range Variable 은 Relation Calculus 에서 매우 중요한 변수이다. 위에서 말한 술어가 적용된, Predicate 된 결과를 표현하기 때문이다.

Range Variable

$range \ of \ T \ is \ X1, X2, X3, ... , Xn$ 에서 $Xn$ 을 relation $Rn$ 의 실행 결과라고 한다면 각 Relation 이 Type-compatible 하다면 $T$ 는 실행 결과들의 Union 연산 결과에 대한 Tuple값을 결과로 갖게 된다.

Quantifiers

• Exist
  • WFF 인 f가 참이 되는 변수 x의 값이 적어도(at least) 한개 존재한다는 의미.
• For All
  • 변수 x 의 모든 값에 대하여 WFF 인 f가 참이라는 의미.

ex) exists 와 for all 에 대한 예시

1. $exists \ spx \ (spx.sno = sx.sno \ and \ spx.pno=p2)$
2. $for \ all \ spx \ (spx.sno = sx.sno \ and \ spx.pno=p2)$

1번식이 참이 되기 위해서는 괄호안의 비교식이 참이 되게하는 tuple variable 이 spx 안에 하나라도 존재해야하고,

2번식이 참이 되기 위해서는 tuple variable spx 가 relation sp 안의 모든 tuple 들에 대하여 괄호 안의 비교식이 참이어야 한다.

이 부분에서 신기한 점을 알 수 있다. 괄호안의 비교식에서는 spx 라는 relation 안의 튜플의 값이 어떻게 되는지에 따라 true or false 로 정해지게 되는데, exists 나 for all 의 경우에는 이 튜플에 대한 값의 비교식이 참이냐 거짓이냐에 의존하게 된다.

즉, 비교식과 튜플의 값이 정해짐과 동시에 Bound(종속) 되는 것이다.

반대로 괄호 안의 비교식은 튜플의 값에 따라 True or False 로 나오게 되므로 이는 Free(독립) 이다.

Free, Bound Variables

$exists \ T(f(T)) = false \ OR \ f(T1)\ OR \ f(T2) ...f(Tn)$

$for \ all \ T(f(T)) = true \ AND \ f(T1)\ AND \ f(T2) ...f(Tn)$

exists 와 for all 을 WFF 의 UNION 혹은 INTERSECT 로 다시 표현하면 위와 같아진다.

이전에 말한 Free 와 Bound 의 개념을 다시 설명하면, WFF 인 $f(T)$ 에서 기술된 $T$ 는 free variable 이고 $exists \ T(f(T))$ 에서 사용된 T 는 bound variable 이다.

자, 이해가 잘 안될 수도 있는데, 우측식은 WFF 이다. 각 식은 union 혹은 intersect 로 이어져 있다. 각 식의 결과는 T1, ... , Tn 의 Tuple 값에 따라 결정된다. 따라서 이는 free variable 이다.

그런데 exists 나 for all 의 결과는 우측 union 혹은 intersect 에 의해 결정된다. 이는 WFF 의 연산된 결과가 참이냐 거짓이냐에 의존하게 되고 그것을 참, 거짓으로 결정짓는 특정 $T..$ 들의 range(범위)에 bound 되는 것.

간단하게는 bound variable 은 어떠한 변수 $x$ 가 range over 하는 relation 이 주어지면 True or False 가 결정되는 것.

Relational Calculus Operations

Target Item List

tuple calculus 를 표현하는 가장 기본식의 형태이다. RA(Relational Algebra)의 PROJECTION 연산과 비슷하나 차이가 존재한다.

• 한 개의 Relation 에 대하여 Range Over 한 target-item-list 는 Projection 과 동일. ⇒ Projection
  
• 복수의 Relation 에 대하여 Range Over 한 target-item-list 는 Cartesian Product 를 수행하고 Where 절을 수행한 후 마지막으로 Projection 수행한 것과 동일 ⇒ Natural Join = Cartesian Product + Restriction + Projection
  

즉, $(T.A, T.B)[where \ f]$ 에서는 relation $TR, UR$ 에 대하여 cartesian product 를 수행하고 where condition $f$ 로 restriction 을 수행하고 마지막으로 target-item-list 로 projection 을 수행한다.

For All 과 Divide By

$sx \ where \ forall \ px(exists \ spx(spx.sno = sx.sno \ and \ spx.pno =px.pno))$ 는

$sx \ where \ not \ exists \ px(not \ exists \ spx(spx.sno = sx.sno \ and \ spx.pno =px.pno))$ 와 같다.

이는 $\forall xf(x) = \neg \exists x(\neg \ \exists f(x))$ 이기에 위의 등식이 성립한다.

Extended Relation Calculus

sum( ), avg( ) 와 같은 Aggregate Function 을 target-item-list 에서 표현 할 수 있는데 이는 위에서 언급한 exists, for all 과 같은 quantifier 로 간주하게 되고 마찬가지로 수행된 Tuple Variable 또한 Aggregate Function 으로 Bound 된다.

$aggregate-function ((target-item-list) \ where \ f)$ 형태로 사용

ex) $sum(spx \ where \ spx.pno = px.pno \ , qty)\ as \ totqty$

여기서 spx 는 where 절에 의해 bound 되게 되고 sum aggregate function 은 px.pno 에 대해 group by 를 수행하게 되는데 이부분이 생략되었음을 인지해야 한다.