chuong-6-phep-tinh-quan-he

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

Chương 6 Phép tóan quan hệ

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ệ)

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”

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 Thu hẹp kết quả của kết nối này chỉ

còn 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#

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

Phép tính quan hệ

 Là 1 phân nhánh của logic vị từ

(predicate logic)

• Phép tính quan hệ bộ (Tuple relational

calculus –TRC)

• Phép tính quan hệ miền (Domain

relational calculus – DRC)

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

 Các query trong TRC đều có dạng:

{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

Target

 T(A) oper S(B) với oper là toán tử so sánh

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

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

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.

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 “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

 X 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

• 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

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’))}

Ví dụ 2

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

TEACHING (P.Id= T.ProfId AND

T.CrsCode = ‘MGT123’)}

SELECT P.Name

FROM PROFESSOR P, TEACHING T

WHERE P.Id= T.ProfId AND T.CrsCode =

‘MGT123’

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ỳ

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)( ))

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”

Một số lưu ý khi dùng lượng từ

begin/end, dùng để xác định phạm vi của biến

 Ví 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)))

Dùng view trong TRC

 Liệ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ư CS

 Cá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 :

CSPROF = {P.ProfId| PROFESSOR(P) AND P.DeptId = ‘CS’}

{R.StudId | P  CSPROF (T1  TEACHING (TRANSCRIPT(R) AND P.ProfId = T1.ProfId AND T1.CrsCode = R.CrsCode AND T1.Semester = R.Semester))}

Truy vấn SQL và truy vấn TRC

 Mộ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 SQL

 Biể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.

Truy vấn SQL và truy vấn TRC

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ơn

định nghĩa bằng tiếng Anh?

So sánh giữa SQL và TRC

 Có 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??

Dịch SQL thành TRC

 Xét 1 mẫu SQL phức như sau:

SELECT R1.A, R2.C

FROM REL1 R1, REL2 R2

WHERE Condition1(R1, R2) AND

R1.B AND (SELECT R3.E

FROM REL3 R3, REL4 R4WHERE Condition2(R2, R3, R4))

Biến R3, R4 là cục bộ của subquery và R1, R2 là biến toàn cục

Dịch SQL thành TRC

toàn cục R2

không phải là dạng mà TRC hiểu

Dịch SQL thành TRC

{R1.A, R2.C| REL1(R1) AND REL2(R2)

AND R.D = R2.D) }

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

là DRC sử dụng biến miền (Domain

variable) thay cho biến bộ (Tuple

variable)

Domain variable

 Biến miền sẽ nhận giá trị từ miền giá trị (domain) của 1 thuộc tính nào đó.

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.

{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ền Target

DRC và TRC

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ư TRC

• Cá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)

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

kiện cơ bản) của DRC QUERY:

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

Điều kiện phức

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à 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 query

Lượ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

DRC query

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 đúng

DRC query

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ộ

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)

Mối quan hệ giữa đại số quan hệ,

phép tính quan hệ TRC, DRC

đạ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

Tương đương của 3 ngôn ngữ