�ݺ�ߣ

1. Never stop improving quality www.elarion.com

2. Phụ thuộc hàm Giới thiệu

3. Định nghĩa

4. Biểu diễn PTH bằng đồ thị

5. Suy diễn logi các PTH

6. Hệ tiên đề Amstrong

7. Bao đóng

8. Bao đóng của tập thuộc tính

9. Khóa – Thuật toán tìm khóa

10. Phủ tối thiểu

11. Giới thiệu Là sự biểu diễn RBTV dưới dạng hình thức toán học.

12. Bảo đảm thông tin không bị tổn thất khi phân rã hoặc kết nối giữa các quan hệ.

13. Định nghĩa Quan hệ R được định nghĩa trên tập thuộc tính U = { A1, A2, ..., An}.

14. A, B ⊂ U là 2 tập con của tập thuộc tính U.

15. Nếu tồn tại một ánh xạ f: A -> B thì nói rằng A xác định hàm B, hay B phụ thuộc hàm vào A.

16. Ký hiệu: A -> B.

17. Định nghĩa Định nghĩa hình thức của PTH:

18. Quan hệ Q (A, B, C) có PTH A xác định B

19. (ký hiệu là A -> B) nếu:

20. ∀ q, q’ ∈ Q, sao cho q.A = q’.A thì q.B = q’.B

21. Nghĩa là: ứng với 1 giá trị của A thì có một giá trị duy nhất của B

22. A là vế trái của PTH, B là vế phải của PTH

23. PTH A -> A được gọi là PTH hiển nhiên.

24. Định nghĩa Ví dụ 1: Trong quan hệ Sinhvien ( Masv , Hoten, Phai, NgSinh, Quequan, Diachi) Có các PTH sau: Masv -> Quequan, Diachi

25. Masv, Hoten -> Ngsinh, Quequan Không có các PTH sau: Hoten -> Ngsinh, Quequan Tức là xác định sinh viên thì tối thiểu phải có mã sinh viên nên không tồn tại phụ thuộc hàm suy ra từ thuộc tính Hoten.

26. Định nghĩa Ví dụ 2: Trong QuanHệ CHITIẾT_HĐ ( Số-hóađơn, Mã-hàng , Số-lượng, Đơn-giá, Trị-giá)

27. Có các PTH sau: f1: Số-hóa-đơn, Mã-hàng-> Số-lượng

28. f2: Số-hóa-đơn, Mã-hàng -> Đơn-giá.

29. f3: Số-hóa-đơn, Mã-hàng-> �հ�ị-��á.

30. f4: Số-lượng, Đơn-giá -> �հ�ị-��á.

31. Biểu diễn PTH bằng đồ thị (1/3) PTH có thể biểu diễn bằng đồ thị có hướng: Các nút trong đồ thị chia thành 2 loại: Nút thuộc tính: biểu diễn bằng tên thuộc tính

32. Nút PTH: biểu diễn bằng hình tròn có số thứ tự của PTH. Các cung trong đồ thị cũng có 2 loại: Cung đến PTH: xuất phát từ các thuộc tính ở vế trái của các PTH

33. Cung rời PTH: hướng đến các thuộc tính ở vế phải của các PTH

34. Biểu diễn PTH bằng đồ thị (2/3) Quan hệ R (A, B, C, D, E, H)

35. Tập phụ thuộc hàm F = {AB->C, CD->E, EC->A,

36. CD->H, H->B } TH022_11

37. Biểu diễn PTH bằng đồ thị (3/3) Quan hệ R (A, B, C, D, E, G)

38. Tập phụ thuộc hàm F = {A->C; B->DE; AB->G;

39. A->ED; D->E } TH022_11

40. Suy diễn logic các PTH (1/2) Cho lược đồ quan hệ R với tập thuộc tính U và tập các PTH F.

41. X -> Y là 1 PTH; X,Y ⊆ U.

42. Ta nói rằng X -> Y được suy diễn lôgic từ F nếu ∀ r ∈R, nếu r thỏa tất cả các PTH trong F thì r cũng thỏa X -> Y Ký hiệu là: F = X -> Y.

43. Suy diễn logic các PTH (2/2) Ví dụ: Với F = {X -> Y, X -> Z, Y -> T }

44. Thì ta có các PTH: X -> YZ

45. X -> T

46. Hệ tiên đề Amstrong (1/4) Năm 1974, Amstrong đã đưa ra hệ tiên đề (gọi là hệ luật dẫn Amstrong) : Cho lược đồ quan hệ Q với tập thuộc tính U. X, Y, Z, W ⊆ U. PTH có các tính chất cơ bản sau: A1: Tính phản xạ: Nếu Y ⊆ X thì X -> Y A2: Tính tăng trưởng: Nếu X -> Y thì XZ -> YZ (Z ⊆ U) A3: Tính bắc cầu: Nếu X -> Y và Y -> Z thì X -> Z

47. Hệ tiên đề Amstrong (2/4) Ví dụ 1: Cho F = {AB -> C, C -> A } CMR: BC -> ABC Ta có: (1) C -> A (giả thiết)

