Ràng buộc toàn vẹn các loại

Bây giờ chúng ta biểu diễn cấu trúc CSDL dưới dạng đồ thị như sau: Mỗi nút của đồ thị biểu diễn một quan hệ hoặc một thuộc tính.

(i) Quan hệ được biểu diễn bằng nút tròn trắng (o), và

(ii) Thuộc tính được biểu diễn bởi một nút tròn đen nhỏ hơn (·).

(iii) Tất cả các nút đều được chỉ rõ bằng tên của quan hệ hoặc thuộc tính. Thuộc tính thuộc một quan hệ được biểu diễn bởi một cung nối giữa nút tròn trắng và nút tròn đen đó.

Nếu trên đồ thị chúng ta thấy xuất hiện một đường khép kín thì ta nói rằng trong lược đồ CSDL có sự hiện diện của chu trình. Sự hiện diện này làm nảy sinh một vấn đề mới: Xác định khả năng đảm bảo tính nhất quán của dữ liệu, đó là một RBTV, do sự hiện diện của chu trình.

Ví dụ 4.2.11:

Hãy xét lược đồ CSDL với các lược đồ quan hệ con: Q₁ (A, B), Q₂ (B, C), Q₃ (C, D) và Q₄ (A, C). Biểu diễn lược đồ CSDL bằng đồ thị như sau:  

Hình 4.2.1 Biểu diễn lược đồ CSDL bằng đồ thị để phát hiện chu trình

Với a Ỵ A thì qua quan hệ Q₁ ta có thể xác định được một giá trị b Ỵ B. Vẫn với giá trị a Ỵ A đó nhưng xác định qua con đường Q₄ (để có c Ỵ C) rồi qua Q₂ để có b’. b’ và b có nhất thiết phải giống nhau hay không? Một CSDL là nhất quán nếu qua các cách khác nhau chỉ xác định được 1 giá trị duy nhất của thuộc tính liên quan. Trong trường hợp này có 3 vấn đề nảy sinh: 

Hai cách xác định (hoặc 2 con đường) mang ý nghĩa hoàn toàn giống nhau.

Có một con đường phụ thuộc vào con đường kia, nghĩa là tập hợp một số thuộc tính thông qua một con đường là tập con của các thuộc tính đó thông qua con đường kia.

Hai con đường độc lập nhau thì chu trình ở đây là chu trình giả, và như vậy không có ràng buộc toàn vẹn do sự hiện diện của chu trình.

Ví dụ 4.2.12:

Giả sử các quan hệ Q1, Q2, Q3, và Q4 được dịnh nghĩa trên các thuộc tính như sau:

Q1 (Mã-nhân-viên, Mã-phòng)

Q2 (Mã-phòng, Mã-đề-án)

Q3 (Mã-đề-án, Tên-đề-án)

Q4 (Mã-đề-án, Mã-nhân-viên)

Đồ thị biểu diễn CSDL này như trong hình  4.2.2:

Giả thiết 1: Với tân từ sau:

Mỗi nhân viên (thể hiện qua Mã-nhân-viên) được phân công vào tất cả các đề án do phòng đó (thể hiện qua Mã-phòng) phụ trách.

Hình 4.2.2. Lược đồ CSDL được biểu diễn dưới dạng đồ thị

(i) Hai con đường mang ý nghĩa hoàn toàn giống nhau. Đường dài hơn Q1 kết nối với Q2 (ký hiệu là Q1  I><I  Q2) trùng với con đường ngắn hơn Q4 khi cùng xác định một đề án (thể hiện qua Mã-đề-án) mà một nhân viên (thể hiện qua Mã-nhân-viên) tham gia vào. Đây là một chu trình giả, có thể hủy bỏ (bằng cách loại bỏ quan hệ Q4).

(ii) Nếu vẫn muốn giữ lại quan hệ Q4, tức là không hủy bỏ chu trình, thì phải có một RBTV với thuật toán sau:

