Chương 7: Phép tính quan hệ

Chương 7

PH ÉP TÍN H  Q UA N  H Ệ PH ÉP TÍN H  Q UA N  H Ệ

1

ộ

ộN i dung N i dung

 Phép tính quan hệ

ệ ộ ệ

ề  M i quan h gi a đ i s quan h và phép

• Phép tính quan h b (TRC) • Phép tính quan h mi n (DRC) ố

ệ ữ ạ ố

ệ

tính quan hệ

2

ở ầM đ u ở ầ M đ u

 Đ i s quan h đ

c dùng đ gi i thích các truy v n SQL ệ ượ ể ả ấ

đ c đánh giá nh th nào ư ế

ạ ố ượ  DBMS th ườ ạ ố

ư c khi t ng dùng đ i s quan h nh ngôn ng trung ữ ệ i u hóa th c ướ ố ư ể ị ự ậ

 Xét v m t khái ni m, thì SQL l

gian b c cao dùng đ d ch query tr thi

ệ ạ i d a vào 1 ngôn ng ữ ự

truy v n chính quy hoàn toàn khác (formal query language) ề ặ ấ

3

 Relational calculus (phép tính quan h )ệ

ạ ố ạ ố

ệ ệ

So sánh đ i s quan h và phép So sánh đ i s quan h và phép tính quan hệ tính quan hệ

 Đ i s quan h (relational algebra) có tính th t c, g n

ủ ụ ầ

 Phép tính quan h (relational calculus) không có tính th ủ

ạ ố v i ngôn ng l p trình ớ ệ ữ ậ

ệ

ầ ơ

nhiên h n t kê các nhà cung c p chuyên ụ ấ

4

t c và g n v i ngôn ng t ữ ự ớ ụ  Ví d : xét query sau “ li ệ cung c p ph tùng s 2” ụ ấ ố

ạ ố ạ ố

ệ ệ

So sánh đ i s quan h và phép So sánh đ i s quan h và phép tính quan hệ tính quan hệ

 N u theo đ i s quan h thì trinh t

th c hiên nh sau: ạ ố ệ ế ự ự ư ̀ ̣

1) T o m i k t n i t nhiên c a 2 quan h SUPPLIER ố ế ố ự ạ ủ ệ

và SHIPMENT trên thu c tính S#; ộ

2) Dung phep chon thu h p k t qu c a k t n i này, ế ố ̀ ́ ̣

ẹ ch còn lai các b liên quan đ n ph tùng P2; ả ủ ụ ế ế ộ ỉ ̣

3) Dùng phép chi u (project) đ k t qu ch còn l i ể ế ế ả ỉ ạ

5

thu c tính S#. ộ

ạ ố ạ ố

ệ ệ

So sánh đ i s quan h và phép So sánh đ i s quan h và phép tính quan hệ tính quan hệ

 N u theo phép tính quan h thì:

ồ ế ệ • Tìm mã nhà cung c p S# sao cho t n t ạ ấ

ể

 Phép tính quan h thì mô t

i 1 v n ậ chuy n hàng SP nào đó có cùng mã S# và có mã ph ụ tùng P# là P2.

, đ i s quan h đ a ra qui ệ ả ạ ố ệ ư

6

t c, cách dùng. ắ

Phép tính quan hệ Phép tính quan hệ

 Là 1 phân nhánh c a logic v t  Đ c dùng trong CSDL d ướ

(predicate logic) ủ

ị ừ i 2 d ng: ạ ượ

 Phép tính quan h b (Tuple relational calculus –TRC)  Phép tính quan h mi n (Domain relational calculus – ệ ộ ệ ề

7

DRC)

Phép tính quan h b - TRC Phép tính quan h b - TRC

ệ ộ ệ ộ

 Các query trong TRC đ u có d ng:

Target

Target ch a ứ bi n b (Tuple variable) ế ộ t c thông tin các môn h c đ c d y trong mùa ạ ề {T| Condition} T ọ ượ ạ ấ ả

 Ví d : tìm t ụ thu 2007 { T | TEACHING(T) AND T.Semester = ‘F2007’} SELECT * FROM TEACHING

ủ ế

́ ́ ̣

Teaching(T) tương ưng vơi mênh đê  T.Semester = ‘F2007’ tương ưng vơi

8

́ WHERE T.Semester = ‘F2007’  SQL là 1 bi n th v m t cú pháp c a TRC ể ề ặ ̀ FROM  ́ WHERE

Cú pháp c a condition ủ Cú pháp c a condition ủ

Có th là 1 trong các d ng sau: ể ạ

ế ượ c dùng đ ể

 P(T): P là tên quan h và T là bi n b . P(T) đ ệ ộ ề

 T(A) oper S(B) v i oper là toán t

ộ ki m tra b T có thu c v P hay không ể ộ

so sánh. T và S là bi n ớ ử ế

 T.A oper const. T

b , A và B là các thu c tính ộ ộ

ng t nh trên nh ng T đ c so sánh ươ ự ư ư ượ

v i h ng s ớ ằ ố

c g i là đi u ki n nguyên t ệ ượ ề ệ ọ ố

9

 Các đi u ki n trên đ ề ( atomic condition)

ề ề

Đi u ki n ph c ứ ệ Đi u ki n ph c ứ ệ (Complex condition) (Complex condition)

 Các đi u ki n ph c đ

ứ ượ ệ ề c xây d ng m t cách đ quy nh ư ự ệ ộ

ủ ề ệ ế ề sau: • C là 1 đi u ki n c a query n u nó là 1 đi u ki n ệ

nguyên tố

ế ề

ệ ủ ề

• N u C1 và C2 là đi u ki n c a query thì C1 AND C2, ệ ủ C1 OR C2 và NOT C1 cũng là đi u ki n c a query • N u C là đi u ki n c a query, R là tên quan h và T là ệ ủ R (C) và $ T ˛ R (C) cũng là đi u ề

ệ

ộ

10

ề " T ˛ bi n b thì ki n query ế ế ệ

ng t ng t

L ượ L ượ

ừ ừ

ng t i (existential quantifier): ượ t n t ừ ồ ạ

 L $ T ˛ t đ

r sao cho C tr nên đúng sau khi ộ ˛ i 1 b t ở

c thay th b i T R (C)  t n t ượ ồ ạ ế ở

 L " T ˛

ng t ph quát (universal quantifier): ượ ừ ổ

r, C tr nên đúng n u t đ c ế ở ượ

11

ọ ộ ˛ R (C)  v i m i b t ớ ế thay th b i bi n T. ế ở

ế

ếBi n (variable) Bi n (variable)

ế ộ ứ

 N u bi n b đ ng sau 1 l ế bu c (bound variable). ộ variable)

 X là bi n t

ượ Ng ng t c l bi n ế c g i là ọ do (free , $ ừ " i là ạ ượ đ ượ bi n t ế ự

do trong phát bi u sau ế ự ể

“X is in CS305” (hay có th bi u di n thành C(X) ) ể ể ễ

Phát bi u trên không đúng cũng không sai cho đ n khi ế

12

ể gán 1 giá tr cho X ị

ế

ếBi n (variable) Bi n (variable)

 X là bi n bu c (đ ế

c đ nh l ng) trong phát bi u sau ộ ượ ị ượ ể

“there exists a student X such that X is in CS305” (bi u di n ễ ể

thành $ X˛ S (C(X)), v i S là t p h p t ) t c sinh viên ậ ớ ợ ấ ả

Phát bi u trên có th đ c gán giá tr TRUE/FALSE ể ượ ể ị

13

i b t kỳ 1 th i đi m nào đó c a database t ạ ấ ủ ể ờ

do do

ế ự ế ự

ế ế

ộ ộ

So sánh bi n bu c và bi n t So sánh bi n bu c và bi n t trong TRC trong TRC

 Bi n bu c (Bound variable) đ

ế ượ c dùng đ đánh giá các b ộ ể

ộ trong 1 quan h (đ c dùng trong condition)

ệ ượ do (Free variable) đ c dùng cho các b đ ượ ộ ượ c tr ả

c dùng trong target) ấ ượ

 Bi n t ế ự v b i truy v n (đ ề ở • Khi 1 giá tr đ

c thay th cho bi n S thì đi u ki n s ệ ẽ ế ế ề

ị ượ ặ

do trong đi u ki n ở ỉ ề ệ

T ˛ Transcript

14

tr nên true ho c false • Ch có bi n S là bi n t ế ự ế {S | Student(S) AND ($ (S.Id = T.StudId AND T.CrsCode = ‘CS305’))}

Ví d 1ụVí d 1ụ

 {E| COURSE(E) AND " S˛

STUDENT ($ T

 ???

˛ TRANSCRIPT(T.StudId = S.Id AND T.CrsCode = E.CrsCode))}

15

Li t kê t ệ ấ ả t c các môn h c mà m i sinh viên đ u h c ề ọ ọ ọ

Ví d 2ụVí d 2ụ

 Li

t kê tên c a t ệ ủ ấ ả t c giáo s đã d y môn MGT123?? ạ ư

{P.Name| PROFESSOR(P) AND $ T ˛ TEACHING (P.Id=

T.ProfId AND T.CrsCode = ‘MGT123’)}

 Câu l nh SQL t ệ

ng ng ươ ứ

SELECT P.Name

FROM PROFESSOR P, TEACHING T

16

WHERE P.Id= T.ProfId AND T.CrsCode = ‘MGT123’

Ví d 3ụVí d 3ụ

 Tìm mã s t ố ấ ả nh ng h c kỳ khác nhau ọ

t c các sinh viên đã h c cùng 1 môn 2 l n ọ ầ

17

ở ữ {T.StudId | TRANSCRIPT(T) AND $ T1 ˛ TRANSCRIPT( T.StudId = T1.StudId AND T.CrsCode = T1.CrsCode AND T.Semester „ T1.Semester)}

M t s l u ý khi dùng l M t s l u ý khi dùng l

ng t ng t

ộ ố ư ộ ố ư

ượ ượ

ừ ừ

 Các l Ví d :ụ

ng t ượ ừ ồ ạ $ t n t i ( ) k nhau có th hoán v cho nhau ể ề ị

18

$ R ˛ $ T ˛ TRANSCRIPT ($ T ˛ TEACHING ($ R ˛ TEACHING)(..)) TRANSCRIPT)(..))

M t s l u ý khi dùng l M t s l u ý khi dùng l

ng t ng t

ộ ố ư ộ ố ư

ượ ượ

ừ ừ

 Các l

" ph quát ( ) và t n t ) không hoán v cho ượ ừ ổ ồ ạ $ i ( ị

nhau đ ng t cượ

 Ví d :ụ " T ˛ “For every TEACHING tuple there is a TRANSCRIPT tuple such that statement St is true”

TEACHING($ R ˛ TRANSCRIPT ..)

TRANSCRIPT (" T ˛ TEACHING … C)

is a TRANSCRIPT tuple such that for all

19

Khác v iớ $ R ˛ “There TEACHING tuples St is true”

ề ề

Phép tính quan h mi n ệ Phép tính quan h mi n ệ Domain relational calculus (DRC) Domain relational calculus (DRC)

 Là c s cho ngôn ng truy v n tr c quan nh MS

ơ ở ữ ự ư

ấ Access, IBM QBE, Borland Paradox

 DRC t ế

ự ử ụ ư

ế ộ

20

ng t nh TRC, ch khác nhau là DRC s d ng ươ ỉ bi n mi n (Domain variable) thay cho bi n b (Tuple ề variable)

Domain variable Domain variable

 Bi n mi n s nh n giá tr t

mi n giá tr (domain) c a 1 ề ị ừ ề ẽ ủ ị

ế ộ

ụ

ế

 Ví d : quan h TEACHING có thu c tính ProfId v i ớ . N u bi n Pid là bi n ế này. ứ

21

mi n ch a các ID h p l ậ thu c tính nào đó. ệ mi n giá tr ch a các s Id h p l ố ị ứ mi n thì nó s có giá tr t ị ừ ẽ ộ ợ ệ ế ề ợ ệ ề ề

DRC query DRC query

 K t qu c a DRC query cũng là 1 quan h và có d ng

ả ủ ế ệ ạ

 Ví d : TRC và DRC query t

chung sau: Biến miền {X1,…,Xn| Condition}

Target ươ {Pid, Code | TEACHING (Pid, Code, F2007)} {T | TEACHING(T) AND T.Semester=‘F2007’}

ng nhau: ng đ ụ ươ

c phép so sánh ạ ơ ơ ừ ượ

22

DRC query đ n gi n h n, lo i tr đ ả T.Semester=‘F2007’

DRC và TRC DRC và TRC

 DRC và TRC t gi ng nhau.

ng t nhau. Nhi u tính năng, k thu t ươ ự ề ậ ỹ

 Các quy t c v bi n t

ố

do và bi n bu c c a DRC t ng ắ ề ế ự ộ ủ ế ươ

c phép là t do ỉ ượ ự

trong bi u th c đi u ki n ứ ể

• Cho phép các h ng s (constant) xu t hi n trong

ệ ố ệ ấ

23

t nh TRC ự ư • Các bi n đích ( target variable) ch đ ế ề ằ ph n target (đích) ầ

ề ề

Đi u ki n c b n ơ ả ệ Đi u ki n c b n ơ ả ệ Atomic condition Atomic condition

 Cú pháp c a atomic Condition (đi u ki n c b n) c a

ơ ả ủ ủ ệ ề

ệ ớ DRC QUERY: • P(X1,…,Xn) v i P là tên quan h và X1,…, Xn là

bi n mi n ề ế

• X oper Y v i oper là toán t ử ớ

so sánh, X và Y là bi n ế

mi nề

• X oper const: t h ng s const ố ằ

24

ng t nh trên nh ng so sánh v i ươ ự ư ư ớ

Đi u ki n ph c ứ ệ Đi u ki n ph c ứ ệ

ề ề

 Các condition ph c đ

ứ ượ c xây d ng đ quy nh sau: ệ ự ư

ề ệ ủ

• C là đi u ki n c a query n u nó là 1 atomic condition ế • If C1 và C2 là đi u ki n c a query thì C1 AND C2, C1 ệ ủ

ề

OR C2 và NOT C1 cũng là đi u ki n c a query ệ ủ ề

• N u C là đi u ki n c a query, R là tên c a quan h và ủ R.A (C) cũng

ế ệ

R.A (C) và $ X ˛ ế

25

ệ ủ ề " X ˛ X là bi n mi n thì ề là đi u ki n c a query ệ ủ ề

ng t ng t

L ượ L ượ

ừ ừ

và bi n mi n ế và bi n mi n ế

ề ề

R.A (C) đ c là “ v i m i giá tr x y ra trong c t A ọ ọ ộ

ệ ớ ệ ả

ấ ị

 " X ˛ ị ả c a quan h R thì đi u ki n C ph i đúng ề ủ  và $ X ˛ c t R.A sao cho C tr nên true n u x đ ộ t c các bi n X t ấ ả

ọ ở R.A (C) đ c là “ có ít nh t m t giá tr x trong c thay th cho ế ộ ượ ế

26

ế

DRC query DRC query

 Có d ng {X1,...,Xn| condtion}

ạ

ế ự ặ do xu t hi n ấ ệ

 K t qu c a query trên là 1 t p t

Trong đó Xi v i i=1,..n ho c là bi n t ớ trong condition ho c là h ng s . ằ ặ ố

ả ủ ọ ự ủ ậ ấ ả

27

t c các ch n l a c a ế b (x1,…, xn) sao cho khi thay x1 cho X1, x2 cho X2,… ộ thì condition tr nên đúng ở

DRC query DRC query

 DRC query th

ng s d ng nhi u bi n h n TRC t ử ụ ườ ề ơ

ng ươ ng vì bi n DRC dùng cho m i giá tr đ n trong khi bi n ế ỗ ế ị ơ

 Mi n ph d ng ( universal domain)

ế ứ TRC dùng cho c bả ộ

t c các ổ ụ ề ứ ấ ả U ch a t

 $ X ˛

t c các domain giá tr trong t ị ấ ả

28

c vi t thành $ X (Condition) ượ t t ế ắ U (Condition) đ

Ví dụVí dụ

 Li

t kê tên t ệ ấ ả t c các giáo s d y môn MGT123 ư ạ

PROFESSOR.Id $ D ˛

PROFESSOR.DeptId TEACHING (I, $ S ˛

29

{N| $ I ˛ (PROFESSOR(I,D,N) AND MGT123, S)))}

