Bài giảng Cơ sở dữ liệu - Bài: Mô hình cơ sở dữ liệu quan hệ

xét buộc phải tồn tại trong một hay một vài thuộc tính trong lược đồ khác. 
Ràng buộc liên quan hệ, liên thuộc tính : đây là quy tắc có liên quan nhiều thuộc tính ở nhiều quan hệ với nhau. 
Ràng buộc liên quan hệ, liên bộ : đây là quy tắc có liên quan nhiều thuộc tính với nhiều bộ ở nhiều quan hệ với nhau. 
Mô hình cơ sở dữ liệu quan hệ(Ràng buộc toàn vẹn trên nhiều quan hệ) 
 ; ; ; 
RB1: một bộ trong quan hệ tồn tại được khi phải tồn tại ít nhất là 15 bộ trong quan hệ với học phần đó. 
RB2: Thuộc tính trong lược đồ phải có giá trị trong những giá trị của thuộc tính trong lược đồ 
RB3: Mỗi một sinh viên đều có một nhãn ghi năm thứ mấy (VD: sinh viên năm 3). Mỗi một lần đăng ký một học phần, thì mỗi học phần đều quy định số năm tối thiểu để được phép đăng ký. Vậy một đăng ký phải thỏa là năm thứ của sinh viên phải lớn hơn bằng năm tối thiểu của học phần 
RB4: Thuộc tính phải có giá trị bằng tổng số những đăng ký với mã học phần đó và phải lớn hơn hay bằng 15. 
Mô hình cơ sở dữ liệu quan hệ 
Chính những ràng buộc đã tạo nên mối quan hệ có nghĩa trong cơ sở dữ liệu. Trong đó ràng buộc khóa ngoại được hầu hết các Hệ quản trị cơ sở dữ liệu (HQTCSDL) thể hiện như một quan hệ chính thức (gần như phải có) giữa các quan hệ khi hiện thực một lược đồ cơ sở dữ liệu trên HQTCSDL. 
Xem xét một vài ví dụ về cơ sở dữ liệu để thấy các ràng buộc liên quan. 
PHỤ THUỘC HÀM 
Phụ thuộc hàm 
Với những ràng buộc liên thuộc tính có thể trên 1 hay nhiều quan hệ cho chúng ta thấy sự phụ thuộc lẫn nhau giữa các thuộc tính. 
Sự phụ thuộc này có thể lỏng (không có sự suy diễn lẫn nhau) hay chặt (có khả năng tính toán và suy diễn lẫn nhau). 
Lấy ví dụ: trong quan hệ sinh viên với hai thuộc tính là ngày sinh và tuổi. Giữa hai thuộc tính này có quan hệ ràng buộc chặt và tuổi được tính từ ngày sinh. 
Chính quan hệ ràng buộc chặt này tạo nên khái niệm gọi là phụ thuộc hàm . 
Phụ thuộc hàm 
Như vậy, trong thực tế có rất rất nhiều các quan hệ chặt (phụ thuộc hàm) như vậy. Tuy nhiên không phải bất kỳ phụ thuộc hàm nào cũng được đưa ra thành một quan hệ mới, mà đôi khi phải ngầm hiểu và không nên ghi những phụ thuộc thành thuộc tính trong quan hệ (trừ khi rất cần thiết) và nên cho vào những thủ tục tính toán. 
Ví dụ: cho quan hệ 
Nhìn vào quan hệ này, ta có thể nhận thấy (chủ quan) có: ngaysinh xác định tuoi (ký hiệu: ); đồng thời nhận thấy malop xác định tenlop (Vì: mỗi một lớp thì chỉ có duy nhất 1 và chỉ 1 tên, nếu mã lớp giống nhau thì chắc chắn tên lớp giống nhau ). 
Tuy nhiên, nhìn vào thể hiện của quan hệ sv đó, ta thấy sự lặp lại các giá trị giống nhau của tên lớp. Với trường hợp này ta thử làm 2 việc sau: 
Phụ thuộc hàm 
Năm hiện tại là 2015, chúng ta tác ra làm 3 quan hệ 
sv 
ma 
hoten 
malop 
tenlop 
ngaysinh 
tuoi 
S1 
Hoàng 
TO 
Toán 
1/1/1995 
20 
S2 
Nhân 
TO 
Toán 
18/1/1995 
20 
S3 
Vân 
TH 
Tinhoc 
25/6/1994 
21 
S4 
Hương 
TH 
Tinhoc 
17/9/1994 
21 
S5 
Linh 
TO 
Toan 
20/4/1993 
22 
sv 
ma 
hoten 
malop 
ngaysinh 
S1 
Hoàng 
TO 
1/1/1995 
S2 
Nhân 
TO 
18/1/1995 
S3 
Vân 
TH 
25/6/1994 
S4 
Hương 
TH 
17/9/1994 
S5 
Linh 
TO 
20/4/1993 
L 
malop 
Tenlop 
TO 
Toán 
TH 
Tinhoc 
t 
ns 
t 
1/1/1995 
20 
18/1/1995 
20 
25/6/1994 
21 
17/9/1994 
21 
20/4/1993 
22 
Phụ thuộc hàm 
Nhận thấy việc chia quan hệ ra thì quan hệ sẽ không có sự lặp lại dữ liệu, tuy nhiên quan hệ mới xuất hiện là hợp lý, nhưng quan hệ thì nhìn thấy vẫn dư thừa nhiều lắm. Thực tế ta có thể bỏ hẳn thuộc tính (vì điều này vẫn có thể tính toán ra, và giá trị của tuổi sẽ thay đổi theo thời gian). 
Như vậy quan hệ chứa nhiều dư thừa. Do nó không đạt được một số yêu cầu (gọi là dạng chuẩn). Nên tách nó ra để mỗi cái riêng đạt yêu cầu và dữ liệu không thừa và lặp lại. 
Phụ thuộc hàm(Định nghĩa – Lý thuyết) 
Cho quan hệ và . 
Ta nói thỏa phụ thuộc hàm nếu như 
Ta nói là tập tất cả các quan hệ mà quan hệ này thỏa tập phụ thuộc hàm 
Vấn đề: kiểm tra tập phụ thuộc hàm có thỏa điều kiện: mọi quan hệ có thỏa hay không ?? 
Nếu ta xét từng quan hệ r (đây là thể hiện dữ liệu thật) thì thật sự là không tưởng. Do đó cần có cách khác để xác định việc này. 
Phụ thuộc hàm(Luật dẫn - Hệ tiên đề Armstrong) 
R1: phản xạ:	 
R2: thêm: 
R3: bắc cầu: 
R4: hội: 
R5: phân rã: 
R6: bắc cầu giả: 
Hệ tiên đề ArmStrong là bộ gồm 3 luật R1,R2,R3 
Với hệ tiên đề này thì mọi luật còn lại thì được suy diễn ra 
Trong bộ 3 luật đó, không tồn tại 2 luật nào suy luật còn lại 
Phụ thuộc hàm(Luật dẫn - Hệ tiên đề Armstrong) 
R4: hội: 
CM: 	áp dụng (2) và 
	áp dụng (3) ta ghi lại là 