Q1 I><I Q2 [Mã-nhân-viên, Mã-đề-án] = Q4 [Mã-nhân-viên, Mã-đề-án]

Giả thiết 2: Với tân từ sau:

Mỗi nhân viên (thể hiện qua Mã-nhân-viên) được phân công vào một số đề án do phòng đó (thể hiện qua Mã-phòng) phụ trách.

Con đường ngắn Q4 phụ thuộc vào con đường dài Q1 I><I Q2, bởi vì một nhân viên có thể không tham gia vào tất cả các đề án do phòng mình phụ trách. Chu trình trên mang ý nghĩa thực sự. Ràng buộc toàn vẹn được thể hiện bởi thuật toán sau:

Q4 [Mã-nhân-viên, Mã-đề-án] Í Q1 I><I Q2 [Mã-nhân-viên, Mã-đề-án]

Giả thiết 3: Với tân từ sau:

Mỗi nhân viên (thể hiện qua Mã-nhân-viên) được phân công vào những đề án (thể hiệnqua Mã-phòng) bất kỳ.

Hai con đường hoàn toàn độc lập nhau, không liên quan gì tới nhau, mang ý nghĩa hoàn toàn khác nhau, do đó không có RBTV.

Trong Chương III, mục 3.1, điểm 3.1.7, bài 4 đã trình bày khái niệm cơ bản vềphụ thuộc hàm (Functional Dependency) trong một quan hệ. Phụ thuộc hàm có tầm quan trọng rất lớn trong việc phân tích và thiết kế mô hình dữ liệu. Mục này sẽ trình bày kỹ hơn về vấn đề này.

Khái niệm: Quan hệ R được định nghĩa trên tập thuộc tính U = { A₁, A₂, ..., A_n}. A, BÌ U là 2 tập con của tập thuộc tính U. Nếu tồn tại một ánh xạ f: A ® B thì ta nói rằng A xác định hàm B, hay B phụ thuộc hàm vào A, và ký hiệu là A ® B. 

Định nghĩa hình thức của phụ thuộc hàm như sau:

Quan hệ Q (A, B, C) có phụ thuộc hàm A xác định B (ký hiệu là A ® B) nếu:

" q, q’ Ỵ Q, sao cho q.A = q’.A thì q.B = q’.B

(Nghĩa là: ứng với 1 giá trị của A thì có một giá trị duy nhất của B)

A là vế trái của phụ thuộc hàm, B là vế phải của phụ thuộc hàm.

A ® B được gọi là phụ thuộc hàm hiển nhiên nếu B Í A. Nghĩa là, một tập A lớn hơn và bao tập con B thì A xác định được giá trị của các thuộc tính trong tập B là điều hiển nhiên.

A ® B được gọi là phụ thuộc hàm nguyên tố, hoặc nói cách khác, B được gọi là phụ thuộc hàm đầy đủ (fully functional dependence) vào A nếu "A’ A đều không có A’ ® B.

Ví dụ 4.3.1 :

 

Trong lược đồ CSDL quản lý hóa đơn bán hàng đã cho trong ví dụ 4.1.2 và 4.2.10, quan hệ HÓAĐƠN (Số-hóa-đơn, Số_chủng_loại_mặt_hàng, Tổng-trị-giá) có các phụ thuộc hàm sau:

f1: Số-hóa-đơn ® Số_chủng_loại_mặt_hàng;

f2: Số-hóa-đơn ® Tổng-trị-giá;

bởi vì Số-hóa-đơn là khóa của lược đồ quan hệ HÓAĐƠN. Nếu biết số hóa đơn thì ta có thể xác định được tất cả các thông tin còn lại liên quan đến hóa đơn đó, trong đó có thông tin về Số_chủng_loại_mặt_hàng và Tổng-trị-giá tất cả các mặt hàng của hóa đơn. Các phụ thuộc hàm trên đều là nguyên tố.

