Tài liệu Các lớp phụ thuộc lôgic tổng quát trong mô hình cơ sở dữ liệu quan hệ

MỤC LỤC Trang Lời mỏ* đầu. C h ư ơ n g 1. 4 C Á C Q U A N HỆ V À L Ớ P C Á C PH Ụ T H U Ộ C H À M 1.1. Q u an h ệ. 12 1.1.1. C á c k h á i n iêm . 1.1.2. Cơ sở 12 dữ liệu quan hệ. 1.1.3. C ác ph ép toán trên quan h ệ. 1.2. P h ụ th u ộ c d ữ liệ u . 20 1.2.2. L ư ợ c đ ồ quan h ệ. 21 1.3. C á c phụ th u ộ c hàm . 22 1.3.1. TÍnh ch ất của lố p cá c phụ th u ộ c h àm . 22 1.3.2. H ệ tiên đề A rm stro n g . 23 1.3.3. B a o đ ổ n g củ a tập c á c th u ộ c tín h . 25 Các 30 C h ư o n g 2. quan hệ Armstrong và phủ. L Ớ P C Á C PHỤ TH U Ộ C BO OLE II. 1. 15 19 1.2.1. C á c đ ịn h n g h ĩa . 1.4. 14 DƯ Ơ NG TỔNG QUÁT C á c đ ịn h n g h ĩa c ơ bàn. 11.2. C á c s u y d ẫ n các ph ụ 34 35 tron g lứ p thuộc Boole dương tồng quát. n.2.1. Định lý tương đương. 1 37 38 Trang n.2.2. Các suy dẫn. 38 II.3. Một vài kết quà về quan hệ Armstrong trong lớp các phụ thuộc boole dương tổng quát. 41 n.3.1. Sự tồn tại của các quan hệ Armstrong. 42 n.3.2. Một vài trường hợp riêng. 46 Chương 3. LÔGIC ĐA TRỊ VÀ LỚP CÁC PHỤ THUỘC LÔGIC DƯƠNG ĐÁ TRỊ 55 m.l. Các khái niệm về lôgic đa trị. 56 m.2. Một số tính chất của logic đa trị. 58 m.3. Các phụ thuộc lôgic đa trị trong mô hình dử liệu quan hệ. 66 III.4. Định lý tưcmg dưong. 76 m.5. Suy dần trong lứp các phụ thuộc lôgic đa trị . 79 IĨI.5.1. Biểu diễn các phụ thuộc trong dạng chuẩn tắc. 80 III.5.2. Sự suy dẫn đối với các phụ thuộc . dạng chuẩn tắc không chứa dấu phủ định. Chương 4ị IV, 84 CẤC QUAN HỆ ARMSTRONG VÀ PHỦ 1. Các quan hệ Armstrong trong lớp các phụ thuộc lôgic dương đa trị. IV, 1.1 Các khái niệm . 94 94 2 Trang IV. 1.2. Sự tồn tại cùa các quan hệ Armstrong. IV.2. Phủ trong lớp các phụ thuộc lôgic dương đa trị. 98 107 IV.2.1. Đặt vấn đề. 107 IV.2.2. Các khái niệm và các kết qủa về m-phủ. 107 IV.2.3. Mối liên hẹ giữa các phủ và các m-phù. 110 Lời kết luận. 115 Tài liệu tham khào 1i 9 3 LỜI MỞ ĐÂU Cơ s ở dữ liệu (CSDL) là lĩnh vực của tin học nhằm nghiên cứu các cơ chế, nguyên lý và phương pháp tồ chức dữ liệu trên các vật mang tin để khai thác cđ hiệu quả dữ liệu trong các hệ thống tin học ưng dụng cũng như trong các hệ lưu trữ và tra cưu thông tin . Như vậy cơ sớ dứ liệu chinh là một tập các dứ liệu về các đối tượng cần được quản lý, được lưu trữ trên các thiết bị mang tin cùa máy tính điện tử và được quản lý theo một cơ chế thống nhất nhằm thực hiện cớ hiệu quả các chtíc nâng sau đây: Tạo lập dữ liệu, cập nhật dữ liệu và khai thác dữ liệu . Đẻ tổ chức lưu trữ, quản lý và khai thác dữ liệu người ta thường sứ dụng mô hỉnh phân cấp, mô hình mạng và mô hình quan hệ. Trong số ba mô hình cho việc tồ chưc và khai thác các cơ s ở dữ liệu dd thỉ mô hình quan hệ được quan tâm hơn cả. Sớ dĩ mô hình quan hệ được quan tâm như vậy là vì nó được xây dựng trên một cơ s ở toán học chăt chẽ - đố là lỷ thuyết về các quan hệ cố áp dụng rộng rãi các công cụ đại số và lôgic. Trong CSDL quan hệ các quan hệ cố hình ảnh trực quan khá gần gũi vơi quan niệm của người sử dụng về các bàng biểu thông thường. Các ngôn ngữ thao tác trên CSDL quan hệ cd khà năng tồ hợp cao, dễ học và có hiệu quà. Việc cập nhật dữ liệu trong mô hình quan hệ khá dễ dàng không những thế n<5 còn cho phép đàm bảo được tính an toàn dữ liệu, tính nhất quán dữ liệu và tinh độc lập dứ liệu. 4 E. F. Codd là người đề xuất mô hình dữ liệu quan hệ năm 1970. Người ta xem cơ sớ dử liệu như là một tập hợp các quan hệ. Trong đố mỗi quan hệ cổ thể được hình dung trực quan như là một bảng chiĩ nhật gồm cđ các hàng và các cột. Ncíi đến một quan hệ trướx hết phải nổi đến tập thuộc tính của nổ - đố là một tập hữu hạn khác trống. Mỗi thuộc tính trong bàng chữ nhật . Mỗi được i/ng với một cột hàng trong bảng chứ nhật đổ được gọi là một bộ. Đối vơi các mô hình dứ liệu chđng đều có nhứng đòi hỏi giống nhau như đàm bảo tinh toàn vẹn dứ liệu tưc là không phát sinh các dứ liệu mâu thuẫn, không làm mất dữ liệu , đảm bảo tính độc lập của chương trình khai thác đối vơi tổ chức vật lý cụ thể của dữ liệu, đảm bảo sự tối ưu trong lưu trữ và khai thác v.v. Điều đáng ỉưu ý là khi dùng mô hỉnh quan hệ chúng ta cố thể dễ dàng diễn đạt các vấn đề trên một cách chặt chẽ. Sự quan tâm ở đây là nghiên ci/u cáẹ ràng buộc dữ liệu hay còn gọi là cẩc phụ thuộc dữ liệu trong mô hình quan hệ. Việc nghiên cứu các ràng buộc dữ liệu lần đầu tiên do E. F. Codd [11] đề xuất. Đố là một vấĩi đề cần thiết, cố ý nghĩa và giữ một vai trò quan trọng trong việc đảm bảo tính nhất quấn dữ liệu. đich của việc nêu ra khái niệm phụ thuộc dữ liệu Mục là nhằm bào đảm cho dử liệu trong cơ sớ dữ liệu không mâu thuẫn, phản ánh đũng thế giơi hiện thực, tránh được dư thừa. Thực tế là đa dạng và phong phđ do đổ cấc dữ liệu phàn ánh các đối tượng trong 5 thực tế cũng cd mối quan hệ đa dạng, phong phư và phức tạp. Cũng vì thế cần phải cố nhiều loại phụ thuộc dữ liệu khác nhau để đáp ưng phù hợp vơi tình hình thực tế. Phụ thuộc lôgic đầu tiên là phụ thuộc hàm 1970. Tiếp theo được gicíi thiệu bởi E. F. Codđ vào năm R. Fagin và Zaniolo đã đưa ra phụ thuộc đa trị vào năm 1976. Năm 1979 c . Beeri và J. D. Ullman đề xuất loại phụ thuộc kết nối. Cùng vơi sự phát triển của lớp các phụ thuộc hàm, một số loại phụ thuộc lôgic khác cũng được giới thiệu: Đó là phụ thuộc đối ngẫu, phụ thuộc mạnh, phụ thuộc yếu do J. Demetrovics và Gy. Gyepesy đề xuất năm 1981. Trong công trình của J. Berman and W.J. Blok [10] một lớp các phụ thuộc cân bằng được g i ớ i thiệu vào năm 1990. Lơp này cũng bao hàm lc?p các phụ thuộc hàm cũng như lơp các phụ thuộc Boole, lcíp các phụ thuộc Boole dương và một vài lơp phụ thuộc khác đa được đề cập đển trong các nghiên cứu của G. J. Demetrovics và Gy. Gyepesy [16,17]. Trong công trình Czedli , [35] năm 1992 các tác giả Nguyễn Xuân Huy and Lê Thị Thanh đề cập dến một số khái niệm và các kết quả cho lơp các phụ thuộc Boole dương tổng quát (PTBDTQ). Điều đáng lưu ý là lcýp này cững bao hàm lớp các phụ thuộc cân bằng. Mục tiêu của luận án là nghiên cứu phát triển lơp PTBDTQ , đề xuất một lơp phụ thuộc mơi đố là lơp các phụ thuộc lôgic duơng đa trị (PTLGDĐT). Lơp này là sự mờ rộng tự nhiên của lơp các PTBDTQ. Như vậy lơp phụ thuộc mơi này là sự 6 mớ rộng, bao hàm một số lơp phụ thuộc lôgic đa được nghiên CƯU. Do đố một số kết quà nghiên ci/u cho cấc Iơp trườc đây có thể sẽ được phát triển, mỏ1 rộng và xem xét trong dạng tổng quát hơn. Luận án bao gồm : Lời mờ đầu, 4 chương và phần kết luận, Chương 1- Các quan hệ và các phụ thuộc hàm dành cho việc trình bày một số khái niệm cơ bản về quan hệ, CO’ s ở dử liệu quan hệ. Trong chương này cũng đề cập đến một số khái niệm liên quan đến phụ thuộc dữ liệu nổi chung và một vài kièu phụ thuộc dữ liệu cụ thể. Phần tiếp theo của chương đề cập đến các phụ thuộc hàm, trình bày một tinh chất cơ bản cũng như một số vấn đề liên quan đến phụ thuộc hàm như hệ tiên đề Armstrong, tính xác đáng và đủ của hệ tiên đè Armstrong, bao đống của tập các phụ thuộc hàm, bao đớng của tập thuộc tinh, thuật toán tìm bao đống của tập thuộc tinh, các quan hệ Armstrong và phủ. Chương 2- L ớ p các phụ thuộc Boole dương tổng quát. Trong chương này ngoài việc giứi thiệu một số khái niệm cơ bản và phát biểu một số kết qủa chính trong công trình [35] của các tác giả Nguyễn Xuân Huy và Lê Thị Thanh cũng trình bày một vài kết quả mơi : Một số điều kiện cần và đủ cho các suy dẫn trong lợp các phụ thuộc Boole dương tổng quát. Kết quả đố là sự tổng quát hổa cùa một số phát biểu trong lốp cấc phụ thuộc hàm, phụ thuộc đối ngẫu,...Một số dạng suy dẫn và một số khẳng định liên quan 7 đến sự tồn tại của các quan hệ Armstrong cũng được trình bày trong chương này. Chương 3 - Lôgic đa trị và lơp các phụ thuộc lôgic dương đa trị. Trươc hết giơi thiệu một kiểu lồgỉc đa trị mà nó là sự mở rộng của kiểu lôgic hai trị thông thường. Một số khái niệm, tinh chất của lôgic đa trị và một số khía cạnh ứng dụng của lôgic đa trị vào việc nghiên cứu các phụ thuộc dữ liệu được trình bày. Dựa vào lôgic đa trị xây dựng được một lờp các phụ thuộc lôgic dương đa trị (PTLGDĐT) mà nổ nhận các lc?p phụ thuộc hàm, phụ thuộc đối ngẫu, phụ thuộc mạnh, phụ thuộc Boole đương tồng quát,... là nhứng lơp con của nố. Trong chương này cũng phát biểu và chững minh định lý tương đương trong lơp các PTLGDĐT. Đây là một định lý cố lợi. Dựa vào định lỷ tương đương ta cơ thể nhận được một số kết quả đáng chú ý ờ các phần tiếp theo. Cũng nhờ định lỷ tương đương, chương này sẽ đề cập một số kết quả liên quan đến sự suy đẫn trong lơp các PTLGDĐT. Trươc hết là trình bày khái niệm các công thức cớ dạng chuẩn tắc và chỉ ra rằng: Vời mỗi biểu thức lôgic chỉ chứa các biến lôgic và các liên kết lôgic A (hội ), V (tuyển) thì luôn luôn cố thể biều diễn được trong dạng chuẩn tắc. Trên cơ sớ đố một số điều kiện cần và đủ về tính dẫn được của các PTBDTQ tổng quát trong [35] được hơa và được mờ rộng cho lốp các PTLGDĐT. Mặt khác tứ một số kết qủa đạt được ta cổ thề thay thế việc nghiên 8 cứu tính dẫn được của các công thức f, g -> h trong đố f, g, h là các PTLGDĐT chỉ chi/a các biến lôgic và các liên kết lôgic A, V bới việc nghiên cifu tính dẫn được của các công thức f' , g' -> h' vơi f \ g \ h' là các PTLGDĐT chuẩn tắc không chưa các dấu phủ định. Chương 4- Các quan hệ Armstrong và phủ, dành cho việc trình bày một số kết quả liên quan đến các quan hệ Armstrong trong lơp các PTLGDĐT. Ngoài một số khái niệm, kết quả chfnh trong phần này là sự phát biểu và chưng minh điều kiện cần và đủ để một quan hệ là quan hệ m-Armstrong cho một tập các PTLGDĐT và tham số m cho trươx. Bên cạnh đổ cũng nêu một khẳng định là vơi một tập các PTLGDĐT và tham số m đa cho thì quan hệ m-Armstrong cho Tập các PTLGDĐT đố không phải luôn luôn tồn tại. Phần tiếp theo đề cập đến một số vấn đề liên quan đến phù. Bản luận văn đa đưa ra khái niệm về m-phủ và phử trong icíp các PTLGDĐT . Một số điều kiện cần và đù cho một phụ thuộc, một tập các phụ thuộc là m-dư thừa được phát biểu. quả tương tự cho phủ Những kết được trình bày, Trong đơ cũng phát biểu và chưng minh một điều kiện cần và đủ để một PTLGDĐT f cố suy dẫn được từ tập £ các PTLGDĐT mà không phụ thuộc vào tham số m. Một vài mối liên hệ giữa phủ và các m-phủ trong lớp các phụ thuộc lôgic đa trị cũng được nêu ra. Nói chung ở đây mời đề cập đến những khái niệm và một số kết quả ban đầư về phủ trong lơp các PTLGDĐT. Nhứng kết qủa 9 hay và sâu sắc về phủ trong lốp các thuộc hàm của các tác giả D. Maier, Hồ Thuần, Trần Thái Sơn,... Ià những gợi ý tốt để cố thể phát triển những kết quả mc?i tổng quát hơn khi nghiên ci/u về cấu tníc của phủ không dư và các phủ tối thiểu trong lớp các PTLGDĐT. Các kết qủa của tác giả trong luận văn được trình bày trong nứa cuối của chương 2 và hầu như toàn bộ các chương3,4. Nhứng kết quả trích dẫn của các tác giả khác kể tứ chương 2 đều được để trong ngoặc mđc vuông [ ] . Phần kết luận đành cho việc ttím tắt một số kết quà chinh đa đạt được và đề cập đến một vài khía cạnh cố thể phát triển nghiên cứu tiếp . Trươc hết GS TS Nguyễn tác giả tò Xuân Huy lòng biết ơn sâu sắc t(ýi đa hương dẫn nhiệt tình, truyền đạt những kinh nghiệm quý báu trong nghiên cứu khoa học , giảng dạy và dành tình cảm tốt đẹp cho tác gỉa trong những năm vữa qua. Tác giả xin chân thành biết ơn GS Nguyễn Quốc Toàn, GS Nguyễn Hữu Ngự, GS Đặng Huy Ruận, PTS Nguyễn Xuân My đa rất quan tâm, thường xuyên nhắc nhớ , động viên tác già hoàn thành luận án. Tác già cũng rất biết ơn sự giúp đỡ và những gợi ý rất cố ý nghĩa cùng vời những tình cảm quý báu của 10 GS Hồ Thuần, TS Nguyễn Cát Hồ, GS Phạm văn At GS TS Đỗ Long Vân, GS Lê Tiến Vương, trong quá trình nghiên ci/u cũng như trong khi làm bản luận văn này. Tác giả xin cảm ơn những tình cảm tốt đẹp của GS Đỗ Đưc Giáo, GS Hồ Sĩ Đàm , PTS Nguyễn Tuệ , PTS Trịnh Nhật Tiến , PTS Hoàng Chí Thành, PTS Đỗ Trung Tuấn đã cổ những gổp ý quý báu cho nội dung của bản luận vãn. Nhân dịp này tác giả xin cám ơn toàn thể các anh và bè bạn ở bộ mòn Tin học, viện Tin học -Điện tứ và Khoa Toán -Cơ Tin Học trường Đại học tồng hợp Hà nội. Tác già chân thành cám ơn Ban Giám hiệu, Ban Chủ nhiệm khoa Toán - Cơ Tin học, Phòng Đào tạo Sau đại học, Phòng Tạp chi và các Phòng chư'c năng khác đã gitfp đỡ và tạo điều kiện thuận lợi cho tác giả hoàn thành bàn luận văn này. Còn nhiều ngưôi khác cũng rất quan tâm giiíp đỡ và động viên tác giả hoàn thành bản luận văn. Nhân dịp này, tác giả xin chân thành cảm ơn tất cả những tình cảm quỷ báu đđ. 11 C hương 1 CẤC QUAN HỆ VÀ LƠP CÁC PHỤ THUỘC HÀM 1 . 1 . C Ấ C QUAN HỆ. 1.1.1. Cấc khái niệm. Cho u = {A i,A 2 ,...,AnỊ là một tập hiĩu hạn khác trống. Các phần tử của u được gọi là các thuộc tính . v ơ i mỗi thuộc tính A[ , 1< i < n cố một tập dj nào đđ gồm ít nhất hai phần tử được gọi Jà miền trị của thuộc tính đố. Với A € u miền trị của A cưng được ký hiệu là dom(A). Một quan hệ R trên u là một tập con R hứu hạn của tich d i X ky hiệu ỏ2 X ... X dn. Tập tấ t cả các quan h ệ trên u được là REL(Ư). Mỗi phần tứ trong R được gọi là một bộ. Các ký hiệu cơ bàn: Theo truyền thống của lý thuyết cơ sờ dứ liệu, chđng ta chấp nhận các quy định sau đây : Các thuộc tinh được kỷ hiệu bằng chứ latin hoa đầu bảng A, B,C,...Nổi đến một tập các thuộc tinh là nối đến một tập con nào đố của tập thuộc tinh u. Ta sử dụng các chứ latin hoa X,YjZ... ử cuối bảng để kỷ hiệu các tập thuộc tinh. Các thuộc tính trong một tập được liệt kê như là một xâu kỷ tự, 12 chẳng hạn thay cho cách biểu diễn thông thường một tập các thuộc tính X={A,B,C} ta cđ thể viết X = ABC. Nếu X, Y là hai tập thuộc tinh thì dùng kỷ hiệu XY để biểu diễn hợp và X-Y để biểu diễn hiệu của các tập một quan X và Y. C ắ c bộ trong hệ được biểu diễn bằng chữ ]atin nhỏ t, u, V , .. . Giả sử t € R và A e u khi đố ta ký hiệu t.A là giá trị của bộ t đối vời thuộc tính A. Vời tập X ç u, ta đặt t.x là tập { t.A ỊA €X }. Thi dụ 1.1. Xét quan hệ s v (sinh viên) như sau : s V(MSV,HT,NS,QUE,ĐV) MSV (mã sinh viên), QUE (quê quán), cđ các thuộc HT (họ và tên), NS tinh là : (năm sinh), trong đd miền trị của chưng cơ thể khai báo như sau : dom(MSV) : 0..99 (tập các số nguyên dương không c ó quá hai chi? số ), dom(HT) : A(25) (tập các xâu ký tự trên một bảng chữ cho trươx gồm không quá 25 ký tự ), dom(NS) : 0..99 (là tập các số nguyên dương không quá 2 chtĩ số), đom(QUE): A(15) (tập các xâu ký tự trên một bảng chứ cho trươc mà chiều dài của xâu là không quá 15 ). Một bộ t của quan hệ s v cố thể viết ờ một trong hai dạng sau: < MSV:04 ,HT : Đỗ Quang Thành, NS: 76,QUE : Nam Hà > hoặc đơn giản hơn t=<04, Đỗ Quang Thành,76,Nam Hà>. về mặt trực quan, một quan hệ cđ thể biểu diễn như một bảng hai chiều, các cột là các thuộc tinh, các dòng là các bộ . 13 MSV HT NS QUE ) 06 Lê Hải Đăng 78 Hà Nội 04 Đỗ Quang Thành 76 Nam Hà 08 Nguyễn Tiến 79 Thái BÌnh 09 Vũ Thu Hằng 75 Hà Bắc 1.1.2. Cơ sớ dứ liệu quan hệ. Dứ liệu được lưu trử theo nhứng cách thurc nhất định trên các thiết bị mang tin của hệ thống máy tinh và đưcỵc thay đổi theo thời gian gọi là cơ sờ dứ liệu. Một cơ sử dử liệu bao gồm một tập hứu hạn các quan hệ được gọi là cơ sd dữ liệu quan hệ, viết tắt là CSDLQH hoặc viết gọn hơn trong tài liệu này là CSDL. Như vậy mỗi một quan hệ cố thể cổ sự thay đổi về số lượng và nội dung cấc bộ theo từng thời gian để phản ánh điíng những biến đổi của đối tượng trong thực tiễn . Hệ tháng phần mềm giiíp chúng ta quán xuyến toàn bộ việc tạo lập, cập nhật và khai thác cơ sớ dữ liệu quan hệ được gọi là hệ quản trị cơ sở dử liệu quan hệ . Một số thao tác đối vơi CSDL: Các thao tấc trên CSDL đều nhằm thực hiện cd hiệu quà một trong những chiic nãng sau đây: Tạo lập nhđng quan hệ mơi, cập nhật dữ liệu và cuối cùng là khai thác thông tin từ CSDL. 14 Đê dữ liệu trong một CSDL phàn ánh đứng đối tượng thực mà nđ quản lý, đương nhiên cần phải cố thao tác cập nhật đối vối mỗi CSDL. Thao tác cập nhật đối vcíi cơ sớ dữ liệu thực chất là thực hiện việc cập nhật dứ liệu trên từng quan hệ của CSDL. Việc cập nhật đố bao gồm : Bổ sung những bộ mơi vào quan hệ, loại bỏ đi một số bộ của quan hệ hoặc là loại bỏ chính bản thân quan hệ đố, điều chỉnh nhứng thông tin chưa chinh xác ớ các bộ... Chư'c năng quan trọng nhất của CO' sở diĩ liệu là khai thác dữ liệu đã được lưu trữ một cách cố hiệu quả. Điều đơ cố nghĩa là việc tạo lập các quan hệ cũng như việc cập nhật dứ liệu đều nhằm vào mục đích lưu trứ những thông tin sở CO’ để từ đtí ta cớ thể rút ra được những thông tin mời cố ý nghĩa ho’n. Trên CO’ sớ đố ta c ó thể trả lời được được một số câu hỏi ctí ỷ nghĩa xuất phát tứ yêu cầu của thực tế sinh động hoặc là từ đ ó ta cũng cố thể đề xuất ra những quyết định mcíi đúng đắn. v ì thế mà chúc năng khai thác dữ liệu chủ yếu ỉà chi/c năng tìm kiếm. 1.1.3. Cấc phép toán trên quan hệ. Như ta đa biết mỗi câu hỏi tìm kiếm thông tin thường dược thể hiện thông qua Trong đớ một biểu thức quan hệ nào đ(5. mỗi một hạng thức là một quan hệ còn các phép toán tác động trên chúng chính ỉà các phép toấn quan hệ quen biết trong lỹ thuyết cơ sd dứ liệu quan hệ. Đố chinh là phép 15 hợp, phép giao, phép chiếu, phếp kết nối,... đối vơi các quan hệ . Các phép đổ được định nghĩa như sau : Phép chọn. Cho t là một bộ trong quan hệ R và E là một biểu thtfc lôgic phát biểu trên tập các thuộc tính của quan hệ R. Ta ndi bộ t thỏa man biểu thức E, kí hiệu là t(E) nếu sau khi thay mọi thuộc tính A trong E bằng giá trị t.A ta được một công thức lôgic nhận giá trị đứng. Cho quan hệ ReREL(U) và biểu thức chọn E trên u. Phép chọn quan hệ R theo điều kiện E cho ta một quan hệ p trên tập thuộc tính Ư sao cho p gồm và chỉ gồm các bộ của R thỏa biểu thtfc logic E. Vậy p = { t € R I t(E) }. KÍ hiệu p = R(E). Phép chiếu. Cho quan hệ R.€REL(U) và tập thuộc tinh X £ u. Phếp chiếu quan hệ R trên X cho ta quan hệ p C(5 tập thuộc tính là X và xác định p bởi p = { t.x Ịte R}. Ki hiệu p = R[XJ. Phép kết nối. Cho hai quan hệ R(X) và S(Y). Phép kết nối tự nhiên hai quan hệ R và s cho ta quan hệ p vơi tập thuộc tinh XY và các bộ được xác định như sau : p = {t I t.x € R và t.Y e KÍ hiệu p = R * s. 16 S}. Tich Descartes. Cho các tập thuộc tính X, Y vơi X n > Ỵ = 0 và hai quan hệ R(X) và S(Y). Ký hiệu là bộ được hình thành bằng cách ghép bộ V vào bộ u. Ta cố thể định nghĩa tich Descartes của hai quan hệ R và s là một quan hệ p được xác định như sau : p = { I u e R , V e S}. Kỷ hiệu p = RxS. Hai quan hệ cố cùng tập thuộc tính được gọi là tương thích . Vơi các quan hệ tương thích, ta cơ thể định nghĩa cấc phép toán hợp, giao, hiệu trên tập các quan hệ tương tự như các định nghĩa hợp, giao, hiệu trong lỷ thuyết tập hợp. Cụ thế là Phép hợp. Hợp cùa hai quan hệ tương thích R(X) và S(X) là một quan hệ p vơi tập thuộc tính ]à X. Quan hệ p gồm và chỉ gồm những bộ t sao cho t e R hoặc t € s . p = Ịt I t Phép giao. E R hoặc t € S}. Kỷ hiệu p = R + s. Giao của hai quan hệ tương thich R(X) và S(X) là một quan hệ Q vơi tập thuộc tinh là X.Quan hệ Q gồm và chỉ gồm những bộ t sao cho t G R và t G s . Q = {t I t e R và t e S}. Ký hiệu p = R.s. Phép hiệu. Hiệu của hai quan hệ tương thích R(X) và S(X) là một quan hệ p v ờ i tập thuộc tính là X. Quan hệ p gồm và chỉ gồm nhứng bộ t sao cho t € R và t Ể s. 17 Vậy p = {t I t Ẽ R và t Ể SỊ. Kỷ hiệu p= R-S Phép chia. Cho hai quan hệ R(X) vã S(Y) vời X Đặt M = X-Y. Khi đổ phép chia quan hệ Rcho Y. quanhệslà một quan hệ Q vơi tập thuộc tính là M và các bộđược xác định như sau: Q ={u.M|u G R và (Vv € S)( € R)Ị. Ki hiệu p = R -ỉ- s Phép chọn-chiếu. Cho quan hệ Re REL(U), X Ç u và một biểu thức chọn E trẽn u. Phép chọn-chiếu quan hệ R theo điều kiện E trên tập thuộc tinh X cho ta một quan hệ p trên tập thuộc tính X sao cho p gồm và chỉ gồm các bộ t.x vời điều kiện t e R và Vậy p = { t.x I t thỏa biểu thi/c lôgicE. t G R và t(E) }. Ki hiệu p = R(E,[X]). Nhở c á c phếp toán quan hệ ta c ố thể nhận được nhứng quan hệ mời tứ cấc quan hệ đã cho. Như vậy khi tạo lập các quan hệ cũng như khi khai thác dứ liệu thường dẫn đến những quan hệ mơi. Trong các quá trình đố rất dễ gây ra những sai sổt thiếu chính xác đối vơi dữ liệu cần lưu trữ. Không nhiĩng thế bản thân dữ liệu phải chứa đựng tính hợp lÿ của nổ, hay nối cách khác dữ liệu cần phài thỏa mãn những ràng buộc nào đ(5 để phản ánh đứng thế giời hiện 18 thực. VÍ dụ không thể cơ một sinh viên tại một thời điểm vứa dự xêmina ở giảng đường vữa thực hành ở phòng máy. 1 .2 . PHỤ THUỘC D ữ LIỆU. Một vấn đề là làm thế nào để hạn chế được những bất hợp ly của dứ liệu được phát sinh ra trong quá trinh tạo lập hoặc khai thác dữ liệu. Đê đáp i/ng yêu cầu đổ, một Iỷ thuyết mơi được đề cập đđ là lý thuyết về các phụ thuộc dữ liệu. Nối đến phụ thuộc dứ liệu ỉà nối đến những ràng buộc, quy định mà dứ liệu trong một cơ s ở dữ liệu phải thỏa mãn. Mục đích của việc đặt ra các ràng buộc đđ là phải nhằm bảo đảm cho dư liệu trong cơ sở dứ liệu phản ánh đung thế gicn hiện thực. Các ràng buộc đữ liệu thường được mô tà khi tạo ỉập quan hệ. Các hệ cơ sờ dử liệu cần cđ cơ chế phục vụ cho việc mô tà các ràng bufrc dữ liệu và quảnlý các ràng buộc đã mô tả. Các cơ chế này cho phép ta kiểm tra dứ liệu khi nhập vào cơ sd dữ liệu và các dữ liệu được phát sinh trong các quá tnnh xứ lý và cập nhật . Mục đich của việc kiểm tra là để xem dữ liệu cổ thỏa mãn các ràng buộc đã nêu hay không. Tất nhiên là cd nhiều loại ràng buộc khác nhau và mỗi loại đều đòi hỏi một công cụ và loại hình quàn lỷ phù hợp. Xuất phát tứ thực tế sinh động , một số loại phụ thuộc dứ liệu đã được đề cập đến nhằm làm đảm bảo cho dử liệu 19 lưu trứ là phù hợp , phản ánh đứng các đối tượng thực tế. Sau đây chưng ta sẽ đề cập đến một vài loại phụ thuộc đáng quan tâm và nêu các khái niệm liên quan đến các loại phụ thuộc đổ. 1.2.1. Cấc định nghĩa. loại Trong phần này ta sẽ đề cập đến khái niệm của một số phụ thuộc lôgic đã được các chuyên gia quan tâm tử nhiều năm và cho đến nay những phụ thuộc đtí vẫn còn là vấn đề cần nghiên cứu tiếp. Đ(5 là cấc phụ thuộc hàm, phụ thuộc mạnh, phụ thuộc yếư, phụ thuộc đối ngẫu. Định nghĩa 1.1. Phụ thuộc hàm : Cho X, Y là các tập con của tập các thuộc tinh Ư. Một phụ thuộc hàm ( viết tắt là PTH) là một phát biểu dạng X — » Y. Nối rằng quan hệ R € REL(U) ià thỏa män PTH X - F-> Y nếu vơi mỗi cặp bộ u,V e R mà u ,x = v .x thì cũng có U.Y = V.Y. Hay nđi cách khác, quan hệ R thỏa mãn PTH X — > Y nếu vơi hai bộ u,V bất kỳ của R mà chưng giống nhau trên X thì chung cũng phải giống nhau trên Y. Phụ thuộc đối ngẫu: Cho X,Y Œ u. Một phụ thuộc đối ngẫu (viết tat là PTĐN) là một phát biểu dạng X D > Y. Nđi rằng quan hệ R e REL(U) là thỏa mãn PTĐN X —5—» Y nếu vơi mỗi cặp bộ u,v G R 20 mà chứng giống nhau tại một