Chap. 3 Relational Model

*Textbook: Chapter 2 (6판/7판)

Why Relational Model?

‧ Problems of hierarchical and network model: Data dependence (종속성)

DBMS

Database

AP1

AP2

APn

……

종속성(Dependence)

⇒독립성(Independence) 제공

① Ordering dependence

ex) 예금액이 100,000원 미만인 계좌번호는?

계좌 table - Case 1: Ascending order by 계좌번호

Case 2: Ascending order by 예금액

계좌			계좌
계좌번호	예금액		계좌번호	예금액
556	90,000		647	85,000
647	85,000		556	90,000
801	150,000		900	100,000
900	100,000		801	150,000

⇒ Different application programming for Case 1 and Case 2.

② Indexing dependence

ex) 801 계좌의 예금액은?

계좌 table - Case 1: No index.

Case 2: Index on 계좌번호

계좌			계좌			계좌번호-index
계좌번호	예금액		계좌번호	예금액		Pointer	계좌번호
647	85,000		647	85,000			556
556	90,000		556	90,000			647
900	100,000		900	100,000			801
801	150,000		801	150,000			900

⇒ Different application programming for Case 1 and Case 2.

③ Access path dependence

ex) 예금액이 100,000원 미만인 고객은?

Case 1: 예금 link - 고객 → 계좌

예금 link

이순신  대구 수성동

안중근 서울 신촌

유관순  대전 둔산동

900  100,000

647   85,000

647   85,000

556   90,000

고객

801  150,000

계좌

Case 2:  예금 link - 계좌 → 고객

예금 link

이순신  대구 수성동

안중근 서울 신촌

900  100,000

647   85,000

556   90,000

안중근 서울 신촌

유관순  대전 둔산동

계좌

801  150,000

고객

유관순  대전 둔산동

⇒ Different application programming for Case 1 and Case 2.

‧ Relational model

- E. F. Codd가 1970년대 초에 제안.

- 사용자는 원하는  데이터를 어떻게(How) 찾아야 하는가를 Program할 필요가 없고, 단지 무엇을(What) 원하는가만 지정하면 됨.

⇒ Data independence

ex) Assembler ↔ Compiler

- SQL로 작성된 Query는 Query Processor에 의해 최적화(Optimized)된 Program으로 변환되어 실행됨.

ex1) SELECT 계좌번호

FROM 계좌

WHERE 예금액 < 100000

ex2) SELECT 예금액

FROM 계좌

WHERE 계좌번호 = 801

ex3) SELECT 고객명

FROM 고객, 계좌

WHERE 고객.계좌번호 = 계좌.계좌번호 AND

예금액 < 100000

‧ 강의내용

- Entity set과 relationship set들을 저장하는 Table 구조는 수학적으로 어떻게 정의되는가?

⇒ Relation.

- 원하는 정보를 얻기 위해서 Relation들에 관한 계산은 어떻게 하는가?

⇒ Operations of relational algebra.

Relational Model

‧ The primary data model for commercial data processing application.

ex) ‘정형화’된 문자나 숫자 데이터를 적은 인사 기록카드를 파일에 저장.

⇔ A table of records.

‧ Engineering application: CAD, GIS, etc.

⇒ A group of geometrical ‘objects’

ex) 5 rectangles, 1 ellipse, 4 circles, 1 line, 1 curve

⇒ ‘Object’-oriented model.

ex) Class Hierarchy

⇔ Class 개념 제공: Class/subclass/object, User-defined types, etc.

Figure

quadrangle

ellipse

curve

rectangle

square

What is a Relation?

Def) For sets A, B⊆U, the Cartesian product (or cross product) of A, B is denoted by A×B and equals {(a,b)| a∈A, b∈B}.

ex) Let U={1,2,3,4,5,6,7}

A={2,3,4}

B={4,5}

A×B={(2,4),(2,5),(3,4),(3,5),(4,4),(4,5)}

B×A?

A×A?

Def) For sets A, B⊆U, any subset of A×B is called a relation from A to B.

ex) Let U={1,2,3,4,5,6,7}

A={2,3,4}

B={4,5}

A×B={(2,4),(2,5),(3,4),(3,5),(4,4),(4,5)}

Relations?

How many relations we have? The power set of A×B

6C0+6C1+ … +6C6=26

(By binary theorum, ∑k=0,n nCn-k․xk․yn-k = (x+y)n)

‧ A table of n columns must be a subset of

D1×D2× … ×Dn

where Di: Domain of the ith set.

D1	× D2		⊇	학생
학생명		시도		학생명	시도
홍길동		서울		홍길동	부산
김철수		대전		김철수	서울
박미영		부산		박미영	서울

ex)

