Tài liệu Loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu quan hệ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CAO THỊ NHÂM LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CƠ SỞ DỮ LIỆU QUAN HỆ LUẬN VĂN THẠC SĨ Hà Nội - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Cao Thị Nhâm LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CƠ SỞ DỮ LIỆU QUAN HỆ Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Lê Huy Thập Hà Nội - 2009 3 MỤC LỤC LỜI CAM ĐOAN............................................................................................................1 LỜI CẢM ƠN..................................................................................................................2 MỤC LỤC .......................................................................................................................3 DANH MỤC HÌNH VẼ ..................................................................................................5 DANH MỤC BẢNG .......................................................................................................6 HỆ THỐNG CÁC TỪ VIẾT TẮT ..................................................................................8 MỞ ĐẦU .........................................................................................................................9 Chương 1 1.1 CƠ SỞ LÝ THUYẾT ..............................................................................12 CƠ SỞ DỮ LIỆU QUAN HỆ.........................................................................12 1.1.1 Khái niệm về CSDL quan hệ...................................................................12 1.1.2 Các phép toán đại số quan hệ ..................................................................16 1.2 PHÂN MẢNH CƠ SỞ DỮ LIỆU QUAN HỆ ...............................................23 1.2.1 Khái quát về cơ sở dữ liệu phân tán ........................................................23 1.2.2 Các kiểu phân mảnh cơ sở dữ liệu ..........................................................25 1.3 LÝ THUYẾT CHẮC CHẮN.........................................................................29 1.3.1 Hệ số chắc chắn dành cho dữ kiện ..........................................................29 1.3.2 Hệ số chắc chắc chắn dành cho luật........................................................30 1.3.3 Các quy tắc tính toán trên CF..................................................................30 1.4 TỔNG KẾT CHƯƠNG 1 ...............................................................................32 Chương 2 THUẬT TOÁN LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CSDL QUAN HỆ ..........................................................................................................33 2.1 TƯ TƯỞNG CỦA THUẬT TOÁN ................................................................33 2.2 TIÊU CHUẨN THẨM ĐỊNH BẢN GHI NHÂN BẢN THỪA ....................33 2.3 NỘI DUNG THUẬT TOÁN ..........................................................................35 4 2.3.1 Thuật toán xác định độ chắc chắn lặp cho từng bản ghi .........................35 2.3.2 Thuật toán loại bỏ bản ghi nhân bản thừa ...............................................36 2.3.3 Nhận xét thuật toán .................................................................................38 2.4 TỔNG KẾT CHƯƠNG 2 ...............................................................................39 Chương 3 ỨNG DỤNG THUẬT TOÁN .................................................................40 3.1 HỆ THỐNG LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CSDL QUAN HỆ .................................................................................................................40 3.1.1 Mô tả bài toán..........................................................................................40 3.1.2 Yêu cầu đặt ra đối với hệ thống ..............................................................40 3.1.3 Khả năng giải quyết bài toán...................................................................41 3.1.4 Sơ đồ hệ thống.........................................................................................42 3.2 THIẾT KẾ HỆ THỐNG LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CSDL QUAN HỆ ......................................................................................................49 3.2.1 Xây dựng các lớp đối tượng ....................................................................49 3.2.2 Biểu đồ tuần tự ........................................................................................59 3.3 KẾT QUẢ ỨNG DỤNG THUẬT TOÁN ......................................................61 3.3.1 Môi trường phát triển ..............................................................................61 3.3.2 Kết quả thực nghiệm ...............................................................................62 3.4 TỔNG KẾT CHƯƠNG 3 ...............................................................................68 Chương 4 KẾT LUẬN & HƯỚNG PHÁT TRIỂN .................................................69 4.1.1 Kết quả thu được trong quá trình nghiên cứu đề tài................................69 4.1.2 Hướng phát triển......................................................................................69 TÀI LIỆU THAM KHẢO .............................................................................................71 5 DANH MỤC HÌNH VẼ Hình 1-1 Kiến trúc cơ sở dữ liệu phân tán .................................................................23 Hình 1-2 Phân mảnh hỗn hợp của quan hệ EMP ........................................................27 Hình 3-1 Các tầng xử lý của hệ thống........................................................................42 Hình 3-2 Luồng xử lý của hệ thống EDRS ................................................................44 Hình 3-3 Sơ đồ tương tác giữa các lớp trong hệ thống ..............................................51 Hình 3-4 Biểu đồ tuần tự của quá trình loại bỏ bản ghi nhân bản..............................59 Hình 3-5 Biểu đồ tuần tự của quá tình xử lý bản ghi nghi ngờ nhân bản .....................60 Hình 3-6 Biểu đồ tuần tự của quá trình thiết lập luật cho hệ thống ..............................60 6 DANH MỤC BẢNG Bảng 1-1 Quan hệ EMP.................................................................................................13 Bảng 1-2 Quan hệ EMP1 ............................................................................................14 Bảng 1-3 Quan hệ NHÂNVIÊN....................................................................................17 Bảng 1-4 Kết quả phép chọn .........................................................................................17 Bảng 1-5 Kết quả phép chọn .........................................................................................18 Bảng 1-6 Kết quả của các phép toán tập hợp ................................................................19 Bảng 1-7 Tích Đề Các của hai quan hệ R và S .............................................................20 Bảng 1-8 Phép nối tê-ta hai quan hệ..............................................................................21 Bảng 1-9 Phép nối tự nhiên hai quan hệ........................................................................22 Bảng 3-1 Ví dụ về tính toán hệ số chắc chắn ................................................................46 Bảng 3-2 Các lớp thuộc gói Rule Engine ...................................................................49 Bảng 3-3 Các lớp thuộc gói Process..............................................................................50 Bảng 3-4 Bảng thuộc tính của lớp clsRuleReader.........................................................52 Bảng 3-5 Bảng các phương thức của lớp clsRuleReader ..............................................52 Bảng 3-6 Bảng thuộc tính của lớp clsRuleEngine.........................................................52 Bảng 3-7 Bảng các phương thức của lớp clsRuleEngine ..............................................53 Bảng 3-8 Bảng các phương thức của lớp clsExpressionEvaluator................................54 Bảng 3-9 Bảng các phương thức của lớp clsProxy .......................................................55 Bảng 3-10 Bảng các thuộc tính của lớp clsDeduplicate................................................55 Bảng 3-11 Bảng các phương thức của lớp clsDeduplicate............................................56 7 Bảng 3-12 Bảng các thuộc tính của lớp clsDAO ..........................................................56 Bảng 3-13 Bảng các phương thức của lớp clsDAO ......................................................57 Bảng 3-14 Bảng các phương thức của lớp clsInterface.................................................57 Bảng 3-15 Bảng các phương thức của lớp clsSetting....................................................58 8 HỆ THỐNG CÁC TỪ VIẾT TẮT Kí hiệu viết tắt EDRS Tên tiếng Anh Eliminate system duplicate CSDL Ý nghĩa record Hệ thống loại bỏ mẩu tin nhân bản thừa Cơ sở dữ liệu CF Certainty factor Hệ số chắc chắn FPE False Positive Error Tỉ lệ phán đoán sai SK Cardr Siêu khóa Cardinality - Row Số bộ Hệ số chắc chắn dùng cho dữ CFf Certainty factor – Fact CFr Certainty factor – Rule Hệ số chắc chắn dùng cho luật RC Recall Tỉ lệ phán đoán đúng kiện 9 MỞ ĐẦU Các ứng dụng làm việc với thông tin nói chung và hệ cơ sở dữ liệu lớn ngày càng phát triển và đóng vai trò quan trọng trong mọi lĩnh vực ứng dụng và nghiên cứu. Đi đôi với sự lớn mạnh của các hệ thống này là sự xuất hiện những dữ liệu “bẩn” và dữ liệu dị thường. Dữ liệu dị thường và dữ liệu “bẩn” làm ảnh hưởng rất nhiều tới hiệu quả xử lý và độ chính xác của kết quả xử lý cũng như ảnh hưởng tới việc biểu diễn và phân tích dữ liệu. Tệ hại hơn có thể làm hệ thống phần mềm trở nên vô giá trị. Dữ liệu dị thường và dữ liệu “bẩn” xuất hiện trong dữ liệu thực là chuyện không thể tránh khỏi, người ta ước tính dữ liệu dị thường và dữ liệu “bẩn” chiếm khoảng 5%. Thực tế này dẫn tới xu hướng phát triển các phương pháp làm sạch dữ liệu. Không có mô tả chung nào cho mục đích và cũng không có mô tả bao quát cho quá trình làm sạch dữ liệu. Làm sạch dữ liệu đòi hỏi rất nhiều loại tri thức cũng như đòi hỏi có nhiều kiến thức về việc xử lý và bảo trì dữ liệu. Mục đích trước hết của làm sạch dữ liệu là loại bỏ những nhân bản thừa trong tập hợp dữ liệu có sẵn. Quá trình làm sạch dữ liệu khó có thể thực hiện được nếu không có sự tham gia của các chuyên gia hay các kiến thức chuyên gia, vì việc loại bỏ dữ liệu dị thường và dữ liệu “bẩn” cần phải có kiến thức chuyên gia về lĩnh vực đó. Quá trình làm sạch dữ liệu là quá trình bán tự động. Nhưng nên xử lý tự động nhiều nhất có thể. Hiệu quả và sự thành công của quá trình làm sạch dữ liệu phụ thuộc rất nhiều vào kiến thức chuyên gia hiện có và những thông tin cần thiết để xác định và chỉnh sửa những dữ liệu dị thường. Làm sạch dữ liệu là một thuật ngữ không rõ ràng và không có định nghĩa chính xác. Nguyên nhân chính là vì mục đích chính của làm sạch dữ liệu là tìm ra “lỗi” trong dữ liệu có sẵn, tuy nhiên thế nào là dữ liệu lỗi và thế nào là không lỗi thì phụ thuộc rất nhiều vào từng lĩnh vực, khó có thể đưa ra một định nghĩa chung. Chính vì điều này, nhiều phương pháp chỉ tập trung vào một phần nhỏ của kiến thức về lĩnh vực đang xét bằng cách sử dụng một số thuật toán cũng như áp dụng kinh nghiệm sẵn có. Có nhiều phương pháp được áp dụng để làm sạch dữ liệu như phân tích cú pháp 10 (parsing), biến đổi dữ liệu (data transformation), tạo các ràng buộc về mặt dữ liệu (Integrity constraint enforcement), phương pháp thống kê… Trong phạm vi luận văn này tôi nghiên cứu phương pháp loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu dựa vào hệ chuyên gia và hệ số chắc chắn(certainty factor). Đóng góp của đề tài là nghiên cứu và xây dựng thuật toán loại bỏ mẩu tin thừa cho một quan hệ của cơ sở dữ liệu quan hệ; xây dựng ứng dụng thực hiện ý đồ của giải thuật; bên cạnh đó là thực hiện kiểm thử chương trình với một quan hệ có số lượng bản ghi từ 50 tới 300. Các nghiên cứu trong luận văn này sẽ hữu ích cho các nghiên cứu ở mức cao hơn như loại bỏ mẩu tin thừa cho một cơ sở dữ liệu quan hệ…. Cấu trúc luận văn được trình bày như sau: Chương 1: Cơ sở lý thuyết. Chương này trình bày về các kiến thức cơ sở dùng cho thuật toán loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu quan hệ. Kiến thức cơ sở gồm hai phần: 9 Cơ sở dữ liệu: Phần này là tóm tắt các kiến thức cơ bản về cơ sở dữ liệu quan hệ cũng như các kiến thức về cơ sở dữ liệu phân tán. Đặc biệt, trong phần này luận văn còn đề cập đến các kiểu phân mảnh trong cơ sở dữ liệu phân tán, kiến thức này là nền tảng cho ý tưởng của thuật toán loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu quan hệ. 9 Lý thuyết chắc chắn: Lý thuyết chắc chắn là kiến thức cơ sở giúp xây dựng thuật toán loại bỏ mẩu tin nhân bản thừa. Nội dung cơ bản là nghiên cứu các luật và suy luận dựa vào các hệ số chắc chắn thu thập được từ hệ các chuyên gia hoặc hệ chuyên gia. Chương 2: Thuật toán loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu quan hệ. Chương này trình bày thuật toán nhận diện bản ghi nhân bản thừa trong cơ sở dữ liệu quan hệ dựa vào kiến thức về cơ sở dữ liệu và lý thuyết chắc chắn ở Chương 1. Chương 3: Ứng dụng thuật toán. Là phần phân tích yêu cầu, thiết kế và cài đặt hệ thống loại bỏ mẩu tin nhân bản thừa trong cơ sở dữ liệu quan hệ. Bên cạnh đó luận văn 11 cũng đưa ra những kết quả kiểm thử trên dữ liệu thật để đi đến những đánh giá về hiệu quả của thuật toán. Chương 4. Kết luận và hướng phát triển. Kết luận, đánh giá những gì đã đạt được và chưa làm được trong luận văn tốt nghiệp và nêu ra hướng phát triển của đề tài là nội dung trình bày của chương này. 12 Chương 1 CƠ SỞ LÝ THUYẾT 1.1 CƠ SỞ DỮ LIỆU QUAN HỆ Các cơ sở dữ liệu và các hệ quản trị cơ sở dữ liệu đã trở thành một thành phần chủ yếu trong cuộc sống hàng ngày của xã hội hiện đại. Trong vòng một ngày con người có thể có nhiều hoạt động cần có sự giao tiếp với cơ sở dữ liệu như: đến ngân hàng để rút tiền và gửi tiền, đăng ký chỗ trên máy bay hoặc khách sạn, truy cập vào thư viện đã tin học hoá để tìm sách báo, đặt mua tạp chí ở một nhà xuất bản… Tại các ngân hàng, các cửa hàng, người ta cũng cập nhật tự động việc quản lý tiền bạc, hàng hoá. Tất cả các giao tiếp như trên được gọi là các ứng dụng của cơ sở dữ liệu truyền thống. Trong các cơ sở dữ liệu truyền thống, hầu hết các thông tin được lưu giữ và truy cập là văn bản hoặc số. Những năm gần đây, những tiến bộ về kỹ thuật đã đưa đến những ứng dụng mới của cơ sở dữ liệu. Các cơ sở dữ liệu đa phương tiện bây giờ có thể lưu trữ hình ảnh, phim và tiếng nói. Các hệ thống thông tin địa lý có thể lưu trữ và phân tích các bản đồ, các dữ liệu về thời tiết và các ảnh vệ tinh. Kho dữ liệu và các hệ thống phân tích trực tuyến được sử dụng trong nhiều công ty để lấy ra và phân tích những thông tin có lợi từ các cơ sở dữ liệu rất lớn nhằm đưa ra các quyết định. Các kỹ thuật cơ sở dữ liệu động và thời gian thực được sử dụng trong việc kiểm tra các tiến trình công nghiệp và sản xuất. Các kỹ thuật tìm kiếm cơ sở dữ liệu đang được áp dụng cho World Wide Web để cung cấp việc tìm kiếm các thông tin cần thiết cho người sử dụng bằng cách duyệt qua Internet. Để hiểu được các cơ sở kỹ thuật của cơ sở dữ liệu chúng ta phải bắt đầu từ những khái niệm cơ bản về cơ sở dữ liệu. Mục đích của chương này là định nghĩa cơ sở dữ liệu quan hệ, các phép toán trên cơ sở dữ liệu quan hệ và cơ sở dữ liệu phân tán. 1.1.1 Khái niệm về CSDL quan hệ Trong cơ sở dữ liệu quan hệ, dữ liệu được lưu trữ dưới dạng các bảng, gọi là các quan hệ. Mỗi một dòng trong bảng biểu thị một sự kiện tương ứng với một thực thể 13 hoặc một liên kết của thế giới thực. Tên bảng và tên cột dùng để giải thích ý nghĩa của các giá trị trong mỗi hàng. Mọi giá trị trong cùng một cột có cùng một kiểu dữ liệu. Theo thuật ngữ mô hình quan hệ hình thức, mỗi hàng được gọi là một bộ, mỗi cột được gọi là thuộc tính và bảng được gọi là một quan hệ. Số lượng các thuộc tính có trong một quan hệ gọi là mức(grade), số lượng các bộ gọi là lực lượng(cardinality) của quan hệ đó. Để hiểu rõ hơn các khái niệm nêu trên chúng ta xét ví dụ sau đây: Bảng 1-1 biểu diễn quan hệ EMP (NHÂN VIÊN) gồm 4 thuộc tính: EMPNUM (Mã số nhân viên), NAME (Tên nhân viên), AGE (Tuổi), DEPTNUM (Mã số phòng ban) và 5 bộ, ví dụ (18, Mary, 31, 1) là một bộ. Quan hệ này có 4 thuộc tính do vậy mức của quan hệ này là 4 và lực lượng của quan hệ này là 5. EMPNUM 3 7 11 15 18 NAME Jones Smith Bob Jane Mary AGE 23 45 18 27 31 DEPTNUM 1 2 1 3 1 Bảng 1-1 Quan hệ EMP Một lược đồ quan hệ được tạo nên từ tên một quan hệ và danh sách các thuộc tính của nó, kí hiêu một lược đồ quan hệ như sau: (). Ví dụ: EMP(EMPNUM, NAME, AGE, DEPTNUM) là lược đồ quan hệ của quan hệ EMP ở trên. Tập hợp các giá trị có thể có của một thuộc tính gọi là miền của thuộc tính. Ví dụ, EMPNUM lấy giá trị từ miền mã số nhân viên, là các số nguyên dương, AGE có miền giá trị từ tuổi, giá trị từ 0 tới 100. Có thể tồn tại những giá trị giống nhau giữa hai miền nhưng về bản chất nó thuộc về hai miền hoàn toàn khác nhau, do vậy không thể so sánh các giá trị của những miền khác nhau. Ví dụ, thật vô nghĩa khi so sánh tuổi với mã số nhân viên. 14 Một số khía cạnh quan trọng định nghĩa cơ sở dữ liệu quan hệ: 9 Không bao giờ có hai bản ghi giống hệt nhau trong một quan hệ. 9 Không có quy định về thứ tự các bản ghi trong một quan hệ. Một quan hệ được định nghĩa như một tập hợp các bộ. Các phần tử trong một tập hợp không có thứ tự, vì vậy các bộ trong một quan hệ không có một thứ tự cụ thể. Trong thực tế, không phải tất cả hệ quản trị cơ sở dữ liệu quan hệ nào cũng tuân thủ chặt chẽ quy định này. Vì vậy, trong một số hệ quan trị cở sở dữ liệu vẫn tồn tại các bản ghi nhân bản và vẫn đưa ra một thứ tự sắp xếp ngầm nào đó để thuận tiện trong quá trình xử lý. Người ta cũng đưa ra một định nghĩa khác về quan hệ dựa trên khái niệm về miền. Trong định nghĩa này, người ta cho tập hợp các miền D1, D2,…, Dn có gán thứ tự ưu tiên, quan hệ mức n của các miền này là tập con của tích Đề Các của chúng. Chính xác hơn, quan hệ R là tập hợp các bản ghi có thứ tự (d1, d2,…, dn) trong đó d1 thuộc miền D1, d2 thuộc miền D2,…, dn thuộc miền Dn. Định nghĩa này rất hữu dụng trong việc phân tích các tính chất của mô hình quan hệ và đại số. Trong tài liệu này, chúng ta coi thứ tự các cột trong một quan hệ là không quan trọng. Điều này có nghĩa chúng ta coi quan hệ là ánh xạ từ tập tên của các thuộc tính tới tập giá trị tương ứng. Vì vậy, quan hệ EMP1 dưới đây cũng giống quan hệ EMP ở hình 1-1. EMPNUM 3 7 11 15 18 AGE 23 45 18 27 31 Bảng 1-2 DEPTNUM 1 2 1 3 1 Quan hệ EMP1 NAME Jones Smith Bob Jane Mary 15 1.1.1.1 Khóa Một quan hệ được định nghĩa như một tập hợp các bộ. Theo định nghĩa, các phần tử của một tập hợp là khác nhau, vì vậy, mọi bộ trong một quan hệ phải khác nhau. Điều đó có nghĩa là không có hai bộ có cùng một tổ hợp giá trị cho tất cả các thuộc tính của chúng. Thông thường, tồn tại tập con của các thuộc tính của một quan hệ có tính chất: không có hai bộ nào có cùng một tổ hợp giá trị cho các thuộc tính của nó. Giả sử chúng ta ký hiệu tập con như vậy là SK, khi đó với hai bộ khác nhau bất t1 và t2 trong quan hệ R chúng ta có ràng buộc là t1[SK] # t2[SK]. Tập hợp SK như vậy gọi là siêu khóa của lược đồ quan hệ R. Mỗi quan hệ có ít nhất một siêu khóa mặc định, đó là tập hợp tất cả các thuộc tính của nó. Một khóa K của lược đồ quan hệ R là một siêu khóa của R với tính chất nếu bỏ đi bất kì thuộc tính nào ra khỏi K thì sẽ còn lại một tập K không phải là siêu khóa của R. Như vậy, một khóa là một siêu khóa tối thiểu, nghĩa là đó là một siêu khóa mà ta không thể vứt bỏ thuộc tính nào rời khỏi nó mà vẫn giữ được ràng buộc về tính duy nhất. Tính chất quan trọng của khóa là duy nhất về mặt ngữ nghĩa, chúng ta không coi một thuộc tính là khóa chỉ vì nó thỉnh thoảng mới định danh cho một bản ghi nào đó. Trong bảng 1-1, EMPNUM(mã số nhân viên) là khóa của quan hệ EMP, bởi vì không có hai bộ nhân viên có cùng một giá trị cho EMPNUM(mã số nhân viên). Mọi tập hợp thuộc tính có chứa EMPNUM(mã số nhân viên), ví dụ {EMPNUM, AGE}, đều là một siêu khóa. Tuy nhiên, siêu khóa {EMPNUM, AGE} không phải là khóa vì nếu bỏ thuộc tính AGE đi thì nó vẫn còn là một siêu khóa. Một khóa được xác định từ ý nghĩa của thuộc tính và tính chất là bất biến, tính chất đó phải thỏa mãn khi chúng ta chèn một bộ mới vào quan hệ. Ví dụ: chúng ta không thể và không được chỉ định thuộc tính NAME(Tên nhân viên) làm khóa vì không có gì đảm bảo rằng không tồn tại hai nhân viên có cùng họ tên. Nói chung, một lược đồ quan hệ có thể có nhiều hơn một khóa. Trong trường hợp đó, mỗi khóa được gọi là một khóa dự tuyển. Thông thường ta phải chỉ định một trong 16 các khóa dự tuyển làm khóa chính của quan hệ. Khóa chính là một khóa dự tuyển mà các giá trị của chúng được dùng để xác định các bộ trong quan hệ. Chú ý rằng, khi một lược đồ quan hệ có nhiều khóa dự tuyển thì việc lựa chọn khóa chính là tùy ý, tuy nhiên tốt nhất là chọn khóa chính gồm một thuộc tính hoặc có số thuộc tính ít nhất. 1.1.2 Các phép toán đại số quan hệ Ngoài việc định nghĩa cấu trúc cơ sở dữ liệu và các ràng buộc, một mô hình dữ liệu phải chứa một tập hợp các phép toán để thao tác dữ liệu. Tập hợp cơ sở các phép toán mô hình quan hệ tạo nên đại số quan hệ. Các phép toán này giúp cho người sử dụng xác định rõ yêu cầu lấy tin cơ bản. Kết quả của phép lấy tin là một quan hệ mới, có thể được tạo ra từ một hoặc nhiều quan hệ. Các phép toán quan hệ đại số chia làm hai nhóm. Một nhóm bao gồm các phép toán tập hợp lấy từ lý thuyết tập hợp toán học. Các phép toán đó là phép hợp, phép giao, phép trừ tập hợp và phép tích Đề Các. Nhóm kia bao gồm những phép toán được xây dựng đặc biệt cho các cơ sở dữ liệu quan hệ. Các phép toán đó là phép chiếu, phép chọn, phép nối và một số phép khác. 1.1.2.1 Phép chọn Phép chọn được sử dụng để chọn ra một tập hợp các bộ thỏa mãn điều kiện chọn từ một quan hệ. Ta có thể xem phép chọn như bộ lọc, nó chỉ giữ lại những bộ thỏa mãn điều kiện đặt ra. Phép chọn được kí hiệu như sau: σ< điều kiện chọn>( R) Trong đó σ được dùng để kí hiệu phép chọn, <điều kiện chọn> là một biểu thức logic được chỉ ra trên các thuộc tính của R. Chú ý rằng R nói chung là một biểu thức đại số quan hệ. Kết quả của một biểu thức đại số quan hệ là một quan hệ. Biểu thức đơn giản nhất chính là tên của một quan hệ của một cơ sở dữ liệu. Quan hệ kết quả của phép 17 chọn có cùng thuộc tính như R. Ví dụ: Ta xét quan hệ NHÂNVIÊN như sau MãNV 01 02 04 05 TênNV David Mary John Cathy Lương 2000 3500 1200 5600 Bảng 1-3 Quan hệ NHÂNVIÊN Để chọn ra các bộ NHÂNVIÊN có lương lớn hơn 2000 ta viết như sau: σ< Lương > 2000>( NHÂNVIÊN) Kết quả trả về như dưới đây: MãNV 02 05 TênNV Mary Cathy Lương 3500 5600 Bảng 1-4 Kết quả phép chọn Biểu thức logic chỉ ra trong <điều kiện chọn> được tạo nên từ một số hạng mục có dạng : hoặc trong đó là tên của một thuộc tính trong R, là một trong các phép toán so sánh {<, >, ≤, ≥, ≠, =}, là một giá trị hằng từ miền giá trị của thuộc tính. Các hạng mục có thể được nối với nhau bằng các phép toán logic AND, OR, NOT để tạo ra một điều kiện chọn chung. Phép chọn là phép toán có tính chất giao hoán, nghĩa là : σ< điều kiện chọn 1>( σ< điều kiện chọn 2>( R)) = σ< điều kiện chọn 2>( σ< điều kiện chọn 1>( R)) 18 1.1.2.2 Phép chiếu Nếu ta coi quan hệ như một bảng thì phép chọn chọn một số hàng của bảng thỏa mãn điều kiện chọn và bỏ qua các hàng không thỏa mãn điều kiện chọn. Phép chiếu là phép toán chọn một số cột của bảng. Nếu chúng ta chỉ quan tâm đến một số thuộc tính trong quan hệ, chúng ta dùng phép chiếu để chiếu lên các thuộc tính đó. Phép chiếu được kí hiệu là: π( R) Trong đó π là kí hiệu dùng để biểu diễn phép chiếu và là một danh sách con các thuộc tính của quan hệ R. Nói chung R là một biểu thức đại số quan hệ. Trường hợp đơn giản nhất nó là tên một quan hệ của cơ sở dữ liệu. Kết quả của phép chiếu là một quan hệ chỉ có các thuộc tính nằm trong và có cùng thứ tự như thứ tự của chúng trong danh sách. Nếu không bao gồm thuộc tính khóa của R thì quan hệ kết quả có thể có những bộ trùng nhau. Phép chiếu không có tính chất giao hoán. Ví dụ: Ta xét quan hệ NHÂNVIÊN như bảng 1-3. Phép chiếu π( NHÂNVIÊN) có kết quả như sau: TênNV David Mary John Cathy Lương 2000 3500 1200 5600 Bảng 1-5 Kết quả phép chọn 1.1.2.3 Các phép toán lý thuyết tập hợp Nhóm tiếp theo của các phép toán đại số quan hệ là các phép toán toán học thông 19 thường trên các tập hợp. Đó là các phép giao, hợp và trừ tập hợp. Các phép toán này là phép toán hai ngôi, nghĩa là mỗi phép toán được áp dụng cho hai tập hợp. Khi áp dụng phép toán này cho cơ sở dữ liệu quan hệ, hai quan hệ tham gia vào một trong phép toán trên phải có kiểu của các bộ như nhau, hay nói cách khác, chúng phải có cùng một cấu trúc. Điều đó có nghĩa là, hai quan hệ có cùng số các thuộc tính và mỗi cặp thuộc tính tương ứng có cùng miền giá trị. Các phép toán được định nghĩa như sau : Phép hợp: Hợp của hai quan hệ R và S, kí hiệu là R ∪ S, cho kết quả là một quan hệ chứa tất cả các bộ có trong R hoặc trong S hoặc trong cả hai. Các bộ trùng lặp bị loại bỏ. Phép giao: Giao của hai quan hệ R và S, kí hiệu là R ∩ S, cho kết quả là một quan hệ chứa tất cả các bộ có trong cả hai quan hệ R và S. Phép trừ quan hệ. Phép trừ quan hệ R và S, được kí hiệu là R – S, cho kết quả là một quan hệ chứa tất cả các bộ có trong R nhưng không có trong S. Ví dụ: R HọTên AA BB CC DD Tuổi 20 18 21 25 GiớiTính Nam Nữ Nam Nữ S HọTên BB EE DD FF Tuổi 18 20 25 21 GiớiTính Nữ Nam Nữ Nam R∪S HọTên AA BB CC DD EE FF Tuổi 20 18 21 25 20 21 GiớiTính Nam Nữ Nam Nữ Nam Nam R∩S HọTên BB DD Tuổi 18 25 GiớiTính Nữ Nữ R-S HọTên AA CC Tuổi 20 21 GiớiTính Nam Nam Bảng 1-6 Kết quả của các phép toán tập hợp 20 Các phép toán hợp và giao có tính chất giao hoán, nghĩa là : R ∪ S = S ∪ R và R∩S=S∩R Các phép toán trên cũng có tính chất kết hợp, nghĩa là : R ∪ (S ∪ T) = (R ∪ S) ∪ T R ∩ (S ∩ T) = (R ∩ S) ∩ T và Phép trừ tập hợp không có tính chất giao hoán. Ngoài các phép toán trên, còn một phép toán gọi là tích Đề Các. Tích Đề Các còn gọi là tích hỗn hợp(cross product), được kí hiệu là ×. Đó cũng là phép toán hai ngôi nhưng quan hệ mà nó áp dụng trên đó không phải là tương thích đồng nhất. Phép toán này được sử dụng để nối các bộ của hai quan hệ vào một kiểu kết hợp. Kết quả của R(A1, A2, ..., An) × S(B1, B2, ..., Bm) là một quan hệ Q với n + m thuộc tính Q(A1, A2, ..., An, B1, B2, ..., Bm). Quan hệ Q có các bộ được tạo thành do sự kết hợp một bộ của R và một bộ của S. Ví dụ, xét hai quan hệ sau : R A1 aa ab A2 bb ac A1 R×S S aa ab aa ab B1 cc dd A2 bb ac bb ac B1 cc cc dd dd Bảng 1-7 Tích Đề Các của hai quan hệ R và S 1.1.2.4 Phép nối Phép nối được kí hiệu là và được dùng để kết hợp các bộ có liên hệ với nhau từ hai quan hệ thành một bộ. Phép toán này rất quan trọng đối với cơ sở dữ liệu