R5: phân rã: 
CM:	áp dụng (1) 	áp dụng (3) 
	áp dụng (1) 	áp dụng (3) 	 
R6: bắc cầu giả: 
CM:	áp dụng (2) 
	áp dụng (3) 
Phụ thuộc hàm(Bao đóng) 
Với tập phụ thuộc hàm và mọi thỏa phục thuộc hàm , ta có thể xác định được những phụ thuộc hàm khác (đó là hệ quả, là suy diễn từ ). Tập tất cả các phụ thuộc hàm hệ quả từ và tập phụ thuộc hàm được gọi là bao đóng của , ký hiệu là . 
Cho lược đồ quan hệ và , ta gọi bao đóng của 
Thuật toán: 	 Đầu vào: 	Đầu ra: 
Lặp {	 
	Lặp với mỗi luật 
	{ Nếu thì }	 
} Lặp nếu 
Trả về 
Phụ thuộc hàm(Sự dư thừa) 
Xét một lược đồ quan hệ . 
Trong đó ta có thể thấy chủ quan phụ thuộc hàm 
Nhưng thật sự phụ thuộc hàm bị dư thừa, có thể tìm thấy được chỉ từ phụ thuộc hàm . Do vậy có thể coi như một dạng dư thừa. Đây là dạng đư thừa thứ 1. 
Trường hợp khác, ta thấy phụ thuộc hàm có thể xác định được bởi áp dụng tính bắc cầu trên 2 phụ thuộc hàm và . Vì thế có thể coi là một dạng dư thừa. Đây là dạng dư thừa thứ 2. 
Lời giải ở cuối phần phủ tối tiểu. 
Phụ thuộc hàm(Phủ - Phủ tối tiểu) 
Phủ: Cho lược đồ , ta gọi tập phụ thuộc hàm là phủ của nếu như . Rỏ ràng là phủ của thì cũng là phủ của . 
Phụ thuộc hàm đầy đủ: Cho lược đồ , phụ thuộc hàm là thành viên của . Nếu mọi thuộc tính thuộc mà phụ thuộc hàm không thuộc thì là một phụ thuộc hàm đầy đủ trong lược đồ hay phụ thuộc đầy đủ vào dưới . 
Phủ tối tiểu: Cho lược đồ , tập phụ thuộc hàm gọi là phủ tối tiểu của lược đồ nếu thỏa các điều sau 
 là phủ của 
