zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cơ sở dữ liệu: Chương 3 - Đỗ Thị Mai Hường

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:88

Báo xấu

77
lượt xem 6
download

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

Bài giảng Cơ sở dữ liệu biên soạn bởi giáo viên Đỗ Thị Mai Hường với các nội dung lý thuyết thiết kế cơ sở dữ liệu quan hệ; sự dư thừa; phụ thuộc hàm; hệ tiên đề Armstrong; tính chất của bao đóng X+...

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 3 - Đỗ Thị Mai Hường

CƠ SỞ DỮ LIỆU U GIÁO VIÊN: ĐỖ THỊ T MAI HƯỜNG BỘ MÔN: CÁC HỆ TTHỐNG THÔNG TIN KHOA: CÔNG NG GHỆ THÔNG TIN Lý thuyết CSDL 1
CHƯƠNG 3 Lý th thuyế ết thiết kế cơ sở dữ liệ ệu quan hệ Lý thuyết CSDL 2
Nội dung chi tiết • Giới h hạn của ủ ER • Sự dư thừa • Ph thuộc Phụ h ộ hàm hà • Hệ suy diễn Amstrong • Th ậ toán Thuật á tìm ì bao b đóng đó • Thuật toán tìm khóa • Cá dạng chuẩn Các ẩ • Kiểm tra kết nối không mất thô ông tin Lý thuyết CSDL 3
Sự dư thừa • Sự phụ thuộc giữa các thuộc tính gây g ra sự dư thừa Ví dụ: Điểm các môn học  Điểm trrung bình  xếp loại • Thuộc tính đa trị trong lược đồ ER  nhiều bộ số liệu trong lược đồ quan hệ • Ví dụ: NHANVIEN(TENNV HONV, NHANVIEN(TENNV, HONV NS S DCHI GT LUONG BANGCAP) S,DCHI,GT,LUONG, TENNV HONV NS D DCHI GT LUONG BANGCAP Tung Nguyen 12/08/1955 638 NVC Q5 Nam 40000 Trung học Nhu Le 06/20/1951 291 HVH H QPN Nu 43000 Trung học Nhu Le 06/20/1951 291 HVH H QPN Nu 43000 Đại học Hung Nguyen 09/15/1962 Ba Ria VT Nam 38000 Thạc sỹ Lý thuyết CSDL 4
Sự dư thừa (tt) • Sự dư thừa  sự dị thường – Thao tác sửa đổi: cập nhật tất cả các giá trị liên quan – Thao tác xóa: người cuối cùngg của đơn vị  mất thông tin về đơn vị – Thao tác chèn TENPB MAPB MaTP NG_NHAN NCHUC MANV TENNV HONV … Nghien cuu 5 NV01 05/22/1 1988 NV01 Tung Nguyen … Dieu hanh 4 NV02 01/01/1 1995 NV02 Hung Nguyen … Quan ly 1 NV03 06/19/1 1981 NV03 Vinh Pham … Lý thuyết CSDL 5
Sự dư thừa (tt) • Các Cá giá iá trị t ị khô không xác á định đị h – Đặt thuộc tính Trưởng phòng vàào quan hệ NHANVIEN thay vì vào quan hệ PHONGBAN • Các bộ giả – Sử dụng các phép nối Lý thuyết CSDL 6
Sự dư thừa (tt) • Một số quy tắc 1.Rõ ràng về mặt ngữ nghĩa, tránnh các phụ thuộc giữa các thuộc tính với nhau 2 T á h sự ttrùng 2.Tránh ù lặp lặ vềề nội d g đảm ội dung đả bảo bả tránh t á h được đ các á dị thường th ờ khi thao tác cập nhật dữ liệu 3. Tránh đặt các thuộc tính có nhhiều giá trị Null • Khó thực hiện các phép nối và kết k hợp 4. Thiết kế các lược đồ quan hệ sao s cho chúng có thể được nối với điều ề kiện bằng ằ trên các thuộc tính là khoá chính hoặc khoá ngoài theo cách đảm bảo không sinhh ra các bộ “giả” => Lý thuyết về chuẩn hóa: (dự ựa trên phụ thuộc hàm, hàm …)) sẽ là nền tảng cơ sở để thực hiện việc v phân tích và chuẩn hóa lược đồ quan hệ Lý thuyết CSDL 7
Phụ thuộc hàm Ph thuộc Phụ th ộ hà hàm ttrong quan hệ r • Cho lược đồ quan hệ R và X, Y làà các tập con của R. r là một quan hệ trên R. • Ta nói X xác định phụ thuộc hàm m Y ký hiệu X → Y trong r nếu với mọi t và t’ của r mà t, t’ bằng nhaau trên tập X thì chúng cũng bằng nhau trên tập Y, tức là  t, t’  r nếu t.X = t’.X  t.Y = t’.Y • Ví dụ: – X={MaNV}, { }, Y={Hoten,NS} { , } thỏ ỏa mãn X → Y – X={Hoten}, Y={DC, GT} không g thỏa mãn X → Y • Phụ thuộc hàm trên r là trường hợ ợp riêng của phụ thuộc hàm trên R. R Lý thuyết CSDL 8
Phụ thuộc hàm(tt) • Phụ thuộc hàm trong quan hệ r Ví dụ: trong lược đồ quan hệ sau nếu giả g thiết Hoten nhập vào là khác nhau thì từ Hoten có thể suy diễn ra tất cả các thuộc tính khác. Nhưng nếu ế thêm hê vàoà bộ cóó H Hoten giống iố với ới bộộ đã cóó thì hì phụ h thuộc h ộ hàm hà không khô còn đúng nữa. HoTen NgaySinh MaPB TenPB Nguyễn ễ Văn A 1/1/1980 / / PB01 Hành chính Nguyễn Văn B 20/2/1981 PB02 Tổng hợp Trần ầ C 13/6/1981 PB03 Dự án Trần ầ C 10/2/1982 PB01 Hành chính Lý thuyết CSDL 9
Phụ thuộc hàm(tt) Bài tập: Cho bảng quan hệ r như sau: A B C D x u x y y x z x z y y y y z w z Trong các phụ thuộc hàm sau PT TH nào không thỏa mãn r A →B,A B A →C,B C B →A,C A C →D,D D D →CC D →A C,D A Lý thuyết CSDL 10
Phụ thuộc hàm(tt) Phụ thuộc hàm trên lược đồ quan q hệ R • Cho lược đồ quan hệ R và X, Y là các tập con của R. Ta nói X xác định phụ thuộc hàm Y kký hiệu X → Y trên lược đồ quan hệ R. Nếu với mọi r trên R xác c định X → Y . Lý thuyết CSDL 11
Phụ thuộc hàm(tt) Cá tí Các tính h chất hất của ủ phụ h th thu uộc ộ hà hàm • A1. Tính phản xạ X → X, hay tổng ổ quát hơn ế Y X thì X → Y n nếu • A2. Tính mở rộng hai vế X → Y thì XZ → YZ. (Mở ở rộng hai vế ế Z) • A3. Tính bắc cầu: X → Y và Y → Z thì X → Z. • Hệ A bao gồm ồ các tính chấtấ {A A1, A2, A3} của phụ thuộc hàm được gọi là hệ tiên đề Armstro ong của lớp các phụ thuộc hàm. Lý thuyết CSDL 12
Phụ thuộc hàm(tt) Giả sử t,t’ r 1. Tính phản xạ: hiển ể nhiên vì t và t’ đã đ bằng ằ nhau trong tập X thì chúng phải bằng nhau trong mọi tậpp con của X, nói cách khác t.X t .X  t.X t.X=t’.X t.X=t’.X t .X & t.Y t .Y với Y X  X → Y t.Y=t’.Y 2. Tính mở rộng 2 vế: giả sử t.XZ=t’.X XZ ta phải chứng minh t.YZ=t’.YZ Thật vậy từ t.XZ=t’.XZ ta có t.X=t’.X và t.Z=t’.Z. Theo giả thiết t.X=t’.X thì t.Y=t’.Y. Như vậy ta cóó t.Y=t’.Y và t.Z=t’.Z thì t YZ=t’.YZ t.YZ=t YZ . Suy ra XZ → YZ 3. Tính bắc cầu: t.X X  t.Y t X = t’.X t Y = t’.Y Y t.Y = t’.Y  t.Z = t’.Z  t.X = t’.X thì t.Z = t’.Z  X → Z Lý thuyết CSDL 13
Các tính chất bổ sung g từ Hệ Amstrong Các tính chất sau đều được suy ra từ hệ tiên đề Armstrong. Tính tựa bắc cầu: X → Y và YZ → W thì XZ → W Tính chất chiếu: X → YZ thì X → Y và X → Z Tính cộng đầy đủ: X → Y và Z → W thì XZ → YW Lý thuyết CSDL 14
Hệ tiên đề Armstrong • Chứng minh: • Tính chất tựa bắc cầu: X → Y và YZ → W thì XZ → W X → Y theo tính mở rộng hai vế XZ → YZ Và YZ → W Theo tính bắc cầu XZ → W Lý thuyết CSDL 15
Hệ tiên đề Amstrong Bài tập: ậ Chứng Chứ minh i h các á tính í h chấ hấất ấ còn ò lại l i • Tính chất chiếu: X → YZ thì X → Y và X → Z • Tính cộng đầy đủ: X → Y và Z → W thì XZ → YW Y Lý thuyết CSDL 16
Hệ tiên đề Armstron ng • Phép Phé suy dẫ dẫn theo hệ tiê ê đề Armstrong ên A t o PTH f được suy dẫn theo hệ tiên đề Armstrong là f có thể nhận ậ được từ ừ F sau một ộ số ố hữu h hạn bước ớ áp á dụng các á luật của tiên đề Armstrong. Ký hiệu F |= f. • Phép suy dẫn theo quan n hệ PTH f suy dẫn được từ tập PT TH F theo quan hệ (hoặc PTH f được suy dẫn theo quan hệ ệ từ tập PTH F) ký hiệu F |- f, nếu với mọi quan hệ r trên lược đồ R mà F thỏa mãn thì f cũng thỏa mãn. Lý thuyết CSDL 17
Hệ tiên đề Armstron ng Bổ đề: Giả sử X  R, nếu gọi X+ làà tập các thuộc tính A của R mà F |= X → A thì với mọi tập Y  R, F |= X → Y  Y  X +. a. Chứng minh chiều thuận Ta có F |= X → Y. Giả sử Y={A, B, B C, ...} theo tính mở rộng trái thu hẹp phải: F |= X → A, nên theo định nghĩa X+ ta có A  X+. F |= X → B, nên theo định nghĩa a X+ ta có B  X+. F ||= X → C,, nên theo định ị nghĩa g a X+ ta có C  X+. ..., vậy {A, B, C, ...} = Y  X+. b. Chứngg minh điều ngược g ợ lại ạ Y  X+. Theo định nghĩa tập X+ thhì mọi A  Y ta có F|= X → A, vậy theo tính chất cộng đầy đủ ta có F|= X → Y. Lý thuyết CSDL 18
Hệ tiên đề Armstron ng Định lý: Cho tập PTH F và một PTH f trêên R khi đó ta có F |- f khi và chỉ khi F |= f. Chứng minh: • Giả sử có F ||=XY XY cần chứng m minh F ||-XY XY • Theo bổ đề ta có YX+. Để chứn ng minh F |-XY, ta lấy một quan hệ R tuỳ t ỳ ý thoả th ả mãn ã tất cảả các á fds fds của ủ F vàà ta t phải hải chứng hứ minh i hR thoả XY. • Ta lấy ấ 2 thực thểể bất ấ kỳ t, t' của R mà t[X]=t'[X], ta phải chứng tỏ t[Y]=t'[Y] mà Y X+nên t[Y]=t'[[Y] (đpcm) Lý thuyết CSDL 19
Hệ tiên đề Armstron ng Giả sử có F |-XY | XY chứng minh h F |=XY, |=XY hay chỉ cần chứng minh Y X+ X X+ thì (X Nhận xét: Nếu X' (X'))+  X+ . Xét một quan hệ r trên tập thuộc tính R Lý thuyết CSDL 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.