Chương 1: Phụ thuộc hàm
lượt xem 57
download
Cho tập hữu hạn U = {A1, A2 , ... , An } khác trống (n 1). Các phần tử của U được gọi là thuộc tính, ứng với mỗi thuộc tính Ai U,i = 1,2, ..., n có một tập không rỗng dom(Ai) được gọi là miền trị của thuộc tính Ai
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Chương 1: Phụ thuộc hàm
- Chương 1: Phụ thuộc hàm Nguồn: Nguyễn Xuân Huy, Lê Hoài Bắc, Bài tập cơ sở dữ liệu, Nhà XB Thống kê, 2003 David Maier, The theory of relational database, Computer Science Press, 1983 Jeffrey D.Ullman, The principles of database and knowledge base system Vol1, 2, Computer Science Press, 1989 1
- Quan hệ Cho tập hữu hạn U = {A1, A2 , ... , An } khác trống (n ≥ 1). Các phần tử của U được gọi là thuộc tính, ứng với mỗi thuộc tính Ai ∈ U,i = 1,2, ..., n có một tập không rỗng dom(Ai) được gọi là miền trị của thuộc tính Ai. Lưu ý D là hợp của các dom(Ai) với i=1,2,…,n Một quan hệ R với các thuộc tính U = { A1, A2 , ... , An }, ký hiệu là R(U), là một tập các ánh xạ t : U → D sao cho với mỗi Ai ∈ U ta có t(Ai) ∈ dom(Ai). Mỗi ánh xạ được gọi là một bộ của quan hệ R. Môn học Cơ sở dữ liệu nâng cao 2
- Phụ thuộc hàm Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng f: X → Y; X, Y ⊆ U Cho quan hệ R(U) và một PTH f: X → Y trên U. Ta nói quan hệ R thoả PTH f và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống nhau trên Y, R(X→Y) ⇔ (∀u,v∈R): (u.X=v.X) ⇒ (u.Y=v.Y) Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH F, và viết R(F), nếu R thoả mọi PTH trong F, R(F) ⇔ (∀ f ∈ F): R(f) Môn học Cơ sở dữ liệu nâng cao 3
- Hệ tiên đề Armstrong (1/2) Hệ tiên đề Armstrong bao gồm: ∀ X, Y, Z ⊆ U a1) phản xạ: Nếu Y ⊂ X thì X → Y a2) tăng trưởng: Nếu Z ⊂ U và X → Y thì XZ → YZ Ký hiệu XZ là X ∪ Z a3) bắc cầu: Nếu X → Y và Y → Z thì X → Z Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F+ là tập nhỏ nhất các PTH trên U chứa F và thoả các tính chất a1 a3 của hệ tiên đề Armstrong Môn học Cơ sở dữ liệu nâng cao 4
- Hệ tiên đề Armstrong (2/2) a4) bắc cầu giả: Nếu X → Y và WY → Z thì XW → Z a5) luật hợp: nếu X → Y và X → Z thì X → YZ a6) luật phân rã: Nếu X → Y và Z ⊂ Y thì X → Z Trong sáu luật trên thì a4, a5, a6 suy được từ a1, a2, a3. Môn học Cơ sở dữ liệu nâng cao 5
- Suy dẫn theo tiên đề (suy dẫn logic) Ta nói PTH f được suy dẫn theo tiên đề (hoặc suy dẫn logic) từ tập PTH F và ký hiệu là F ╞ f, nếu f ∈ F+ . F ╞ f ⇔ f ∈ F+ Nói cách khác f được suy dẫn theo tiên đề từ tập PTH F nếu xuất phát từ F, áp dụng các luật a1, a2 và a3 của hệ tiên đề Armstrong sau hữu hạn lần ta sẽ thu được PTH f. Ta viết F !╞ f để biểu thị tập PTH F không dẫn logic ra được PTH f. Môn học Cơ sở dữ liệu nâng cao 6
- Bao đóng của tập thuộc tính Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính X+ = { A ∈ U | X → A ∈ F+ } Môn học Cơ sở dữ liệu nâng cao 7
- Thuật toán tìm bao đóng của một tập thuộc tính Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Để xác định bao đóng của tập thuộc tính X, X+ ta xuất phát từ tập X và bổ sung dần cho X các thuộc tính thuộc vế phải R của các PTH L → R ∈ F thỏa điều kiện L ⊆ X. Thuật toán sẽ dừng khi không thể bổ sung thêm thuộc tính nào cho X. Môn học Cơ sở dữ liệu nâng cao 8
- Bài toán thành viên Cho tập thuộc tính U, một tập các PTH F trên U và một PTH X → Y trên U. Hỏi rằng X → Y ∈ F+ hay không ? Định lý X → Y ∈ F+ khi và chỉ khi Y ⊆ X+. Môn học Cơ sở dữ liệu nâng cao 9
- Bài toán thành viên Procedure Member Vào: tập PTH F và PTH X → Y Ra : Đúng nếu X → Y ∈ F+ và Sai nếu nguợc lại Member(F, X → Y) Begin If Y ⊆ Closure(X,F) Then return (True) Else Return (False) End Môn học Cơ sở dữ liệu nâng cao 10
- Lược đồ quan hệ Lược đồ quan hệ (LĐQH) LĐQH là một cặp p= (U,F), trong đó U là tập hữu hạn các thuộc tính, F là tập các PTH trên U. Môn học Cơ sở dữ liệu nâng cao 11
- Khóa của quan hệ (1/2) Khóa của lược đồ quan hệ Cho LĐQH p = (U,F). Tập thuộc tính K ⊆ U được gọi là khoá của LĐ p nếu (i) K+ = U (ii) ∀A ∈ K: (K {A})+ ≠ U Môn học Cơ sở dữ liệu nâng cao 12
- Khóa của quan hệ (2/2) Thuộc tính A ∈ U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở) nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá. Chú ý: Trong một số tàì liệu thuật ngữ khoá được dùng theo nghĩa siêu khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá. Môn học Cơ sở dữ liệu nâng cao 13
- 4.30. Xây dựng thuật toán tìm một khóa của LĐQH. Tư tưởng: Xuất phát từ một siêu khóa K tùy ý của LĐQH, duyệt l ần lượt các thuộc tính A của K, nếu bất biến (K-{A})+ = U được bảo toàn thì loại A khỏi K. Có thể thay kiểm tra (K-{A})+ = U bằng kiểm tra A ∈ (K-{A})+ (?). Algorithm Key Format: Key(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Khóa K ⊆ U thỏa K+ = U ∀ A ∈ K: (K-{A})+ ≠ U Method K:=U; for each attribute A in U do if A ∈ (K-{A})+ then K := K-{A} endif; endfor; return K; end Key; Môn học Cơ sở dữ liệu nâng cao 14
- Phủ Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn ra được G, ký hiệu F ╞ G, nếu (∀ g ∈ G): (F ╞ g). Ta nói F tương đương với G, ký hiệu F ≡ G, nếu F ╞ G và G ╞ F. Nếu F ≡ G ta nói G là một phủ của F. Ký hiệu F !╞ G: F không suy dẫn ra được G. F !≡ G: F và G không tương đương. Môn học Cơ sở dữ liệu nâng cao 15
- Thuật toán DERIVES kiểm tra F |= G Vào : hai tập PTH F và G Ra: Đúng nếu F |= G và sai nếu ngược lại. DERIVES (F,G) Begin V:= true; For each X → Y ∈ G do V := V AND member(F, X → Y) Return (V); End. Môn học Cơ sở dữ liệu nâng cao 16
- Thuật toán kiểm tra F ≡ G Vào: hai tập pth F và G Ra: Đúng nếu F ≡ G, sai nếu ngược lại EQUIVALENCE( F, G) Begin V := Derives (F,G) AND Derives(G,F) Return (V) End. Môn học Cơ sở dữ liệu nâng cao 17
- Phủ thu gọn tự nhiên Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ thu gọn tự nhiên của F nếu 1) G là một phủ của F, và 2) G có dạng thu gọn tự nhiên theo nghĩa sau: a) Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau) b) Các vế trái của mọi PTH trong G khác nhau đôi một. Môn học Cơ sở dữ liệu nâng cao 18
- Phủ không dư Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ không dư của F nếu 1) G là một phủ của F, và 2) G có dạng không dư theo nghĩa sau: (∀ g ∈ G): G { g } !≡ G Môn học Cơ sở dữ liệu nâng cao 19
- 4.24 Xây dựng thuật toán tìm phủ không dư của tập PTH F. Algorithm Nonredundant Format: Nonredundant(F) - Tập PTH F Input: Output: - Một phủ không dư G của F G≡ F ∀ g ∈ G: G-{g} !≡ G Method G:=F; for each FD g:L → R in F do if R ⊆ L+G-{g} then G:= G –{g}; endif; endfor; return G; end Nonredundant; Môn học Cơ sở dữ liệu nâng cao 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Cơ sở dữ liệu 1_Chương 4: Phụ thuộc hàm và dạng chuẩn
32 p | 893 | 216
-
Cơ sở dữ liệu 1_Bài tập Chương 4
7 p | 397 | 118
-
Giáo trình Thông tin số
213 p | 487 | 92
-
Bài giảng Nhập môn Cơ sở dữ liệu - Chương 4
25 p | 174 | 29
-
PHÂN TÍCH THIẾT KẾ HỆ THỐNG - CHƯƠNG 11
8 p | 112 | 26
-
Giáo trình Cơ sở dữ liệu: Phần 2 - ĐH công nghiệp Tp.HCM
81 p | 140 | 22
-
CƠ SỞ DỮ LIỆU
309 p | 155 | 22
-
Giáo trình Cơ sở dữ liệu: Phần 1 - ĐH Công nghiệp Tp.HCM
94 p | 118 | 19
-
Giáo trình Nhập môn Cơ sở dữ liệu - GV. Nguyễn Thế Dũng
280 p | 50 | 17
-
Cơ sở Matlab v5.3-1 - Phần 2 - Chương 4
24 p | 126 | 14
-
Giáo trình lập trình C cho winform - 7
9 p | 91 | 9
-
Bài giảng Cơ sở dữ liệu: Chương 8 - TS. Nguyễn Quốc Tuấn
16 p | 86 | 9
-
Bài giảng Cơ sở dữ liệu (Database): Chương 6 - TS. Đặng Thị Thu Hiền
52 p | 25 | 6
-
Bài giảng Hệ cơ sở dữ liệu: Chương 5.1 - TS. Lê Thị Tú Kiên
69 p | 27 | 5
-
Bài giảng Chương 8: Chuẩn hóa
36 p | 50 | 4
-
Giáo trình Cơ sở dữ liệu 1: Phần 2 - Trường ĐH Phan Thiết
81 p | 23 | 4
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