Cho l−ợc đồ quan hệ R xác định trên tập thuộc tính U, F là tập các phụ thuộc hàm, Z→ Y∈ F. Nói rằng phụ thuộc hàm Z → Y có vế trái d− thừa (phụ thuộc không đầy đủ) nếu có một A∈Z sao cho:
F ≈ F- {Z → Y} ∪ {(Z - A) → Y}.
Ng−ợc lại Z → Y là phụ thuộc hàm có vế trái không d− thừa hay Y phụ thuộc hàm đầy đủ vào Z hay Z → Y là phụ thuộc hàm đầy đủ.
Chú ý: phụ thuộc hàm có vế trái chứa một thuộc tính là phụ thuộc hàm đầy đủ.
Ví dụ 1.13: Cho tập phụ thuộc hàm F = {A → BC, B → C, AB → D} thì phụ
thuộc hàm AB→D có vế trái d− thừa B vì: F ≈ F – {AB → D}∪{A → D}.
≈ {A → BC, B → C, A → D}.
Ta nói F là tập phụ thuộc hàm có vế trái không d− thừa nếu F không chứa phụ thuộc hàm có vế trái d− thừa.
Thuật toán 1.5 (loại khỏi F các phụ thuộc hàm có vế trái d− thừa)
Vào: Tập phụ thuộc hàm F, l−ợc đồ quan hệ R xác định trên U. Ra: Tập F không chứa các phụ thuộc hàm có vế trái d− thừa. Ph−ơng pháp:
B−ớc 1: Lần l−ợt thực hiện b−ớc 2 cho các phụ thuộc hàm X→Y của F. B−ớc 2: Với mọi tập con thật sự X’≠∅ của X.
Nếu X'→Y∈ F+ thì thay X→Y trong F bằng X'→Y và thực hiện lại b−ớc 2.
Ví dụ 1.14: Cho F = {A → BC, B → C, AB → D}. Phụ thuộc hàm AB→D có
A+=ABCD ⇒ A→D∈F+, nên trong F ta thay AB→D bằng A→D ⇒ F ≈ {A → BC, B → C, A → D}
1.7.2. Tập phụ thuộc hàm có vế phải một thuộc tính
Mỗi tập phụ thuộc hàm F đều t−ơng đ−ơng với một tập phụ thuộc hàm G mà vế phải của các phụ thuộc hàm trong G chỉ gồm một thuộc tính.
Ví dụ 1.15: Cho F = {A → BC, B → C, AB → D} ta suy ra
F ≈ {A → B, A → C , B → C, AB → D} = G. G đ−ợc gọi là tập phụ thuộc hàm có vế phải một thuộc tính.
1.7.3. Tập phụ thuộc hàm không d− thừa
Nói rằng F là tập phụ thuộc hàm không d− thừa nếu không tồn tại F’⊂ F sao cho F’≈ F. Ng−ợc lại F là tập phụ thuộc hàm d− thừa.
Ví dụ 1.16: Cho F = {A→BC, B→D, AB→D} thì F d− thừa vì
Thuật toán 1.6 (loại khỏi F các phụ thuộc hàm d− thừa)
Vào: Tập phụ thuộc hàm F, l−ợc đồ quan hệ R xác định trên U. Ra: Tập F không chứa các phụ thuộc hàm d− thừa.
Ph−ơng pháp:
B−ớc 1: Lần l−ợt xét các phụ thuộc hàm X → Y của F.
B−ớc 2: Nếu X → Y là thành viên của F - {X → Y} thì loại X → Y khỏi F. B−ớc 3: Thực hiện b−ớc 2 cho các phụ thuộc hàm tiếp theo của F.
1.7.4. Tập phụ thuộc hàm tối thiểu (phủ tối thiểu của tập phụ thuộc hàm)
F đ−ợc gọi là một tập phụ thuộc hàm tối thiểu (hay phủ tối thiểu) nếu F thỏa đồng thời ba điều kiện sau:
• F là tập phụ thuộc hàm có vế trái không d− thừa.
• F là tập phụ thuộc hàm có vế phải gồm một thuộc tính. • F là tập phụ thuộc hàm không d− thừa.
Thuật toán 1.7 (tìm phủ tối thiểu của một tập phụ thuộc hàm)
Vào: Tập phụ thuộc hàm F , l−ợc đồ quan hệ R xác định trên U. Ra: Phủ tối thiểu của F.
Ph−ơng pháp:
B−ớc 1: Loại khỏi F các phụ thuộc hàm có vế trái d− thừa.
B−ớc 2: Tách các phụ thuộc hàm có vế phải trên một thuộc tính thành các phụ thuộc hàm có vế phải gồm một thuộc tính.
B−ớc 3: Loại khỏi F các phụ thuộc hàm d− thừa.
Chú ý: Theo thuật toán trên, từ một tập phụ thuộc hàm F luôn tìm đ−ợc ít nhất một phủ tối thiểu Ftt để F≈Ftt và nếu thứ tự loại các phụ thuộc hàm trong tập F là khác nhau thì có thể sẽ thu đ−ợc những phủ tối thiểu khác nhau.
1.8. Các dạng chuẩn của l−ợc đồ quan hệ
Chuẩn hoá l−ợc đồ quan hệ làm cho mối quan hệ giữa các tập thuộc tính đơn giản hơn, loại bỏ đ−ợc sự d− thừa dữ liệu và các dị th−ờng cập nhật.
Định nghĩa 1.12 (dạng chuẩn 1, ký hiệu là 1NF)
Một l−ợc đồ quan hệ R đ−ợc gọi là ở dạng chuẩn 1 nếu và chỉ nếu toàn bộ các miền giá trị của các thuộc tính trong R đều chỉ chứa các giá trị nguyên tố.
Định nghĩa 1.13
Phụ thuộc đầy đủ và phụ thuộc bộ phận.
Cho quan hệ r (U); X, Y ⊆ U:
• Nói rằng Y phụ thuộc đầy đủ vào X nếu:
- X → Y hay phụ thuộc hàm X xác định Y. - Không tồn tại X’ ⊂ X mà X’ →Y.
• Nói rằng Y phụ thuộc bộ phận vào X nếu: - X → Y.
- ∃ X’ ⊂ X mà X’ → Y.
Dạng chuẩn 2, ký hiệu là 2NF.
Một l−ợc đồ quan hệ R đ−ợc gọi là ở dạng chuẩn 2 nếu nó ở dạng chuẩn 1 và mọi thuộc tính không khoá của R đều phụ thuộc đầy đủ vào khoá.
Định nghĩa 1.14
Phụ thuộc bắc cầu.
Cho l−ợc đồ quan hệ R(U), X là tập con các thuộc tính của U, A là một thuộc tính thuộc U. A đ−ợc gọi là phụ thuộc bắc cầu vào X trên R nếu tồn tại tập con Y của R sao cho: X → Y, Y → A nh−ng Y → X với A ∉XY.
Dạng chuẩn 3, ký hiệu là 3NF.
Một l−ợc đồ quan hệ R đ−ợc gọi là ở dạng chuẩn 3 nếu nó ở dạng chuẩn 2 và mọi thuộc tính không khoá của R đều không phụ thuộc hàm bắc cầu vào khoá.
Định nghĩa 1.15 (Dạng chuẩn BC: Boye-Codd Normal Form)
Một l−ợc đồ quan hệ R đ−ợc gọi là ở dạng chuẩn Boye-Codd nếu mọi phụ thuộc hàm X→A thoả mãn trên R và với A∉X thì X là siêu khóa của R.
1.9. Phụ thuộc đa trị
Ta thấy rằng giữa dữ liệu có mối quan hệ với nhau và đó là phụ thuộc hàm, nh−ng đó không phải là duy nhất. Trong thực tế còn nhiều loại phụ thuộc nữa. Chẳng hạn: mỗi cặp vợ chồng (tên cha, tên mẹ) không phải là xác định duy nhất tên một đứa con mà là một hoặc một số con. Mối quan hệ này trong cơ sở dữ liệu quan hệ gọi là phụ thuộc đa trị [1], [15], [16].
1.9.1. Định nghĩa phụ thuộc đa trị
Cho l−ợc đồ quan hệ R(U) với U = {A1, A2, …, An} là tập các thuộc tính. Cho X, Y ⊆ U. Ta nói rằng X xác định đa trị Y hay Y phụ thuộc đa trị vào X và kí hiệu X Y nếu với mọi quan hệ xác định trên R(U) và với hai bộ t
→→
1, t2 bất kỳ mà t1(X) = t2(X) thì tồn tại bộ t3 sao cho:
t3(X) = t1(X), t3(Y) = t1(Y) và t3(Z) = t2(Z) với Z = U \ XY.
Do tính đối xứng của t1, t2 dễ dàng thấy rằng trong r còn tồn tại bộ t4 sao cho: t4(X) = t2(X), t4(Y) = t2(Y) và t4(Z) = t1(Z) với Z = U \ XY.
Tập tất cả các phụ thuộc đa trị trên l−ợc đồ quan hệ ta kí hiệu là MVD (MultiValued Dependencies).
• Khái niệm phụ thuộc đa trị cũng mô tả ràng buộc (phụ thuộc dữ liệu) giữa tập các thuộc tính. Ng−ời ta sử dụng các phụ thuộc đa trị để chuẩn hoá các l−ợc đồ quan hệ về dạng chuẩn 4.
Ví dụ 1.17: Cho quan hệ r(A, B, C, D, E) nh− sau:
r (A B C D E G) 101 J M 2 K B t1 101 J W 3 K B t4 101 J F 2 K B 101 J M 2 Z C t3 101 J W 3 Z C t2 101 J F 2 Z C
Trong quan hệ trên có A →→ CD. Thật vậy với:
t1= (101, J, M, 2, K, B) ∈r ; t2= (101, J, W, 3, Z, C) ∈r tồn tại 2 bộ: t3= (101, J, M, 2, Z, C) ∈r và t4= (101, J, W, 3, K, B) ∈r.
Theo định nghĩa ta thấy ngay A →/→ C và A →/→ D.
Từ định nghĩa trên ta suy ra rằng nếu X → Y thoả trên quan hệ r thì X→→Y cũng thoả trên r. Do vậy mỗi phụ thuộc hàm đều là phụ thuộc đa trị.
Dạng chuẩn 4, ký hiệu là 4NF.
Cho l−ợc đồ quan hệ R, D là tập các phụ thuộc có thể áp dụng trên R. Ta nói R ở dạng chuẩn 4 nếu có một phụ thuộc đa trị X Y với Y ≠ ỉ, Y không là tập con của X và XY không chứa tất cả các thuộc tính của R thì X chứa một khoá của R.
→→
1.9.2. Các tính chất của phụ thuộc đa trị.
Cho l−ợc đồ quan hệ R(U) với U= {A1, A2, …, An} là tập các thuộc tính và X, Y, Z, W U. ⊆
Tính chất 1:
X→→Y khi và chỉ khi X→→Z với X ∪Y ∪ Z = U.
Tính chất 2: Nếu X→→Y và V ⊆ W thì WX→→ VY. Tính chất 3: Nếu X→→Y và Y→→Z thì X→→Z \ Y. Tính chất 4 Nếu X → Y thì X→→Y. Tính chất 5 Nếu X→→Y và W → Z với Z Y và W⊆ ∩ Y = ∅ thì X → Z.
Các luật suy dẫn đ−ợc đối với phụ thuộc đa trị:
Tính chất 6:
Tính chất 7: Nếu X→→Y và WY→→Z thì WX→→Z \ WY. Tính chất 8: Nếu X→→Y và XY→Z thì X→Z \ Y. Tính chất 9: Nếu X→→Y và X→→Z thì X→→ Y∩Z, X→→ Y \ Z, X→→ Z \ Y. 1.10. Kết luận ch−ơng 1
Ch−ơng này đã trình bày một số các khái niệm cơ bản nhất trong mô hình dữ liệu quan hệ. Trình bày các phép toán cơ bản, các khái niệm về phụ thuộc hàm, phụ thuộc đa trị, khoá, bao đóng và phủ của tập phụ thuộc hàm cùng với các tính chất của chúng. Ngoài ra các thuật toán tìm khoá, bao đóng, phủ tối thiểu của tập phụ thuộc hàm cũng đ−ợc trình bày.
Mô hình dữ liệu quan hệ có tính độc lập dữ liệu cao, dễ dàng sử dụng và còn cho phép dễ dàng mô phỏng các hệ thống thông tin đa dạng trong thực tiễn.
Trong mô hình này, cơ sở dữ liệu đ−ợc xem nh− là một tập hợp các quan hệ, mỗi quan hệ có thể đ−ợc hình dung một cách trực quan nh− là một bảng chữ nhật gồm có các hàng và các cột. ở bảng này mỗi cột ứng với một thuộc tính, mỗi hàng đ−ợc gọi là một bộ. Do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này sẽ rất khó khăn khi biểu diễn các dữ liệu có tính chất động (phi tuyến).
cHƯƠNG 2: MÔ HìNH CƠ Sở Dữ LIệU DạNG KHốI
Để mở rộng mô hình quan hệ, ch−ơng này đ−a ra một mô hình cơ sở dữ liệu khác gọi là mô hình cơ sở dữ liệu dạng khối đ−ợc xây dựng và mô tả trong [3], [4], [5], [6], [13]. Mô hình này phản ánh đ−ợc các dữ liệu ở dạng động, giúp biểu diễn thế giới thực trong quá trình vận động một cách tự nhiên hơn. ý nghĩa của các khái niệm phụ thuộc dữ liệu, khoá, các dạng chuẩn nh−
ở mô hình dữ liệu quan hệ.
2.1. Khối, l−ợc đồ khối
Khái niệm toán học làm nền tảng cho mô hình cơ sở dữ liệu dạng khối (gọi tắt là mô hình khối) là các khối hiểu theo nghĩa của lý thuyết tập hợp.
Định nghĩa 2.1 [3], [4]
Gọi R = (id; A1, A2, ..., An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1,n) là các thuộc tính. Mỗi thuộc tính Ai (i=1,n) có miền giá trị t−ơng ứng là dom(Ai ). Một khối trên R, kí hiệu
r(R), là tập hữu hạn các phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai , (i=1,n). Nói một cách khác: t ∈ r(R) ⇔ t = {ti : id → dom(Ai)} i =1,n .
Kí hiệu khối là r(R) hoặc đơn giản là r.
Cho R = (id; A1, A2, ..., An) và r(R) là một khối trên R, khi đó R đ−ợc gọi là l−ợc đồ của khối r(R). Nh− vậy trên cùng một l−ợc đồ khối R có thể xây dựng đ−ợc nhiều khối khác nhau.
Ví dụ 2.1: Xây dựng khối nhân viên (ký hiệu NV(R)) (hình 2.1) để quản lý
nhân viên một cơ quan: cho l−ợc đồ khối R = (id; A1, A2, A3, A4), trong đó: id = {1/2009, 2/2009, 3/2009, ..., 12/2009} và các thuộc tính là A1 = ma (mã), A2 = ten (tên), A3 = luong (l−ơng), A4 = trinh_do (trình độ).
Với khối NV(R) ở hình 2.1 thì nó gồm 3 phần tử: t1, t2, t3.
ma ten luong trinh_do
A01 A 500 TS A01 A 350 ThS t1 A01 A 200 DH B02 B 350 DH A02 B 300 DH t2 A02 B 250 DH C01 C 300 DH 3/2009 A03 C 250 CD 2/2009 t3 A03 C 200 CD 1/2009
Hình 2.1: Biểu diễn khối nhân viên NV(R). • L−ơng của nhân viên t1 ở thời điểm tháng 1/2009 là:
t1(1/2009, luong) = 200.
• Tên của cán bộ t2 vào tháng 2/2009 là: t2(2/2009, ten) = 'B'. • Trình độ của cán bộ t3 vào tháng 2/2009 là:
t3(2/2009, trinh_do) = ‘CD’.
Mã số của cán bộ t3 vào tháng 3/2009 là: t3(3/2009, ma) = 'C01'.
2.2. Lát cắt
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r(R) là một khối trên R. Với mỗi x∈ id ta kí hiệu r(Rx) là một khối với Rx = ({x}; A1, A2, ..., An) sao cho:
tx ∈ r(Rx) ⇔ tx = { tix = ti }i =1,n với t ∈ r(R)
x và t = {ti : id → dom(Ai)}i =1,n. ở đây ti
x(x) = ti(x) với i=1,n.
Khi đó r(Rx) đ−ợc gọi là một lát cắt trên khối r(R) tại điểm x.
Ví dụ 2.2: Với khối NV(R) đã cho ở trên, R = (id; A1, A2, A3, A4)
trong đó: id = {1/2009, 2/2009, 3/2009, ..., 12/2009} A1 = ma, A2 = ten, A3 = luong, A4 = trinh_do.
r(R2/2009): ma ten luong trinh_do
A01 A 350 ThS
A02 B 300 DH
A03 C 250 CD
Nhận xét 2.1
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r(R) là một khối trên R. Với mỗi x∈ id thì lát cắt r(Rx) là một quan hệ. Trong tr−ờng hợp tập chỉ số id chỉ gồm một phần tử thì r(R) trở thành một quan hệ.
Nh− vậy mỗi quan hệ r(A1, A2, ..., An) là một tr−ờng hợp đặc biệt của khối, đó chính là khối r(R) với R = ({x}; A1, A2, ..., An).
Mệnh đề 2.1 [3], [4]
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r(R) là một khối trên R, khi đó tồn tại một họ quan hệ (hiểu theo nghĩa tập hợp) duy nhất biểu diễn họ {r(Rx)}x∈id các lát cắt của khối r(R). Ng−ợc lại không đúng, nghĩa là với một họ quan hệ cho tr−ớc biểu diễn họ các lát cắt của một khối nào đó thì khối tìm đ−ợc không duy nhất.
2.3. Khóa của khối
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r là một khối trên R. Với mỗi x ∈ id, t ∈ r(R), t = (t1, t2, ..., tn), kí hiệu t(x; Ai), (i = 1 .. n) là giá trị của phần tử t ở thuộc tính Ai tại chỉ số x.
Để đơn giản việc trình bày, đặt x(i) = (x; Ai) với x ∈ id và nh− vậy: t(x(i)) = t( x; Ai) = ti (x), (i = 1 .. n). Từ đó, kí hiệu:
id(i) = {x(i)|x∈id}, nh− vậy id(i) = {(x; Ai)|x∈id}. Với X(i)⊆ id(i) thì kí hiệu: t(X(i)) = {t(y(i))| y(i)∈ X(i)}. Giả sử t1 , t2∈ r(R) với t1 = {ti1 : id → dom(Ai)} i =1.. n , t2 = {ti
2 : id → dom(Ai)} i =1.. n , khi đó định nghĩa khóa của khối r(R) nh− sau:
Định nghĩa 2.2 [5], [13]
Khóa của khối r trên l−ợc đồ khối R = (id; A1, A2, ..., An) là một tập K = {X(i1),X(i2), ..., X(ih)}, trong đó X(ik) ≠∅, X(ik) ⊆ id(ik), (k = 1 .. h) thỏa mãn hai tính chất:
a) Với mọi t1, t2 ∈ r và t1≠t2 đều tồn tại một X(ik)∈ K sao cho: - t1ik(X(ik)) ≠ t2ik(X(ik))
Nói một cách khác, không tồn tại 2 phần tử mà: - t1ik(X(ik)) = t2ik(X(ik)), ∀ k = 1 .. h.
b) Với bất kì tập K’ nào, K’ = {X(i1’), X(i2’), ..., X(ih’)} với X(ik’)⊆ X(ik), (k = 1.. h) và tồn tại X(im’) ⊂ X(im), với m ∈ {1, 2, ..., h} đều không có tính chất a) nói trên.
Nếu tập K là khóa của khối r(R) thì mọi tập
K” = {X(i1’’),X(i2’’), ..., X(ih’’)}, trong đó X(ik)⊆ X(ik’’), (∀ k = 1 .. h) đ−ợc gọi là siêu khóa của khối r.
Mệnh đề 2.2 [5], [13]
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r(R) là một khối trên R. Khi đó với x ∈ id mà ta có {x(i1), x(i2), ..., x(ik)} là khóa của lát cắt r(Rx) thì ta cũng có với mọi y ∈ id, {y(i1), y(i2), ...,y(ik)} là khóa của lát cắt r(Ry ) hay nói một cách khác {Ai1, Ai2, ..., Aik} là khóa của quan hệ r(A1, A2, ..., An).
Mệnh đề 2.3 [5], [13]
Cho l−ợc đồ khối R = (id; A1, A2, ...,An), r(R) là một khối trên R, id = {x}. Khi đó r(R) trở thành quan hệ r(A1, A2, …, An) và mỗi khóa
K = {X(i1),X(i2), ..., X(ih)}, trong đó X(ik) ⊆ id(ik), (k = 1, 2, ..., h) của khối r(R) lại trở thành khóa của quan hệ r(A1, A2, ..., An).
Mệnh đề 2.4 [5], [13]
mà {x(i1), x(i2), ..., x(ik)} là khóa của khối r(R) thì ta cũng có với mọi y ∈ id, {y(i1), y(i2), ..., y(ik)} là khóa của lát cắt r(Ry) hay nói một cách khác
{Ai1, Ai2, ..., Aik} là khóa của quan hệ r(A1, A2, ..., An).
Mệnh đề 2.5 [5], [13]
Cho l−ợc đồ khối R = (id; A1, A2, ..., An), r(R) là một khối trên R. Khi đó nếu với x ∈ id nào đó mà ta có {x(i1), x(i2), ..., x(ik)} là khóa của lát cắt r(Rx) thì {id(i1), id(i2), ..., id(ik)} là khóa của khối r(R).
2.4. Đại số quan hệ trên khối
Cho r là một khối trên l−ợc đồ khối R = (id; A1, A2, ..., An), ở đây ta giả thiết rằng r là một khối gồm một tập hữu hạn các phần tử. Cũng t−ơng tự nh− đại số quan hệ trong mô hình cơ sở dữ liệu quan hệ, ở đây các phép toán của đại số quan hệ lại đ−ợc áp dụng cho các khối; bên cạnh đó còn có thêm phép toán mới đ−ợc xây dựng đó là tích Đề-các theo tập chỉ số [6].
Đối với các phép hợp, giao và trừ thì hai khối tham gia phải là khả hợp (nghĩa là chúng có cùng một l−ợc đồ khối).
2.4.1. Phép hợp
Cho hai khối r và s khả hợp, khi đó hợp của r và s, kí hiệu là r ∪ s, là một khối gồm các phần tử thuộc khối r hoặc thuộc khối s đã cho. Ta có:
r ∪ s = {t ⎜t ∈ r hoặc t ∈ s}.
2.4.2. Phép giao
Cho hai khối r và s khả hợp, khi đó giao của r và s là một khối, kí hiệu