Tất cả các phụ thuộc hàm có vế phải là một thuộc tính. 
Tất cả các phụ thuộc hàm là phụ thuộc hàm đầy đủ 
Nếu ta có , thì không là tương đương với 
Phụ thuộc hàm(ví dụ: phụ thuộc hàm đầy đủ) 
Cho lược đồ 
Xét , ta làm 
Loại , xét có thuộc không. Ta thấy , do đó vậy dư thừa. 
Lúc này ta chỉ còn . Vậy vế trái còn 1 thuộc tính nên không làm tiếp. 
Kết quả là 
Ghi chú: Nếu ta xét loại trước, thì ta nhận kết quả là không loại , khi đó vẫn còn nguyên và lại xét tiếp có loại không. 
Ví dụ cho lược đồ trên: . Tập phụ thuộc hàm 
Ta thấy f2 có thuộc tính hoten là dư thừa. 
Phụ thuộc hàm(ví dụ: phụ thuộc hàm đầy đủ) 
Cho lược đồ 
Xét , ta làm 
Loại , xét có thuộc không. Ta thấy , do đó vậy dư thừa. 
Lúc này ta chỉ còn . Vậy vế trái còn 1 thuộc tính nên không làm tiếp. 
Kết quả là 
Ghi chú: Nếu ta xét loại trước, thì ta nhận kết quả là loại , khi đó thay đổi và chỉ còn lại thay cho . Do đó ta không xét tiếp. Và kết quả là 
Phụ thuộc hàm(ví dụ: phụ thuộc hàm đầy đủ) 
Cho lược đồ , 
Xét , ta làm 
Loại , xét có thuộc hay không. Ta thấy , do đó vậy không dư thừa. 
Loại , xét có thuộc hay không. Ta thấy , do đó vậy dư thừa. 
	Lúc này } 
Loại , xét có thuộc } không. Ta thấy , do đó vậy dư thừa. 
 	Lúc này } chấm dứt vì chỉ còn 1 pth. 
Ví dụ cho lược đồ trên: . Tập phụ thuộc hàm 
Ta thấy f2 có thuộc tính hoten là dư thừa. 
Phụ thuộc hàm(Thuật toán tìm phủ tối tiểu) 
Đầu vào: 	Đầu ra: 
Với mỗi phụ thuộc hàm làm 
	Với mỗi thuộc tính làm 
 Với mỗi phụ thuộc hàm ta làm { 
	đặt 
	Lặp nếu ( ) thì làm { 
	} 
} 
Với mỗi phụ thuộc hàm ta làm: Nếu thì 
Trả về 	 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ 
B1: Rã thành 
B2: KHÔNG LÀM (VÌ MỌI VẾ TRÁI CHỈ CÓ 1 THUỘC TÍNH) 
B3: Với từng phụ thuộc hàm trong 
 : Nếu bỏ thì và =ACD có , không dư 
 : Nếu bỏ thì và =B có , không dư 
 : Nếu bỏ thì và =ABCD có , dư (bỏ) 
 : Nếu bỏ thì và =ABC có , không dư 
Kết quả: 
Ví dụ cho lược đồ trên: . Tập phụ thuộc hàm 
Ta thấy f5 là dư thừa theo cách làm trên ta loại phụ thuộc hàm f5 . 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ 
B1: 
B2: Xét từng phụ thuộc hàm mà vế trái hơn 1 thuộc tính 
 : 
Loại , ta xét có trong không. Thấy vậy không dư thừa 
Loại C, ta xét có trong không. Thấy vậy do đó dư thừa. 
Vậy 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ 
B1: 
B2: Xét từng phụ thuộc hàm mà vế trái hơn 1 thuộc tính 
Loại , ta xét có trong không. Thấy vậy không dư thừa. Khi này vẫn không đổi 
Loại , ta xét có trong không. Thấy vậy dư thừa. Khi này 
Loại , ta xét có trong không. Thấy vậy không dư 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ 
B1: 
B2: Xét từng phụ thuộc hàm mà vế trái hơn 1 thuộc tính 
Loại , ta xét có trong không. Thấy vậy không dư 
Loại , ta xét có trong không. Thấy vậy dư thừa. Khi này 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ 
B1: 
B2: Xét từng phụ thuộc hàm mà vế trái hơn 1 thuộc tính 
Loại , ta xét có trong không. Thấy vậy không dư 
Loại , ta xét có trong không. Thấy vậy dư thừa. Khi này 
Vậy 
Phụ thuộc hàm(ví dụ: phủ tối tiểu) 
Cho lược đồ với 	 
B3: Xác định các phụ thuộc hàm dư thừa 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy không dư thừa. 
 : . Vậy dư thừa . 
