Tài liệu Nghiên cứu một số vấn đề về cơ sở dữ liệu và ứng dụng trong bài toán quản lý dân cư

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÙI TRUNG HIẾU NGHIÊN CỨU MỘT SỐ VẤN ĐỀ VỀ CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG BÀI TOÁN QUẢN LÝ DÂN CƯ LUẬN VĂN THẠC SĨ: HỆ THỐNG THÔNG TIN Hà Nội - 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÙI TRUNG HIẾU NGHIÊN CỨU MỘT SỐ VẤN ĐỀ VỀ CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG BÀI TOÁN QUẢN LÝ DÂN CƯ Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.01.04 LUẬN VĂN THẠC SĨ: HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TS VŨ ĐỨC THI Hà Nội - 2016 1 LỜI CẢM ƠN Đầu tiên, tôi xin gửi lời biết ơn sâu sắc đến thầy Giáo sư, Tiến sĩ Vũ Đức Thi, thầy đã dành nhiều thời gian và tâm huyết hướng dẫn và giúp tôi hoàn thành tốt luận văn tốt nghiệp này. Thầy đã định hướng nghiên cứu các kiến thức cần thiết và hữu ích đúng trọng tâm của vấn đề, đồng thời tạo mọi điều kiện thuận lợi nhất cho tôi trong quá trình học tập và nghiên cứu đề tài luận văn. Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy, cô giáo trường Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho bản thân tôi. Tôi xin gửi lời cảm ơn đến các thấy và các anh chị đã thường xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn. Cuối cùng, tôi cũng bày tỏ lòng biết ơn về sự giúp đỡ của các anh, chị đang công tác tại Cục Cảnh sát đăng ký, quản lý cư trú và cơ sở dữ liệu quốc gia về dân cư; và Văn phòng Bộ - cơ quan nơi tôi công tác đã tạo điều kiện tốt nhất cho tôi về thời gian cũng như động viên tôi hoàn thành luận văn. Một lần nữa, tôi xin chân thành cảm ơn ! Hà Nội, tháng 10 năm 2016 Học viên Bùi Trung Hiếu 2 LỜI CAM ĐOAN Những kiến thức trình bày trong luận văn là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu. Trong quá trình làm luận văn, tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Tôi xin cam đoan đây là công trình nghiên cứu của tôi và không sao chép của bất kỳ ai. Hà Nội, tháng 10 năm 2016 Học viên Bùi Trung Hiếu 3 MỤC LỤC LỜI CẢM ƠN ................................................................................................................1 LỜI CAM ĐOAN ..........................................................................................................2 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT ............................................................5 DANH MỤC HÌNH VẼ.................................................................................................7 DANH SÁCH BẢNG BIỂU ..........................................................................................8 MỞ ĐẦU .........................................................................................................................9 CHƢƠNG I. MỘT SỐ VẤN ĐỀ VỀ SƠ SỞ DỮ LIỆU ...........................................11 1.1. Những khái niệm cơ bản ..................................................................................11 1.1.1. Khái quát về mô hình dữ liệu ......................................................................11 1.1.2. Các khái niệm cơ bản và hệ tiên đề Armstrong...........................................12 1.1.2.1. Quan hệ .................................................................................................12 1.1.2.2. Phụ thuộc hàm ......................................................................................13 1.1.2.3. Hệ tiên đề Armstrong ...........................................................................13 1.1.2.4. Sơ đồ quan hệ .......................................................................................15 1.2. Những vấn đề liên quan đến khóa...................................................................15 1.2.1. Khóa ............................................................................................................15 1.2.2. Thuật toán liên quan đến khóa ....................................................................16 1.2.2.1. Thuật toán tìm khóa tối tiểu của một sơ đồ quan hệ ............................17 1.2.2.2. Thuật toán tìm một khóa tối tiểu của một quan hệ ...............................17 1.3. Chuẩn hóa .........................................................................................................17 1.3.1. Các khái niệm cơ bản ..................................................................................18 1.3.2. Các thuật toán liên quan đến chuẩn hóa ......................................................19 1.4. Ngôn ngữ xử lý bảng ........................................................................................20 1.4.1. Các phép toán cơ bản...................................................................................20 1.4.1.1. Phép hợp (r  t) ...................................................................................21 1.4.1.2. Phép trừ (r – t) ......................................................................................21 1.4.1.3. Phép giao (r  t) ..................................................................................21 1.4.1.4. Tích Đề các ...........................................................................................22 1.4.1.5. Phép chiếu ............................................................................................23 1.4.1.6. Phép chọn .............................................................................................23 1.4.2. Các phép toán khác ......................................................................................24 1.4.2.1. Phép chia (r  s) ...................................................................................24 1.4.2.2. Phép nối  .............................................................................................24 1.4.2.3. Phép nối ................................................................................................25 CHƢƠNG II. KHO DỮ LIỆU....................................................................................26 2.1. Kiến trúc chung về kho dữ liệu .......................................................................26 2.1.1. Tầng xử lý dữ liệu .......................................................................................26 2.1.2. Tầng kho dữ liệu ..........................................................................................27 2.1.3. Tầng khai thác dữ liệu .................................................................................27 2.2. Một số thành phần cơ bản của kho dữ liệu ....................................................28 2.2.1. Kho dữ liệu trong DBMS ............................................................................28 2.2.2. Nguồn dữ liệu ..............................................................................................29 2.2.3. Siêu dữ liệu meta data .................................................................................29 2.2.4. Công cụ truy cập ..........................................................................................30 2.2.5. Kho dữ liệu chủ đề ......................................................................................31 2.2.6. Quản trị kho dữ liệu .....................................................................................32 4 2.2.7. Hệ thống thông tin .......................................................................................33 2.3. Công cụ kho dữ liệu của Microsoft .................................................................33 2.3.1. Dịch vụ tich hợp dữ liệu ..............................................................................34 2.3.2. Dịch vụ Báo cáo ..........................................................................................38 2.3.3. Dịch vụ phân tích.........................................................................................41 2.3.4. Bộ công cụ phát triển tri tuệ doanh nghiệp .................................................43 2.3.5. Công cụ quản lý SQL Server .......................................................................44 2.3.6. Dịch vụ tác nhân SQL Server ......................................................................45 CHƢƠNG III. THỬ NGHIỆM GIẢI QUYẾT BÀI TOÁN QUẢN LÝ DÂN CƢ 47 3.1. Mô tả bài toán quản lý dân cƣ .........................................................................47 3.2. Các chỉ tiêu của bài toán quản lý dân cƣ........................................................49 3.2.1. Nguyên tắc thiết kế ......................................................................................49 3.2.2. Các yêu cầu thiết kế .....................................................................................49 3.2.3. Nhu cầu xử lý dữ liệu ..................................................................................50 3.2.4. Kho dữ liệu gốc về công dân .......................................................................51 3.3. Hệ thống biểu mẫu............................................................................................52 3.3.1. Biểu mẫu thu thập, cập nhật thông tin dân cư .............................................52 3.3.2. Biểu mẫu thống kê dữ liệu...........................................................................60 3.4. Quy mô bài toán ................................................................................................63 3.4.1. Mục tiêu đầu tư ............................................................................................63 3.4.2. Quy mô đầu tư .............................................................................................64 3.5. Phần mềm thủ nghiệm .....................................................................................64 3.5.1. Mô hình kiến trúc hệ thống tổng thể ...........................................................64 3.5.2. Thiết kế Cơ sở dữ liệu .................................................................................66 3.5.3. Thiết kế phần mềm nội bộ ...........................................................................68 3.5.4. Thiết kế hạ tầng kỹ thuật .............................................................................69 3.5.5. Giải pháp sinh mã số định danh cá nhân .....................................................71 3.5.6. Giải pháp khai thác, chia sẻ dữ liệu .............................................................72 3.5.6.1. Giới thiệu chung về giải pháp ..............................................................72 3.5.6.2. Đối tượng tham gia khai thác, chia sẻ ..................................................73 3.5.6.3. Công cụ khai thác, chia sẻ và cung cấp dịch vụ công ..........................75 3.5.6.4. Nguyên tắc phân quyền khai thác, chia sẻ dữ liệu ...............................78 3.5.7. Giải pháp đồng bộ dữ liệu Trung tâm dữ liệu chính và Trung tâm dữ liệu dự phòng .....................................................................................................................78 KẾT LUẬN ..................................................................................................................80 TÀI LIỆU THAM KHẢO...........................................................................................81 5 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT STT Từ viết tắt 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Từ hoặc cụm từ ActiveX Data Object.NET ADO.NET Thư viên phần mềm .NET Framework Business Intelligent BI Kinh doanh thông minh Business warehouse BW Kho dữ liệu CSDL Cơ sở dữ liệu CSDLQG Cơ sở dữ liệu quốc gia Database Management System DBMS Hệ quản trị cơ sở dữ liệu Extract – Transform – Load ETL Trích xuất – Chuyển đổi – Tải File Transfer Protocol FTP Giao thức truyền tập tin Hybrid OLAP HOLAP OLAP kết hợp HyperText Transfer Protocol HTTP Giao thức truyền tải siêu văn bản Multidimensional OLAP MOLAP OLAP đa chiều Online Analysis Processing OLAP Xử lý phân tích trực tuyến Object Linking and Embedding, Database OLE DB Đối tượng kết nối và nhúng cơ sở dữ liệu Relational Database Management System RDBMS Hệ quản trị cơ sở dữ liệu quan hệ Relational OLAP ROLAP OLAP quan hệ Server Querry Language SQL Ngôn ngữ truy vấn máy chủ SQL Server Analysis Service SSAS Dịch vụ phân tích máy chủ SQL SQL Server Integration Service SSIS Dịch vụ tích hợp dữ liệu máy chủ SQL 6 19 SSMS 20 SSRS 21 T-SQL 22 XML SQL Server Management Studio Công cụ quản trị máy chủ SQL SQL Server Reporting Service Dịch vụ báo cáo máy chủ SQL Transact-SQL Ngôn ngữ SQL mở rộng eXtensible Markup Language Ngôn ngữ đánh dấu mở rộng 7 DANH MỤC HÌNH VẼ Hình 1.1. – Quan hệ r1 và quan hệ r2 Hình 1.2. – Mối quan hệ giữa lớp quan hệ và phụ thuộc hàm Hình 1.3. – Mối quan hệ giữa lớp các họ phụ thuộc hàm với hàm đóng Hình 1.4. – Mối quan hệ giữa lớp họ phụ thuộc hàm với lớp các hệ Sperner Hình 1.5. – Phân lớp các dạng chuẩn của cơ sở dữ liệu Hình 1.6. – Quan hệ r và quan hệ t Hình 2.1. – Kiến trúc hệ thống Kho dữ liệu Hình 2.2. – Kiến trúc dịch vụ tích hợp SSIS Hình 2.3. – Ví dụ về một luồng dữ liệu Hình 2.4. – Kiến trúc dịch vụ báo cáo SSRS Hình 2.5. – Kiến trúc dịch vụ phân tích SSAS Hình 2.6. – Màn hình khởi tạo mẫu dự án DW/BI trong BIDS Hình 2.7. – Màn hình quản lý của SQL Server Hình 2.8. – Màn hình tạo công việc Hình 3.1. – Biểu mẫu thu thập thông tin dân cư Hình 3.2. – Biểu mẫu cập nhật, chỉnh sửa thông tin dân cư Hình 3.3. – Biểu mẫu Tờ khai nhân khẩu Hình 3.4. – Biểu mẫu phiếu báo thay đổi hộ khẩu, nhân khẩu Hình 3.5. – Biểu mẫu phiếu khai báo tạm vắng Hình 3.6. – Biểu mẫu tờ khai căn cước công dân Hình 3.7. – Biểu mẫu phiếu thu nhận thông tin căn cước công dân Hình 3.8. – Biểu mẫu tờ khai xin cấp hộ chiếu Hình 3.9. – Thống kê việc cấp và quản lý căn cước công dân Hình 3.10. – Thống kê hộ, nhân khẩu Hình 3.11. – Thống kê đăng ký, quản lý cư trú Hình 3.12. – Kiến trúc hệ thống Cơ sở dữ liệu quốc gia về dân cư Hình 3.13. – Mô hình dữ liệu trong hệ thống Cơ sở dữ liệu quốc gia về dân cư Hình 3.14. – Gói phần mềm ứng dụng trong hệ thống Cơ sở dữ liệu quốc gia về dân cư Hình 3.15. – Mô hình thiết kế tổng thể hạ tầng hệ thống Cơ sở dữ liệu quốc gia về dân cư Hình 3.16. – Môi trường của hệ thống Cơ sở dữ liệu quốc gia về dân cư 8 DANH SÁCH BẢNG BIỂU Bảng 1.1. – Quan hệ r Bảng 1.2. – Phép nối r  t  Bảng 1.3. – Phép nối r  t 9 MỞ ĐẦU Trong công tác quản lý dân cư hiện nay, theo đặc thù quản lý Nhà nước của từng ngành, mỗi Bộ, ngành lưu trữ dữ liệu về dân cư theo phạm vi quản lý hành chính của mình mà trong đó chủ yếu được quản lý theo phương pháp thủ công, mất nhiều thời gian, công sức khi quản lý công dân. Đặc biệt tại các thành phố lớn, các khu công nghiệp có mật độ dân cư, số lượng người dân dịch chuyển lớn thì việc quản lý là hết sức phức tạp. Thực tế này đòi hỏi công tác quản lý dân cư cần phải áp dụng các phương pháp tiên tiến ứng dụng kỹ thuật công nghệ thông tin, nhằm tăng hiệu quả và năng suất trong công tác quản lý công dân. Thủ tục hành chính tại nước ta với điểm chung là hầu hết đều được thực hiện thủ công và đòi hỏi công dân phải tự chính minh về nhân thân của mình thông qua việc xuất trình hoặc nộp bản sao có chứng thực các giấy tờ, hồ sơ để thực hiện thủ tục hành chính, và các kết quả giải quyết thủ tục hành chính cũng chưa được chia sẻ, sử dụng chung nên đã tạo ra gánh nặng hành chính lên tới hàng ngàn tỷ đồng mỗi năm cho các cá nhân, tổ chức khi tham gia vào các giao dịch hành chính. Đây là một sự lãng phí lớn cho xã hội, và là một trong những cản trở cho sự phát triển kinh tế - xã hội của đất nước trong hiện tại và tương lại nếu không có sự đột phá mang tính chiến lược trong cải cách hành chính và cải cách thủ tục hành chính. Hiện nay, Việt Nam chưa xây dựng một hệ thống quản lý dân cư đồng bộ trên toàn quốc. Một số địa phương chủ động xây dựng hệ thống quản lý dân cư trong phạm vi hành chính của mình, nhưng các hệ thống này chưa hoàn chỉnh, không thống nhất về kỹ thuật và công nghệ nên chưa thể đồng bộ dữ liệu với nhau. Ngoài ra, việc chia sẻ thông tin dân cư giữa các Bộ, Ngành và địa phương gặp nhiều khó khăn do chưa có cơ chế phối hợp trong quan hệ hành chính và chưa đảm bảo yêu cầu bảo mật thông tin. Công tác quản lý dân cư của các Bộ, ngành và địa phương hiện nay đang tồn tại một số nhược điểm sau: - Thiếu cách tiếp cận tổng thể, chỉ xuất phát từ mục đích yêu cầu cụ thể của riêng tổ chức mình. - Thiếu thiết kế theo chuẩn thống nhất nên khó kết nối liên thông để trao đổi, chia sẻ dữ liệu. - Dữ liệu trùng lắp, sai lệch rất nhiều, khó quản lý. - Dữ liệu thiếu nhất quán, chính xác do không được cập nhật kịp thời, đồng bộ và dữ liệu bị phân tán. Trước những yêu cầu thực tế trong công tác quản lý dân cư, thách thức cải cách thủ tục hành chính cho người dân, vấn đề xây dựng một hệ thống CSDLQG về dân cư là vấn đề cần thực hiện ngay từ sớm (như Hungari thực hiện xây dựng 10 hệ thống cơ sở dữ liệu dân cư từ thập niên 70 của thế kỷ 20) để giải quyết những tồn tại trong hoạt động hành chính nhà nước. Luận văn này với đề tài “Nghiên cứu một số vấn đề về cơ sở dữ liệu và ứng dụng trong bài toán quản lý dân cư” giới thiệu những lý thuyết cơ bản về cơ sở dữ liệu, kho dữ liệu để từ đó ứng dụng vào giải quyết bài toán quản lý dân cư trong hệ thống quản lý hành chính nhà nước của Việt Nam hiện nay. Luận văn gồm ba chương: Chương 1. Một số vấn đề về cơ sở dữ liệu giới thiệu những khái niệm cơ bản, vấn đề liên quan đến khóa, chuẩn hóa và ngôn ngữ xử lý bảng. Chương 2. Kho dữ liệu giới thiệu kiến trúc chung, một số thành phần cơ bản và công cụ kho dữ liệu của Microsoft. Chương 3. Thử nghiệm giải quyết bài toán quản lý dân cư mô tả bài toán quản lý dân, đưa ra các chỉ tiêu, hệ thống bảng biểu, quy mô bài toán và phần mềm thử nghiệm giải quyết bài toán dân cư. 11 CHƢƠNG I. MỘT SỐ VẤN ĐỀ VỀ SƠ SỞ DỮ LIỆU 1.1. Những khái niệm cơ bản 1.1.1. Khái quát về mô hình dữ liệu Thông thường đối với việc thiết kế và xây dựng các hệ thông tin quản lý, chúng ta cần xử lý các file dữ liệu. Những file này bao gồm nhiều bản ghi (record) có cùng một cấu trúc xác định (loại bản ghi). Đồng thời, mỗi bản ghi được phân chia thành các trường dữ liệu (field). Một CSDL là một hệ thống các file dữ liệu, mỗi file này có cấu trúc bản ghi khác nhau, nhưng về mặt nội dung có quan hệ với nhau. Một hệ quản trị CSDL là một hệ thống quản lý và điều hành các file dữ liệu. Nói chung một hệ quản trị CSDL thường có những đặc tính sau: - Có tính độc lập với các công cụ lưu trữ, - Có tính độc lập với các chương trình phần mềm của người sử dụng (có nghĩa là các ngôn ngữ lập trình khác nhau có thể được dùng trong hệ này), - Có khả năng tại một thời điểm truy nhập vào nhiều nơi trong hệ này, - Có khả năng khai thác tốt tiềm năng của máy, - Người dùng với kiến thức tối thiểu cũng có thể sử dụng được hệ này, - Bảo đảm an toàn dữ liệu và bảo mật dữ liệu, - Thuận lợi và mềm dẻo trong việc bổ sung, loại bỏ, thay đổi dữ liệu, - Giảm bớt sự dư thừa dữ liệu trong lưu trữ. Trong quá trình thiết kế và xây dựng các hệ quản trị CSDL, 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 các mối quan hệ bản chất của các dữ liệu mà các dữ liệu này phản ánh các mối quan hệ và các thực thể trong thế giới hiện thực. Có thể thấy mô hình dữ liệu phản ánh khía cạnh cấu trúc lôgic mà không đi vào khía cạnh vật lý của các CSDL. Khi xây dựng các mô hình dữ liệu cần phân biệt các thành phần cơ bản sau: - Thực thể (entity): đó là đối tượng có trong thực tế mà chúng ta cần mô tả các đặc trưng của chúng. - Thuộc tính (Properties): đó là các dữ liệu thể hiện các đặc trưng của thực thể. - Ràng buộc (Relation): đó là các mối quan hệ lôgic của các thực thể. Tuy vậy, ba thành phần cơ bản trên được thể hiện ở hai mức: - Mức loại dữ liệu (type): là sự khái quát hóa các ràng buộc, các thuộc tính, các thực thể cụ thể. - Mức thể hiện: là một ràng buộc cụ thể, hoặc là các giá trị thuộc tính, hoặc là một thực thể cụ thể. 12 Thông thường chúng ta sẽ nhận được các loại dữ liệu (type) của các đối tượng cần khảo sát trong quá trình phân tích các thể hiện cụ thể của chúng. Yếu tố quan trọng nhất của cấu trúc CSDL là dạng cấu trúc dữ liệu mà trong đó các mối quan hệ giữa cá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 (record type). 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ủa CSDL. 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. Trên thực tế chúng ta phân biệt hai loại mô hình dữ liệu: - Mô hình dữ liệu mạng: Trong đó chúng ta thể hiện trực tiếp các ràng buộc tùy ý giữa các loại bản ghi. - Mô hình dữ liệu quan hệ: Trong mô hình này các ràng buộc trên được thể hiện qua các quan hệ (bảng). Mô hình dữ liệu quan hệ là một công cụ rất tiện lợi để mô tả cấu trúc lôgic của các CSDL. Như vậy, ở mức lôgic mô hình này bao gồm các file được biểu diễn dưới dạng các bảng. Do đó đơn vị của CSDL 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 loại bản ghi), còn tên các cột là các thuộc tính. Theo cách nhìn của người sử dụng thì một CSDL quan hệ là một tập hợp các bảng biến đổi theo thời gian. 1.1.2. Các khái niệm cơ bản và hệ tiên đề Armstrong Phần này trình bài những khái niệm cơ bản nhất về mô hình dữ liệu quan hệ của E.F.Codd. Những khái niệm cơ bản này gồm các khái niệm về quan hệ, thuộc tính, phụ thuộc hàm, hệ tiên đề Armstrong, khóa, dạng chuẩn… Những khái niệm này đóng vai trò rất quan trọng trong mô hình dữ liệu quan hệ. Chúng được áp dụng nhiều trong việc thiết kế các hệ quản trị CSDL hiện nay. 1.1.2.1. Quan hệ R = {a1,…,an} là một tập hữu hạn và không rỗng các thuộc tính. Mỗi thuộc tính ai có miền giá trị là Dai. Khi đó r là một tập hợp các bộ {h 1,…,hm} được gọi là một quan hệ trên R với hj (j=1,…m) là một hàm: hj : R →  Dai ai  R sao cho: hj (ai)  Dai Có thể biểu diễn quan hệ r thành Bảng 1.1: 13 h1 h2 ai a2 an h1(a1) h1(a2) …… h1(an) h2(a1) h2(a2) …… h2(an) ……………………………………… hm hm(a1) hm(a2) hm(an) Bảng 1.1. Quan hệ r 1.1.2.2. Phụ thuộc hàm Cho R = {a1, … , an} là tập các thuộc tính r = {h1, … , hm} là một quan hệ trên R và A, B  R/ Khi đó chúng ta nói A xác định hàm cho B hay B phụ thuộc hàm vào A f trong r (Kí pháp A r > B) nếu (  hi, hj  r)((  a  A)(hi(a) = hj(a))  (  b  B)(hi(b) = hj(b))) f Đặt Fr = {(A, B): A, B  R, A r > B). Lúc đó Fr được gọi là họ đầy đủ các phụ thuộc hàm của r. Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ liệu) xảy ra tự nhiên nhất giữa các tập thuộc tính. Dù hiện nay đã có nhiều loại phụ thuộc dữ liệu được nghiên cứu, xong về cơ bản các hệ quản trị CSDL lớn sử dụng phụ thuộc hàm. Phụ thuộc hàm trên tập các thuộc tính R là một dãy kí tự có dạng A  B, ở đây A, B  R. chúng ta nói phụ thuộc hàm A  B đúng trong quan hệ r f nếu A r > B. Chúng ta cũng nói rằng r thỏa mãn A  B. Dễ thấy, Fr là tập tất cả các phụ thuộc hàm đúng trong r. Có thể viết (A, f B) hoặc A  B thay cho A r > B mà không bị lẫn về mặt kí pháp. 1.1.2.3. Hệ tiên đề Armstrong R là tập các thuộc tính và kí pháp P(R) là tập các tập con của R. Cho Y  P(R) x P(R). Chúng ta nói Y là một họ f trên R nếu đối với  A, B, C, D  R thì (1) (A, A)  Y, (2) (A, B)  Y, (B, C)  Y  (A, C)  Y, (3) (A, B)  Y, A  C, D  B  (C, D)  Y, (4) (A, B)  Y, (C, D)  Y  (A  C, B  D)  Y. Rõ ràng, Fr là một họ f trên R. 14 Trong (1), A. A. Armstrong đã chứng minh một kết quả rất quan trọng như sau: Nếu Y là một họ f bất kỳ thì tồn tại một quan hệ r trên R sao cho F r = Y. Kết quả này cùng với định nghĩa của phụ thuộc hàm chứng tỏ rằng hệ tiên đề Armstrong là đúng đắn và đầy đủ. Mặt khác, hệ tiên đề này cho chúng ta những đặc trưng của họ các phụ thuộc hàm, mà các đặc trưng này không phụ thuộc vào các quan hệ (bảng) cụ thể. Nhờ có hệ tiên đề này, các công cụ của toán học được áp dụng để nghiên cứu làm sáng tỏ cấu trúc logic của mô hình dữ liệu quan hệ. Đặc biệt chúng ta sử dụng công cụ thuật toán để thiết kế các công đoạn xây dựng các hệ quản trị CSDL. Chúng ta đưa ra ví dụ chỉ ra có nhiều quan hệ khác nhau xong các họ đầy đủ các phụ thuộc hàm của chúng lại như nhau. Cho r1 và r2 là các quan hệ trong Hình 1.1 a b a b 0 0 0 0 r1 = 1 1 r2 = 1 1 2 1 2 1 3 2 3 1 Hình 1.1. Quan hệ r1 và quan hệ r2 Có thể thấy r1 và r2 khác nhau nhưng Fr1 = Fr2. Như vậy, tương quan giữa lớp các quan hệ với lớp các họ phụ thuộc hàm có thể được thể hiện bằng Hình 1.2: Lớp các quan hệ Lớp các phụ thuộc hàm Hình 1.2.Mối quan hệ giữa lớp quan hệ với phụ thuộc hàm Một hàm L: P(R)  P(R) được gọi là một hàm đóng trên R nếu với  A, B  P(R) thì: - A  L(A), 15 - Nếu A  B thì L(A)  L(B), - L(L(A)) = L(A). Nếu F là một họ f và chúng ta đặt LF = {a: a R và (A, {a})  F} Thì LF là một hàm đóng. Ngược lại, nếu L là một hàm đóng thì tồn tại duy nhất một họ f(F) trên R sao cho L = LF, ở đây: F = {(A, B): A, B  R, B  L(A)}. Như vậy, chúng ta thấy một tương ứng 1-1 giữa lớp các hàm đóng và lớp các họ f. Chúng ta có Hình 1.3: Lớp các họ phụ thuộc hàm Lớp các hàm đóng Hình 1.3. Mối quan hệ giữa lớp các họ phụ thuộc hàm với hàm đóng 1.1.2.4. Sơ đồ quan hệ Sơ đồ quan hệ s là một cặp , ở đây R là tập các thuộc tính và F là tập các phụ thuộc hàm trên R. Kí pháp F+ là tập tất cả các phụ thuộc hàm được dẫn xuất từ F bằng việc áp dụng các quy tắc trong hệ tiên đề Armstrong. Đặt A+ = {a: A  {a}  F+}. A+ được gọi là bao đóng của A trên s. Có thể thấy rằng A  B  F+ nếu và chỉ nếu B  A+. f Tương tự đặt Ar+ = {a: A r >{a}}. Ar+ được gọi là bao đóng của A trên r. Theo [1] có thể thấy nếu s = là sơ đồ quan hệ thì có quan hệ r trên R sao cho Fr = F+. Quan hệ r như vậy gọi là quan hệ Armstrong của s. Trong trường hợp này hiển nhiên các phụ thuộc hàm của s đúng trong r. 1.2. Những vấn đề liên quan đến khóa 1.2.1. Khóa Giả sử r là một quan hệ, s = là một sơ đồ quan hệ, Y là một họ f trên R và A  R. Khi đó, A là một khóa của r (tương ứng là một khóa của s, một khóa f của Y) nếu A r > R (A  R  F+, (A, R)  Y). Chúng ta gọi A là một khóa tối tiểu của r (tương ứng của s, của Y) nếu: - A là một khóa của r (s, Y), 16 - Bất kỳ một tập con thực sự của A không là khóa của r (s, Y). Kí pháp Kr (Ks, KY) tương ứng là tập tất cả các khóa tối tiểu của r (s, Y) K (một tập con của P(R)) là một hệ Sperner trên R nếu với  A, B  K  A  B. K , K , K là các hệ Sperner trên R. r s Y  Phản khóa Giả sử K là một hệ Sperner trên R, khi đó định nghĩa tập các phản khóa K, kí hiệu là K-1 như sau: K-1 = {A  R: (B K)  (B  A) & nếu (A  C)  (  B  K)(B  C), dễ thấy K-1 cũng là một hệ Sperner trên R. Tập phản khóa đóng vai trò rất quan trọng trong quá trình nghiên cứu cấu trúc logic của các họ phụ thuộc hàm, khóa, dạng chuẩn, quan hệ Armstrong, đặc biệt đối với các bài toán tổ hợp trong mô hình dữ liệu quan hệ. Ở các phần trên đã chỉ ra rằng, nếu s = là một sơ đồ quan hệ trên R thì KS là hệ Sperner trên R. Ngược lại, nếu K là một hệ Sperner bất kỳ trên R thì tồn tại một sơ đồ quan hệ s sao cho KS = K. Mối quan hệ giữa lớp họ phụ thuộc hàm và lớp các hệ Sperner thể hiện qua Hình 1.4: Lớp các họ phụ thuộc hàm Lớp các hệ Sperner Hình 1.4. Mối quan hệ giữa lớp họ phụ thuộc hàm với lớp các hệ Sperner  Khóa tối tiểu Giả sử k = là một tập thuộc tính của khóa. Khi đó, k là tập thuộc tính của khóa tối tiểu nếu với mọi tập thuộc tính của khóa h = tương đương với tập thuộc tính của khóa k có |K|  |H|. |K| là số lượng các thuộc tính trong K. 1.2.2. Thuật toán liên quan đến khóa Khi giải quyết các bài toán quản lý thông tin, chúng ta thường sử dụng các hệ quản trị CSDL mà trong đó chứa CSDL quan hệ. Các phép xử lý đối với lớp bài toán này thường là tìm kiếm bản ghi sau đó thay đổi nội dung bản ghi, thêm bản ghi mới hoặc xóa bản ghi cũ. Trong các thao tác trên việc tìm kiếm bản ghi là rất quan trọng. Muốn tìm được bản ghi trong một file dữ liệu chúng ta phải xây dựng khóa cho file dữ liệu đó. 17 Việc xây dựng khóa ở đây chính là xây dựng khóa tối tiểu. 1.2.2.1. Thuật toán tìm khóa tối tiểu của một sơ đồ quan hệ Sơ đồ quan hệ s = trong đó: F là tập các phụ thuộc hàm R = {a1, a2, … , an} là tập các thuộc tính. Để tìm khóa tối thiểu K, cần thực hiện tính liên tiếp các tập thuộc tính K 0, K1, …, Kn như sau: K0 = R = {a1, a2, … , an} Ki-1 nếu Ki-1 – {ai}  R  F+ K= Ki-1 – {ai} ngược lại K = Kn là khóa tối tiểu. Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên chúng ta có thể tìm được một khóa tối tiểu khác. Chú ý, không nhất thiết đặt K0 = R mà có thể đặt K0 = A, ở đây A là một khóa. Khi đó thuật toán vẫn tính ra một khóa tối tiểu. 1.2.2.2. Thuật toán tìm một khóa tối tiểu của một quan hệ Quan hệ r = {h1, h2, … , hm} trên tập thuộc tính R = {a1, a2, … , an}. Hệ bằng nhau của quan hệ r được định nghĩa như sau: Er = {Eij: 1  i  j  m}, ở đây Eij = {a  R: hi(a) = hj(a)} Dễ dàng thấy rằng Er được tính bằng thời gian đa thức từ r. Thuật toán tìm một khóa tối tiểu của một quan hệ r = {h 1, h2, …, hm} là một quan hệ trên tập thuộc tính R = {a1, a2, …, an} như sau: Bước 1: Tính Er = {A1, A2, … , Ai} Bước 2: Tính Mr = {A: có Aj  Er : A = Aj và không có Ai : Ai  E: A  Ai} Bước 3: Lần lượt tính các tập thuộc tính khóa K0, K1, K2…Kn tính theo quy tắc: K0 = R = {a1, a2, …, an} hoặc K0 là một khóa đã biết. Ki = Ki-1 – {ai} nếu không tồn tại A  Mr sao cho Ki-1 – {ai}  A hoặc Ki = Ki-1 trong trường hợp ngược lại. Bước 4: Đặt K = Kn, khi đó K là khóa tối tiểu. Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên, chúng ta sẽ tìm được một khóa tối tiểu khác. 1.3. Chuẩn hóa Việc chuẩn hóa các quan hệ cũng như các sơ đồ quan hệ đóng vai trò cực kì quan trọng trong việc thiết kế các hệ quản trị CSDL trên mô hình dữ liệu của 18 Codd. Nhờ có chuẩn hóa các quan hệ và các sơ đồ quan hệ, chúng ta tránh được việc dư thừa dữ liệu và chúng tăng tốc độ của các phép toán xử lý quan hệ. 1.3.1. Các khái niệm cơ bản Chúng ta định nghĩa các dạng chuẩn như sau: Cho r = {h1, h2, … hm} là quan hệ trên R = {a1, a2, … , an}.  Dạng chuẩn 1 – 1NF Khi đó r là dạng chuẩn 1 nếu các phần tử trong r là sơ cấp, nghĩa là giá trị hi(aj) (với i = 1, 2, …,m và j = 1, 2, …, n) không phân chia được nữa.  Dạng chuẩn 2 – 2NF Quan hệ r ở trên là dạng chuẩn 2 nếu - r là dạng chuẩn 1 - A  {a}  Fr đối với mọi khóa tối thiểu K, A  K và a là thuộc tính thứ cấp.  Dạng chuẩn 3 – 3NF Quan hệ r ở trên là dạng chuẩn 3 nếu: A  {a}  Fr đối với A mà A+  R, a  A, a   K. Có nghĩa rằng: + K là một khóa tối tiểu. + a là thuộc tính thứ cấp. + A không là khóa. + A  {a} không đúng trong r.  Dạng chuẩn BCNF Boye-Codd Quan hệ r là dạng chuẩn của Boye-Codd nếu: A  {a}  Fr đối với A mà A+  R, a  A. Qua định nghĩa, chúng ta có thể thấy dạng chuẩn BCNF là 3NF và 3NF là 2NF. Tuy vậy, chúng ta có thể đưa ra các ví dụ chứng tỏ có quan hệ là 2NF nhưng không là 3NF và có quan hệ là 3NF nhưng không là BCNF. Nói cách khác là lớp các quan hệ BCNF là lớp con thực sự của lớp các quan hệ 3NF và lớp các quan hệ 3NF này lại là lớp con thực sự của các lớp các quan hệ 2NF. Đối với s = thì các dạng chuẩn 2NF, 3NF, BCNF trong đó chúng ta thay Fr bằng F+. Chú ý là đối với sơ đồ quan hệ chúng ta không có dạng 1NF. Việc phân lớp các dạng chuẩn được thể hiện qua Hình 1.5: