Bài giảng Cơ sở dũ liệu - Chương 6: Phép toán quan hệ

So sánh đại số quan hệ và phép 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ạ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. The calculus formation is descriptive while the algebraic one is prescriptive 6Phép tính quan hệLà 1 phân nhánh của logic vị từ (predicate logic)Được dùng trong CSDL dướ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 – DRC)7Phép tính quan hệ bộ - TRCCác query trong TRC đều có dạng:	{T| Condition}Target chứa biến bộ (Tuple variable) TVí dụ: tìm tất cả thông tin các môn học được dạy trong mùa thu 2007{ T | TEACHING(T) AND T.Semester = ‘F2007’}SELECT * FROM TEACHINGWHERE T.Semester = ‘F2007’ SQL là 1 biến thể về mặt cú pháp của TRCTarget8Cú pháp của conditionCó thể 1 trong các dạng sau:P(T): P là tên quan hệ và T là biến bộ. P(T) được dùng để kiểm tra bộ T có thuộc về P hay khôngT(A) oper S(B) với oper là toán tử so sánh. T và S là biến bộ, A và B là các thuộc tínhT.A oper const. Tương tự như trên nhưng T được so sánh với hằng số Các điều kiện trên được gọi là điều kiện nguyên tố ( atomic condition)9Điều kiện phức(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 queryNếu C là điều kiện của query, R là tên quan hệ và T là biến bộ thì T  R (C) và T  R (C) cũng là điều kiện query10Lượng từLượng từ tồn tại (existential quantifier): T  R (C)  tồn tại 1 bộ tr sao cho C trở nên đúng sau khi t được thay thế bởi TLượng từ phổ quát (universal quantifier): T  R (C)  với mọi bộ t  r, C trở nên đúng nếu t được thay thế bởi biến T.11Biến (variable)Nếu biến bộ đứng sau 1 lượng từ ,  được gọi là biến buộc ( bound variable). Ngược lại là biến tự do (free variable)X là biến tự do trong phát biểu “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 gán 1 giá trị cho XX là biến buộc (được định lượng) trong phát biểu “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 tại bất kỳ 1 thời điểm nào đó của database12So sánh biến buộc và biến tự do trong TRCBiến buộc (Bound variable) được dùng để đánh giá các bộ trong 1 quan hệ (được dùng trong condition) Biến tự do (Free variable) được dùng cho các bộ được trả về bởi truy vấn (được dùng trong targetKhi 1 giá trị được thay thế cho biến S thì điều kiện sẽ trở nên true hoặc falseChỉ có biến S là biến tự do trong điều kiện{S | Student(S) AND ( T Transcript (S.Id = T.StudId AND T.CrsCode = ‘CS305’))}13Ví dụ 1{E| COURSE(E) AND S STUDENT (T TRANSCRIPT(T.StudId = S.Id AND T.CrsCode = E.CrsCode))} ???Liệt kê tất cả các môn học mà mọi sinh viên đều học14Ví dụ 2Liệ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 ứngSELECT P.NameFROM PROFESSOR P, TEACHING TWHERE P.Id= T.ProfId AND T.CrsCode = ‘MGT123’15Ví dụ 3Tìm mã số tất cả các sinh viên đã học cùng 1 môn 2 lần ở những học kỳ khác nhau{T.StudId | TRANSCRIPT(T) AND T1  TRANSCRIPT( T.StudId = T1.StudId AND T.CrsCode = T1.CrsCode AND T.Semester  T1.Semester)}16Một số lưu ý khi dùng lượng từCác lượng từ tồn tại () kề nhau có thể hoán vị cho nhauVí dụ:R  TRANSCRIPT (T  TEACHING)(..))T  TEACHING (R  TRANSCRIPT)(..)) 17Một số lưu ý khi dùng lượng từCác lượng từ phổ quát () và tồn tại () không hoán vị cho nhau đượcVí dụ:T  TEACHING(R  TRANSCRIPT ..)“For every TEACHING tuple there is a TRANSCRIPT tuple such that statement St is true”Khác vớiR  TRANSCRIPT (T  TEACHING  C)“There is a TRANSCRIPT tuple such that for all TEACHING tuples St is true”18Một số lưu ý khi dùng lượng từCác lượng từ tương tự như khối begin/end, dùng để xác định phạm vi của biếnVí dụ: T  R1( U(T) AND T  R2(V(T)))  Biến T xuất hiện 2 lần dưới những lượng từ khác nhau, nên được xem như 2 biến trùng tên độc lập nhau và tương đương với biểu thức sau:T  R1( U(T) AND S  R2(V(S)))19Dùng view trong TRCLiệt kê tất cả sinh viên đã học những môn mà được dạy bởi tất cả các giáo sư CSCách 1:{R.StudId| T  TEACHING (T1  TEACHING (TRANSCRIPT(R) AND T.ProfId= T1.ProfID AND T1.CrsCode = R.CrsCode AND T1.Semester = R.Semester))}Cách 2 :Tạo 1 view như sau:CSPROF = {P.ProfId| PROFESSOR(P) AND P.DeptId = ‘CS’}Tạo query{R.StudId | P  CSPROF (T1  TEACHING (TRANSCRIPT(R) AND P.ProfId = T1.ProfId AND T1.CrsCode = R.CrsCode AND T1.Semester = R.Semester))} 20Truy vấn SQL và truy vấn TRCMột số sách SQL đã dựa vào đại số quan hệ để xác định ngữ nghĩa khi phát ra các truy vấn SQLBiểu thức đại số cũng không trực giác hơn truy vấn TRC và cũng không hỗ trợ nhiều với SQL cao cấp.Việc dịch truy vấn SQL có subquery thành biểu thức đại số không dễ dàngĐại số quan hệ không phải là phương tiện tốt để dịch truy vấn SQL thành English để kiểm tra xem nó có đúng yêu cầu mong đợi không.21Truy vấn SQL và truy vấn TRCMặc dù mô tả bằng tiếng Anh không chính quy bằng định nghĩa toán học nhưng nó giúp cho cả khách hàng và người lập trình dễ hiểu nhau hơnSQL query liệu có thỏa mãn những định nghĩa bằng tiếng Anh?22So sánh giữa SQL và TRCCó 1 sự tương đương gần giữa SQL và TRC.Với 1 SQL query, xây dựng 1 TRC query tương đương, sau đó dịch TRC query này thành tiếng Anh Chuyển bài toán kiểm chứng SQL query xuống thành bài toán dịch SQL thành TRC  Với các query phức tạp (có subquery) thì việc dịch này sẽ như thế nào??23Dịch SQL thành TRCXét 1 mẫu SQL phức như sau:SELECT R1.A, R2.CFROM REL1 R1, REL2 R2WHERE Condition1(R1, R2) AND R1.B AND (SELECT R3.E	FROM REL3 R3, REL4 R4	WHERE Condition2(R2, R3, R4))Biến R3, R4 là cục bộ của subquery và R1, R2 là biến toàn cục24Dịch SQL thành TRCSubquery được tham số hóa bởi biến toàn cục R2Condition2 của subquery hiển nhiên không phải là dạng mà TRC hiểu đượcCách giải quyết: dùng view với tập thuộc tính của danh sách đích của subquery ( tức R3.E) cùng với biến R225Dịch SQL thành TRCView có tên Temp được định nghĩa như sau:Temp = {R3.E,R2.C, R2.D | REL2(R2) AND REL3(R3) AND R4  REL4 (Condition2(R2,R3,R4)) }Biến R2, R3 là free nhưng biến R4 phải định lượng vì nó không xuất hiện trong danh sách đích (target) của view26Dịch SQL thành TRCSQL query được dịch thành TRC:{R1.A, R2.C| REL1(R1) AND REL2(R2) AND Condition1(R1,R2) AND R TEMP (R.E= R1.B AND R.C= R2.C AND R.D = R2.D) }27Phép tính quan hệ miềnDomain relational calculus (DRC)Là cơ sở cho ngôn ngữ truy vấn trực quan như MS Access, IBM QBE, Borland ParadoxDRC tươ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)28Domain variableBiến miền sẽ nhận giá trị từ miền giá trị (domain) của 1 thuộc tính nào đó.Ví dụ: quan hệ TEACHING có thuộc tính ProfId với miền giá trị chứa các số Id hợp lệ. Nếu biến Pid là biến miền thì nó sẽ có giá trị từ miền chứa các ID hợp lệ này.29DRC queryKết quả của DRC query cũng là 1 quan hệ và có dạng chung sau:{X1,,Xn| Condition}Ví dụ: TRC và DRC query tương đương nhau:{Pid, Code | TEACHING (Pid, Code, F2007)}{T | TEACHING(T) AND T.Semester=‘F2007’}DRC query đơn giản hơn, loại trừ được phép so sánh T.Semester=‘F2007’Biến miềnTarget30DRC và TRCDRC và TRC tương tự nhau. Nhiều tính năng, kỹ thuật giống nhau. Các quy tắc về biến tự do và biến buộc của DRC tương tự như TRCCác biến đích ( target variable) chỉ đượ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 phần target (đích)31Điều kiện cơ bảnAtomic conditionCú 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ềnX oper Y với oper là toán tử so sánh, X và Y là biến miềnX oper const: tương tự như trên nhưng so sánh với hằng số const32Điều kiện phứcCá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 conditionIf 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 queryNếu C là điều kiện của query, R là tên của quan hệ và X là biến miền thì X  R.A (C) và X  R.A (C) cũng là điều kiện của query33Lượng từ và biến miềnX  R.A (C) đọc là “ với mọi giá trị xảy ra trong cột A của quan hệ R thì điều kiện C phải đúng và X  R.A (C) đọc là “ có ít nhất một giá trị x trong cột R.A sao cho C trở nên true nếu x được thay thế cho tất cả các biến X 34DRC queryCó dạng {X1,...,Xn| condtion}Trong đó Xi với i=1,..n hoặc là biến tự do xuất hiện trong condition hoặc là hằng số. Kết quả của query trên là 1 tập tấ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 đúng35DRC queryDRC 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 TRC dùng cho cả bộMiền phổ dụng ( universal domain) U chứa tất cả các giá trị trong tất cả các domainX  U (Condition) được viết tắt thành X (Condition) 36Ví dụLiệt kê tên tất cả các giáo sư dạy môn MGT123{N| I  PROFESSOR.Id D  PROFESSOR.DeptId (PROFESSOR(I,D,N) AND S  TEACHING (I, MGT123, S)))}37Mối quan hệ giữa đại số quan hệ, phép tính quan hệ TRC, DRC Cả 3 ngôn ngữ đều có khả năng diễn đạt mạnh như nhau: các query được viết bằng ngôn ngữ này có thể được viết bằng ngôn ngữ khác 38Tương đương của 3 ngôn ngữPhép chọn (selection)Algebra:  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 Condition2 sẽ là X1=X2 AND X3=d39Tương đương của 3 ngôn ngữPhép chiếu (Projection)	Algebra: A,B,C(R) TRC: {T.A, T.B, T.C| R(T)}DRC: {X,Y,Z| VW R(X,Y,Z,V,W)}Giả sử R có 5 attribute với A,B,C là 3 thuộc tính đầu40Tương đương của 3 ngôn ngữTích DescartesAlgebra: R xSTRC: {T.A, T.B, T.C, V.D, V.E| R(T) AND S(V)}Giả sử R có 3 thuộc tính A,B,C và S có 2 thuộc tính D,EDRC: {X,Y,Z,V,W | R(X,Y,Z) AND S(V,W) } 41