Vậy kết quả: 
Phụ thuộc hàm(Phủ - Phủ tối tiểu) 
Như vậy làm phủ tối tiểu để ta loại bỏ đi những phụ thuộc hàm dư thừa. Điều này giúp ích rất lớn cho việc tách lược đồ thành những quan hệ con thỏa dạng chuẩn một cách nhanh và dể làm hơn. 
Xét một lược đồ quan hệ . 
Trong đó ta có thể thấy chủ quan phụ thuộc hàm 
Nếu làm theo thuật toán thì 
Ta loại thuộc tính hoten trong phụ thuộc hàm f2 . 
Ta loại tiếp phụ thuộc hàm f5 . Vì khi tập phụ thuộc hàm F đã bỏ f5 đi, ta có 
 vì trong đó với f1,f2,f3,f4 ta hoàn toàn tìm lại được phụ thuộc hàm f5 bằng cách tính bao đóng của masv, ta có 	 
Kết quả ta có 
Sau đó ta tách ra (theo thuật toán tổng hợp/phân rả) và kết quả ghi ở đây . 
DẠNG CHUẨN 
Dạng chuẩn 
Dạng chuẩn: Đó là một tập các quy ước được đặt ra trên quan hệ để giảm thiểu tối đa nguy cơ dư thừa trong việc lưu trử. 
Thuộc tính khóa: là thuộc tính tồn tại 1 trong bất kỳ khóa nào của lược đồ. 
Thuộc tính không khóa: Là thuộc tính không hề tồn tại trong bất kỳ khóa nào của lược đồ (ngược thuộc tính khóa) 
Dạng chuẩn 1 
Tính nguyên tố : Một thuộc tính được gọi là nguyên tố nếu như mọi giá trị trong miền giá trị của thuộc tính đó không phải là tập giá trị hay là giá trị phức hợp. 
Lược đồ quan hệ được gọi là đạt dạng chuẩn 1 nếu như mọi thuộc tính đều được gọi là nguyên tố. 
Lược đồ cơ sở dữ liệu được gọi là đạt dạng chuẩn 1 nếu như mọi lược đồ quan hệ trong nó đạt chuẩn 1. 
Ví dụ: Thuộc tính ngày sinh là thuộc tính có giá trị phức, là tổ hợp 3 giá trị ngày tháng năm không là nguyên tố 
Cho quan hệ khachhang(makh, sothevisa,) thuộc tính sothevisa lưu một tập các số thẻ của khác hàng đó, vậy nó là dạng tập không nguyên tố. 
Dạng chuẩn 2 
Lược đồ quan hệ đạt dạng chuẩn 2 nếu như đạt dạng chuẩn 1 và mọi thuộc tính không khóa đều phải phụ thuộc đầy đủ vào tất cả các khóa của lược đồ quan hệ. 
Lược đồ cơ sở dữ liệu đạt dạng chuẩn 2 nếu như mọi lược đồ quan hệ của D đều đạt dạng chuẩn 2 dưới . 
Ví dụ: Cho lược đồ quan hệ 
Lược đồ quan hệ này không đạt chuẩn 2, vì khóa chỉ duy nhất là , thuộc tính không khóa thì phụ thuộc đầy đủ vào khóa, thuộc tính không phụ thuộc đầy đủ vào khóa. 
Cho lược đồ cơ sở dữ liệu 
Lược đồ cơ sở dữ liệu đạt dạng chuẩn 2 vì mọi thành viên đều đạt dạng chuẩn 2 
Dạng chuẩn 3 
Thuộc tính bắc cầu : Cho tập phụ thuộc hàm , ta gọi là phụ thuộc bắc cầu vào (thông qua ) nếu như tồn tại sao cho có nhưng không suy và có và . 
Lược đồ quan hệ đạt dạng chuẩn 3 dưới nếu đạt dạng chuẩn 2 và mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào bất kỳ khóa nào của . 
Lược đồ cơ sở dữ liệu là dạt dạng chuẩ n 3 dưới nếu như mọi lược đồ quan hệ của đều đạt dạng chuẩn 3 dưới . 
Ví dụ: Cho lược đồ quan hệ 
Không đạt dạng chuẩn 3 vì: Khóa là và duy nhất, là thuộc tính không khóa lại phụ thuộc bắc cầu vào khóa thông qua . 
Ghi chú: nếu vi phạm dạng chuẩn 2 sẽ vi phạm dạng chuẩn 3; Nếu đạt dạng chuẩn 3 thì hiển nhiên đạt dạng chuẩn 2. 
Dạng chuẩn 3(Ví dụ) 
Cho lược đồ quan hệ 
Không đạt dạng chuẩn 3 vì: Khóa là và duy nhất, là thuộc tính không khóa lại phụ thuộc bắc cầu vào khóa thông qua . 
Nếu ta phân rả thành lược đồ cơ sở dữ liệu sau 
Ta nhận thấy các lược đồ quan hệ con đều đạt dạng chuẩn 3. Như vậy lược đồ cơ sở dữ liệu cũng đạt dạng chuẩn 3 
Dạng chuẩn BC (Boyce-Codd) 
Lược đồ quan hệ đạt dạng chuẩn BC dưới nếu như đạt dạng chuẩn 3 và mọi thuộc tính trong đều không phụ thuộc bắc cầu vào bất kỳ khóa nào của . 
Lược đồ cơ sở dữ liệu đạt dạng chuẩn BC dưới nếu như mọi lược đồ quan hệ trong đạt dạng chuẩn BC dưới . 
Ghi chú: dể nhận thấy là nếu tồn tại bất kỳ phụ thuộc hàm mà không chứa khóa thì khẳng định là vi phạm dạng chuẩn BC. 
Như vậy để lược đồ cơ sở dữ liệu đạt chuẩn BC, thì mọi lược đồ quan hệ con chỉ tồn tại những phụ thuộc hàm có vế trái chứa khóa. 
Nhận xét 
Những khái niệm này mang ý nghĩa để phục vụ cho việc kiểm tra hay định hình những cơ sở dữ liệu sao cho hạn chế tối đa sự dư thừa dữ liệu, dữ liệu không hợp lý. 
Hơn nữa, qua những dạng chuẩn và cách rả 1 lược đồ quan hệ ra thành lược đồ cơ sở dữ liệu để đạt dạng chuẩn ở từng lược đồ quan hệ con là một cách để xây dựng cơ sở dữ liệu theo hướng tập hợp mọi thuộc tính và các quan hệ lẫn nhau và từ đó dựng lược đồ cơ sở dữ liệu phù hợp. 
Sinh viên tự xem phương pháp phân rả (tự học) 
Phân rả 
Cho 1 lược đồ quan hệ và ta phân rả thành 
Được gọi là bảo toàn thông tin nếu tồn tại trong F pth hay trong đó 
Được gọi là bảo toàn phụ thuộc hàm nếu 
Ví dụ:
Cho R={ X Y Z} F={ X→ Y, Y→ Z} ta rả thành
R1={ X Y} F1={ X → Y}
R2={ Y Z} F2={ Y→ Z}
Chứa đủ phụ thuộc hàm trong và trong 
Phân rả 
Phương pháp:
B1: Tìm các phụ thuộc hàm vi phạm dạng chuẩn 3 rồi đến các phụ thuộc hàm vi phạm dạng chuẩn 2
 B11: Với từng phụ thuộc hàm vi phạm
 Phân rả bảo toàn thông tin và phụ thuộc hàm
 B12: Làm lại bước B1 với các lược đồ quan hệ sau 
 phân rả
 Thuật toán ngưng khi không thể phân rả được 
Phân rả 
Cho R={masv ,tensv,malop,tenlop,mamon,diem}
F={masv→tensv,malop; malop→tenlop; mamon,masv→diem}
Xác định khóa masv,mamon
Chọn malop→tenlop (Vi phạm bắc cầu) ta có
R1={malop,tenlop} F1={malop→tenlop}
R2={ masv ,tensv,malop,mamon,diem} 
F2={masv→tensv,malop; mamon,masv→diem}
Tiếp tục làm với R2 và khóa vẫn là masv,mamon
Chọn masv→tensv,malop vì không còn pth bắc cầu. Ta có:
R21={ masv ,tensv,malop} F21={masv→tensv,malop} 
R22={ masv ,mamon,diem} F22= {mamon,masv→diem} 
Chấm dứt thuật toán 
Phân rả 
Chọn masv→tensv,malop ta có kết quả không bảo toàn pth 
R1(masv,tensv,malop) {masv→tensv,malop}
R2(masv,tenlop,mamon,diem) {mamon,masv→diem}
Lưu ý: nên tìm phủ tối thiểu trước khi bắt đầu phân rả