Bài giảng Cơ sở dữ liệu - Chương 6: Chuẩn hóa cơ sở dữ liệu

Chia sẻ: Nguyễn Thị Hiền Phúc | Ngày: | Loại File: PPTX | Số trang:35

Thêm vào BST

Báo xấu

64
lượt xem 7
download

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

Bài giảng cung cấp cho người học các kiến thức: Chuẩn hóa cơ sở dữ liệu. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu - Chương 6: Chuẩn hóa cơ sở dữ liệu

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG HỌC PHẦN CƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 6 CHUẨN HÓA CƠ SỞ DỮ LIỆU Giảng viên: ThS. Nguyễn Vương Thịnh B ộ m ô n : H ệ t h ốn g t h ô n g t in Hải Phòng, 2016
Th ô n g t in v ề g i ản g v iê n Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn Website http://scholar.vimaru.edu.vn/thinhnv 2
Th ô n g t in v ề h ọc p h ần Tên học phần Cơ sở dữ liệu và quản trị cơ sở dữ liệu Tên tiếng Anh Database and Database Management Mã học phần 17425 Số tín chỉ 04 tín chỉ (LT: 45 tiết, TH: 30 tiết) Bộ môn phụ trách Hệ thống thông tin PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨ v UN g h e g i ản g , t h ảo lu ận , t ra o đ ổi v ới g i ản g v iê n t rê n l ớp . PH v TựN ƯƠ nG P HÁP g h iê n c ứ ĐuÁN t àH GIÁ i li ệu v à là m b à i t ập ở n h à . v S V p h ải t h a m d ự ít n h ất 7 5 % t h ời g ia n . v Có 0 2 b à i k i ểm t ra v i ết g i ữa h ọc p h ần ( X2 = ( L1 + L2 ) /2 ) , 0 1 b à i k i ểm t ra t h ực h à n h ( X3 ) . Đ i ểm q u á t rìn h X = ( X2 + X3 ) /2 . 3 v Th i k ết t h ú c h ọc p h ần b ằn g h ìn h t h ức t r ắc n g h i ệm
Tài liệu tham khảo 1. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004. 2. Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu, Nhà xuất bản Giáo dục Việt Nam, 2007. 3. Nguyễn Kim Anh, N g u y ê n lý c ủa c á c h ệ C ơ s ở d ữ li ệu , Nhà xuất bản Đại học Quốc gia Hà Nội, 2004. 4
Tà i li ệu t h a m k h ảo 5
CHUẨN HÓA CƠ SỞ DỮ LIỆU 6.1. TẠI SAO PHẢI CHUẨN HÓA CƠ SỞ DỮ LIỆU? 6.2. CÁC DẠNG CHUẨN HÓA CỦA CƠ SỞ DỮ LIỆU 6.3. CÁC PHÉP TÁCH BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM 6.4. PHÉP TÁCH VỀ DẠNG CHUẨN BOYCE CODD (BCNF) BẢO TOÀN THÔNG TIN 6.5. PHÉP TÁCH VỀ DẠNG CHUẨN 3 (3NF) BẢO TOÀN THÔNG TIN VÀ BẢO TOÀN PHỤ THUỘC HÀM 6
6.1. TẠI SAO PHẢI CHUẤN HÓA CƠ SỞ DỮ LIỆU? Ví dụ 6.1: Xét quan hệ trên lược đồ quan hệ Kết_Quả_Học_Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm) Mã SV Họ và tên Mã HP Tên HP Điểm HHA001 Nguyễn Văn An HP01 Toán rời rạc 6.5 HHA002 Nguyễn Thu Ân HP02 Cơ sở dữ liệu 7.0 HHA003 Nguyễn Văn Bình HP01 Toán rời rạc 7.5 HHA001 Nguyễn Văn An HP03 Tin học đại cương 8.0 HHA002 Nguyễn Thu Ân HP01 Toán rời rạc 6.0 HHA001 Nguyễn Văn An HP02 Cơ sở dữ liệu 7.0 NHƯỢC ĐIỂM 1. Dư thừa dữ liệu: Cùng 01 sinh viên nhưng không chỉ có mã sinh viên mà họ tên sinh viên cũng bị lặp đi lặp lại nhiều lần ở các vị trí khác nhau. Tương tự, cùng một học phần thì không chỉ có mã học phần mà tên học phần cũng bị lặp lại ở những vị trí khác nhau. 7
2 . K h ó k h ă n k h i c ập n h ật d ữ li ệu : q Th ê m : Ta k h ô n g t h ể t h ê m t ê n m ột h ọc p h ần m ới v à o q u a n h ệ n ếu h ọc p h ần đ ó c h ưa đ ược s in h v iê n n à o đ ă n g k ý. Tươn g t ự t a k h ô n g t h ể t h ê m t h ô n g t in v ề m ột s in h v iê n m ới n ếu s in h v iê n đ ó c h ưa đ ă n g k ý m ột h ọc p h ần n à o . q Xó a : N ếu t a x ó a t h ô n g t in v ề h ọc p h ần "To á n r ời r ạc " t h ì c ũ n g s ẽ m ất lu ô n t h ô n g t in c ủa s in h v iê n "N g u y ễn Vă n Bìn h " c ó m ã s in h v iê n là "HHA0 0 3 " v ì c h ỉ c ó m ột b ản g h i d u y n h ất c ó c h ứa t h ô n g t in v ề s in h v iê n n à y. q S ửa : Gi ả s ử c ó n h i ều s in h v iê n đ ă n g k ý h ọc m ô n "To á n r ời r ạc ", k h i đ ó s ẽ c ó n h i ều b ản g h i c ó liê n q u a n đ ến "To á n r ời r ạc ". N ếu t a m u ốn đ ổi t ê n m ô n "To á n r ời r ạc " t h à n h "To á n t in " t h ì t a s ẽ p h ải c ập n h ật t ê n m ô n ở n h i ều v ị t rí t ươn g ứn g , g â y m ất n h i ều t h ời g ia n v à d ễ x ảy ra s a i s ó t . 8 3 . K h ô n g n h ất q u á n d ữ li ệu : Là h ệ q u ả c ủa 0 2 đ i ều t rê n .
6.2. CÁC DẠNG CHUẨN HÓA CƠ SỞ DỮ LIỆU 6.2.1. DẠNG CHUẨN 1 (1NF) Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 1 (1NF) nếu như toàn bộ các thuộc tính đều mang giá trị đơn và nguyên tố. Ví d ụ 6 . 2 : Các lược đồ quan hệ sau đây k h ô n g thỏa mãn chuẩn 1: Mã NV Họ tên Chuyên Môn Ngoại Ngữ NV01 Nguyễn Văn An Kỹ sư xây dựng Tiếng Anh Tiếng Anh NV02 Nguyễn Thị Ánh Kiến trúc sư Tiếng Pháp Tiếng Anh NV03 Lê Văn Bình Cử nhân Kinh tế Tiếng Trung Thuộc tính Mã hàng hóa Số lượng Kích thước Khối lượng Màu sắc MH01 40 40 100 Đỏ MH02 50 65 250 Vàng MH03 120 45 130 Xanh 9 MH04 123 56 300 Tím
6.2.2. DẠNG CHUẨN 2 (2NF) Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 2 (2NF) nếu nó ở dạng chuẩn 1 và mỗi thuộc tính không khóa (nếu có) đều phải phụ thuộc hàm đầy đủ vào một khóa nào đó của lược đồ quan hệ. Lưu ý một số khái niệm: v Thuộc tính không khóa (n o n p rim e a t t rib u t e ) là t h u ộc t ín h k h ô n g n ằm t ro n g bất kỳ một khóa nào của lược đồ quan hệ. v Y được gọi là phụ thuộc hàm đầy đủ vào X nếu X → Y và không tồn tại X’⊆ X sao cho X’→Y (nói cách khác: phụ thuộc hàm đầy đủ có nghĩa là Y chỉ phụ thuộc hàm vào X chứ không phụ thuộc vào một tập con nào đó của X). Ví dụ 6.2: Xét lược đồ quan hệ Kết Quả Học Phần(Mã SV, Họ và tên, Mã HP, Tên HP, Điểm) Có tập phụ thuộc hàm: F = {Mã SV → Họ và tên, Mã HP → Tên HP, {Mã SV, Mã HP} → Điểm} Khóa K = {Mã SV, Mã HP} Họ và tên phụ thuộc hàm vào Mã SV là 1 phần của khóa Tên HP phụ thuộc hàm vào Mã HP là 1 phần của khóa 10 KHÔNG THỎA MÃN CHUẨN 2
Hệ quả: q Nếu một lược đồ quan hệ đạt chuẩn 1 và tập thuộc tính không khóa của nó là tập rỗng thì đương nhiên lược đồ quan hệ đó đạt chuẩn 2. q Nếu tất cả các khóa của lược đồ quan hệ chỉ gồm một thuộc tính thì lược đồ quan hệ đó đạt chuẩn 2. THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN 2 Input: Lược đồ quan hệ R(Ω ) và tập phụ thuộc hàm F Output: Khẳng định R(Ω ) có đạt chuẩn 2 hay không. q Bước 1: Tìm tất cả các khóa của lược đồ quan hệ và xác định các thuộc tính không khóa. q Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả các tập con thật sự S của K. q Bước 3: Nếu tồn tại một bao đóng S+ nào đó chứa thuộc tính không khóa thì R(Ω ) không đạt chuẩn 2. Ngược lại thì đạt chuẩn 2. Lưu ý: Đối với những bài toán đơn giản, người ta thường xuất phát từ định nghĩa của dạng chuẩn 2 để xác định xem một lược đồ quan hệ có thỏa mãn dạng chuẩn 11 2 hay không thay vì phải sử dụng thuật toán nêu trên.
Ví d ụ 6 . 3 : Ch o l ược đ ồ q u a n h ệ R( A, B, C, D ) v à t ập p h ụ t h u ộc h à m : F = { AB → C, B → D , BC → A} H ỏi l ược đ ồ q u a n h ệ n à y c ó đ ạt c h u ẩn 2 h a y k h ô n g ? G i ải Đ ầu t iê n t a t ìm t ất c ả c á c k h ó a c ủa l ược đ ồ q u a n h ệ: TN = B, TG = AC Xi Si = TN ∪ Xi (TN ∪ Xi)+ Siêu khóa Khóa ⍉ B BD A AB Ω AB AB C BC Ω BC BC AC ABC Ω ABC Ta c ó h a i k h ó a K1 = AB, K2 = BC. Th u ộc t ín h k h ô n g k h ó a là D . Ta t h ấy B →D t ro n g k h i B ⊂ K1 . V ậy t h u ộc t ín h k h ô n g k h ó a D p h ụ t h u ộc h à m v à o m ột p h ần c ủa k h ó a n ê n l ược đ ồ q u a n h ệ k h ô n g t h ỏa m ã n c h u ẩn 2 . 12
Ví d ụ 6 . 4 : Ch o l ược đ ồ q u a n h ệ R( A, B, C, D ) v à t ập p h ụ t h u ộc hàm F = { B → D , A → C, C → ABD } . H ỏi l ược đ ồ q u a n h ệ n à y c ó đ ạt c h u ẩn 2 h a y k h ô n g ? Gi ải Đ ầu t iê n t a t ìm t ất c ả c á c k h ó a c ủa l ược đ ồ q u a n h ệ: TN = ? , TG = ABC Xi Si = TN ∪ Xi (TN ∪ Xi)+ Siêu khóa Khóa ⍉ ⍉ A A Ω A A B B BD C C Ω C C AB AB Ω AB BC BC Ω BC AC AC Ω AC ABC ABC Ω ABC Ta c ó h a i k h ó a K1 = A, K2 = C. Tất c ả c á c k h ó a c ủa l ược đ ồ q u a n h ệ đ ều c ó m ột t h u ộc t ín h n ê n t h e o h ệ q u ả 2 , l ược đ ồ 13 q u a n h ệ đ ạt c h u ẩn 2 .
6.2.3. DẠNG CHUẨN 3 (3NF) A. Định nghĩa cổ điển Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu nó đã ở dạng chuẩn 2 và không tồn tại thuộc tính không khóa phụ thuộc hàm bắc cầu vào khóa chính của lược đồ quan hệ. Lưu ý: Một thuộc tính A được gọi là phụ thuộc hàm bắc cầu vào tập thuộc tính X nếu tồn tại tập thuộc tính Y để cả ba điều sau được thỏa mãn: 1. X → Y, Y → A 2. Y → X ∉ F+ 3. A ∉ XY B. Định nghĩa tổng quát Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn 3 (3NF) nếu với mọi phụ thuộc hàm X→A ∈ F+ (A ∉ X) ta đều có: .Hoặc X là siêu khóa. .Hoặc A là thuộc tính khóa. 14
Ví dụ 6.5: Xé t l ược đ ồ q u a n h ệ: S in h Vie n ( Ma S V, Ho Te n , Ma Lo p , Te n Lo p ) MaSV HoTen MaLop TenLop HHA001 Nguyễn Văn An L01 CNT50-ĐH1 HHA002 Nguyễn Văn Án L02 ĐKT51-ĐH2 HHA003 Nguyễn Văn Ân L01 CNT50-ĐH1 HHA004 Nguyễn Văn Bình L02 ĐKT51-ĐH2 HHA005 Nguyễn Văn Bông L01 CNT50-ĐH1 HHA006 Nguyễn Văn Cường L03 CTT51-ĐH • Tập p h ụ t h u ộc h à m : F = { Ma Lo p → Te n Lo p ; Ma S V → Ho Te n , Ma Lo p } • Kh ó a c h ín h K = { Ma S V} Lược đ ồ n à y không thỏa mãn chuẩn 3 v ì c ó t h u ộc t ín h k h ô n g k h ó a là Te n Lo p p h ụ t h u ộc h à m b ắc c ầu v à o k h ó a c h ín h Ma S V n h ư s au: 15 Ma S V → Ma Lo p v à Ma Lo p → Te n Lo p .
H ệ q u ả: • N ếu m ột l ược đ ồ q u a n h ệ đ ạt c h u ẩn 3 t h ì đ ươn g n h iê n đ ạt c h u ẩn 2 . • N ếu m ột l ược đ ồ q u a n h ệ k h ô n g c ó t h u ộc t ín h k h ô n g k hẬóT TOÁN KI THU a t h ì đ ạt c h u ẩn 3 . ỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN ỂM TRA M 3 Input: Lược đồ quan hệ R(Ω ) và tập phụ thuộc hàm F. Output: Khẳng định R(Ω ) có đạt chuẩn 2 hay không. Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω ). Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã). 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ì lược đồ quan hệ đạt chuẩn 3. Ngược lại 16
Ví d ụ 6 . 6 : Ch o l ược đ ồ q u a n h ệ R( A, B, C, D ) v à t ập p h ụ t h u ộc hàm : F = { AB → C, D → B, C → ABD } H ỏi l ược đ ồ q u a n h ệ n à y c ó đ ạt c h u ẩn 3 h a y k h ô n g ? Gi ải B ước 1 : S a u k h i á p d ụn g t h u ật t o á n t ìm t ất c ả c á c k h ó a , t a t ìm đ ược 3 k h ó a : K1 = AB, K2 = AD , K3 = C. N h ư v ậy, c á c t h u ộc t ín h k h ó a là : A, B, C, D . B ước 2 : Xâ y d ựn g t ập p h ụ t h u ộc h à m F’ t ươn g đ ươn g v ới F c ó v ế p h ải m ột t h u ộc t ín h n h ờ lu ật p h â n rã : F’ = { AB → C, D → B, C → A, C → B, C → D } B ước 3 : D u y ệt c á c p h ụ t h u ộc h à m t ro n g F’, t a t h ấy t ất c ả c á c p h ụ t h u ộc h à m đ ều c ó v ế p h ải là t h u ộc t ín h k h ó a n ê n 17 l ược đ ồ q u a n h ệ đ ạt c h u ẩn 3 .
Ví d ụ 6 . 7 : Ch o l ược đ ồ q u a n h ệ R( A, B, C, D ) v à t ập p h ụ t h u ộc hàm : F = { B → D , A → C, C → ABD } H ỏi l ược đ ồ q u a n h ệ n à y c ó đ ạt c h u ẩn 3 h a y k h ô n g ? Gi ải B ước 1 : S a u k h i á p d ụn g t h u ật t o á n t ìm t ất c ả c á c k h ó a , t a t ìm đ ược 2 k h ó a : K1 = A v à K2 = C. Cá c t h u ộc t ín h k h ó a là : A, C. B ước 2 : Xâ y d ựn g t ập p h ụ t h u ộc h à m F’ t ươn g đ ươn g v ới F c ó v ế p h ải m ột t h u ộc t ín h n h ờ lu ật p h â n rã : F’ = { B → D , A → C, C → A, C → B, C → D } B ước 3 : D u y ệt c á c p h ụ t h u ộc h à m t ro n g F’ t a t h ấy p h ụ t h u ộc h à m B → D c ó v ế t rá i k h ô n g p h ải là s iê u k h ó a , v ế 18 p h ải c ũ n g k h ô n g p h ải là t h u ộc t ín h k h ó a . V ậy l ược đ ồ q u a n
6.2.4. DẠNG CHUẨN BOYCE CODD (BCNF) Một lược đồ quan hệ R(Ω) được gọi là ở dạng chuẩn Boyce Codd (BCNF) nếu với mọi phụ thuộc hàm X → A ∈ F+ (A ∉ X) ta đều có X là siêu khóa. G ần g i ốn g đ ịn h n g h ĩa t ổn g q u á t c ủa c h u ẩn 3 , n h ưn g c h ặt c h ẽ h ơn ở c h ỗ k h ô n g c h ấp n h ận t r ườn g h ợp A là t h u ộc t ín h k h ó a . H ệ q u ả: N ếu m ột l ược đ ồ q u a n h ệ đ ạt c h u ẩn Bo y c e Co d d t h ì đ ươn g n h iê n đ ạt c h u ẩn 3 . 19
THUẬT TOÁN KIỂM TRA MỘT LƯỢC ĐỒ QUAN HỆ CÓ ĐẠT CHUẨN BOYCE CODD Input: Lược đồ quan hệ R(Ω ) và tập phụ thuộc hàm F. Output: Khẳng định R(Ω ) có đạt chuẩn Boyce Codd hay không. Bước 1: Tìm tất cả các khóa của lược đồ quan hệ R(Ω ). Bước 2: Từ tập phụ thuộc hàm F, tạo ra tập phụ thuộc hàm F’ tương đương với F và có vế phải chỉ có một thuộc tính (nhờ sử dụng luật phân rã). 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 thì lược đồ quan hệ đạt chuẩn Boyce Codd. Ngược lại thì lược đồ quan hệ không đạt chuẩn Boyce Codd. 20