CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU

Chia sẻ: Shop Tin Học | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

638
lượt xem 80
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hợp lý, nghĩa là phải đủ, không dư thừa. 2. Tiện lợi khi truy nhập, nghĩa là thao tác tìm kiếm, cập nhật, bổ sung và loại bỏ các thông tin phải diễn ra một cách nhanh chóng, thuận tiện. Nội dung của chương này là giới thiệu một số công cụ thường dùng trong quá trình xây dựng CSDL.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU

CHƯƠNG V: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Cơ sở dữ liệu (CSDL) là nơi lưu trữ lâu dài các dữ liệu của hệ thống ở bộ nhớ ngoài. CSDL này phải được tổ chức tốt theo hai tiêu chí: 1. Hợp lý, nghĩa là phải đủ, không dư thừa. 2. Tiện lợi khi truy nhập, nghĩa là thao tác tìm kiếm, cập nhật, bổ sung và loại bỏ các thông tin phải diễn ra một cách nhanh chóng, thuận tiện. Nội dung của chương này là giới thiệu một số công cụ thường dùng trong quá trình xây dựng CSDL. I. PHỤ THUỘC HÀM Khái niệm về phụ thuộc hàm (trong một quân hệ) là một khái niệm có tầm quan trọng hết sức lớn đối với việc thiết kế các mô hình dữ liệu. Để biết được phụ thuộc hàm là gì ta xét ví dụ sau: Ví dụ: SOXE LOAIXE XEMAY= CHUSH 92N95501 DREAMII NAM 92N95502 WAVE@ HOA 92N95504 DREAMII MY 92N95501 @ NAM Þ Bất hợp lý à đưa ra rang buộc nếu 2 bộ dữ liệu bằng nhau trên SOXE thì bằng nhau trên LOAIXE và bằng nhau CHUSH Þ Ràng buộc như vậy ta gọi là phụ thuộc hàm. Như vậy: Phụ thuộc hàm là một loại ràng buộc dữ liệu nhằm đảm bảo các bộ dữ liệu nếu bằng nhau trên tập thuộc tính này thì bằng nhau trên tập thuộc tính khác. I.1.Một số định nghĩa Định nghĩa 1: Cho một quan hệ r định nghỉatên lược đồ quan hệ R. X,Y ⊆ R ta nói phụ thuộc hàm X xác địnhu hàm Y hay Y thuộc hàm vào X, ký hiệu: X → Y đúng trên r nếu ở trong r không tồn tại bất kỳ 2 bộ dữ liệu t1, t2 mà: + t1[X] = t2[X] + t1[Y] ≠ t2[Y] Nhận xét: · Nếu phụ thuộc hàm X xác định hàm Y đúng trên r thì ta nói r thỏa X → Y. · Cho quan hệ r (R), F là một tập các phụ thuộc hàm được định nghĩa như sau: F= {Χ → Υ / Χ, Υ ⊆ R} Ta nói r thỏa F ( hay đúng trên R) nếu r thỏa tất cả các phụ thuộc hàm trong F.
· Cho lược đồ quan R, F là một tập phụ thuộc hàm trên R. Một quan hệ tương ứng với R chỉ được gọi là thể hiện của R nếu quan hệ đó thỏa F. Định nghĩa: Cho một quan hệ r định nghĩa trên lược đồ quan hệ R: X, Y Í R. Xét quan hệ r, giả sử thỏa thuộc hàm X®Y và nếu không tồn tại một tập con thật sự X’ của X sao cho r cũng thỏa phụ thuộc hàm X®Y thì ta nói Y phụ thuộc hàm đầy đủ vào X trong r. Người ta dùng ký hiệu FD (Functional Dependency) để chỉ phụ thuộc hàm và FFD (Functinoal Dependency) để chỉ phụ thuộc hàm đầy đủ. Định lý 2.1: Cho một quan hệ r định nghĩa trên lược đồ quan hệ R. X,Y R, ta có: - X ® Y là phụ thuộc hàm trên r khi và chỉ khi X là khóa của quan hệ r(XY). - X ® Y là phụ thuộc hàm đầy đủ trên r khi và chỉ khi X là khóa tối thiểu của quan hệ r(XY). II.2. Hệ tiên đề cho phụ thuộc hàm Hệ tiên đề Armstrong Gọi r(R) là lược đồ quan hệ với R={A1, A2,....,An} là tập các thuộc tính; giả sử X, Y, Z Í R, hệ tiên đề Armstrong bao gồm: A1: Tính phản xạ: Nếu Y Í X thì X ® Y A2: Tính tăng trưởng: Nếu Z Í R, X ®Y thì ZX® ZY, trong đó ZX = Z È X. A3: Tính bắc cầu: Nếu X®Y và Y® Z thì X ®Z. Ví dụ: Xét một số ví dụ áp dụng: Cho AB ® C, C®A. Chứng minh: BC®ABC Chứng minh: Theo giả thiết: C ® A suy ra BC ® AB (1) (Tính tăng trưởng) Mặt khác ta có: AB ® C (giả thiết) Suy ra: AB ® ABC (2) (tính tăng trưởng) Từ (1) và (2) suy ra B ® ABC (tính bắc cầu). a. Bổ đề 1 Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng trên quan hệ r và f: X ® Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì f đúng trên r. b. Bổ đề 2: A4: Tính hợp: Nếu X® Y và X ® Z thì X ®Y Z. A5: Tính tự bắc cầu: Nếu X→ Y và WY →Z thì XW→Z. Nếu X→Y và Z→Y thì X→Z. A6: Tính tách: c. Bao đóng của tập thuộc tính: Định nghĩa: Cho lược đồ quan hệ R, tập thuộc tính hàm F trên R . X ⊆ R, bao đóng của X theo F là một tập các thuộc tính được định như sau: A X+F ={A/A ∈ R, F |= X→A}
Ví dụ: Cho R = (A, B, C, D ) F = {A→C, CD→ B, BD→E} Tính bao đóng: AD, AB AD+F = ADCBE AB+F = ABC Thuật toán tìm bao đóng của tập thuộc tính trong lược đồ quan hệ: - Cho tập phụ thuộc hàm F trên tập thuộc tính R và một tập con các thuộc tính X, X+ ta xuất phát từ thuộc tập X và bổ sung dần cho X các thuộc tính vế phải P của các phụthuộc hàm T → P Î F thỏa điều kiện T ⊆ X. Thuật toán sẽ dừng khi không thể bổ sung thêm thuộc tính nào cho X. Thuật toán : Đầu vào: - LĐQH p = (R, F ) - Tập thuộc tính X ⊆ R A Đầu ra: X+F = {A /A ∈ R , F |= X →A } Phương pháp: Y := X ; Repeat Z := Y; For each FD T→P in F do If T ⊆ Y then Y:= Y ∪ P Until Y := Z; X+F = Y Ví dụ: Cho quan hệ r trên lược đồ quan hệ R(A, B, C, E, F ) và F là tập phụ thuộc hàm: F = { A →E , DC →B , F→C,A→D }. Tìm bao đóng của A và AF . A+ = AED Ta có : AF+ = AFECDB. d . B ổ đề X→Y có thể suy dẫn từ F nhờ hệ Armstrong khi và chỉ khi Y ⊆ X+ Chứng minh ( ⇒ ) Nếu F |= X→ Y thì Y ⊆ X+ Đặt Y = A1,A2,… An ∀ Ai ∈ Y ta có F |= X→Ai (luật tách) + + ⇒ Ai ∈ X ⇒ Y ⊆ X ( ⇐ ) Y ⊆ X+ thì F |= X→Y Gọi Y = A1,A2,…, An.
+ ∀ Ai ( i=1,…,n), Ai Î X ⇒ F |= X →Ai ( ∀ i= 1,…,n) ⇒ F |= X→Y (hợp). e. Dùng bao đóng của tập thuộc tính để xác định khóa một lược đồ quan hệ Định lý Cho R là một tập các thuộc tính, F là tập phụ thuộc hàm trên R và X ⊆ R. K là khóa của R dưới F khi và chỉ khi K+= R Ta có thuật tóan tìm khóa của lược đồ như sau : Xuất phát từ một siêu khóa K , lọai dần các thuộc tính trong K, bảo tòan bbất biến K+=R Thuật toán: Đầu vào: LĐQH p = (R,F) Đầu ra: khóa K ⊆ R thỏa mãn: - K+ =R. - "A ∈ R: (K\A)+ ¹ R. Phương pháp: := R {K là khóa} or mỗi A Î R do F (K\A)+ Ví dụ: Cho quan hệ r trên lược đồ quan hệ R=(A,B,C,D) và tập phụ thuộc hàm F: F= {AB C, C A, B D}. Tìm khóa của lược đồ quan hệ R. Ta có: + giả sử K là khóa, ta có: K= ABCD + Loại A trong K ta được K = BCD (1), nếu loại C trong K ta được K = ABD (2) + Loại D trong K ở (1) ta được K = BC là khóa + Loại D trong K (2) ta được K = AB là khóa. +Vậy khóa của lược đồ quan hệ: K ={BC, AB} Nhược điểm: +Bắt đầu tập khoía với số lượng thuộc tính lớn +Xét tất cả thuộc tínhtrong R(A ∈ X). Nhận xét: +Những thuộc tính nào xuất hiện duy nhất ở phía phải tập phụ thuộc hàm ₣thì tham gia vào khóa. +Những thuộc tính xuất hiện duy nhất ở phía trái thì chắc chắn tham gia vào khóa. +Những thuộc tính không xuất hiện trong các phụ thuộc hàm chắc chắn phải tham gia vào khóa +Những thuộc tính vuầ nằm ở vế phải là thuộc tính có khả năng tham gia vào khóa hoặc không tham gia vào khóa.
Từ nhận xét trên ta có: Cho Gọi T= ∪ X (Tập những thuộc tính xuất hiệnở vế trái trong trong PTH F) X →Y ∈ F P = ∪ Y (tập những thuộc tĩnhuất hiện ở vế trảitong PTH F). X→Y ∈ F Nếu k là khóa thì: (R\P) ⊆ K ⊆ (R\P) ∪ (T ∩ P) a) Cải tiến: T:= ∪ X X→Y ∈ F P := ∪Y X →Y ∈ F K:=(R\P) ∪ (T ∩ P) For mỗi thuộc tínhA ∈ T ∩ Pdo If (K\A)+=R then K=K\A Return k; Như vậy trong cả 2 phương pháp trên ta có kết luận. Bắt đầu với một siêu khóathid ta có thể tồn được khóa + Nếu (R\P)+ =R thì được đồ quan hệ R chỉ có duy nhất một khkóa + Nếu T ∩ P= Æ thì trên lược đồ quan hệ Rchỉ có duy nhất 1 khóalà R f. Dùng đồ thị của tập phụ thuộc hàm để xác định khóa của một lược đồ quan hệ 1. Đồ thị của một tập phụ thuộc hàm Ta có thể biểu diển một phụ thuộc hàm bằng một đồ thị như sau: A B - Phụ thuộc hà m A® B A C - Phụ thuộc hàm AB ® C B A -Phụ thuộc hàm ABC ® D B D
C B - Hàm phụ thuộc A ® BC A C Đồ thị của một tập phụ thuộc hàm:Cho một tập phụ thuộc hàm F,ta có thể biểu diển thành một đồ thịvới qui tắc: Mỗi một thuộc tính là một đỉnh trong đồ thị. Ví dụ: Cho một tập phụ thuộc hàm F={A ®B, AB ®C, B®D,CD®E} ta biểu diễn thành đồ thị sau: A C E B D Trong đồ thị, ta định nghĩa : Đỉnh gốc: là đỉnh mà chỉ có điểm đi của mủi tên. Ví dụ: Đỉnh A của đồ thị trên Đỉnh ngọn: là đỉnh chỉ có điểm đến của mũi tên. Vi dụ: Đỉnh E của đồ thị trên Đỉnh trung gian: là đình vừa có điểm đến, vừa có điểm đi của mũi tên. Ví dụ: Đỉnh B, C, D của đồ thị trên. 2. Dùng đồ thị của một tập phụ thuộc hàm để xác định khóa của lược đồ quan hệ: Cho lược đồ quan hệ r (R) và tập phụ thuộc hàm F trên R. Thuật giải dùng đồ thị để tìm phụ thuộc hàm F trên R - Các đỉnh gốc của đồ thị để tìm khóa lược đồ quan hệ. - Các đỉnh gốc của đồ thị là khóa của lược - K là tập các đỉnh gốc: Nếu K+F= R thì K là khóa. Ngược lại, ta thêm lần lượt vào K một số thuộc tính là đỉnh trung gian cho đến khi K+F = R. Trong đồ thị của ví dụ trên, A là khóa của R. g. Phủ của tập phụ thuộc hàm Cho tập phụ thuộc hàm F và G trên tập thuộc tính R. Định nghĩa 1 - Ta nói F suy ra G, ký hiệu F|= G, nếu và chỉ nếu G+ Í F+. - Ta nói F và G tương đương, ký hiệu F º G, nếu và chỉ nếu F|=G và G|=F, khi đó ta nói G là một phủ của F và ngược lại. Định nghĩa 2 Tập phụ thuộc hàm F gọi là tối thiểu nếu: 1. "f ÎF Þ X ® A (vế phải chỉ có 1 thuộc tính)
2. Không tồn tại f= X ® A Î F và Z Ì X thỏa F+= (F\{F} È {Z A})+ 3. Không tồn tại f = X ® A Î F sao cho F+ = (F\{f}+ Định nghĩa 3: Tập phụ thuộc hàm F, tập phụ thuộc hàm G gọi là phủ tối thiểu của F khi và chỉ khi G là một phủ của F và G là tối thiểu. Ví dụ: Xét lược đồ quan hệ R(A,B,C,D,E) và tập phụ thuộc hàm: F={AB ® C, C ® A, CB ® DE, AB ® DE} Ta thấy CB ® DE là thừa. Xét F’ ={AB®C, C® A, AB ® DE} F º F’/ F’ |= CB ® DE (vì CB+F = CBADE) · Mọi tập phụ thuộc hàm đều tương đương với một tập thuộc hàm mà vế phải của các phụ thuộc hàm chỉ có duy nhất một thuộc tính. · Hiển nhiên nhận xét trên là đúng: Nếu trong F có một phụ thuộc hàm · X ® A1A2....An thay bởi X ® A1, X ® A2, X ® An. · Cho 1 tập phụ thuộc hàm F, phụ thuộc hàm X ® A Î F là thừa nếu: + Một tập phụ thuộc hàm được gọi là không dư thừa nếu không có bất cứ một phụ thuộc hàm nào là thừa. + Cho một tập hợp thuộc hàm F, X "A Î F. X ® A là thừa A Î X+F\{A ®A} Phương pháp để loại các thuộc tính dư thừa trong F: For mỗi X ® A Î F do IF A Î X+F\{A ®A} then F:=F\{X"A}; RETURN F. Ÿ Cho một tập phụ thuộc hàm F, X ® A Î F, B Î X, B được gọi là thừa nếu: F\ {A ® A} È {X\B ®A} º F Ví dụ : Xét tập phụ thuộc hàm F F={AB"C, A"D, D"B} Xét AB ® C Þ B là thừa Do F’= {A ® C, A ® D, D ® B} º F Ÿ Cho tập phụ thuộc hàm F, X ® A Î F, B Î X là thừa Û A Î (A|B)+ Phương pháp loại các phụ thuộc hàm dư thừa: For mỗi X ® A Î F do For mỗi B ÎX do IF AÎ(X\B)+F then F=F\{X ® A} È {X\B ® A} Ÿ Một tập phụ thuộc hàm được gọi là cực tiểu nếu thỏa mãn các điều kiện sau: (1) Mỗi một phụ thuộc hàm chỉ có duy nhất 1 thuộc tính ở vế phải . (2) Không tồn tại bất cứ 1 phụ thuộc hàm nào mà vế trái có những thuộc tính thừa.
(3) Không tồn tại bất cứ 1 phụ thuộc hàm nào thừa. Cho một tập phụ thuộc hàm F nếu G là tập phụ thuộc hàm tương đương với F. Mà G là cực tiểu thì ta nói G là phủ cực tiểu của F. · Phương pháp để tìm phủ cực tiiểu của R. Bước 1: Làm cho F thỏa mãn điều kiện (1) Bước 2: Làm cho F thỏa mãn điều kiện (2) Bước 3: Làm cho F thỏa mãn điều kiện (3) II. TÁCH MỘT QUAN HỆ Như ta đã biết mô hình quan hệ do cold đề xuất năm 1970, có những ưu điểm vượt trội so với các mô hình dữ liệu trước đó: - Đơn giản: các dữ liệu được biểu diễn dưới dang duy nhất, là các bảng giá trị, khá tự nhiên và dễ hiểu đối vớimọi người sử dụng. - Chặt chẽ: Các khái niệm được hình thức hóa cao ,cho phép sử dụng các công cụ Toán học,các thuật toán. - Trựu tượng hóa cao: mô hình chỉ ở mức quan niệm, nghĩa là độc lập với các mức vật lý, với sự cài đặt, với thiết bị. Nhờ đó mà làm tăng thêm tính độc lập giữa dữ liệu và chương trình. - Cung cấp các ngôn ngữ truy cập dữ liệu ở mức cao (như SQL,….): nhờ đó dễ sử dụng và trở thành chuẩn. Tuy vậy, khi cần thiết kế một dữ liệu quan hệ thường đòi hỏi phải các lượt đồ quan hệ. Việc chọn tập các lược đồ này có thể tốt hơn hay xấu hơn tập các lược đồ khác dựa trên một số tiêu chuẩn nào đó. Trọng tâm của việc thiết kế các lược đồ cơ sở dư liệu là ta tổ chức bao nhiêu lược đồ và mỗi lược đồ có nhưng thuộc tính nào để đảm bảo các tinh chất sau : Không trùng lặp dữ liệu liệu: Trong một quan hệ, giá trị của một thuộc tính nào đó chiếm dung lượng bộ nhớ lớn không được lặp lại nhiều lần. II.1.Tách một lược quan hệ Phép tách một lược đồ quan hệ R=A1, A2,……….An là việc thay thế lược đồ quan hệ R bằng một tập lược đồ R1,R2,………Rn trong đó Ri ⊆ R,i=1…n. R1 ∪ R2 ∪ R3 ∪ Rn và Ri ≠ RJ với i ≠ j. Ví dụ: Với lược đồ quan hệ :r (M_HANG,MAKH,TENKH,DCKH,SOLUONG,DONGIA)tacó phụ thuộchàm : r1(M_HANG,MAKH,SOLUONG,DONGIA),r2(MAKH,TENKH,DCKH) Việc phân rã một lược đồ phụ thuộc hàm xác định trên lược đồ ấy . a. Phép tắc bảo toàn thông tin Định nghĩa 1: Cho một lược đồ quan hệ Rvà tập phụ thuộc hàm F trênR .Phép tách của lược đồ quan hệ R là việc thay bởi một tập các lược đồ R1, R2, ..., Rk sao cho R1 È...È Rk = R
Kí hiệu: r(R1,R2, R3,....,Rk) Định nghĩa 2: Cho quan hệ r trên lược đồ quan hệ R và F là tập phụ thuộc hàm xác định trên R, r(R1,R2, R3,....,Rk). Ta nói rằng r là một phép tách bảo toàn thông tin nếu " quan hệ r(R) ta có: r= PR1(r) wv PR2(r) wv .....wv PRk(r) Kí hiệu: mr(r) Ta có: mr(r) Ê r. b. Kiểm tra phép tách bảo toàn thông tin: Liệu một phép tính lượt đò r thành các lươc đò con r1,r2,….rn dựa trênbảo toàn thông tin hay không, được kiểm tra qua phương pháp sau đay gọi là tableau. Thuật toán: Kiểm tra phép tách bảo toàn thong tin . Vào: R, F, r =(R1,R2,….Rk);R=A1,A2,….,An Ra : Kết luận r có bảo tyòan thông tin (theo F). Phương Pháp Bước 1: Xây dựng bảng có k dòng và cột - Mỗi một dòng tương ứng với một lượt đồ tách. - Mỗi một cột tương ứng với 1 thuộc tính của R. A1 A2 ........... An R1 R2 . . Tiến hành khởi tạo giá trị các ô: aj nếu Aj ∈ Ri Ô tại vị trí (dòng i,cột j)= bjj nếu Aj Î Ri Bước 2: Biến đổi bảng (lặp ) Xét lần lượt từng phụ thuộc hàm X→Y ∈ F, tìm trong bảng từng cặp hai dòng bao gồm bằng nhau trên X. Nếu tồn tại hai dòng như vậy thì biến đối các giá trị phía Y sao cho 2 dòng này cũng bằng nhau ở Y theo nguyên tắc sau: + Nếu 1 trong 2 ô nhận giá trị là a thì ô còn lại bằng a. + Nếu trong trường hợp cả 2 ô nhận giá trị là b thì cho ô này bằng ô kia. Điều kiện dừng: Qúa trình này lặp đi lặp lại cho đén khi ở trong bảng xuất hiện 1 dong toàn là a sau khi xét hết 1 lượt đồ phụ thuộc hàm mà không có sự thay đổi trên bảng. Kết luận: + Nếu trong bảng có một dòng toàn là a thì ta nói phép tách bảo toàn thông tin
và ngược lại ta nói phép tách không bảo toàn thông tin . Ví dụ: Cho lược đồ quan hệ R(A,B,C,D,E,F,G) thỏa mãn phụ thuộc hàm: F={A ®BC, AD ® EF, D ® G} 1) Kiểm tra phép tách r ={ABC, AEF, ADG} có bảo toàn thông tin không ? Ta có: A B C D E F G a1 a2 a3 b14 b15 b16 b17 ABC a1 b22 b23 b24 a5 a6 b27 AEF a1 b32 b33 a4 b35 b36 a7 ADG Xét A ® BC (2,2) = a2 (3,2) = a2 (2,3) = a3 (3,3) = a3 Ta được bảng sau: A B C D E F G a1 a2 a3 b14 b15 b16 b17 ABC a1 a2 a3 b24 a5 a6 b27 AEF a1 a2 a3 a4 b35 b36 a7 ADG Xét AD ® EF (không thay đổi) D ® F(không thay đổi) A ® BC (không thay đổi) AD ® EF (không thay đổi) D ® G (không thay đổi) 2) Kiểm tra phép tách r ={ABCE, ADEF,DG} có bảo toàn thông tin không? Ta có: A B C D E F G a1 a2 a3 b14 a5 b16 b17 ABCE a1 b22 b23 a4 a5 a6 b27 ADEF b31 b32 b33 a4 b35 b36 a7 DG Xét A ® BC (2,2) = a2 , (2,3)= a3 AD ® EF (không thay đổi) D®G (2,7) = a7 Ta có bảng sau:
A B C D E F G a1 a2 a3 b14 a5 b16 b17 ABCE a1 a2 a3 a4 a5 a6 a7 ADEF b31 b32 b33 a4 b35 b36 a7 DG Vậy phép tách bảo toàn thông tin. Định lý: Cho phép tách ρ(R1,R2)của R là bảo toàn thông tin khi và chỉ khi F|= (R1 Ç R2)→R1\R2. Ví dụ: R(A,B,C,D,E) F= {A → B, AC→DE r= (AB, ACDE) AB Ç ACDE ® AB\ ACDE II.2 CHUẨN HÓA LƯỢC ĐỒ QUAN HỆ Khi thiết kế lược đồ quan hệ phải tuân theo một số nguyên tắc để khi thao tác trên dữ liệu không dẫn đến sự dị thường dữ liệu,Công việc thiêt kế dữ liệu theo một dạng chuẩn nào đógọi là chuẩn hóa dữ liệu. Lý thuyết cơ sở dữ liệu nay đã đưa ra nhiều dạng chuẩn,tuy nhiên xét thấy rằngdữ liệu trong thực tế không đến nỗi quá phức tạp,trong quá trình này chúng tôi chỉ đưa raba dạng chuẩn nhất là dạng1, dạng2, dangj 3,ngoài ra còn có dang chuẩn Boyce codd(BCCF). a.Các dạng chuẩn trong lược đồ quan hệ Do việc cập nhật dử liệu (qua phép chèn,loại bỏ , sửa đổi)gây nên những dị thường, cho nên các quan hệ nhất thiết phải được phổ biến đổi thành dạng phù hợp,quá trình đó gọi là quá trình chuẩn hóa.Quan hệ được chuẩn hóalà quan hệ trong đó mỗi miền của một thuợc tính chỉ chứa những giá trị trong quan hệ cũng nguyên tố. Quan hệ có chứa các miền trị là những nguyên tố gọi là quan hệ không chuẩn hóa.Một quan hệ được chuẩn hóa có thể tách thành một hoăc nhiều quan hệ chuẩn hóa khác và không làm mất thông tin .Giới hạn trong việc xem xét các lược đồ quan hệ với các phụ thuộchàm,ta định nghĩa dưới đây các dạng chuẩn 1NF,2NF,3NF.Ư b. Một số định nghĩa Thuộc tính khóa:Một thuọc tính trong lược đò quan hệ r(R)được gọi là thuộc tính khóa nếu nó là một thành phần của khóa nào đó của r.Ngược lại được gọi là thược tính không khóa. Phụ thuộc hàm đầy đủ: Cho lược đồ quan hệ r(R), R là tập thuộc tính, X và Y là hai tập con khác nhau của R, Y là phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ tập hợp con thực sự nào của X.
Phụ thuộc bắc cầu: Cho lược đồ quan hệ r(R), R là tập thuộc tính, X là tập con của R, A là một thuộc tính thuộc R, A được gọi là phụ thuộc hàm bắc cầu vào X trên r nếu tồn tại một tập con Y của R sao cho X ®Y, Y ® A nhưng Y ® X với A Ï XY. c. Dạng chuẩn 1 (Frist Normal Form 1NF) Một lược đồ quan hệ 1NF nếu mọi thuộc tính của lược đồ là nguyên tố. Ví dụ: Kiểu record ® không nguyên tố. + Cho lược đồ quan hệ R(B,O,I, S, Q,D) và tập phụ thuộc hàm: F={S ® D, I ® B, IS ®Q, B ® O} · Dạng chuẩn 1 được xem như là một qui ước trên lược đồ quan hệ và tức nhiên ta thừa nhận lược đồ luôn có dạng chuẩn 1. d. Dạng chuẩn 2 (Second Normal Form 3 NF) Lược đồ quan hệ R được gọi là 2 NF nếu X ® A trên R(A X) thì + Hoặc là A là thuộc tính khóa. + Hoặc X không là phải là tập con thật sự của khóa. Ví dụ: Cho lược đồ quan hệ R(A,B, C, D) thỏa mãn phụ thuộc hàm: F={A ® BCD, C ® D} e. Dạng chuẩn 3 (Third Normal Form 3NF) Lược đồ quan hệ R được gọi là 3NF nếu X ® A trên R (A X) thì + Hoặc A là thuộc tính khóa + Hoặc X là siêu khóa Ví dụ: Cho lược đồ quan hệ A(A,B,C,D) thỏa mãn phụ thuộc hàm F={AB ® CD, D ® A} f. Dạng chuẩn BCNF (BOYCE- CODD) Lược đồ quan hệ R được gọi là BCNF nếu X ® A trên R (A X) thì + X là siêu khóa Ví dụ: Cho lược đồ quan hệ R(A, B,C, D) thỏa mãn phụ thuộc hàm F={ AB ® C, BC ®A} g. Dạng chuẩn một lược đồ cơ sở dữ liệu: Một lược đồ cơ sở dữ liệu (một tập hợp nhiều lược đồ quan hệ) gọi là ở dạng chuẩn i ( i= 1,2,3..) nếu mọi lược đồ con của nó đều ở dạng chuẩn i. h. Chuẩn hóa một lược đồ cơ sở dữ liệu Trong những tiết trước ta đã địng nghĩa phép tách một lược đồ quan hệ thanh nhiều lược đồ con bảo toàn thông tin .Sau đây ,ta xét một cách tách mộtlược đồ quan hệ thành nhiều lươc đồ con bảo toàn phụ thuộc hàm dạng chuẩn 3NF. Thuật toán: Phép tách bảo toàn phụ thuộc hàm thành 3NF Vào: R,F Ra: ρ = {R1, R 2,...., RK }RI là 3 NT ρ là bảo toàn phụ thuộc hàm Phương pháp: Bước 1: - Tìm phủ cực tiểu G của F -ρ =φ
Bước2: -Nếu trong R có thuộc tính không xuất hiện trong PTH thì đưa các thuộc tinh này thành 1 lược đồ trong ρ , loại các thuộc tính này khỏi R Bước3: Nếu tồn tại một phụ thuộc liên quan đến tất cả các thuộc tính thì: ρ = ρ ∪ {R }, kết thúc Ngược lại qua bước 4; Bước 4: Với mỗi các phụ thuộc hàm X ® A, X ®A2,....., X ®Ak thì tạo thành 1 lược đồ XA1A2.....Ak. Bước 5: Nếu tồn tại Ri, Rj Î r mà Ri Î Rj thì loại Ri khỏi r Ví dụ: R(A, B,C, D,E,F,G), F={AB ® C, AB ® D, C ®B, CD ® E} - F: đã là phủ cực tiểu - F,G không có trong PTH Þ r= (F,G) Xét R(A,B,C,D,E) r = (ABCD, CB, CDE). Vậy r = (FG, ABCD, CDE) · Phép tách tìm được theo phương pháp trên luôn bảo toàn PTH tuy nhiên có thể không bảo toàn thông tin. Trong trường hợp này ta bổ sung thêm vào phép tách lược đồ một khóa K, với K là một khóa bất kỳ của lược đồ quan hệ R. Vậy r= r È {k}