Quan hệ CHITIẾT_HĐ (Số-hóa-đơn, Mã-hàng, Số-lượng-đặt, Đơn-giá, Trị-giá) có các phụ thuộc hàm sau:

f1: Số-hóa-đơn, Mã-hàng ® Số-lượng-đặt.

f2: Số-hóa-đơn, Mã-hàng ® Đơn-giá.

f3: Số-hóa-đơn, Mã-hàng ® Trị-giá.

f4: Số-lượng-đạt, Đơn-giá ® Trị-giá.

Thuộc tính Đơn-giá phụ thuộc hàm không đầy đủ vào khóa (Số-hóa-đơn, Mã-hàng), bởi vì nó chỉ phụ thuộc vào mặt hàng (thông qua Mã-hàng).

Qua ví dụ vừa nêu chúng ta thấy, trên một lược đồ quan hệ có thể tồn tại nhiều phụ thuộc hàm. Tập các phụ thuộc hàm thường được ký hiệu bằng chữ F.

Gọi F  là tập các phụ thuộc hàm đối với lược đồ quan hệ R định nghĩa trên tập thuộc tính U và X ® Y là một phụ thuộc hàm; X,Y Í U. Ta nói rằng X ® Y được suy diễn lôgic từ F nếu R thỏa các phụ thuộc hàm của F  thì cũng thỏa X ® Y và ký hiệu là:

    F ½= X ® Y.

 

Ví dụ 4.3.2:

Với F = { X ® Y, X ® Z, Y ® T }

Thì ta có các phụ thuộc hàm X ® YZ  và X ® T.

Gọi F⁺ là bao đóng (Closure) của F , tức là tập các phụ thuộc hàm được suy diễn lôgic từ F. Nếu F = F⁺ thì ta nói F là họ đầy đủ (full family) của các phụ thuộc hàm.

Bài toán thành viên (MemberShip) nêu vấn đề phụ thuộc hàm X ® Y có phải là được suy diễn lôgíc từ F hay không (tức là X ® Y Ỵ F ⁺ ? ) là một bài toán khó giải. Nó đòi hỏi chúng ta phải có một hệ luật dẫn để suy diễn lôgic các phụ thuộc hàm.

Năm 1974, Amstrong đã đưa ra hệ tiên đề (còn gọi là hệ luật dẫn Amstrong, hay các tính chất của phụ thuộc hàm) (D.Maier - 1983 [2]) như sau:

X, Y, Z, W Í U. Phụ thuộc hàm có các tính chất sau đây:

(i) Tính phản xạ:

Nếu Y Í X thì X ® Y.

X ® Y thì X Z ® YZ.

(iii) Tính bắc cầu:

Nếu X ® Y và Y ® Z thì X ® Z.

Và người ta đã chứng minh rằng hệ tiên đề Amstrong là đúng đắn và đầy đủ thông qua 3 bổ đề (ở đây không chứng minh):

Bổ đề 1: Hệ tiên đề Amstrong là đúng, nghĩa là, với F là tập phụ thuộc hàm đúng trên quan hệ R, nếu X ® Y là một phụ thuộc hàm

Bổ đề 2: Từ hệ tiên đề Amstrong suy ra một số luật bổ sung sau đây:

(iv) Tính phân rã (hoặc luật tách):

Nếu X ® YZ thì X ® Y và X ® Z.

(v) Tính hợp (hoặc luật hợp):

Nếu X ® Y và X ® Z thì X ® YZ.

(vi) Tính tựa bắc cầu, hoặc bắc cầu giả:

Nếu X ® Y và YZ ® W thì XZ ® W.

Định nghĩa: Bao đóng (Closure) của tập các thuộc tính X đối với tập các phụ thuộc hàm F (ký hiệu là X_F⁺) là tập tất cả các thuộc tính A có thể suy dẫn từ X nhờ tập bao đóng của các phụ thuộc hàm F⁺:

X⁺_F = { A ½ X ® A Ỵ F⁺ }

Và

 Bổ đề 3: X ® Y được suy diễn lôgic từ F nhờ hệ tiên đề Amstrong khi và chỉ khi Y Ỵ X+F.

Định lý: Hệ tiên đề Amstrong là đúng và đầy đủ.

Đây là nền tảng để chứng minh các lý thuyết CSDL quan hệ, đặc biệt là trong “bài toán thành viên” - kiểm tra xem một phụ thuộc hàm f : X ® Y có thuộc bao đóng của tập F hay không? ...

Ví dụ 4.3.3:

Cho lược đồ quan hệ R (A,B,C,D,E,G,H) và tập các phụ thuộc hàm F = {AB®C, B®D, CD®E, CE®GH, G®A }. Áp dụng hệ tiên đề Amstrong, tìm một chuỗi suy diễn AB®E.

Giải:

1. AB®C (cho trước - phụ thuộc hàm f₁)

2. AB®AB (tính chất phản xạ)

3. AB®B (luật tách)

4. B®D (cho trước - phụ thuộc hàm f₂)

5. AB®D (bắc cầu 3 & 4)

6. AB®CD (hợp 1 & 5)

7. CD®E (cho trước - phụ thuộc hàm f₃)

8. AB®E (bắc cầu 6 & 7). Kết thúc. 

Ví dụ 4.3.4:

Cho lược đồ quan hệ R (A,B,C,D,E,G,H,I,J) và tập các phụ thuộc hàm F = {AB®E, AG®J, BE®I, E®G, GI®H }. Tìm chuỗi suy diễn AB®GH (Bài tập mẫu của David Maier tr. 51)

Giải:

1. AB®E (cho trước - phụ thuộc hàm f₁)

2. AB®AB (phản xạ)

3. AB®B (luật tách)

4. AB®BE (hợp của 1 & 3)

5. BE®I (cho trước - phụ thuộc hàm f₃)

6. AB®I (bắc cầu 4 & 5)

7. E®G (cho trước - phụ thuộc hàm f₄)

8. AB®G (bắc cầu 1 & 7)

9. AB®GI (hợp 6 & 8)

10. GI®H (cho trước - phụ thuộc hàm f₅)

11. AB®H (bắc cầu 9 & 10)

12. AB®GH (hợp 8 & 11)

Thuật toán tìm bao đóng của X dựa trên tập phụ thuộc hàm F đối với quan hệ R được mô tả bằng ngôn ngữ tựa Pascal như sau (Xem D.Maier - 1983 tr.64-69 [4]):

Procedure Closure (X, F)

Begin

OldDep := Ỉ NewDep := X;

While NewDep <> OldDep Do

Begin

OldDep= NewDep;

For  every  FD: W®Z Ỵ F Do

If W Í NewDep Then NewDep := NewDep Z;

End;

Return NewDep;

End;

Ứng dụng để giải bài toán tìm khóa của quan hệ:

Định nghĩa 3.1.6.2 trong Chương III, mục 3.1 về khóa được viết lại bằng phụ thuộc hàm như sau:

R là lược đồ quan hệ định nghĩa trên tập các thuộc tính U = { A₁, A₂, ... , A_n }, với tập các phụ thuộc hàm F = { f₁, f₂, ..., f_m } xác định trên R. K Í U là khóa của R nếu thỏa mãn hai điều kiện sau đây:

(i) K ® U.

(ii)$ K’ Ì K mà K’ ®  U.

Bây giờ chúng ta hãy biểu diễn lược đồ quan hệ R (U) bằng đồ thị có hướng như sau:

-Mỗi nút của đồ thị là tên một thuộc tính của R.

-Cung nối 2 thuộc tính A và B thể hiện phụ thuộc hàm A® B

