Bài giảng Cơ sở dữ liệu: Chương 4 - Hoàng Thị Hà

CHƯƠNG 4: LÝ THUYẾT THIẾT KẾ CSDL QUAN HỆ

GV: Hoàng Thị Hà Email: htha@vnua.edu.vn

Nội dung

1. Giới thiệu 2. Phụ thuộc hàm 3. Khóa tối thiểu 4. Chuẩn hóa cơ sở dữ liệu

Hoang Thi Ha

Bài 1: Giới thiệu

I. Đặt vấn đề

Hoang Thi Ha

Xét ví dụ:

S#

SNAME

STATUS

CITY P#,

PNAME COLOR WEIGHT

PRICE QTY

Paris P1 B1

do

23

100

200

S1 A1

17

Paris P2 B2

Xanh

11

150

300

S1 A1

17

P2 B2

Xanh

17

150

250

S2 A2

20

Lond on

Hoang Thi Ha

Câu hỏi?

 Vậy làm thế nào để thiết kế một CSDL cho

tốt?

Hoang Thi Ha

Nhận xét

 Ưu điểm: Khi thực hiện truy vấn SQL chỉ cần

thực hiện các phép toán một ngôi do đó biếu diễn câu hỏi dễ dàng, thời gian chi phí đáp ứng nhỏ.

Hoang Thi Ha

Nhận xét (cont)

 Nhược điểm:

 Dư thừa dữ liệu (Redundancy): Dễ dàng thấy rằng mỗi khi xuất hiện tên nhà cung cấp thì địa chỉ của ông ta lại lặp lại trong mối quan hệ.  Không nhất quán (Inconsistency) (dị thường xuất hiện khi sửa dữ

liệu): Là hệ quả của việc dư thừa dữ liệu. VD: khi sửa đổi địa chỉ của nhà cung cấp ở bộ nào đó còn các bộ khác giữ nguyên thì một nhà cung cấp có nhiều địa chỉ.

 Dị thường khi thêm bộ (Insertion anomalies): Nếu một nhà cung cấp chưa cung cấp một mặt hàng nào cả, khi đó ta không thể đưa thông tin về nhà cung cấp đó vì …sẽ phải đưa giá trị nào vào các thuộc tính còn lại.

 Dị thường khi xoá bộ (Deletion anomalies): Là vấn đề ngược lại của vấn đề trên. Nếu vô tình một nhà cung cấp chỉ mới cung cấp một mặt hàng duy nhất (giả sử S2, P2) thì sẽ bị mất thông tin về nhà cung cấp đó.

Hoang Thi Ha

Cách giải quyết thế nào?.

 Để khắc phục những nhược điểm trên thì cần

tách quan hệ trên thành các quan hệ khác nhau ta được một lược đồ CSDL (tập các lược đồ quan hệ) sao cho tốt hơn.

Hoang Thi Ha