⇒ 학생 table = a relation

‧ Any row of a table must consist of a n-tuple(순서쌍),

(v1, v2, … , vn)

where vi is a element in the domain Di.

‧ entity set (relationship set) ⇔ table   ⇔ relation ⇔ file

entity     (relationship)     ⇔ row    ⇔ tuple   ⇔ record

attribute	⇔ column ⇔ domain ⇔ field

‧ A relation scheme: A list of attributes and their corresponding domains.

ex) 계좌-scheme (계좌번호,지점명,고객명,예금액)

계좌번호: serial   /* entity integrity */

지점명: char(20)

고객명: char(10)

예금액: integer

‧ Order of tuples is ‘irrelevant’.

⇒ Tuples may be stored in an arbitrary order.

계좌

degree: 속성의 갯수

cardinality: 튜플의 갯수

‧ Schema Diagram: 주키와 외래키 간의 참조(reference) 관계를 나타냄.

⇒ 참조하는 relation의 외래키로부터 참조된 relation의 주키로 이르는 화살표로 나타냄.

Relational Algebra

‧ Takes one or two relations as input and

produce a new relation as their result.

‧ Fundamental operations: 기본 연산 (p.199, 6th ed.)

① Select: 선택

- Select rows.

σθR (θ: conditions)

ex) σ(지점명=‘신촌’ and 예금액>100,000) (계좌)

p.199 Fig.6-2 (6th ed.)

② Project: 추출

- Select columns.

πA R (A: attributes)

ex) π계좌번호,고객명 (계좌)

p.201 Fig.6-3 (6th ed.)

③ Cartesian Product: 카티션 곱

R×S

ex) 고객×계좌

p.201 Fig.6-8 (6th ed.)

ex) SQL 실습 DB:

http://comedudb6.knue.ac.kr/tykim/Myhome/Dbnote/db-chap4-1.pdf

④ Rename: 재명명

- Returns relation R under the name X.

ρX R

ex)	‘서울’시에 사는 고객들? π고객명 σ시=‘서울’ (고객)

‘유관순’과 같은 시에 사는 고객들?

π고객.고객명(σ고객.시=고객2.시(고객×(π시(σ고객명=‘유관순’(ρ고객2 (고객)))))))

고객
고객명	주민번호	시	동
유관순		서울

⇒ This is used when the same relation appears more than once in a query.

p.208 Fig.6-11 (6th ed.)

⑤ Union: 합집합

R∪S

ex) ‘신촌’ 지점에 거래하는 모든 고객들?

(π고객명(σ지점명=‘신촌’(예금))) ∪ (π고객명(σ지점명=‘신촌’(대출)))

예금					대출
예금계좌번호	지점명	고객명	예금액		대출계좌번호	지점명	고객명	대출액
	신촌					신촌

p.202 Fig.6-5 (6th ed.)

⑥ Difference: 차집합

R-S

ex) ‘신촌’ 지점에 예금 거래만 하는 모든 고객들?

(π고객명(σ지점명=‘신촌’(예금))) - (π고객명(σ지점명=‘신촌’(대출)))

p.203 Fig.6-6 (6th ed.)

가장 큰 예금액을 가진 고객명?

(π고객명,예금액(예금))

- (π고객명,예금.예금액(σ예금.예금액<예금2.예금액(예금×(ρ예금2 (예금)))))

p.208 Fig.6-11 (6th ed.)

* The fundamental operations of the relational algebra are 'sufficient' to express any relational query.

⇒ Completeness of the relational algebra.

‧ Additional operations: 추가 연산 (p.209, 6th ed.)

- We define additional operations that do not add any power to the algebra, but simplify common queries.

ex) +, -, ×, ÷

① Intersection: 교집합

R∩S = R-(R-S)

ex) ‘신촌’ 지점에 예금거래와 대출거래를 모두 하는 고객들?

(π고객명(σ지점명=‘신촌’(예금))) ∩ (π고객명(σ지점명=‘신촌’(대출)))

p.210 Fig.6-13 (6th ed.)

② (Natural) Join: 자연 조인 (Product, select and project)

[eqn: R∞S~ = & Π_r∪s left{σ_{(R.A_1 = S.A_1 )~and~ ... ~and~ (R.A_n = S.A_n )} R×S right} # & where~ r~:~R~ has~attribute~ X_1 ...X_s A_1 ... A_n # &~~~~~~~s~:~S~ has ~attribute~ Y_1 ...Y_t A_1 ... A_n # &~~~~~~~r ∪ s~:~X_1 ...X_s A_1 ... A_n Y_1 ... Y_t]

⇒ 두 table을 link하는 연산.

r∩s = A1A2…An : 공통된 attr. 중에서 Join attribute(s)를 지정.

default: r∩s

What if r∩s = φ?  R∞S = R×S

p.211 Fig.6-14 (6th ed.)

ex)	π고객명 (σ예금액>95,000 (고객 ∞ 계좌))

