Chapter 6: Formal Relational Query Languages

Chapter 6: 정규 관계형 질의 언어 Relational Algebra (관계 대수언어) Tuple Relational Calculus (튜플 관계 해석) Domain Relational Calculus (도메인 관계 해석)

관계형 대수 (Relational Algebra) 절차식 언어 6 가지 기본 연산자 (Six basic operators) 선택 (select):  추출 (project):  합집합 (union):  차집합 (set difference): – 카티션 곱 (Cartesian product): x 재명명 (rename):  연산자는 입력으로서 하나 이상의 릴레이션을 취해 그 결과로 새로운 릴레이션을 생성한다.

Select Operation – Example Relation r A=B ^ D > 5 (r)

Select Operation 표기법 (Notation):  p(r) p 를 선택 술어 (selection predicate) 라고 부른다. 다음과 같이 정의된다: p(r) = {t | t  r and p(t)} 여기에서 p 는 다음과 같은 유형의 명제 해석식이다. <애트리뷰트> = <애트리뷰트> 또는 <상수>  >  <  (and), (or), (not)으로 연결된다. Example of selection:  dept_name=“Physics”(instructor)

Project Operation – Example Relation r: A,C (r)

Project Operation Notation: 여기서 A1, A2는 애트리뷰트명이고 r은 릴레이션명이다. 결과는 명시하지 않은 열을 제외한 k 열의 릴레이션으로 정의된다. 릴레이션은 집합이기 때문에 중복 행은 결과에서 제거된다. Example: To eliminate the dept_name attribute of instructor ID, name, salary (instructor)

Union Operation – Example Relations r, s: r  s:

Union Operation Notation: r  s Defined as: r  s = {t | t  r or t  s} r  s가 가능하려면, 1. r과 s는 같은 항(애트리뷰트의 수가 같음)을 가져야 한다. 2. 애트리뷰트의 도메인은 양립할 수 있어야 한다(즉, r의 두번째 열은 s의 두번째 열의 것과 같은 유형의 값을 다룬다). Example: to find all courses taught in the Fall 2009 semester, or in the Spring 2010 semester, or in both course_id ( semester=“Fall” Λ year=2009 (section))  course_id ( semester=“Spring” Λ year=2010 (section))

Set difference of two relations Relations r, s: r – s:

Set Difference Operation Notation r – s Defined as: r – s = {t | t  r and t  s} 차집합 연산은 양립할 수 있는 릴레이션 간에만 이루어질 수 있다. - r과 s는 같은 항을 가져야 한다. - r과 s의 애트리뷰트 도메인은 양립해야만 한다. Example: to find all courses taught in the Fall 2009 semester, but not in the Spring 2010 semester course_id ( semester=“Fall” Λ year=2009 (section)) − course_id ( semester=“Spring” Λ year=2010 (section))

Cartesian-Product Operation – Example Relations r, s: r x s:

Cartesian-Product Operation Notation r x s Defined as: r x s = {t q | t  r and q  s} r(R)과 s(S)의 애트리뷰트가 서로 다르다고 가정하자(즉, RS = ). r(R)과 s(S)의 애트리뷰트가 서로 다르지 않다면, 재명명을 사용해야 한다.

복합 연산 (Composition of Operations) 여러 연산을 사용해 표현식을 만들 수 있다. Example: A=C(r x s) r x s A=C(r x s)

Rename Operation 이름을 줄 수 있도록 하여 관계형 대수 표현식의 결과를 참조하도록 한다. 하나 이상의 이름으로 릴레이션을 참조하도록 한다. Example:  x (E) 이름 x라는 이름으로 표현식 E를 리턴한다. 관계형 대수 표현식 E가 n항이면, x (A1, A2, …,An)(E) x라는 이름으로 A1, A2, …,An으로 재명명된 애트리뷰트를 가 진 표현식 E의 결과를 리턴한다.

예제 질의 대학에서 가장 높은 급여는 ? Step 1: 임의의 다른 강사보다 적은 급여를 받는 강사 급여를 모두 찾아라. (i.e. not maximum) using a copy of instructor under a new name d instructor.salary ( instructor.salary < d.salary (instructor x d (instructor))) Step 2: 최대값을 갖는 급여를 찾아라. salary (instructor) – instructor.salary ( instructor.salary < d,salary (instructor x d (instructor)))

예제 질의 물리학과 (Physics department)에 소속된 강사 ID와, 이 들 강사가 가르친 모든 course_id 를 찾으시오. Query 1 instructor.ID,course_id (dept_name=“Physics” (  instructor.ID=teaches.ID (instructor x teaches))) Query 2 instructor.ID,course_id (instructor.ID=teaches.ID (  dept_name=“Physics” (instructor) x teaches))