Lược đồ VT có thể tách thành 3 lược đồ như sau

 S (S#, SNAME, STATUS, CITY)  P (p#, PNAME, COLOR, WEIGHT, PRICE)  SP (S#, P#, QTY)

Hoang Thi Ha

Nhận xét

 Ưu điểm:

 Khắc phục được sự dư thừa dữ liệu  Tránh dị thường  Nhược điểm:

 Biểu diễn câu hỏi phức tạp hơn.  Thời gian và chi phí tính toán các phép tính toán kết nối

tăng lên.

Hoang Thi Ha

II. Các bước thiết kế một Cơ sở dữ liệu

 Bước 1: Phân tích toàn bộ các yêu cầu  Bước 2: Nhận diện những thực thế và tìm các

thuộc tính cần lưu trữ của nó.

 Bước 3: Nhận diện các mối liên quan giữa các thực

thể

 Bước 4: Xác đinh khoá chính  Bước 5: Nhận diện khoá ngoại lai  Bước 6: Thêm các thuộc tính không phải khoá vào

bảng dữ liệu

 Bước 7: Xây dựng mạng dữ liệu  Bước 8: Khai báo phạm vi của mỗi thuộc tính  Bước 9: Kiểm tra tính chuẩn của các quan hệ(3NF)

Hoang Thi Ha

BÀI 2: PHỤ THUỘC HÀM.

Hoang Thi Ha

I. Khái niệm PTH

t1[Y] = t2[Y] ). X  Y

 Định nghĩa: Cho R(U) là một sơ đồ quan hệ với U= {A1, A2, …, An} là tập các thuộc tính. X,Y U. Ta nói rằng X xác định Y (hay Y phụ thuộc hàm vào X) nếu với hai bộ t1, t2 bất kỳ chúng bằng nhau trên tập X thì cũng bằng nhau trên tập Y( t1[X] = t2[X] thì  Ký hiệu:  Ví dụ: Trong quan hệ NCC ở trên, SID SNAME, SID 

SNAME, SID  SADDR

Hoang Thi Ha

II. Hệ tiên đề Amstrong đối với các phụ thuộc hàm

2. Hệ tiên đề Amstrong đối với các phụ thuộc hàm.  Cho R(U) là một sơ đồ quan hệ với U = {A1, A2, …, An} là tập các thuộc tính. X,Y, Z, W  U.

 Ta ký hiệu XY= X Y  Hệ tiên đề Amstrong:

 A1: Phản xạ(reflexivity): Nếu Y  X  U thì X  Y  A2: Tăng trưởng(augmentation): Nếu X  Y, Z  U thì

XZ  YZ

 A3: Bắc cầu (transitivity): Nếu X  Y, Y  Z thì X  Z

Hoang Thi Ha

Định lý:

 Hệ tiên đề Amstrong là đúng và đầy đủ(đã được

chứng minh)

Hoang Thi Ha

Từ hệ tiên đề Armstrong suy ra một số luật sau đây:

Với X,Y, Z, W  U:  a. Luật hợp (Union rule): Nếu X  Y, X  Z thì X  YZ  b. Luật tựa bắc cầu (pseudotransitivity rule): Nếu X  Y,

WY  Z thì WX  Z

 c. Luật tách(decomposition): Nếu X  Y, Z Y thì X  Z

Hoang Thi Ha

III. Bao đóng(closures of attribute sets)

 Đặt vấn đề: Cho quan hệ r, tập PTH F, và tập

phụ thuộc tính X,Y  U. Hỏi rằng X  Y có thõa mãn trong r?.

 Để trả lời được câu hỏi trên có 2 cách:

 Cách 1: Tính F+ và xem X  Y  F+ hay không?. Như

vậy, ta phải tính F+ , nhưng việc tính F+ là rất khó.

 Cách 2: Tính bao đóng của X . Cách thứ 2 này đơn giản

hơn so với cách thức nhất.

Hoang Thi Ha

Bao đóng(cont)

 Bao đóng của tập thuộc tính X  Định nghĩa: Bao đóng của tập thuộc tính X (ký hiệu X+) bao gồm các thuộc tính A  U sao cho

X  A  F+.

 Vậy, bao đóng của 1 tập thuộc tính X cho ta biết được các

thuộc tính mà X xác định nó.

Hoang Thi Ha

Thuật toán tìm bao đóng của tập thuộc tính X:

 Input: Tập hữu hạn các thuộc tính U, tập các

PTH F trên U và X  U

+)

 Output: Bao đóng của X đối với F (XF  Thuật toán:Tính liên tiếp X0, X1, X2, …X(k) theo

các bước sau:  Bước 1: Đặt X0 = X  Bước 2: Lần lượt xét các phụ thuộc hàm trong F, nếu

Y  Z  F mà Y  Xi ; A  Xi và A  Z thì Xi+1 = Xi  A.

 Bước 3: Nếu Xi+1 = Xi , khi đó ta có: XF

+ = Xi+1

Hoang Thi Ha

Ví dụ

Ví dụ: Cho lược đồ R(U, F) , U= {A, B, C, D,E}

F= {A BC, C DE, E A}

+ Hãy tính CF  Đặt X0 = C 









+ = CDEAB

X 1 = CDE vì (C DE) X2 = CDEA vì ( E  A) X3 = CDEAB vì (A BC) X4 = X3 Vậy : CF

Hoang Thi Ha

Tính chất của bao đóng

 1. Tính phản xạ: X ⊆ X+  2. Tính đơn điệu: Nếu X ⊆ Y thì X+ ⊆ Y+  3. Tính lũy đẳng: X++ = X+  4. (XY)+ ⊇ X+Y+  5. (X+Y)+ = (XY+)+ = (X+Y+)+  6. X → Y ⇔ Y+ ⊆ X+  7. X+ = Y+ ⇔ X → Y và Y → X

Hoang Thi Ha

Bao đóng của tập PTH F (F+)

 Định nghĩa: Cho một lược đồ quan hệ R(U,F),

bao đóng của tập PTH F (ký hiệu là F+) là tất cả các PTH được suy diễn logic từ F mà mọi quan hệ trên lược đồ R đều thõa mãn điều kiện sau:  F  F+  Khi ta áp dụng hệ tiên đề Armstrong đối với các PTH trong F+ thì không thể thêm được một PTH nào khác ngoài các PTH trong F+ .

Hoang Thi Ha

Tính chất :

 Tính chất 1: Tính phản xạ: F  F+  Tính chất 2: Tính đơn điệu: F, G là hai tập PTH,

nếu F  G thì F+ G+

 Tính chất 3: Tính lũy đẳng: (F+)+ = F+  Tính chất 4: (F+G)+=(FG+)+=(FG)+  Tính chất 5: F+G+  (FG)+

Hoang Thi Ha

Thuật toán tìm bao đóng của tập phụ thuộc hàm F(F+)

 Input: Lược đồ quan hệ R (U,F)  Output: F+ là bao đóng của F  Thuật toán:

 Bước1: Tìm tất cả các tập con của U: Xi⊆U  Bước 2: Tìm (Xi)+ với F ban đầu  Bước 3: Dựa vào (Xi)+ đã tìm để suy ra các PTH thuộc F+

Hoang Thi Ha

 Cho lược đồ quan hệ R(A,B,C) với

F = {AB → C,C → B}

 Hãy tính F+

Hoang Thi Ha

B1: Các tập con của U

Hoang Thi Ha

B2: Tìm bao đóng của tất cả các tập con của R

Hoang Thi Ha

V. Phủ của các tập phụ thuộc hàm

V.1. Hai tập phụ thuộc hàm tương đương  Định nghĩa: Cho F và G là tập các PTH trên tập thuộc tính U. Ta nói F và G là tương đương nếu F+ = G+ ( F phủ G hay G phủ F). Ký hiệu là F  G

Hoang Thi Ha

Thuật toán xác định F và G có tương đương không

 Bước 1: Với mỗi PTH XY của F ta xác định xem XY có là thành viên của G không?.

 Bước 2: Với mỗi PTH XY của G ta xác định

xem XY có là thành viên của F không?.  Nếu cả hai bước trên đều đúng thì F  G

Hoang Thi Ha

Ví dụ:

 Cho lược đồ quan hệ R(ABCDE) và hai tập phụ

thuộc hàm F={A→BC,A→D,CD→E} và G = {A→BCE,A→ABD,CD→E}

 Hỏi:

 a. F có tương đương với G không?.  b. F có tương đương với G’={A→BCDE}không?.

Hoang Thi Ha

V.2. Phủ tối thiểu của một tập phụ thuộc hàm (minimal cover):

 Tập phụ thuộc hàm F là tối thiểu nếu:

 1. Vế phải của các tất cả các phụ thuộc hàm trong F chỉ

có một thuộc tính.

 2. Không tồn tại X → Y trong F và một tập con thực sự Z

của X sao cho F\ {X → Y}{Z→Y}tương đương với F. (Điều kiện này đảm bảo không có vế trái nào có thuộc tính dư thừa)  3. Không tồn tại X → Y trong F sao cho F\{ X → Y } tương

đương với F

(Điều kiện này đảm bảo cho F không có phụ thuộc hàm dư

thừa)

Chú ý: PTH có vế trái chứa 1 thuộc tính gọi là PTH đầy đủ

Hoang Thi Ha

Tập phụ thuộc hàm không dư thừa

 Cho F là một tập phụ thuộc hàm, ta nói F là

không dư thừa nếu không tồn tại một phụ thuộc hàm X → Y trong F , sao cho F\ X → Y tương đương với F.

Hoang Thi Ha

Thuật toán tìm tập phụ thuộc hàm F không dư thừa

 Giả sử F={ X i→ Yi }i=1,n  Lần lượt xét các phụ thuộc hàm X → Y của F để tính các tập F0, F1, F2, …, Fn theo các bước sau:





- Bước 0: F0 = F - Bước i: Tính Fi từ Fi-1 theo công thức:

 Fi = Fi-1\{ X i→ Yi } nếu Fi-1\{ X i→ Yi } tương đương với

Fi-1, ngược lại ta đặt Fi = Fi-1.

 Cuối cùng ta được: F= Fn chính là tập phụ thuộc hàm F

không dư thừa.

Hoang Thi Ha

Ví dụ

1. Cho R(A,B,C) F={AB→C; B→C}

 Hỏi PTH F này có phải là PTH tối thiểu không?.

2. Cho R(A,B,C,D) F = {A → BC,B → C,AB → D}

 Hỏi PTH F này có phải là PTH tối thiểu không?.

Hoang Thi Ha

Thuật toán loại khỏi F các PTH có vế trái dư thừa

 Bước 1: Lần lượt thực hiện bước 2 cho các PTH

X → Y thuộc 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 bằng X’ → Y

thực hiện lại bước 2

Hoang Thi Ha

Ví dụ

 Trong phụ thuộc hàm

F = {A → BC,B → C,AB → D} có A+= ABCD nên A → D vì vậy, ta thay AB → D bằng A → D ⇒ F ≡ {A → BC,B → C,A → D}

Hoang Thi Ha

Thuật toán loại khỏi F các PTH dư thừa

 Bước 1: Lần lượt xét các PTH X → Y thuộc F  Bước 2: Nếu X → Y là thành viên của F - {X →

Y} thì loại bỏ X → Y khỏi F

 Bước 3: Thực hiện bước 2 cho các PTH còn lại

của F

Hoang Thi Ha

Chú ý

 Từ một tập PTH F ta luôn tìm được ít nhất một PTH Ftt, nếu thứ tự loại bỏ các PTH trong F là khác nhau thì ta thu được các Ftt khác nhau

Hoang Thi Ha

VD:

Hoang Thi Ha

Ví dụ

Hoang Thi Ha

Bài 3: Khóa của một lược đồ quan hệ

 Định nghĩa: Cho một lược đồ quan hệ R(U) và một tập PTH F, K là tập con của U. Ta nói K là khóa của quan hệ R(U) nếu:  K+= U  Không tồn tại K’K mà K’+=U Tập thuộc tính S được gọi là siêu khóa nếu: S K Thuộc tính A được gọi là thuộc tính khóa nếu A thuộc bất kỳ khóa nào của R(U), ngược lại A được gọi là thuộc tính không khóa

Chú ý: Một lược đồ quan hệ có thể có nhiều khóa và

thuộc tính không khóa có thể bằng rỗng

Hoang Thi Ha

IV.1. Thuật toán tìm 1 khóa tối thiểu

 Vào: Lược đồ quan hệ R(U,F)với U={A1, A2,… An}  Ra: Một khóa tối thiểu của R với phụ thuộc hàm F  Thuật toán: Lần lượt tính các tập K0, K1,…

Kn theo các bước sau:  Bước 0: Đặt K0=U  Bước i: Tính Ki từ Ki-1, cụ thể Ki = Ki-1\{ Ai } nếu

Ki-1\ { Ai } ->U

 Ngược lại,Ki =Ki-1

Cuối cùng, đặt K=Kn

Hoang Thi Ha

Ví dụ 1

Cho lược đồ quan hệ: R(A,B,C,D,E,G) và tập phụ thuộc hàm F={AB→ C;C → A; BC→D; ACD→B; D→EG; BE→C, CG →BD, CE →AG}

 Hãy tìm một khóa tối thiểu của R

Hoang Thi Ha

Áp dụng thuật toán ta có;

 Bước 0: Đặt K=U=(A,B,C,D,E,G)  Bước 1: K1=K\{A} = BCDEG vì BCDEG →U  Bước 2:K2=K1\{B}= CDEG vì BCDEG →U  Bước 3: K3=K2= CDEG  Bước 4: K4=K3\D = CEG vì CEG →U  Bước 5: K5=K4\E=CG vì CG →U  Bước 6: K6=K5=CG Vậy khóa tối thiểu của R là CG.

Hoang Thi Ha

Lưu ý

 Thuật toán tìm khóa trên chỉ nên sử dụng trong

trường hợp tìm một khóa.

Hoang Thi Ha

IV.2.Thuật toán tìm tất cả các khóa của R(U)

 B1: Tìm tất cả các tập con Xi khác rỗng của U

(XiU)

 B2: Tìm bao đóng của các Xi  B3: Siêu khóa chính là các Xi có bao đóng đúng

bằng U. Giả sử ta có các siêu khóa là

S ={S1,S2,…,Sm}

 Xây dựng tập chứa tất cả các khóa của R(U) từ tập S bằng cách xét mọi Si, Sj(ij), nếu Sj  Si Thì ta loại Sj(i,j=1..n) kết quả còn lại của S chính là

tập các khóa cần tìm

Hoang Thi Ha

Ví dụ

 Cho quan hệ R(C,S,Z);  F = {f1:CS → Z; f2:Z → C}

 Tìm tất cả các khóa của lược đồ quan hệ trên

Hoang Thi Ha

Hoang Thi Ha

 Vậy, lược đồ trên có hai khóa là {C,S} và {S,Z}  Nhận xét:

 Thuật toán trên dễ hiểu, dễ cài đặt, tuy nhiên nếu n lớn thì phép duyệt để tìm ra tất cả các tập con của U là không hiệu quả. Do vậy, cần thu hẹp không gian duyệt

Hoang Thi Ha

Thuật toán cải tiến tìm tất cả các khóa

 Trước hết cần xét một số khái niệm:

 Tập thuộc tính nguồn(TN) là tập tất cả các thuộc tính chỉ xuất hiện ở vế trái mà không xuất hiện ở vế phải của các PTH và những thuộc tính không xuất hiện ở cả vế trái và vế phải của các PTH.

 Tập thuộc tính đích(TD) là tập tất cả các thuộc tính chỉ xuất hiện ở vế phải mà không xuất hiện ở vế tráicủa các PTH

 Tập thuộc tính trung gian(TG) là tập tất cả các

thuộc tính xuất hiện ở cả 2 vế của các PTH

Hoang Thi Ha

Thuật toán tìm tất cả các khóa của R(U)

Input: R(U,F) Output: Tập tất cả các khóa của R(U) Thuật toán:

Hoang Thi Ha

Thuật toán

Hoang Thi Ha

Ví dụ

 Cho quan hệ Q(C,S,Z);  F = {f1:CS → Z; f2:Z → C}

 Tìm tất cả các khóa của lược đồ quan hệ trên

Hoang Thi Ha

 TN={S}  TG={Z,C}  Gọi Xi là các tập con của tập TG

Hoang Thi Ha

 Vậy tập các khóa là {S,C} và {S,Z}

Hoang Thi Ha

Bài tập về phụ thuộc hàm, Khóa

Hoang Thi Ha

Bài tập(cont)

Hoang Thi Ha

Bài tập (Cont)

Hoang Thi Ha

Bài tập (cont)

Hoang Thi Ha

Hoang Thi Ha

Bài tập (cont)

Hoang Thi Ha

Bài 4. CHUẨN HÓA CÁC LƯỢC ĐỒ QUAN HỆ (normal forms for relation schemes)

Hoang Thi Ha

NỘI DUNG

 Thảo luận về entity integrity và referential integrity

 Lược đồ ở dạng chuẩn (1NF)

 Lược đồ ở dạng chuẩn (2NF)

 Lược đồ ở dạng chuẩn (3NF)

 Lược đồ ở dạng chuẩn (BCNF)

 Phép tách các lược đồ quan hệ

Hoang Thi Ha

TẠI SAO PHẢI CHUẨN HÓA LƯỢC ĐỒ QUAN HỆ?

Xét một số khái niệm sau:

 Toàn vẹn dữ liệu: Tất cả các dữ liệu trong Database là

phù hợp

 Dư thừa dữ liệu: Dữ liệu bị lặp lại trong Database.

 Vì vậy, mục đích của chuẩn hóa các lược đồ quan hệ là

tránh sự dư thừa dẫn đến sự sai sót của dữ liệu .

Hoang Thi Ha

I. Định nghĩa các dạng chuẩn

1. Dạng chuẩn 1NF: Một lược đồ quan hệ R được gọi là ở dạng chuẩn 1 (1NF) nếu và chỉ nếu toàn bộ các miền có mặt trong R đều chỉ chứa các giá trị nguyên tố(hay các thuộc tính của mọi bộ đều mang giá trị đơn)  Quy tắc 1NF nhằm loại bỏ nhóm lặp, nghĩa là bảng 1NF không được chứa các thuộc tính có thể xuất hiện nhiều lần đối với cùng một kiêủ thực thể.

Hoang Thi Ha

Ví dụ: Có quan hệ Student:

Hoang Thi Ha

Nhận xét

 Quan hệ sinh viên trên sẽ không ở dạng chuẩn

1NF(hay gọi là dạng không chuẩn)

 Ta có thể chuyển quan hệ sinh viên trên về dạng

chuẩn 1NF như sau:

Hoang Thi Ha

Student

Hoang Thi Ha

1NF

 Mặc dù cách giải quyết này có cải tiến nhưng

sẽ gặp phải một số vấn đề:

 student_no không thể làm primary key vì bị lặp lại

 Vì vậy phải tìm một khóa mới, trong trường hợp này nó phải là khóa phức- có nhiều hơn một thuộc tính. Khóa mới là student_no và subject.

 Nhưng dữ liệu lại bị lặp lại nhiều, dư thừa dữ liệu ->

việc xử lý dữ liệu có thể sai sót. Mà sự dư thừa dữ liệu lại là nguyên nhân chính gây nên sự dị thường của dữ liệu mỗi khi thực hiện các thao tác chèn, xóa, và cập nhật dữ liệu.

Hoang Thi Ha

1NF

 Dị thường khi thêm bộ: Ta không thể thêm một

sinh viên mới vào database nếu như sinh viên đó chưa tham gia học môn nào(vì ta không thể bỏ trống trường Subject)

 Dị thường khi cập nhật dữ liệu  Dị thường khi xóa bộ

Hoang Thi Ha

Vậy phải làm thế nào?

 Ta sẽ phải chia bảng Student ban đầu thành 2

bảng, khóa chính trong quan hệ ban đầu có trong cả 2 quan hệ:  Quan hệ thứ nhất chứa các thông tin không bị lặp lại  Quan hệ thứ hai chứa các thông tin bị lặp

Hoang Thi Ha

1NF

Diem

Sinhvien

Hoang Thi Ha

1NF

 Trong quan hệ Sinhvien sẽ giữ trường

Student_no làm khóa chính

 Trong quan hệ Diem sẽ lấy trường Student_no

và subject làm khóa chính

 Trường Student_no sẽ liên kết hai bảng Sinh viên và điểm, giúp ta tìm được các thông tin về các môn học cùng với điểm các môn học của các sinh viên.Trong bảng Diem trường Student_no sẽ làm khóa ngoại lai.

Hoang Thi Ha

1NF

 Vậy, với việc tách trên thì đã giảm bớt được một số sự

dị thường:

 Khi thêm: Ta có thể thêm sinh viên mới mà không cần biết họ đã tham gia học hay chưa?. Việc thêm này, chỉ nằm trong quan hệ Student và không nằm trong quan hệ Record cho đến khi sinh viên này sinh viên này học ít nhất một môn

 Khi xóa: Ta có thể xóa tất cả các bản ghi trong bảng

Diem nhưng sinh viên có mã student 960145 vẫn còn tồn tại trong bảng Student.

 Khi update dữ liệu

Hoang Thi Ha

Dạng chuẩn 2NF

 2NF là dạng chuẩn chặt hơn dạng chuẩn 1NF. Một quan hệ là ở 2NF nếu và chỉ nếu nó ở dạng 1NF và mỗi thuộc tính không khóa đều phụ thuộc hàm đầy đủ vào khóa chính.

 Nhận xét: Nếu quan hệ ở 1NF và có khóa chỉ là một

thuộc tính thì nó đã tồn tại ở 2NF.

Hoang Thi Ha

2NF

 Vậy, vấn đề là khi quan hệ có khóa chính có

nhiều hơn một thuộc tính.

 Ví dụ: Trong quan hệ Diem có khóa chính là

student_no,subject

Hoang Thi Ha

2NF

 Xét quan hệ Student với các thuộc tính sau:

 Student (student_no, course_no, student_name,

address, course_name, grade)

Hoang Thi Ha

2NF

 Trong quan hệ trên ta nhận thấy:

 student_no student_name, address

 student_no không xác định course_name

 course_no course_name, nhưng không xác định

student_name, và address.

 Ta có thẻ biểu diễn các PTH bằng cách sử dụng sơ đồ

PTH sau:

Hoang Thi Ha

2NF

 Sơ đồ trên cho thấy các thuộc tính không khóa của của quan hệ Student liên quan với các thuộc tính khóa. Một mũi tên áp dụng cho một PTH, ngược lại không áp dụng cho PTHStudent

Hoang Thi Ha

2NF

 Vậy, quan hệ trên không ở 2NF.

 Ta sẽ chia quan hệ trên thành 3 quan hệ:

 Quan hệ Student_detail với các thuộc tính mà chỉ có

thuộc tính student_no làm khóa chính.

 Quan hệ thứ hai là Course bao gồm các thuộc tính chỉ

PTH vào thuộc tính course_no, trong quan hệ này khóa chính là course_no.

 Thuộc tính grade PTH vào cả hai thuộc tính là khóa của 2 quan hệ trên (student_no, course_no), vì vậy tách thành quan hệ riêng bao gồm các thuộc tính student_no, course_no và grade.

Hoang Thi Ha

2NF

 Student_details

 Course

 Student

Hoang Thi Ha

2NF

 Với cách chia trên ta nhận thấy, trong các quan hệ mới tất cả các thuộc tính sẽ PTH đầy đủ vào khóa chính. Vì xậy, các quan hệ này đều là ở 2NF.

Hoang Thi Ha

Dạng chuẩn 3NF

 Dạng chuẩn 3NF là một dạng chuẩn chặt, trong dạng chuẩn này đã loại bỏ được tất cả các dị thường xảy ra trong DataBase.

 Định nghĩa:Một quan hệ là ở 3NF nếu và chỉ nếu nó ở 2NF và mọi thuộc tính không khóa đều PTH trực tiếp vào khóa chính(hay không có thuộc tính không khóa này lại PTH vào thuộc tính không khóa khác)



Nhận xét: Nếu một quan hệ ở 2NF và không có hoặc có một thuộc tính không khóa thì nó sẽ tồn tại ở 3NF.

Hoang Thi Ha

Thuật toán kiểm tra dạng chuẩn 3NF

 Vào: Một lược đồ quan hệ R(U,F)  Ra: Lược đồ quan hệ trên có ở dạng chuẩn 3NF

hay không ở dạng 3NF .

 Phương pháp:

 Bước 1: Tìm tất cả các khóa của R  Bước 2: Từ F tạo một tập phụ thuộc hàm tương đương F’

có vế phải một thuộc tính

 Bước 3: Nếu mọi phụ thuộc hàm X→ A  F’ với A X đều có X là siêu khóa hoặc A là thuộc tính khóa thì R đạt dạng chuẩn 3NF, ngược lại R không ở dạng chuẩn 3NF.

Hoang Thi Ha

Ví dụ

 Project có nhiều hơn một thuộc tính không khóa là

address và manager.

 Theo quan hệ trên ta nhận thấy address phụ thuộc vào giá

trị trong cột manager . Vì vậy, manager  address

Hoang Thi Ha

Ví dụ 1

 Trong sơ đồ trên xuất hiện sự dư thừa của dữ liệu. Ta

thấy địa chỉ của manager vị lặp lại nếu như một manager tham gia nhiều hơn một project.

 Để loại bỏ sự dư thừa này ta phải tách quan hệ trên thành 2

quan hệ:

 Một quan hệ bao gồm các thuộc tính mà có PTH trực tiếp vào

khóa chính.

 Một quan hệ bao gồm các thuộc tính còn lại

 Vậy, chia quan hệ Project thành Project và Manager.

 Quan hệ Manager có khóa chính là manager .

 Khóa chính ban đầu trở thành thuộc tính khóa trong

quan hệ Projects mới.

Hoang Thi Ha

Example - 3

 Project

Manager

 Bây giờ, ta chỉ cần lưu trữ địa chỉ một lần

Hoang Thi Ha

Tóm tắt_1

 1NF

 Một quan hệ ở 1NF nếu và chỉ nếu toàn bộ các miền giá trị của các thuộc tính trong quan hệ đều chỉ chứa các giá trị nguyên tố(các giá trị không thể phân chia được).

 Để chuyển từ quan hệ không chuẩn thành 1NF:

 Làm phẳng bảng và thay đổi khóa chính.

 Chia quan hệ thành những quan hệ nhỏ hơn, một quan hệ chứa các giá trị lặp và một quan hệ không chúa các giá trị lặp. Chú ý, đặt khóa chính vào cả hai quan hệ mới.

Hoang Thi Ha

Tóm tắt- 2

 2NF

 Một quan hệ ở 2NF nếu nó ở 1NF và mọi thuộc tính không khóa của nó đều PTH đầy đủ vào khóa chính.

Nếu một quan hệ chỉ có một thuộc tính thì ở

 Chú ý: 2NF.

 Để chuyển một quan hệ chưa ở 2NF thành 2NF thì ta tạo

một tập quan hệ mới:

 Một quan hệ với các thuộc tính là những PTH đầy đủ vào khóa chính, và những quan hệ còn lại cho các PTH bị vi phạm 2NF.

Hoang Thi Ha

Tóm tắt- 3

 3NF

 Một quan hệ ở 3NF nếu nó ở 2NF và các thuộc tính

không khóa đều PTH trực tiếp vào khóa chính

 Để chuyển một quan hệ vi phạm 3NF thành 3NF ta loại bỏ các thuộc tính liên quan đến những PTH bị vi phạm và đặt chúng trong một quan hệ mới

 Rule: Một quan hệ ở 2NF nếu không có hoặc chỉ có 1

thuộc tính không khóa đều ở 3NF.

 Các quan hệ ở dạng chuẩn 3NF rất tốt cho hầu hết các bài toán thiết kế CSDL thực tế. Mặc dù vậy, 3NF không dảm bảo rằng tất cả các dị thường đều bị xóa hết.

Hoang Thi Ha

Quá trình tách một lược đồ quan hệ dạng chưa chuẩn về dạng chuẩn 1NF, 2NF, 3NF

Hoang Thi Ha

DẠNG CHUẨN Boye-Codd(BCNF)

 Định nghĩa: Một sơ đồ quan hệ R(U) với tập PTH F được gọi là ở dạng chuẩn Boye – Codd nếu với mọi X→A thuộc F+ và A X thì X chứa một khóa của R.

 Xét ví dụ: Cho sơ đồ quan hệ R(C,S,Z), giả sử

trên sơ đồ này có các PTH CS→Z, Z→C. Ta đã biết sơ đồ này có hai khóa tối thiểu là CS và SZ, như vậy sơ đồ này không có thuộc tính không khóa và ở dạng 3NF, tuy nhiên nó không ở BCNF do Z→C thuộc F nhưng Z không chứa khóa của R.

Hoang Thi Ha

BCNF(cont)

 Mục đích của BCNF: Loại bỏ sự dư thừa dữ liệu và tránh các dị thường cập nhật do thao tác thêm và thao tác xóa. Tuy nhiên, dạng chuẩn BCNF còn có thể loại bỏ được một số dị thường mà dạng chuẩn 3NF không loại bỏ được.

 Ví dụ:  Định lý: Một quan hệ ở BCNF thì ở 3NF

Hoang Thi Ha

PHÉP TÁCH CÁC SƠ ĐỒ QUAN HỆ

 Giới thiệu: Phép tách một sơ đồ quan hệ R với

R={A1, A2,…,An} là thay thế nó bởi một tập các sơ đồ con  = {R1(u1), R2(u2),…,Rk(uk)}, ở đây, Ri (i=1,2,…,k) là các tập con của R và R1 R2…Rk =R và Ri=ui(R). Phép tách sơ đồ có thể cho phép loại bỏ được những vấn đề đã đề cập ở phần đầu chương.

 Phép tách không mất thông tin (lossless join)

 Giả sử sơ đồ quan hệ R được phân tách thành các sơ đồ con R1, R2,…,Rk và F là các PTH trên R, ta nói phép tách này là không mất mát thông tin nếu R1*R2*…*Rk R

Hoang Thi Ha

Định lý tách

 Cho R(U),  = {R1(u1), R2(u2)} là phép tách 2 không làm mất thông tin nếu u1u2 u1\u2 hoặc u1u2 u2\u1

 Hệ quả tách:

 Cho R(U) , XY, = {R1(u1), R2(u2)}, u1=XY, U2=XZ

(Z=U\XY) thì  không làm mất mát thông tin,

Hoang Thi Ha

Thuật toán kiểm tra phép tách  có làm mất mát thông tin hay không?.

 Input: R(A1,A2,…,An),

 = {R1(u1), R2(u2),…,Rm(um)} F={LiRi}, i=1,k

 Output:  có làm mất thông tin hay không?.  Thuật toán:

 Xác định bảng kiểm tra Tmxn gồm n cột, m dòng  Tmxn =(tij)  Mọi j=1m với Ai Uj thì tij=ai, ngược lại tij=bij  Mọi i=1k, xét LiRi , nếu mọi t1,t2  T mà t1[Li] =t2[Li]

thì gán t1[Ri]=t2[Ri], ưu tiên các biến ai

Hoang Thi Ha

Thuật toán kiểm tra một phép tách không làm mất thông tin



Bước 1: Tạo một bảng Tm n gồm m hàng và n cột. Cột thứ j tương ứng

với thuộc tính Aj , hàng thứ i tương ứng với lược đồ quan hệ con Ri . Ở vị trí hàng i, cột j , ta đặt ký hiệu aj nếu Aj  Ri , ngược lại ta đặt ký hiệu bij vào vị trí đó.



Bước 2: Lần lượt xét các phụ thuộc hàm trong F và áp dụng các phụ

thuộc hàm này cho bảng vừa xây dựng được. Giả sử xét phụ thuộc hàm X→ Y∈ F. Nếu tồn tại hai hàng mà tất cả các cột tương ứng với các thuộc tính của X có giá trị như nhau thì ta làm cho các cột ứng với các thuộc tính của Y cũng có giá trị như nhau trong hai hàng này theo nguyên tắc sau: nếu có một ký hiệu aj trong các cột ứng với các thuộc tính Y thì đồng nhất các ký hiệu aj , nếu không thì đồng nhất bằng bij.



Tiếp tục áp dụng các phụ thuộc hàm cho bảng trên (kể cả việc lặp lại các phụ thuộc hàm đã được áp dụng) cho tới khi không có sự thay đổi trong bảng.



Bước 3: Kiểm tra bảng trên, nếu có tồn tại một hàng gồm các ký hiệu

a1, a2,..., an (chứa toàn a) thì phép tách không tổn thất thông tin (còn gọi là bảo toàn thông tin). Ngược lại, thì phép tách làm tổn thất thoongg tin (hay còn gọi là không bảo toàn thông tin) .

Hoang Thi Ha

Hoang Thi Ha

 Cho lược đồ R(U,F), U=ABCDE



F= {A  C, B C, C  D, DE  C, CE A} Phép tách  tách lược đồ quan hệ trên thành: R1=AD, R2=AB, R3=BE, R4 =CDE, R5=AE  Hỏi phép tách  trên có làm mất thông tin hay

không?.

Hoang Thi Ha

THUẬT TOÁN TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM VỀ DẠNG CHUẨN 3NF.

 Vào: - R(U); Tập phụ thuộc hàm F. Không mất

tính tổng quát giả sử F là phủ tối thiểu.

 Ra:  - một phép tách bảo toàn tập phụ thuộc

hàm bao gồm 1 tập các sơ đồ con, trong đó mỗi sơ đồ con đều ở dạng chuẩn 3NF với các phụ thuộc hàm là hình chiếu của F lên sơ đồ đó.

Hoang Thi Ha

PHƯƠNG PHÁP TÁCH

 1. Nếu có những thuộc tính nào đó thuộc R nhưng

không xuất hiện trong bất kỳ một phụ thuộc hàm nào kể cả vế trái lẫn vế phải của 1 phụ thuộc hàm trong F thì về nguyên tắc có thể hình thành một sơ đồ quan hệ riêng xác định trên những thuộc tính này và loại nó ra khỏi R.

 2. Nếu có 1 phụ thuộc hàm liên quan tới tất cả các

thuộc tính của R thì kết quả ra chính là R.

 3. Ngược lại, kết quả ra bao gồm các sơ đồ XA ứng với 1 phụ thuộc hàm X->A trong F. Tuy nhiên, nếu chúng ta có các phụ thuộc hàm X->A1,...X->An, thì chúng ta có thể sử dụng XA1A2....An thay cho XAi (i=1,n).

Hoang Thi Ha

VÍ DỤ

 Cho sơ đồ quan hệ: R(ABCDEG) và tập phụ thuộc

hàm F=AB->C, C->A, BC->D, ACD->B, D->EG, BE- >C, CG->BD, CE->AG. Hãy tách sơ đồ quan hệ trên về dạng chuẩn 3NF bảo toàn tập PTH .

Bài làm

 - Bước 1: Kiểm tra F có phải là phủ tối thiểu?. 

Vì F không phải là phủ tối thiểu nên ta

phải chuyển F về phủ tối thiểu:



+ Tách các vế phải với nhiều hơn 1 thuộc tính với vế trái giữ nguyên thu được F1= AB->C, C- >A, BC->D, ACD->B, D->E,D->G, BE->C, CG->B, CG->D, CE->A, CE->G

Hoang Thi Ha

TiÕp



+ Xét mỗi phụ thuộc hàm trong F1 với vế trái nhiều hơn 1 thuộc tính theo thứ tự như trên để loại bỏ các thuộc tính dư thừa. Ta có F2= AB->C, C- >A, BC->D, CD->B, D->E, D->G, BE->C, CG->B, CG->D, CE->A, CE->G



+ Loại bỏ các PTH dư thừa: Đặt F0=F2. Để tính F1ta phải kiểm tra phụ thuộc hàm thứ nhất AB->C có được suy diễn từ các PTH còn lại không, cụ thể tính bao đóng AB đối với các PTH F0 \ AB- >C. Nếu (AB)+ không chứa C thì không bỏ được PTH AB-> C. Tương tự cho các PTH còn lại. Cuối cùng ta có:



F’= Ftt=AB->C, C->A, BC->D, D->E, D->G,

BE->C, CG->B, CE->G

Hoang Thi Ha

Tiếp

 Bước 2: áp dụng thuật toán trên ta có:

=ABC, CA, BCD, DEG, BEC, CGB, CEG  Vì AC ABC nên ta loại AC khỏi . Kết quả là =ABC, BCD, DEG, BEC, CGB, CEGlà phép tách về dạng chuẩn 3NF

Hoang Thi Ha

 Vào: - R(U,Ftt);  Ra:  - một phép tách không mất thông tin và bảo toàn tập phụ thuộc hàm,  bao gồm 1 tập các sơ đồ con, trong đó mỗi sơ đồ con đều ở dạng chuẩn 3NF

THUẬT TOÁN TÁCH BẢO TOÀN TẬP PHỤ THUỘC HÀM VÊ DẠNG CHUẨN 3NF VÀ KHÔNG MẤT THÔNG TIN BẢO TOÀN TẬP PTH

Hoang Thi Ha

Thuật toán

 Giả sử  là phép tách của thuật toán trên(TToán 8) và K là 1 khoá của R thì  =   {K} là một phép tách bảo toàn F và không mất thông tin.

 Vậy các bước: - Bước 1: Tìm  - Bước 2: Tìm khoá tối thiểu K - Bước 3: Tồn tại Ri(ui) thuộc  mà K ui

   = , ngược lại  =   Ri(K)

Hoang Thi Ha

Ví dụ

 Cho R(U), U=A,B,C,D,E,F,G,H,I,K

F={AB->CDE, DE->C, F->GH, AF->I}  Hãy tách R(U) thành các lược đồ con ở 3NF

không mất thông tin và bảo toàn tập phụ thuộc hàm.

Hoang Thi Ha

Phép tách một lược đồ về dạng chuẩn BCNF

không mất thông tin  Bước 1: Tìm tập tất cả các khóa của R(U,F) Bước 2: Tìm phụ thuộc hàm X →Y F có X không là siêu

khóa. Có hai trường hợp xảy ra: - Trường hợp 1: Nếu tìm thấy thì tách R thành R1 và R2 theo nguyên tắc sau: R1(U1, F1) với U1 =XY, F1= X →Y; R2(U2, F2) với U2 =U\Y, F2=  F(U2). Sau bước này ta được lược đồ R1(U1, F1) đã tồn tại ở dạng BCNF. - Trường hợp 2: Nếu không tìm thấy thì lược đồ đang xét đã tồn tại ở dạng BCNF.

 Bước 3: Lặp lại bước 1 và bước 2 cho lược đồ R2(U2,

F2).

Tiếp tục quá trình trên cho đến khi mọi sơ đồ con đều

ở dạng chuẩn BCNF. Kết quả cuối cùng ta được một phép tách không mất thông tin về dạng chuẩn BCNF.

Hoang Thi Ha

Ví dụ 5.21. Xét lược đồ quan hệ R(U,F) với U=

CTHRSG

 Trong đó: C = course (khóa học), T=teacher

(thầy giáo), H = hour(giờ học),

R=room (phòng học), S=Student (sinh viên),

G=grade (điểm số).

 Các phụ thuộc hàm F tối thiểu tồn tại là:

Ftt = { C→T,HR → C ,

HT → R, CS→ G, HS → R}  Hãy xác định một phép tách  tách lược đồ trên

về BCNF không mất thông tin.

Hoang Thi Ha

Bài làm

U= CTHRSG F= Ftt = { C→T, HR → C, HT → R, CS→ G, HS → R }

U1=CSG F1= CS→ G

U2=CTHRS F2= { C→T, HR → C, HT → R, HS → R }

U21=CT F21= { C→T}

U22=CHRS F22= { HR → C, HS → R }

U222=HRS F222= { HS→ R}

U221=HRC F221= { HR→C}

Hình:

Hoang Thi Ha

Câu hỏi và bài tập chương 4

 (Xem trong cuối chương 4, bài giảng word đầy

đủ)

Hoang Thi Ha

112

Hoang Thi Ha