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

Chia sẻ: Trần Công Chính | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST

Báo xấu

395
lượt xem 89
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đạ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ường dùng đại số quan hệ như ngôn ngữ trung gian bậc cao dùng để dịch query trước khi tối ưu hóa thực thi. Xét về mặt khái niệm, thì SQL lại dựa vào 1 ngôn ngữ truy vấn chính quy hoàn toàn khác (formal query language). Relational calculus (phép tính quan hệ).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 7: Phép tính quan hệ

Chương 7 PH ÉP N H UA N Ệ TÍ Q H 1
N ộidung  Phép tính quan hệ • Phép tính quan hệ bộ (TRC) • Phép tính quan hệ miền (DRC)  Mối quan hệ giữa đại số quan hệ và phép tính quan hệ 2
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ường dùng đại số quan hệ như ngôn ngữ trung gian bậc cao dùng để dịch query trước khi tối ưu hóa thực thi  Xét về mặt khái niệm, thì SQL lại dựa vào 1 ngôn ngữ truy vấn chính quy hoàn toàn khác (formal query language)  Relational calculus (phép tính quan hệ) 3
So sánh đại số quan hệ và phép tính quan hệ  Đại số quan hệ (relational algebra) có tính thủ tục, gần với ngôn ngữ lập trình  Phép tính quan hệ (relational calculus) không có tính thủ tục và gần với ngôn ngữ tự nhiên hơn  Ví dụ: xét query sau “ liệt kê các nhà cung cấp chuyên cung cấp phụ tùng số 2” 4
So sánh đại số quan hệ và phép 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 thuộc tính S#. 5
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.  Phép tính quan hệ thì mô tả, đại số quan hệ đưa ra qui tắc, cách dùng. 6
Phé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) 7
Phép tính quan hệ bộ - TRC  Các query trong TRC đều có dạng: Target {T| Condition} Target chứa biến bộ (Tuple variable) T  Ví 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 TEACHING WHERE T.Semester = ‘F2007’  SQL là 1 biến thể về mặt cú pháp của TRC Teaching(T) tương ưng vơi mênh đê FROM ́ ́ ̣ ̀ T.Semester = ‘F2007’ tương ưng vơi WHERE ́ ́ 8
Cú pháp của condition Có thể là 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ông  T(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ính  T.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 query • Nế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 query 10
Lượ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 T  Lượ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. 11
Biế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 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 gán 1 giá trị cho X 12
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 tại bất kỳ 1 thời điểm nào đó của database 13
So sánh biến buộc và biến tự do 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)  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 target) • Khi 1 giá trị được thay thế cho biến S thì điều kiện sẽ trở nên true hoặc false • Chỉ 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’))} 14
Ví 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ọc 15
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 WHERE P.Id= T.ProfId AND T.CrsCode = ‘MGT123’ 16
Ví dụ 3  Tì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)} 17
Mộ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 nhau Ví dụ: ∃ R ∈ TRANSCRIPT (∃ T ∈ TEACHING)(..)) ∃ T ∈ TEACHING (∃ R ∈ TRANSCRIPT)(..)) 18
Mộ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 được  Ví 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” 19
Phép tính quan hệ miền 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ươ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) 20