ố ố

ệ ệ

M i quan h gi a đ i s quan h , phép ạ ố ệ ữ M i quan h gi a đ i s quan h , phép ệ ữ ạ ố tính quan h TRC, DRC ệ tính quan h TRC, DRC ệ

ả ễ ạ

c vi ượ

 C 3 ngôn ng đ u có kh năng di n đ t m nh nh ạ ả ư t b ng ngôn ng này có th ể ữ ế ằ ữ

30

t b ng ngôn ng khác c vi ữ ề nhau: các query đ đ ượ ế ằ

T T

ng đ ng đ

ng c a 3 ngôn ng ng c a 3 ngôn ng

ươ ươ

ươ ươ

ủ ủ

ữ ữ

 Phép ch n (selection) ọ • Algebra: s Condition (R) • TRC: {T|R(T) AND Condition1} • DRC: {X1,…,Xn|R(X1,…,Xn) AND Condition2}

Trong đó: n u Condition có d ng A=B and C=d thì ế ạ

 Condition1 s là T.A = T.B AND T.C =D ẽ

31

 Condition2 s là X1=X2 AND X3=d ẽ

T T

ng đ ng đ

ng c a 3 ngôn ng ng c a 3 ngôn ng

ươ ươ

ươ ươ

ủ ủ

ữ ữ

Gi c ộ ầ ượ

s R có 5 attribute v i A,B,C là 3 thu c tính đ u đ ớ ả ử dùng trong phép chi uế  Phép chi u (Projection) ế • Algebra:

A,B,C(R)

• TRC:

P

• DRC:

{T.A, T.B, T.C| R(T)}

32

{X,Y,Z| $ V$ W R(X,Y,Z,V,W)}

T T

ng đ ng đ

ng c a 3 ngôn ng ng c a 3 ngôn ng

ươ ươ

ươ ươ

ủ ủ

ữ ữ

s R có 3 thu c tính A,B,C và S có 2 thu c tính D,E ộ ộ ả ử

• Algebra: R x S • TRC:

Gi  Tích Descartes

• DRC:

{T.A, T.B, T.C, V.D, V.E| R(T) AND S(V)}

33

{X,Y,Z,V,W | R(X,Y,Z) AND S(V,W) }