ch 6. Formal Relational Query Languages (part1. Relational Algebra)

ch 6. Formal Relational Query Languages

Relational Algebra (관계 대수)

• Procedural Language (순차적 언어)
• Six Basic Operators (기본 연산자)
  • 
• 연산자는 1개 혹은 2개의 릴레이션을 입력으로 받아서, 새로운 릴레이션을 결과로 출력한다.
  • 질의를 R,A로 표현

---

Select (선택)
표기 및 정의 :
• p는 selection predicate

• 

  
  

  
  

• p는 과 같은 기호(term)로 연결되어 구성된 명제 대수에 해당하는 식
• 
  
  
selection 예시
• 
• 
  
  

• Project
표기 및 정의
• 
• A1, A2는 속성 이름이고, r은 릴레이션 이름
• 언급된 속성에 한하여 (언급되지 않은 속성을 제외) 해당 릴레이션의 K개의 열(columns)이 결과로 나타냄
• 중복되는 행은 결과에서 제거된다, 왜냐하면 릴레이션은 집합이기 때문
Project 예시
• 
dept_name 속성을 instructor 릴레이션에서 제외하는 경우
• 

Union (합집합)
표기 및 정의
• 
• 릴레이션 r과 s의 union이 유효하기 위한 조건
  • 1) r과 s가 동일한 arity를 가져야 함 (arity : 속성의 수가 동일해야함)
  • 2)속성 영역은 반드시 compatible 해야함
    • 예시 : 릴레이션 r의 2번째 열은 반드시 릴레이션 s의 2번째 열과 동일한 타입의 값이어야 함
union 예시
• 
• (2009년 가을 학기의 모든 과목) 혹은 (2010년 봄학기의 모든 과목)
• 

• Set Difference (차집합)
• 표기 및 정의
  • 
  • 
    
• (주의) 차집합은 반드시 호환 가능한 (compatible) 릴레이션에서만 발생한다
  • 릴레이션 r과 s는 동일한 arity
  • 릴레이션 r과 s의 속성 범위는 반드시 compatible 해야함
  • * 합집합과 동일한 조건
• set difference 예시
• 
• 2009년 가을 학기에 열렸던 모든 과목 중에서 2010년 봄학기에 열린 과목을 제외
• 

• Cartesian-Product (카테시안 곱)
• 표기 및 정의
  • 
  • 
    
• 릴레이션 r과 s의 속성은 공통점이 없어야 함. (중복된 속성 없어야 함)
• 만약에 릴레이션 r과 s에 중복된 속성이 존재한다면, 반드시 renaming이 필요함
• cartesian-product 예
• 

---

• 연산들의 조합
• 여러개의 연산을 이용해서 표현식을 세울 수 있다.
• 예
• 

Rename 연산
• 릴레이션을 하나 이상의 다른 이름으로 부를 수 있도록 함
예시
• 
• 이것은 표현식 E를 x라는 이름으로 반환한다.
  
  
• 만약에 관계대수식 E가 n개의 arity를 가지는 경우,
• 
• 이것은 해당 표현식 E를 x라는 이름으로 반환하면서, 각 속성은 A1,A2...An이라는 이름으로 대치된다.
쿼리 예시 1
• 문제 : "대학에서 가장 큰 봉급을 찾아라"
• 1단계 : 지도자의 봉급이 다른 사람 봉급보다 작지 않은 경우를 찾기 (즉 최댓값이 아닌 것)
• 
  
  
• 2단계 : 최대 봉급 찾기
• 

• 쿼리 예시 2
• 문제 : 물리학부의 모든 교수 이름(instructor name)을 찾되, 그들이 수업한 모든 과목의 course_id도 함께 찾아라
• 쿼리 예시
• 

---

• Formal Definition (형식적 정의)
• 관계 대수의 기본 표현식은 다음 중 하나를 따라 구성된다 :
  • 데이터베이스의 릴레이션 (relation in database)
  • 변함없는 릴레이션 (constant relation)
• E1과 E2가 관계대수식이라 하면, 다음은 모두 관계 대수식이다 :
• 

• 기타 연산자
• 교집합 (set-intersection)
• 표기 및 정의
• 
• 가정
• 릴레이션 r과 s는 동일한 arity
• 릴레이션 r과 s의 속성은 호환 가능 (compatible)
• 참고사항
• 
• 예
• 

• 자연 조인 (Natural Join)
• 표기
  • 
    
    
• 릴레이션 r과 s는 각각 스키마 R과 S에서 온 것이라 하자. 그러면 r과 s의 자연 조인은 스키마 R과 S의 합집합을 통해 얻게 되는 것과 같다:
  • 릴레이션 r과 s에서 각각 튜플을 t(r)과 t(s)를 생각해보자
  • 만약 t(r)과 t(s)가 R과 S의 교집합에서 같은 값을 가지고 있다면, 결과적으로 하나의 튜플 t 만 추가된다.
  • t = 릴레이션 r의 t(r) = 릴레이션 s의 t(s)
• 예시
• 
• 
  
• 

cf. 자연조인(Natural Join) vs. 세타 조인 (theta join)
• theta join 표기
• 

• 자연 조인은 값이 같은 걸 합치는 반면
• 세타 조인은 세타라는 조건을 통해, 해당 조건에 만족하는 경우에 한하여 값이 같은 것을 합침
  
  
  
• 예시 : 컴퓨터공학과의 모든 교수 이름을 찾고, 그 교수들이 가르친 과목의 모든 과목명을 찾아라
• 
  
  
• natural join은 결합법칙이 적용됨
  
  
• natural join은 교환법칙이 적용됨 

예
• 
  
  
  

• 할당 연산 (Assignment Operation, <- )

• 할당연산은 복잡한 쿼리를 표현하기에 편리함
• Write query as a sequential program consisting of :
  • a series of assignments
  • followed by an expression whose value is displayed as a result of the query.
• 할당은 반드시 일시적인 릴레이션 값으로 만들어진다.
  
  

• 외부 조인 (outer join)
• join연산의 확장판으로서, 정보의 손실을 피할 수 있다
• join 연산을 수행하면서, 한 릴레이션(A)에는 존재하지만 다른 한쪽 릴레이션(B)에 존재하지 않는 튜플의 경우에도 해당 튜플을 join의 결과에 추가한다.
• null 값 사용
  • null값은 값을 알 수 없거나 (unknown) 존재하지 않음(not exist)을 나타낸다.
  • null을 포함하는 모든 비교 연산은 정의에 따라 false(거짓)이다. (후에 null을 포함하는 비교연산에 대해 상세하게 설명 예정)
• 예
• 
  
  

• 참고) join 연산을 이용한 outer join
• 
  
  
  

• Null 값
• tuple은 속성값으로 null 값을 가질 수 있다. (표기 : null)
• null 은 알 수 없는 값(unknown)이거나 존재하지 않는 값(not exist)를 의미한다
• (SQL에서) 합계 함수(aggregate function)는 단순하게 null을 무시한다.
• (SQL에서) 중복 제거 및 그룹화에서, null은 다른 어떤 값들과 동등하게 값으로나 취급되며, 두개의 null 값은 동일하다고 가정한다.
• null값과의 비교는 특수한 참 값(truth)을 반환한다 : unknown
  • A가 null이고, 만약에 false값이 unknown 대신에 쓰였다면, not(A<5) 는 A>=5 와 동일하지 않다.
• 
• 만약 null을 unknown으로 취급한다면, Select의 결과는 false로 간주된다.

• Division Operator (나누기 연산자)
• 릴레이션 r(R)과 s(S)가 있고, S는 R에 속하는 경우, r÷s는  가장 큰 릴레이션 t(R-S) 라고 볼 수 있다. 단, t × s ⊆ r 이 만족해야 함.
• 예시) 
• 
  
  
r÷s 는 다음과 같이 쓸 수 있다.
• 
  
  
예시)
• 
  
  

---

확장된 관계 대수 연산들

• Generalized Projection
• 산술 연산기능을 projection list에서 사용할 수 있도록 함으로써, Projection 연산을 확장
• 
• F1~ Fn 은 산술연산식으로써, 스키마 E의 속성과 상수를 포함한다.
• 예) 주어진 릴레이션 instructor(ID, name, dept_name, salary) 에서 salary는 연간 수입일 때, 동일한 정보에서 월간 수입으로 변경된 정보 구하기
• 

• Aggregate Functions
• Aggregate function :일련의 값을 받아서, 하나의 값을 결과로 내는 함수
• 

• 관계 대수에서의 Aggregate operation 
  • 
  • 
    
• G1~Gn 은 그룹으로 묶일 속성의 목록이다 (빈 것이어도 괜찮음. can be empty)
• 각 F는 aggregation function
• 각 A는 속성 이름

예시 )

• 

• 

• Aggregation의 결과는 이름을 갖지 않음
• rename 연산을 통해 이름을 부여할 수 있음
• 편의를 위해, aggregation 연산의 일부로 renaming을 허용함
• 

---

데이터베이스의 수정

• 데이터베이스의 내용은 다음 연산들로 인하여 수정될 수 있다
• 삭제
• 삽입
• 갱신 (update)

• 이 모든 연산은 assignment(←) 연산자를 통해 표현할 수 있다.

• Multiset Relational Algebra
• 순수한 관계 대수는 중복을 모두 제거한다. (e.g.projection 후)
• 멀티셋 관계대수는 SQL의 의미에 합치하는 것에 한해 중복을 남겨둔다. (원소 중복이 가능)
  • SQL의 중복 보유는 초기에는 효율성 때문이었으나, 지금은 하나의 특징으로 여김
    
    
• 멀티셋 관계대수는 다음과 같이 정의된다
• Selection : 만약에 튜플이 selection을 만족하는 경우, 가능한한 많은 중복된 튜플을 의미
• Projection : 중복이라 할지라도, 하나의 입력 튜플 당 하나의 튜플을 의미
• Cross Product : 만약에 r에 t1의 중복이 m개 존재하고, s에 t2의 중복이 n개 존재한다면, r×s의 t1.t2는 m×n개의 중복이 존재함을 의미
• 다른 연산자들도 유사하게 정의한다.
• 합집합 : m+n 개의 중복
• 교집합 : min(m, n) 중복
• 차집합 : min(0, m-n) 중복

SQL과 Relational Algebra
(ex1)
• 
• 위의 SQL은 multiset relational algebra 로 표현된 아래식과 동일하다.
• 

(ex2)
• 
• 위의 SQL은 multiset relational algebra 로 표현된 아래식과 동일하다.
• 

(ex3)
• 일반적으로, Selection 절의 통합되지않은 속성들은 group by 속성의 부분집합이 될수 있다.
  
  
• 
• 위의 SQL은 multiset relational algebra 로 표현된 아래식과 동일하다.
•