Đề tài Phân tích các dạng chuẩn hoá dữ liệu trong mô hình quan hệ và một số thuật toán

LỜI GIỚI THIỆU Ngày nay, mọi ngành, mọi lĩnh vực trong đời sống, trong khoa học kinh doanh cũng như trong mọi mặt vận động của xã hội dưới mọi quy mô từ xí nghiệp nhà máy, công ty đến quốc gia, quốc tế đều đã áp dụng công nghệ thông tin vào quản lý và nhiều lĩnh vực khác như: điều khiển các quá trình sản xuất, điều khiển tự động, trợ giúp quyết định, thương mại điện tử ... Môn cơ sở dữ liệu là một trong những môn quan trọng liên quan đến các vấn đề thu thập, xử lý và cho những thông tin cần thiết từ dữ liệu. Mục tiêu chính của môn này là đưa ra các phương pháp để tổ chức thông tin làm sao cho tối ưu nhất các khâu trên của dữ liệu[3]. Để tiến hành các mục tiêu trên, người ta đi xây dựng các mô hình dữ liệu, và trên cơ sở mô hình dữ liệu này người ta đi xây dựng các hệ cơ sở dữ liệu. Từ các mô hình này, nhân loại đã đạt được nhiều thành công rực rỡ trên lĩnh vực này mà sản phẩm của nó được thương mại hoá trên khắp thế giới như: Foxbase, Foxpro, DBase, Access, SQL for Windows,... Lý thuyết cơ sở dữ liệu nguyê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. Trong số các mô hình cho việc tổ chức và khai thác cơ sở dữ liệu (CSDL), trên thực tế mô hình quan hệ [6] là được quan tâm hơn cả. Bởi vì mô hình này được xây dựng trên cơ sở lý thuyết và các quan hệ có cơ sở toán học chặt chẽ, xử dụng rộng rãi các công cụ đại số và logíc. Trong cơ sở dữ liệu quan hệ, các quan hệ có hình ảnh trực quan như là các bảng biểu thông thường mà ta hay gặp. Điều đó tạo nên những thuận lợi trong việc thực hiện các thao tác trên các quan hệ, các ngôn ngữ thao tác trên cơ sở dữ liệu quan hệ có khả năng tổ hợp cao và hiệu quả. Việc cập nhật dữ liệu trong mô hình quan hệ khá dễ dàng. Điều đáng quan tâm là cơ sở dữ liệu quan hệ 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à tính độc lập dữ liệu [5]. Trong quá trình nguyên cứu và xử lý bảng biểu, các bảng này do các chuyên gia trong lĩnh vực tin học đề xuất ra, trong những năm 1970, người sáng lập ra mô hình dữ liệu quan hệ đã đề xuất ra 4 dạng chuẩn để chuẩn hoá các tệp dữ liệu (các bảng biểu). Nhờ các dạng chuẩn này, khi xử lý các tệp dữ liệu người ta tách được dữ liệu gốc ( do các chuyên gia trong mọi lĩnh vực đề xuất ra ). Vì thế các tệp dữ liệu con đã ở trong dạng chuẩn rồi và khi xử lý người ta lưu trữ các tệp dữ liệu con trong máy chứ không phải là các tệp dữ liệu lớn, nhưng một điều rất quan trọng là, để khỏi mất mát thông tin ( có tính pháp lý ) thì phải phục hồi tệp gốc ở bất cứ thời điểm nào cần, muốn hồi phục được người ta phải dùng phép nối tự nhiên nối tất cả các tệp dữ liệu con thì ta sẽ được tệp dữ liệu gốc lớn. Việc lưu trữ các tệp dữ liệu con thường chiếm ít bộ nhớ hơn các tệp dữ liệu gốc to, tốc độ chuẩn hoá các tệp dữ liệu đã được chuẩn hoá nhanh hơn rất nhiều các tệp dữ liệu chưa được chuẩn hoá ( tệp dữ liệu gốc to). Nhờ có những đóng góp như vậy mà người sáng lập ra đã được nhận giải thưởng Turing[3]. Cho đến nay tất cả các hãng máy tính trên thế giới khi xây dựng Mô hình dữ liệu quan hệ ( xử lý các tệp dữ liệu ) đều đã áp dụng các phụ thuộc hàm và các dạng chuẩn trong ngôn ngữ sử lý của họ, trong đó đặc biệt là phép kết nối tự nhiên . Mục tiêu của luận văn là tập chung nghiên cứu các tính chất của phụ thuộc hàm và các dạng chuẩn của mô hình dữ liệu quan hệ. Nội dung chính của đề tài được trình bày trong 4 chương Chương 1: Tổng quan về cơ sở dữ liệu Chương 2: Giới thiệu về phụ thuộc hàm và một số tính chất của chúng Chương 3: Các dạng chuẩn hoá dữ liệu trong mô hình quan hệ và một số thuật toán của chúng Chương 4: Cài đặt một số chương trình thực hiện cho thuật toán đã nêu trên. Trong thời gian hoàn thành bản luận văn tốt nghiệp, em xin chân thành cảm ơn khoa CNTT và các thầy cô giáo đã giúp đỡ và truyền đạt cho em những kiến thức cơ bản trong những năm học vừa qua. Đặc biệt em xin chân thành cảm ơn thầy Đoàn Văn Ban - Viện CNTT đã tận tình giúp đỡ và chỉ dẫn cho em những kiến thức và phương pháp làm việc để em hoàn thành bản luận văn tốt nghiệp. CHƯƠNG I : TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU I.1. KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU Để lý giải cho các khái niệm, trước hết chúng ta hãy xem xét hệ thống bán xe máy của công ty HONDA Việt Nam bằng máy tính. Dữ liệu lưu trữ trong máy tính bao gồm thông tin về hành khách, loại xe, phân khối và giá cả .... Mọi thông tin về mối quan hệ này được biểu diễn trong máy thông qua việc đặt mua xe của khách hàng.Vậy làm sao để biểu diễn dữ liệu đó và bảo đảm cho khách hàng mua đúng chiếc xe mà mình đăng kí. Những dữ liệu nêu trên được lưu trữ trong máy theo một quy định nào đó được gọi là cơ sở dữ liệu (CSDL). Phần chương trình để xử lý, thay đổi số liệu này là các hệ quản trị cơ sở dữ liệu [6]. Tổng quát chúng ta có các định nghĩa sau : 1. Cơ sở dữ liệu: Là khối dữ liệu phản ánh thông tin được lưu trữ trên hệ thống theo một cấu trúc nào đó gọi tắt là cơ sở dữ liệu ( CSDL ). 2. Hệ quản trị cơ sở dữ liệu: Là một hệ thống phần mềm quản lý cơ sở dữ liệu và tập các thao tác xử lý dữ liệu. Hệ quản trị cơ sở dữ liệu là rất quan trọng, như là một bộ diễn dịch với ngôn ngữ bậc cao nhằm giúp người sử dụng có thể dùng được hệ thống mà ít nhiều không cần quan tâm đến thuật toán chi tiết hoặc biểu diễn ở trong máy. 3. Chức năng của hệ quản trị cơ sở dữ liệu a. Thiết lấp cơ sở dữ liệu : Gồm các giai đoạn - Khai báo - Định nghĩa - Nạp dữ liệu vào cơ sở dữ liệu b. Cập nhật dữ liệu: - Bổ sung dữ liệu vào cơ sở dữ liệu, - Loại bỏ dữ liệu khỏi cơ sở dữ liệu, - Sửa dữ liệu trong cơ sở dữ liệu. c. Khai thác dữ liệu trong cơ sở dữ liệu - Tìm kiếm thông tin theo yêu cầu, - Kết xuất thông tin theo yêu cầu. I.2. KHÁI QUÁT CHUNG VỀ MÔ HÌNH DỮ LIỆU Thông thường việc thiết kế và xây dựng các hệ thống thông tin quản lý, chúng ta cần xử lý các tệp (tệp ) dữ liệu, các tệp này bao gồm nhiều bản ghi ( record ) và có cùng cấu trúc xác định. Đồng thời, mỗi bản ghi được phân chia thành các trường dữ liệu. Mỗi cơ sở dữ liệu là một hệ thống các tệp dữ liệu , mỗi tệp này có cấu trúc bản ghi khác nhau . Mỗi hệ quản trị cơ sở dữ liệu là một hệ thống quản lý và điều hành các tệp dữ liệu. Trong quá trình thiết kế và xây dựng các hệ quản trị cơ sở dữ liệu, người ta tiến hành xây dựng các mô hình dữ liệu. Mô hình dữ liệu phải thể hiện được bản chất mối quan hệ cơ bản của các dữ liệu mà dữ liệu này phản ánh các mối quan hệ và các thực thể trong thế giới thực. Có thể thấy mô hình dữ liệu phản ánh khía cạnh cấu trúc logíc mà không đi vào khía cạnh vật lý của cơ sở dữ liệu. Yếu tố quan trọng nhất của cấu trúc cơ sở dữ liệu là dạng cấu trúc dữ liệu lưu trữ được mô tả. Có thể thấy rằng loại dữ liệu nền tảng của việc mô tả các mối quan hệ là loại bản ghi. Bởi vì các ràng buộc giữa các loại bản ghi tạo ra bản chất cấu trúc cơ sở dữ liệu. Vì thế dựa trên việc xác định các ràng buộc giữa các loại dữ liệu được cho như thế nào mà chúng ta phân loại các mô hình dữ liệu. Có nghĩa là từ cách nhìn của người sử dụng việc mô tả các dữ liệu và các ràng buộc giữa các dữ liệu được thực hiện như thế nào. Hiện nay đã có nhiều loại mô hìmh dữ liệu. Bốn loại mô hình dữ liệu đang được sử dụng rộng rãi là: Mô hình phân cấp, Mô hình mạng, Mô hình quan hệ, Mô hình hướng đối tượng. I.2.1. Mô hình phân cấp [6] Mô hình dưc liệu là một cây, trong đó các nút biểu diễn các tập thực thể, giữa các con và nút cha được liên hệ theo một mối quan hệ xác định ( Dựa trên cấu trúc cây) Ví dụ hình sau: Gốc Alà thực thể lớn, ta chia thực thể A làm 3 thực thể nhỏ hơn là B,C,D. Trong đó thực thể B ta lại chia ra làm 3 thực thể nhỏ hơn là G,H,I, tương tự C có hai thực thể nhỏ là K và L, và D có 3 thực thể nhỏ là M,N và P B D C G H I K L M N P A I.2.2. Mô hình mạng [6] Mô hình biểu diễn là một đồ thị có hướng ( Cấu trúc đồ thị ) A B D C E Ví dụ: Mô tả cho mô hình dữ liệu mạng: Cho 5 đỉnh A,B,C,D,E. Các đỉnh này nối với nhau bởi các đường, trong đó đỉnh A gọi là tệp dữ liệu lớn được phân chia thành các tệp dữ liệu nhỏ hơn. Tương tự ta có các đỉnh tiếp theo được thể hiện giống như đỉnh A và chúng được biểu diễn như hình trên. I.2.3. Mô hình quan hệ [6] Mô hình này dựa trên cơ sở khái niệm lý thuyết tập hợp của các quan hệ, tức là tập các k _ bộ với k là cố định, các ràng buộc trên được thể hiện qua các quan hệ (bảng ). I.2.4. Mô hình hướng đối tượng Hệ thống được xem như là tập các thực thể ( Đối tượng ), tác động qua lại với nhau thông qua các thông báo để thực hiện các nhiệm vụ đặt ra. Đây là mô hình mới đang được tập trung nghiên cứu và phát triển ứng dụng. Trong 4 loại mô hình trên thì mô hình quan hệ có nhiều ưu điểm và được nhiều người quan tâm hơn cả, bởi lẽ mô hình dữ liệu quan hệ có tính độc lập dữ liệu rất cao, lại rễ sử dụng. Điều quan trọng hơn cả là mô hình quan hệ được hình thức hoá toán học tốt, do đó được nghiên cứu, phát triển và cho được nhiều kết quả lý thuyết cũng như ứng dụng trong thực tiễn . Mô hình dữ liệu quan hệ là một mô hình rất tiện lợi để mô tả cấu trúc Logíc của các cơ sở dữ liệu. Như vậy, ở mức logíc mô hình bao gồm các tệp được biểu diễn dưới dạng các bảng. Do đó đơn vị cơ sở dữ liệu quan hệ là một bảng, trong đó các dòng của bảng là các bản ghi dữ liệu cụ thể ( đó là các thể hiện cụ thể của các bản ghi ) còn tên các cột trong bảng là các thuộc tính. Trên cơ sở mô hình dữ liệu quan hệ, đến nay đã phát triển thêm một số loại mô hình khác nhau nhằm mô tả và thể hiện thế giới thực một cách chính xác và phù hợp như mô hình quan hệ thực thể ( Entily Relationship Model), mô hình dữ liệu hướng đối tượng ( Object Oriented Model ),... Theo cách nhìn của người sử dụng thì một cơ sở dữ liệu quan hệ là một tập các bảng biến đổi theo thời gian. Với ưu điểm về tính cấu trúc đơn giản và khả năng hình thức hoá phong phú cơ sở dữ liệu quan hệ dễ dàng mô phỏng các hệ thống thông tin tiết kiệm có tính độc lập cao, dễ sửa đổi, bổ xung cũng như khai thác dữ liệu. Mặt khác, việc khai thác và áp dụng kĩ thuật tổ chức và sử dụng bộ nhớ cho phép cài đặt các cơ sở dữ liệu quan hệ đem lại hiệu quả cao và làm cho cơ sở dữ liệu khẳng định được ưu thế của mình trên thị trường. CHƯƠNG II : CÁC PHỤ THUỘC HÀM Đặt vấn đề: - Khái niệm thực thể: Là đối tượng có trong thực tế mà chúng ta cần khảo sát và giải quyết nhiều vấn đề liên qua đến đối tượng này. Ví dụ: Thực thể sinh viên, thực thể con người, thực thể hệ thống kế toán tài vụ ,... Thông thường người ta chia các thực thể lớn thành các thực thể đơn giản hơn và đến khi một thực thể được mô tả bàng một tệp dữ liệu. Hệ thống quản lý công chức Hệ thống công chức do ban tổ chức cán bộ chính phủ Hệ thống công chức do ban tổ chức TW Các bộ, ngành Tỉnh, Huyện Tổng công đoàn Hội phụ nữ Các ban - Các thuộc tính: Là đặc trưng của một thực thể. Các thuộc tính dùng để phân biệt thực thể đó với thực thể khác. Ví dụ: Thực thể sinh viên có các thuộc tính sau :Mã_SV, Họ_tên, Giới_tính, Nơi_sinh, Quê_quán ... Nếu một thực thể được mô tả bằng một tệp dữ liệu thì các thuộc tính được mô tả bằng các trường dữ liệu. Như vậy thực thể là một bảng thì thuộc tính là một cột trong bảng đó. - Thể hiện của một thực thể: Một mô tả cụ thể của thực thể đó. Nếu thực thể là một tệp dữ liệu thì thể hiện là một dòng ( bản ghi ) của tệp dữ liệu đó . Từ ví dụ thực thể Sinh viên trên chúng ta mô tả một cách tổng quát các thuộc tính của thực thể. Mã_SV Họ tên Giới tính Năm sinh Quê quán 01 Nguyễn văn Giang Nam 01-01-1977 Phú thọ 02 Nguyễnviệt Cường Nam 12-5-1974 Vĩnh phúc 03 Phan Hoa Nữ 13-7-1978 Hà tĩnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Hoàng quốc Khanh Nam 12-6-1976 Hà nội Dễ thấy rằng thực thể sinh viên trên chính là tệp dữ liệu mô tả về thông tin của các Sinh viên của một trường nào đó, với năm thuộc tính cụ thể gồm: Mã_sv, Họ_tên, Giới_tính, Năm_sinh, Quê_quán. Trong tệp dữ liệu trên có 20 bản ghi. II.1. PHỤ THUỘC HÀM II.1.1. Khái niệm về phụ thuộc hàm Trên cơ sở nghiên cứu tệp dữ liệu người ta định nghĩa chính xác tệp dữ liệu như sau ( đôi khi người ta còn gọi là quan hệ ). Cho trước R = { a1, a2,..., an } là tập hữu hạn và không rỗng, nó được gọi là tập các thuộc tính. Mỗi thuộc tính ai ( i = 1,2,...,n ) là một miền giá trị D(ai ) và D(ai) có thể trùng nhau được. Khi đó r = { h1,h2,...,hm } được gọi là các tệp dữ liệu quan hệ nếu h: R®È D, ai ÎR(aI) Với điều kiện hj( ai ) Î D(aI) Ví dụ: Sinh viên = {Mã_sv, Họ_tên,....} Với định nghĩa này chúng ta lập được một bảng tương đương sau: a1 a2 ... an h1(a1) h1(a2) ... h1(an) h2(a1) h2(a2) . .. h2(an) . . . . . . . . . . . . hm(a1) hm(a2) . . . hm(an) Định nghĩa này là quan trọng nhất và nó là hạt nhân của mô hình cơ sở dữ liệu quan hệ. Vì h1, h2, ..., hm là các thành phần trong tập hợp của tệp dữ liệu nhở. Một hạn chế là không chấp nhận có hai dòng giống nhau trong một tệp dữ liệu, có nghĩa là: " i ¹ j Þ hI ¹ hj . Đứng về khía cạnh sử dụng, một hệ cơ sở dữ liệu quan hệ đó là một tập hợp các tệp dữ liệu được định nghĩa như sau: Một hệ cơ sở dữ liệu là một tập hợp hữu hạn các tệp dữ liệu đã được định nghĩa ở trên và chúng được thay đổi theo thời gian. Đây là hệ cơ sở dữ liệu quan hệ. II.1.2. Định nghĩa phụ thuộc hàm Cho trước R = { a1, a2,..., an }là tập các thuộc tính và r = { h1, h2, ..., hm }. Giả sử A,B Í R. Khi đó ta nói rằng B phụ thuộc hàm vào A hoặc A xác định hàm vào B : Nếu mọi hi, hj Î r ta có ( a ÎA mà hi(a) = hj(a)) => ( bÎB ( hi(b) = hj(b))) Þ A®B Có thể thấy rằng, B mà phụ thuộc hàm vào A nếu hai dòng bất kỳ mà các giá trị của tập thuộc tính A bằng nhau từng cặp một thì kéo theo các giá trị trên tập thuộc tính B cũng phải bằng nhau từng cặp một. Ví dụ: Trong quan hệ Xe_máy có các thông tin về số xe, mác của xe, màu của xe, giá xe, năm sản xuất. Số xe Mác Màu Giá Năm sản xuất 100 Honda Đỏ 500 1996 300 Dream Mận 700 1998 500 Wave Xanh biển 1000 1999 Theo định nghĩa, trong quan hệ trên, nếu số xe xác định màu xe thì khi biết số xe người ta biết ngay được màu của xe, giá trị về màu này là duy nhất. Số xe ® Màu Số xe ® Giá Mác ® Giá Định nghĩa phụ thuộc hàm là rất quan trọng, nó nói lên mối quan hệ ngữ nghĩa trong nội bộ một tệp dữ liệu. Mối quan hệ ngữ nghĩa này được thể hiện giữa các tập cột. Ngoài phụ thuộc hàm ra, hiện nay người ta đã phát hiện ra trên ba mươi loại phụ thuộc dữ liệu. Người ta cũng chỉ ra tương ứng mỗi phụ thuộc dữ liệu ấy là một lớp bài toán có trong thực tiễn. Nhưng phổ thông nhất vẫn là phụ thuộc hàm, vì nó đơn giản và nó phổ thông theo nghĩa nếu tập cột A xác định hàm với tập cột B có nghĩa rằng A là xác định duy nhất B. Giả sử: f(x1) = y1, f(x2) = y2. Nếu x1 = x2 Þ f(x1) = f(x2) Þ y1 = y2 Với ý nghĩa đơn giản và phổ thông như vậy. Chỉ có phụ thuộc hàm mới đưa ra được thương trường. II.1.3. Định nghĩa hệ tiên đề Amstrong cho phụ thuộc hàm Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ R, và X®Y là một phụ thuộc hàm, X,Y là tập con của R. Nói rằng X ®Y được suy diễn logíc từ F nếu mối quan hệ r trên R đều thoả mãn các phụ thuộc hàm của F thì cũng thoả mãn X ®Y[3]. Chẳng hạn F = {A ®B, B ®C } thì A ®C suy ra từ F. Gọi F+ là bao đóng của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logíc từ F. Nếu F = F+ thì F là họ đầy đủ của các phụ thuộc hàm. Gọi R = {A1,A2,...,An}là tập các thuộc tính. X,Y,Z,W Í R. Hệ tiên đề Amstrong bao gồm : A1(phản xạ): Nếu Y Í X thì X®Y A2(tăng trưởng):Nếu Z Í R, X®Y thì XZ ® YZ A3(bắc cầu):Nếu X®Y, Y®Z thì X®Z Xét ví dụ sau: AB ® C, C ® A Cần chứng minh rằngBC ® ABC. Thật vậy từ 1. C ® A(giả thiết) 2. BC ® AB (tăng trưởng) AB ® C (giả thiết) AB ® ABC (tăng trưởng (3) thêm AB) BC ® ABC (bắc cầu từ (2) và (4)). Chúng ta có các bổ đề sau: Bổ đề 1: Hệ tiên đề Amstrong là đúng. Có nghĩa là F là tập phụ thuộc hàm đúng trên quan hệ r. Nếu X®Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Amstrong thì X®Y là đúng trên quan hệ r. Chứng minh: Lần lượt kiểm tra tính đúng đắn của ba đề A1,A2,A3 A1: Tiên đề A1 rõ ràng là đúng vì không thể có hai bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó . A2: Giả sử rằng quan hệ r thoả X®Y. Tồn tại hai bộ t,u sao cho t[XZ] = u[XZ] mà t[YZ] = u[YZ]. Vì rằng t[Z] = u[Z] nên để có t[YZ] # u[YZ] thì t[Y] # u[Y]. Nhưng vì t[X] = u[X]nên t[Y] # u[Y] là trái với giả thiết X®Y. Với t[YZ] = u[YZ]. A3: Cho X®Y và Y®Z đúng trên quan hệ r . Giả sử tồn tại hai bộ t và u Î r sao cho t[X] = u[X] và t[Z] # u[Z]. Từ X®Y suy ra t[X] = u[X] nên t[Y] = u[Y]. Nhưng lại có t[Y] = u[Y] và t[Z] # u[Z] là trái với giả thiết X ®Y. Do vậy t[Z] = u[Z]. Suy ra X ®Z đúng trên quan hệ r. Bổ đề 2: a. Luật hợp: nếu X ®Y và X ®Z thì X ®YZ . b. Luật tựa bắc cầu: nếu X ®Y và WY ®Z thì XW ®Z. c. Luật tách: nếu X ®Y và Z Í Y thì X ®Z . Chứng minh: a. Từ X ®Y dùng luật tăng trưởng, thêm X ta có X ®XY . khi X ®Z, dùng luật tăng trưởng thêm Y ta có XY ®YZ Và cuối cùng dùng luật bắc cầu suy ra cho X ®XY và XY ®ZX có X®YZ. b. Từ X ®Y dùng luật tăng trưởng thêm W có WX ®WY . Dùng luật bắc cầu cho WX ®WY và WY ®Z suy ra WX ®Z . c. Vì Z Í Y nên X ®Z ( theo luật phản xạ ) Dùng luật bắc cầu cho X ®Y và Y ®Z có X ®Z. Một hệ quả quan trọng của luật tách và luật hợp là nếu X ®Y suy ra X®Ai với mọi A i Î Y. Để dễ dàng chứng minh cho tính đầy đủ của hệ tiên đề Amstrong, ở đây đưa thêm khái niệm bao đóng của tập các thuộc tính của tập các phụ thuộc hàm. Gọi F là tập các phụ thuộc hàm trên tập thuộc tính R, X Í R. X+ là bao đóng của X đối với F được định nghĩa như sau: X+ = {A \ X ®A ÎF+ } Nói cụ thể X+ là tập tất cả các thuộc tính A mà phụ thuộc hàm X®A có thể được suy diễn logíc từ F nhờ hệ tiên đề Amstrong. Bổ đề 3: X ®Y suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y Í X+ Chứng minh: Giả sử Y = A1,A2,,...,An với A1,A2,,...,An là các thuộc tính và Y Í X+. Từ định nghĩa X+ có X®Ai , áp dụng hệ tiên đề Amstrong cho mỗi i có X®Ai, Ai ÎY, nhờ luật tách. Từ đó suy ra Y Í X+ . Định lý 1: Hệ tiên đề Amstrong là đúng và đầy đủ. Chứng minh: Tính đúng đắn của hệ tiên đề đã được chứng minh qua bổ đề 1.ở đây chỉ cần chứng minh tính đầy đủ tức là nếu X®Y không thoả trên r thì X®Y không thể suy diễn từ F. Gọi F là tập các phụ thuộc hàm trên tập thuộc tính R. Giả sử rằng X®Y là không thể suy dẫn được từ hệ tiên đề. Xét quan hệ r gồm hai tập sau: 11...1 11...1 11...1 00...0 Các thuộc tính thuộc X+ Các thuộc tính còn lại Trước hết cần chỉ ra rằng tất cả các phụ thuộc hàm thuộc F đều thoả r. Thật vậy, giả sử (V®W) ÎF nhưng không thoả trên r. Do đó V Í X+ , hoặc hai bộ của r sẽ không bằng nhau ít nhất trên một thuộc tính của V. Như vậy W không thể là tập con của X+ hoặc V ® W thoả trên r . Gọi A Î W nhưng A không thuộc X+. Vì XV Î X+, X®V suy ra từ bổ đề 3 .( X®V Î F ) do vậy, nhờ luật bắc cầu suy ra X®A, nhưng do A không thuộc X+ như giả thiết, do vậy là mâu thuẫn. Từ đó kết luận rằng mỗi (V®W) Î F đề thoả trên r . Bây giờ cần chứng minh rằng X®Y không thoả trên r. Giả sử rằng X®Y là thoả trên r. Như trên có X Í X+ và suy ra Y Í X+, nếu không hai bộ là bằng nhau trên X nhưng không bằng nhau trên Y. Theo bổ đề 3 thì X®Y có thể suy ra được từ hệ tiên đề, điều đó là hoàn toàn mâu thuẫn. Do vậy X®Y không thể đúng trên r. Đến đây có thể kết luận rằng: Nếu X®Y không suy dẫn được từ hệ tiên đề Amstrong thì X®Y không suy dẫn logíc được từ F. Hệ tiên đề đầy đủ. II.1.4. Phủ của các tập phụ thuộc hàm Cho tập phụ thuộc hàm F, hãy thay thế F bằng phụ thuộc G sao cho G vẫn đảm bảo đúng chức năng của F. Khi đó ta gọi G là phủ của tập phụ thuộc hàm F. Bổ đề 4: Mỗi ttập phụ thuộc hàm F đều được phủ bằng tập các phụ thuộc hàm G sao cho G mà vế phải các phụ thuộc hàm đó bao gồm không quá một thuộc tính . Chứng minh: Gọi G là tập các phụ thuộc hàm X®A sao cho với X®Y thuộc F thì A Î Y . Từ X®Y suy ra X®A (theo luật tách) Do vậy G Í F+ . Ngược lại, có F Í G+ vì nếu Y = A1,...,An thì X®Y được suy ra X®A1,. . . , X®An nhờ luật hợp . Để có thể phục vụ quá trình thiết kế lược đồ cơ sở dữ liệu, sau đây sẽ đưa ra một số khái niệm. Gọi các tập phụ thuộc hàm F là tối thiểu nếu : a/ Mỗi vế phải của một phụ thuộc hàm F chỉ có một thuộc tính . b/ Không tồn tại một phụ thuộc hàm X®A thuộc F mà F+ = (F - { X®A}) + c/ Không tồn tại một phụ thuộc hàm X®A thuộc F và một tập con Z của X mà : F+ = (F - { X®A} È { Z®A } ) +. Thực vậy điều kiện b/ bảo đảm cho tập F không có phụ thuộc hàm nào là dư thừa và diều kiện c/ đảm bảo không có một thuộc tính nào tham gia phía trái của phụ thuộc hàm là dư thừa. Vế phải của phụ thuộc hàm ở điều kiện a/ chỉ có một thuộc tính bảo đảm chắc chắn không có một thuộc tính nào trên vế phải là dư thừa . II.1.5. Định nghĩa sơ đồ quan hệ Cho trước R = { a1, a2,..., an } A,B Î R, đặt A® B là một phụ thuộc hàm. Khi đó S là một sơ đồ quan hệ nếu: S = trong đó F = F gồm t phụ thuộc hàm thì tập ấy gọi là sơ đồ quan hệ. t phụ thuộc hàm này do người thiết kế đặt ra, dựa trên cơ sở nội dung của các cột a1,a2,..,an. Sơ đồ quan hệ đó là đầu biểu ( cấu trúc tệp ) cộng với các ràng buộc logíc (các phụ thuộc hàm ) do người thiết kế đề xuất ra ,các phụ thuộc hàm này làm nhiệm vụ không chỉ phân tích mối quan hệ lôgíc mà còn kiểm tra tính đúng đắn của dữ liệu nữa. II.1.6. Định nghĩa khoá Cho trước r = {h1,h2,...,hm} là tệp dữ liệu trên tập thuộc tính R = { a1, a2,..., an}. Khi đó A Í R được gọi là khoá của tệp dữ liệu r nếu A®R.sao cho bất kỳ hai bộ khác nhau t1,t2 Î r luôn thoả mãn t1(A) ¹ t2(A) - A là khoá tối tiểu nếu : A®R Không tồn tại A’ sao cho A’ Ì A(A’ tập con thực sự của A) mà A’ ® R Khoá cho sơ đồ quan hệ: Cho trước s = là sơ đồ quan hệ .Trong đó F = . Khi đó : A Í R được gọi là khoá của s nếu A®RÎF+. A là k hoá tối tiểu của s nếu : - A®RÎF+ - Không tồn tại A’ sao cho A’ Ì A sao cho A’®RÎF+ Khoá đây chính là hình ảnh của cột mã số hay cột số thứ tự trong Tệp dữ liệu nào đó . Ví dụ: Quan hệ Hàng_hoá được cho như sau: MSMH Tên hàng Số lượng 10101 10102 10111 Xi măng Thép Tấm lợp 2000 1500 1000 Trong ví dụ này biểu diễn quan hệ Hàng_hoá, trong đó MSMH là khoá. Mỗi giá trị MSMH đều xác định duy nhất một loạI mặt hàng trong quan hệ Hàng_hoá. II.1.7. Định nghĩa bao đóng Cho trước S = là sơ đồ quan hệ với R = {a1,a2,...,an} là tập hữu hạn các thuộc tính. Trong đó F = . Và A Í R. Khi đó bao đóng của A trong S là A+ . Trong đó : A+ = {a : a Î R và A®{a}ÎF+ } Cho r = {h1,h2,...,hm} là tệp dữ liệu trên tập thuộc tính R = {a1,a2,...,an}, AÎ R. A+r = {a : a Î R và Ar®{a}} A+r được gọi là bao đóng của A trong r. Nếu A là một tập bất kỳ ( tập cột bất kỳ ) thì A+ là tập hợp tất cả những cột mà phụ thuộc hàm vào A trong sơ đồ quan hệ S, chúng ta có A+r là tập hợp tất cả các cột mà phụ thuộc hàm vào {a} trong tệp dữ liệu r. Dễ thấy rằng theo hệ tiên đề của Amstrong thì. A Í A+ A Í A+r Trên cơ sở địmh nghĩa này chúng ta có các kết quả sau : Giả sử S = là sơ đồ quan hệ . A®B Î F B Í A+ Cho r = {h1,h2,...hm }là tệp dữ liệu trên R = {a1,a2,...,an} . ta có A®B (B phụ thuộc hàm r vào A) B Í A+r Kết quả này nói lên rằng một tập B nào đó mà phụ thuộc và tập A khi và chỉ khi B là tập con của bao đóng của A. Nhờ có kết quả này, người ta không cần phải lưu trữ tất cả các phụ thuộc hàm của một tệp dữ liệu hoặc của một sơ đồ quan hệ (số lượng này như chúng ta đã biết có thể là một hàm số mũ ) mà vẫn kiểm tra được hai tập thuộc tính bất kỳ (hai tập cột bất kỳ ) có phụ thuộc hàm với nhau hay không, bằng cách kiểm tra một tập này có phải là tập con của tập kia hay không. Vì vậy chúng ta chúng ta phải tính được bao đóng của một tập cột bất kỳ. Nói cách khác chúng ta phải tính được A+. Người ta đã tìm ra được hai thuật toán để tính A+ và A+r với thời gian tính là đa thức sẽ được trình bầy ở chương sau.. II.2. CÁC PHÉP TOÁN TRÊN CƠ SỞ DỮ LIỆU QUAN HỆ II.2.1. Phép chèn (Insert) Phép chèn là phép thêm một bộ vào quan hệ r{A1,A2,...,An} có dạng: r = rÈt. Cú pháp: Insert{r;A1=d1,A2=d2,...,An=dn}. Trong đó Ai với i= 1,2,...,n là tên các thuộc tính và Di Î Dom(Ai) là các giá trị thuộc miền trị tương ứng của thuộc tính Ai. Ví dụ: Thêm một bộ t4 = ( Vũ văn Tần ,1960,Trương ĐHĐĐ,422 ) vào quan hệ Nhân_viên trên: Insert(Nhân_viên ; Họ tên = Vũ vă Tần, Năm _sinh = 1960, Công tác= ĐH ĐĐ, Lương=425). Nếu xem như các trường là cố định, khi đó có thể biểu diễn phép chèn dưới dạng không tường minh như sau : Insert (r ;d1,d2,...,dn). Mục đích của phép chèn là thêm một bộ phận vào một quan hệ nhất định.Kết quả của phép tính này có thể gây ra một số sai sót với những lý do sau đây : 1. Bộ mới thêm vào là không phù hợp với lược đồ quan hệ cho trước; 2. Một số giá trị của một số thuộc tính nằm ngoài miền giá trị của bộ đó; 3. Giá trị khoá của bộ mới có thể là giá trị đã có trong quan hệ đang lưu trữ . Do vậy, tuỳ từng hệ cụ thể sẽ có từng cách khắc phục riêng. II.2.2. Phép loại bỏ (Del) Phép loại bỏ là phép xoá một bộ ra khỏi quan hệ cho trước. Giống như phép chèn, phép loại bỏ có dạng: r = r – t DEL(r; A1 = d1, A2 = d2,..., An = dn ) hoặc DEL( r; d1,d2,...,dn) . Ví dụ: Loại bỏ bộ t2 từ quan hệ Sinh_viên ở ví dụ trước: Del(Sinh_viên; 372013, Trần hà, 1976, NN, 6.95 ) Tất nhiên không phải lúc nào phép loại bỏ cũng cần đầy đủ thông tin về bộ cần loại bỏ. Nếu có giá trị về bộ đó tại các thuộc tính khoá K ={B1,...,Bi}khi đó phép loại bỏ chỉ cần viết : DEL( r; B1 = e1,B2 = e2,..., Bi = ei ) II.2.3. Phép thay đổi (CH) Trong thực tế không phải lúc nào cũng chỉ dùng phép chèn hoặc loại bỏ đi một bộ mà nhiều khi chỉ cần sửa đổi một số giá trị nào đó tại một số thuộc tính, lúc đó cần thiết phải sử dụng phép thay đổi . Gọi tập {C1,C2,...,Cp}là tập các thuộc tính mà tại đó các giá trị của bộ cần thay đổi, khi đó phép thay đổi có dạng : r = r \ t È t’ CH( r; A1 = d1, A2 = d2, ...,An = dn; C1 =e1, C2 = e2,...Cp = ep) Nếu K = {B1,B2,...,Bm}là khoá của quan hệ, khi đó chỉ cần viết : CH( r; B1 = d1, B2 = d2,...,Bm = dm; C1 = e1, C2 = e2,...,Cp = ep ) Ví dụ: Phép thay đổi là phép tính rất thuận lợi hay dùng. Cũng có thể không dùng phép thay đổi mà dùng tổ hợp của phép loại bỏ và phép chèn bộ mới. Do đó những sai sót của phép thay đổi cũng sẽ xảy ra tương tự như phép chèn và phép loại bỏ. II.3. CÁC PHÉP TÍNH XỬ LÝ BẢNG Yêu cầu bài toán: Trong phần này chúng ta sẽ khảo sát một số phép toán sử lý bảng ( Tệp dữ liệu ). Chúng tạo nên ngôn ngữ xử lý dữ liệu. Ngôn ngữ xử lý dữ liệu là một ngôn ngữ quan trọng trong hệ quản trị cơ sở dữ liệu ngững hệ quản trị Cơ sở dữ liệu này là những công cụ sắc bén cho chúng ta trong quá trình xử lý, đặc biệt là xử lý thông tin trong các hệ thông tin quản lý như: SQL for Windows, Orcale, IBM DB2, Foxpro, Access,... Ngôn ngữ xử lý dữ liệu đều dựa trên mô hình dữ liệu quan hệ. Trong đó hạt nhân chủ yếu là tệp dữ liệu (bảng). Chúng ta sẽ khảo sát những phép toán xử lý tệp dữ liệu cơ bản nhất của cái nằm trong ngôn ngữ xử lý dữ liệu này. Các phép toán này được đề xuất bởi người sáng lập ra mô hình dữ liệu quan hệ. Các phép toán xử lý tệp dữ liệu sau đây được chắt lọc từ ngôn ngữ xử lý dữ liệu (Ngôn ngữ đại số quan hệ). Đại số quan hệ như là cơ sở của ngôn ngữ bậc cao để thao tác trên quan hệ. Người khai thác cơ sở dữ liệu phải nêu ra những câu hỏi diễn tả yêu cầu tìm kiếm thông tin, kết xuất thông tin. Đại số quan hệ cung cấp các phép toán để đáp ứng nhu cầu trên. Gọi r là một quan hệ trên tập thuộc tính R = {A1,...,An} ở đây luôn giả thiết rằng quan hệ r là tập hữu hạn các bộ. Đối với các phép hợp, giao và trừ, hai quan hệ tham gia phải là khả hợp. Cho trước hai quan hệ D A E a a b b c d e f g t= A B C a a c a c b b c d a a d r = = Từ hai quan hệ trên ta có các phép tính sau: II.3.1. Phép hợp Giả sử r và t là hai tệp dữ liệu cùng có n cột , trong ví dụ trên thì r và t có 3 cột. Khi đó quan hệ r È t là một quan hệ (tệp dữ liệu ) cũng n cột bao gồm các bản ghi (dòng) của cả r lẫn t. Chú ý rằng những bản ghi giống nhau chỉ giữ lại một lần, nếu r và t là tệp dữ liệu có tên các cột khác nhau thì tệp dữ liệu hợp không ghi tên cột nữa. Nói cách khác là chỉ có khung mà thôi. Phép toán này dùng để hoà lẫn hai tệp dữ liệu có cùng số cột. Hai tệp này đều có cấu trúc cột như nhau, như vậy ta dùng phép hợp này thông thường đối với hai tệp có cùng số cột cùng cấu trúc cột . Kí kiệu của phép hợp hai quan hệ : r È t Biểu diễn hình thức phép hợp có dạng: r È t :={s : s Î r hoặc s Î t} a a b a c b b c d a a d e f g Từ hai quan hệ cho trước ta có phép hợp của hai quan hệ r và t: rÈt: = II.3.2. Phép trừ Được thực hiện như phép hợp, kết quả của phép trừ là lấy những dòng thuộc r nhưng không thuộc t. Trong trường hợp tên cột khác nhau thì kết quả không có tên cột. Ký hiệu phép trừ của hai quan hệ r và t: r \ t Phép trừ dùng để chắt lọc những dòng của tệp dữ liệu r mà không được phép có mặt trong tệp dữ liệu t . a c b a a d Từ hai quan hệ cho trước ở trên, ta có phép trừ của r và t r \ t : = II.3.3. Phép giao Giả sử hai quan hệ r và t là hai tệp dữ liệu n cột khi đó quan hệ giao là quan hệ n cột bao gồm các dòng có mặt trong cả r lẫn t. Trong trường r và t có tên cột khác nhau thì các cột của tệp dữ liệu giao không có tên . Ký hiệu phép giao của hai quan hệ r và t: r Ç t Từ hai quan hệ cho trước ở trên, ta có phép giao của r và t a a b b c d r Ç t:= II.3.4. Phép tích Đề_các Giả sử tệp dữ liệu r có n cột và tệp dữ liệu t có m cột (m # n). Khi đó tích đề các là tệp dữ liệu có n+m cột và dòng được hình thành như sau : x1,x2,... ,xn Î r, y1,y2,..., ym Î t Thì ( x1,x2,... ,xn , y1,y2,..., ym) Î r x t, thì r x t là kí pháp của tích đề các Trong trường hợp tệp dữ liệu r và t có những cột trùng tên nhau thì chúng ta đặt tên của tệp dữ liệu rồi đến dấu chấm rồi mới đến tên các cột đó . Ký hiệu phép tích Đề các của hai quan hệ r và t: r x t Từ hai quan hệ cho trước ở trên, ta có phép tích Đề các của r và t: r.A B C D t.A E a a b a a b a a b b c d a a b e f g a c b a a b a c b b c d a c b e f g b c d a a b . . . r x t := Tích đề các cho phép nối các tệp dữ liệu bất kỳ với nhau và nó là nền tảng xây dựng nên các phép toán quan trọng khác. II.3.5. Phép chiếu r là tệp dữ liệu n cột. Kí hiệu Õi1,i2,...ip(r) là phép chiếu lên tệp dữ liệu r. Ở đây i1,i2,..,ip là p số chỉ thứ tự cột mà chúng ta muốn lấy ra khỏi r và hình thành một tệp dữ liệu gồm p cột đó. Ví dụ: cho tệp dữ liệu r: A B C 1 0 1 1 1 1 0 1 0 0 0 2 r = Từ ví dụ trên ta có A B 1 0 1 1 0 1 0 0 Õ1, 2(r ) = A C 1 1 0 0 0 2 Õ1, 3(r) = Nếu có nhiều dòng giống nhau thì ta chỉ lấy một dòng. Phép chiếu là phép phổ biến nhất dùng để nhặt ra một số các cột trong một tệp dữ liệu cho trước. II.3.6. Phép chọn Cho tệp dữ liệu n cột , gọi dF(r) là phép chọn. F: Là biểu thức điều kiện. Các phép so sánh trong biểu thức F la: , >=, <=, =, ¹,...;Các phép logíc là Ù (và), Ú (hoặc) và Ø (không) . Hình thức phép chọn được định nghĩa như sau: dF(r) = {t Î r : F(t) = đúng } F(t) được hiểu là các giá trị của các thuộc tính xuất hiện trong biểu thức F tại bộ t thoả mãn các điều kiện của F. Kết quả của phép chọn là hình thành ra một tệp dữ liệu mới có cấu trúc và số cột như tệp dữ liêụ cũ, nhưng dòng phải thoả mãn điềy kiện F. Ví dụ: Từ quan hệ r cho trên, chọn quan hệ r trên các thuộc tính (a1 = “1” Ù a3 = “2”), ta được quan hệ mới có kết quả là số bộ giảm đi. a1 a2 a3 1 1 0 0 0 2 dF(r) = II.3.7. Phép chia Gọi r là tệp dữ liệu n cột và t là tệp dữ liệu m cột ( n > m , t ¹ Æ ). Phép chia r ¸ t là tập tất cả ( n – m ) bộ s sao cho:"u Î t thì bộ s Ç u Î r. a b c d a b e f b c e f e d c d e d e f a b d c b b b b Ví dụ: Cho tệp dữ liệu r = c d e f t = a b e d Ta có quan hệ r ¸ t = Bản chất của phép chia là các cặp n – m cột đầu tiên của quan hệ r phải đối chứng với quan hệ t. Quan hệ này không phổ biến chủ yếu được dùng trong phân tích dữ liệu, khi đối chứng giữa hai dữ liệu của hai tệp r và t. II.3.8. Phép kết nối có điều kiện Gọi r là tệp dữ liệu n cột và t là tệp dữ liệu m cột. Ký pháp q = {, =, ¹} là các phép toán quan hệ số học iqj Khi đó phép kết nối có điều kiện với i và j là tên hoặc số cột tương ứng của r và t thoả mãn điều kiện q. Ký hiệu là r >< t a1 a2 a3 0 1 0 0 1 1 0 0 1 Ví dụ: cho hai quan hệ: r = a3 a5 a7 1 1 0 1 1 1 t = a1 a2 r.a3 t.a3 a5 a7 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 Tính tích đề các r x t: r x t = a1 a2 r.a3 t.a3 a5 a7 0 0 1 1 1 1 Từ hai quan hệ trên ta được phép kết nối có điều kiện r >< t là: a2<a7 r >< t = II.3.9. Phép kết nối tự nhiên Cho trước r là tệp dữ liệu n cột, và t là tệp dữ liệu m cột. Khi đó phép kết nối tự nhiên là: r >< t. Được thực hiện như sau. r x t Giả sử r và t có p cột tên giống nhau. Đó là các cột A1,A2,...,Ap. Ký hiệu: B = sr. .A1 = t.A1 Ù ... Ù r.Ap = t.Ap A B C 1 0 1 0 1 0 0 0 0 c. Tính P 1, 2,...,m + n -p (B) Ví dụ: Cho hai quan hệ: r = D B 1 0 2 0 t = A r.B C D t.B 1 0 1 1 0 1 0 1 2 0 0 1 0 1 0 0 1 0 2 0 0 0 0 1 0 0 0 0 2 0 a/ Tính tích Đề_các: r x t = A r.B C D t.B 1 0 1 1 0 1 0 1 2 0 0 0 0 1 0 0 0 0 2 0 b/ Tính bước 2: A r.B C D 1 0 1 1 1 0 1 2 0 0 0 1 0 0 0 2 c/ r >< t: Trong 9 phép toán mà chúng ta học, phép toán quan trọng nhất là phép kết nối tự nhiên bởi lý do như sau. Trong quá trình sử lý biểu bảng ( tệp dữ liệu ) các biểu bảng này không phải là những người làm tin học đề xuất ra mà do các chuyên gia trong lĩnh vực tin học đề xuất ra, chính vì thế trong những năm 1970, người sáng lập ra mô hình dữ liệu quan hệ đã đề xuất ra 4 dạng chuẩn để chuẩn hoá dữ liệu. Các dạng chuẩn này sẽ được giới thiệu ngay sau chương này. Nhờ có các dạng chuẩn này, khi xử lý tệp dữ liệu người ta tách tệp dữ liệu gốc (do các chuyên gia ở mọi lĩnh vực đề xuất ra ) thành các tệp dữ liệu con đã ở trong dạng chuẩn rồi và khi xử lý người ta lưu trữ các tệp dữ liệu con trong máy chứ không phải là các tệp dữ liệu gốc to, nhưng một điều rất quan trọng là để khỏi mất thông tin (có tính pháp lý )thì phải hồi phục được tệp gốc ở bất cứ thời điểm nào cần, muốn hồi phục được người ta dùng phép kết nối tự nhiên nối tất cả các tệp dữ liệu con thì ta sẽ được tệp dữ liệu gốc to. Việc lưu trữ các tệp dữ liệu con thường chiếm ít bộ nhớ hơn là tệp dữ liệu gốc to, tốc độ xử lý các tệp dữ liệu đã chuẩn hoá nhanh hơn rất nhiều so với tệp dữ liệu chưa được chuẩn hoá (tệp dữ liệu gốc to). Cho đến nay tất cả các hãng máy tính trên thế giới khi xây dựng mô hình dữ liệu quan hệ đều áp dụng phép kết nối tự nhiên trong ngôn ngữ xử lý của họ. II.4. CÁC THUẬT TOÁN CỦA PHỤ THUỘC HÀM II.4.1. Thuật toán tính A+ Input: s = với  R = {a1,a2,...,an } và F = , A Í R. Output: A+ = ? Thực hiện thuật toán: Bước 0: A0 = A, Bước i ( i >= 1):Kiểm tra trong danh sách các phụ thuộc hàm. Nếu có Aj ® Bj ( phụ thuộc hàm) mà: Aj Í Ai -1. Và Bj Í Ai - 1 thì Ai = Ai - 1 È Bj , Việc làm này lặp đi lặp lại cho đến khi không còn sự phụ thuộc Aj ® Bj như trên thì đặt A+ = Ap ( p <= t ). Ví dụ: Cho R = {a1,a2,a3,a4}, F = {{a1} ® {a2,a3},{a3} ® {a} } , cho A = {a1} , tính A+ = ? Thực hiện thuật toán: Bước 0: A0 = {a1} Bước 1: A1 = A0 È {a2,a3} = {a1,a2,a3} Bước 2: A2 = A1 È {a4} = {a1,a2,a3,a4} = R A = {a2,a4} A0 = {a2,a4} A+ = A0 = {a2,a4} = A. Dễ thấy rằng độ phức tạp của thuật toán này là đa thức. Kết quả của rhuật toán này được phát hiện năm 1979. Ngay sau khi phát hiện được thuật toán này thì cơ sở dữ liệu quan hệ đã đi vào phát triển rất sôi động. Nhờ có thuật toán này chúng ta giải quyết được bài toán thành viên theo nghĩa (cho trước một cấu trúc xem thử xem, một phần tử bất kỳ có thuộc cấu trúc đó hay không. Trong trường hợp này cho trước một sơ đồ quan hệ bao gồm các cột (r) và danh sách các phụ thuộc hàm do người thiết kế áp đặt. Xem thử xem hai tập cột bất kỳ có phụ thuộc hàm với nhau hay không. Nói cách khác A®B có thuộc F+ hay không ). II.4.2. Thuật toán tính A+r Input: Cho r = {h1,h2,...,hm}là tệp dữ liệu trên tập thuộc tính R = {a1,a2,...,an}.Trong đó A Í R. Output: A+r = ? Thực hiện thuật toán: Bước 1: Tính E r = {Ei j : 1 <= i < j <= m } Ta tính Ei j = {a : a Î R và hi(a) = hj(a)} Bước 2: Tính A+r = Ç Ei j nếu có Ei j mà A Í Ei j A+r = R nếu không có Ei j như thế . Tập Er được gọi là họ các tập bằng nhau của r, Ei j gọi là các tập bằng nhau. Có thể thấy rằng Ei j = F trong trường hợp hai dòng i, j không có cột nào trùng nhau về giá trị, có nghĩa là chúng khác nhau hoàn toàn có thể sảy ra một số các tập bằn nhau, trùng nhau. Không bao giờ có Ei j = R. Có nghĩa rằng Ei j = toàn bộ không gian, nghĩa là bao gồm tất cả các cột vì nếu sảy ra thì ta sẽ có 2 dòng bằng nhau (trùng nhau). Ví dụ: Ta có bảng thực thể R = (a1, a2, ..., a5.) a1 a2 a3 a4 a5 1 0 1 0 0 1 2 0 1 1 1 0 1 1 1 0 1 0 0 0 Tính E12 = {a1}, E13 = {a1,a2,a3}, E14={a4,a5}, E23={a1,a2,a5}, E24={a3}, E34=F. Cho A={a2,a3} => A+r = {a1,a2,a3} Cho A={a1,a4} => A+r = {a1,a4,a5} Cho A={a4,a5} => A+r = {a4,a5} Ç{a1,a4,a5}= {a4,a5} Chú ý: Nếu có Ei j=a thì nó chính là E+r. Các tập bằng nhau đóng vai trò rất then chốt trong quá trình thiết kế cơ sở dữ liệu mà đầu vào là phai dữ liệu . Việc tính Ei j là khá đơn giản, số lượng Ei j nhiều nhất bằng lực lượng của r. Vì có nhiều Ei j trùng nhau nên lực lượng giảm hẳn đi. II.4.3. Thuật toán tìm một khoá tối tiểu trong phai dữ liệu Input : Cho r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an}. Ouput : K Î Kr Thực hiện thuật toán : Bước 1: Từ r tính E r = {Ei j : 1 < i < j < m } Bước 2: Đặt A0 = R = {a1,a2..an} Bước 3: Ai = Ai-1 \ ai nếu {Ai-1 \ ai}r+ = R Ai = Ai-1 nếu ngược lại (1<=i <=n) Bước 4: Kết luận: K= An II.4.4. Thuật toán tìm khoá tối tiểu cho một sơ đồ quan hệ Vào: s= là một sơ đồ quan hệ R={a1 ,a2,. . . .,an} là tập các thuộc tính F: là tập các Phụ thuộc hàm. A1 ® B1 F= . . . . . . At ® Bt Ra: K là một khoá tối tiểu. Thực hiện thuật toán: -Bước 1: K0 =R={a1 ,a2,. . . .,an} -Bước i: (1£ i £ n). Ki = Ki-1 nếu Ki-1- { ai }® R Ï F+ Ki-1-{ ai } Ngược lại -Bước n+1: K= Kn là khoá tối tiểu. Ví dụ: Cho R={a1, a2, a3, a4 } F = { a1}® {a2, a3} { a3}® {a4} K0 ={a1, a2, a3,a4} K1 = {K0 - a1}={ a2, a3,a4} { a2, a3,a4}+ ¹ R Þ K0 =K1 =R K2 = {K1 - a2}={ a1, a3,a4} { a1, a3,a4}+ = R Þ K2 =K1 - {a2} ={ a1, a3,a4} K3 = {K2 - a3}={ a1, a4} { a1, a4}+ = R Þ K3 =K2 - {a3} ={ a1, a4} K4 = {K3 - a4}={ a1} { a1}+ = R Þ K4 =K3 - {a4} ={ a1} Þ K =K4 ={ a1} Vậy khoá tối tiểu của sơ đồ quan hệ này K ={ a1}. Dễ thấy rằng thuật toán này dựa trên cơ sở tính A+ chính là kiểm tra {Bi-1 -ai }+ có bằng R hay không ?. Vì thuật toán tính A+ có độ phức tạp là đa thức nên thuật toán tính khoá tối tiểu cho một sơ đồ quan hệ cũng là đa thức. Thực chất tìm khoá tối tiểu là sàng lọc các cột thừa mà bắt đầu từ tập R. Vì một lý do nào đó chúng ta phát hiện ra một tập A là khoá tức là A+ = R thì chúng ta có thể bớt các bước đi bằng cách đặt B0 = A lúc ấy số các bước chỉ bằng lực lượng của A. Nhờ có nhận xét này trong nhiều trường hợp viết thuật toán thực hiện rất nhanh. Hơn nữa thuật toán này phụ thuộc và thứ tự của các cột trong R nếu chúng ta đảo thứ tự đi thì chúng ta có thể tìm được khoá tối tiểu mới. Sau khi tìm được khoá tối tiểu rồi mà chúng ta thấy hài lòng thì ta đặt nó làm khoá chính. Nếu không được thì chúng ta đảo thứ tự các cột để tìm khoá khác. II.4.5. Thuật toán cải tiến tính mọi khoá tối tiểu cho tệp dữ liệu Input: Cho r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an}. Ouput: K Î R Thực hiện thuật toán : Bước 1: Từ r tính Er = {Ei j : 1 <= i < j < =m } Bước 2: Tính Mr = {B: có Ei j để Ei j = B và không có Est. B không phải là tập con thật sự của Est ; Ei j và Est Î Er }. Mr gọi là các tập bằng nhau cực đại. Bước 3: Đặt A0 = R = {a1,a2..an} Bước 4: Tính Ai = Ai-1 \ ai nếu Ï B Î Mr mà Ai-1 \ ai Í B Ai = Ai-1 nếu ngược lại.(1<=i<= n ) Bước 5: Kết luận: K= An Vì số lượng phần tử của Mr nhỏ hơn rất nhiều so với só lượng Er Ví dụ: Cho quan hệ r a1 a2 a3 a4 r = 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 -Bước 1: Tính Er : E12 = {a1,a4} E13 = {a2,a3} E14 = {F} E23 = {F} E24 = {a2 , a3} -Bước 2: Tính Mr : Mr = {a1 , a4}, {a2, a3} A1 A2 -Bước 3: Đặt K0 =R ={a1, a2, a3,a4} -Bước 4: K0 - a1 ={ a2, a3,a4} Þ K1 = K0 - a1 ={ a2, a3,a4} -Bước 5: K2 = K1 - a2 ={a3, a4} (Vì có A2 để {a3, a4} Î A2) Þ K2 = K1 ={ a2, a3,a4} -Bước 6: K3 = K2 - a3 ={a2, a4} (Vì có A1 để {a2, a4} Î A1) Þ K3 = K2 ={ a2, a3,a4} -Bước 7: K4 = K3 - a4 ={a2, a3} (Vì có A4 để {a2, a3} Î A4) Þ K4 = K3 ={ a2, a3,a4} Vậy K = K4 ={ a2, a3,a4} là khoá tối tiểu của quan hệ r. CHƯƠNG III: CÁC DẠNG CHUẨN HOÁ DỮ LIỆU III.1. ĐẶT VẤN ĐỀ Việc chuẩn hoá thông tin trong các quan hệ và trong các sơ đồ quan hệ, đóng vai trò rất quan trọng trong việc giải quyết các bài toán thông tin quản lý trên máy tính. Việc chuẩn hoá này bao gồm các loại sau: - Chuẩn hoá các tệp dữ liệu và các cột, ý nghĩa nội dung các cột trong tệp dữ liệu đó. - Chuẩn hoá những danh mục đi kèm với tệp dữ liệu đó ( Danh mục gồm 2 cột, cột mã và cột tên danh mục). - Chuẩn hoá tất cả các biểu bảng đưa ra trên màn hình và trên máy in. - Chuẩn hoá quy trình thu thập, cập nhật, lưu trữ, xử lý và truyền bá thông tin. - Việc chuẩn hoá thông tin này đều khó khăn và thất bại nếu không được quan tâm đúng mức. Vì vậy khi giải quyết bài toán nên quan niệm điều trước tiên phải chuẩn hoá các tệp dữ liệu gốc trong đó quan trọng là nội dung các trường phải được hiểu theo một nghĩa duy nhất . Sau khi đã thống nhất được các tệp dữ liệu thì tất cả những trường (cột) nào, có thể danh mục hoá được thì phải tiến hành danh mục. Nhìn chung nhờ có chuẩn hoá các quan hệ và sơ đồ quan hệ chúng ta tránh được việc dư thừa dữ liệu và tăng tốc độ của các phép toán xử lý quan hệ . Ví dụ: Nghề nghiệp của các biểu về quản lý nhân sự cho đến nay về cơ bản vẫn chưa có. Một trong những lý do đó chính là do xã hội phát triển xuất hiện nhiều nghành nghề mới mà cơ quan nhà nước được giao trách nhiệm này đã không theo kịp. Mặt khác, chúng ta có thể lấy danh mục của liên hợp quốc đưa vào thì có nhiều nghành nghề không phù hợp với Việt Nam vì Việt Nam là một nước đang dần dần hoà nhập với thế giới. Có thể thấy rằng khi chúng ta xử lý các biểu mẫu mà bản chất là các cột thì các cột này về cơ bản lại gắn với danh mục nào đó. Cho nên việc chuẩn hoá các cột gắn liền với việc chuẩn hoá các danh mục. Trên thực tế các biểu báo này là do các chuyên gia trên mọi lĩnh vực đề xuất ra chứ không phải những người làm tin học. Tuy vậy người ta phát hiện ra rằng, những biểu báo đó dư thừa thông tin rất nhiều và sự dư thừa này cản trở việc xử lý thông tin trên máy tính . Để giải quyết vấn đề nêu trên người ta đề xuất ra bốn dạng chuẩn để loại bỏ sự dư thừa này. Đó là các dạng chuẩn: Dạng chuẩn 1: 1NF ( First Normal Form ) Dạng chuẩn 2: 2NF ( Secand Normal Form ) Dạng chuẩn 3: 3NF ( Third Normal Form ) - Dạng chuẩn 4: BCNF ( Boid Cold Normal Form ) Tất cả các hệ quản trị cơ sở dữ liệu hiện nay bán trên thị trường như : Oracle, IBM DB2, Sysbase ....Đều thực hiện theo chuẩn hoá các thông tin này. Việc chuẩn hoá các quy trình, thu thập, truy cập, cập nhật, xử lý và truyền bá dữ liệu trong hệ thống thông tin là vô cùng quan trọng, nó quyết định sự thành, bại của việc áp dụng công nghệ thông tin, mà bản chất là đưa tác phong công nghiệp vào việc áp dụng công nghệ thông tin để chống lại sự nguỵ biện, tự do tùy tiện. Việc thực hiện chuẩn hoá các quy trình trên phụ thuộc vào công cuộc cải cách hành chính ở Việt Nam. III.2. CÁC DẠNG CHUẨN[3] III.2.1. Định nghĩa 1NF Giả sử r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an} . Khi đó r là 1NF nếu: hi(aj) là sơ cấp "i, "j. Nói một cách khác các giá trị nằm trong các cột nếu được thể hiện bằng các dòng kí tự bằng các dòng chữ số hoặc các dòng thể hiện ngày tháng thì chấp nhận là sơ cấp. Như vậy các tệp dữ liệu trong Foxpro đương nhiên là 1NF. III.2.2. Phụ thuộc hoàn toàn Giả sử r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an} . Và A,B Í R. Khi đó người ta nói rằng B phụ thuộc hoàn toàn vào A nếu. A ® B " A' mà A' Ì A ( Tập con thực sự ) thì A' ® B Ví dụ: Xét quan hệ HOA ĐON sau . SO_HĐ NGAY HỌTÊN ĐỊACHỈ MA_SP A007 2/3/98 Hà Giang 4 Hà Trung_Hà Nội C58,A30 B563 14/3/98 Nguyễn Văn Giang Lâm Thao_Phú Thọ A37,B25 A008 14/3/98 Nguyễn Việt Dũng Vĩnh Yên_Vĩnh Phúc C58,A30 C351 20/3/98 Hà Phương Hải Việt Trì_Phú Thọ B26 Khoá chính ; SO_HĐ , MA_SP Ta tìm ra phụ thuộc bộ phận giữa SO_HĐ và { TEN_KH , SO_ NHA,TINH, NGAY } . Như vậy cần phân rã HOAĐON thành hai quan hệ là HOAĐON 11 và HOAĐON 12 như sau HOÁĐON11 SO_HĐ MA_SP A007 A12 A007 C98 B563 A37 B563 B25 A008 C58 A008 A30 C315 B26 HOÁĐƠN12 SO_HĐ NGAY TEN_KH S_NHA TINH A007 2/3/98 Hà Giang 4 Hà Trung Hà nội B563 14/3/98 Nguyễn Văn Giang Lâm Thao Phú thọ A008 14/3/98 Nguyễn Việt Dũng Vĩnh Yên Vĩnh phúc C351 20/3/98 Hà Phương Hải Việt Trì Phú thọ Để xem một quan hệ (bảng) có ở dạng chuẩn 2 hay không trong thực tế người ta không tìm tất cả các khối tiểu của nó mà chỉ tìm ra một khoá tối tiểu gọi là khoá chính . Thường khoá này được tìm căn cứ vào ý nghĩa thực tế của các thuộc tính nhưng cũng có thể áp dụng các thuật toán tìm một khoá tối tiểu nếu người thiết kế không thật hiểu rõ ý nghĩa các thuộc tính . Bây giờ ta sẽ sét đến việc phân rã các quan hệ chưa ở dạng chuẩn 2 thành các quan hệ ở dạng chuẩn 2 Đầu vào của ta là các quan hệ ở dạng chuẩn 1 với tập tất cả các thuộc tính R . Trước khi xem xét đến các quan hệ ở dạng chuẩn 2 hay không một vấn đề đặt ra là ; Tập các thuộc tính nào là chính khoá của quan hệ. Trong phần lớn các quan hệ QTCSDL khoá chính đã được chỉ ra ngay khi chỉ ra định nghĩa dữ liệu, tức là khi xây dựng cấu trúc của bảng. Nếu không ta cũng có thể xác định khoá chính căn cứ vào ý nghĩa của các thuộc tính. Gỉa sử ta xác định được khoá chính là tập K Sự vi phạm điều kiện dạng chuẩn 2 thể hiện ở chỗ tồn tại một tập thuộc tính Y chỉ phụ thuộc vào một bộ phận của khoá chính là M ÌK Khi ấy ta thực hiện phân rã bằng cách đưa thuộc tính trong MY sang một bảng và thuộc tính nằm trong R- Y sang một bảng khác. Rõ ràng K là khoá của bảng chứa các thuộc tính trong R-Y, còn M là khoá của bảng chứa các thuộc tính trong MY. Trên cơ sở định nghĩa này người ta đưa ra dạng chuẩn hai như sau. III.2.3. Định nghĩa 2NF Giả sử r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an} .và a Î R\ " K được gọi là thuộc tính thứ cấp K Î Kr. Dễ thấy rằng a không tham gia bất kỳ khoá tối tiểu nào. Ngược lại a gọi là sơ cấp nếu nó tham gia một khoá tối tiểu nào đó khi đó r là 2NF nếu: r là 1NF Với mỗi K Î K(r) và a là thứ cấp thì a phụ thuộc hoàn toàn vào K. (K(r) là tập các khoá ) Dạng chuẩn hai là một trong những dạng chuẩn quan trọng nhất để chống dư thừa thông tin. III.2.4. Định nghĩa 2NF cho sơ đồ quan hệ Giả sử s = là sơ đồ quan hệ ,trong đó R = {a1,a2,...,an } và F = KÎKr Z = È K Khi đó s là 2NF nếu với mỗi K Î Kr và aÎR-Z ta có a phụ thuộc hoàn toàn vào K. Định nghĩa này tương tự như định nghĩa 2NF, nhưng không yêu cầu s là 1NF , sơ đồ quan hệ không có dữ liệu . Dạng chuẩn 2NF đối với sơ đồ quan hệ cũng rất phổ biến. Thông thường người ta đưa ra một tệp dữ liệu hoặc một sơ đò quan hệ về dạng chuẩn hai. III.2.5. Định nghĩa phụ thuộc bắc cầu Giả sử r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an} . f A B r (A xác định hàm f của r vào B) Là phụ thuộc bắc cầu nếu $ C sao cho C # A và C # B và A C f r f r C B , , Tương tự như vậy ta có định nghĩa sơ đồ quan hệ trong đó có phụ thuộc bắc cầu .Phụ thuộc bắc cầu cũng xuất hiện nhiều trong một tệp dữ liệuvà trong một sơ đồ quan hệ ,người ta đã chứng tỏ rằng phụ thuộc bắc cầu cũng tạo nên sự dư thừa thông tin, sự không minh bạch giữa các mối quan hệ phụ thuộc hàm. Nói cách khác nó cản trở tốc độ xử lý đối với tệp dữ liệu cũng như đối với sơ đồ quan hệ. B A C Ngược với phụ thuộc bắc cầu, người ta gọi là phụ thuộc trực tiếp, có nghĩa rằng nếu phụ thuộc phần tử C mà $ như trên A®B bắc cầu nếu $ C: A C f r C B f r C # A, C# B và , Thì người ta gọi là phụ thuộc trực tiếp. Ví dụ: Xét hai quan hệ HOÁĐƠN11 và HOÁĐƠN12 ở ví dụ trên Quan hệ HOÁĐƠN11 đã ở dạng chuẩn 3 vì không còn thuộc tính nào ngoài khoá chính, Quan hệ HOÁĐƠN12 cũng đã ở dạng chuẩn 3 không còn phụ thuộc bắc cầu , Rõ ràng hai quan hệ trên đã ở dạng chuẩn 3. Như vậy với quan hệ HOÁĐƠN ban đầu, để đạt được mức quan hệ ở dạng chuẩn, ta phải phân rã thành HOÁĐƠN11, HOÁĐƠN12, HOÁĐƠN13. Trên cơ sở ví dụ này chúng ta có định nghĩa dạng chuẩn 3 như sau: III.2.6. Định nghĩa 3NF Giả sử r = {h1, h2 , ..., hm} là tệp dữ liệu trên tập cột R = {a1,a2,...,an} . Khi đó r là 3NF nếu : K (a) r là 2NF. r f Với mỗi KÎ Kr và a là thứ cấp thì KÎKr là trực tiếp ( Z = ÈK thì a Î R - Z ) Như vậy dạng chuẩn 3 cũng giống như dạng chuẩn 2, chúng ta chỉ xét trong tập hợp các khoá tối tiểu và trong thuộc tính thứ cấp . Vậy dạng chuẩn 3 đòi hỏi phụ thuộc hoàn toàn và trực tiếp giữa tập khoá tối tiểu và tập thuộc tính thứ cấp. Cho đến nay người ta về cơ bản sẽ biến đổi một tệp dữ liệu bất kỳ hoặc một sơ đồ quan hệ bất kỳ về dạng chuẩn 3. III.2.7. Định nghĩa 3NF cho sơ đồ quan hệ Giả sử s = là sơ đồ quan hệ ,trong đó R = {a1,a2,...,an } và F = Khi đó s là 3NF nếu: s là 2NF. Với mỗi KÎKr và a là thứ cấp thì K® {a} Î F+ là trực tiếp. KÎKr ( Z = ÈK thì a Î R - Z) Trên thực tế sơ đồ quan hệ không có dạng chuẩn 1. III.2.8. Định nghĩa BCNF A (a) f r Giả sử r là tệp dữ liệu và s là sơ đồ quan hệ . Khi đó ta nói r là BCNF (s là BCNF) nếu với mỗi a Î A và (A®{a} Î F+ ) thì A+r = R ( A+ = R ). Theo định nghĩa trên với một tập A bất kỳ và một thuộc tính a bất kỳ nằm ngoài A. Dễ thấy rằng nếu một sơ đồ quan hệ (tệp dữ liệu ) ở dạng chuẩn BCNF thì đương nhiên nó là 3NF. Dạng chuẩn BCNF là một dạng chuẩn cực đoan, vì thế thông thường người ta chuyển một tệp dữ liệu hoặc một sơ đồ quan hệ về 3NF mà thôi. Trước khi biến đổi một tệp dữ liệu hoặc một sơ đồ quan hệ phải kiểm tra nó đã là 3NF hay BCNF hay chưa, nếu đã là 3NF hay BCNF thì thôi, trong trường hợp ngược lại thì ta mới tiến hành. III.3. CÁC THUẬT TOÁN CHUẨN HOÁ SƠ ĐỒ QUAN HỆ. III.3.1. Kiểm tra sơ đồ quan hệ có là BCNF không Input: s = .Trong đó R = {A1®B1,. . ., At®Bt} Và Bi không phải là tập con thực sự của Ai Output: s có là BCNF không ? Thực hiện thuật toán: Bước i: nếu A+i = R thì sang bước 2, ngược lại s không là BCNF Với i = 1,2,...,t Bước t + 1: Kết luận: s là BCNF III.3.2. Kiểm tra tệp dữ liệu có là BCNF không Input: Cho r = {h1,h2,...,hm}là tệp dữ liệu trên tập thuộc tính R = {a1,a2,...,an}. Output: r có là 3NF không = ?. Thực hiện thuật toán: Bước 1: Tính E r = {Ei j : 1 <= i < j <= m } Bước 2 : Từ Er tính Mr Bước 3: Tính Z = Ç A mà A Í Mr Bước 4: kiểm tra: Với mỗi A Í Mr và b Í Z Mà {A \ b}+r = A \ b thì r là 3NF.Ngược lại có A Í Mr và b Í Z mà {A \ b}+r # A \ b thì r không là 3NF. CHƯƠNG IV. CHƯƠNG TRÌNH DEMO MÔ PHỎNG CHO CÁC THUẬT TOÁN IV.I. CÀI ĐẶT THUẬT TOÁN TÍNH BAO ĐÓNG Program baodong; Uses Crt; Var r,A,x: String; i,j,n: Integer; f: Array[1..10,1..2] of string; {cac cap phu thuoc ham} Co: Boolean; { Kiểm tra substr có là tập con của s hay không, nếu có hàm trả về trả lại True nếu không là False} Function Sub(Substr,s: String): Boolean; Var i,j,dem: Integer; Begin dem:=0; {de kiem tra co bang so phan tu cua tap con} For i:=1 to length(SubStr) do For j:=1 to length(s) do If SubStr[i] = s[j] then Inc(dem); If Dem = Length(SubStr) then Sub:= True {neu Substr la tap con} Else Sub:=False; End; Begin ClrScr; Write('Input R: '); Readln(r); {Nhap day thuoc tinh} Write('So cap phu thuoc ham: '); Readln(n); For i:=1 to n do For j:=1 to 2 do Begin Write('f',i,'[',j,'] = '); Readln(f[i,j]); End; Write('Bao dong can tim: '); Readln(A); x:=A; {Buoc 0 X = A} Repeat; Co:=False; For i:=1 to n do For j:=1 to 2 do if Sub(f[i,1],x) and not Sub(f[i,2],x) then Begin {Kiem tra dieu kien bao dong} x:= x + f[i,2]; Co:=True; {Thoa man dieu kien ve bao dong} End; Until not co; Writeln('Bao dong cua ',a,' la: ',x); Readln; End. IV.II. CÀI ĐẶT THUẬT TOÁN TÍNH KHOÁ Program Tim_khoa; uses crt; Type CharArr = Array[1..100] of Char; Var Khoiphuc,K_chinh,R,A,A_Plus: CharArr; F1,F2:Array[1..10]of CharArr; Sopt_K,i,k,Sopt_R,Sopt_A,Sopt_A_Plus,Soxdh,tam: integer; Procedure Khoitao(var X:CharArr); var i: integer; Begin for i:=1 to 100 do x[i]:=#0; end; Procedure Nhap(var Y:CharArr; var dem:integer); var c: char; Begin dem:=0; read(c); while (c#13) do Begin if (c',') and (c#10) then Begin inc(dem); Y[dem]:=c; end; read(c); end; end; {ham kiem tra mot tap X co phai la tap con cua Y hay khong} Function Tapcon(X,Y:CharArr):Boolean; var SoptX,SoptY,i,j:integer; kt:Boolean; Begin SoptX:=1; while X[SoptX]#0 do Inc(SoptX); Dec(SoptX); SoptY:=1; while Y[SoptY]#0 do Inc(SoptY); Dec(SoptY); Tapcon:=True; i:=1; while i<= SoptX do Begin j:=1; kt:=false; while j <= SoptY do Begin if X[i] = Y[i] then Begin kt:=true; j:=SoptY+1; End else inc(j); end; if not kt then Begin Tapcon:=false; i:=SoptX+1; end Else inc(i); End; End; {Thu tuc tinh bao dong cuar tap X} Procedure Baodong(X: CharArr); Var i,j,k: integer; Ketqua,Tmp: CharArr; Begin khoitao(ketqua); khoitao(Tmp); Ketqua:=X; Sopt_A_Plus:=Sopt_K; i:=1; While (i<=Sopt_R) do Begin Tmp[1]:=R[i]; j:=1; While j<=Soxdh do Begin if Tapcon(Tmp,f2[j]) and tapcon (F1[j],Ketqua) and not Tapcon(Tmp,Ketqua) then Begin inc(Sopt_A_Plus); Ketqua[Sopt_A_Plus]:= R[i]; j:=soxdh+1; end else inc(j); end; inc(i); end; A_Plus:= ketqua; end; Procedure Delete (var khoa:CharArr;var k:integer); var i:integer; begin Khoitao(khoiphuc); khoiphuc:=Khoa; For i:= k to Sopt_k-1 do Begin Khoa[i]:=Khoa[i+1]; end; Sopt_K:=Sopt_K-1; K_chinh:=Khoa; end; Procedure Timkhoa(R:CharArr); var k,i,j:integer; thu,khoa: CharArr; begin Khoitao(Khoa); Khoitao(thu); Thu:=R; Sopt_K:=Sopt_R; j:=0; For i:=1 to Sopt_R do Begin k:=i-j; Delete(Thu,k); Baodong(K_chinh); If Tapcon(R,A_Plus) then Begin j:=j+1; thu:=K_chinh; end else begin Thu:=Khoiphuc; Sopt_K:=Sopt_K+1; end; end; K_chinh:=Thu; end; {---------------------------------------------------------------} {CHUONG TRINH CHINH} BEGIN Repeat clrscr; Writeln (#32:10,'CHUONG TRINH TIM KHOA CHINH CUA MOT TAP CAC THUOC TINH'); Writeln (#32:10,'TREN TAP CAC PHU THUOC HAM DOI VOI MOT LUOC DO QUA HE '); Writeln (#32:10,'------------------------------------------------------'); Writeln (' Vao cac phan tu cua tap R cach nhau boi dau "," Nhan ENTER de ket thuc'); Write('R='); Nhap(R,Sopt_R); Write('cho biet so cap xac dinh ham cua tap F:'); Readln(Soxdh); for i:=1 to Soxdh do Begin Write('F1[',i,']='); Nhap(F1[i],tam); Write('F2[',i,']='); Nhap(F2[i],tam); End; Timkhoa(R); Write(#13#10,' Khoa chinh cua tap R = '); For i:=1 to Sopt_R-1 do Write(R[i],','); Write(R[Sopt_R],'la:'); for i:=1 to Sopt_K-1 do write(K_chinh[i],','); writeln(K_chinh[sopt_K]); Writeln (#10#13,'Co tiet tuc nua khong(C/K)'); Until (Upcase(Readkey)='K'); End. KẾT LUẬN Việc nghiên cứu lý thuyết về mô hình dữ liệu quan hệ và các dạng chuẩn nhằm vào lý thuyết chuẩn hoá cacs quan hệ đóng vai trò quan trọng trong nghiên cứu lý thuyết và ứng dụng trong thực tế. Mục đích của việc nghiên cứu này nhằm bỏ đi các phần tử không bình thường của quan hệ khi thực hiện các phép cập nhật, loại bỏ các dữ liệu dư thừa, hiểu quan hệ ngữ nghĩa giữa các dữ liệu. Việc nghiên cứu lý thuyết về mô hình dữ liệu và các dạng chuẩn góp phần sử dụng hiệu quả các phần mềm như DBASE, FOXPRO, ACCESS trong WINDOWS... Với phạm vi cho phép, luận văn đã nêu lên được một số khái niệm cơ bản về cơ sở dữ liệu quan hệ cũng như một số thuật toán về bao đóng, khoá,..., cũng như phần cài đặt một số chương trình thể hiện cho thuật toán đó bằng ngôn ngữ PASCAL . Một lần nữa cho em được gửi lòng biết ơn đối với thầy giáo Đoàn Văn Ban đã hướng dẫn em hoàn thành được bản luận văn này. Hà nội tháng 6 năn 2000 Sinh viên thực hiện Nguyễn Văn Giang TÀI LIỆU THAM KHẢO [1]. Cơ sở dữ liệu (Database), PGS, PTS Đỗ Trung Tuấn, NXB Giáo dục1998. [2]. Cấu trúc dữ liệu và giải thuật, PGS Đỗ Xuân Lôi, NXB Khoa học và kỹ thuật 1998. [3]. Cơ sở dữ liệu – Kiến thức và thực hành, PGS Vũ Đức Thi, NXB Thống kê 1997. [4]. Luận văn tốt nghiệp “Phần mềm trợ giúp thiết kế CSDL quan hệ dạng chuẩn ba” của Phạm Thị Minh Châu, 1995. [5]. Luận văn thạc sỹkhoa học toán lý “Một vài khía cạnh mở rộng cho lớp các phụ thuộc hàm trong mo hình cơ sở dữ liệu quan hệ ”, 1996. [6]. Nhập môn cơ sở dữ liệu quan hệ “Relational Database”, PGS, PTS Lê Tiến Vượng, NXB Thống kê, 1997.