intTypePromotion=1
ADSENSE

Bài giảng Cơ sở dữ liệu - Chương 5: Lý thuyết về phụ thuộc hàm

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

56
lượt xem
1
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: Lý thuyết về phụ thuộc hàm. 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ủ đề:
Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu - Chương 5: Lý thuyết về phụ thuộc hàm

  1. 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 5 LÝ THUYẾT VỀ PHỤ THUỘC HÀM 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
  2. 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
  3. 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  
  4. 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
  5. Tà i li ệu  t h a m  k h ảo 5
  6. LÝ THUYẾT VỀ PHỤ THUỘC HÀM 5.1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG 5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 5.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM 5.6. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 6
  7. Giáo sư William Ward Armstrong Đ ại h ọc  Mo n t re a l,  Ca n a d a 7
  8. 5.1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG 5.1.1. ĐỊNH NGHĨA PHỤ THUỘC HÀM Ví dụ: Xét quan hệ trên lược đồ quan hệ Đặt Hàng Đơn vị Số Ngày Mã KH Tên KH Số CMND Điện Thoại Mã MH Tên MH Đơn Giá tính Lượng Đặt KH01 An 031275568 0988812322 MH01 USB 32G Chiếc 25$ 30 11/6 KH02 Bình 031254678 0912345678 MH02 Ốp lưng Chiếc 10$ 100 20/7 KH01 An 031275568 0988812322 MH02 Ốp lưng Chiếc 20$ 50 28/7 KH03 Cường 031255566 0987654323 MH01 USB 32G Chiếc 25$ 25 29/7 KH02 Bình 031254678 0912345678 MH03 Thẻ 16G Chiếc 15$ 20 01/8 KH03 Cường 031255566 0987654323 MH03 Thẻ 16G Chiếc 15$ 55 09/10 Mã KH quyết định Tên KH, Số CMND, Điện Thoại  Ký hiệu: Mã KH →  Tên KH, Số CMND, Điện Thoại Số CMND quyết định Mã KH, Tên KH, Điện Thoại Ký hiệu: Số CMND →  Mã KH, Tên KH, Điện Thoại Phụ thuộc hàm Mã MH quyết định Tên MH, Đơn Vị Tính, Đơn Giá Ký hiệu: Mã MH →  Tên MH, Đơn Vị Tính, Đơn Giá Mã KH, Mã MH quyết định Số Lượng, Ngày Đặt 8 Ký hiệu: Mã KH, Mã MH →  Số Lượng, Ngày Đặt
  9. Cho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y Ω. Ta nói X quyết định Y hay Y phụ thuộc hàm vào X (ký hiệu: X→Y) khi và chỉ khi với mọi quan hệ r trên R(Ω) và với 02 bộ t1, t2 bất kỳ thuộc r ta luôn có: Nếu t1[X] = t2[X] thì t1[Y] = t2[Y] Lưu ý: + Phụ thuộc hàm X → đúng với mọi quan hệ r + Phụ thuộc hàm → Y đúng với quan hệ r có cùng giá trị trên Y X Y A B C Viết X →  Y có nghĩa là: a2 b2 c2 Cứ  mang  giá  trị  giống  a1 b1 c1 nhau trên X thì phải mang  a2 b2 c2 giá trị giống nhau trên Y a1 b1 c1 a2 b2 c2 9 a1 b1 c1
  10. 5.1.2. HỆ TIÊN ĐỀ ARMSTRONG Cho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y, Z, W Ω 5.1.2.1. LUẬT PHẢN XẠ: Nếu Y X thì X → Y 5.1.2.2. LUẬT TĂNG TRƯỞNG: Nếu X → Y thì XZ → YZ 5.1.2.3. LUẬT BẮC CẦU: Nếu X → Y và Y → Z thì X → Z Được công bố bởi William Ward Armstrong vào năm 1974 → Z th ì X → YZ N ếu X → Y và X U ẬT KẾ T HỢP: v à X→Z . 2.4. L X → Y 5.1 N ế u X → YZ thì T P H ÂN R Ã: Z t h ì X W →Z 5.1.2.5. LUẬ u X → Y v à YW → IẢ B Ắ C C ẦU: Nế TG 5.1.2.6. LUẬ 10
  11. 5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 11
  12. 12
  13. 5.2.2.3. Tính chất của bao đóng của tập phụ thuộc hàm A. Tính phản xạ: F F+ B. Tính đơn điệu: Nếu F G thì F+ G+ C. Tính bao phủ: Nếu F G+ thì F+ G+ D. Tính lũy đẳng: (F+)+ = F+ 13
  14. 5 . 2 . 3 .  H Ệ TIÊN  Đ Ề ARMS TRON G LÀ Đ ÚN G VÀ  Đ ẦY  Đ Ủ A.  H ệ t iê n   đ ề Arm s t ro n g  là  đ ú n g :  Từ  t ập   p h ụ  t h u ộc   h à m   F  b a n   đ ầu ,   h ệ  t iê n   đ ề  Arm s t ro n g   c h ỉ  c ó  t h ể s in h  ra  c á c  p h ụ t h u ộc  h à m  n ằm  t ro n g  F* B.   H ệ t iê n   đ ề Arm s t ro n g  là  đ ầy   đ ủ:  Từ t ập  p h ụ t h u ộc  h à m  F b a n   đ ầu ,  h ệ t iê n   đ ề Arm s t ro n g  c ó   t h ể s in h  ra   đ ược   t ất  c ả  c á c  p h ụ t h u ộc  h à m  c ủa  F* V ậy   Kể  từ  giờ  trở  đi  ta  nê n: k h ô n g   p h â n   b i ệt   F*  h a y   F+   n ữa   m à   c h ỉ  d ù n g   m ột   k h á i  14 n i ệm  b a o   đ ó n g  F+
  15. 5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 15
  16. Ví  dụ:  Ch o   l ược   đ ồ  q u a n   h ệ  R( A, B, C, D , E, G, H)  v à   t ập   p h ụ  t h u ộc  h à m :  F =  { B  → A,  D A  → CE,  D   → H,  GH  → C,  AC  → D } Tìm  b a o  đ ó n g  c ủa  X =  AC. Gi ải : B ước  1 : X o  =  AC B ước  2 : D u y ệt  c á c  p h ụ t h u ộc  h à m  t ro n g  F: ­ Có  AC  → D  n ê n  X 1  =  X o    { D }  =  ACD  v à  lo ại AC  → D  k h ỏi F Lặp  l ại b ước  2 : D u y ệt  c á c  p h ụ t h u ộc  h à m  c ò n  l ại t ro n g  F: ­  Có   D A   →  CE  n ê n   X 2   =   X 1    { CE}   =   ACD E  v à   lo ại  D A   →  CE  ra  k h ỏi F ­  Có   D   →  H  n ê n   X 3   =   X 2    { H}   =   ACD EH  v à   lo ại  D   →  H  ra   k h ỏi F. 16 Lặp   l ại  b ước   2 :  T ừ  c á c   p h ụ  t h u ộc   h à m   c ò n   l ại  F  =   { B  →  A ,  
  17. 5 . 3 . 3 .  TÍN H CH ẤT CỦA BAO  Đ ÓN G CỦA TẬP  THU ỘC TÍN H A.  Tín h  p h ản  x ạ:  X   X+ B.  Tín h   đ ơn   đ i ệu :  N ếu  X   Y t h ì X+    Y+ C.  Tín h  lũ y  đ ẳn g :  ( X+ ) +  =  X+   D .  Cá c  t ín h  c h ất  k h á c :   X+ Y+    ( XY) + ( X+ Y) +  =  ( XY+ ) +  =  ( X+  Y+ ) + X  → Y   Y+    X+ X  → X+   v à  X+   → X X+  =  Y+     X  → Y v à  Y  → X  17
  18. 5 . 3 . 4 .   Đ ỊN H LÝ BÀI TOÁN  THÀN H VIÊN 18
  19. 19
  20. 5 . 3 . 5 .   TÌM  BAO  Đ ÓN G  CỦA  TẬP   P H Ụ  THU ỘC  HÀM  D ỰA  TRÊN  BAO Đ ÓN G CỦA TẬP  THU ỘC TÍN H Ch o  l ược   đ ồ q u a n  h ệ R( Ω)  v à  t ập  p h ụ t h u ộc  h à m  F Th u ật  t o á n  t ìm  F+ B ước   1 :  Tìm   t ất   c ả  c á c   t ập   t h u ộc   t ín h   là   t ập   c o n   t h ực   s ự  c ủa   Ω. B ước   2 :  Tìm   b a o   đ ó n g   c ủa   t ừn g   t ập   t h u ộc   t ín h   c o n   c ủa   Ω  t ìm   đ ược   ở b ước  1 . B ước   3 :  D ựa   v à o   c á c   b a o   đ ó n g   c ủa   c á c   t ập   t h u ộc   t ín h   c o n   t ìm   đ ược   ở b ước  2   đ ể s u y  ra  c á c  p h ụ t h u ộc  h à m  t ro n g  F+ . 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2