= π고객명 (σ고객.계좌=계좌.계좌 AND 예금액>95,000 (계좌×고객))

= π고객명 ((π고객명,계좌 고객) ∞ (σ예금액>95,000 계좌))

⇒ Which one has better performance?

고객						계좌
고객명	시	동	계좌			계좌	예금액
안중근	서울	신 촌	556			900	100,000
안중근	서울	신 촌	647			556	90,000
유관순	대전	둔산동	801			647	85,000
유관순	대전	둔산동	647			801	150,000
이순신	대구	수성동	900
		Projection					Selection
	고객명	계좌				계좌	예금액
	안중근	556				900	100,000
	안중근	647				801	150,000
	유관순	801
	유관순	647
	이순신	900
				Join
			고객명	계좌	예금액
			이순신	900	100,000
			유관순	801	150,000
					Projection
				고객명
				이순신
				유관순

ex) ‘신촌’ 지점에 예금거래와 대출거래를 모두 하는 고객들?

가정: 고객명은 한 지점내에서는 모두 다름.

[eqn: Π_고객명left (σ_{지점명='신촌'}(예금∞대출)right)]

⇔[eqn: Π_고객명left (σ_{지점명='신촌'}(예금)∞σ_{지점명='신촌'}(대출)right)]

⇒ 같은 query를 두 개 이상의 relational algebra 식으로 표현이 가능함.

⇒ Which one has better performance?

⇒ Query optimiation: Rule-based/Cost-based

③ Outer Join: 외부 조인

- Null값을 다룰 수 있도록 Join을 확장함.

⇒ 누락된 정보들도 Join 결과에 포함시킴.

ex)	Left outer join: p.214 Fig.6-17 (6th ed.)

Right outer join: p.215 Fig.6-18 (6th ed.)

Fully outer join: 양쪽 다 포함

④ Assignment: 배정

temp ← relational algebra

⇒ A nested query can be written as a sequential form consisting of a series of assignment

ex)  Nested form

σ(π(σ(R)))

⇔ sequential form

temp1  ← σ(R)

temp2  ← π(temp1)

temp3  ← σ(temp2)

p.213 (6th ed.)

⑤ Division: Project, product and difference

[eqn: R~÷~S~ = & Π_{X_1 ...Xs}( R) - Π_{X_1 ... Xs}~ ((Π_{X1 ... Xs}~(R)×S ) -~R)# & where~ r~:~R~ has~attribute~ X_1 ...X_s A_1 ... A_n # &~~~~~~~s~:~S~ has ~attribute~ A_1 ... A_n ~~division~ attribute, ~s⊆r]

⇒ Dividend table에서 divisor table의 tuple값을 모두 갖고 있는 tuple들을 골라내는 연산.

ex)

R			S		R÷S
A	B		B		A
a	x		x		a
a	y		z
a	z
b	x
c	y

ex) ‘서울’에 있는 모든 지점에 예금계좌를 갖고 있는 고객명?

지점				예금
지점명	시	자산		예금계좌번호	지점명	고객명	예금액
압구정 신촌 수성동 남신동	서울 서울 대구 대구			111 112 113 114	압구정 압구정 신촌 신촌	유관순 안중근 유관순 이순신

⇒        R                   S

지점명	고객명	÷	지점명	=	고객명
압구정	유관순		압구정		유관순
신 촌	유관순		신 촌
압구정	안중근
신촌	이순신

[eqn: Π_지점명,고객명 예금~÷~Π_지점명 (σ_시='서울' 지점)]

‧ 확장된 연산

① Generalized Projection: 일반화 추출

- 추출시 산술함수를 허용.

p.215 (6th ed.)

② Aggregation Functions: 집합체 함수

- Sum(), Avg(), Count(), Max(), Min() 등.

- group(ɡ)

p.215 Fig.6-20 (6th ed.)

Tuple Relational Calculus

‧ The tuple relational calculus is a nonprocedural language. (비절차적)

⇒ The relational algebra was procedural. (절차적 - 연산순서 명시)

⇒ Formal description of the information desired. (원하는 정보의 내용만 기술)

⇒ 논리(logic) 기호를 사용

‧ A ‘query’ in the tuple relational calculus is expressed as

{t |P(t)}

i.e. the set of tuples for which predicate P is true.

⇒ 즉, 술어 P가 참인 모든 투플 t의 집합

‧ We also use the notation

t[A] : to indicate tuple t on 'attribute' A.