형식적 정의 관계형 대수에서의 기본 표현식은 다음 중 하나 이상으로 구성된다. - 데이터베이스내의 릴레이션 - 상수 릴레이션 E1과 E2를 관계형 대수 표현식이라 하면, 다음은 모두 관계형 대수 표현식이다: - E1  E2 - E1 - E2 - E1  E2 - P(E1), P는 E1내 애트리뷰트 상의 술어이다. - S(E1), S는 E1내 어떤 애트리뷰트로 구성된 리스트이다. - x(E1), x는 E1 의 결과에 대한 새로운 이름이다.

추가 연산 관계형 대수에 어떠한 능력도 추가되지 않지만 질의를 단순화하는 추가 연산을 정의한다. 공통 집합 (Set intersection) 자연 죠인 (Natural join) 배정 (Assignment) 외부 조인 (Outer join)

공통 집합 연산 Notation: r  s Defined as: r  s = { t | t  r and t  s } 가정: - r과 s는 같은 항수를 갖는다. - r과 s의 애트리뷰트는 양립성이 있다. 유의: r  s = r - (r - s)

Set-Intersection Operation – Example Relation r, s: r  s

자연 조인 연산 Notation: r s r과 s를 각각 스키마 R과 S상의 릴레이션이라 하자. 결과는 r의 튜플 tr과 s의 튜플 ts의 각 쌍을 고려해 얻은 스키마 R  S 상의 릴레이션이다. tr 과 ts 가 RS의 애트리뷰트 각각에 같은 값을 가지면, 다음과 같이 튜플 t가 결과에 추가된다. - t 는 r 상에 tr 로서 같은 값을 갖는다. - t 는 s상에 ts 로서 같은 값을 갖는다. Example: R = (A, B, C, D) S = (E, B, D) Result schema = (A, B, C, D, E) r s is defined as: r.A, r.B, r.C, r.D, s.E (r.B = s.B  r.D = s.D (r x s))

Natural Join Example Relations r, s: r s

Natural Join and Theta Join Comp. Sci. department에 속한 모든 강사 이름과 이 들 강사가 가르친 모든 코스 명을 찾으시오.  name, title ( dept_name=“Comp. Sci.” (instructor teaches course)) Natural join 연산에는 결합법칙이 성립한다. (instructor teaches) course is equivalent to instructor (teaches course) Natural join 연산에는 교환법칙이 성립한다. instruct teaches is equivalent to teaches instructor 세타 조인 (theta join) 연산자 r  s 는 다음과 같이 정의된다. r  s =  (r x s)

배정 연산 (Assignment Operation) 배정 연산()은 복잡한 질의를 편리하게 표현하는 방법을 제공한다. 질의를 일련의 배정 연산과 질의의 결과 값이 디스플레이되는 표현식으로 구성된 순차 프로그램으로 작성한다. 배정은 항상 임시 릴레이션 변수로 작성되어야 한다.

외부 조인 (Outer Join) 정보 손실을 피하기 위한 조인 연산의 확장. 조인을 계산하고 다른 릴레이션의 튜플과 그 값이 일치하지 않는 어떤 릴레이션의 튜플들을 죠인의 결과에 추가한다. 널 값을 사용한다. - 널은 알려지지 않은 값이나 존재하지 않는 값을 의미한다. - 널을 내포한 모든 비교는 정의에 의해 거짓이다.

Outer Join – Example Relation instructor Comp. Sci. Finance Music ID dept_name 10101 12121 15151 name Srinivasan Wu Mozart Relation teaches ID course_id 10101 12121 76766 CS-101 FIN-201 BIO-101

Outer Join – Example Join instructor teaches ID name dept_name course_id 10101 12121 Srinivasan Wu Comp. Sci. Finance CS-101 FIN-201 Left Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 Srinivasan Wu Mozart Comp. Sci. Finance Music CS-101 FIN-201 null

Outer Join – Example Right Outer Join instructor teaches ID name dept_name course_id 10101 12121 76766 Srinivasan Wu null Comp. Sci. Finance null CS-101 FIN-201 BIO-101 Full Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 76766 Srinivasan Wu Mozart null Comp. Sci. Finance Music null CS-101 FIN-201 null BIO-101