48. (2) BC -> AB (tăng trưởng 1)

49. (3) AB -> C (giả thiết)

50. (4) AB -> ABC (tăng trưởng 3)

51. (5) BC -> ABC (bắc cầu 2 & 4)

52. Hệ tiên đề Amstrong (3/4) Các tính chất bổ sung: A4: Luật giả bắc cầu: Nếu X -> Y và YZ -> W thì XZ -> W A5: Luật hợp: Nếu X -> Y và X -> Z thì X -> YZ A6: Luật tách: Nếu X -> YZ thì X -> Y và X -> Z

53. Hệ tiên đề Amstrong (4/4) Ví dụ: Cho R(A,B,C,D,E,G,H). CMR: AB->E với F = {AB->C, B->D, CD->E, CE->GH, G->A }.

54. Ta có: (1) AB->C (cho�ٰ�ước)

55. (2) AB->AB (phản ��ạ)

56. (3) AB->B (luật ��á��)

57. (4) B->D (cho �ٰ�ước)

58. (5) AB->D (bắc cầu 3 & 4)

59. (6) AB->CD (hợp 1 & 5)

60. (7) CD->E (cho �ٰ�ước)

61. (8) AB->E (bắc cầu 6 & 7)

62. Bao đóng (Closure) (1/3) Gọi F+ là bao đóng (Closure) của F, tức là tập các PTH được suy diễn lôgic từ F.

63. Nếu F = F+ thì ta nói F là họ đầy đủ (full family) của các PTH.

64. Bao đóng (Closure) (2/3) Bài toán thành viên (MemberShip):

65. Kiểm tra PTH X -> Y có được suy diễn lôgíc từ F không? (tức là X -> Y ∈ F+ ? ) Đây là một bài toán khó giải.

66. Đòi hỏi phải có một hệ luật dẫn để suy diễn lôgic các PTH.

67. Bao đóng (Closure) (3/3) Bài toán thành viên – Ví dụ: Cho Q(ABCDEG). F = {AE -> C, CG -> A, BD -> G, GA -> E }

68. CMR: BDC -> Q+ ∈ F+ (Q+ = ABCDEG+) Ta có: (1) BDC->BDC (phản ��ạ)

69. (2) BD->G (giả thiết f3)

70. (3) CG->A (giả thiết f2)

71. (4) BDC->A (giả bắc cầu 2,3)

72. (5) BDC->GA (hợp 2 & 4)

73. (6) BDC->E (bắc cầu 5 & f4)

74. (7) BDC->Q+ (hợp 1,2,4,6)

75. Bao đóng của tập thuộc tính (1/5) Thuật toán Tìm bao đóng của tập thuộc tính

76. Input: Tập U hữu hạn các thuộc tính & tập các

77. PTH F trên U & X ⊆ U.

78. Output: X + F

79. Phương pháp: Tính liên tiếp X 0 , X 1 , X 2 , … theo quy tắc như sau:

80. Bao đóng của tập thuộc tính (2/5) Thuật toán Tìm bao đóng của tập thuộc tính

81. Bước 1. X 0 = X

82. Bước 2. X i+1 = X i ∪ A sao cho ∃ (Y -> Z ) ∈ F, mà A ∈ Z và Y ∈ Xi

83. Bước 3. Cho đến khi X i+1 = Xi (Vì X= X 0 ⊆ X 1 ⊆ X 2 ⊆ … ⊆ U, mà U hữu hạn cho nên sẽ tồn tại 1 chỉ số i nào đó mà X i+1 = X i )

84. Khi đó X + F = X i

85. Bao đóng của tập thuộc tính (3/5) Tìm bao đóng của tập thuộc tính – Ví dụ 1

86. Cho R(U) với U=ABCDEG

87. F = {AB -> C, C -> A, BC -> D, ACD -> B,

88. D -> EG, BE -> C, CG -> BD, CE -> AG }

89. Tính X + F , với:

90. X= D

91. X= BD

92. Bao đóng của tập thuộc tính (4/5) Vậy D + = DEG

93. Bao đóng của tập thuộc tính (5/5) Vậy BD + = ABCDEG

94. Khóa – Thuật toán tìm khóa R là lược đồ quan hệ định nghĩa trên tập các thuộc tính U = { A 1 , A 2 , ... , A n }

95. Tập các PTH F = { f 1 , f 2 , ..., f m } xác định trên R.

96. K ⊆ U là khóa của R nếu thỏa mãn hai điều kiện sau đây: K -> U. ( K là siêu khóa )

97. ∃ K’ ⊂ K mà K’ -> U.

98. Bài Toán Tìm khóa (1/6) Xác định tất cả các khóa của 1 lược đồ quan hệ.

99. Bài toán này được giải quyết qua 2 giai đoạn: Giai đoạn 1 : Xây dựng tập S chứa tất cả các siêu khóa của R

100. Giai đoạn 2 : Xây dựng tập K chứa tất cả các khóa của R từ tập S bằng cách loại bỏ khỏi S những siêu khóa không tối thiểu.

