Bài giảng Cơ sở dữ liệu - Bài 4: Phụ thuộc hàm

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

Thêm vào BST

Báo xấu

209
lượt xem 12
download

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

Mục tiêu chính của Bài giảng Cơ sở dữ liệu Bài 4 Phụ thuộc hàm nghiên cứu hình thức các ràng buộc, xây dựng cấu trúc bảo đảm các ràng buộc tự động thoả, do đó không cần lập trình. Đánh giá một lược đồ cơ sở dữ liệ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 - Bài 4: Phụ thuộc hàm

CƠ SỞ DỮ LIỆU Bài 4: PHỤ THUỘC HÀM 13/08/2012 HVĐ – THQL 1
BÀI TOÁN THỰC TẾ • Nghiên cứu hình thức các ràng buộc – Xây dựng cấu trúc bảo đảm các ràng buộc tự động thoả, do đó không cần lập trình – Đánh giá một lược đồ cơ sở dữ liệu 13/08/2012 HVĐ – THQL 2
MỤC TIÊU • Kiến thức: – Phụ thuộc hàm – Dạng chuẩn – Kỹ thuật tableaux • Kỹ năng: – Tìm phủ tối tiểu – Xác định dạng chuẩn – Đánh giá lược đồ CSDL • Yêu cầu: áp dụng thực tế 13/08/2012 HVĐ – THQL 3
NỘI DUNG • Phụ thuộc hàm • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 4
PHỤ THUỘC HÀM • Phụ thuộc hàm – Khái niệm – Bài toán thành viên • Phủ tối tiểu • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 5
QUAN HỆ HÀM Y • Hình bên có – Quan hệ thuần túy – Quan hệ đường • Không có quan hệ hàm • Quan hệ hàm từ X vào Y • Quan hệ hàm từ Y vào X X MaSV MaLop • Hàm từ X vào Y: S01 L1 – Mỗi x có duy nhất y S02 L2 – Nếu chiếu xuống XY S03 L2 • Bảng: x xuất hiện một lần S04 13/08/2012 L2 HVĐ – THQL • Lược đồ: X là siêu khoá 6
PHỤ THUỘC HÀM • Phụ thuộc hàm là một loại ràng buộc toàn vẹn HDSo NLap MaHG DGia SoL • Phụ thuộc hàm là luật H01 12 H01 12 5 – PTH X  Y ngụ ý: biết H01 12 H02 5 2 X sẽ xác định được Y H02 14 H01 12 4 – Quan hệ r thỏa X  Y H02 14 H03 20 3 • Các dòng có X giống nhau thì Y cũng vậy • r[X,Y] có X siêu khoá – Luật nên lưu riêng để áp dụng, ví dụ HDSo NLap • HDSo  NLap H01 12 • MaHG  Dgia • HDSo,MaHG  SoL H02 14 13/08/2012 HVĐ – THQL 7
THẢO LUẬN MSV HT ML TL MM TM STC MGV TGV KH ĐT a Tèo 1 T x DSTT 5p Minh T 6 a Tèo 1 T y LTHT 3q Lan T 7 a Tèo 1 T z CSDL 3p Minh T 9 b Nị 2K x DSTT 5q Lan T 5 b Nị 2K y LTHT 3q Lan T 7 b Nị 2K z CSDL 3p Minh T 8 c Bi 1T x DSTT 5p Minh T 6 c Bi 1T y LTHT 3q Lan T 4 c Bi 1T z CSDL 3p Minh T 8 • Tìm các phụ thuộc hàm • Tổ chức lại các bảng • Bài tập 1, 13a 13/08/2012 HVĐ – THQL 8
QUY TẮC QUẢN LÝ • Cho cơ sở dữ liệu lưu các dữ liệu liên quan đến {Gviên, Sviên, Lớp , Môn, Khoa, Điểm, Tênsv} • Các quy tắc sau đây, cái nào là phụ thuộc hàm – Sinh viên thuộc về một lớp – Sinh viên thuộc về một khoa – Lớp thuộc về một khoa – Sinh viên học một môn phải có điểm – Sinh viên phải có tên – Mỗi lớp có không quá 30 sinh viên • Tổ chức lại các bảng 13/08/2012 HVĐ – THQL 9
BÀI TOÁN THÀNH VIÊN • Ta nói f là hệ quả của F (hay được suy từ F) nếu một quan hệ r bất kỳ thoả F thì thoả f • Ký hiệu tập các phụ thuộc hàm hệ quả là F+ và được gọi là bao đóng của F • Bài toán kiểm tra f  F được gọi là bài toán thành viên 13/08/2012 HVĐ – THQL 10
LUẬT DẪN • Bộ luật – F1: XX – F2: XY suy ra XZY – F3: XY và XZ suy ra XYZ – F4: XYZ suy ra XY và XZ – F5: XY và YZ suy ra XZ – F6: XY và YZW suy ra XZW • Hệ tiên đề Amstrong {F1, F2, F6} • {AD,ABE,BIE,CDI,EC}⊨ AEDI 13/08/2012 HVĐ – THQL 11
BAO ĐÓNG • X+F = { A | (X  A)  F+ } • Áp dụng Y  X+F  X  Y (F+) • Kiểm tra tính thành viên f = AEDI đối với F = {AD,ABE,BIE,CDI,EC} – Tính AE+ = AEDCI – Ta có DI  AE + – Suy ra f F+ 13/08/2012 HVĐ – THQL 12
THẢO LUẬN • Bài tập 2, 3, 4, 5 13/08/2012 HVĐ – THQL 13
PHỦ TỐI TIỂU • Phụ thuộc hàm • Phủ tối tiểu – Khái niệm – Thuật toán • Dạng chuẩn • Kỹ thuật tableaux • Đánh giá lược đồ CSDL • Khảo sát tình huống 13/08/2012 HVĐ – THQL 14
PHỦ TỐI TIỂU • Phụ thuộc hàm, như luật, đúng trong ngữ cảnh nhất định. Với ngữ cảnh cho trước chúng ta có tập phụ thuộc hàm • Xác định phụ thuộc hàm để lưu riêng một cách tuỳ tiện có thể dẫn đến dư thừa • Tập phụ thuộc hàm không dư thừa được gọi là phủ tối tiểu – Vế phải gồm một thuộc tính – Vế trái không dư thừa – Không có phụ thuộc hàm dư thừa • Dư thừa được xác định nhờ hệ tiên đề Armstrong 13/08/2012 HVĐ – THQL 15
THẢO LUẬN • Các ký tự GSLMKNDHY là viết tắt của Gviên, Sviên, Lớp, Môn, Khoa, Ngành, Điểm, Hệ, học kỲ • Xét hai ngữ cảnh – Tổng quát: NM  Y, SM  D, N  K, L  HN, S  HN, M  H, LM  G – Trong một học kỳ: S  L • Với mỗi ngữ cảnh cho biết F có tối tiểu không 13/08/2012 HVĐ – THQL 16
TÌM PHỦ TỐI TIỂU • Cơ sở: bài toán thành viên • Các bước – Phân rã – Rút gọn vế trái – Rút gọn phụ thuộc hàm 13/08/2012 HVĐ – THQL 17
A->C AB->C VÍ DỤ C->DI CD->I A->C A+=ACDI A->C EC->AB AB->C B+=B EI->C C->D C+=CDI C->D A+=A C->I D+=D C->I C CD->I E+=E EI+=EI EC->A I+=I EC->A EC->B EC->B A->C EI->C EI->C C->DI • Dùng thuật toán: EC->AB – Phân rã EI->C – Rút gọn VT – Rút gọn PTH • Dùng bộ luật dẫn 13/08/2012 HVĐ – THQL 18
THẢO LUẬN { S -> D, { A -> BC, { AB -> C, I -> B, B -> AC, C -> A, IS -> Q, C -> A } BC -> D, B -> O } ACD -> B, D -> EG, BE -> C, CG -> BD, CE -> AG } • Dùng luật • Dùng thuật toán 13/08/2012 HVĐ – THQL 19
DƯ THỪA PHẢI R(KDHNMLG) • Tìm những thuộc tính xuất hiện F={ K -> D, ở vế phải nhiều lần (ví dụ D) H -> KDN, • Chọn một PTH liên quan (ví dụ M -> G, H->KDN) HM -> L} • Bỏ thuộc tính này, rồi tính bao đóng (ví dụ H+ =HKDN) • Kết luận (ví dụ H->KDN dư thừa D) 13/08/2012 HVĐ – THQL 20