-Thuộc tính mà chỉ có các mũi tên đi ra (tức là chỉ nằm trong vế trái của các phụ thuộc hàm) được gọi là nút gốc.

-Thuộc tính mà tới nó chỉ có các cung đi tới (tức là chỉ nằm trong vế phải của các phụ thuộc hàm) được gọi là nút lá. 

Như vậy khóa của lược đồ quan hệ phải bao phủ tập các nút gốc, đồng thời không chứa bất kỳ nút lá nào của đồ thị.

Xuất phát từ tập các nút gốc (X), dựa trên tập các phụ thuộc hàm F, chúng ta tìm bao đóng X_F⁺ . Nếu X_F⁺ = U thì X là khoá, ngược lại thì bổ sung một thuộc tính không thuộc nút lá vào X rồi tìm bao đóng. Cứ như thế cho đến khi tìm được bao đóng của X bằng U.

Ví dụ 4.3.5 :

Cho R (A, B, C, D, E, H) vơi F = { AB®C, CD®E, EC®A, CD®H,  H®B }. Hãy tìm khóa của R. 

Trong đồ thị trên chúng ta thấy chỉ có nút D là nút gốc, các nút còn lại đều không phải nút lá. Khóa của R phải chứa thuộc tính D.

^D_F^{+ = Ỉ, bởi vì không tìm thấy phụ thuộc hàm nào có vế trái chỉ có một mình D.}

Vì CD có mặt trong vế trái của 2 phụ thuộc hàm do đó ghép thêm C vào tập các nút gốc để xét khóa.  

Như vậy CD®{C,D,E,H,B,A } do đó CD là khóa của R.

Ví dụ 4.3.6:

Cho quan hệ GIẢNG-DẠY (MS_CBGD, MS_MH, T_CBGD, HH_CBGD, ML, TSSV) với tập phụ thuộc hàm:

F = {MS_CBGD ® T_CBGD;

MS_MH ® HH_CBGD, ML;

HH_CBGD ® ML;

MS_CBGD ® HH_CBGD;

MS_CBGD, MS_MH ® TSSV

}

Ở đây MS_CBGD là mã số cán bộ giảng dạy; MS_MH là mã số môn học; T_CBGD là tên cán bộ giảng dạy; HH_CBGD là học hàm của cán bộ giảng dạy; ML là mã số lớp học; và TSSV là tổng số sinh viên theo học môn MS_MH do giảng viên MS_CBGD phụ trách.

Bài toán: Xác định khóa của quan hệ GIẢNG-DẠY.

(TS. Đồng thị Bích Thủy, đề thi năm 1992).

Lời giải: Để cho đơn giản, chúng ta hãy ký hiệu tên các thuộc tính của quan hệ trên lần lượt là A, B, C, D, E, G tương ứng. Khi đó quan hệ GIẢNG-DẠY và tập phụ thuộc hàm F được viết ngắn gọn lại là:

R (A, B, C, D, E, G)

F = { A®C; B®D,E; D®E; A®ED; AB®G }

Đồ thị biểu diễn các phụ thuộc hàm như sau:

Chúng ta nhận thấy trên đồ thị, hai thuộc tính A và B là các nút gốc. E, C và G là các nút lá. Khóa của quan hệ phải chứa các thuộc tính ở các nút gốc.

Xét X = { A }

X_F⁺  = { A, C, D, E }  // Còn thiếu thuộc tính B và G

Xét X = { B }

X_F⁺= { D, E }  // Còn thiếu thuộc tính A,B,C và G  

Lấy X = { A,B }

Vậy AB là khóa của R. Tức là, khóa của quan hệ giảng-dạy là { MS_CBGD, MS_MH }

Phụ thuộc hàm cùng với các loại phụ thuộc đa trị (Multivalued Dependency) và phụ thuộc kết (Join Dependency) là những khái niệm rất quan trọng trong lý thuyết, phân tích và thiết kế CSDL.