101. Bài Toán Tìm khóa (2/6) Để xác định tất cả các siêu khóa của 1 lược đồ quan hệ R, ta lần lượt xét (2 n -1) tập hợp con của R + : X 1 , X 2 , … Nếu 1 tập con X i của R + có bao đóng bằng đúng R + thì tập con X i chính là 1 siêu khóa.

102. Nếu R chỉ có 1 siêu khóa S thì siêu khóa đó cũng là khóa của lược đồ quan hệ R

103. Bài Toán Tìm khóa (3/6) Trong trường hợp R có nhiều hơn 1 siêu khóa (hữu hạn), để xác định tất cả các khóa chỉ định, ta so sánh 1 cặp siêu khóa S i và S j . Nếu S i ⊂ S j , ta loại S j và giữ lại S i .

104. Lần lượt so sánh từng cặp siêu khóa để loại bỏ tập lớn, cuối cùng thu được tập các khóa chỉ định của R.

105. Suy ra Thuật toán không khả thi khi n lớn.

106. Bài toán tìm khóa (4/6) Bài Toán Tìm khóa – Thuật toán cải tiến: Chúng ta sẽ cải tiến thuật toán dựa trên việc phân loại tập thuộc tính R + A gọi là thuộc tính nguồn nếu A không xuất hiện ở vế phải của bất kỳ PTH không hiển nhiên nào của F.

107. Tập các thuộc tính nguồn ký hiệu là N

108. A gọi là thuộc tính đích nếu A không phải thuộc tính nguồn và A không xuất hiện ở vế trái của bất kỳ PTH không hiển nhiên nào của F.

109. Tập các thuộc tính đích ký hiệu là D.

110. Bài toán tìm khóa (5/6) Tập hợp các thuộc tính không phải nguồn và không phải đích gọi là tập trung gian. Ký hiệu là L

111. Các tập hợp N, D, L rời nhau từng đôi một và N ∪ D ∪ L = R + Nhận xét Nếu K là khóa của R thì K chứa tất cả các thuộc tính nguồn và không chứa bất kỳ thuộc tính đích nào.

112. Bài toán tìm khóa (6/6) B1: Xây dựng 2v tập con của L: L1, L2, … bằng phương pháp đường chạy nhị phân.

113. B2: Xây dựng tập K chứa các siêu khóa K = ∅

114. ∀ L i , X i = N ∪ L i

115. Tính X i + F . Nếu X i + F = R + thì K = K ∪ X i B3: Loại bỏ dần các siêu khóa lớn

116. Ví dụ – thuật toán cải tiến (1/3) Ví dụ: Cho R(ABCDEG) với tập PTH F = { AE -> C, CG -> A, BD -> G, GA -> E } Xác định tất cả các khóa của R

117. Ta có: N = { B, D }

118. D = ∅

119. L = { A, C, E, G }

120. Xây dựng tập thuộc tính L i bằng phương pháp đường chạy nhị phân.

121. Ví dụ – thuật toán cải tiến (2/3)

122. Ví dụ – thuật toán cải tiến (3/3) Vậy có 2 siêu khóa: BDC

123. BDA Và 2 khóa: BDC

124. BDA

125. Phủ tối thiểu (1/4) PTH tương đương Gọi F và G là các tập PTH. Ta nói rằng F và G là tương đương nếu F + = G + .

126. Nếu F và G tương đương, đôi khi còn nói F phủ G (hay G phủ F).

127. Phủ tối thiểu (2/4) Phủ tối thiểu: Gọi F là tối thiểu nếu Mỗi vế phải của 1 PTH ∈ F chỉ có 1 thuộc tính

128. Không tồn tại 1 PTH X -> A thuộc F, mà: F + = (F - {X -> A} ) + Không tồn tại 1 PTH X -> A thuộc F, và 1 tập con Z của X mà: F + = (F - {X -> A} ∪ {Z -> A} ) +

129. Ví dụ - Phủ tối thiểu (3/4) Ví dụ 1: Cho F = { AB -> C, C-> A, BC -> D, ACD -> B,D -> E, D -> G, BE -> C, CG -> B, CG -> D, CE -> A, CE -> G }

130. Tìm Phủ tối thiểu .

131. Ta có: CE -> A là dư thừa (vì C -> A )

132. CG -> B là dư thừa (vì CG -> D, C -> A và ACD -> B)

133. ACD -> B thay bằng CD -> B vì C -> A Suy ra PTT = { AB -> C, C-> A, BC -> D, CD -> B, D -> E, D -> G, BE -> C, CG -> D, CE -> G }

134. Phủ tối thiểu (4/4) Ví dụ 2: Cho F = { AB -> C, C-> A, BC -> D, ACD ->B,D -> E, D -> G, BE -> C, CG -> B, CG -> D, CE -> A, CE -> G } Tìm Phủ tối thiểu . Loại bỏ CE -> A, CG -> D và ACD -> B sẽ có tập tối thiểu:

135. Suy ra PTT = { AB -> C, C-> A, BC -> D, D -> E, D -> G, BE -> C, CG -> B, CE -> G }

�ݺ�ߣ

Phan5

More Related Content

Phan5