나누기 연산 (Division Operator) r  s “모두에 대한”이라는 구절을 내포한 질의에 적합하다. q = r  s라 하자. 그러면 q는 q  s  r을 만족하는 가장 큰 릴레이션이다. E.g. let r(ID, course_id) = ID, course_id (takes ) and s(course_id) = course_id (dept_name=“Biology”(course ) then r  s gives us students who have taken all courses in the Biology department Can write r  s as temp1  R-S (r ) temp2  R-S ((temp1 x s ) – R-S,S (r )) result = temp1 – temp2

나누기 연산의 예제 A B B  1 1  2 2  3  1  1  1  3  4  6 s  1  2 A  릴레이션 r, s : r  s A B  1  2  3  1  1  1  3  4  6  1  2 B 1 2 A   s r

또 다른 나누기 예제 A B C D E D E a 1 b 1 s r A B C  a  a 1  a  a 1 릴레이션 r, s: r  s A B C D E  a  a 1  a  a 1  a  b 1  a  a 1  a  b 3  a  a 1  a  b 1  a  b 1 D E a 1 b 1 s r A B C  a   a . 

확장 관계형 대수 연산 일반화 추출 (Generalized Projection) 집성 합수 (Aggregate Functions)

일반화 추출 추출 리스트에 산술 함수를 사용 하도록 함으로써 추출 연산을 확장한다. F1, F2, …, Fn(E) Given relation instructor(ID, name, dept_name, salary) where salary is annual salary, get the same information but with monthly salary ID, name, dept_name, salary/12 (instructor)

집성 함수 Aggregation function: 값의 모임을 취해 하나의 값을 결과로 돌려준다. avg: average value min: minimum value max: maximum value sum: sum of values count: number of values Aggregate operation in relational algebra E is any relational-algebra expression G1, G2 …, Gn is a list of attributes on which to group (can be empty) Each Fi is an aggregate function Each Ai is an attribute name

Aggregate Operation – Example Relation r: A B C     7 3 10 sum(c) (r) sum(c ) 27

데이터베이스의 수정 데이터베이스의 내용은 다음 연산을 사용해 수정할 수 있다. - 삭제 - 삽입 - 갱신 이들 모든 연산은 배정 연산자를 사용해 표현된다.

SQL and Relational Algebra select A1, A2, .. An from r1, r2, …, rm where P is equivalent to the following expression in multiset relational algebra  A1, .., An ( P (r1 x r2 x .. x rm)) select A1, A2, sum(A3) from r1, r2, …, rm where P group by A1, A2 A1, A2 sum(A3) ( P (r1 x r2 x .. x rm)))

Tuple Relational Calculus

튜플 관계형 해석 각 질의가 다음과 같은 형식인 비절차식 질의어 { t | P(t) } 술어 P가 t에 대해 참인 모든 튜플 t의 집합이다. t는 튜플 변수이고, t[A]는 애트리뷰트 A에 대한 튜플 t의 값을 의미한다. t  r은 튜플 t가 릴레이션 r에 속함을 의미한다. P는 술어 해석의 그것과 유사한 식이다.

술어 해석식 1. 애트리뷰트와 상수의 집합 2. 비교 연산자의 집합 : (예를 들어, <, , =, , >, ) 3. 연결자의 집합 : and(), or(), not() 4. 내포() : x  y, x가 참이면 y도 참이다. x  y   x  y 5. 한정자의 집합 :  t  r (Q(t))  술어 Q(t)가 참인 릴레이션 r내에 튜플 t가 존재한다.  t  r (Q(t))  릴레이션 r내의 모든 튜플 t에 대해 Q가 참이다.

Example Queries {t | t  instructor  t [salary ]  80000} 급여가 $80,000 이상인 강사의 ID, name, dept_name, salary 를 찾으시오. {t | t  instructor  t [salary ]  80000} 앞의 질의에서 ID 속성값만을 찾으시오. {t |  s instructor (t [ID ] = s [ID ]  s [salary ]  80000)} Notice that a relation on schema (ID) is implicitly defined by the query

Domain Relational Calculus

도메인 관계형 해석 튜플 관계형 해석과 능력이 동등한 비절차식 질의어 각 질의는 다음과 같은 형식의 표현식이다. {<x1, x2, …, x n> | P(x1, x2, …, x n)} - x1, x2, …, x n 은 도메인 변수를 표현한다. - P는 술어 해석의 그것과 유사한 식이다.

Example Queries Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000 {< i, n, d, s> | < i, n, d, s>  instructor  s  80000} As in the previous query, but output only the ID attribute value {< i> | < i, n, d, s>  instructor  s  80000} Find the names of all instructors whose department is in the Watson building {< n > |  i, d, s (< i, n, d, s >  instructor   b, a (< d, b, a>  department  b = “Watson” ))}

