DB Chapter 5

Ch5. Algebraic and Logical Query Languages

1. Relational Operation on Bags

Relational algebra: operand가 relation인 algebra

Aggregate: sum, avg등

• Union, Intersection, Difference n: R의 원소 갯수, m: S의 원소 갯수

  • Union: R U S = n+m

    {1,2,1} U {1,2,3,3} = {1,1,1,2,2,3,3}

  • Intersection: R n S = min(n, m)

    {1,2,1,1} n {1,1,2,3,3} = {1,2}

  • Difference = {1,3,1,1} - {1,3,3,5} = {1, 1}

  bag에서는 분배법칙이 성립하지 않음.

• Projection

• Product

• Join

2. Extended Operators of Relational Algebra

• Distinct: 중복되는거는 하나만 나오게 한다. $\delta(R)$

• Aggregation(relational operator는 아님): Sum, Avg, Max, Min, Count

• Grouping: 어떤 attribute를 기준으로 group화 해서 sorting할 것인지 정함. L을 기준으로 R을 group $\gamma_L(R)$

• Extended Projection: projection을 한 번에 여러번 할 수 있음

• Sorting: 보통은 오름차순으로 sort. $\tau_L(R)$

• Outerjoin: join을 했을 때 서로 겹치는 게 없어도 data를 사라지지 않게 함.

R하고 S에 left outerjoin을 하면 R에 해당 하는 부분은 NULL이 없어야 하고 right는 S에 해당하는 부분에는 NULL이 없어야함.

3. A Logic for Relations

logical rule은 대부분의 정보를 합치는 시스템의 기반임

Predicate는 변수가 있고 그 변수의 값에 의해 True/False가 결정.

Atom: 각각의 독립변수(argument)에 의해 값이 결정되는 predicate

Datalog Rules: 2가지가 있음. 예시를 통해 봅시다.

S(x,y) <- R(x,z) AND R(z,y) AND NOT R(x,y)

여기서 S(x,y)를 head, <- 를 if, 오른쪽에 있는 애들을 body, 오른쪽의 atom(R(x,z) 등)을 subgoal이라 부름

R = {(1,2), (2,3)}

1. Variable-based

   R(x,z)가 R(1,2)가 되고, z가 그대로 R(z, y)에 들어가 R(2, y)가 됨. 그럼 R안에 2,y를 만족하는 값은 3이므로 y=3이 됨.

2. Tuple-based

   Tuple을 전부 나열하고 나서 관계 없는 값들을 지워나감.

   

   이 그림을 봤을 때 1,3,4번 tuple은 z의 값이 일치하지 않고, 1, 4번째 tuple은 R에 이미 같은 값이 있음. NOT R(x,y)인데 R(1,2)나 (2,3)이 R에 있으므로 제거. 그래서 2번만 남게 됨.

Safety

head나 negated relational subgoal이나 any arithmetic subgoal에 나타나는 any variable은 무조건 nonnegated, relational subgoal 에 나타나야 한다. 뭔소릴까요? 예시를 봅시당

P(x,y) <- Q(x,z) AND NOT R(w,x,z) AND x<y

여기서 head에 나타나는 variable은 x,y, negated relational subgoal에서는 w,x,z, arithmetic subgoal에는 x,y가 나온다.

그러면 하나씩 보는데 x와 z는 Q라는 nonnegated, relational subgoal에 나타나지만 w,y는 그러지 못하기 때문에 safe하지 못함.

Extensional and Intensional Predicates

Extensional: 실제로 DB에 저장되어 있는 predicate

Intensional: 그냥 룰만 지킴

Datalog Rules Applied to Bags

예시를 봅시다

위에꺼 만족하는거 3개, 아래꺼 만족하는거 1개, 겹쳐도 갠춘 합쳐서 4개~

###

4. Relational Algebra and Datalog

• Boolean operation(union, intersection, difference)

• Projection

  • Movies(t, y, l, g, s, p)에서 t, y, l을 projection 할 경우

    P(t, y, l) <- Movies(t, y, l, g, s, p)

• Selection

  • 길이가 100이상이고 s가 Fox인 애를 찾을 경우

    S(t,y,l,g,s,p) <- Movies(t, y, l, g, s, p) AND l >= 100 AND s = ‘Fox’

• Product( AND가 만능임 )
  • P(a,b,c,x,y,z) <- R(a,b,c) AND S(x,y,z)

• Join

  • J(a,b,c,,d) <- R(a,b) AND S(b,c,d) [알아서 join 잘해줌]

  theta join 예시

  

• Multiple Operations with Datalog

  Selection에 쓰인 예시를 나눠서 풀수도 있는데 그거도 방법이 있음. relational algebra랑 별차이 X

  

Comparison Between Datalog and Relational Algebra

Datalog는 data의 중복이 안됨.

Datalog는 relational algebra로 항상 바꿀 수 있지만 역은 안댐

Datalog는 recursion이 가능.