t∈r : to show that tuple t is in 'relation' r.

ex) 대출액이 1200만원이 넘는 loan-number, branch-name, amount를 찾아라.

{t |t∈loan ∧ t[amount]＞12000000}

loan

loan-number	branch-name	amount

loan-number 속성만 필요할 경우?

‧ Several ‘tuple variables’ may appear in a formula. (투플 변수)

⇒ A tuple variable is said to be a ‘free variable’ unless it is quantified by a ∃(there exists) or a ∀(for all). (자유 변수)

⇒ Then it is said to be a ‘bound variable’. (한정 변수)

∃t ∈ r(Q(t)): "술어 Q(t)가 참인 릴레이션 r에 투플 t가 존재한다. "

∀t ∈ r(Q(t)): "릴레이션 r의 모든 투플 t에 대해 술어 Q(t)가 참이다. "

ex) 대출액이 1200만원이 넘는 'loan-number'를 찾아라.

{t |∃s ∈ loan(t[loan-number]=s[loan-number] ∧ s[amount]＞12000000}

⇒ “투플 t와 s가 속성 loan-number에 같은 값을 가지고 있고 s의 amount 값이 1200만원이 넘는 투플 s가 릴레이션 loan에 존재하는 모든 투플 t의 집합을 구하라.”

⇒ 투플 변수 t는 'loan-number 속성에만 정의'된다. t에 지정된 조건은 오직 이 속성에만 유효하기 때문이다.

⇒ 따라서 결과는 전체 투플이 아닌 loan-number만의 릴레이션이다.

ex) Perryridge 지점에 대출이 있는 모든 고객들의 '이름'을 찾아라.

{t |∃s ∈ borrower(t[customer-name]=s[customer-name]

∧ ∃u ∈ loan(u[loan-number]=s[loan-number]

∧ u[branch-name]='Perryridge') ) }

⇒ 두 릴레이션 borrower와 loan을 죠인

⇒ 투플 변수 u는 고객이 Perryridge 지점의 대출자임을 보장.

ex) 은행에 대출, 계좌 또는 양쪽을 가지고 있는 모든 고객들을 찾아라.

{t |∃s ∈ borrower(t[customer-name]=s[customer-name]

∨ ∃u ∈ depositor(t[customer-name]=u[customer-name]}

ex) 은행에 대출은 가지고 있지만 계좌는 가지고 있지 않은 모든 고객들을 찾아라.

{t |∃s ∈ borrower(t[customer-name]=s[customer-name]

∧ ￢∃u ∈ depositor(t[customer-name]=u[customer-name]}

‧ A ‘formula’ is built of atoms. (식은 원자들로 이루어진다.)

An atom is one of the following forms:

- s∈r, where s is a tuple variable, and r is a relation (∉ is not allowed).

- s[x]θu[y], where s and u are tuple variables, and x and y are attributes, and θ is a comparison operator (＜, ≤, ＝, ≠, ≥, ＞, 비교연산자).

- s[x]θc, where c is a ‘constant’ in the domain of attribute x. (상수)

‧ Formulae are built up from atoms using the following rules: (규칙들)

- An atom is a formula.

- If P is a formula, then so are ￢P and (P).

- If P1 and P2 are formulae, then so are  P1∧P2, P1∨P2 and P1⇒P2.

- If P(s) is a formula containing a free tuple variable s, then the followings are formulae also.

∃s ∈ r(P(s)) and ∀s ∈ r(P(s))

‧ Note some equivalences: (동등성들)

- P1∧P2  = ￢(￢P1∨￢P2)	// and-or 관계

-	∀t∈r(P(t)) =￢∃t∈￢r(P(t))	// ∀-∃ 관계

릴레이션 r의 모든 투플 t에 대해 술어 P(t)가 참이다.

⇔ 릴레이션 r에 술어 P(t)를 만족하지 않는 투플 t는 존재하지 않는다.

-	P1⇒P2 =￢P1∨P2	// P1이면 P2이다 - 내포(implication)

P1이 참이면 P2는 반드시 참이다.

not(￢)과 or(∨)의 사용보다는 직관적인 표현방식.

‧ 안전한 표현(safe expression)

- 무한 릴레이션의 생성

{t | ￢(t ∈ borrower) }

⇒ 릴레이션 loan에 속하지 않은 투플들은 ‘무한히’ 많다.

⇒ ‘unsafe’ expression

‧ 표현 능력

- The tuple relational calculus restricted to safe expressions is ‘equivalent’ in expressive power to the relational algebra.

⇒ 모든 관계 대수 표현식에 대해 ‘동등한’ 안전한 투플 관계 해석 표현식이 존재하며, 또한 그 반대의 경우도 마찬가지이다.