Example Queries Fall 2009 semester 혹은 Spring 2010 semester 에 개설된 모든 코스 정보를 찾으시오. {<c> |  a, s, y, b, r, t ( <c, a, s, y, b, t >  section  s = “Fall”  y = 2009 ) v  a, s, y, b, r, t ( <c, a, s, y, b, t >  section ]  s = “Spring”  y = 2010)} This case can also be written as {<c> |  a, s, y, b, r, t ( <c, a, s, y, b, t >  section  ( (s = “Fall”  y = 2009 ) v (s = “Spring”  y = 2010))} Fall 2009 semester 와 Spring 2010 semester 에 개설된 모든 코스 정보를 찾으시오. {<c> |  a, s, y, b, r, t ( <c, a, s, y, b, t >  section  s = “Fall”  y = 2009 )   a, s, y, b, r, t ( <c, a, s, y, b, t >  section ]  s = “Spring”  y = 2010)}

End of Chapter 6

Figure 6.01

Figure 6.02

Figure 6.03

Figure 6.04

Figure 6.05

Figure 6.06

Figure 6.07

Figure 6.08

Figure 6.09

Figure 6.10

Figure 6.11

Figure 6.12

Figure 6.13

Figure 6.14

Figure 6.15

Figure 6.16

Figure 6.17

Figure 6.18

Figure 6.19

Figure 6.20

Figure 6.21

Deletion A delete request is expressed similarly to a query, except instead of displaying tuples to the user, the selected tuples are removed from the database. Can delete only whole tuples; cannot delete values on only particular attributes A deletion is expressed in relational algebra by: r  r – E where r is a relation and E is a relational algebra query.

Deletion Examples Delete all account records in the Perryridge branch. account  account – branch_name = “Perryridge” (account ) Delete all loan records with amount in the range of 0 to 50 loan  loan – amount 0and amount  50 (loan) Delete all accounts at branches located in Needham. r1  branch_city = “Needham” (account branch ) r2   account_number, branch_name, balance (r1) r3   customer_name, account_number (r2 depositor) account  account – r2 depositor  depositor – r3

Insertion To insert data into a relation, we either: specify a tuple to be inserted write a query whose result is a set of tuples to be inserted in relational algebra, an insertion is expressed by: r  r  E where r is a relation and E is a relational algebra expression. The insertion of a single tuple is expressed by letting E be a constant relation containing one tuple.

Insertion Examples account  account  {(“A-973”, “Perryridge”, 1200)} Insert information in the database specifying that Smith has $1200 in account A-973 at the Perryridge branch. account  account  {(“A-973”, “Perryridge”, 1200)} depositor  depositor  {(“Smith”, “A-973”)} Provide as a gift for all loan customers in the Perryridge branch, a $200 savings account. Let the loan number serve as the account number for the new savings account. r1  (branch_name = “Perryridge” (borrower loan)) account  account  loan_number, branch_name, 200 (r1) depositor  depositor  customer_name, loan_number (r1)

Updating A mechanism to change a value in a tuple without charging all values in the tuple Use the generalized projection operator to do this task Each Fi is either the I th attribute of r, if the I th attribute is not updated, or, if the attribute is to be updated Fi is an expression, involving only constants and the attributes of r, which gives the new value for the attribute

Update Examples Make interest payments by increasing all balances by 5 percent. account   account_number, branch_name, balance * 1.05 (account) Pay all accounts with balances over $10,000 6 percent interest and pay all others 5 percent account   account_number, branch_name, balance * 1.06 ( BAL  10000 (account ))   account_number, branch_name, balance * 1.05 (BAL  10000 (account))

Example Queries customer_name (borrower)  customer_name (depositor) Find the names of all customers who have a loan and an account at bank. customer_name (borrower)  customer_name (depositor) Find the name of all customers who have a loan at the bank and the loan amount customer_name, loan_number, amount (borrower loan)

Example Queries Find all customers who have an account from at least the “Downtown” and the Uptown” branches. Query 1 customer_name (branch_name = “Downtown” (depositor account ))  customer_name (branch_name = “Uptown” (depositor account)) Query 2 customer_name, branch_name (depositor account)  temp(branch_name) ({(“Downtown” ), (“Uptown” )}) Note that Query 2 uses a constant relation.

Bank Example Queries Find all customers who have an account at all branches located in Brooklyn city. customer_name, branch_name (depositor account)  branch_name (branch_city = “Brooklyn” (branch))