Tài liệu Một số phụ thuộc hàm mở rộng trong mô hình dữ liệu dạng khối

1 Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo TS Trịnh Đình Vinh, người đã tận tình hướng dẫn, giúp đỡ và động viên tôi trong suốt quá trình làm luận văn. Xin cám ơn tập thể cán bộ, giáo viên công nhân viên trường trung cấp nghề Kỹ thuật xây dựng và Nghiệp vụ đã tạo điều kiện hết sức để tôi được học tập và hoàn thành khóa học được thuận lợi. Xin chân thành cảm ơn các thầy giáo, cô giáo đã trực tiếp giảng dạy và mang đến cho tôi niềm say mê nghiên cứu khoa học. Tôi xin gửi lời biết ơn chân thành tới đồng nghiệp, bạn bè, gia đình đã luôn tạo điều kiện, ủng hộ về mọi mặt để tôi hoàn thành luận văn. Hà Nội, tháng 12 năm 2013 Tác giả luận văn Trịnh Thị Thuy 1 LỜI CAM ĐOAN Tôi xin cam đoan đây là kết quả nghiên cứu của tôi dưới sự hướng dẫn khoa học của thầy TS Trịnh Đình Vinh. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Học viên Trịnh Thị Thuy 1 MỞ ĐẦU 1. Lý do chọn đề tài Trong những thập niên gần đây, việc ứng dụng công nghệ thông tin trở nên rộng rãi và vai trò của công nghệ thông tin ngày càng được khẳng định trong nhiều lĩnh vực khác nhau như: Học tập, khoa học kỹ thuật, kinh doanh,... dưới nhiều quy mô khác nhau. Với việc sử dụng các ứng dụng của công nghệ, lượng dữ liệu được sử dụng ngày càng tăng và việc xây dựng các mô hình quản lý dữ liệu trên ngày càng cấp thiết và ảnh hưởng rất lớn đến giá trị sử dụng của dữ liệu. Từ đó, đã có nhiều mô hình cơ sở dữ liệu được ra đời nhằm đáp ứng nhu cầu trên như: Mô hình dữ liệu thực thể - liên kết, mô hình dữ liệu mạng, mô hình dữ liệu phân cấp, mô hình hướng đối tượng, mô hình dữ liệu quan hệ, mô hình dữ liệu khối. Trong đó, mô hình dữ liệu dạng khối là mở rộng của các mô hình đang được sử dụng rất phổ biến là mô hình dữ liệu quan hệ và mô hình thực thể liên kết. Mô hình dữ liệu khối thể hiện mối quan hệ giữa dữ liệu với các thông tin thực tế một cách tự nhiên hơn. Trong quá trình nghiên cứu về mô hình dữ liệu khối thì việc xây dựng và phân tích mối quan hệ phụ thuộc dữ liệu đóng vai trò quan trọng trong việc thiết kế và xây dựng cơ sở dữ liệu. Việc khai phá lớp phụ thuộc hàm có yếu tố quyết định trong việc thiết kế lược đồ khối và mối quan hệ giữa các khối bên trong lược đồ khối. Từ đó, trong luận văn này nghiên cứu các dạng phụ thuộc hàm của mô hình dữ liệu khối. Đặc biệt là hai dạng phụ thuộc hàm là phụ thuộc hàm mạnh và phụ thuộc hàm yếu. Vì vậy, em lựa chọn đề tài nghiên cứu là: “Một số phụ thuộc hàm mở rộng trong mô hình dữ liệu dạng khối ” nhằm góp phần hoàn thiện hơn lý thuyết về mô hình dữ liệu dạng khối. 2 2. Mục đích nghiên cứu Tìm hiểu về mối quan hệ giữa các khối trong lược đồ khối. Tiến hành nghiên cứu về các phụ thuộc hàm trên khối như: phụ thuộc hàm đa trị, phụ thuộc hàm mạnh, phụ thuộc hàm yếu… Đồng thời tìm hiểu mối quan hệ giữa các phụ thuộc hàm mạnh, yếu và ý nghĩa của chúng. 3. Nhiệm vụ nghiên cứu Tìm hiểu về mô hình cơ sở dữ liệu dạng khối Tìm hiểu các mối quan hệ giữa các khối trong lược đồ khối Nghiên cứu và đề xuất các phụ thuộc hàm mới trong mô hình cơ sở dữ liệu dạng khối. 4. Đối tượng và phạm vi nghiên cứu Đối tượng, phạm vi nghiên cứu về phụ thuộc hàm, các khái niệm cơ bản về phụ thuộc hàm mạnh , phụ thuộc hàm yếu và mối quan hệ giữa chúng. 5. Phương pháp nghiên cứu Thu thập tài liệu, phân tích, suy luận, tổng hợp, đánh giá. Từ đó, đề xuất các khái niệm liên quan đến phụ thuộc hàm trong cơ sở dữ liệu dạng khối. 6. Những đóng góp mới của đề tài - Phát biểu định nghĩa, chứng minh các mệnh đề về phụ thuộc hàm mạnh trong mô hinh dữ liệu khối. - Phát biểu định nghĩa, chứng minh các mệnh đề về phụ thuộc hàm yếu trong mô hinh dữ liệu khối. - Mối quan hệ giữa phụ thuộc hàm mạnh và yếu trong mô hình dữ liệu khối. 7. Cấu trúc của luận văn Luận văn gồm: Lời mở đầu, ba chương nội dung, phần kết luận và tài liệu tham khảo. 3 Chương 1: Các mô hình dữ liệu Chương này giới thiệu tóm tắt các mô hình dữ liệu đã được nghiên cứu. Đầu tiên là mô hình dữ liệu thực thể - liên kết, mô hình dữ liệu mạng, mô hình dữ liệu phân cấp, mô hình hướng tới đối tượng và mô hình dạng datalog. Phần cuối của chương trình bày mô hình dữ liệu quan hệ, trong đó có nêu nội dung phần phụ thuộc hàm mạnh, phụ thuộc hàm yếu. Chương 2: Mô hình cơ sở dữ liệu dạng khối Chương này trình bày các khái niệm cơ bản về mô hình dữ liệu dạng khối như : định nghĩa khối, lát cắt, lược đồ khối, đại số trên khối, khóa của khối, phụ thuộc hàm trên khối…. được trình bày. Chương 3: Một số phụ thuộc hàm mở rộng trên mô hình cơ sở dữ liệu dạng khối Chương này trình bày các nội dung liên quan đến phụ thuộc hàm mạnh và phụ thuộc hàm yếu trong mô hình cơ sở dữ liệu dạng khối: định nghĩa phụ thuộc hàm mạnh và yếu, các tính chất liên quan, mối quan hệ giữa các phụ thuộc hàm mạnh, yếu. 4 CHƯƠNG 1: CÁC MÔ HÌNH DỮ LIỆU 1.1. Mô hình dữ liệu thực thể - liên kết. 1.1.1 Thực thể [1], [2] Thuật ngữ “thực thể” (entity) không có một định nghĩa hình thức, cũng giống như các thuật ngữ “điểm” và “đường” trong hình học ngầm được định nghĩa bằng các tiên đề về các đặc tính của chúng. Ta có thể nói rằng: thực thể là một sự vật tồn tại và phân biệt được, nghĩa là có thể phân biệt thực thể này với thực thể khác. Một nhóm bao gồm tất cả các thực thể “tương tự” tạo ra một tập thực thể (entity set). Tính “tương tự” ít nhất cũng đủ hiểu rằng có thể tìm được một tập các đặc tính chung cho tất cả các phần tử của một tập thực thể. Các đặc tính của tập thực thể gọi là các thuộc tính. Thuộc tính của thực thể bao gồm các loại sau: - Thuộc tính định danh (còn gọi là định danh thực thể, đôi khi còn gọi là thuộc tính khoá): Là một hoặc một số thuộc tính mà giá trị của nó cho phép phân biệt các thực thể khác nhau. Một thực thể bao giờ cũng được xác định một thuộc tính định danh làm cơ sở để phân biệt các thể hiện cụ thể của nó. Ví dụ : Số hiệu khách hàng, Mã mặt hàng, Mã sinh viên,... Thuộc tính mô tả: Là các thuộc tính mà giá trị của chúng chỉ có tính mô tả cho thực thể hay liên kết mà thôi. Hầu hết các thuộc tính trong một kiểu thực thể đều là mô tả. Có một số thuộc tính mô tả đặc biệt như sau: - Thuộc tính tên gọi: là thuộc tính mô tả để chỉ tên các đối tượng thuộc thực thể. Thuộc tính tên gọi để phân biệt các thực thể (tách các thực thể). - Thuộc tính kết nối (thuộc tính khoá ngoài): là thuộc tính chỉ ra mối quan 5 hệ giữa một thực thể đã có và một thực thể trong bảng khác. Thuộc tính kết nối giống thuộc tính mô tả thông thường trong thực thể chứa nó nhưng nó lại là thuộc tính khoá của một thực thể trong bảng khác. 1.1.2 Liên kết và các kiểu liên kết [1], [2] Liên kết (còn gọi là quan hệ) là sự kết hợp giữa hai hay nhiều thực thể phản ánh sự rang buộc trong quản lý. Đặc biệt: Một thực thể có thể liên kết với chính nó ta thường gọi là tự liên kết. Giữa hai thực thể có thể có nhiều hơn một liên kết. Có ba kiểu liên kết: một - một, một - nhiều, nhiều - nhiều. - Liên kết một - một (1-1): Mỗi thể hiện của thực thể A quan hệ với một thể hiện của thực thể B và ngược lại. Ví dụ: Một học viên có một luận văn, một luận văn thuộc về một học viên - Liên kết một - nhiều (1-N): Mỗi thể hiện của thực thể A quan hệ với nhiều thể hiện của thực thể B. Ngược lại mỗi thể hiện của thực thể B quan hệ với chỉ một thể hiện của thực thể A. Ví dụ: Một khoa có nhiều sinh viên, nhiều sinh viên thuộc về một khoa - Liên kết nhiều - nhiều (N-N): Mỗi thể hiện của thực thể A quan hệ với nhiều thể hiện của thực thể B. Ngược lại mỗi thể hiện của thực thể B quan hệ với nhiều thể hiện của thực thể A. Ví dụ: Một giáo viên dạy nhiều sinh viên. Một sinh viên được dạy bởi nhiều giáo viên. Mục đích của mô hình này là cho phép mô tả lược đồ khái niệm của một tổ chức mà không cần chú ý đến tính hiệu quả hoặc các chi tiết thiết kế cơ sở dữ liệu vật lý. Mô tả bằng hình ảnh: Mô hình thực thể liên kết 6 Hình 1.1 Mô hình thực thể liên kết * Nhận xét: - Ưu điểm: Dễ dàng biểu diễn cái mà con người nhận thức từ thế giới thực. Biểu diễn ngữ nghĩa phong phú của các thực thể và quan hệ giữa các thực thể. - Nhược điểm: Không dễ dàng ánh xạ vào những cấu trúc lưu trữ trên máy. 1.2. Mô hình dữ liệu mạng Mô hình dữ liệu mạng (Network Data Model) hay gọi tắt là mô hình mạng (Network Model) là mô hình được biểu diễn bởi một đồ thị có hướng. Mô hình này được xây dựng bởi Honeywell vào năm 1964-1965. Trong mô hình này, có 3 khái niệm được sử dụng: mẫu tin hay bản ghi (record), loại mẫu tin (record type) và loại liên hệ (set type). Loại mẫu tin: đặc trưng cho một loại đối tượng riêng biệt. Chẳng hạn như trong quản lý nhân sự tại một đơn vị thì đối tượng cần phản ảnh của thế giới thực có thể là: phòng, nhân viên, công việc, lý lịch,… do đó có các loại mẫu tin đặc trưng cho từng đối tượng này. Trong mô hình mạng, mỗi loại mẫu 7 tin được thể hiện bằng một hình chữ nhật, một thể hiện (instance) của một loại mẫu tin được gọi là bản ghi (record). Ở ví dụ trên loại mẫu tin phòng có các mẫu tin là các phòng ban trong công ty, loại mẫu tin Nhân viên có các mẫu tin là các nhân viên đang làm việc tại các phòng ban của công ty,… Loại liên hệ: là sự liên kết giữa một loại mẫu tin chủ với một mẫu tin thành viên. Trong mô hình mạng, một loại liên hệ được thể hiện bằng hình bầu dục và sự liên kết giữa hai loại mẫu tin được thể hiện bằng các cung có hướng đi từ loại mẫu tin chủ đến loại liên hệ và từ loại liên hệ đến loại mẫu tin thành viên. Trong loại liên kết người ta còn chỉ ra số lượng các mẫu tin tham gia vào trong mối kết hợp. Có một số loại sau: • 1÷ 1 (One to One): Mỗi mẫu tin của loại mẫu tin chủ kết hợp với đúng 1 mẫu tin của loại mẫu tin thành viên. Ví dụ, mỗi nhân viên có duy nhất một lý lịch cá nhân. • 1÷ n (One to Many): Mỗi mẫu tin của loại mẫu tin chủ kết hợp với 1 hay nhiều mẫu tin của loại mẫu tin thành viên. Ví dụ, mỗi phòng ban có thể có một hoặc nhiều nhân viên. • n ÷ 1 (Many to One): Nhiều mẫu tin của loại mẫu tin chủ kết hợp với đúng 1 mẫu tin của loại mẫu tin thành viên. Ví dụ, nhiều nhân viên cùng làm một công việc. • Đệ quy (Recursive): Một loại mẫu tin chủ cũng có thể đồng thời là mẫu tin thành viên với chính nó. Ví dụ, trưởng phòng cũng là một nhân viên thuộc phòng trong công ty. 8 Hình 1.2: Mô hình dữ liệu mạng *Nhận xét: - Ưu điểm: đơn giản, dễ sử dụng. Có thể biểu diễn các ngữ nghĩa đa dạng với kiểu bản ghi và kiểu móc nối. Truy vấn thông qua phép duyệt đồ thị. - Nhược điểm: Số lượng các con trỏ lớn. Hạn chế biểu diễn bởi ngữ nghĩa của các móc nối giữa các bản ghi. 1.3. Mô hình dữ liệu phân cấp [1], [2] Mô hình dữ liệu phân cấp (Hieracical Data Model), còn gọi là mô hình phân cấp (Hieracical Model), được thực hiện thông qua sự kết hợp giữa IBM và North American Rockwell vào khoảng năm 1965. Mô hình là một cây, trong đó mỗi nút của cây biểu diễn một thực thể, giữa nút con với nút cha được liên hệ với nhau theo một mối quan hệ xác định. Đường lối ở đây nếu được biểu diễn bằng một mũi tên sẽ đi từ con đến cha để biểu thị khái niệm “Xác định duy nhất” chứ không phải đường duyệt qua cơ sở dữ liệu theo nghĩa ngược lại. 9 Các thể hiện của cơ sở dữ liệu trong mô hình phân cấp tương ứng với một lược đồ sẽ chứa một tập các cây có các nút là mẫu tin, mỗi cây được gọi là một mẫu tin cơ sở dữ liệu tương ứng với một cây trong lược đồ cơ sở dữ liệu và mẫu tin gốc của một mẫu tin cơ sở dữ liệu tương ứng với một thực thể của kiểu mẫu tin gốc. Loại mẫu tin: giống trong mô hình dữ liệu mạng Loại mối liên hệ: kiểu liên hệ là phân cấp. * Nhận xét: - Ưu điểm: Dễ xây dựng và thao tác. Tương thích với các lĩnh vực tổ chức và phân cấp. Ngôn ngữ thao tác đơn giản. - Nhược điểm: Sự lặp lại của các bản ghi dư thừa dữ liệu và dữ liệu không nhất quán. Hạn chế biểu diễn ngữ nghĩa của các móc nối giữa các bản ghi(chỉ cho phép quan hệ 1->n). 1.4. Mô hình dữ liệu hướng đối tượng [1], [6] Được ra đời vào những năm 1990, một đặc điểm chung của mô hình hướng đối tượng là chúng hỗ trợ: - Đặc tính nhận dạng đối tượng (Object Identity): các thành phần chúng xử lí điển hình là những mẫu tin, có địa chỉ duy nhất giống như trong mô hình mạng và mô hình phân cấp. - Các đối tượng phức (Complex object): cho phép xây dựng một kiểu mới bằng thao tác tạo lập mẫu tin hoặc tạo lập tập hợp. - Phân cấp theo kiểu (Type hierarchy): cho phép những kiểu có thể có những kiểu con và có thuộc tính riêng. Tập tất cả các cấu trúc đối tượng (object structure) được định nghĩa trong mô hình này rất gần với tập các lược đồ cho các mẫu tin cơ sở dữ liệu trong mô hình phân cấp. Một mô hình hướng đối tượng không bị giới hạn trong khái niệm kiểu 10 đối tượng. Khái niệm cơ bản thực sự là lớp (class), đó là một kiểu đối tượng làm cấu trúc dữ liệu nền tảng và một tập các phương pháp (method), đó là các thao tác được thực hiện trên các đối tượng có cấu trúc thuộc về lớp đó. Mô hình hướng đối tượng gắn liền với mô hình phân cấp theo nghĩa là nếu được cho trước một lược đồ phân cấp nào đó, ta có thể mô phỏng nó trong mô hình hướng đối tượng bằng cách xem các con của một nút (gồm tất cả các con là các kiểu mẫu tin ảo) trong lược đồ phân cấp như là các trường trong một cấu trúc đối tượng ứng với n. Các cấu trúc đối tượng cho các con của n lại có các con của chúng là các trường … Như vậy mô hình hướng đối tượng có thể diễn tả mọi cấu trúc của mô hình thực thể - liên kết, tuy nhiên để đảm bảo yêu cầu truy xuất hiệu quả các thông tin cần thiết trong các cấu trúc đối tượng cũng không phải là một công việc đơn giản. * Nhận xét: - Ưu điểm: Cho phép định nghĩa đối tượng phức tạp. Tính chất bao đóng, kế thừa, đa hình. - Nhược điểm: Cấu trúc lưu trữ phức tạp và có thể sử dụng nhiều con trỏ. Khả năng tối ưu hóa các xử lý bị hạn chế trong nhiều trường hợp. 1.5. Mô hình cơ sở dữ liệu quan hệ [2], [6],[8],[10] Mô hình cơ sở dữ liệu quan hệ được E.F.Codd đề xuất năm 1970 1.5.1. Các khái niệm cơ bản [2], [6] 1.5.1.1 Thuộc tính và miền thuộc tính Định nghĩa 1.1 [8],[10] - Thuộc tính là đặc trưng của đối tượng. - Tập tất cả các giá trị có thể có của thuộc tính Ai gọi là miền giá trị của thuộc tính đó, ký hiệu: Dom(Ai) hay viết tắt là DAi Ví dụ 1.1: Đối tượng Sinh viên có các thuộc tính như: MaSV, Hoten, NgSinh, Dchi, ... 11 Miền giá trị của các thuộc tính của đối tượng Sinh viên : Dom(MaSV) = {char(4)} = {‘SV01’, ‘SV02’, ‘SV032’ ...} ; Dom(Hoten) = {char(30)} = {‘Nguyễn Văn A’, ‘Nguyễn Văn B’, ... } ; Dom(NgSinh) = {date} = {‘30/03/78’, 22/12/96, ...} ; Dom(Đchi) ={char(10)} ; {‘HN’, ‘HP’, ‘VP’, …}. 1.5.1.2. Quan hệ, lược đồ quan hệ Định nghĩa 1.2 Cho U= {A1, A2, …, An} là một tập hữu hạn không rỗng các thuộc tính. Mỗi thuộc tính Ai (i=1,2, …, n) có miền giá trị là Dom(Ai) . Khi đó r là một tập các bộ {h1, h2, …, hm} được gọi là quan hệ trên U với hj (j=1, 2, …, m) là một hàm: h j: U → UD Ai ÎU Ai sao cho hj(Ai) Î DAi (i=1, 2, ...,n). Ta có thể xem một quan hệ như một bảng, trong đó mỗi hàng (phần tử) là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc tính. Biểu diễn quan hệ r thành bảng như sau: A1 A2 … An h1 h1(A1) h1(A2) … h1(An) h2 h2(A1) h2(A2) … h2(An) … … … … … hm hm(A1) hm(A2) … Bảng 1.1: Biểu diễn quan hệ r. hm(An) Ví dụ 1.2: Cho quan hệ SINH_VIEN SINHVIEN MaSV HOTEN NGAYSINH DIACHI KHOA t1 SV01 Nguyễn Thị Hòa 24/01/92 Hà Nội Toán t2 SV02 Trần Văn Mạnh 03/05/92 Vĩnh Phúc Lý t3 SV03 Lê Văn Lượng 03/05/92 Ninh Bình Hóa 12 Trong đó các thuộc tính là MaSV: Mã sinh viên; HOTEN: Họ tên; NGAYSINH: ngày sinh; DIACHI: địa chỉ; KHOA: khoa. t1= (SV01, Nguyễn Thị Hòa, 24/01/92, Hà nội, Toán) là một bộ của quan hệ SINH_VIEN. Nếu có một bộ t = (d1, d2, d3, , dm) Î r, r xác định trên U, X Í U thì t(X) (hoặc t.X) được gọi là giá trị của tập thuộc tính X trên bộ t. Định nghĩa 1.3 Tập tất cả các thuộc tính trong một quan hệ cùng với mối liên hệ giữa chúng được gọi là lược đồ quan hệ. Lược đồ quan hệ R với tập thuộc tính U={A1, A2, .., An} được viết là R(U) hoặc R(A1, A2, .., An). 1.5.1.3. Khoá của quan hệ Định nghĩa 1.4 Khoá của quan hệ r xác định trên tập thuộc U={A1, A2, .., An} là tập con K Í U sao cho bất kỳ hai bộ khác nhau t1, t2 Î r luôn thoả t1(K) ≠ t2(K) và bất kỳ tập con thực sự K1 Ì K nào đó đều không có tính chất đó. Tập thuộc tính K’ được gọi là siêu khoá nếu K’ Ê K và K là một khoá của quan hệ r. Ví dụ 1.3: Cho quan hệ SINH_VIEN (ví dụ 1.2), ta có thuộc tính MaSV là khóa của quan hệ. 1.5.2. Các phép toán đại số quan hệ [1], [6],[8],[10] Ngoài việc định nghĩa cấu trúc của cơ sở dữ liệu và các ràng buộc, một mô hình dữ liệu cần phải có một tập các phép toán để thao tác dữ liệu. Ngôn ngữ đại số quan hệ(hay đại số quan hệ) chính là tập hợp các phép toán mà mô hình quan hệ cung cấp và là cơ sở quan trọng của một ngôn ngữ bậc cao được sử dụng để thao tác trên các quan hệ. Vì dữ liệu được biểu diễn dưới dạng các quan hệ nên từ các quan hệ ban 13 đầu được lưu trữ, có thể sử dụng các phép toán của đại số quan hệ để tao ta quan hệ mới, quan hệ mới này chứa thông tin do người dùng yêu cầu. Các phép toán của đại số quân hệ thường được chia làm hai nhóm: Phép toán tập hợp: hợp, giao, trừ, tích Đề-các. Phép toán quan hệ: chiếu, chọn, kết nối, chia. Định nghĩa 1.5 [1], [7],[10] Hai quan hệ r và s được gọi là khả hợp nếu như hai quan hệ này xác định trên cùng tập thuộc tính và các thuộc tính cùng tên có cùng miền giá trị. 1.5.2.1. Phép hợp Phép hợp hai quan hệ khả hợp r và s, kí hiệu là r ⊄ s, là tập tất cả các bộ thuộc r hoặc thuộc s. Ta có: r ⊄ s = {t│ t ⊄ r ⊄ t ⊄s} Ví dụ 1.4: r r⊄s (A B C) x1 y1 s B C) z1 x1 y1 z1 x2 y1 z2 x2 y2 z2 x2 y2 z1 (A B C) x1 y1 z1 x2 y1 z2 x2 y2 z2 x2 y2 z1 (A 1.5.2.2. Phép giao Phép giao của hai quan hệ khả hợp r và s, kí hiệu là r ∩s, là tập tất cả các bộ thuộc cả hai quan hệ r và s. Ta có: r ∩ s = {t│ t ⊄ r ⊄ t ⊄ s} 14 Ví dụ 1.5: r (A B C) x1 y1 x2 x2 r∩s s (A B C) z1 x1 y1 z1 y1 z2 x2 y2 z2 y2 z1 (A B C) x1 z1 y1 1.5.2.3. Phép trừ Phép trừ của hai quan hệ khả hợp r và s, kí hiệu: r - s là tập tất cả các bộ thuộc r nhưng không thuộc s. Ta có: r - s = {t│ t ⊄ r ⊄ t ⊄ s} Ví dụ 1.6: r (A B C) x1 y1 B C) z1 x1 y1 z1 x2 y1 z2 x2 y2 z2 x2 y2 z1 r - s = (A B C) s - r = (A B C) x2 y1 z2 z2 s (A x2 y2 z2 y2 z1 * Chú ý: Từ định nghĩa phép giao và phép trừ của 2 quan hệ r và s cho thấy Phép giao của 2 quan hệ r ∩ s có thể biểu diễn thông qua phép trừ: r ∩ s =r-(r-s) 1.5.2.4. Tích Đề-các Cho quan hệ r xác định trên tập thuộc tính {A1, A2, .., An} và quan hệ s xác định trên tập thuộc tính {B1, B2, .., Bm}. Tích Đề-các của hai quan hệ r và s kí hiệu là r × s, là tập tất cả các (m+n) - bộ có n thành phần đầu tiên là một bộ thuộc r và m thành phần sau là một bộ thuộc s. Ta có: 15 r × s = {t=(a1, a2, .., an, b1, b2, .., bm) │(a1, a2, .., an) ⊄ r ϕ (b1 b2, .., bm) ⊄ s} Ví dụ 1.7 : Ta có các quan hệ r, s r r × s= A x1 x1 x1 x2 x2 x2 x2 x2 x2 A B C x1 y1 x2 x2 B y1 y1 y1 y1 y1 y1 y2 y2 y2 D E F z1 x1 y1 z1 y1 z2 x2 y2 z2 y2 z1 x1 y2 z2 C z1 z1 z1 z2 z2 z2 z1 z1 z1 s G x1 x2 x1 x1 x2 x1 x1 x2 x1 H y1 y2 y2 y1 y2 y2 y1 y2 y2 F z1 z2 z2 z1 z2 z2 z1 z2 z2 Bảng 1.2: Biểu diễn r x s 1.5.2.5. Phép chiếu Cho r là một quan hệ n ngôi xác định trên tập thuộc tính U={A1, A2, .., An}, X là tập con của U. Phép chiếu của quan hệ r trên tập thuộc tính X, kí hiệu là Õ x (r), là tập các bộ của r xác định trên tập thuộc tính X. Ta có: Õ x (r) = {t.X│ t ⊄ r }. Phép chiếu thực chất là phép toán giữ lại một số thuộc tính cần thiết của quan hệ và loại bỏ những thuộc tính không cần thiết. Ví dụ 1.8: 16 r (A B C D) x1 1 x 4 y1 5 y 2 y1 5 z 5 x1 1 x 5 y1 1 y 4 Õ A,B (r) = (A B) Õ BD (r)= (B D) x1 1 1 4 y1 5 5 2 y1 1 5 5 1 5 1.5.2.6. Phép chọn Phép chọn là phép toán lọc lấy ra một tập con các bộ của quan hệ đã cho thoả mãn một điều kiện xác định. Điều kiện đó được gọi là điều kiện chọn hay biểu thức chọn. Biểu thức chọn F được định nghĩa là một tổ hợp logic của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa một biến là một thuộc tính và một giá trị hằng. Biểu thức chọn F cho giá trị đúng hoặc sai đối với mỗi bộ đã cho của quan hệ khi kiểm tra riêng bộ đó. - Các phép toán so sánh trong biểu thức F: >, <, =, ≥, ≠, ≤. - Các phép toán logic trong biểu thức F: ⊄ (và), ⊄ (hoặc), Ø (phủ định). Cho r là một quan hệ và F là một biểu thức logic trên các thuộc tính của r. Phép chọn trên quan hệ r với biểu thức chọn F, kí hiệu là d F (r), là tập tất cả các bộ của r thoả mãn F. Ta có: d F (r) Ví dụ 1.9: Cho quan hệ r = { t│ t⊄r ϕ F(t)}. 17 r dB³ D (r) = (A B C D) 4 y1 5 y 2 y 2 z1 5 z 5 z1 5 z 5 x1 8 x 5 x1 8 x 5 y1 1 y 4 (A B C D) x1 1 x y1 5 1.5.2.7. Phép kết nối Cho quan hệ r xác định trên tập thuộc tính {A1, A2, .., An} và quan hệ s xác định trên tập thuộc tính {B1, B2, .., Bm}. Để định nghĩa phép kết nối của hai quan hệ, trước hết chúng ta làm quen với khái niệm ghép bộ. Giả sử cho hai bộ u=(a1, a2, .., an) và v=(b1, b2, .., bm). Phép gộp bộ u với bộ v, kí hiệu (u,v), được định nghĩa là: (u,v)=(a1, a2, .., an, b1, b2, .., bm). Phép kết nối hai quan hệ thực chất là phép ghép các cặp bộ của hai quan hệ thoả mãn một điều kiện nào đó trên chúng. Điều kiện đó đựợc gọi là điều kiện kết nối hay biểu thức kết nối. Biểu thức kết nối được định nghĩa là phép hội của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa một thuộc tính của quan hệ r và một thuộc tính của quan hệ s. Phép kết nối của quan hệ r với quan hệ s với biểu thức kết nối F được định nghĩa như sau: r >< s= {t (u, v)│ u ⊄ r ⊄ v ⊄ s ⊄ F(t)}. F Tất nhiên ở đây cần giả thiết rằng các phép so sánh của các cặp thuộc tính thuộc hai quan hệ là có nghĩa, hay mỗi giá trị của thuộc tính này có thể so sánh được với mỗi giá trị của thuộc tính kia. Trong trường hợp phép so sánh là “=”, chúng ta gọi phép kết nối đó là phép kết nối bằng. Trường phép hợp kết nối bằng trên các thuộc tính cùng tên của hai quan hệ và sau khi kết nối một trong hai thuộc tính của phép so sánh “=” được loại bỏ thông qua phép chiếu thì phép kết nối này được gọi là kết nối 18 tự nhiên và sử dụng kí hiệu “ * ”. Phép kết nối tự nhiên của hai quan hệ có thể được định nghĩa như sau: r(U) * s(V) = {t.(U⊄V) ⊄ t.U ⊄ r ⊄ t.V ⊄ s}. Ví dụ 1.10: r r >< s = B>E (A B C D) x1 1 x y1 5 z1 s (E F) 4 6 x y 2 4 y 5 z 5 5 z x1 8 x 5 y1 1 y 4 A B C D E F y1 5 y 2 4 y z1 5 z 5 4 z x1 8 x 5 6 x x1 8 x 5 4 y x1 8 x 5 5 z 1.5.2.8. Phép chia Cho r là một quan hệ n ngôi xác định trên tập thuộc tính U và s là một quan hệ m ngôi xác định trên tập thuộc tính V, với V ⊄ U, n > m và s ≠ ⊄, có nghĩa là lực lượng của s là khác 0 hay s có ít nhất một bộ. Phép chia quan hệ r cho quan hệ s, kí hiệu là r ÷ s, là tập tất cả các bộ t sao cho với mọi bộ v ⊄ s thì khi ghép bộ t với bộ v ta được một bộ thuộc r. Ta có: r ÷ s = {t│⊄ v ⊄ s , (t , v) ⊄ r} Ví dụ 1.11: r (A B C D) a b c a b b c s (C D) d c d e f e f e f